Trending News

BTC
ETH
LTC
DASH
XMR
NXT
ETC

वर्कल ट्री स्ट्रक्चर | एथेरियम फाउंडेशन ब्लॉग

0


वर्कल ट्री एक प्रतिबद्धता योजना है जो मर्कल ट्री के समान काम करती है, लेकिन इसमें बहुत कम गवाह होते हैं। यह मर्कल ट्री में हैश को वेक्टर प्रतिबद्धता के साथ बदलकर काम करता है, जो व्यापक शाखाओं वाले कारकों को अधिक कुशल बनाता है।

पोस्ट पर प्रतिक्रिया के लिए केवौंड्रे वेडरबर्न को धन्यवाद।

अवलोकन

वर्कल पेड़ कैसे काम करते हैं, इसके विवरण के लिए देखें:


इस पोस्ट का उद्देश्य के ठोस लेआउट की व्याख्या करना है ड्राफ्ट वर्कल ट्री EIP. इसका उद्देश्य उन क्लाइंट डेवलपर्स के लिए है जो वर्कल ट्री को लागू करना चाहते हैं और ईआईपी में गहराई से जाने से पहले एक परिचय की तलाश कर रहे हैं।

वर्कल पेड़ पेड़ की संरचना में कई बदलाव पेश करते हैं। सबसे महत्वपूर्ण परिवर्तन हैं:

  • 20 बाइट कुंजियों से 32 बाइट कुंजियों पर स्विच (32 बाइट पतों के साथ भ्रमित नहीं होना चाहिए, जो एक अलग परिवर्तन है);
  • खाते और संग्रहण का विलय प्रयास करता है; और अंत में
  • वर्कल ट्री का परिचय स्वयं है, जो हैश के बजाय वेक्टर प्रतिबद्धताओं का उपयोग करता है।

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

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

बैंडर्सनैच का वक्र क्रम/स्केलर क्षेत्र आकार है पी = 13108968793781547619861935127046491459309155893440570251786403306729687672801, जो 253 बिट प्राइम है। इसके परिणामस्वरूप, हम केवल अधिकतम 252 बिट्स के बिट स्ट्रिंग्स के लिए सुरक्षित रूप से प्रतिबद्ध हो सकते हैं, अन्यथा फ़ील्ड ओवरफ्लो हो जाती है। हमने वर्कल ट्री के लिए 256 का एक शाखा कारक (चौड़ाई) चुना, जिसका अर्थ है कि प्रत्येक प्रतिबद्धता 252 बिट्स प्रत्येक के 256 मानों तक प्रतिबद्ध हो सकती है (या सटीक होने के लिए, पूर्णांक तक पी – 1) हम इसे इस प्रकार लिखते हैं कमिट (v₀, v₁, …, v₂₅₅) सूची में प्रतिबद्ध करने के लिए वी लंबाई 256.

वर्कल ट्री का लेआउट

वर्कल ट्री ईआईपी के साथ डिजाइन लक्ष्यों में से एक है पड़ोसी पदों तक पहुंच बनाना (उदाहरण के लिए लगभग एक ही पते या पड़ोसी कोड भाग के साथ भंडारण) तक पहुंच के लिए सस्ता। ऐसा करने के लिए, एक कुंजी में a . होता है तना 31 बाइट्स और a प्रत्यय कुल 32 बाइट्स के लिए एक बाइट का। मुख्य योजना इस तरह से डिज़ाइन की गई है कि “करीबी” भंडारण स्थानों को एक ही स्टेम और एक अलग प्रत्यय में मैप किया जाता है। विवरण के लिए कृपया देखें ईआईपी ड्राफ्ट.

वर्कल ट्री तब दो प्रकार के नोड्स से बना होता है:

  • एक्सटेंशन नोड्सजो एक ही तने लेकिन भिन्न प्रत्यय वाले 256 मानों का प्रतिनिधित्व करते हैं
  • आंतरिक नोड्सजिसमें अधिकतम 256 बच्चे हैं, जो या तो अन्य आंतरिक नोड या एक्सटेंशन नोड हो सकते हैं।

एक विस्तार नोड के प्रति प्रतिबद्धता एक 4 तत्व वेक्टर के प्रति प्रतिबद्धता है; शेष स्थान 0 होंगे। यह है:

C₁ और C₂ दो और प्रतिबद्धताएं हैं जो के बराबर स्टेम वाले सभी मूल्यों के लिए प्रतिबद्ध हैं तना. हमें प्रतिबद्धताओं की आवश्यकता का कारण यह है कि मानों में 32 बाइट्स होते हैं, लेकिन हम प्रति फ़ील्ड तत्व केवल 252 बिट्स ही स्टोर कर सकते हैं। इस प्रकार एक एकल प्रतिबद्धता 256 मूल्यों को संग्रहीत करने के लिए पर्याप्त नहीं होगी। इसलिए इसके बजाय C₁ प्रत्यय 0 से 127 के लिए मानों को संग्रहीत करता है, और C₂ 128 से 255 तक संग्रहीत करता है, जहां फ़ील्ड आकार में फ़िट होने के लिए मानों को दो में विभाजित किया जाता है (हम उस पर बाद में आएंगे।)

प्रतिबद्धताओं सी₁ और सी₂ के साथ विस्तार को “विस्तार-और-प्रत्यय वृक्ष” (संक्षिप्त के लिए ईएएस) के रूप में जाना जाता है।


आकृति 1 कुंजी के लिए एक वर्कल पेड़ के माध्यम से चलने का प्रतिनिधित्व 0xfe0002abcd..ff04: पथ 3 आंतरिक नोड्स के माध्यम से जाता है जिसमें प्रत्येक में 256 बच्चे (254, 0, 2) होते हैं, एक एक्सटेंशन नोड का प्रतिनिधित्व करता है एबीसीडी..एफएफ और दो प्रत्यय वृक्ष प्रतिबद्धताएं, जिनमें के लिए मूल्य शामिल है 04, वी। ध्यान दें कि तना आंतरिक नोड्स के माध्यम से पथ सहित, वास्तव में कुंजी के पहले 31 बाइट्स हैं।

लीफ नोड्स के मूल्यों के प्रति प्रतिबद्धता

प्रत्येक एक्सटेंशन और प्रत्यय ट्री नोड में 256 मान होते हैं। क्योंकि एक मान 256 बिट चौड़ा है, और हम केवल 252 बिट्स को एक फ़ील्ड तत्व में सुरक्षित रूप से संग्रहीत कर सकते हैं, यदि हम केवल एक फ़ील्ड तत्व में एक मान को संग्रहीत करने का प्रयास करते हैं तो चार बिट खो जाएंगे।

इस समस्या को दूर करने के लिए, हमने 256 मानों के समूह को 128 मानों के दो समूहों में विभाजित करना चुना। एक समूह में प्रत्येक 32-बाइट मान को दो 16-बाइट मानों में विभाजित किया जाता है। तो एक मान vᵢ∈ को v⁽ˡᵒʷᵉʳ⁾ᵢ और v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ में बदल दिया जाता है जैसे कि v⁽ˡᵒʷᵉʳ⁾ᵢ ++ v⁽ᵘᵖᵖᵉʳ⁾ᵢ= vᵢ।

एक “लीफ मार्कर” को v⁽ˡᵒʷᵉʳ⁾ᵢ में ​​जोड़ा जाता है, एक ऐसे पत्ते के बीच अंतर करने के लिए जिसे कभी एक्सेस नहीं किया गया है और एक पत्ता जिसे 0s के साथ ओवरराइट किया गया है। वर्कल ट्री से कभी भी कोई मान नहीं हटाया जाता है. यह आगामी राज्य समाप्ति योजनाओं के लिए आवश्यक है। वह मार्कर 129वें बिट पर सेट है, अर्थात v⁽ˡᵒʷᵉʳ = v⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ यदि vᵢ को पहले एक्सेस किया गया है, और v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0 यदि vᵢ को कभी एक्सेस नहीं किया गया है।

दो प्रतिबद्धताओं C₁ और C₂ को तब परिभाषित किया जाता है:

विस्तार नोड्स की प्रतिबद्धता

एक एक्सटेंशन नोड के प्रति प्रतिबद्धता एक “एक्सटेंशन मार्कर” से बनी होती है, जो सिर्फ नंबर 1 है, दो उप-प्रतिबद्धताएं C₁ और C₂, और तना इस एक्सटेंशन नोड की ओर ले जाने वाली कुंजी।

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

आंतरिक नोड्स की प्रतिबद्धता

आंतरिक नोड्स में उनकी प्रतिबद्धताओं के लिए सरल गणना पद्धति होती है: नोड को 256 मानों के वेक्टर के रूप में देखा जाता है, जो कि उनके प्रत्येक 256 उपट्री की मूल प्रतिबद्धता (क्षेत्र का प्रतिनिधित्व) है। एक खाली सबट्री के लिए प्रतिबद्धता 0 है। यदि सबट्री खाली नहीं है, तो आंतरिक नोड के लिए प्रतिबद्धता है

जहां Cᵢ आंतरिक नोड के बच्चे हैं, और 0 यदि कोई बच्चा खाली है।

पेड़ में सम्मिलन

चित्र 2 पेड़ में एक नया मान डालने की प्रक्रिया का एक उदाहरण है, जो तब दिलचस्प हो जाता है जब तने कई प्रारंभिक बाइट्स पर टकराते हैं।

चित्र 2 मान v₁₉₂ स्थान पर डाला गया है 0000010000…0000 एक वर्कल ट्री में जिसमें केवल मान v₁₂₇ स्थान पर होता है 0000000000…0000. चूंकि तने तीसरे बाइट में भिन्न होते हैं, इसलिए भिन्न बाइट तक दो आंतरिक नोड्स जोड़े जाते हैं। फिर एक और “एक्सटेंशन-एंड-प्रत्यय” पेड़ डाला जाता है, जिसमें पूर्ण 31-बाइट स्टेम होता है। प्रारंभिक नोड अछूता है, और C²₀ का वही मान है जो सम्मिलन से पहले C⁰₀ है।

उथले पेड़, छोटे सबूत

वर्कल ट्री संरचना उथले पेड़ों के लिए बनाती है, जो संग्रहीत डेटा की मात्रा को कम करती है। हालाँकि, इसकी वास्तविक शक्ति छोटे सबूत, यानी गवाह पेश करने की क्षमता से आती है। यह अगले लेख में समझाया जाएगा।



Source link

Leave A Reply

Your email address will not be published.

Shares