View source for मर्कल ट्री

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

यह दर्शाने के लिए कि लीफ नोड किसी दिए गए बाइनरी हैश ट्री का एक भाग है, ट्री में लीफ नोड्स की संख्या के लघुगणक के आनुपातिक हैश की संख्या की गणना करने की आवश्यकता है।<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
 | country = US
 | number = 4309569
 | status = patent
 | title = Method of providing digital signatures
 | pubdate = Jan 5, 1982
 | gdate = 
 | fdate = Sep 5, 1979
 | pridate = 
 | inventor = Ralph Merkle
 | invent1 = 
 | invent2 = 
 | assign1 = The Board of Trustees of the Leland Stanford Junior University
 | assign2 = 
 | class = 
}}</ref>
==उपयोग==
हैश ट्री का उपयोग किसी भी प्रकार के डेटा को सत्यापित करने के लिए किया जा सकता है जो कंप्यूटर में और उसके बीच संग्रहीत, प्रबंधित और स्थानांतरित किया जाता है। वे यह सुनिश्चित करने में मदद कर सकते हैं कि पीयर-टू-पीयर नेटवर्क में अन्य साथियों से प्राप्त डेटा ब्लॉक अपरिवर्तित और अपरिवर्तित प्राप्त होते हैं, और यहां तक कि यह भी जांचते हैं कि अन्य पीअर्स निहित नहीं हैं और गलत ब्लॉक नहीं भेजते हैं।

[[हैश-आधारित क्रिप्टोग्राफी]] में हैश ट्री का उपयोग किया जाता है। हैश ट्री का उपयोग [[इंटरप्लेनेटरी फ़ाइल सिस्टम]] (आईपीएफएस), बीटीआरएफएस और जेडएफएस फाइल सिस्टम में भी किया जाता है<ref>{{Cite web |url=https://blogs.oracle.com/bonwick/entry/zfs_end_to_end_data |title=ZFS एंड-टू-एंड डेटा इंटीग्रिटी|last=Bonwick |first=Jeff |website=Jeff Bonwick's Blog}}</ref> (डेटा क्षरण का संयोधन करने के लिए<ref>{{cite web|url = http://lifecs.likai.org/2014/06/bitrot-resistance-on-single-drive.html|title = सिंगल ड्राइव पर बिट्रोट प्रतिरोध|author = Likai Liu | website = likai.org}}</ref>); डेटा प्रोटोकॉल; अपाचे वेव प्रोटोकॉल;<ref>{{Cite web |url=http://www.waveprotocol.org/whitepapers/wave-protocol-verification |title=सामान्य सत्यापन योग्य संघ|website=Google Wave Protocol |access-date=2017-03-09 |archive-url=https://web.archive.org/web/20180408150608/http://www.waveprotocol.org/whitepapers/wave-protocol-verification |archive-date=2018-04-08 |url-status=dead }}</ref> गिट और मर्कुरियल वितरित संशोधन नियंत्रण प्रणाली; [[ताहो-एलएएफएस]] बैकअप सिस्टम; [[ज़ेरोनेट]]; बिटकॉइन और एथेरियम पीयर-टू-पीयर नेटवर्क;<ref>{{Cite journal |last1=Koblitz |first1=Neal  |last2=Menezes |first2=Alfred J. |date=January 2016 |title=क्रिप्टोकैश, क्रिप्टोकरेंसी और क्रिप्टो अनुबंध|journal=Designs, Codes and Cryptography |volume=78 |issue=1 |pages=87–102 |doi=10.1007/s10623-015-0148-5|citeseerx=10.1.1.701.8721 |s2cid=16594958 }}</ref> सर्टिफिकेट ट्रांसपेरेंसी फ्रेमवर्क; निक्स पैकेज मैनेजर और जीएनयू गुइक्स जैसे परिणाम;<ref>Dolstra, E. [https://nixos.org/~eelco/pubs/phd-thesis.pdf#page21 ''The Purely Functional Software Deployment Model.''] PhD thesis, Faculty of Science, Utrecht, The Netherlands. January 2006. p.21 {{ISBN|90-393-4130-3}}.</ref> और कई नोएसक्यूएल सिस्टम जैसे अपाचे कैसेंड्रा, रीक और डायनमो।<ref>{{cite web
 | url = http://www.aosabook.org/en/nosql.html
 | title = The NoSQL Ecosystem
 | author = Adam Marcus | website = aosabook.org
 | quote = 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.
}}</ref> विश्वसनीय कंप्यूटिंग प्रणालियों में हैश ट्री का उपयोग करने के सुझाव दिए गए हैं।<ref>{{Cite journal |last=Kilian |first=J. |date=1995 |title=बेहतर कुशल तर्क (प्रारंभिक संस्करण)|journal=CRYPTO|url=https://link.springer.com/content/pdf/10.1007/3-540-44750-4_25.pdf|doi=10.1007/3-540-44750-4_25 |doi-access=free }}</ref>

[[सातोशी नाकामोतो]] द्वारा मर्कल ट्रीज़ का प्रारंभिक बिटकॉइन कार्यान्वयन हैश फ़ंक्शन के संपीड़न चरण को अत्यधिक डिग्री तक लागू करता है, जिसे तेज़ मर्कल ट्रीज़ का उपयोग करके कम किया जाता है।<ref>[https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki Mark Friedenbach: Fast Merkle Trees]</ref>

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

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

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

हैश ट्री के टॉप पर, टॉप हैश (या ''रूट हैश'' या ''मास्टर हैश'') होता है। पी2पी नेटवर्क पर फ़ाइल डाउनलोड करने से पहले, ज्यादातर स्थितियों में, टॉप हैश किसी विश्वसनीय स्रोत से प्राप्त किया जाता है, उदाहरण के लिए, किसी मित्र या वेबसाइट से जिसे डाउनलोड करने के लिए फ़ाइलों की अच्छी अनुशंसाओं के लिए जाना जाता है। जब टॉप हैश उपलब्ध होता है, तो हैश ट्री किसी भी गैर-भरोसेमंद स्रोत से प्राप्त किया जा सकता है, जैसे पी2पी नेटवर्क में कोई भी पीयर। फिर, प्राप्त हैश ट्री को विश्वसनीय टॉप हैश के विरुद्ध जांचा जाता है, और यदि हैश ट्री क्षतिग्रस्त या नकली है, तो किसी अन्य स्रोत से एक और हैश ट्री की प्रयास किया जायेगा जब तक कि प्रोग्राम को टॉप हैश से मेल खाने वाला एक नहीं मिल जाता।<ref name=":0">{{Cite journal|last1=Laurie|first1=B.|last2=Langley|first2=A.|last3=Kasper|first3=E.|date=June 2013|title=प्रमाणपत्र पारदर्शिता|url=https://www.rfc-editor.org/info/rfc6962|journal=IETF|language=en|pages=RFC6962|doi=10.17487/rfc6962|doi-access=free}}</ref>

हैश सूची से मुख्य अंतर यह है कि हैश ट्री की एक ब्रांच को एक समय में डाउनलोड किया जा सकता है और प्रत्येक ब्रांच की प्रामाणिकता की तुरंत जाँच की जा सकती है, भले ही पूरा ट्री अभी तक उपलब्ध नहीं है। उदाहरण के लिए, चित्र में, डेटा ''ब्लॉक L2'' की प्रामाणिकता को तुरंत सत्यापित किया जा सकता है यदि ट्री में पहले से ही ''हैश 0-0'' और हैश 1 है, डेटा ब्लॉक को हैश करके और परिणाम को ''हैश 0-0'' और फिर ''हैश 1'' के साथ संयोजित करके और अंत में ''टॉप हैश'' के साथ परिणाम की तुलना करके। इसी प्रकार, ''डेटा ब्लॉक L3'' की प्रामाणिकता को सत्यापित किया जा सकता है यदि ट्री में पहले से ही हैश 1-1 और ''हैश 0'' है। यह एक फायदा हो सकता है क्योंकि यह फ़ाइलों को बहुत छोटे डेटा ब्लॉक में विभाजित करने में कुशल है ताकि केवल छोटे ब्लॉक क्षतिग्रस्त होने पर उन्हें फिर से डाउनलोड करना पड़े। यदि हैशेड फ़ाइल बड़ी है, तो ऐसी हैश सूची या हैश श्रृंखला काफी बड़ी हो जाती है। लेकिन यदि यह एक ट्री है, तो एक छोटी ब्रांच को जल्दी से डाउनलोड किया जा सकता है, ब्रांच की जांच की जा सकती है, और फिर डेटा ब्लॉक की डाउनलोडिंग प्रारम्भ हो सकती है।

===दूसरा प्रीइमेज अटैक===
मर्कल हैश रूट ट्री की गहराई को इंगित नहीं करता है, जिससे दूसरे-प्रीइमेज अटैक्स को सक्षम किया जा सकता है जिसमें अटैकर रुट के अलावा डॉक्यूमेंट बनाता है जिसमें समान मर्कल हैश रूट होता है। उपरोक्त उदाहरण के लिए, अटैकर दो डेटा ब्लॉक वाला एक नया डॉक्यूमेंट बना सकता है, जहां पहला ''हैश 0-0 + हैश 0-1'' है, और दूसरा ''हैश 1-0 + हैश 1-1'' है।<ref>{{cite book |author1=Elena Andreeva |author2=Charles Bouillaguet |author3=Orr Dunkelman |author4=John Kelsey |title=क्रिप्टोग्राफी में चयनित क्षेत्र|volume=5867 |date=January 2009 |publisher=SAC |pages=393–414 |chapter=Herding, Second Preimage and Trojan Message Attacks beyond Merkle–Damgård|doi=10.1007/978-3-642-05445-7_25 |series=Lecture Notes in Computer Science |isbn=978-3-642-05443-3 }}</ref><ref>{{cite book |author1=Elena Andreeva |author2=Charles Bouillaguet |author3=Pierre-Alain Fouque |author4=Jonathan J. Hoch |author5=John Kelsey |author6=Adi Shamir |author7=Sebastien Zimmer |editor1-last=Smart |editor1-first=Nigel |title=Advances in Cryptology – EUROCRYPT 2008 |volume=4965 |date=2008 |location=Istanbul, Turkey |pages=270–288 |chapter=Second Preimage Attacks on Dithered Hash Functions|doi=10.1007/978-3-540-78967-3_16 |series=Lecture Notes in Computer Science |isbn=978-3-540-78966-6 |s2cid=12844017 }}</ref>

सर्टिफिकेट ट्रांसपेरेंसी में एक सरल समाधान परिभाषित किया गया है: लीफ नोड हैश की गणना करते समय, एक 0x00 बाइट को हैश डेटा से जोड़ा जाता है, जबकि 0x01 को आंतरिक नोड हैश की गणना करते समय जोड़ा जाता है।<ref name=":0" /> हैश ट्री के आकार को सीमित करना कुछ औपचारिक सुरक्षा प्रमाणों की एक पूर्व शर्त है, और कुछ प्रमाणों को सख्त बनाने में सहायता करता है। कुछ कार्यान्वयन हैश से पहले हैश ट्री गहराई उपसर्गों का उपयोग करके ट्री की गहराई को सीमित करते हैं, इसलिए किसी भी निकाली गई हैश श्रृंखला को केवल तभी वैध माना जाता है जब प्रत्येक चरण में उपसर्ग कम हो जाता है और लीफ तक पहुंचने पर भी धनात्मक रहता है।

===टाइगर ट्री हैश===
टाइगर ट्री हैश, हैश ट्री का व्यापक रूप से उपयोग किया जाने वाला रूप है। यह एक बाइनरी हैश ट्री (प्रत्येक नोड के नीचे दो चाइल्ड नोड्स) का उपयोग करता है, सामान्यतः डेटा ब्लॉक का आकार 1024 बाइट्स होता है और [[टाइगर (हैश फ़ंक्शन)|टाइगर]] हैश का उपयोग करता है।<ref>{{Cite web |url=http://open-content.net/specs/draft-jchapweske-thex-02.html |title=ट्री हैश एक्सचेंज प्रारूप (THEX)|last1=Chapweske |first1=J.  |last2=Mohr |first2=G.  |date=March 4, 2003 |archive-url=https://web.archive.org/web/20090803220648/http://open-content.net/specs/draft-jchapweske-thex-02.html |archive-date=2009-08-03}}</ref>

टाइगर ट्री हैश का उपयोग [[ग्नुटेला]],<ref>{{cite web |title=Tigertree.c फ़ाइल संदर्भ|url=http://gtk-gnutella.sourceforge.net/doxygen/tigertree_8c.html |website=Gtk-Gnutella |access-date=23 September 2018}}</ref> ग्नुटेला2, और डायरेक्ट कनेक्ट पी2पी फ़ाइल शेयरिंग प्रोटोकॉल<ref>{{cite web |title=Audit: P2P DirectConnect Application |url=https://www.symantec.com/security_response/attacksignatures/detail.jsp?asid=21587 |website=Symantec |access-date=23 September 2018}}</ref> और फ़ेक्स,<ref>{{cite web |author1=Arne Babenhauserheide |title=Phex 3.0.0 released |url=http://www.phex.org/mambo/content/view/80/2/ |website=Phex |access-date=23 September 2018 |date=7 Jan 2007}}</ref> बियरशेयर, लाइमवायर, शेयराज़ा, डीसी++<ref>{{cite web|url=http://dcplusplus.sourceforge.net/features.html |title=DC++ की सुविधा सूची|website=dcplusplus.sourceforge.net}}</ref> और जीटीके-ग्नुटेला जैसे फ़ाइल शेयरिंग अनुप्रयोगों में किया जाता है।<ref>{{cite web |title=विकास|url=http://gtk-gnutella.sourceforge.net/en/?page=devel |website=GTK-Gnutella |access-date=23 September 2018}}</ref>
==यह भी देखें==

* बाइनरी ट्री 
* ब्लॉकचेन
* डिस्ट्रिब्यूटेड हैश टेबल 
* हैश टेबल
* [[हैश ट्राई]]
* [[लिंक्ड टाइमस्टैम्पिंग]]
* रेडिक्स ट्री {{Portal|Computer programming}}

==संदर्भ==
{{Reflist}}


==अग्रिम पठन==
* {{US patent|4309569|Merkle tree patent 4,309,569}}{{snd}} explains both the hash tree structure and the use of it to handle many one-time signatures
* [https://web.archive.org/web/20080316033726/http://www.open-content.net/specs/draft-jchapweske-thex-02.html Tree Hash EXchange format (THEX)]{{snd}} a detailed description of Tiger trees


==बाहरी संबंध==
{{Spoken Wikipedia|en-Merkle Tree.ogg|date=2013-09-17}}

* [https://github.com/IAIK/merkle-tree A C implementation of a dynamically re-sizeable binary SHA-256 hash tree (Merkle tree)]
* [https://github.com/richpl/merkletree Merkle tree implementation in Java]
* [https://www.codeproject.com/articles/9336/thexcs-tth-tiger-tree-hash-maker-in-c Tiger Tree Hash (TTH) source code in C#], by Gil Schmidt
* [http://sourceforge.net/projects/tigertree/ Tiger Tree Hash (TTH) implementations in C and Java]
* [http://rhash.sourceforge.net/ RHash], an open source command-line tool, which can calculate TTH and magnet links with TTH

{{Cryptography navbox}}
{{CS-Trees}}

[[Category:Articles with hAudio microformats]]
[[Category:CS1 English-language sources (en)]]
[[Category:Collapse templates]]
[[Category:Created On 09/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with empty portal template]]
[[Category:Pages with script errors]]
[[Category:Portal templates with redlinked portals]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Spoken articles]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:क्रिप्टोग्राफ़िक हैश फ़ंक्शंस]]
[[Category:त्रुटि का पता लगाना और सुधार करना]]
[[Category:पेड़ (डेटा संरचनाएं)]]
[[Category:हैशिंग]]