यदि हम एक-दूसरे पर भरोसा नहीं करते हैं तो क्या यादृच्छिक संख्याएँ उत्पन्न करना संभव है? भाग 1

हे हबर!

इस लेख में मैं उन प्रतिभागियों द्वारा छद्म-यादृच्छिक संख्याओं की पीढ़ी के बारे में बात करूंगा जो एक-दूसरे पर भरोसा नहीं करते हैं। जैसा कि हम नीचे देखेंगे, एक "लगभग" अच्छा जनरेटर लागू करना काफी सरल है, लेकिन एक बहुत अच्छा जनरेटर लागू करना कठिन है।

उन प्रतिभागियों के बीच यादृच्छिक संख्याएँ उत्पन्न करना क्यों आवश्यक होगा जो एक-दूसरे पर भरोसा नहीं करते हैं? एक अनुप्रयोग क्षेत्र विकेंद्रीकृत अनुप्रयोग है। उदाहरण के लिए, एक एप्लिकेशन जो किसी प्रतिभागी से शर्त स्वीकार करता है और या तो 49% संभावना के साथ राशि को दोगुना कर देता है या 51% संभावना के साथ ले जाता है, केवल तभी काम करेगा जब वह निष्पक्ष रूप से एक यादृच्छिक संख्या प्राप्त कर सकता है। यदि कोई हमलावर यादृच्छिक संख्या जनरेटर के परिणाम को प्रभावित कर सकता है, और एप्लिकेशन में भुगतान प्राप्त करने की अपनी संभावना को थोड़ा भी बढ़ा सकता है, तो वह इसे आसानी से नष्ट कर देगा।

जब हम एक वितरित यादृच्छिक संख्या पीढ़ी प्रोटोकॉल डिज़ाइन करते हैं, तो हम चाहते हैं कि इसमें तीन गुण हों:

1. वह निष्पक्ष होना चाहिए. दूसरे शब्दों में, किसी भी प्रतिभागी को किसी भी तरह से यादृच्छिक संख्या जनरेटर के परिणाम को प्रभावित नहीं करना चाहिए।

2. वह अप्रत्याशित होना चाहिए. दूसरे शब्दों में, किसी भी प्रतिभागी को यह अनुमान लगाने में सक्षम नहीं होना चाहिए कि कौन सी संख्या उत्पन्न होगी (या उसके किसी भी गुण का अनुमान लगाने से पहले)।

3. प्रोटोकॉल व्यवहार्य होना चाहिए, अर्थात, इस तथ्य के प्रति प्रतिरोधी होना चाहिए कि प्रतिभागियों का एक निश्चित प्रतिशत नेटवर्क से डिस्कनेक्ट हो जाता है या जानबूझकर प्रोटोकॉल को रोकने का प्रयास करता है।

इस लेख में हम दो दृष्टिकोण देखेंगे: RANDAO + VDF और इरेज़र कोड दृष्टिकोण। अगले भाग में, हम थ्रेशोल्ड हस्ताक्षरों पर आधारित दृष्टिकोण की विस्तार से जांच करेंगे।

लेकिन पहले, आइए एक सरल और आमतौर पर उपयोग किए जाने वाले एल्गोरिदम को देखें जो व्यवहार्य, अप्रत्याशित, लेकिन पक्षपातपूर्ण है।

रैंडो

RANDAO यादृच्छिकता उत्पन्न करने के लिए एक बहुत ही सरल और इसलिए आमतौर पर इस्तेमाल किया जाने वाला दृष्टिकोण है। सभी नेटवर्क प्रतिभागी पहले स्थानीय रूप से एक छद्म यादृच्छिक संख्या का चयन करते हैं, फिर प्रत्येक प्रतिभागी चयनित संख्या का हैश भेजता है। इसके बाद, प्रतिभागी बारी-बारी से अपने चुने हुए नंबरों को प्रकट करते हैं और प्रकट किए गए नंबरों पर एक XOR ऑपरेशन करते हैं, और इस ऑपरेशन का परिणाम प्रोटोकॉल का परिणाम बन जाता है।

संख्याओं को प्रकट करने से पहले हैश प्रकाशित करने का चरण आवश्यक है ताकि हमलावर अन्य प्रतिभागियों की संख्या देखने के बाद अपना नंबर न चुन सके। यह उसे वस्तुतः अकेले ही यादृच्छिक संख्या जनरेटर के आउटपुट को निर्धारित करने की अनुमति देगा।

प्रोटोकॉल के दौरान, प्रतिभागियों को दो बार एक आम निर्णय (तथाकथित सर्वसम्मति) पर आने की आवश्यकता होती है: कब चयनित संख्याओं को प्रकट करना शुरू करना है, और इसलिए हैश स्वीकार करना बंद करना है, और कब चयनित संख्याओं को स्वीकार करना बंद करना है और परिणामी यादृच्छिक गणना करना है संख्या। एक-दूसरे पर भरोसा नहीं करने वाले प्रतिभागियों के बीच ऐसे निर्णय लेना अपने आप में एक आसान काम नहीं है, और हम भविष्य के लेखों में इस पर लौटेंगे; इस लेख में हम मानेंगे कि ऐसा सर्वसम्मति एल्गोरिदम हमारे लिए उपलब्ध है।

RANDAO के पास ऊपर बताई गई कौन सी संपत्ति है? यह अप्रत्याशित है, इसमें अंतर्निहित सर्वसम्मति प्रोटोकॉल के समान ही जीवन शक्ति है, लेकिन यह पक्षपाती है। विशेष रूप से, एक हमलावर नेटवर्क का निरीक्षण कर सकता है, और अन्य प्रतिभागियों द्वारा अपनी संख्या प्रकट करने के बाद, वह उनके एक्सओआर की गणना कर सकता है, और निर्णय ले सकता है कि परिणाम को प्रभावित करने के लिए अपनी संख्या प्रकट करनी है या नहीं। हालाँकि यह हमलावर को यादृच्छिक संख्या जनरेटर के आउटपुट को अकेले निर्धारित करने से रोकता है, फिर भी यह उसे 1 बिट प्रभाव देता है। और यदि हमलावर कई प्रतिभागियों को नियंत्रित करते हैं, तो उनके द्वारा नियंत्रित बिट्स की संख्या उनके नियंत्रण में प्रतिभागियों की संख्या के बराबर होगी।

प्रतिभागियों को क्रम से संख्या बताने की आवश्यकता से हमलावरों के प्रभाव को काफी हद तक कम किया जा सकता है। फिर हमलावर नतीजे को तभी प्रभावित कर पाएगा जब इसे आखिरी बार खोला जाएगा। हालांकि प्रभाव काफी कम है, एल्गोरिदम अभी भी पक्षपाती है।

रैंडाओ+वीडीएफ

RANDAO को निष्पक्ष बनाने का एक तरीका यह है: सभी संख्याएँ सामने आने और XOR की गणना करने के बाद, इसका परिणाम एक फ़ंक्शन के इनपुट में फीड किया जाता है, जिसकी गणना करने में बहुत लंबा समय लगता है, लेकिन आपको इसकी शुद्धता की जांच करने की अनुमति मिलती है गणना बहुत जल्दी.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

इस फ़ंक्शन को सत्यापन योग्य विलंब फ़ंक्शन या VDF कहा जाता है। यदि अंतिम परिणाम की गणना करने में संख्या प्रकटीकरण चरण से अधिक समय लगता है, तो हमलावर अपनी संख्या दिखाने या छिपाने के प्रभाव की भविष्यवाणी करने में सक्षम नहीं होगा, और इसलिए वह परिणाम को प्रभावित करने का अवसर खो देगा।

अच्छे वीडीएफ विकसित करना बेहद कठिन है। हाल ही में कई सफलताएँ मिली हैं, उदा. यह и यह एक जिसने VDF को व्यवहार में अधिक व्यावहारिक बना दिया, और Ethereum 2.0 ने लंबी अवधि में VDF के साथ RANDAO को यादृच्छिक संख्या स्रोत के रूप में उपयोग करने की योजना बनाई है। इस तथ्य के अलावा कि यह दृष्टिकोण अप्रत्याशित और निष्पक्ष है, इसके व्यवहार्य होने का अतिरिक्त लाभ यह है कि यदि नेटवर्क पर कम से कम दो प्रतिभागी उपलब्ध हैं (यह मानते हुए कि इतनी कम संख्या में प्रतिभागियों के साथ व्यवहार करते समय उपयोग किया जाने वाला सर्वसम्मति प्रोटोकॉल व्यवहार्य है)।

इस दृष्टिकोण की सबसे बड़ी चुनौती वीडीएफ को इस तरह स्थापित करना है कि बहुत महंगे विशिष्ट हार्डवेयर वाला एक प्रतिभागी भी खोज चरण के अंत से पहले वीडीएफ की गणना करने में सक्षम नहीं होगा। आदर्श रूप से, एल्गोरिदम में एक महत्वपूर्ण सुरक्षा मार्जिन भी होना चाहिए, मान लीजिए 10x। नीचे दिया गया आंकड़ा एक अभिनेता द्वारा किए गए हमले को दर्शाता है जिसके पास एक विशेष ASIC है जो उसे RANDAO पुष्टिकरण प्रकट करने के लिए आवंटित समय से अधिक तेजी से VDF चलाने की अनुमति देता है। ऐसा प्रतिभागी अभी भी अपने नंबर का उपयोग करके या न करके अंतिम परिणाम की गणना कर सकता है, और फिर, गणना के आधार पर, चुन सकता है कि इसे दिखाना है या नहीं।

ऊपर उल्लिखित वीडीएफ परिवार के लिए, समर्पित एएसआईसी का प्रदर्शन पारंपरिक हार्डवेयर की तुलना में 100+ गुना अधिक हो सकता है। इसलिए यदि परिनियोजन चरण 10 सेकंड तक चलता है, तो ऐसे ASIC पर गणना किए गए VDF को 100x सुरक्षा मार्जिन प्राप्त करने के लिए 10 सेकंड से अधिक समय लेना चाहिए, और इस प्रकार कमोडिटी हार्डवेयर पर गणना की गई समान VDF को 100x 100 सेकंड = ~ 3 घंटे का समय लेना चाहिए।

एथेरियम फाउंडेशन ने अपनी स्वयं की सार्वजनिक रूप से उपलब्ध, निःशुल्क ASIC बनाकर इस समस्या को हल करने की योजना बनाई है। एक बार ऐसा होने पर, अन्य सभी प्रोटोकॉल भी इस तकनीक का लाभ उठा सकते हैं, लेकिन तब तक RANDAO+VDF दृष्टिकोण उन प्रोटोकॉल के लिए उतना व्यवहार्य नहीं होगा जो अपने स्वयं के ASIC को विकसित करने में निवेश नहीं कर सकते हैं।

वीडीएफ के बारे में कई लेख, वीडियो और अन्य जानकारी एकत्र की गई है यह साइट.

हम इरेज़र कोड का उपयोग करते हैं

इस अनुभाग में, हम एक यादृच्छिक संख्या पीढ़ी प्रोटोकॉल को देखेंगे जो उपयोग करता है कोड मिटाना. यह व्यवहार्य रहते हुए ⅓ तक हमलावरों को सहन कर सकता है, और परिणाम की भविष्यवाणी करने या उसे प्रभावित करने से पहले ⅔ तक हमलावरों को मौजूद रहने की अनुमति देता है।

प्रोटोकॉल का मुख्य विचार इस प्रकार है. सरलता के लिए, मान लें कि इसमें ठीक 100 प्रतिभागी हैं। आइए हम यह भी मान लें कि सभी प्रतिभागियों के पास स्थानीय रूप से कुछ निजी कुंजी हैं, और सभी प्रतिभागियों की सार्वजनिक कुंजी सभी प्रतिभागियों को ज्ञात है:

1. प्रत्येक प्रतिभागी स्थानीय रूप से एक लंबी स्ट्रिंग लेकर आता है, इसे 67 भागों में तोड़ता है, 100 शेयर प्राप्त करने के लिए इरेज़र कोड बनाता है जैसे कि कोई भी 67 स्ट्रिंग को पुनर्प्राप्त करने के लिए पर्याप्त हो, 100 शेयरों में से प्रत्येक को प्रतिभागियों में से एक को सौंपता है, और उन्हें एन्क्रिप्ट करता है उसी प्रतिभागी की सार्वजनिक कुंजी। फिर सभी एन्कोडेड शेयर प्रकाशित किए जाते हैं।

2. विशिष्ट 67 प्रतिभागियों से कोडित सेट पर सहमति तक पहुंचने के लिए प्रतिभागी किसी प्रकार की आम सहमति का उपयोग करते हैं।

3. एक बार आम सहमति बन जाने के बाद, प्रत्येक भागीदार अपनी सार्वजनिक कुंजी के साथ एन्क्रिप्टेड 67 सेटों में से प्रत्येक में एन्कोडेड शेयर लेता है, ऐसे सभी शेयरों को डिक्रिप्ट करता है, और ऐसे सभी डिक्रिप्टेड शेयरों को प्रकाशित करता है।

4. एक बार जब 67 प्रतिभागियों ने चरण (3) पूरा कर लिया, तो सभी सहमत सेटों को इरेज़र कोड के गुणों के कारण पूरी तरह से डिकोड और पुनर्निर्माण किया जा सकता है, और अंतिम संख्या प्रारंभिक पंक्तियों के एक्सओआर के रूप में प्राप्त की जा सकती है, जिसे प्रतिभागियों ने (1) में शुरू किया था। .

इस प्रोटोकॉल को निष्पक्ष और अप्रत्याशित दिखाया जा सकता है। परिणामी यादृच्छिक संख्या आम सहमति बनने के बाद निर्धारित की जाती है, लेकिन किसी को तब तक ज्ञात नहीं होती जब तक कि प्रतिभागियों में से ⅔ अपनी सार्वजनिक कुंजी के साथ एन्क्रिप्टेड भागों को डिकोड नहीं कर लेते। इस प्रकार, पुनर्निर्माण के लिए पर्याप्त जानकारी प्रकाशित होने से पहले यादृच्छिक संख्या निर्धारित की जाती है।

यदि चरण (1) में प्रतिभागियों में से एक ने अन्य प्रतिभागियों को एन्कोडेड शेयर भेजे जो कुछ स्ट्रिंग के लिए सही इरेज़र कोड नहीं हैं तो क्या होगा? अतिरिक्त परिवर्तनों के बिना, अलग-अलग प्रतिभागी या तो स्ट्रिंग को पुनर्प्राप्त करने में सक्षम नहीं होंगे, या वे अलग-अलग स्ट्रिंग को पुनर्प्राप्त करेंगे, जिसके परिणामस्वरूप विभिन्न प्रतिभागियों को एक अलग यादृच्छिक संख्या प्राप्त होगी। इसे रोकने के लिए, आप निम्न कार्य कर सकते हैं: प्रत्येक भागीदार, एन्कोडेड शेयरों के अलावा, गणना भी करता है मर्कला वृक्ष ऐसे सभी शेयर, और प्रत्येक भागीदार को एन्कोडेड शेयर और मर्कल ट्री की जड़, और मर्कल ट्री में शेयर को शामिल करने का प्रमाण भेजता है। चरण (2) में आम सहमति में, प्रतिभागी न केवल सेटों के एक सेट पर सहमत होते हैं, बल्कि ऐसे पेड़ों की विशिष्ट जड़ों के एक सेट पर भी सहमत होते हैं (यदि कुछ प्रतिभागी प्रोटोकॉल से विचलित हो जाते हैं, और अलग-अलग प्रतिभागियों को अलग-अलग मर्कल पेड़ की जड़ें भेजते हैं, और ऐसी दो जड़ें आम सहमति के दौरान दिखाई जाती हैं, उनकी पंक्ति परिणाम सेट में शामिल नहीं है)। सर्वसम्मति के परिणामस्वरूप, हमारे पास 67 एन्कोडेड लाइनें और मर्केल ट्री की संबंधित जड़ें होंगी, जैसे कि कम से कम 67 प्रतिभागी हों (जरूरी नहीं कि वही लोग हों जिन्होंने संबंधित लाइनें प्रस्तावित की हों), जिन्होंने 67 लाइनों में से प्रत्येक के लिए इरेज़र कोड के एक हिस्से के साथ एक संदेश, और संबंधित पेड़ में उनके हिस्से की घटना का प्रमाण फीका पड़ गया।

जब चरण (4) में प्रतिभागी एक निश्चित स्ट्रिंग के लिए 67 बीट्स को समझता है और उनमें से मूल स्ट्रिंग को फिर से बनाने की कोशिश करता है, तो विकल्पों में से एक संभव है:

1. स्ट्रिंग को पुनर्स्थापित किया जाता है, और यदि इसे फिर से मिटाया-एनकोड किया जाता है, और मर्कल ट्री की गणना स्थानीय रूप से गणना किए गए शेयरों के लिए की जाती है, तो रूट उसी के साथ मेल खाता है जिस पर सहमति बनी थी।

2. पंक्ति बहाल कर दी गई है, लेकिन स्थानीय रूप से गणना की गई रूट उस रूट से मेल नहीं खाती है जिस पर सहमति बनी थी।

3. पंक्ति पुनर्स्थापित नहीं की गई है.

यह दिखाना आसान है कि यदि विकल्प (1) उपरोक्त कम से कम एक प्रतिभागी के लिए हुआ, तो विकल्प (1) सभी प्रतिभागियों के लिए हुआ, और इसके विपरीत, यदि विकल्प (2) या (3) कम से कम एक प्रतिभागी के लिए हुआ, तो सभी प्रतिभागियों के लिए विकल्प (2) या (3) होगा। इस प्रकार, सेट में प्रत्येक पंक्ति के लिए, या तो सभी प्रतिभागी इसे सफलतापूर्वक पुनर्प्राप्त कर लेंगे, या सभी प्रतिभागी इसे पुनर्प्राप्त करने में विफल हो जाएंगे। परिणामी यादृच्छिक संख्या केवल उन पंक्तियों का एक XOR है जिसे प्रतिभागी पुनर्प्राप्त करने में सक्षम थे।

दहलीज हस्ताक्षर

यादृच्छिकता के लिए एक अन्य दृष्टिकोण बीएलएस थ्रेशोल्ड हस्ताक्षर कहलाने वाले का उपयोग करना है। थ्रेशोल्ड हस्ताक्षरों पर आधारित एक यादृच्छिक संख्या जनरेटर में ऊपर वर्णित इरेज़र कोड-आधारित एल्गोरिदम के समान ही गारंटी होती है, लेकिन प्रत्येक उत्पन्न संख्या के लिए नेटवर्क पर भेजे गए संदेशों की स्पर्शोन्मुख संख्या काफी कम होती है।

बीएलएस हस्ताक्षर एक डिज़ाइन है जो कई प्रतिभागियों को एक संदेश के लिए एक सामान्य हस्ताक्षर बनाने की अनुमति देता है। इन हस्ताक्षरों का उपयोग अक्सर कई हस्ताक्षरों को भेजने की आवश्यकता न करके स्थान और बैंडविड्थ को बचाने के लिए किया जाता है। 

ब्लॉकचेन प्रोटोकॉल में बीएलएस हस्ताक्षर के लिए एक सामान्य अनुप्रयोग, यादृच्छिक संख्या उत्पन्न करने के अलावा, बीएफटी प्रोटोकॉल में ब्लॉक साइनिंग है। मान लीजिए कि 100 प्रतिभागी ब्लॉक बनाते हैं, और यदि उनमें से 67 उस पर हस्ताक्षर करते हैं तो एक ब्लॉक को अंतिम माना जाता है। वे सभी बीएलएस हस्ताक्षर के अपने हिस्से जमा कर सकते हैं और उनमें से 67 पर सहमत होने के लिए कुछ सर्वसम्मति एल्गोरिदम का उपयोग कर सकते हैं और फिर उन्हें एक बीएलएस हस्ताक्षर में विलय कर सकते हैं। अंतिम हस्ताक्षर बनाने के लिए किसी भी 67 (या अधिक) भागों का उपयोग किया जा सकता है, जो इस बात पर निर्भर करेगा कि 67 हस्ताक्षरों को संयुक्त किया गया था और इसलिए भिन्न हो सकते हैं, हालांकि 67 प्रतिभागियों द्वारा अलग-अलग विकल्प एक अलग हस्ताक्षर बनाएंगे, ऐसा कोई भी हस्ताक्षर वैध होगा ब्लॉक के लिए हस्ताक्षर. शेष प्रतिभागियों को नेटवर्क पर 67 के बजाय प्रति ब्लॉक केवल एक हस्ताक्षर प्राप्त करने और सत्यापित करने की आवश्यकता होती है, जो नेटवर्क पर लोड को काफी कम कर देता है।

यह पता चलता है कि यदि प्रतिभागियों द्वारा उपयोग की जाने वाली निजी कुंजियाँ एक निश्चित तरीके से उत्पन्न होती हैं, तो इससे कोई फर्क नहीं पड़ता कि 67 हस्ताक्षर (या अधिक, लेकिन कम नहीं) एकत्रित किए गए हैं, परिणामी हस्ताक्षर वही होंगे। इसका उपयोग यादृच्छिकता के स्रोत के रूप में किया जा सकता है: प्रतिभागी पहले कुछ संदेश पर सहमत होते हैं जिस पर वे हस्ताक्षर करेंगे (यह RANDAO का आउटपुट या सिर्फ अंतिम ब्लॉक का हैश हो सकता है, यह वास्तव में तब तक मायने नहीं रखता जब तक यह हर बार बदलता है और सुसंगत है) और इसके लिए एक बीएलएस हस्ताक्षर बनाएं। पीढ़ी का परिणाम तब तक अप्रत्याशित होगा जब तक कि 67 प्रतिभागी अपने हिस्से प्रदान नहीं करते हैं, और उसके बाद आउटपुट पहले से ही पूर्व निर्धारित होता है और किसी भी प्रतिभागी के कार्यों पर निर्भर नहीं हो सकता है।

यादृच्छिकता के लिए यह दृष्टिकोण तब तक व्यवहार्य है जब तक कि ऑनलाइन प्रतिभागियों में से कम से कम ⅔ दोनों प्रोटोकॉल का पालन करते हैं, और तब तक निष्पक्ष और अप्रत्याशित है जब तक कि कम से कम ⅓ प्रतिभागी प्रोटोकॉल का पालन करते हैं। यह ध्यान रखना महत्वपूर्ण है कि एक हमलावर जो ⅓ से अधिक लेकिन ⅔ से कम प्रतिभागियों को नियंत्रित करता है, वह प्रोटोकॉल को रोक सकता है, लेकिन इसके आउटपुट की भविष्यवाणी या प्रभावित नहीं कर सकता है।

थ्रेसहोल्ड हस्ताक्षर अपने आप में एक बहुत ही दिलचस्प विषय है। लेख के दूसरे भाग में, हम विस्तार से विश्लेषण करेंगे कि वे कैसे काम करते हैं, और प्रतिभागी कुंजी उत्पन्न करना वास्तव में कैसे आवश्यक है ताकि थ्रेशोल्ड हस्ताक्षर को यादृच्छिक संख्या जनरेटर के रूप में उपयोग किया जा सके।

अंत में

यह लेख तकनीकी ब्लॉग लेखों की श्रृंखला में पहला है NEAR. NEAR एक ब्लॉकचेन प्रोटोकॉल और प्लेटफ़ॉर्म है जो विकेंद्रीकृत अनुप्रयोगों को विकसित करने के लिए है, जिसमें विकास में आसानी और अंतिम उपयोगकर्ताओं के लिए उपयोग में आसानी पर जोर दिया गया है।

प्रोटोकॉल कोड खुला है, हमारा कार्यान्वयन रस्ट में लिखा गया है, इसे पाया जा सकता है यहां.

आप देख सकते हैं कि NEAR के लिए विकास कैसा दिखता है और ऑनलाइन IDE में प्रयोग कर सकते हैं यहां.

आप यहां रूसी भाषा में सभी समाचारों का अनुसरण कर सकते हैं टेलीग्राम समूह और VKontakte पर समूह, और आधिकारिक में अंग्रेजी में चहचहाना.

जल्द मिलते हैं!

स्रोत: www.habr.com