Listen to this article

मर्कल ट्री

From Vigyanwiki
Revision as of 15:45, 25 July 2023 by alpha>Neeraja (added Category:Vigyan Ready using HotCat)
बाइनरी हैश ट्री का एक उदाहरण. हैश 0-0 और 0-1 क्रमशः डेटा ब्लॉक एल1 और एल2 के हैश मान हैं, और हैश 0 हैश 0-0 और 0-1 के संयोजन का हैश है।

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

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

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

उपयोग

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

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

सातोशी नाकामोतो द्वारा मर्कल ट्रीज़ का प्रारंभिक बिटकॉइन कार्यान्वयन हैश फ़ंक्शन के संपीड़न चरण को अत्यधिक डिग्री तक लागू करता है, जिसे तेज़ मर्कल ट्रीज़ का उपयोग करके कम किया जाता है।[11]

अवलोकन

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

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

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

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

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

दूसरा प्रीइमेज अटैक

मर्कल हैश रूट ट्री की गहराई को इंगित नहीं करता है, जिससे दूसरे-प्रीइमेज अटैक्स को सक्षम किया जा सकता है जिसमें अटैकर रुट के अलावा डॉक्यूमेंट बनाता है जिसमें समान मर्कल हैश रूट होता है। उपरोक्त उदाहरण के लिए, अटैकर दो डेटा ब्लॉक वाला एक नया डॉक्यूमेंट बना सकता है, जहां पहला हैश 0-0 + हैश 0-1 है, और दूसरा हैश 1-0 + हैश 1-1 है।[13][14]

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

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

टाइगर ट्री हैश, हैश ट्री का व्यापक रूप से उपयोग किया जाने वाला रूप है। यह एक बाइनरी हैश ट्री (प्रत्येक नोड के नीचे दो चाइल्ड नोड्स) का उपयोग करता है, सामान्यतः डेटा ब्लॉक का आकार 1024 बाइट्स होता है और टाइगर हैश का उपयोग करता है।[15]

टाइगर ट्री हैश का उपयोग ग्नुटेला,[16] ग्नुटेला2, और डायरेक्ट कनेक्ट पी2पी फ़ाइल शेयरिंग प्रोटोकॉल[17] और फ़ेक्स,[18] बियरशेयर, लाइमवायर, शेयराज़ा, डीसी++[19] और जीटीके-ग्नुटेला जैसे फ़ाइल शेयरिंग अनुप्रयोगों में किया जाता है।[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=226130’