Listen to this article

मर्कल ट्री: Difference between revisions

From Vigyanwiki
m (Sugatha moved page मर्केल वृक्ष to मर्कल ट्री without leaving a redirect)
No edit summary
Line 1: Line 1:
{{short description|Type of data structure}}
{{short description|Type of data structure}}
[[File:Hash Tree.svg|thumb|upright=1.4|बाइनरी हैश ट्री का एक उदाहरण. हैश 0-0 और 0-1 क्रमशः डेटा ब्लॉक एल1 और एल2 के हैश मान हैं, और हैश 0 हैश 0-0 और 0-1 के संयोजन का हैश है।]][[क्रिप्टोग्राफी]] और [[कंप्यूटर विज्ञान]] में, एक हैश ट्री या मर्कल ट्री एक ट्री ([[डेटा संरचना]]) है जिसमें प्रत्येक पत्ती (ट्री (डेटा संरचना) # शब्दावली) को डेटा ब्लॉक के [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन]] के साथ लेबल किया जाता है, और प्रत्येक नोड जो नहीं है एक पत्ती (जिसे ''शाखा'', ''आंतरिक नोड'', या ''इनोड'' कहा जाता है) को उसके चाइल्ड नोड्स के लेबल के क्रिप्टोग्राफ़िक हैश के साथ लेबल किया जाता है। एक हैश ट्री एक बड़ी डेटा संरचना की सामग्री के कुशल और सुरक्षित सत्यापन की अनुमति देता है। हैश ट्री एक [[हैश सूची]] और हैश श्रृंखला का सामान्यीकरण है।
[[File:Hash Tree.svg|thumb|upright=1.4|बाइनरी हैश ट्री का एक उदाहरण. हैश 0-0 और 0-1 क्रमशः डेटा ब्लॉक एल1 और एल2 के हैश मान हैं, और हैश 0 हैश 0-0 और 0-1 के संयोजन का हैश है।]][[क्रिप्टोग्राफी]] और [[कंप्यूटर विज्ञान]] में, एक '''हैश ट्री''' या '''मर्कल ट्री''' एक ऐसा ट्री है जिसमें प्रत्येक "लीफ" (नोड) को डेटा ब्लॉक के [[क्रिप्टोग्राफ़िक हैश फ़ंक्शन|क्रिप्टोग्राफ़िक हैश]] के साथ लेबल किया जाता है, और प्रत्येक नोड जो एक पत्ती नहीं है (जिसे ''ब्रांच'', ''आंतरिक नोड या इनोड'' कहा जाता है) को उसके बच्चे नोड्स के लेबल के क्रिप्टोग्राफ़िक हैश के साथ लेबल किया जाता है। हैश ट्री एक बड़ी डेटा संरचना की सामग्री के कुशल और सुरक्षित सत्यापन की अनुमति देता है। एक हैश ट्री एक हैश सूची और एक हैश श्रृंखला का सामान्यीकरण है।


यह प्रदर्शित करने के लिए कि एक लीफ नोड किसी दिए गए बाइनरी हैश ट्री का एक हिस्सा है, ट्री में लीफ नोड्स की संख्या के लघुगणक के अनुपात में हैश की संख्या की गणना करने की आवश्यकता होती है।<ref>{{Cite web |url=http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |title=मर्कल हस्ताक्षर योजनाएं, मर्कल पेड़ और उनका क्रिप्टोनालिसिस|last=Becker |first=Georg  |date=2008-07-18 |publisher=Ruhr-Universität Bochum |page=16 |access-date=2013-11-20}}</ref> इसके विपरीत, हैश सूची में, संख्या लीफ नोड्स की संख्या के समानुपाती होती है। इसलिए एक मर्कल पेड़ एक क्रिप्टोग्राफ़िक प्रतिबद्धता#आंशिक खुलासा का एक कुशल उदाहरण है, जिसमें पेड़ की जड़ को प्रतिबद्धता के रूप में देखा जाता है और पत्ती नोड्स को प्रकट किया जा सकता है और मूल प्रतिबद्धता का हिस्सा साबित किया जा सकता है{{Citation needed|reason=It is not clear that the scheme mentioned in this page is hiding (though, it is known to be computationally binding)|date=January 2022}}.
यह दर्शाने के लिए कि एक लीफ नोड किसी दिए गए बाइनरी हैश ट्री का एक हिस्सा है, ट्री में लीफ नोड्स की संख्या के लघुगणक के आनुपातिक हैश की संख्या की गणना करने की आवश्यकता है।<ref>{{Cite web |url=http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |title=मर्कल हस्ताक्षर योजनाएं, मर्कल पेड़ और उनका क्रिप्टोनालिसिस|last=Becker |first=Georg  |date=2008-07-18 |publisher=Ruhr-Universität Bochum |page=16 |access-date=2013-11-20}}</ref> इसके विपरीत, हैश सूची में, संख्या स्वयं लीफ नोड्स की संख्या के समानुपाती होती है। इसलिए, मर्कल ट्री एक क्रिप्टोग्राफ़िक प्रतिबद्धता योजना का एक कुशल उदाहरण है, जिसमें पेड़ की जड़ को प्रतिबद्धता के रूप में देखा जाता है और पत्ती नोड्स को प्रकट किया जा सकता है और मूल प्रतिबद्धता का हिस्सा साबित किया जा सकता है।


हैश ट्री की अवधारणा का नाम [[राल्फ मर्कले]] के नाम पर रखा गया है, जिन्होंने 1979 में इसका पेटेंट कराया था।<ref>{{Cite book | doi = 10.1007/3-540-48184-2_32| chapter = A Digital Signature Based on a Conventional Encryption Function| title = Advances in Cryptology – CRYPTO '87| volume = 293| pages = 369–378| series = Lecture Notes in Computer Science| year = 1988| last1 = Merkle | first1 = R. C. | isbn = 978-3-540-18796-7}}</ref><ref>{{ cite patent
हैश ट्री की अवधारणा का नाम [[राल्फ मर्कले]] के नाम पर रखा गया है, जिन्होंने 1979 में इसका पेटेंट कराया था।<ref>{{Cite book | doi = 10.1007/3-540-48184-2_32| chapter = A Digital Signature Based on a Conventional Encryption Function| title = Advances in Cryptology – CRYPTO '87| volume = 293| pages = 369–378| series = Lecture Notes in Computer Science| year = 1988| last1 = Merkle | first1 = R. C. | isbn = 978-3-540-18796-7}}</ref><ref>{{ cite patent
Line 20: Line 20:
  | class =  
  | class =  
}}</ref>
}}</ref>
==उपयोग==
==उपयोग==
हैश ट्री का उपयोग कंप्यूटर में और उसके बीच संग्रहीत, संभाले और स्थानांतरित किए गए किसी भी प्रकार के डेटा को सत्यापित करने के लिए किया जा सकता है। वे यह सुनिश्चित करने में मदद कर सकते हैं कि पीयर-टू-पीयर | पीयर-टू-पीयर नेटवर्क में अन्य साथियों से प्राप्त डेटा [[ब्लॉकचेन]] को अप्रकाशित और अपरिवर्तित प्राप्त होता है, और यहां तक ​​​​कि यह जांचने के लिए भी कि अन्य सहकर्मी झूठ नहीं बोलते हैं और नकली ब्लॉक नहीं भेजते हैं।
हैश ट्री का उपयोग कंप्यूटर में और उसके बीच संग्रहीत, संभाले और स्थानांतरित किए गए किसी भी प्रकार के डेटा को सत्यापित करने के लिए किया जा सकता है। वे यह सुनिश्चित करने में मदद कर सकते हैं कि पीयर-टू-पीयर | पीयर-टू-पीयर नेटवर्क में अन्य साथियों से प्राप्त डेटा [[ब्लॉकचेन]] को अप्रकाशित और अपरिवर्तित प्राप्त होता है, और यहां तक ​​​​कि यह जांचने के लिए भी कि अन्य सहकर्मी झूठ नहीं बोलते हैं और नकली ब्लॉक नहीं भेजते हैं।

Revision as of 06:01, 21 July 2023

बाइनरी हैश ट्री का एक उदाहरण. हैश 0-0 और 0-1 क्रमशः डेटा ब्लॉक एल1 और एल2 के हैश मान हैं, और हैश 0 हैश 0-0 और 0-1 के संयोजन का हैश है।

क्रिप्टोग्राफी और कंप्यूटर विज्ञान में, एक हैश ट्री या मर्कल ट्री एक ऐसा ट्री है जिसमें प्रत्येक "लीफ" (नोड) को डेटा ब्लॉक के क्रिप्टोग्राफ़िक हैश के साथ लेबल किया जाता है, और प्रत्येक नोड जो एक पत्ती नहीं है (जिसे ब्रांच, आंतरिक नोड या इनोड कहा जाता है) को उसके बच्चे नोड्स के लेबल के क्रिप्टोग्राफ़िक हैश के साथ लेबल किया जाता है। हैश ट्री एक बड़ी डेटा संरचना की सामग्री के कुशल और सुरक्षित सत्यापन की अनुमति देता है। एक हैश ट्री एक हैश सूची और एक हैश श्रृंखला का सामान्यीकरण है।

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

हैश ट्री की अवधारणा का नाम राल्फ मर्कले के नाम पर रखा गया है, जिन्होंने 1979 में इसका पेटेंट कराया था।[2][3]

उपयोग

हैश ट्री का उपयोग कंप्यूटर में और उसके बीच संग्रहीत, संभाले और स्थानांतरित किए गए किसी भी प्रकार के डेटा को सत्यापित करने के लिए किया जा सकता है। वे यह सुनिश्चित करने में मदद कर सकते हैं कि पीयर-टू-पीयर | पीयर-टू-पीयर नेटवर्क में अन्य साथियों से प्राप्त डेटा ब्लॉकचेन को अप्रकाशित और अपरिवर्तित प्राप्त होता है, और यहां तक ​​​​कि यह जांचने के लिए भी कि अन्य सहकर्मी झूठ नहीं बोलते हैं और नकली ब्लॉक नहीं भेजते हैं।

हैश ट्री का उपयोग हैश-आधारित क्रिप्टोग्राफी में किया जाता है। हैश ट्री का उपयोग इंटरप्लेनेटरी फ़ाइल सिस्टम (आईपीएफएस), Btrfs और ZFS फाइल सिस्टम में भी किया जाता है[4] (डेटा क्षरण का मुकाबला करने के लिए[5]); वह (सॉफ़्टवेयर) प्रोटोकॉल; अपाचे लहर प्रोटोकॉल;[6] Git (सॉफ़्टवेयर) और अस्थिर वितरित पुनरीक्षण नियंत्रण प्रणाली; ताहो-एलएएफएस बैकअप सिस्टम; ज़ेरोनेट; Bitcoin और Ethereum पीयर-टू-पीयर नेटवर्क;[7] प्रमाणपत्र पारदर्शिता ढांचा; निक्स पैकेज मैनेजर और जीएनयू गुइक्स जैसे वंशज;[8] और कई NoSQL सिस्टम जैसे Apache Cassandra, Riak, और Dynamo (भंडारण प्रणाली)।[9] विश्वसनीय कंप्यूटिंग सिस्टम में हैश ट्री का उपयोग करने के सुझाव दिए गए हैं।[10] सातोशी नाकामोतो द्वारा मर्कल ट्रीज़ का प्रारंभिक बिटकॉइन कार्यान्वयन हैश फ़ंक्शन के संपीड़न चरण को अत्यधिक डिग्री पर लागू करता है, जिसे फास्ट मर्कल ट्रीज़ का उपयोग करके कम किया जाता है।[11]


अवलोकन

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

अधिकांश हैश ट्री कार्यान्वयन बाइनरी हैं (प्रत्येक नोड के नीचे दो चाइल्ड नोड्स) लेकिन वे प्रत्येक नोड के तहत कई और चाइल्ड नोड्स का भी उपयोग कर सकते हैं।

आमतौर पर, हैशिंग के लिए SHA-2 जैसे क्रिप्टोग्राफ़िक हैश फ़ंक्शन का उपयोग किया जाता है। यदि हैश ट्री को केवल अनजाने क्षति से बचाने की आवश्यकता है, तो चक्रीय अतिरेक जांच जैसे असुरक्षित अंततः, का उपयोग किया जा सकता है।

हैश ट्री के शीर्ष में एक शीर्ष हैश (या रूट हैश या मास्टर हैश) होता है। पी2पी नेटवर्क पर किसी फ़ाइल को डाउनलोड करने से पहले, ज्यादातर मामलों में शीर्ष हैश किसी विश्वसनीय स्रोत से प्राप्त किया जाता है, उदाहरण के लिए किसी मित्र या किसी वेब साइट से जिसे डाउनलोड करने के लिए फ़ाइलों की अच्छी अनुशंसाओं के लिए जाना जाता है। जब शीर्ष हैश उपलब्ध होता है, तो हैश ट्री किसी भी गैर-भरोसेमंद स्रोत से प्राप्त किया जा सकता है, जैसे कि पी2पी नेटवर्क में कोई भी सहकर्मी। फिर, प्राप्त हैश ट्री को विश्वसनीय शीर्ष हैश के विरुद्ध जांचा जाता है, और यदि हैश ट्री क्षतिग्रस्त या नकली है, तो किसी अन्य स्रोत से एक और हैश ट्री की कोशिश की जाएगी जब तक कि प्रोग्राम को शीर्ष हैश से मेल खाने वाला एक नहीं मिल जाता।[12] हैश सूची से मुख्य अंतर यह है कि हैश ट्री की एक शाखा को एक समय में डाउनलोड किया जा सकता है और प्रत्येक शाखा की अखंडता की तुरंत जांच की जा सकती है, भले ही पूरा पेड़ अभी तक उपलब्ध नहीं है। उदाहरण के लिए, चित्र में, यदि पेड़ में पहले से ही हैश 0-0 और हैश 1 है तो डेटा ब्लॉक एल2 की अखंडता को तुरंत सत्यापित किया जा सकता है, डेटा ब्लॉक को हैश करके और परिणाम को हैश 0-0 और फिर हैश 1 और अंत में संयोजित करके। शीर्ष हैश के साथ परिणाम की तुलना करना। इसी तरह, डेटा ब्लॉक L3 की अखंडता को सत्यापित किया जा सकता है यदि पेड़ में पहले से ही हैश 1-1 और हैश 0 है। यह एक फायदा हो सकता है क्योंकि यह फ़ाइलों को बहुत छोटे डेटा ब्लॉक में विभाजित करने में कुशल है ताकि केवल छोटे ब्लॉक ही हों यदि वे क्षतिग्रस्त हो जाते हैं तो पुनः डाउनलोड करें। यदि हैश की गई फ़ाइल बड़ी है, तो ऐसी हैश सूची या हैश श्रृंखला काफी बड़ी हो जाती है। लेकिन अगर यह एक पेड़ है, तो एक छोटी शाखा को जल्दी से डाउनलोड किया जा सकता है, शाखा की अखंडता की जांच की जा सकती है, और फिर डेटा ब्लॉक की डाउनलोडिंग शुरू हो सकती है।[citation needed]

दूसरा प्रीइमेज हमला

मर्कल हैश रूट पेड़ की गहराई को इंगित नहीं करता है, एक दूसरे-प्रीइमेज हमले को सक्षम करता है जिसमें एक हमलावर मूल के अलावा एक दस्तावेज़ बनाता है जिसमें समान मर्कल हैश रूट होता है। उपरोक्त उदाहरण के लिए, एक हमलावर दो डेटा ब्लॉक वाला एक नया दस्तावेज़ बना सकता है, जहां पहला हैश 0-0 + हैश 0-1 है, और दूसरा हैश 1-0 + हैश 1-1 है।[13][14] सर्टिफिकेट ट्रांसपेरेंसी में एक सरल समाधान परिभाषित किया गया है: लीफ नोड हैश की गणना करते समय, एक 0x00 बाइट को हैश डेटा से जोड़ा जाता है, जबकि 0x01 को आंतरिक नोड हैश की गणना करते समय जोड़ा जाता है।[12] हैश ट्री आकार को सीमित करना कुछ लिंक्ड टाइमस्टैम्पिंग#प्रमाणित सुरक्षा की एक शर्त है, और कुछ प्रमाणों को सख्त बनाने में मदद करता है। कुछ कार्यान्वयन हैश से पहले हैश ट्री गहराई उपसर्गों का उपयोग करके पेड़ की गहराई को सीमित करते हैं, इसलिए किसी भी निकाली गई हैश श्रृंखला को केवल तभी वैध माना जाता है जब उपसर्ग प्रत्येक चरण में घटता है और पत्ती तक पहुंचने पर भी सकारात्मक होता है।

टाइगर ट्री हैश

टाइगर ट्री हैश, हैश ट्री का व्यापक रूप से उपयोग किया जाने वाला रूप है। यह एक बाइनरी हैश ट्री (प्रत्येक नोड के नीचे दो चाइल्ड नोड्स) का उपयोग करता है, आमतौर पर इसका डेटा ब्लॉक आकार 1024 बाइट्स होता है और टाइगर (हैश फ़ंक्शन) का उपयोग करता है।[15] टाइगर ट्री हैश का उपयोग ग्नुटेला में किया जाता है,[16] Gnutella2, और डायरेक्ट कनेक्ट (फ़ाइल शेयरिंग) पीयर-टू-पीयर फ़ाइल शेयरिंग प्रोटोकॉल[17] और फ़ेक्स जैसे फ़ाइल साझाकरण अनुप्रयोगों में,[18] BearShare , limewire , शेयराज़ा, डी.सी.प्लसप्लस|डीसी++[19] और gtk-gnutella.[20]


यह भी देखें

संदर्भ

  1. ↑ Becker, Georg (2008-07-18). "मर्कल हस्ताक्षर योजनाएं, मर्कल पेड़ और उनका क्रिप्टोनालिसिस" (PDF). Ruhr-Universität Bochum. p. 16. Retrieved 2013-11-20.
  2. ↑ Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology – CRYPTO '87. Lecture Notes in Computer Science. Vol. 293. pp. 369–378. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7.
  3. ↑ US patent 4309569, Ralph Merkle, "Method of providing digital signatures", published Jan 5, 1982, assigned to The Board of Trustees of the Leland Stanford Junior University 
  4. ↑ Bonwick, Jeff. "ZFS एंड-टू-एंड डेटा इंटीग्रिटी". Jeff Bonwick's Blog.
  5. ↑ Likai Liu. "सिंगल ड्राइव पर बिट्रोट प्रतिरोध". likai.org.
  6. ↑ "सामान्य सत्यापन योग्य संघ". Google Wave Protocol. Archived from the original on 2018-04-08. Retrieved 2017-03-09.
  7. ↑ Koblitz, Neal; Menezes, Alfred J. (January 2016). "क्रिप्टोकैश, क्रिप्टोकरेंसी और क्रिप्टो अनुबंध". Designs, Codes and Cryptography. 78 (1): 87–102. CiteSeerX 10.1.1.701.8721. doi:10.1007/s10623-015-0148-5. S2CID 16594958.
  8. ↑ Dolstra, E. The Purely Functional Software Deployment Model. PhD thesis, Faculty of Science, Utrecht, The Netherlands. January 2006. p.21 ISBN 90-393-4130-3.
  9. ↑ Adam Marcus. "The NoSQL Ecosystem". aosabook.org. When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.
  10. ↑ Kilian, J. (1995). "बेहतर कुशल तर्क (प्रारंभिक संस्करण)" (PDF). CRYPTO. doi:10.1007/3-540-44750-4_25.
  11. ↑ Mark Friedenbach: Fast Merkle Trees
  12. ↑ 12.0 12.1 Laurie, B.; Langley, A.; Kasper, E. (June 2013). "प्रमाणपत्र पारदर्शिता". IETF (in English): RFC6962. doi:10.17487/rfc6962.
  13. ↑ Elena Andreeva; Charles Bouillaguet; Orr Dunkelman; John Kelsey (January 2009). "Herding, Second Preimage and Trojan Message Attacks beyond Merkle–Damgård". क्रिप्टोग्राफी में चयनित क्षेत्र. Lecture Notes in Computer Science. Vol. 5867. SAC. pp. 393–414. doi:10.1007/978-3-642-05445-7_25. ISBN 978-3-642-05443-3.
  14. ↑ Elena Andreeva; Charles Bouillaguet; Pierre-Alain Fouque; Jonathan J. Hoch; John Kelsey; Adi Shamir; Sebastien Zimmer (2008). "Second Preimage Attacks on Dithered Hash Functions". In Smart, Nigel (ed.). Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. Istanbul, Turkey. pp. 270–288. doi:10.1007/978-3-540-78967-3_16. ISBN 978-3-540-78966-6. S2CID 12844017.{{cite book}}: CS1 maint: location missing publisher (link)
  15. ↑ Chapweske, J.; Mohr, G. (March 4, 2003). "ट्री हैश एक्सचेंज प्रारूप (THEX)". Archived from the original on 2009-08-03.
  16. ↑ "Tigertree.c फ़ाइल संदर्भ". Gtk-Gnutella. Retrieved 23 September 2018.
  17. ↑ "Audit: P2P DirectConnect Application". Symantec. Retrieved 23 September 2018.
  18. ↑ Arne Babenhauserheide (7 Jan 2007). "Phex 3.0.0 released". Phex. Retrieved 23 September 2018.
  19. ↑ "DC++ की सुविधा सूची". dcplusplus.sourceforge.net.
  20. ↑ "विकास". GTK-Gnutella. Retrieved 23 September 2018.


अग्रिम पठन


बाहरी संबंध

Listen to this article (5 minutes)
Spoken Wikipedia icon
This audio file was created from a revision of this article dated 17 September 2013 (2013-09-17), and does not reflect subsequent edits.
(Audio help · More spoken articles)
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=मर्कल_ट्री&oldid=226123’