Verifiable computing
ચકાસી શકાય તેવું કમ્પ્યુટિંગ (અથવા ચકાસી શકાય તેવી ગણતરી અથવા ચકાસી શકાય તેવું કમ્પ્યુટિંગ) કોમ્પ્યુટરને ચકાસી શકાય તેવા પરિણામો જાળવી રાખીને, કેટલાક કાર્યોની ગણતરીને અન્ય કદાચ અવિશ્વસનીય ગ્રાહકો સુધી પહોંચાડવા માટે સક્ષમ બનાવે છે. અન્ય ગ્રાહકો કાર્યનું મૂલ્યાંકન કરે છે અને કાર્યની ગણતરી યોગ્ય રીતે કરવામાં આવી હતી તેના પુરાવા સાથે પરિણામ પરત કરે છે. આ કલ્પનાની રજૂઆત SETI@home જેવા પ્રોજેક્ટ્સમાં અવિશ્વસનીય વપરાશકર્તાઓ માટે "આઉટસોર્સિંગ" ગણતરીની વધુને વધુ સામાન્ય ઘટનાના પરિણામે અને ક્લાઉડ કમ્પ્યુટિંગ જેવી વધુ શક્તિશાળી ગણતરી સેવામાં કોમ્પ્યુટેશનલ કાર્યોને આઉટસોર્સ કરવાની નબળા ગ્રાહકોની વધતી ઇચ્છાના પરિણામે આવી છે. આ ખ્યાલ બાબાઇ એટ અલ દ્વારા કામ કરવા માટે શરૂ થાય છે, અને વિવિધ શબ્દો હેઠળ અભ્યાસ કરવામાં આવ્યો છે, જેમાં "ગણતરીઓ તપાસવી" (બાબાઇ એટ અલ. ), "પ્રત્યાયોજિત ગણતરીઓ", "પ્રમાણિત ગણતરી", અને ચકાસી શકાય તેવી ગણતરી. ચકાસી શકાય તેવું કમ્પ્યુટિંગ શબ્દ પોતે રોઝારિયો ગેન્નારો, ક્રેગ જેન્ટ્રી અને બ્રાયન પાર્નો દ્વારા ઔપચારિક બનાવવામાં આવ્યો હતો અને મિકાલીની "પ્રમાણિત ગણતરી" નો પડઘો પાડે છે. પ્રેરણા અને ઝાંખી પ્રમાણમાં નબળા કોમ્પ્યુટેશનલ ઉપકરણ (ક્લાયન્ટ) થી વધુ શક્તિશાળી ગણતરી સેવાઓ (કાર્યકર) માટે કોમ્પ્યુટેશનલ કાર્યોને આઉટસોર્સ કરવાની વધતી ઇચ્છા અને અપ્રમાણિક કામદારોની સમસ્યા કે જેઓ વાસ્તવિક કાર્ય કર્યા વિના બુદ્ધિગમ્ય પરિણામો પરત કરવા માટે તેમના ક્લાયન્ટના સોફ્ટવેરમાં ફેરફાર કરે છે, તેમણે ચકાસી શકાય તેવી ગણતરીની કલ્પનાને ઔપચારિક બનાવવા માટે પ્રેરિત કરી. ચકાસી શકાય તેવું કમ્પ્યુટિંગ માત્ર ક્લાયન્ટના ઇનપુટ પર આઉટસોર્સ કરેલા કાર્યનું પરિણામ અને તેની ચોકસાઈના પુરાવા સાથે સંબંધિત નથી, પરંતુ ક્લાયન્ટ શરૂઆતથી કાર્યની ગણતરી કરતાં નોંધપાત્ર રીતે ઓછા કોમ્પ્યુટેશનલ પ્રયત્નો સાથે સાબિતીને ચકાસવામાં સક્ષમ છે. સુરક્ષિત કોપ્રોસેસર્સ, ટ્રસ્ટેડ પ્લેટફોર્મ મોડ્યુલો (ટી. પી. એમ.), ઇન્ટરેક્ટિવ સાબિતીઓ, સંભવિત રીતે ચકાસી શકાય તેવા સાબિતીઓ, કાર્યક્ષમ દલીલો અને મિકાલીના સી. એસ. સાબિતીઓ સહિત અવિશ્વસનીય કામદારો દ્વારા કરવામાં આવેલા કાર્યોની ગણતરીની ચકાસણી કરવા માટે નોંધપાત્ર ધ્યાન આપવામાં આવ્યું છે. આ ચકાસણીઓ કાં તો ક્રિયાપ્રતિક્રિયાશીલ હોય છે જેમાં ક્લાયન્ટને ચોકસાઈના સાબિતીની ચકાસણી કરવા માટે કાર્યકર સાથે ક્રિયાપ્રતિક્રિયા કરવાની જરૂર પડે છે, અથવા બિન-ક્રિયાપ્રતિક્રિયાશીલ પ્રોટોકોલ છે જે રેન્ડમ ઓરેકલ મોડેલમાં સાબિત થઈ શકે છે. નકલ દ્વારા ચકાસણી સૌથી મોટી ચકાસાયેલ ગણતરી (SETI@home) નકલ દ્વારા ચકાસણીનો ઉપયોગ કરે છે. SETI@home ચકાસણી પ્રક્રિયામાં એક ક્લાયન્ટ મશીન અને ઘણા કામદાર મશીનોનો સમાવેશ થાય છે. ક્લાયન્ટ મશીન બહુવિધ કમ્પ્યુટર્સ (ઓછામાં ઓછા 2) ને સમાન કાર્ય એકમો મોકલે છે. જ્યારે પૂરતા પરિણામો વાજબી સમયમાં પરત ન આવે-અકસ્માતે મશીનો બંધ થઈ જવાને કારણે, સંદેશાવ્યવહારમાં ભંગાણ વગેરે-અથવા પરિણામો સંમત ન થાય-ગણતરીની ભૂલો, વાસ્તવમાં કામ કર્યા વિના ખોટી માહિતી સબમિટ કરીને છેતરપિંડી વગેરેને કારણે-પછી ક્લાયન્ટ મશીન અન્ય કામદાર મશીનોને વધુ સમાન વર્ક યુનિટ્સ મોકલે છે. એકવાર પરિણામોની લઘુતમ કોરમ (ઘણીવાર 2) સંમત થઈ જાય, પછી ગ્રાહક ધારે છે કે તે પરિણામો (અને તે કાર્ય એકમના અન્ય સમાન પરિણામો) સાચા છે. ગ્રાહક તમામ મશીનોને ક્રેડિટ આપે છે જે સાચા પરિણામો આપે છે. ચકાસી શકાય તેવી ગણતરી ગેન્નારો એટ અલ. ફંકશન F: {0,1} n → {0,1} m ની ગણતરી પર સહયોગ કરવા માટે બે બહુપદી સમય પક્ષો વચ્ચેના પ્રોટોકોલ તરીકે ચકાસી શકાય તેવી ગણતરી યોજનાની કલ્પનાને વ્યાખ્યાયિત કરી. આ યોજનામાં ત્રણ મુખ્ય તબક્કાઓનો સમાવેશ થાય છેઃ પૂર્વપ્રક્રિયા. આ તબક્કો ગ્રાહક દ્વારા એફ સાથે સંકળાયેલી કેટલીક સહાયક માહિતીની ગણતરી કરવા માટે એકવાર કરવામાં આવે છે. આ માહિતીનો એક ભાગ કાર્યકર સાથે શેર કરવા માટે જાહેર છે જ્યારે બાકીનો ભાગ ખાનગી છે અને ગ્રાહક સાથે રાખવામાં આવે છે. તૈયારી દાખલ કરો. આ તબક્કામાં, ક્લાયન્ટ કાર્યના ઇનપુટ વિશે કેટલીક સહાયક માહિતીની ગણતરી કરે છે. આ માહિતીનો એક ભાગ જાહેર છે જ્યારે બાકીનો ભાગ ખાનગી છે અને ગ્રાહક પાસે રાખવામાં આવે છે. ઇનપુટ ડેટા પર F ની ગણતરી કરવા માટે કામદારને જાહેર માહિતી મોકલવામાં આવે છે. આઉટપુટ ગણતરી અને ચકાસણી. આ તબક્કામાં, કાર્યકર પ્રદાન કરેલા ઇનપુટ પર ફંક્શન F ના એન્કોડેડ આઉટપુટની ગણતરી કરવા માટે ફંક્શન F અને ઇનપુટ સાથે સંકળાયેલી જાહેર માહિતીનો ઉપયોગ કરે છે, જેની ગણતરી અગાઉના બે તબક્કામાં કરવામાં આવે છે. આ પરિણામ પછી અગાઉના તબક્કામાં ગણવામાં આવેલી ખાનગી માહિતીનો ઉપયોગ કરીને કામદાર દ્વારા પરત કરવામાં આવેલા પરિણામને ડીકોડ કરીને આઉટપુટના વાસ્તવિક મૂલ્યની ગણતરી કરીને તેની ચોકસાઈ ચકાસવા માટે ગ્રાહકને પરત કરવામાં આવે છે. ચકાસી શકાય તેવી ગણતરી યોજનાની વ્યાખ્યાયિત કલ્પના ગ્રાહક અને કાર્યકર વચ્ચેની ક્રિયાપ્રતિક્રિયાને બરાબર બે સંદેશાઓમાં ઘટાડે છે, જ્યાં પ્રોટોકોલના વિવિધ તબક્કાઓ દરમિયાન દરેક પક્ષ તરફથી અન્ય પક્ષને એક જ સંદેશ મોકલવામાં આવે છે. સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન ગેન્નારો એટ અલ પર આધારિત એક ઉદાહરણ યોજના. સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન સિસ્ટમ સાથે જોડાયેલી યાઓની ગરબલ્ડ સર્કિટનો ઉપયોગ કરીને કોઈપણ ફંક્શન F માટે ચકાસી શકાય તેવી ગણતરી યોજનાને વ્યાખ્યાયિત કરી. આ ચકાસી શકાય તેવી ગણતરી યોજના વી. સી. ને નીચે પ્રમાણે વ્યાખ્યાયિત કરવામાં આવે છેઃ વી. સી. = (કીજેન, પ્રોબજેન, કમ્પ્યુટ, વેરિફાય) માં નીચે મુજબ ચાર અલ્ગોરિધમ્સનો સમાવેશ થાય છેઃ કીજેન (એફ, λ) → (પી. કે., એસ. કે.): રેન્ડમાઇઝ્ડ કી જનરેશન અલ્ગોરિધમ સુરક્ષા પરિમાણ λ પર આધારિત બે જાહેર અને ખાનગી કીઓ ઉત્પન્ન કરે છે. જાહેર કી લક્ષ્ય કાર્ય F ને એન્કોડ કરે છે અને કાર્યકરને F ની ગણતરી કરવા માટે મોકલવામાં આવે છે. બીજી બાજુ, ગુપ્ત કી ગ્રાહક દ્વારા ખાનગી રાખવામાં આવે છે. પ્રોબજેન (SK, x) → (σx, τx): પ્રોબ્લેમ જનરેશન અલ્ગોરિધમ ગુપ્ત કી SK નો ઉપયોગ કરીને ફંક્શન ઇનપુટ x ને બે મૂલ્યો, જાહેર અને ખાનગીમાં એન્કોડ કરે છે. કર્મચારીને F (x) ની ગણતરી કરવા માટે જાહેર મૂલ્ય σx આપવામાં આવે છે, જ્યારે ગ્રાહક દ્વારા ગુપ્ત મૂલ્ય τx ખાનગી રાખવામાં આવે છે. ગણતરી (પીકે, σx) → σy: કાર્યકર ક્લાયન્ટની જાહેર કી પીકે અને એન્કોડેડ ઇનપુટ σx નો ઉપયોગ કરીને કાર્યના આઉટપુટ y = F (x) ના એન્કોડેડ મૂલ્યની ગણતરી કરે છે. વેરીફાઈએસકે (τx, σy) → વાય વાયઃ ચકાસણી અલ્ગોરિધમ ગુપ્ત કી એસકે અને ગુપ્ત "ડીકોડિંગ" τx બંનેનો ઉપયોગ કરીને કાર્યકરના એન્કોડેડ આઉટપુટ σy ને ફંક્શન એફના વાસ્તવિક આઉટપુટમાં રૂપાંતરિત કરે છે. તે y = F (x) નું આઉટપુટ આપે છે જો σy એ x પર F ના માન્ય આઉટપુટને રજૂ કરે છે, અથવા અન્યથા δ નું આઉટપુટ આપે છે. ગેન્નારો એટ અલ દ્વારા વ્યાખ્યાયિત ચકાસી શકાય તેવી ગણતરી યોજનાનો પ્રોટોકોલ. નીચે પ્રમાણે કામ કરે છેઃ ફંક્શન F ને બુલિયન સર્કિટ તરીકે રજૂ કરવું જોઈએ જેના પર કી જનરેશન અલ્ગોરિધમ લાગુ કરવામાં આવશે. કી જનરેશન અલ્ગોરિધમ જાહેર અને ગુપ્ત કીઓની ગણતરી કરવા માટે આ બુલિયન સર્કિટ પર યાઓની ગેરબ્લિંગ પ્રક્રિયા ચલાવે છે. પબ્લિક કી (પી. કે.) એ તમામ સાઇફરટેક્સ્ટ્સથી બનેલી હોય છે જે ખરબચડી સર્કિટને રજૂ કરે છે, અને સિક્રેટ કી (એસ. કે.) તમામ રેન્ડમ વાયર લેબલોથી બનેલી હોય છે. જનરેટેડ સિક્રેટ કી પછી પ્રોબ્લેમ જનરેશન અલ્ગોરિધમમાં ઉપયોગમાં લેવાય છે. આ અલ્ગોરિધમ પહેલા હોમોમોર્ફિક એન્ક્રિપ્શન યોજના માટે જાહેર અને ગુપ્ત કીઓની નવી જોડી બનાવે છે, અને પછી આ કીનો ઉપયોગ હોમોમોર્ફિક યોજના સાથે યોગ્ય ઇનપુટ વાયરને એન્ક્રિપ્ટ કરવા માટે કરે છે, જે ખરબચડી સર્કિટની ગુપ્ત કી તરીકે રજૂ થાય છે. ઉત્પાદિત સિફરટેક્સ્ટ્સ કામદારને આપવામાં આવતા ઇનપુટ (σx) ના જાહેર એન્કોડિંગનું પ્રતિનિધિત્વ કરે છે, જ્યારે ગુપ્ત કી (τx) ગ્રાહક દ્વારા ખાનગી રાખવામાં આવે છે. તે પછી, કાર્યકર સમસ્યા જનરેશન અલ્ગોરિધમ દ્વારા પેદા થયેલ સાઇફરટેક્સ્ટ્સ પર યાઓ પ્રોટોકોલના ગણતરીના પગલાં લાગુ કરે છે. આ અંતિમ આઉટપુટ વાયર મૂલ્યો (σy) પર ન પહોંચે ત્યાં સુધી ગેટ સિફરટેક્સ્ટ્સને પુનરાવર્તિત રીતે ડિક્રિપ્ટ કરીને કરવામાં આવે છે. એન્ક્રિપ્શન યોજનાના હોમોમોર્ફિક ગુણધર્મો કાર્યકરને સાચા આઉટપુટ વાયરનું એન્ક્રિપ્શન મેળવવા માટે સક્ષમ બનાવે છે. છેવટે, કાર્યકર આઉટપુટના સિફરટેક્સ્ટ્સને ક્લાયન્ટને પરત કરે છે જે તેમને વાસ્તવિક આઉટપુટ y = F (x) અથવા δ ની ગણતરી કરવા માટે ડિક્રિપ્ટ કરે છે. ચકાસી શકાય તેવી ગણતરી યોજનાની વ્યાખ્યા જણાવે છે કે યોજના સાચી અને સુરક્ષિત બંને હોવી જોઈએ. યોજનાની ચોકસાઈ પ્રાપ્ત થાય છે જો સમસ્યા નિર્માણ અલ્ગોરિધમ એવા મૂલ્યો ઉત્પન્ન કરે છે જે પ્રામાણિક કાર્યકરને એન્કોડેડ આઉટપુટ મૂલ્યોની ગણતરી કરવા માટે સક્ષમ બનાવે છે જે સફળતાપૂર્વક ચકાસશે અને તે ઇનપુટ્સ પર F ના મૂલ્યાંકનને અનુરૂપ હશે. બીજી બાજુ, ચકાસી શકાય તેવી ગણતરી યોજના સુરક્ષિત છે જો દૂષિત કાર્યકર આપેલ કાર્ય F અને ઇનપુટ x માટે ખોટા આઉટપુટને સ્વીકારવા માટે ચકાસણી અલ્ગોરિધમને સહમત કરી શકતો નથી. જો કે તે દર્શાવવામાં આવ્યું હતું કે સિદ્ધાંતમાં ચકાસી શકાય તેવું કમ્પ્યુટિંગ શક્ય છે (સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શનનો ઉપયોગ કરીને અથવા સંભવિત રીતે ચકાસી શકાય તેવા પુરાવાઓ દ્વારા), મોટાભાગની જાણીતી રચનાઓ વ્યવહારમાં ખૂબ ખર્ચાળ છે. તાજેતરમાં, કેટલાક સંશોધકોએ ચકાસી શકાય તેવી ગણતરીને વ્યવહારુ બનાવવા તરફ ધ્યાન આપ્યું છે. આવો જ એક પ્રયાસ યુ. ટી. ઓસ્ટિનના સંશોધકોનું કાર્ય છે. લેખકો સંભવિત રીતે ચકાસી શકાય તેવા પુરાવાઓ પર આધારિત દલીલ પ્રણાલીથી શરૂઆત કરે છે અને તેના ખર્ચમાં 1020ના પરિબળનો ઘટાડો કરે છે. તેઓએ મરી પ્રણાલીમાં તેમની તકનીકોનો પણ અમલ કર્યો. લેખકો નોંધે છે કે "અમારું અત્યાર સુધીનું નિષ્કર્ષ એ છે કે, સુરક્ષિત પ્રણાલીઓ બનાવવા માટેના સાધન તરીકે, પી. સી. પી. અને દલીલ પ્રણાલીઓ ખોવાયેલા કારણ નથી". એકંદર વિસ્તાર, જેમાં હવે વિવિધ જૂથો દ્વારા સંખ્યાબંધ અમલીકરણનો સમાવેશ થાય છે, તેનું સર્વેક્ષણ કરવામાં આવ્યું છે. 2010 ના દાયકામાં, ચકાસી શકાય તેવી કમ્પ્યુટિંગ તકનીકોએ બ્લોકચેન તકનીકમાં વ્યવહારુ ઉપયોગોમાં વધારો જોયો છે. સંદર્ભો સુરક્ષિત સંદેશાવ્યવહાર વિતરિત કમ્પ્યુટિંગ