एथेरियम के लिए वर्कल ट्री में एक गहरा गोता लगाएँ

मर्कल ट्री की तुलना में, ईटीएच 2.0 अपग्रेड के एक महत्वपूर्ण हिस्से के रूप में प्रूफ आकार में वर्कल ट्री में काफी सुधार किया गया है। जब एक अरब के आकार के डेटा की बात आती है, तो मर्कल ट्री प्रूफ में 1kB लगेगा, जबकि वर्कल ट्री प्रूफ को केवल 150 बाइट्स से अधिक की आवश्यकता नहीं है।

वर्कल ट्री अवधारणा 2018 में प्रस्तावित की गई थी (अधिक विवरण यहां पाया जा सकता है।) Sin7Y द्वारा 23वीं तकनीकी समीक्षा Verkle Tree के सिद्धांत को प्रदर्शित करेगी।

मर्कल ट्री

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

यह साबित करने के लिए कि (कुंजी: मान) = (06: 32) ट्री (हरा-चिह्नित) में मौजूद है, सबूत में आकृति में सभी लाल-चिह्नित नोड्स होने चाहिए।

सत्यापनकर्ता चित्र 1 में दर्शाई गई विधि के अनुसार रूट की गणना कर सकता है और फिर इसकी तुलना अपेक्षित रूट (ग्रे-चिह्नित) से कर सकता है।

यह अनुमान लगाया जा सकता है कि पेड़ की गहराई और चौड़ाई अधिक होने के साथ, प्रूफ का आकार भी बड़ा होगा (ब्रांच्ड-2 के लिए, जटिलता log_2(n) है, जबकि ब्रांच्ड-के के लिए, यह (k−1)log_k है। (एन) ।

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

वर्कल ट्री - संकल्पना

बस पेड़ की चौड़ाई बढ़ाने से इसकी गहराई कम हो सकती है, लेकिन प्रूफ का आकार कम नहीं होगा क्योंकि प्रूफ का आकार मूल log_2(n) से (k−1)log_k(n) में बदल जाता है।

अर्थात्, प्रत्येक परत के लिए, प्रोवर को (k−1) अतिरिक्त नोड जानकारी प्रदान करने की आवश्यकता होती है। पेपर वेर्कल ट्री में, जॉन कुज़्मौल ने सबूत जटिलता को कम करने के लिए एक योजना का उल्लेख किया logk(n) ।

यदि हम k=1024 सेट करते हैं, तो प्रूफ कम हो जाएगा log_2(k) = 10 गुना ।

वर्कल ट्री डिज़ाइन निम्नानुसार दिखाया गया है:

प्रत्येक नोड के लिए, जानकारी के दो भाग होते हैं: (1) मान; (2) अस्तित्व प्रमाण । उदाहरण के लिए, हरा-चिह्नित (H(k,v),π_03) दर्शाता है कि H(k,v) प्रतिबद्धता में मौजूद है C_0 और π_03 इस तर्क का प्रमाण है।

इसी तरह, (C_0,π_0) का अर्थ है कि C_0 प्रतिबद्धता में मौजूद है C_Root और π_0 इस तर्क का प्रमाण है।

पेपर वर्कल ट्री में, ऐसी अस्तित्व प्रतिबद्धता की विधि को वेक्टर प्रतिबद्धता कहा जाता है। यदि मूल डेटा के लिए अस्तित्व प्रतिबद्धता को निष्पादित करने के लिए वेक्टर प्रतिबद्धता योजना का उपयोग किया जाता है, तो O(1 ) जटिलता के साथ प्रमाण प्राप्त किया जाएगा, जबकि निर्माण प्रमाण की जटिलता और अद्यतन प्रमाण की जटिलता O(n^2),O(n) है। क्रमश।

इसलिए, एक संतुलन बनाने के लिए, K-ary Verkle Tree योजना का उपयोग कागज Verkle Tree में किया जाता है (जैसा कि चित्र 2 में दिखाया गया है) निर्माण प्रूफ, अपडेट प्रूफ और प्रूफ को O(kn),O(klogk n) की जटिलता बनाने के लिए ), हे (लॉग एन) क्रमशः।

विशिष्ट प्रदर्शन तुलना तालिका 1 में दिखाई गई है:

इस लेख में, हम कुछ विशिष्ट वेक्टर प्रतिबद्धता योजनाओं का विस्तृत परिचय प्रदान करने का इरादा नहीं रखते हैं, जिसे जॉन कुज़मौल ने अपने पेपर में अच्छी तरह से समझाया है।

सौभाग्य से, वेक्टर प्रतिबद्धता की तुलना में, हमारे पास बहुपद प्रतिबद्धता नामक एक अधिक कुशल उपकरण है।

निर्देशांक सेट (c_0,c_1,....,c_n) और एक मान सेट (y_1,y_2,....,y_n) के एक समूह को देखते हुए, आप P(c_i ) को संतुष्ट करते हुए एक बहुपद (लैग्रेंज इंटरपोलेशन ) बना सकते हैं। )=y_i , और इस बहुपद के प्रति वचनबद्धता का संचालन करें।

KZG10 और IPA सामान्य बहुपद प्रतिबद्धता योजनाएं हैं (इस बिंदु पर, प्रतिबद्धता अण्डाकार वक्र पर एक बिंदु है, आमतौर पर आकार में 32 और 48 बाइट्स के बीच)।

आधार

सिंगल पॉइंट के लिए KZG

उदाहरण के तौर पर KZG10 को लें। बहुपद P(x) के लिए, हम बहुपद प्रतिबद्धता का प्रतिनिधित्व करने के लिए [P(s)]_1 का उपयोग करते हैं।

जैसा कि हम सभी जानते हैं, P(x) के लिए, यदि P(z)=y , तो (x−z)|(P(x)−y) । अर्थात, यदि हम Q(x)=(P (x)−y)/(x−z) , तो Q(x) एक बहुपद है।

अब, हम P(x)P(x) के लिए P(z)=yP(z)=y को संतुष्ट करने के लिए एक प्रमाण उत्पन्न करते हैं। अर्थात्, [Q(s)]1[Q(s)]1 की गणना करें और इसे सत्यापनकर्ता को भेजें, जिसे सत्यापित करने की आवश्यकता है:

क्योंकि s परिमित डोमेन F में एक बेतरतीब ढंग से चुना गया बिंदु है, प्रोवर के सफल बुरे व्यवहार की संभावना डिग्री (क्यू) / पी ( श्वार्ट्ज-ज़िप्पल लेम्मा ) है।

कई बिंदुओं के लिए KZG

अब, हम यह सिद्ध करना चाहते हैं कि (z0,z1,....,zk−1) पर बहुपद P(x) के मान क्रमशः (y1,y2,....,yk−1) हैं। इसलिए, हमें दो बहुपदों को परिभाषित करने की आवश्यकता है:

ऊपर वर्णित विवरण के अनुसार, हमें V(x)|(P(x)−I(x)) को संतुष्ट करने की आवश्यकता है। अर्थात्, एक बहुपद Q(x) मौजूद है, जो संतुष्ट करता है:

इसलिए, प्रोवर को P(x) और Q(x) के लिए प्रतिबद्धताएं [P(s)]_1,[Q(s)]_1 प्रदान करने और सत्यापनकर्ता को प्रतिबद्धताएं भेजने की आवश्यकता है।

सत्यापनकर्ता स्थानीय रूप से [I(s)]_1,[V(s)]_2 की गणना करता है और समीकरण की पुष्टि करता है:

यह स्पष्ट है कि प्रूफ़ का आकार स्थिर रहता है चाहे कितने भी बिंदु हों। यदि हम BLS12-381 कर्व चुनते हैं, तो प्रूफ का आकार केवल 48 बाइट्स है, जो बहुत ही कुशल है।

वर्कल ट्री - ETH

मर्कल ट्री की तुलना में, जिसमें एक तत्व के अस्तित्व को साबित करने के लिए, प्रोवर को अभी भी O(log_2n) आकार के साथ प्रमाण प्रदान करने की आवश्यकता है, वर्कल ट्री ने प्रूफ आकार में बहुत सुधार किया है।

आइए वर्कल ट्री का एक सरल उदाहरण देखें।

यह देखा जा सकता है कि, मर्कल पेट्रीसिया ट्री संरचना के समान, नोड्स को तीन प्रकारों में विभाजित किया जा सकता है - खाली नोड, आंतरिक नोड और लीफ नोड।

प्रत्येक आंतरिक नोड ट्री की चौड़ाई 16 (0000->1111 हेक्साडेसिमल में) है। यह साबित करने के लिए कि लीफ नोड की स्थिति (0101 0111 1010 1111 -> 1213) है, हमें इनर नोड ए और इनर नोड बी के प्रति प्रतिबद्धता का संचालन करने की आवश्यकता है:

1. साबित करें कि इंडेक्स 1010 पर इनर नोड बी की प्रतिबद्धता का मूल्य हैश (0101 0111 1010 1111, 1213) है।

   
   

2. साबित करें कि आंतरिक नोड ए की प्रतिबद्धता का मूल्य हैश (cm_B) सूचकांक 0111 पर है।

   
   

3. साबित करें कि नोड रूट की प्रतिबद्धता का मूल्य हैश (cm_A) इंडेक्स 0101 पर है;

ऊपर वर्णित प्रतिबद्धताओं का प्रतिनिधित्व करने के लिए C_0(InnernodeB),C_1(InnernodeA),C_2(Root) का उपयोग करें और उन्हें बहुपद f_i(x) के अनुरूप करें।

इसलिए, प्रोवर को साबित करने की जरूरत है:

एकाधिक पोलिस के लिए संपीड़ित करें

इसे आसान बनाने के लिए, हम सूचकांक का प्रतिनिधित्व करने के लिए z_i का उपयोग करेंगे।

कहावत को यह साबित करने की आवश्यकता है कि बहुपद सेट के लिए f_0(x),f_1(x),....,f_m−1(x) , यह बिंदुओं पर निम्नलिखित शर्तों को पूरा करता है z_0,z_1,....,z_m− 1 , क्रमशः:
पिछले विवरण के अनुसार (एकल बिंदु के लिए KZG), प्रत्येक बहुपद के लिए, एक भागफल बहुपद संतोषजनक होता है:
Prover को मूल बहुपद और भागफल बहुपद के प्रति वचनबद्धता का संचालन करने और सत्यापनकर्ता को भेजने की आवश्यकता है:

सत्यापनकर्ता सत्यापन निष्पादित करता है:
यह स्पष्ट है कि हम नहीं चाहते कि सत्यापनकर्ता इतने सारे पेयरिंग ऑपरेशन निष्पादित करे (यह महंगा है)। इसलिए, हमें निम्नानुसार एक सेक को निष्पादित करने की आवश्यकता है।

कुछ यादृच्छिक संख्याएँ उत्पन्न करें r_0,r_1,....,r_m−1 , और उपरोक्त भागफल बहुपदों को एक साथ इकट्ठा करें:
मान लें कि यदि और केवल यदि प्रत्येक q_i(x) एक बहुपद है, तो g(x) एक बहुपद होगा (संभावना है कि q_i(x ) के बीच के अंश यादृच्छिक संख्याओं के कारण बहुत कम हैं)।

नीतिवचन बहुपद g(x) के प्रति वचनबद्धता का संचालन करता है और सत्यापनकर्ता को [g(s)]_1 भेजता है।

इसके बाद, सत्यापनकर्ता को यह विश्वास करने दें कि [g(s)]_1 बहुपद g(x) के प्रति प्रतिबद्धता है।

बहुपद g(x)g(x) के रूप का निरीक्षण करें, जिसे इस प्रकार लिखा जा सकता है:

यादृच्छिक रूप से एक मान tt चुनें और वहाँ है:

बहुपद को परिभाषित करें:

इसकी प्रतिबद्धता की गणना निम्नलिखित विधि से की जा सकती है:

फिर बिंदु tt पर बहुपद h(x)−g(x)h(x)−g(x) का मान है:

भागफल बहुपद q(x)=(h(x)−g(x)−y)/(x−z) की गणना करें।

प्रतिबद्धता की गणना करें π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1, और इसे सत्यापनकर्ता को भेजें।

सत्यापनकर्ता निम्नलिखित सत्यापन करता है:

1. गणना

   

2. सत्यापित करना

   

प्रमुख गुण

1. प्रूफ साइज़ को बदले बिना इस योजना का उपयोग करके कितने भी अंक सिद्ध किए जा सकते हैं। (प्रत्येक प्रतिबद्धता के लिए, एक प्रमाण है π ।)

   
   

2. y_i का मान स्पष्ट रूप से प्रदान करने की आवश्यकता नहीं है क्योंकि यह अगली परत मान का हैश है।

   
   

3. x_i के मान को स्पष्ट रूप से प्रदान करने की आवश्यकता नहीं है क्योंकि इसे कुंजी से आंका जा सकता है।

   
   

4. उपयोग की गई सार्वजनिक जानकारी में साबित करने के लिए कुंजी/मूल्य जोड़ी और बुनियादी स्तर से ऊपरी स्तर तक संबंधित प्रतिबद्धताएं शामिल हैं।

संदर्भ

1. Dankrad Feist, "यादृच्छिक मूल्यांकन का उपयोग कर PCS मल्टीप्रूफ," https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html , एक्सेस किया गया: 2022-05-10।

   
   

2. विटालिक ब्यूटिरिन, "वेर्कल ट्री," https://vitalik.ca/general/2021/06/18/verkle.html , एक्सेस किया गया: 2022-05-10।

   
   

3. जॉन कुज़्मौल, "वेर्कल ट्रीज़," https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf , एक्सेस किया गया: 2022-05-10।