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

हे हबर!

В पहले भाग इस लेख में, हमने चर्चा की कि उन प्रतिभागियों के लिए यादृच्छिक संख्याएँ उत्पन्न करना क्यों आवश्यक हो सकता है जो एक-दूसरे पर भरोसा नहीं करते हैं, ऐसे यादृच्छिक संख्या जनरेटर के लिए क्या आवश्यकताएँ रखी गई हैं, और उनके कार्यान्वयन के लिए दो दृष्टिकोणों पर विचार किया गया है।

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

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

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

थ्रेशोल्ड हस्ताक्षरों की मूल बातें समझने के लिए, आपको कुछ बुनियादी चीज़ों के अलावा, यह समझने की ज़रूरत नहीं है कि अण्डाकार वक्र कैसे काम करते हैं:

1. एक अण्डाकार वक्र पर बिंदुओं को जोड़ा जा सकता है और एक अदिश से गुणा किया जा सकता है (हम एक अदिश द्वारा गुणन को इस प्रकार निरूपित करेंगे) xG, हालांकि संकेतन Gx अक्सर साहित्य में भी प्रयोग किया जाता है)। एक अदिश द्वारा जोड़ और गुणा करने का परिणाम एक अण्डाकार वक्र पर एक बिंदु होता है।

2. सिर्फ बात को जानना G और इसका गुणनफल एक अदिश राशि से होता है xG गणना नहीं की जा सकती x.

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

यह किसी भी बहुपद के लिए दिलचस्प है p (x) और वक्र पर कुछ बिंदु Gअर्थ जानना पी(एक्स)जी किसी के लिए k विभिन्न अर्थ x, हम गणना भी कर सकते हैं पी(एक्स)जी किसी के लिए x.

थ्रेशोल्ड हस्ताक्षर कैसे काम करते हैं और यादृच्छिक संख्याएँ उत्पन्न करने के लिए उनका उपयोग कैसे करें, इसके विवरण को समझने के लिए यह पर्याप्त जानकारी है।

दहलीज हस्ताक्षरों पर यादृच्छिक संख्या जनरेटर

चलिए ऐसा कहते हैं n प्रतिभागी एक यादृच्छिक संख्या उत्पन्न करना चाहते हैं, और हम चाहते हैं कि कोई भी भाग ले k संख्या उत्पन्न करने के लिए उनमें से पर्याप्त थे, लेकिन ताकि हमलावरों पर नियंत्रण हो सके k-1 या उससे कम प्रतिभागी उत्पन्न संख्या का अनुमान नहीं लगा सकते थे या उसे प्रभावित नहीं कर सकते थे।

मान लीजिए कि ऐसा कोई बहुपद है p (x) डिग्री k-1 पहला प्रतिभागी क्या जानता है पी (1), दूसरा जानता है पी(2), और इसी तरह (n-वें जानता है पी (एन)). हम यह भी मानते हैं कि किसी पूर्वनिर्धारित बिंदु के लिए G सब जानते हैं पी(एक्स)जी सभी मूल्यों के लिए x. हम कॉल करेंगे पी(आई) "निजी घटक" iवें प्रतिभागी (क्योंकि केवल iवें प्रतिभागी उसे जानता है), और सुअर "सार्वजनिक घटक" i-वें प्रतिभागी (क्योंकि सभी प्रतिभागी उसे जानते हैं)। जैसा कि आपको याद है, ज्ञान सुअर पुनर्स्थापित करने के लिए पर्याप्त नहीं है पी(आई).

ऐसे बहुपद की रचना करना ताकि केवल i-पहला प्रतिभागी और कोई भी उसके निजी घटक को नहीं जानता था - यह प्रोटोकॉल का सबसे जटिल और दिलचस्प हिस्सा है, और हम इसका विश्लेषण नीचे करेंगे। अभी के लिए, मान लें कि हमारे पास ऐसा बहुपद है और सभी प्रतिभागी अपने निजी घटकों को जानते हैं।

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

एच = स्केलारटूप्वाइंट(एच)

फिर प्रत्येक प्रतिभागी i गणना करता है और प्रकाशित करता है हाय = पी(आई)एच, वे क्या कर सकते हैं क्योंकि वे जानते हैं पी(आई) और एच. प्रकटीकरण Hमैं अन्य प्रतिभागियों को निजी घटक को पुनर्स्थापित करने की अनुमति नहीं देता iवें प्रतिभागी, और इसलिए निजी घटकों के एक सेट का उपयोग ब्लॉक से ब्लॉक तक किया जा सकता है। इस प्रकार, नीचे वर्णित महंगी बहुपद पीढ़ी एल्गोरिदम को केवल एक बार निष्पादित करने की आवश्यकता है।

जब k प्रतिभागियों का शव परीक्षण किया गया हाय = पी(आई)एच, हर कोई गणना कर सकता है Hएक्स = पी(एक्स)एच सभी के लिए x बहुपदों के गुणधर्म के लिए धन्यवाद जिसकी हमने पिछले भाग में चर्चा की थी। इस समय, सभी प्रतिभागी गणना करते हैं H0 = p(0)H, और यह परिणामी यादृच्छिक संख्या है. कृपया ध्यान दें कि कोई नहीं जानता पी(0), और इसलिए गणना करने का एकमात्र तरीका पी(0)एच - यह अंतर्वेशन है पी(एक्स)एच, जो तभी संभव है जब k मूल्यों पी(आई)एच ज्ञात। किसी भी छोटी मात्रा को खोलना पी(आई)एच के बारे में कोई जानकारी नहीं देता पी(0)एच.

उपरोक्त जनरेटर में वे सभी गुण हैं जो हम चाहते हैं: केवल हमलावरों को नियंत्रित करना k-1 या उससे कम प्रतिभागियों के पास निष्कर्ष पर कोई जानकारी या प्रभाव नहीं है, जबकि कोई भी k प्रतिभागी परिणामी संख्या और किसी भी उपसमूह की गणना कर सकते हैं k प्रतिभागी हमेशा एक ही बीज के लिए एक ही परिणाम पर आएंगे।

एक समस्या है जिसे हमने ऊपर सावधानीपूर्वक टाला है। इंटरपोलेशन के काम करने के लिए, यह महत्वपूर्ण है कि मूल्य Hi जिसे प्रत्येक प्रतिभागी द्वारा प्रकाशित किया गया था i यह वास्तव में वैसा ही था पी(आई)एच. चूंकि कोई नहीं सिवाय i-वें प्रतिभागी को नहीं पता पी(आई), सिवाय कोई नहीं i-वां प्रतिभागी इसे सत्यापित नहीं कर सकता Hi वास्तव में सही ढंग से गणना की गई, और शुद्धता के किसी भी क्रिप्टोग्राफ़िक प्रमाण के बिना Hमैं एक हमलावर के रूप में कोई भी मूल्य प्रकाशित कर सकता हूं हाय, और यादृच्छिक संख्या जनरेटर के आउटपुट को मनमाने ढंग से प्रभावित करते हैं:

पहले प्रतिभागी द्वारा भेजे गए H_1 के अलग-अलग मान अलग-अलग परिणामी H_0 की ओर ले जाते हैं

सही साबित करने के कम से कम दो तरीके हैं Hमैं, बहुपद की पीढ़ी का विश्लेषण करने के बाद उन पर विचार करूंगा।

बहुपद पीढ़ी

पिछले भाग में हमने मान लिया था कि हमारे पास एक ऐसा बहुपद है p (x) डिग्री k-1 वह प्रतिभागी i वह जानता है कि पी(आई), और किसी अन्य को इस मूल्य के बारे में कोई जानकारी नहीं है। अगले भाग में हमें किसी पूर्व निर्धारित बिंदु के लिए उसकी भी आवश्यकता होगी G सब जानते थे पी(एक्स)जी सभी के लिए x.

इस अनुभाग में हम मान लेंगे कि प्रत्येक प्रतिभागी के पास स्थानीय रूप से कुछ निजी कुंजी है ग्यारहवीं, ताकि हर कोई संबंधित सार्वजनिक कुंजी को जान सके Xi.

एक संभावित बहुपद पीढ़ी प्रोटोकॉल इस प्रकार है:

1. प्रत्येक प्रतिभागी i स्थानीय रूप से एक मनमाना बहुपद बनाता है pi(x) डिग्री k-1. फिर वे प्रत्येक प्रतिभागी को भेजते हैं j मूल्य pi(j), सार्वजनिक कुंजी के साथ एन्क्रिप्टेड एक्सजे. इस प्रकार केवल i-वें и j-वें प्रतिभागी को पता है pमैं(जे). प्रतिभागी i सार्वजनिक रूप से घोषणा भी करता है पीआई(जे)जी सभी के लिए j से 1 से k समावेशी।

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

3. प्रतिभागी यह सुनिश्चित करें कि वे जिन मूल्यों को जानते हैं pi(j) सार्वजनिक रूप से घोषित के अनुरूप है पीआई(जे)जी. इसके बाद अंदर कदम रखें Z केवल बहुपद जिसके लिए निजी तौर पर प्रसारित किया जाता है pi(j) सार्वजनिक रूप से घोषित के अनुरूप है पीआई(जे)जी.

4. प्रत्येक प्रतिभागी j इसके निजी घटक की गणना करता है पी(जे) एक राशि के रूप में pमैं(जे) सबके लिए i в Z. प्रत्येक प्रतिभागी सभी मूल्यों की गणना भी करता है पी(एक्स)जी एक राशि के रूप में सभी i के लिए pi(x)G в Z.

ध्यान दें कि पी(एक्स) – यह वास्तव में एक बहुपद है के-1, क्योंकि यह व्यक्ति का योग है pi(x), जिनमें से प्रत्येक डिग्री का बहुपद है k-1. फिर, ध्यान दें कि प्रत्येक प्रतिभागी j वह जानता है कि पी(जे), उन्हें इसके बारे में कोई जानकारी नहीं है p (x) के लिए एक्स ≠ जे. दरअसल, इस मूल्य की गणना करने के लिए, उन्हें सब कुछ जानने की जरूरत है पाई(एक्स), और जब तक प्रतिभागी j चयनित बहुपदों में से कम से कम एक को नहीं जानता, उनके पास इसके बारे में पर्याप्त जानकारी नहीं है पी(एक्स).

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

विशेष रूप से, हमें यह साबित करने में सक्षम होने की आवश्यकता है कि यह एन्क्रिप्टेड है pi(j) वास्तव में प्रकाशित लोगों से मेल खाता है पीआई(जे)जी. यदि हम इसे साबित नहीं कर सकते, तो हमलावर i इसके बजाय कचरा भेज सकते हैं pi(j)प्रतिभागी को j, और प्रतिभागी j वास्तविक मूल्य नहीं मिल पाएगा पाई(जे), और इसके निजी घटक की गणना नहीं कर पाएगा.

एक क्रिप्टोग्राफ़िक प्रोटोकॉल है जो आपको एक अतिरिक्त संदेश बनाने की अनुमति देता है प्रमाणi(j), जैसे कि कोई भी प्रतिभागी, जिसका कुछ मूल्य हो e, तथा प्रूफ़ी(जे) и pi(j)G, स्थानीय स्तर पर इसे सत्यापित कर सकता है e - यह सच है पाई(जे), प्रतिभागी की कुंजी के साथ एन्क्रिप्ट किया गया j. दुर्भाग्य से, ऐसे सबूतों का आकार अविश्वसनीय रूप से बड़ा है, और इसे प्रकाशित करना आवश्यक है हे (nk) इस उद्देश्य के लिए ऐसे साक्ष्य का उपयोग नहीं किया जा सकता।

इसे साबित करने के बजाय पाई(जे) से मेल खाती है pi(j)G हम बहुपद पीढ़ी प्रोटोकॉल में बहुत लंबी अवधि आवंटित कर सकते हैं, जिसके दौरान सभी प्रतिभागी प्राप्त एन्क्रिप्टेड की जांच करते हैं पाई(जे), और यदि डिक्रिप्ट किया गया संदेश जनता के अनुरूप नहीं है pi(j)G, वे एक क्रिप्टोग्राफ़िक प्रमाण प्रकाशित करते हैं कि उन्हें प्राप्त एन्क्रिप्टेड संदेश गलत है। उस संदेश को सिद्ध करें नहीं से मेल खाती है सुअर) यह साबित करने से कहीं अधिक आसान है कि यह मेल खाता है। यह ध्यान दिया जाना चाहिए कि इसके लिए प्रत्येक प्रतिभागी को ऐसे साक्ष्य बनाने के लिए आवंटित समय के दौरान कम से कम एक बार ऑनलाइन उपस्थित होने की आवश्यकता होती है, और यह इस धारणा पर निर्भर करता है कि यदि वे ऐसा प्रमाण प्रकाशित करते हैं, तो यह उसी आवंटित समय में अन्य सभी प्रतिभागियों तक पहुंच जाएगा।

यदि कोई प्रतिभागी इस अवधि के दौरान ऑनलाइन उपस्थित नहीं हुआ, और उसके पास कम से कम एक गलत घटक था, तो वह विशेष प्रतिभागी आगे की संख्या सृजन में भाग नहीं ले पाएगा। हालाँकि, प्रोटोकॉल तब भी कार्य करेगा यदि कम से कम है k जिन प्रतिभागियों को या तो सही घटक प्राप्त हुए या आवंटित समय के भीतर गलतता का प्रमाण छोड़ने में कामयाब रहे।

H_i की शुद्धता के प्रमाण

अंतिम भाग जिस पर चर्चा बाकी है वह यह है कि प्रकाशित की सत्यता को कैसे सिद्ध किया जाए Hमैं, अर्थात् वह हाय = पी(आई)एच, बिना खोले पी(आई).

आइए याद रखें कि मूल्य एच, जी, पी(i)जी सार्वजनिक और सभी को ज्ञात। ऑपरेशन प्राप्त करें पी(आई) जानने सुअर и G असतत लघुगणक कहा जाता है, या डीलॉग, और हम यह साबित करना चाहते हैं:

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

बिना प्रकटीकरण के पी(आई). उदाहरण के लिए, ऐसे प्रमाणों के निर्माण मौजूद हैं श्नोर प्रोटोकॉल.

इस डिज़ाइन के साथ, प्रत्येक प्रतिभागी के साथ Hi डिज़ाइन के अनुसार शुद्धता का प्रमाण भेजता है।

एक बार जब एक यादृच्छिक संख्या उत्पन्न हो जाती है, तो इसे अक्सर इसे उत्पन्न करने वालों के अलावा अन्य प्रतिभागियों द्वारा उपयोग करने की आवश्यकता होती है। ऐसे प्रतिभागियों को नंबर सहित सभी भेजना होगा Hi और संबंधित साक्ष्य।

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

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

समस्या यह है कि Schnorr प्रोटोकॉल का उपयोग करके ऐसा प्रमाण नहीं बनाया जा सकता क्योंकि कोई भी इसका मूल्य नहीं जानता है पी (0), प्रमाण बनाने के लिए आवश्यक है, और इससे भी अधिक, संपूर्ण यादृच्छिक संख्या जनरेटर इस तथ्य पर आधारित है कि कोई भी इस मान को नहीं जानता है। इसलिए सभी मूल्यों का होना आवश्यक है Hi और सत्यता साबित करने के लिए उनके व्यक्तिगत साक्ष्य H0.

हालाँकि, यदि अण्डाकार वक्रों पर बिंदुओं पर कुछ ऑपरेशन होता है जो शब्दार्थिक रूप से गुणन के समान होता है, तो शुद्धता का प्रमाण H0 यह तुच्छ होगा, हम बस यह सुनिश्चित करेंगे

H0 × G = पी(0)जी × एच

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

अंत में

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

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

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

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

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

स्रोत: www.habr.com