Merkle tree

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة
An example of a binary hash tree. Hashes 0-0 and 0-1 are the hash values of data blocks L1 and L2, respectively, and hash 0 is the hash of the concatenation of hashes 0-0 and 0-1.

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" node is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure. A hash tree is a generalization of a hash list and a hash chain.

Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree.[1] Conversely, in a hash list, the number is proportional to the number of leaf nodes itself. A Merkle tree is therefore an efficient example of a cryptographic commitment scheme, in which the root of the tree is seen as a commitment and leaf nodes may be revealed and proven to be part of the original commitment.[2]

The concept of a hash tree is named after Ralph Merkle, who patented it in 1979.[3][4]

Uses

Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers. They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks.

Hash trees are used in:

تم تقديم اقتراحات لاستخدام أشجار التجزئة في أنظمة الحوسبة الموثوقة . [ 14 ]

ملخص

شجرة التجزئة هي شجرة من التجزئات ، حيث تمثل الأوراق (أي العقد الطرفية، والتي تُسمى أحيانًا "الأوراق") تجزئات كتل البيانات في ملف أو مجموعة ملفات، على سبيل المثال. أما العقد الأعلى في الشجرة فتمثل تجزئات أبنائها. على سبيل المثال، في الصورة أعلاه، التجزئة 0 هي نتيجة تجزئة دمج التجزئة 0-0 والتجزئة 0-1 . أي أن التجزئة 0 = التجزئة ( التجزئة 0-0 + التجزئة 0-1 )، حيث يرمز "+" إلى الدمج.

معظم تطبيقات شجرة التجزئة ثنائية (عقدتان فرعيتان تحت كل عقدة) ولكن يمكنها أيضًا استخدام عدد أكبر بكثير من العقد الفرعية تحت كل عقدة.

عادةً ما تُستخدم دالة تجزئة تشفيرية مثل SHA-2 للتجزئة. أما إذا كانت شجرة التجزئة تحتاج فقط إلى الحماية من التلف غير المقصود، فيمكن استخدام مجاميع اختبارية غير تشفيرية مثل CRC .

في قمة شجرة التجزئة، توجد تجزئة رئيسية (أو تجزئة جذرية أو تجزئة أساسية ). قبل تنزيل أي ملف على شبكة نظير إلى نظير ، في معظم الحالات، يتم الحصول على التجزئة الرئيسية من مصدر موثوق، كصديق أو موقع ويب معروف بتوصياته الجيدة للملفات. عند توفر التجزئة الرئيسية، يمكن الحصول على شجرة التجزئة من أي مصدر غير موثوق، كأي نظير في شبكة نظير إلى نظير. بعد ذلك، تُقارن شجرة التجزئة المستلمة بالتجزئة الرئيسية الموثوقة، وإذا كانت شجرة التجزئة تالفة أو مزيفة، تُجرَّب شجرة تجزئة أخرى من مصدر مختلف حتى يعثر البرنامج على شجرة تجزئة مطابقة للتجزئة الرئيسية. [ 15 ]

يتمثل الاختلاف الرئيسي بين التجزئة وقائمة التجزئة في إمكانية تنزيل فرع واحد من شجرة التجزئة في كل مرة، والتحقق من سلامة كل فرع فورًا، حتى قبل اكتمال الشجرة. على سبيل المثال، في الصورة، يمكن التحقق من سلامة كتلة البيانات L2 فورًا إذا كانت الشجرة تحتوي بالفعل على التجزئة 0-0 والتجزئة 1، وذلك بتجزئة كتلة البيانات ودمج النتيجة بشكل متكرر مع التجزئة 0-0 ثم التجزئة 1، وأخيرًا مقارنة النتيجة مع التجزئة العليا . وبالمثل، يمكن التحقق من سلامة كتلة البيانات L3 إذا كانت الشجرة تحتوي بالفعل على التجزئة 1-1 والتجزئة 0. تُعد هذه ميزةً، إذ تُسهّل تقسيم الملفات إلى كتل بيانات صغيرة جدًا، بحيث لا يلزم إعادة تنزيل سوى الكتل الصغيرة في حال تلفها. إذا كان الملف المُجزأ كبيرًا، تصبح قائمة التجزئة أو سلسلة التجزئة كبيرة نسبيًا. أما إذا كانت شجرة، فيمكن تنزيل فرع صغير بسرعة، والتحقق من سلامة الفرع، ثم بدء تنزيل كتل البيانات.

هجوم الصورة المسبقة الثاني

لا يُشير جذر تجزئة ميركل إلى عمق الشجرة، مما يُتيح هجومًا يُسمى هجوم الصورة السابقة الثانية، حيث يُنشئ المهاجم مستندًا آخر غير المستند الأصلي له نفس جذر تجزئة ميركل. في المثال أعلاه، يُمكن للمهاجم إنشاء مستند جديد يحتوي على كتلتين من البيانات، الأولى هي التجزئة 0-0 + التجزئة 0-1 ، والثانية هي التجزئة 1-0 + التجزئة 1-1 . [ 16 ] [ 17 ]

يُعرّف مبدأ شفافية الشهادات حلاً بسيطاً : عند حساب تجزئات العقد الطرفية، يُضاف بايت 0x00 إلى بيانات التجزئة، بينما يُضاف 0x01 عند حساب تجزئات العقد الداخلية. [ 15 ] يُعدّ تحديد حجم شجرة التجزئة شرطاً أساسياً لبعض البراهين الأمنية الرسمية ، ويُسهم في تعزيز دقة بعضها. تُحدّد بعض التطبيقات عمق الشجرة باستخدام بادئات عمق شجرة التجزئة قبل حساب التجزئات، لذا تُعتبر أي سلسلة تجزئة مُستخرجة صالحة فقط إذا انخفضت البادئة في كل خطوة وظلت موجبة عند الوصول إلى العقدة الطرفية.

حشيش شجرة النمر

تُعدّ تجزئة شجرة النمر شكلاً شائع الاستخدام من أشكال شجرة التجزئة. وهي تستخدم شجرة تجزئة ثنائية (عقدتان فرعيتان تحت كل عقدة)، وعادةً ما يكون حجم كتلة البيانات فيها 1024 بايت ، وتستخدم تجزئة النمر . [ 18 ]

Tiger tree hashes are used in Gnutella,[19]Gnutella2, and Direct ConnectP2P file sharing protocols[20] and in file sharing applications such as Phex,[21]BearShare, LimeWire, Shareaza, DC++[22] and gtk-gnutella.[23]

See also

References

  1. ↑Becker, Georg (2008-07-18). "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis"(PDF). Ruhr-Universität Bochum. p. 16. Archived from the original(PDF) on 2014-12-22. Retrieved 2013-11-20.
  2. ↑"Handbook of Applied Cryptography". cacr.uwaterloo.ca. Section 13.4.1. Retrieved 2024-03-07.
  3. ↑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.
  4. ↑USpatent 4309569,Ralph Merkle,"Method of providing digital signatures",published Jan 5, 1982, assigned to The Board of Trustees of the Leland Stanford Junior University 
  5. ↑"hashtree developer page".
  6. ↑Bonwick, Jeff (2005-12-08). "ZFS End-to-End Data Integrity". blogs.oracle.com. Archived from the original on April 3, 2012. Retrieved 2013-09-19.
  7. ↑Likai Liu. "Bitrot Resistance on a Single Drive". likai.org.
  8. ↑"General Verifiable Federation". Google Wave Protocol. Archived from the original on 2018-04-08. Retrieved 2017-03-09.
  9. ↑"Introduction to ZFS — openzfs latest documentation". openzfs.readthedocs.io. Retrieved 2025-05-27.
  10. ↑ كوبليتز، نيل؛ مينيزيس، ألفريد ج. (يناير 2016). "العملات المشفرة، والعقود المشفرة". التصاميم، والرموز، والتشفير . 78 (1): 87-102 . CiteSeerX 10.1.1.701.8721 . doi : 10.1007/s10623-015-0148-5 . S2CID 16594958 .  
  11. ^ د. بنيامين. د.أوبراين؛ بي ويستربان؛ إل فالنتا؛ واو فالسوردا (24/05/2026). "شهادات شجرة ميركل" . فرقة عمل هندسة الإنترنت . فريق عمل الإنترنت . تم الاسترجاع 2026-06-11 .
  12. ↑ دولسترا، إي. نموذج نشر البرمجيات الوظيفية البحتة. أطروحة دكتوراه، كلية العلوم، أوتريخت، هولندا. يناير 2006. ص 21 ISBN 90-393-4130-3.
  13. ↑ آدم ماركوس. "نظام NoSQL البيئي" . aosabook.org . عندما تتعطل نسخة احتياطية لفترة طويلة، أو عندما يتعطل الجهاز الذي يخزن عمليات التسليم المُلمحة لنسخة احتياطية غير متاحة، يجب على النسخ الاحتياطية مزامنة بياناتها. في هذه الحالة، تُطبّق كاساندرا ورياك عملية مستوحاة من دينامو تُسمى "مكافحة الإنتروبيا". في هذه العملية، تتبادل النسخ الاحتياطية أشجار ميركل لتحديد أجزاء نطاقات المفاتيح المنسوخة غير المتزامنة. شجرة ميركل هي عملية تحقق هرمية من التجزئة: إذا لم تكن قيمة التجزئة لمساحة المفاتيح بأكملها متطابقة بين نسختين احتياطيتين، فإنهما ستتبادلان قيم التجزئة لأجزاء أصغر فأصغر من مساحة المفاتيح المنسوخة حتى يتم تحديد المفاتيح غير المتزامنة. يقلل هذا الأسلوب من نقل البيانات غير الضروري بين النسخ الاحتياطية التي تحتوي في الغالب على بيانات متشابهة.
  14. ↑ كيليان، ج. (1995). "حجج فعّالة محسّنة" (ملف PDF) . التطورات في علم التشفير - CRYPT0' 95. سلسلة محاضرات في علوم الحاسوب. المجلد 963. الصفحات 311-324 . doi : 10.1007/3-540-44750-4_25 . ISBN   978-3-540-60221-7.
  15. 1 2 لوري، ب.؛ لانغلي، أ.؛ كاسبر، إ. (يونيو 2013). "شفافية الشهادات" . IETF RFC6962. doi : 10.17487/rfc6962 .
  16. ↑ إيلينا أندريفا؛ تشارلز بويلاجيه؛ أور دانكلمان؛ جون كيلسي (يناير 2009). "هجمات القطيع، والصورة العكسية الثانية، ورسائل حصان طروادة خارج نطاق ميركل-دامغارد". مجالات مختارة في علم التشفير . سلسلة محاضرات في علوم الحاسوب. المجلد 5867. SAC. الصفحات 393-414 . doi : 10.1007/978-3-642-05445-7_25 . ISBN   978-3-642-05443-3.
  17. ↑ إيلينا أندريفا؛ تشارلز بوياغيه؛ بيير آلان فوك؛ جوناثان ج. هوخ؛ جون كيلسي؛ آدي شامير؛ سيباستيان زيمر (2008). "هجمات الصورة العكسية الثانية على دوال التجزئة المترددة". في سمارت، نايجل (محرر). التطورات في علم التشفير - يورو كريبت 2008. سلسلة محاضرات في علوم الحاسوب. المجلد 4965. إسطنبول، تركيا. الصفحات 270-288 . doi : 10.1007/978-3-540-78967-3_16 . ISBN   978-3-540-78966-6. S2CID 12844017 . {{cite book}}: CS1 maint: موقع الناشر مفقود ( رابط )
  18. ↑ تشابويسكي، ج.؛ موهر، ج. (4 مارس 2003). "تنسيق تبادل تجزئة الشجرة (THEX)" . مؤرشف من الأصل في 3 أغسطس 2009.
  19. ↑ "مرجع ملف tigertree.c" . Gtk-Gnutella . تم الاطلاع عليه بتاريخ 23 سبتمبر 2018 .
  20. ↑ "تدقيق: تطبيق P2P DirectConnect" . سيمانتك . مؤرشف من الأصل في 29 يناير 2015. تم الاطلاع عليه في 23 سبتمبر 2018 .
  21. ^ آرني بابنهاوسرهايد (7 يناير 2007). "تم إصدار Phex 3.0.0" . فيكس . تم الاسترجاع في 23 سبتمبر 2018 .
  22. ↑ "قائمة ميزات DC++" . dcplusplus.sourceforge.net .
  23. ↑ "التطوير" . GTK-Gnutella . تم الاطلاع عليه بتاريخ 23 سبتمبر 2018 .

للمزيد من القراءة

  • براءة اختراع شجرة ميركل رقم 4,309,569 – تشرح بنية شجرة التجزئة واستخدامها للتعامل مع العديد من التوقيعات لمرة واحدة 
  • تنسيق تبادل تجزئة الشجرة (THEX) – وصف تفصيلي لأشجار تايجر