सॉलिडिटी में मर्कल ट्री को कैसे लागू करें

मर्कल ट्री एक बाइनरी ट्री है जो बड़े डेटा संरचनाओं की सामग्री को कुशलतापूर्वक और सुरक्षित रूप से सत्यापित करना संभव बनाता है। इस पेड़ की अवधारणा 1982 में एक अमेरिकी क्रिप्टोग्राफर राल्फ मर्कले द्वारा प्रस्तावित और पेटेंट कराई गई थी।

किसी भी मात्रा में इनपुट डेटा के लिए हैश की लंबाई समान रहती है। लीफ वर्टिस में डेटा के ब्लॉक से हैश शामिल होते हैं, जबकि आंतरिक वर्टिस में दो चाइल्ड वर्टिस में मूल्यों को जोड़ने से हैश शामिल होते हैं। बदले में, रूट वर्टेक्स में संपूर्ण डेटा सेट का हैश शामिल होता है।

लिखित

प्रारंभ में, डेटा का एक सेट होता है जो किसी भी तरह से एक दूसरे से संबंधित नहीं होता है। डेटा के प्रत्येक ब्लॉक के लिए (लेन-देन ब्लॉकचेन के संदर्भ में), हमें ब्लॉक के हैश की गणना करने की आवश्यकता है। डेटा ब्लॉक की संख्या 2^N होनी चाहिए, क्योंकि जैसे ही पेड़ बनाया जाता है, पिछले ब्लॉक प्रत्येक पुनरावृत्ति पर जोड़े में हैश किए जाते हैं। फिर हैश की एक जोड़ी को एक साथ समूहीकृत किया जाता है और उनके आधार पर एक नया हैश बनाया जाता है। हैशिंग तब तक जारी रहेगी जब तक प्रत्येक स्तर पर समूह बनाने के लिए कुछ है, और यह तब रुक जाएगा जब केवल एक जोड़ी बची होगी जिससे रूट हैश - मर्कल रूट - प्राप्त किया जाएगा।

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

एक बार हमारे पास रूट हो जाने पर, हम डेटा को सत्यापित कर सकते हैं। यदि रूट हैश मूल हैश से मेल खाता है, तो सब कुछ ठीक है, डेटा मान्य है। यह कुशलतापूर्वक जांचना भी संभव है कि वृक्ष संरचना में कुछ डेटा मौजूद है या नहीं।

मान लीजिए कि हम यह जांचना चाहते हैं कि पेड़ में H2 हैश मौजूद है या नहीं। प्रमाण डेटा की एक श्रृंखला होगी: H1 , H3-4 , H5-6-7-8 . इन हैश के लिए धन्यवाद, हम रूट हैश का पुनर्निर्माण कर सकते हैं:

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

फिर हम परिणामी हैश की तुलना मूल हैश से करते हैं। यदि वे मेल खाते हैं, तो इसका मतलब है कि हैश H2 पेड़ में मौजूद है।

अभ्यास

आइए अब देखें कि सॉलिडिटी में मर्कल ट्री और डेटा सत्यापन को कैसे लागू किया जाए।

सरलता के लिए, हम लेनदेन की सारणी को सीधे ब्लॉकचेन पर लिखेंगे, साथ ही हैश की सारणी को भी लिखेंगे। चूँकि हम अंतर्निहित keccak256 फ़ंक्शन का उपयोग करेंगे, जो 32 बाइट्स का हैश लौटाता है, हैश सरणी का डेटाटाइप bytes32 होगा। सरणी की एक गतिशील लंबाई भी होगी. सामान्य तौर पर, हैश सरणी की लंबाई लेनदेन सरणी की लंबाई के समान नहीं होगी, क्योंकि यह उत्पादित हैश को धारण करेगी। हम पहले से ही लंबाई की गणना कर सकते हैं, लेकिन कोड सरलीकरण के लिए हम ऐसा नहीं करेंगे। यदि आप चाहें, तो आप इनमें से प्रत्येक सारणी को public कर सकते हैं और लेनदेन के हैश पढ़ सकते हैं।

हम कंस्ट्रक्टर में hashes उत्पादन करेंगे। पहला कदम लूप में transactions वाले ब्लॉक के लिए हैश की गणना करना है। फिर, पेड़ के प्रत्येक स्तर पर, हैश की संख्या 2 के कारक से कम हो जाती है। चूंकि हम हैश को हैश सरणी में संग्रहीत करेंगे, इसलिए इंडेक्स ऑफसेट को अलग से संग्रहीत किया जाना चाहिए। आंतरिक लूप में पुनरावर्तक को 2 से बढ़ाया गया है क्योंकि गणना करते समय और हैश जोड़ते समय हम कुछ तत्वों को लेंगे। abi.encodePacked में इस बार हम 2 हैश जोड़ेंगे, जिनमें से प्रत्येक में हम सूचकांकों को सही ढंग से सेट करेंगे: बाएं तत्व के लिए - वर्तमान शिफ्ट ऑफ़सेट का मान + वर्तमान ट्री स्तर पर सूचकांक, और दाएं तत्व के लिए - वही +1.

तो, हमने पेड़ बना लिया है, लेकिन रुचि डेटा को मान्य करने में है। ऐसा करने के लिए, आइए एक validateTransaction फ़ंक्शन लिखें जो एक लेनदेन और उसका सूचकांक लेता है। दुर्भाग्य से, सॉलिडिटी में सरणियों के लिए कोई find विधि नहीं है, इसलिए केवल लेनदेन सूचकांक को पास करना आसान है।

सबसे पहले, आइए लेनदेन के हैश की गणना करें और सबूतों की एक श्रृंखला बनाएं। हम लेन-देन सरणी की लंबाई के आधार पर प्रमाणों की संख्या पाते हैं और proofsIndexes की लंबाई निर्धारित करते हैं। इसके बाद, पेड़ के प्रत्येक स्तर पर, हम सूचकांक के आधार पर, दाएं या बाएं तत्व को लेते हुए, hashes में ऑफसेट को ध्यान में रखते हुए, आवश्यक तत्व ढूंढते हैं। फिर हम प्रमाण सूचकांकों की श्रृंखला से गुजरते हैं, समता के लिए सूचकांक की जांच करते हैं और हैश की गणना करते हैं, यह इस बात पर निर्भर करता है कि तत्व जोड़ी में बाएँ या दाएँ है या नहीं। अंत में, हम परिणामी हैश की तुलना रूट हैश से करते हैं और परिणाम लौटाते हैं।

आवेदन

ब्लॉकचेन में मर्कल ट्री के कई अनुप्रयोग हैं।

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

सारांश

मर्कल पेड़ों के बिना, ब्लॉकचेन बहुत बोझिल होंगे, और मर्कल प्रमाण डेटा प्रामाणिकता के लागत प्रभावी सत्यापन की अनुमति देते हैं।

लेन-देन को कुशलतापूर्वक संग्रहीत करने के लिए ब्लॉकचेन (उदाहरण के लिए, बिटकॉइन, एथेरियम) में मर्कल पेड़ों का सक्रिय रूप से उपयोग किया जाता है, लेकिन यह एकमात्र एप्लिकेशन नहीं है। उदाहरण के लिए, एफटीएक्स एक्सचेंज के पतन के बाद, कई एक्सचेंजों ने प्रूफ-ऑफ-रिजर्व तंत्र लागू किया, जो मर्कल ट्री का उपयोग करता है।