Verifiable computing
सत्यापन योग्य संगणना (या सत्यापित संगणना या सत्यापित संगणना) एक कंप्यूटर को सत्यापन योग्य परिणामों को बनाए रखते हुए, अन्य शायद अविश्वसनीय ग्राहकों को कुछ कार्य की गणना को बंद करने में सक्षम बनाता है। अन्य ग्राहक कार्य का मूल्यांकन करते हैं और परिणाम को इस प्रमाण के साथ लौटाते हैं कि कार्य की गणना सही ढंग से की गई थी। इस धारणा की शुरुआत SETI@home जैसी परियोजनाओं में अविश्वसनीय उपयोगकर्ताओं के लिए "आउटसोर्सिंग" गणना की बढ़ती सामान्य घटना और क्लाउड कंप्यूटिंग जैसी अधिक शक्तिशाली गणना सेवा के लिए कम्प्यूटेशनल कार्यों को आउटसोर्स करने की कमजोर ग्राहकों की बढ़ती इच्छा के परिणामस्वरूप हुई। यह अवधारणा बाबाई और अन्य लोगों द्वारा काम करने से पहले की है, और इसका अध्ययन विभिन्न शब्दों के तहत किया गया है, जिसमें "गणना की जाँच" (बाबाई और अन्य) शामिल हैं। ), "प्रत्यायोजित गणना", "प्रमाणित गणना", और सत्यापन योग्य गणना। सत्यापन योग्य कम्प्यूटिंग शब्द को रोसारियो गेन्नारो, क्रेग जेंट्री और ब्रायन पार्नो द्वारा औपचारिक रूप दिया गया था और यह मिकाली की "प्रमाणित गणना" को प्रतिध्वनित करता है। प्रेरणा और अवलोकन कम्प्यूटेशनल कार्यों को अपेक्षाकृत कमजोर कम्प्यूटेशनल उपकरण (क्लाइंट) से अधिक शक्तिशाली कम्प्यूटेशन सेवाओं (कार्यकर्ता) को आउटसोर्स करने की बढ़ती इच्छा, और बेईमान श्रमिकों की समस्या जो वास्तविक कार्य किए बिना प्रशंसनीय परिणाम देने के लिए अपने क्लाइंट के सॉफ्टवेयर को संशोधित करते हैं, ने सत्यापन योग्य गणना की धारणा के औपचारिकरण को प्रेरित किया। सत्यापन योग्य कंप्यूटिंग न केवल ग्राहक के इनपुट पर आउटसोर्स किए गए कार्य के परिणाम और इसकी शुद्धता के प्रमाण को प्राप्त करने से संबंधित है, बल्कि ग्राहक को शुरू से कार्य की गणना करने की तुलना में काफी कम कम्प्यूटेशनल प्रयास के साथ प्रमाण को सत्यापित करने में सक्षम होने से भी संबंधित है। असुरक्षित श्रमिकों द्वारा किए गए कार्यों की गणना को सत्यापित करने में काफी ध्यान दिया गया है, जिसमें सुरक्षित सह-प्रोसेसर, विश्वसनीय प्लेटफॉर्म मॉड्यूल (टी. पी. एम.), संवादात्मक प्रमाण, संभावित रूप से जांच योग्य प्रमाण, कुशल तर्क और मिकाली के सी. एस. प्रमाण शामिल हैं। ये सत्यापन या तो संवादात्मक होते हैं जिनके लिए ग्राहक को शुद्धता प्रमाण को सत्यापित करने के लिए कार्यकर्ता के साथ बातचीत करने की आवश्यकता होती है, या गैर-संवादात्मक प्रोटोकॉल होते हैं जिन्हें यादृच्छिक दैवज्ञ मॉडल में साबित किया जा सकता है। प्रतिकृति द्वारा सत्यापन सबसे बड़ी सत्यापित गणना (SETI@home) प्रतिकृति द्वारा सत्यापन का उपयोग करती है। SETI@home सत्यापन प्रक्रिया में एक ग्राहक मशीन और कई कार्यकर्ता मशीनें शामिल होती हैं। क्लाइंट मशीन कई कंप्यूटरों (कम से कम 2) को समान कार्य इकाइयाँ भेजती है। जब उचित समय में पर्याप्त परिणाम नहीं मिलते हैं-मशीनों के गलती से बंद होने, संचार टूटने आदि के कारण-या परिणाम सहमत नहीं होते हैं-गणना त्रुटियों, वास्तव में काम किए बिना गलत डेटा जमा करके धोखाधड़ी आदि के कारण-तो क्लाइंट मशीन अन्य श्रमिक मशीनों को अधिक समान कार्य इकाइयाँ भेजती है। एक बार जब परिणामों की न्यूनतम कोरम (अक्सर 2) सहमत हो जाती है, तो ग्राहक मानता है कि वे परिणाम (और उस कार्य इकाई के लिए अन्य समान परिणाम) सही हैं। ग्राहक उन सभी मशीनों को श्रेय देता है जो सही परिणाम देती हैं। सत्यापन योग्य गणना गेन्नारो और अन्य। सत्यापन योग्य गणना योजना की धारणा को दो बहुपद समय दलों के बीच एक प्रोटोकॉल के रूप में परिभाषित किया गया है ताकि एक फलन F: {0,1} n → {0,1} m की गणना पर सहयोग किया जा सके। इस योजना में तीन मुख्य चरण होते हैंः पूर्व प्रसंस्करण। एफ से जुड़ी कुछ सहायक जानकारी की गणना करने के लिए ग्राहक द्वारा इस चरण को एक बार किया जाता है। इस जानकारी का एक हिस्सा कर्मचारी के साथ साझा करने के लिए सार्वजनिक है जबकि बाकी निजी है और ग्राहक के साथ रखा जाता है। तैयारियाँ प्रविष्ट करें। इस चरण में, क्लाइंट फ़ंक्शन के इनपुट के बारे में कुछ सहायक जानकारी की गणना करता है। इस जानकारी का कुछ हिस्सा सार्वजनिक है जबकि बाकी निजी है और ग्राहक के पास रखा जाता है। इनपुट डेटा पर एफ की गणना करने के लिए कर्मचारी को सार्वजनिक जानकारी भेजी जाती है। आउटपुट गणना और सत्यापन। इस चरण में, कार्यकर्ता प्रदान किए गए इनपुट पर फ़ंक्शन F के एन्कोडेड आउटपुट की गणना करने के लिए फ़ंक्शन F और इनपुट से जुड़ी सार्वजनिक जानकारी का उपयोग करता है, जिसकी गणना पिछले दो चरणों में की जाती है। यह परिणाम तब पिछले चरणों में गणना की गई निजी जानकारी का उपयोग करके कार्यकर्ता द्वारा वापस किए गए परिणाम को डिकोड करके आउटपुट के वास्तविक मूल्य की गणना करके अपनी शुद्धता को सत्यापित करने के लिए ग्राहक को वापस कर दिया जाता है। सत्यापन योग्य गणना योजना की परिभाषित धारणा ग्राहक और कार्यकर्ता के बीच बातचीत को ठीक दो संदेशों में कम करती है, जहां प्रोटोकॉल के विभिन्न चरणों के दौरान प्रत्येक पक्ष से दूसरे पक्ष को भेजा गया एक संदेश होता है। पूरी तरह से होमोमोर्फिक एन्क्रिप्शन गेन्नारो एट अल पर आधारित एक उदाहरण योजना। एक पूरी तरह से समरूपी कूटलेखन प्रणाली के साथ संयुक्त याओ के खराब परिपथ का उपयोग करके किसी भी कार्य F के लिए एक सत्यापन योग्य गणना योजना को परिभाषित किया। इस सत्यापन योग्य गणना योजना वी. सी. को निम्नानुसार परिभाषित किया गया हैः वी. सी. = (कीजेन, प्रोबजेन, कंप्यूट, वेरिफाई) में निम्नलिखित चार एल्गोरिदम होते हैंः कीजेन (एफ, λ) → (पी. के., एस. के.): यादृच्छिक की पीढ़ी एल्गोरिदम सुरक्षा पैरामीटर λ के आधार पर दो कुंजी, सार्वजनिक और निजी उत्पन्न करता है। सार्वजनिक कुंजी लक्ष्य फलन एफ को कूटबद्ध करती है और कर्मचारी को एफ की गणना करने के लिए भेजी जाती है। दूसरी ओर, गुप्त कुंजी ग्राहक द्वारा निजी रखी जाती है। ProbGen (SK, x) → (σx, τx): समस्या उत्पन्न करने वाला एल्गोरिथ्म गुप्त कुंजी SK का उपयोग करके फ़ंक्शन इनपुट x को दो मूल्यों, सार्वजनिक और निजी में कूटबद्ध करता है। एफ (एक्स) की गणना करने के लिए कर्मचारी को सार्वजनिक मूल्य σx दिया जाता है, जबकि ग्राहक द्वारा गुप्त मूल्य τx को निजी रखा जाता है। गणना (पीके, σx) → σy: कार्यकर्ता क्लाइंट की सार्वजनिक कुंजी पीके और एन्कोडेड इनपुट σx का उपयोग करके फ़ंक्शन के आउटपुट y = F (x) के एक एन्कोडेड मान σy की गणना करता है। सत्यापन एस. के. (τx, σy) → y ≤ D: सत्यापन एल्गोरिथ्म गुप्त कुंजी एस. के. और गुप्त "डिकोडिंग" τx दोनों का उपयोग करके कार्यकर्ता के एन्कोडेड आउटपुट σy को फ़ंक्शन एफ के वास्तविक आउटपुट में परिवर्तित करता है। यह आउटपुट y = F (x) देता है यदि σy x पर F के वैध आउटपुट का प्रतिनिधित्व करता है, या अन्यथा आउटपुट δ देता है। गेन्नारो एट अल द्वारा परिभाषित सत्यापन योग्य गणना योजना का प्रोटोकॉल। निम्नलिखित रूप में कार्य करता हैः फलन F को एक बूलियन परिपथ के रूप में दर्शाया जाना चाहिए जिस पर कुंजी पीढ़ी एल्गोरिथ्म लागू किया जाएगा। कुंजी पीढ़ी एल्गोरिथ्म सार्वजनिक और गुप्त कुंजी की गणना करने के लिए इस बूलियन परिपथ पर याओ की गार्बलिंग प्रक्रिया को चलाता है। सार्वजनिक कुंजी (पी. के.) उन सभी सांकेतिक पाठों से बनी होती है जो खराब परिपथ का प्रतिनिधित्व करते हैं, और गुप्त कुंजी (एस. के.) सभी यादृच्छिक तार लेबलों से बनी होती है। उत्पन्न गुप्त कुंजी का उपयोग समस्या उत्पादन एल्गोरिदम में किया जाता है। यह एल्गोरिथ्म पहले समरूपी कूटलेखन योजना के लिए सार्वजनिक और गुप्त कुंजी की एक नई जोड़ी उत्पन्न करता है, और फिर इन कुंजी का उपयोग समरूपी योजना के साथ सही इनपुट तारों को कूटबद्ध करने के लिए करता है, जिसे खराब परिपथ की गुप्त कुंजी के रूप में दर्शाया जाता है। उत्पादित सिफरटेक्स्ट कर्मचारी को दिए गए इनपुट (σx) के सार्वजनिक एन्कोडिंग का प्रतिनिधित्व करते हैं, जबकि गुप्त कुंजी (τx) को ग्राहक द्वारा निजी रखा जाता है। उसके बाद, कार्यकर्ता समस्या उत्पादन एल्गोरिदम द्वारा उत्पन्न सिफरटेक्स्ट पर याओ के प्रोटोकॉल के गणना चरणों को लागू करता है। यह अंतिम आउटपुट तार मूल्यों (σy) तक पहुंचने तक गेट सिफरटेक्स्ट को पुनरावर्ती रूप से डिक्रिप्ट करके किया जाता है। कूटलेखन योजना के समरूपी गुण कार्यकर्ता को सही आउटपुट तार का कूटलेखन प्राप्त करने में सक्षम बनाते हैं। अंत में, कर्मचारी ग्राहक को आउटपुट के सिफरटेक्स्ट लौटाता है जो वास्तविक आउटपुट y = F (x) या δ की गणना करने के लिए उन्हें डिक्रिप्ट करता है। सत्यापन योग्य गणना योजना की परिभाषा में कहा गया है कि योजना सही और सुरक्षित दोनों होनी चाहिए। योजना की शुद्धता तब प्राप्त की जाती है जब समस्या उत्पादन एल्गोरिथ्म ऐसे मूल्यों का उत्पादन करता है जो एक ईमानदार कार्यकर्ता को एन्कोडेड आउटपुट मूल्यों की गणना करने में सक्षम बनाते हैं जो सफलतापूर्वक सत्यापित होंगे और उन निवेशों पर एफ के मूल्यांकन के अनुरूप होंगे। दूसरी ओर, एक सत्यापन योग्य गणना योजना सुरक्षित है यदि एक दुर्भावनापूर्ण कार्यकर्ता किसी दिए गए फ़ंक्शन F और इनपुट x के लिए एक गलत आउटपुट को स्वीकार करने के लिए सत्यापन एल्गोरिथ्म को मना नहीं सकता है। हालांकि यह दिखाया गया था कि सिद्धांत रूप में सत्यापन योग्य कंप्यूटिंग संभव है (पूरी तरह से समरूप एन्क्रिप्शन का उपयोग करके या संभावित रूप से जांच योग्य प्रमाणों के माध्यम से), अधिकांश ज्ञात निर्माण व्यवहार में बहुत महंगे हैं। हाल ही में, कुछ शोधकर्ताओं ने सत्यापन योग्य गणना को व्यावहारिक बनाने पर ध्यान दिया है। ऐसा ही एक प्रयास है यू. टी. ऑस्टिन शोधकर्ताओं का काम। लेखक संभावित रूप से जांच योग्य प्रमाणों के आधार पर एक तर्क प्रणाली के साथ शुरू करते हैं और इसकी लागत को 1020 के कारक से कम करते हैं। उन्होंने काली मिर्च प्रणाली में अपनी तकनीकों को भी लागू किया। लेखकों ने नोट किया कि "अब तक हमारा निष्कर्ष यह है कि, सुरक्षित प्रणालियों के निर्माण के लिए एक उपकरण के रूप में, पी. सी. पी. और तर्क प्रणाली एक खोए हुए कारण नहीं हैं।" समग्र क्षेत्र, जिसमें अब विभिन्न समूहों द्वारा कई कार्यान्वयन शामिल हैं, का सर्वेक्षण किया गया है। 2010 के दशक में, सत्यापन योग्य कंप्यूटिंग तकनीकों ने ब्लॉकचैन प्रौद्योगिकी में व्यावहारिक अनुप्रयोगों में वृद्धि देखी है। संदर्भ सुरक्षित संचार वितरित कंप्यूटिंग