شجرة ميركل

الموسوعة الحرة
مثال على شجرة تجزئة ثنائية. تمثل قيم التجزئة 0-0 و0-1 قيم التجزئة لكتل ​​البيانات L1 وL2 على التوالي، وتمثل قيمة التجزئة 0 قيمة التجزئة الناتجة عن دمج قيم التجزئة 0-0 و0-1.

في علم التشفير وعلوم الحاسوب ، تُعرف شجرة التجزئة أو شجرة ميركل بأنها شجرة تُوسَم فيها كل عقدة "ورقية" بالتجزئة المشفرة لكتلة بيانات، بينما تُوسَم كل عقدة ليست ورقة (وتُسمى فرعًا أو عقدة داخلية أو inode ) بالتجزئة المشفرة لوسوم عقدها الفرعية. تُمكّن شجرة التجزئة من التحقق بكفاءة وأمان من محتويات بنية بيانات كبيرة . وتُعد شجرة التجزئة تعميمًا لقائمة التجزئة وسلسلة التجزئة .

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

يُنسب مفهوم شجرة التجزئة إلى رالف ميركل ، الذي حصل على براءة اختراعها في عام 1979. [ 3 ] [ 4 ]

الاستخدامات

يمكن استخدام أشجار التجزئة للتحقق من أي نوع من البيانات المخزنة والمعالجة والمنقولة داخل وبين أجهزة الكمبيوتر. فهي تساعد على ضمان وصول كتل البيانات من النظراء الآخرين في شبكة الند للند سليمة وغير معدلة، بل وتتحقق أيضاً من عدم قيام النظراء الآخرين بإرسال كتل بيانات مزيفة.

تُستخدم أشجار التجزئة في:

تم تقديم اقتراحات لاستخدام أشجار التجزئة في أنظمة الحوسبة الموثوقة . [ 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 ]

تُستخدم تجزئات شجرة النمر في بروتوكولات مشاركة الملفات Gnutella [ 19 ] و Gnutella2 و Direct Connect P2P [ 20 ] وفي تطبيقات مشاركة الملفات مثل Phex [ 21 ] و BearShare و LimeWire و Shareaza و DC++ [ 22 ] و gtk- gnutella [ 23 ] .

انظر أيضاً

مراجع

  1. ^ بيكر ، جورج (2008-07-18). “مخططات توقيع Merkle وأشجار Merkle وتحليل التشفير الخاص بها” (PDF) . جامعة الرور بوخوم. ص.  16. مؤرشفة من الأصلي (PDF) بتاريخ 22-12-2014 . تم الاسترجاع 2013/11/20 .
  2. ↑ "دليل التشفير التطبيقي" . cacr.uwaterloo.ca . القسم 13.4.1 . تاريخ الاسترجاع: 2024-03-07 .
  3. ↑ ميركل، آر سي (1988). "توقيع رقمي قائم على دالة تشفير تقليدية". التطورات في علم التشفير - CRYPTO '87 . سلسلة محاضرات في علوم الحاسوب. المجلد 293. الصفحات 369-378 . doi : 10.1007/3-540-48184-2_32 . ISBN   978-3-540-18796-7.
  4. ↑ براءة اختراع أمريكية رقم 4309569 ، رالف ميركل، "طريقة توفير التوقيعات الرقمية"، نُشرت في 5 يناير 1982، مُسجلة باسم مجلس أمناء جامعة ليلاند ستانفورد جونيور. 
  5. ↑ "صفحة مطوري هاش تري" .
  6. ↑ بونويك، جيف (8 ديسمبر 2005). "تكامل البيانات الشامل في نظام ZFS" . blogs.oracle.com . مؤرشف من الأصل في 3 أبريل 2012. تم الاطلاع عليه في 19 سبتمبر 2013 .
  7. ↑ ليكاي ليو. "مقاومة التباطؤ على محرك أقراص واحد" . likai.org .
  8. ↑ "الاتحاد العام القابل للتحقق" . بروتوكول جوجل ويف . مؤرشف من الأصل بتاريخ 2018-04-08 . تم الاطلاع عليه بتاريخ 2017-03-09 .
  9. ↑ "مقدمة إلى ZFS — أحدث وثائق openzfs" . openzfs.readthedocs.io . تم ​​الاطلاع عليه بتاريخ 27-05-2025 .
  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). "شهادات شجرة ميركل" . فرقة عمل هندسة الإنترنت . فريق عمل الإنترنت . تم الاسترجاع بتاريخ 11/06/2026 .
  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) – وصف تفصيلي لأشجار تايجر