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

अहो हाब्र!

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

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

थोडी क्रिप्टोग्राफी

थ्रेशोल्ड स्वाक्षरी कशी कार्य करतात हे समजून घेण्यासाठी, तुम्हाला थोडे मूलभूत क्रिप्टोग्राफी समजून घेणे आवश्यक आहे. आम्ही दोन संकल्पना वापरू: स्केलर किंवा फक्त संख्या, ज्या आम्ही लोअरकेस अक्षरांनी दर्शवू (x, y) आणि लंबवर्तुळाकार वक्र वरील बिंदू, जे आपण मोठ्या अक्षरांनी दर्शवू.

थ्रेशोल्ड स्वाक्षरीच्या मूलभूत गोष्टी समजून घेण्यासाठी, काही मूलभूत गोष्टींव्यतिरिक्त, लंबवर्तुळाकार वक्र कसे कार्य करतात हे समजून घेणे आवश्यक नाही:

1. लंबवर्तुळाकार वक्र वरील बिंदू जोडले जाऊ शकतात आणि स्केलरने गुणाकार केला जाऊ शकतो (आम्ही स्केलरद्वारे गुणाकार दर्शवू xG, नोटेशन जरी Gx अनेकदा साहित्यात देखील वापरले जाते). स्केलरद्वारे बेरीज आणि गुणाकाराचा परिणाम लंबवर्तुळाकार वक्र बिंदू आहे.

2. फक्त मुद्दा जाणून G आणि त्याचे उत्पादन स्केलरसह xG गणना करता येत नाही x.

आपण बहुपदीची संकल्पना देखील वापरू p(x) अंश k-1. विशेषतः, आम्ही बहुपदींचा खालील गुणधर्म वापरू: जर आम्हाला मूल्य माहित असेल p(x) कोणत्याही k विविध x (आणि आम्हाला याबद्दल अधिक माहिती नाही p(x)), आम्ही गणना करू शकतो p(x) इतर कोणासाठीही x.

हे मनोरंजक आहे की कोणत्याही बहुपदीसाठी p(x) आणि वक्र वर काही बिंदू Gअर्थ जाणून घेणे p(x)G कोणत्याही k भिन्न अर्थ x, आम्ही गणना देखील करू शकतो p(x)G कोणत्याही x.

थ्रेशोल्ड स्वाक्षरी कशी कार्य करतात आणि यादृच्छिक संख्या तयार करण्यासाठी त्यांचा वापर कसा करावा याच्या तपशीलांमध्ये खोदण्यासाठी ही पुरेशी माहिती आहे.

थ्रेशोल्ड स्वाक्षरींवर यादृच्छिक क्रमांक जनरेटर

असे म्हणूया n सहभागींना एक यादृच्छिक क्रमांक व्युत्पन्न करायचा आहे आणि कोणीही सहभागी व्हावे अशी आमची इच्छा आहे k संख्या निर्माण करण्यासाठी त्यांना पुरेसे होते, परंतु जेणेकरून हल्लेखोर जे नियंत्रित करतात k-1 किंवा त्यापेक्षा कमी सहभागी व्युत्पन्न केलेल्या संख्येचा अंदाज लावू शकत नाहीत किंवा प्रभावित करू शकत नाहीत.

समजा असा बहुपदी आहे p(x) अंश k-1 प्रथम सहभागीला काय माहित आहे पी (1), दुसऱ्याला माहीत आहे p(2), आणि असेच (n- ठाऊक आहे p(n)). आम्ही असेही गृहीत धरतो की काही पूर्वनिर्धारित बिंदूसाठी G सर्वाना माहित आहे p(x)G सर्व मूल्यांसाठी x. आम्ही कॉल करू p(i) "खाजगी घटक" iवा सहभागी (कारण फक्त iसहभागी तिला ओळखतो), आणि p(i)G "सार्वजनिक घटक" i-वा सहभागी (कारण सर्व सहभागी तिला ओळखतात). जसे तुम्हाला आठवते, ज्ञान p(i)G पुनर्संचयित करण्यासाठी पुरेसे नाही p(i).

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

यादृच्छिक संख्या निर्माण करण्यासाठी आपण अशा बहुपदीचा वापर कसा करू शकतो? सुरुवातीला, आम्हाला काही स्ट्रिंगची आवश्यकता आहे जी यापूर्वी जनरेटरसाठी इनपुट म्हणून वापरली गेली नाही. ब्लॉकचेनच्या बाबतीत, शेवटच्या ब्लॉकचा हॅश h अशा ओळीसाठी एक चांगला उमेदवार आहे. सहभागींना वापरून एक यादृच्छिक क्रमांक तयार करू द्या h बियाणे सारखे. सहभागी प्रथम रूपांतर करतात h कोणतेही पूर्वनिर्धारित फंक्शन वापरून वक्र बिंदूवर:

H = scalarToPoint(h)

मग प्रत्येक सहभागी i गणना करते आणि प्रकाशित करते हाय = p(i)H, ते काय करू शकतात कारण त्यांना माहित आहे p(i) आणि H. प्रकटीकरण Hमी इतर सहभागींना खाजगी घटक पुनर्संचयित करू देत नाही ith सहभागी, आणि म्हणून खाजगी घटकांचा एक संच ब्लॉक ते ब्लॉक वापरला जाऊ शकतो. अशा प्रकारे, खाली वर्णन केलेले महाग बहुपद जनरेशन अल्गोरिदम फक्त एकदाच कार्यान्वित करणे आवश्यक आहे.

जेव्हा k सहभागींचे शवविच्छेदन करण्यात आले हाय = p(i)H, प्रत्येकजण गणना करू शकतो Hx = p(x)H सर्वांसाठी x आम्ही शेवटच्या विभागात चर्चा केलेल्या बहुपदींच्या गुणधर्माबद्दल धन्यवाद. या क्षणी, सर्व सहभागी गणना करतात H0 = p(0)H, आणि ही परिणामी यादृच्छिक संख्या आहे. कोणाला माहीत नाही याची कृपया नोंद घ्यावी p(0), आणि म्हणून गणना करण्याचा एकमेव मार्ग आहे p(0)H - हे इंटरपोलेशन आहे p(x)H, जे तेव्हाच शक्य आहे k मूल्ये p(i)H ज्ञात कोणत्याही लहान प्रमाणात उघडणे p(i)H बद्दल कोणतीही माहिती देत ​​नाही p(0)H

वरील जनरेटरमध्ये आम्हाला हवे असलेले सर्व गुणधर्म आहेत: केवळ आक्रमणकर्ते नियंत्रित करतात k-1 किंवा त्यापेक्षा कमी सहभागींना निष्कर्षावर कोणतीही माहिती किंवा प्रभाव नाही, तर कोणताही k सहभागी परिणामी संख्या आणि कोणत्याही उपसंचाची गणना करू शकतात k सहभागी नेहमी समान बियाण्यासाठी समान निकालावर येतील.

एक समस्या आहे जी आम्ही वर काळजीपूर्वक टाळली आहे. इंटरपोलेशन कार्य करण्यासाठी, हे मूल्य महत्वाचे आहे Hi जे प्रत्येक सहभागीने प्रकाशित केले होते i ते खरोखर समान होते p(i)H शिवाय कोणीही नाही म्हणून i-व्या सहभागीला माहित नाही p(i), शिवाय कोणीही नाही i-सहभागी ते सत्यापित करू शकत नाही Hi प्रत्यक्षात अचूकपणे आणि कोणत्याही क्रिप्टोग्राफिक पुराव्याशिवाय गणना केली Hमी एक आक्रमणकर्ता म्हणून कोणतेही मूल्य प्रकाशित करू शकतो हाय, आणि यादृच्छिक संख्या जनरेटरच्या आउटपुटवर अनियंत्रितपणे प्रभाव पाडतात:

पहिल्या सहभागीने पाठवलेल्या H_1 ची भिन्न मूल्ये भिन्न परिणाम H_0 कडे घेऊन जातात

अचूकता सिद्ध करण्याचे किमान दोन मार्ग आहेत Hi, आम्ही बहुपदीच्या पिढीचे विश्लेषण केल्यानंतर त्यांचा विचार करू.

बहुपदी पिढी

शेवटच्या विभागात आपण असे गृहीत धरले आहे की आपल्याकडे अशी बहुपदी आहे p(x) अंश k-1 की सहभागी i माहित आहे p(i), आणि इतर कोणाकडेही या मूल्याबद्दल कोणतीही माहिती नाही. पुढील भागात आपल्याला काही पूर्वनिर्धारित मुद्द्यासाठी देखील याची आवश्यकता असेल G सर्वांना माहित होते p(x)G सर्वांसाठी x.

या विभागात आम्ही असे गृहीत धरू की प्रत्येक सहभागीकडे स्थानिक पातळीवर काही खाजगी की आहे xi, प्रत्येकाला संबंधित सार्वजनिक की माहीत आहे Xi.

एक संभाव्य बहुपदी जनरेशन प्रोटोकॉल खालीलप्रमाणे आहे:

1. प्रत्येक सहभागी i स्थानिक पातळीवर एक अनियंत्रित बहुपद तयार करते pi(x) डिग्री k-1. त्यानंतर ते प्रत्येक सहभागीला पाठवतात j अर्थ pi(j), सार्वजनिक की सह एनक्रिप्ट केलेले Xj. अशा प्रकारे फक्त i-वाई и j-वाई सहभागी माहित आहे pi(j). सहभागी i जाहीरपणे देखील जाहीर करते pi(j)G सर्वांसाठी j पासून 1 ते k समावेशक

2. सर्व सहभागी निवडण्यासाठी काही एकमत वापरतात k सहभागी ज्यांचे बहुपद वापरले जाईल. काही सहभागी ऑफलाइन असल्याने, आम्ही प्रत्येकजण होईपर्यंत प्रतीक्षा करू शकत नाही n सहभागी बहुपदी प्रकाशित करतील. या चरणाचा परिणाम एक संच आहे Z किमान समावेश k स्टेपमध्ये बनवलेले बहुपद (1).

3. सहभागी खात्री करतात की त्यांना माहित असलेली मूल्ये pi(j) सार्वजनिकरित्या घोषित केलेल्याशी संबंधित आहे pi(j)G या चरणानंतर Z केवळ बहुपदी ज्यासाठी खाजगीरित्या प्रसारित केले जातात pi(j) सार्वजनिकरित्या घोषित केलेल्याशी संबंधित आहे pi(j)G

4. प्रत्येक सहभागी j त्याच्या खाजगी घटकाची गणना करते p(j) बेरीज म्हणून pi(j) सर्वांसाठी i в Z. प्रत्येक सहभागी सर्व मूल्यांची गणना देखील करतो p(x)G बेरीज म्हणून सर्व i साठी pi(x)G в Z.

लक्षात ठेवा की p(x) - हे खरोखर बहुपदी आहे k-1, कारण ती व्यक्तीची बेरीज आहे pi(x), त्यातील प्रत्येक पदवीचा बहुपदी आहे k-1. नंतर, प्रत्येक सहभागी असताना लक्षात ठेवा j माहित आहे p(j), त्यांना याबद्दल कोणतीही माहिती नाही p(x) ते x ≠ j. खरंच, या मूल्याची गणना करण्यासाठी, त्यांना सर्वकाही माहित असणे आवश्यक आहे pi(x), आणि जोपर्यंत सहभागी आहे j निवडलेल्या बहुपदांपैकी किमान एक माहीत नाही, त्यांच्याकडे पुरेशी माहिती नाही p(x).

ही संपूर्ण बहुपदी निर्मिती प्रक्रिया आहे जी शेवटच्या विभागात आवश्यक होती. वरील चरण 1, 2 आणि 4 ची अगदी स्पष्ट अंमलबजावणी आहे. पण तिसरी पायरी इतकी क्षुल्लक नाही.

विशेषत:, आम्ही ते कूटबद्ध असल्याचे सिद्ध करण्यास सक्षम असणे आवश्यक आहे pi(j) खरोखर प्रकाशित केलेल्याशी संबंधित आहे pi(j)G आम्ही ते सिद्ध करू शकत नसल्यास, हल्लेखोर i त्याऐवजी कचरा पाठवू शकतो pi(j) ते सहभागी j, आणि सहभागी j वास्तविक मूल्य मिळू शकणार नाही pi(j), आणि त्याच्या खाजगी घटकाची गणना करू शकणार नाही.

एक क्रिप्टोग्राफिक प्रोटोकॉल आहे जो आपल्याला अतिरिक्त संदेश तयार करण्यास अनुमती देतो पुरावाi(j), जसे की कोणत्याही सहभागीला काही मूल्य आहे e, आणि देखील पुरावा(j) и pi(j)G, स्थानिक पातळीवर ते सत्यापित करू शकतो e - खरच pi(j), सहभागी की सह कूटबद्ध j. दुर्दैवाने, अशा पुराव्यांचा आकार आश्चर्यकारकपणे मोठा आहे आणि ते प्रकाशित करणे आवश्यक आहे O(nk) असे पुरावे यासाठी वापरले जाऊ शकत नाहीत.

ते सिद्ध करण्याऐवजी pi(j) च्याशी संबंधित आहे pi(j)G आम्ही बहुपदी जनरेशन प्रोटोकॉलमध्ये बराच वेळ वाटप करू शकतो, ज्या दरम्यान सर्व सहभागी प्राप्त एनक्रिप्टेड तपासतात. pi(j), आणि जर डिक्रिप्ट केलेला संदेश लोकांशी संबंधित नसेल pi(j)G, ते एक क्रिप्टोग्राफिक पुरावा प्रकाशित करतात की त्यांना मिळालेला एनक्रिप्टेड संदेश चुकीचा आहे. तो संदेश सिद्ध करा नाही च्याशी संबंधित आहे pi(G) ते जुळते हे सिद्ध करण्यापेक्षा खूप सोपे. हे लक्षात घेतले पाहिजे की यासाठी प्रत्येक सहभागीने असा पुरावा तयार करण्यासाठी दिलेल्या वेळेत किमान एकदा ऑनलाइन दिसणे आवश्यक आहे आणि त्यांनी असा पुरावा प्रकाशित केल्यास, तो त्याच वाटप केलेल्या वेळेत इतर सर्व सहभागींपर्यंत पोहोचेल या गृहितकावर अवलंबून आहे.

या कालावधीत जर एखादा सहभागी ऑनलाइन दिसला नाही आणि त्याच्याकडे कमीत कमी एक चुकीचा घटक असेल, तर तो विशिष्ट सहभागी पुढील संख्या निर्मितीमध्ये भाग घेऊ शकणार नाही. प्रोटोकॉल, तथापि, किमान असल्यास कार्य करेल k सहभागी ज्यांना एकतर नुकतेच योग्य घटक मिळाले आहेत किंवा वाटप केलेल्या वेळेत चुकीचा पुरावा सोडण्यात व्यवस्थापित केले आहे.

H_i च्या अचूकतेचे पुरावे

शेवटचा भाग ज्यावर चर्चा करायची आहे ती म्हणजे प्रकाशित केलेली शुद्धता कशी सिद्ध करावी Hमी, म्हणजे हाय = p(i)H, न उघडता p(i).

आपण मूल्ये लक्षात ठेवा H, G, p(i)G सार्वजनिक आणि प्रत्येकाला ज्ञात. ऑपरेशन प्राप्त करा p(i) जाणून घेणे p(i)G и G स्वतंत्र लॉगरिथम म्हणतात, किंवा dlog आणि आम्ही हे सिद्ध करू इच्छितो:

dlog(p(i)G, G) = dlog(Hi, H)

उघड न करता p(i). अशा पुराव्यासाठी बांधकामे अस्तित्वात आहेत, उदाहरणार्थ Schnorr प्रोटोकॉल.

या डिझाइनसह, प्रत्येक सहभागी, सोबत Hi डिझाइननुसार अचूकतेचा पुरावा पाठवते.

एकदा यादृच्छिक क्रमांक व्युत्पन्न झाल्यानंतर, तो अनेकदा जनरेट करणाऱ्यांव्यतिरिक्त इतर सहभागींनी वापरला जाणे आवश्यक आहे. अशा सहभागींनी क्रमांकासह, सर्वांना पाठवणे आवश्यक आहे Hi आणि संबंधित पुरावे.

एक जिज्ञासू वाचक विचारू शकतो: अंतिम यादृच्छिक संख्या असल्याने H0, आणि p(0)जी - ही सार्वजनिक माहिती आहे, आम्हाला प्रत्येक व्यक्तीसाठी पुरावा का हवा आहे Hमी, त्याऐवजी पुरावा का पाठवत नाही

dlog(p(0)G, G) = dlog(H0, H)

समस्या अशी आहे की असा पुरावा Schnorr प्रोटोकॉल वापरून तयार केला जाऊ शकत नाही कारण कोणालाही त्याचे मूल्य माहित नाही पी (0), पुरावा तयार करण्यासाठी आवश्यक आहे, आणि आणखी काय, संपूर्ण यादृच्छिक संख्या जनरेटर या वस्तुस्थितीवर आधारित आहे की हे मूल्य कोणालाही माहित नाही. त्यामुळे सर्व मूल्ये असणे आवश्यक आहे Hi आणि अचूकता सिद्ध करण्यासाठी त्यांचे वैयक्तिक पुरावे H0.

तथापि, जर लंबवर्तुळाकार वक्र बिंदूंवर काही ऑपरेशन केले असेल जे शब्दार्थाने गुणाकार सारखे असेल, तर अचूकतेचा पुरावा H0 क्षुल्लक असेल, आम्ही फक्त याची खात्री करू

Hएक्सएनयूएमएक्स × G = p(0)G × H

जर निवडलेला वक्र समर्थन देत असेल लंबवर्तुळाकार वक्र जोड्या, हा पुरावा कार्य करतो. या प्रकरणात H0 हे केवळ यादृच्छिक क्रमांक जनरेटरचे आउटपुट नाही, जे कोणत्याही सहभागीद्वारे सत्यापित केले जाऊ शकते ज्याला माहित आहे जी, एच и p(0)G. एच0 ही संदेशावर एक स्वाक्षरी देखील आहे जी एक बीज म्हणून वापरली गेली होती, याची पुष्टी करते k и n सहभागींनी या संदेशावर स्वाक्षरी केली. अशा प्रकारे, जर बियाणे - ब्लॉकचेन प्रोटोकॉलमधील ब्लॉकचा हॅश आहे H0 ब्लॉकवर एक बहु-स्वाक्षरी आणि खूप चांगली यादृच्छिक संख्या दोन्ही आहे.

शेवटी

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

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

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

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

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

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