जर आपला एकमेकांवर विश्वास नसेल तर यादृच्छिक संख्या निर्माण करणे शक्य आहे का? भाग 1

अहो हाब्र!

या लेखात मी एकमेकांवर विश्वास नसलेल्या सहभागींद्वारे छद्म-यादृच्छिक संख्यांच्या निर्मितीबद्दल बोलेन. जसे आपण खाली पाहणार आहोत, “जवळजवळ” चांगला जनरेटर लागू करणे अगदी सोपे आहे, परंतु खूप चांगले जनरेटर कठीण आहे.

एकमेकांवर विश्वास नसलेल्या सहभागींमध्ये यादृच्छिक संख्या निर्माण करणे का आवश्यक आहे? एक अर्ज क्षेत्र विकेंद्रित अनुप्रयोग आहे. उदाहरणार्थ, एखादा अर्ज जो सहभागीकडून पैज स्वीकारतो आणि एकतर 49% संभाव्यतेसह रक्कम दुप्पट करतो किंवा 51% संभाव्यतेसह काढून घेतो तो केवळ तेव्हाच कार्य करेल जेव्हा तो निःपक्षपातीपणे यादृच्छिक क्रमांक प्राप्त करू शकतो. जर एखादा हल्लेखोर यादृच्छिक क्रमांक जनरेटरच्या परिणामावर प्रभाव टाकू शकतो आणि अर्जामध्ये पेआउट मिळण्याची शक्यता थोडीशी वाढवू शकतो, तर तो सहजपणे त्याचा नाश करेल.

जेव्हा आम्ही वितरित यादृच्छिक संख्या निर्मिती प्रोटोकॉल तयार करतो, तेव्हा आम्हाला तीन गुणधर्म हवे असतात:

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

2. तो अप्रत्याशित असावा. दुस-या शब्दात सांगायचे तर, कोणती संख्या व्युत्पन्न केली जाईल (किंवा त्याच्या कोणत्याही गुणधर्माचा अंदाज लावणे) ती व्युत्पन्न होण्यापूर्वी कोणताही सहभागी सांगू शकत नाही.

3. प्रोटोकॉल व्यवहार्य असणे आवश्यक आहे, म्हणजेच, काही टक्के सहभागी नेटवर्कवरून डिस्कनेक्ट होतात किंवा मुद्दाम प्रोटोकॉल थांबवण्याचा प्रयत्न करतात या वस्तुस्थितीला प्रतिरोधक असणे आवश्यक आहे.

या लेखात आपण दोन दृष्टिकोन पाहू: RANDAO + VDF आणि इरेजर कोडचा दृष्टिकोन. पुढील भागात, आम्ही थ्रेशोल्ड स्वाक्षरीवर आधारित दृष्टिकोनाचे तपशीलवार परीक्षण करू.

परंतु प्रथम, व्यवहार्य, अप्रत्याशित, परंतु पक्षपाती असलेले एक साधे आणि सामान्यतः वापरले जाणारे अल्गोरिदम पाहू.

रांडाओ

यादृच्छिकता निर्माण करण्यासाठी RANDAO ही एक अतिशय सोपी आणि म्हणून सामान्यतः वापरली जाणारी पद्धत आहे. सर्व नेटवर्क सहभागी प्रथम स्थानिकरित्या एक छद्म यादृच्छिक क्रमांक निवडतात, त्यानंतर प्रत्येक सहभागी निवडलेल्या क्रमांकाचा हॅश पाठवतो. पुढे, सहभागी वळण घेतात आणि त्यांची निवडलेली संख्या उघड करतात आणि उघड केलेल्या संख्येवर XOR ऑपरेशन करतात आणि या ऑपरेशनचा परिणाम प्रोटोकॉलचा परिणाम बनतो.

संख्या उघड करण्यापूर्वी हॅश प्रकाशित करण्याची पायरी आवश्यक आहे जेणेकरून आक्रमणकर्त्याने इतर सहभागींची संख्या पाहिल्यानंतर त्याचा नंबर निवडू शकत नाही. हे त्याला अक्षरशः एकट्याने यादृच्छिक संख्या जनरेटरचे आउटपुट निर्धारित करण्यास अनुमती देईल.

प्रोटोकॉल दरम्यान, सहभागींनी दोनदा एक सामान्य निर्णय (तथाकथित एकमत) गाठणे आवश्यक आहे: निवडलेल्या संख्या उघड करणे केव्हा सुरू करावे, आणि म्हणून हॅश स्वीकारणे थांबवावे, आणि निवडलेल्या संख्या स्वीकारणे आणि परिणामी यादृच्छिक गणना करणे कधी थांबवावे. संख्या एकमेकांवर विश्वास नसलेल्या सहभागींमध्ये असे निर्णय घेणे स्वतःच सोपे काम नाही आणि आम्ही भविष्यातील लेखांमध्ये त्यावर परत येऊ; या लेखात आम्ही असे गृहीत धरू की असे एकमत अल्गोरिदम आमच्यासाठी उपलब्ध आहे.

RANDAO मध्ये आम्ही वर वर्णन केलेल्या गुणधर्मांपैकी कोणते गुणधर्म आहेत? हे अप्रत्याशित आहे, अंतर्निहित सहमती प्रोटोकॉल प्रमाणेच जिवंतपणा आहे, परंतु ते पक्षपाती आहे. विशेषतः, आक्रमणकर्ता नेटवर्कचे निरीक्षण करू शकतो आणि इतर सहभागींनी त्यांची संख्या उघड केल्यानंतर, तो त्यांच्या XOR ची गणना करू शकतो आणि निकालावर प्रभाव टाकण्यासाठी त्याचा नंबर उघड करायचा की नाही हे ठरवू शकतो. हे आक्रमणकर्त्याला यादृच्छिक क्रमांक जनरेटरचे आउटपुट निर्धारित करण्यापासून प्रतिबंधित करते, तरीही ते त्याला 1 बिट प्रभाव देते. आणि जर हल्लेखोर अनेक सहभागींवर नियंत्रण ठेवत असतील, तर त्यांनी नियंत्रित केलेल्या बिट्सची संख्या त्यांच्या नियंत्रणाखाली असलेल्या सहभागींच्या संख्येइतकी असेल.

सहभागींनी क्रमाने संख्या प्रकट करणे आवश्यक करून हल्लेखोरांचा प्रभाव मोठ्या प्रमाणात कमी केला जाऊ शकतो. नंतर हल्लेखोर शेवटचे उघडले तरच परिणाम प्रभावित करू शकेल. प्रभाव लक्षणीयरीत्या कमी असताना, अल्गोरिदम अजूनही पक्षपाती आहे.

RANDAO+VDF

RANDAO निःपक्षपाती करण्याचा एक मार्ग हा आहे: सर्व आकडे उघड झाल्यानंतर आणि XOR ची गणना केल्यानंतर, त्याचा परिणाम फंक्शनच्या इनपुटमध्ये दिला जातो, ज्याची गणना करण्यास बराच वेळ लागतो, परंतु आपल्याला त्याची शुद्धता तपासण्याची परवानगी देते. गणना खूप लवकर.

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

या फंक्शनला व्हेरिफायेबल डिले फंक्शन किंवा व्हीडीएफ म्हणतात. अंतिम निकालाची गणना करण्यात संख्या प्रकटीकरणाच्या टप्प्यापेक्षा जास्त वेळ लागल्यास, आक्रमणकर्ता आपला नंबर दर्शविण्याच्या किंवा लपविण्याच्या परिणामाचा अंदाज लावू शकणार नाही आणि म्हणून तो निकालावर प्रभाव टाकण्याची संधी गमावेल.

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

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

वर नमूद केलेल्या VDF कुटुंबासाठी, समर्पित ASIC ची कामगिरी पारंपारिक हार्डवेअरपेक्षा 100+ पट जास्त असू शकते. म्हणून जर उपयोजन टप्पा 10 सेकंदांचा असेल, तर अशा ASIC वर गणना केलेल्या VDF ला 100x सुरक्षितता मार्जिन मिळण्यासाठी 10 सेकंदांपेक्षा जास्त वेळ लागणे आवश्यक आहे आणि अशा प्रकारे कमोडिटी हार्डवेअरवर गणना केलेल्या VDF ला 100x 100 सेकंद = ~3 तास लागतील.

इथरियम फाउंडेशनने स्वतःचे सार्वजनिकरित्या उपलब्ध, विनामूल्य ASICs तयार करून या समस्येचे निराकरण करण्याची योजना आखली आहे. एकदा असे झाले की, इतर सर्व प्रोटोकॉल देखील या तंत्रज्ञानाचा लाभ घेऊ शकतात, परंतु तोपर्यंत RANDAO+VDF दृष्टिकोन त्यांच्या स्वतःच्या ASIC विकसित करण्यासाठी गुंतवणूक करू शकत नसलेल्या प्रोटोकॉलसाठी व्यवहार्य असणार नाही.

VDF बद्दल अनेक लेख, व्हिडिओ आणि इतर माहिती संकलित केली आहे ही साइट.

आम्ही इरेजर कोड वापरतो

या विभागात, आपण वापरत असलेल्या यादृच्छिक संख्या निर्मिती प्रोटोकॉलकडे पाहू कोड मिटवत आहे. ते व्यवहार्य राहून ⅓ हल्लेखोरांना सहन करू शकते आणि परिणामाचा अंदाज वर्तवण्याआधी किंवा त्यावर प्रभाव टाकण्यापूर्वी ⅔ हल्लेखोरांना अस्तित्वात ठेवण्याची परवानगी देते.

प्रोटोकॉलची मुख्य कल्पना खालीलप्रमाणे आहे. साधेपणासाठी, असे गृहीत धरू की नक्की 100 सहभागी आहेत. आपण हे देखील गृहीत धरूया की सर्व सहभागींकडे स्थानिक पातळीवर काही खाजगी की आहे आणि सर्व सहभागींच्या सार्वजनिक की सर्व सहभागींना ज्ञात आहेत:

1. प्रत्येक सहभागी स्थानिक पातळीवर एक लांब स्ट्रिंग घेऊन येतो, त्याला 67 भागांमध्ये विभाजित करतो, 100 शेअर्स मिळविण्यासाठी इरेजर कोड तयार करतो जसे की स्ट्रिंग पुनर्प्राप्त करण्यासाठी कोणतेही 67 पुरेसे असतात, 100 पैकी प्रत्येक शेअर्स सहभागींपैकी एकाला नियुक्त करतो आणि त्यांना एनक्रिप्ट करतो. त्याच सहभागीची सार्वजनिक की. सर्व एन्कोड केलेले शेअर्स नंतर प्रकाशित केले जातात.

2. विशिष्ट 67 सहभागींकडून कोडेड सेटवर करारावर पोहोचण्यासाठी सहभागी काही प्रकारचे एकमत वापरतात.

3. एकदा एकमत झाल्यावर, प्रत्येक सहभागी त्यांच्या सार्वजनिक कीसह कूटबद्ध केलेल्या प्रत्येक 67 संचातील एन्कोड केलेले शेअर्स घेतो, असे सर्व शेअर्स डिक्रिप्ट करतो आणि असे सर्व डिक्रिप्ट केलेले शेअर्स प्रकाशित करतो.

4. एकदा 67 सहभागींनी चरण (3) पूर्ण केल्यावर, सर्व सहमत संच पूर्णपणे डीकोड केले जाऊ शकतात आणि इरेजर कोडच्या गुणधर्मांमुळे पुनर्रचना केले जाऊ शकतात आणि अंतिम संख्या प्रारंभिक पंक्तींच्या XOR म्हणून प्राप्त केली जाऊ शकते जी सहभागींनी (1) मध्ये सुरू केली होती. .

हा प्रोटोकॉल निःपक्षपाती आणि अप्रत्याशित असल्याचे दर्शविले जाऊ शकते. एकमत झाल्यानंतर परिणामी यादृच्छिक संख्या निर्धारित केली जाते, परंतु सहभागींच्या ⅔ त्यांच्या सार्वजनिक कीसह कूटबद्ध केलेले भाग डीकोड करेपर्यंत कोणालाही माहिती नसते. अशा प्रकारे, पुनर्रचना करण्यासाठी पुरेशी माहिती प्रकाशित होण्यापूर्वी यादृच्छिक संख्या निर्धारित केली जाते.

चरण (1) मध्ये सहभागींपैकी एकाने इतर सहभागींना एन्कोड केलेले शेअर पाठवले तर काय होईल जे काही स्ट्रिंगसाठी योग्य इरेजर कोड नाहीत? अतिरिक्त बदलांशिवाय, भिन्न सहभागी एकतर स्ट्रिंग अजिबात पुनर्प्राप्त करू शकणार नाहीत किंवा ते भिन्न स्ट्रिंग पुनर्प्राप्त करतील, ज्यामुळे भिन्न सहभागींना भिन्न यादृच्छिक क्रमांक प्राप्त होतील. हे प्रतिबंधित करण्यासाठी, आपण पुढील गोष्टी करू शकता: प्रत्येक सहभागी, एन्कोड केलेल्या शेअर्स व्यतिरिक्त, देखील गणना करतो मर्क्ला झाड असे सर्व शेअर्स, आणि प्रत्येक सहभागीला एन्कोड केलेला शेअर स्वतः आणि मर्कल ट्रीचे रूट आणि मर्कल ट्रीमध्ये शेअरच्या समावेशाचा पुरावा पाठवतो. स्टेप (2) मधील एकमतामध्ये, सहभागींनी केवळ संचांच्या संचावरच सहमती दर्शवली नाही, तर अशा झाडांच्या विशिष्ट मुळांच्या संचावर (जर काही सहभागींनी प्रोटोकॉलपासून विचलित केले असेल, आणि वेगवेगळ्या सहभागींना वेगवेगळ्या मर्कल वृक्षाची मुळे पाठवली असतील तर, आणि अशी दोन मुळे सहमती दरम्यान दर्शविली जातात, त्याची पंक्ती निकाल सेटमध्ये समाविष्ट केलेली नाही). एकमताच्या परिणामी, आमच्याकडे 67 एन्कोड केलेल्या रेषा आणि मर्कल ट्रीची संबंधित मुळे असतील जसे की किमान 67 सहभागी असतील (संबंधित रेषा प्रस्तावित करणारे तेच असावेत असे नाही), ज्यांनी प्रत्येक 67 ओळींसाठी इरेजर कोडच्या शेअरसह संदेश आणि संबंधित झाडामध्ये त्यांचा वाटा कमी झाल्याचा पुरावा.

जेव्हा चरण (4) मध्ये सहभागी विशिष्ट स्ट्रिंगसाठी 67 बीट्सचा उलगडा करतो आणि त्यांच्याकडून मूळ स्ट्रिंगची पुनर्रचना करण्याचा प्रयत्न करतो तेव्हा पर्यायांपैकी एक शक्य आहे:

1. स्ट्रिंग पुनर्संचयित केली जाते, आणि जर ती पुन्हा इरेजर-एनकोड केली गेली आणि स्थानिकरित्या गणना केलेल्या शेअर्ससाठी मर्कल ट्रीची गणना केली गेली, तर मूळ ज्यावर एकमत झाले होते त्याच्याशी जुळते.

2. पंक्ती पुनर्संचयित केली आहे, परंतु स्थानिकरित्या गणना केलेले मूळ ज्यावर एकमत झाले होते त्याच्याशी जुळत नाही.

3. पंक्ती पुनर्संचयित केलेली नाही.

हे दर्शविणे सोपे आहे की जर पर्याय (1) वरील किमान एका सहभागीसाठी झाला असेल, तर पर्याय (1) सर्व सहभागींसाठी झाला असेल आणि त्याउलट, जर पर्याय (2) किंवा (3) कमीत कमी एका सहभागीसाठी झाला असेल, तर सर्व सहभागींसाठी पर्याय (2) किंवा (3) होईल. अशा प्रकारे, सेटमधील प्रत्येक पंक्तीसाठी, एकतर सर्व सहभागी यशस्वीरित्या ते पुनर्प्राप्त करतील किंवा सर्व सहभागी ते पुनर्प्राप्त करण्यात अयशस्वी होतील. परिणामी यादृच्छिक संख्या ही फक्त त्या पंक्तींची एक XOR असते जी सहभागी पुनर्प्राप्त करण्यात सक्षम होते.

थ्रेशोल्ड स्वाक्षर्या

यादृच्छिकतेचा दुसरा दृष्टीकोन म्हणजे BLS थ्रेशोल्ड स्वाक्षरी वापरणे. थ्रेशोल्ड स्वाक्षरीवर आधारित यादृच्छिक क्रमांक जनरेटरमध्ये वर वर्णन केलेल्या इरेजर कोड-आधारित अल्गोरिदम प्रमाणेच हमी असतात, परंतु प्रत्येक व्युत्पन्न केलेल्या संख्येसाठी नेटवर्कवर पाठवलेल्या संदेशांची संख्या लक्षणीयरीत्या कमी असते.

BLS स्वाक्षरी ही एक रचना आहे जी एकाधिक सहभागींना संदेशासाठी एक सामान्य स्वाक्षरी तयार करण्यास अनुमती देते. या स्वाक्षर्‍या बर्‍याचदा जागा आणि बँडविड्थ वाचवण्यासाठी वापरल्या जातात आणि एकाधिक स्वाक्षरी पाठविण्याची आवश्यकता नसते. 

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

असे दिसून आले की सहभागी वापरत असलेल्या खाजगी की एका विशिष्ट प्रकारे व्युत्पन्न केल्या गेल्या असतील, तर 67 स्वाक्षरी (किंवा अधिक, परंतु कमी नाही) एकत्रित केल्या गेल्या असतील, परिणामी स्वाक्षरी समान असेल. हे यादृच्छिकतेचे स्त्रोत म्हणून वापरले जाऊ शकते: सहभागी प्रथम काही संदेशावर सहमत आहेत की ते स्वाक्षरी करतील (हे RANDAO चे आउटपुट किंवा फक्त शेवटच्या ब्लॉकचे हॅश असू शकते, प्रत्येक वेळी ते बदलते तोपर्यंत काही फरक पडत नाही. आणि सुसंगत आहे) आणि त्यासाठी BLS स्वाक्षरी तयार करा. 67 सहभागी त्यांचे भाग प्रदान करेपर्यंत पिढीचा परिणाम अप्रत्याशित असेल आणि त्यानंतर आउटपुट आधीच पूर्वनिर्धारित असेल आणि कोणत्याही सहभागीच्या कृतींवर अवलंबून राहू शकत नाही.

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

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

शेवटी

हा लेख तांत्रिक ब्लॉग लेखांच्या मालिकेतील पहिला आहे NEAR. NEAR हे विकेंद्रित ऍप्लिकेशन्स विकसित करण्यासाठी ब्लॉकचेन प्रोटोकॉल आणि प्लॅटफॉर्म आहे ज्याचा विकास सुलभतेवर आणि अंतिम वापरकर्त्यांसाठी वापर सुलभतेवर भर आहे.

प्रोटोकॉल कोड खुला आहे, आमची अंमलबजावणी रस्टमध्ये लिहिलेली आहे, ती आढळू शकते येथे.

NEAR चा विकास कसा दिसतो ते तुम्ही पाहू शकता आणि ऑनलाइन IDE मध्ये प्रयोग करू शकता येथे.

आपण येथे रशियनमधील सर्व बातम्यांचे अनुसरण करू शकता टेलीग्राम गट आणि मध्ये VKontakte वर गट, आणि अधिकृत मध्ये इंग्रजी मध्ये ट्विटर.

Встреч скорых встреч!

स्त्रोत: www.habr.com