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

इस डेटा संरचना के बारे में बात करें
देखो क्या जंग पहले से ही है
अपने कार्यान्वयन की पेशकश करें
प्रदर्शन की तुलना करें

मर्कल ट्री

यह अपेक्षाकृत सरल डेटा संरचना है, और इंटरनेट पर इसके बारे में पहले से ही बहुत सारी जानकारी है, लेकिन मुझे लगता है कि मेरा लेख पेड़ के विवरण के बिना अधूरा होगा।

क्या समस्या है

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

एक पेड़ कैसे काम करता है

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

एक पेड़ कैसे काम करता है?

एक मर्कल ट्री होने से, आप किसी ब्लॉक में लेन-देन हैश से रूट के रूप में एक लेनदेन में शामिल किए जाने के प्रमाण का निर्माण कर सकते हैं। उदाहरण के लिए, हम Tx2 के लेन-देन में रुचि रखते हैं, इसके लिए प्रमाण (Hash3, Hash01) होगा। एसपीवी में भी इस तंत्र का उपयोग किया जाता है। क्लाइंट केवल अपने हैश के साथ ब्लॉक हेडर को डाउनलोड करता है। ब्याज का लेन-देन करने के बाद, वह पूरी श्रृंखला वाले नोड से प्रमाण का अनुरोध करता है। तो यह एक जाँच करता है, Tx2 के लिए यह होगा:

hash(Hash01, hash(Hash2, Hash3)) = Root Hash

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

जो पहले से ही लागू हैं

जंग एक युवा भाषा है, लेकिन मर्कल पेड़ के कई अहसास पहले से ही इस पर लिखे गए हैं। गितुब द्वारा निर्णय लेना, फिलहाल 56, यह सी और सी + + संयुक्त की तुलना में अधिक है। हालाँकि गो उन्हें 80 कार्यान्वयन के साथ खड़ा करता है।

SpinResearch / merkle.rs

मेरी तुलना के लिए, मैंने इस कार्यान्वयन को रिपॉजिटरी में सितारों की संख्या द्वारा चुना।

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

साक्ष्य का निर्माण गहराई से खोज के माध्यम से होता है। यदि सही हैश के साथ एक शीट मिलती है, तो इसके लिए पथ परिणाम होगा।

क्या सुधार किया जा सकता है

मेरे लिए एक सरल (n + 1) -थ कार्यान्वयन करना दिलचस्प नहीं था, इसलिए मैंने अनुकूलन के बारे में सोचा। मेरे वेक्टर-मर्कल-ट्री के लिए कोड जीथब पर है।

डेटा भंडारण

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

सबूत

जब आप पेड़ को इनिशियलाइज़ करते हैं, तो आप सभी लीफ इंडेक्स के साथ एक हैशपॉप बना सकते हैं। इस प्रकार, जब कोई पत्ती नहीं होती है, तो पूरे पेड़ के चारों ओर जाना आवश्यक नहीं होता है, और अगर वहाँ है, तो आप तुरंत उस पर जा सकते हैं और जड़ तक बढ़ सकते हैं, एक प्रमाण का निर्माण कर सकते हैं। मेरे कार्यान्वयन में, मैंने HashMap को वैकल्पिक बनाया।

कॉनटैशन और हैशिंग

ऐसा लगता है कि यहां सुधार किया जा सकता है? सब के बाद, सब कुछ स्पष्ट है - दो हैश लें, उन्हें गोंद करें और एक नया हैश की गणना करें। लेकिन तथ्य यह है कि यह फ़ंक्शन गैर-कम्यूटेटिव है, अर्थात हैश (H0, H1) (हैश (H1, H0)। इस वजह से, सबूत का निर्माण करते समय, आपको यह याद रखना होगा कि पड़ोसी नोड किस तरफ है। यह एल्गोरिथ्म को लागू करने के लिए अधिक कठिन बनाता है, और अनावश्यक डेटा स्टोर करने की आवश्यकता को जोड़ता है। सब कुछ ठीक करना बहुत आसान है, बस हैशिंग से पहले दो नोड्स को सॉर्ट करें। उदाहरण के लिए, मैंने Tx2 दिया, कम्यूटेटिविटी को ध्यान में रखते हुए, चेक इस तरह दिखेगा:

 hash(hash(Hash2, Hash3), Hash01) = Root Hash

जब आपको ऑर्डर के बारे में चिंता करने की ज़रूरत नहीं है, तो सत्यापन एल्गोरिथ्म एक सरणी के एक साधारण दृढ़ संकल्प की तरह दिखता है:

 pub fn validate(&self, proof: &Vec<&[u8]>) -> bool { proof[2..].iter() .fold( get_pair_hash(proof[0], proof[1], self.algo), |a, b| get_pair_hash(a.as_ref(), b, self.algo) ).as_ref() == self.get_root() }

शून्य तत्व वांछित वस्तु का हैश है, पहला इसका पड़ोसी है।

चलो चलते हैं!

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

 pub trait TreeWrapper<V> { fn create(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn find(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn validate(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); }

दोनों पेड़ एक ही रिंग क्रिप्टोग्राफी के साथ काम करते हैं। यहाँ मैं विभिन्न पुस्तकालयों की तुलना नहीं करने जा रहा हूँ। मैंने सबसे आम लिया।

हैश ऑब्जेक्ट्स के रूप में, बेतरतीब ढंग से उत्पन्न स्ट्रिंग्स का उपयोग किया जाता है। पेड़ों की तुलना विभिन्न लंबाई के सरणियों पर की जाती है: (500, 1000, 1500, 2000, 2500 3000)। 2500 - 3000 इस समय बिटकॉइन ब्लॉक में लेनदेन की अनुमानित संख्या है।

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

वृक्ष बनाने की क्रिया

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

इसके अलावा, तुलना में, मैंने वेक्टर पेड़ के दो वेरिएंट जोड़े: हशप के साथ और उसके बिना। अतिरिक्त डेटा संरचना भरने से लगभग 20% जुड़ जाता है, लेकिन यह आपको प्रमाण बनाते समय वस्तुओं को बहुत तेज़ी से खोजने की अनुमति देता है।

भवन प्रमाण

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

प्रमाणों की मान्यता

यह आखिरी ऑपरेशन है। यह पेड़ की संरचना पर निर्भर नहीं करता है, क्योंकि साक्ष्य के निर्माण के साथ काम करता है। मेरा मानना है कि यहाँ मुख्य कठिनाई हैश गणना है।

परिणाम

जिस तरह से डेटा संग्रहीत किया जाता है वह प्रदर्शन को बहुत प्रभावित करता है। जब एक सरणी में सब कुछ बहुत तेज होता है। और इस तरह की संरचना को क्रमबद्ध करना बहुत सरल होगा। कोड की कुल राशि भी कम हो गई है।
सॉर्टिंग नोड्स को छांटने के साथ कोड को बहुत सरल करता है, लेकिन यह तेजी से नहीं बनाता है।

थोड़ा जंग के बारे में

कसौटी की रूपरेखा को पसंद किया। यह ग्राफ़ के साथ सुसज्जित औसत मूल्यों और विचलन के साथ स्पष्ट परिणाम देता है। एक ही कोड के विभिन्न कार्यान्वयन की तुलना करने में सक्षम।
वंशानुक्रम की कमी जीवन में बहुत हस्तक्षेप नहीं करती है।
मैक्रोज़ एक शक्तिशाली तंत्र हैं। मैंने उन्हें अपने पेड़ परीक्षणों में मानकीकरण के लिए इस्तेमाल किया। मुझे लगता है कि यदि उनका उपयोग खराब तरीके से किया जाता है, तो आप ऐसा काम कर सकते हैं कि आप खुद खुश नहीं होंगे।
कुछ स्थानों पर, संकलक इसकी मेमोरी जांच से ऊब गया है। मेरी आरंभिक धारणा जो रस्ट में लिखना शुरू करती है, इसलिए बस काम नहीं करना सही था।

मर्कल ट्री: रस्टी और फास्ट