أشجار Merkle: سلامة المعاملات على نطاق واسع

تحتوي كتلة Bitcoin على نحو 2000 معاملة. ولإثبات إدراج المعاملة T من دون تنزيل جميع المعاملات البالغ عددها 2000، نحتاج إلى إثبات مضغوط. تحل أشجار Merkle هذه المشكلة: فحجم الإثبات هو O(log n) من التجزئات بدلًا من O(n) من المعاملات.

الأوراق: SHA256d (تجزئة SHA256 مزدوجة) لكل معاملة. العقدة الأب: SHA256d(left_child_hash || right_child_hash). كرّر العملية حتى تصل إلى تجزئة جذر واحدة. إذا كان عدد العقد فرديًا، فكرّر العقدة الأخيرة. والجذر هو جذر Merkle المخزّن في ترويسة الكتلة (32 بايت).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

لإثبات أن المعاملة T موجودة في الموضع i، قدّم تجزئات العقد الشقيقة عند كل مستوى، من ورقة T إلى الجذر (O(log n) من التجزئات). يعيد المدقّق حساب الجذر انطلاقًا من T ومسار العقد الشقيقة. وإذا تطابق الجذر المحسوب مع جذر Merkle في ترويسة الكتلة، يثبت وجود T.

1024 معاملة ← يتكون إثبات Merkle من 10 تجزئات = 320 بايتًا. يبلغ حجم الكتلة الكاملة نحو 1 MB. ينزّل عملاء SPV الترويسة ذات الحجم 80 بايتًا فقط، إضافة إلى إثبات Merkle ذي الحجم 320 بايتًا لكل معاملة تهمهم — أي توفير بنسبة 99.97% من النطاق الترددي مقارنة بتنزيل الكتلة الكاملة.

إذا تغيرت أي معاملة في الشجرة، تتغير تجزئة ورقتها، وينتشر التغيير صعودًا حتى يغيّر جذر Merkle. ولن يتطابق الجذر المعدّل مع ترويسة الكتلة المحمية بإثبات العمل PoW. ويمكن كشف أي تعديل بحساب الجذر انطلاقًا من المعاملات.

توسّع Ethereum أشجار Merkle باستخدام أشجار trie (شجرة Patricia Merkle): وهي شجرة radix مشفّرة ببادئة سداسية عشرية، تُجزّأ كل عقدة فيها باستخدام Merkle. وتُستخدم في: شجرة الحالة (أرصدة الحسابات)، وشجرة المعاملات، وشجرة الإيصالات. وتتيح إثبات حالة الحساب بكفاءة من دون بيانات العقدة الكاملة.

نطاق Merkle الجبلي (MMR) هو بنية Merkle لا تسمح إلا بالإضافة في نهايتها، ومخصصة للبيانات الشبيهة بالسجلات. تُضاف العناصر الجديدة، مع الحفاظ على القمم (جذور الأشجار الفرعية ذات الأحجام التي تمثل قوى العدد 2). ويُستخدم في Grin/MimbleWimble وZCash لإجراء إثباتات مضغوطة وفعّالة على سجل لا يسمح إلا بالإضافة في نهايته.

تستبدل أشجار Verkle أشجار Merkle في خارطة طريق Ethereum (EIP-6800)، إذ تستخدم التزامات المتجهات (التزامات كثيرات الحدود KZG) بدلًا من التجزئات. ويكون حجم الإثبات O(1) بدلًا من O(log n) في Merkle. ويسمح ذلك للعملاء عديمي الحالة بالتحقق من الحالة من دون تخزين شجرة trie كاملة.

تستخدم شفافية الشهادات (RFC 6962) سجل Merkle لا يسمح إلا بالإضافة في نهايته، بحيث تكون كل شهادة صادرة عن CA ورقةً فيه. وتتحقق إثباتات الإدراج من تسجيل الشهادة. أما إثباتات الاتساق فتتحقق من أن السجل لا يسمح إلا بالإضافة في نهايته (من دون حذف أو إدراج). ويتحقق مورّدو المتصفحات من SCTs عبر هذا السجل.

تُعد أشجار Git (لقطات المجلدات) أشجار Merkle، إذ تجزّئ كل عقدة شجرية كتل الملفات الثنائية والأشجار الفرعية التابعة لها. وتعرّف تجزئة commit حالة قاعدة الكود بأكملها تعريفًا فريدًا. ولهذا يعطي git checkout الملفات نفسها تمامًا في كل مرة.

تتيح أشجار Merkle إثباتات إدراج بحجم O(log n). يخزّن Bitcoin جذر Merkle في ترويسات الكتل، ويستخدم عملاء SPV الإثباتات. وتوسّع Ethereum ذلك إلى أشجار Patricia Merkle. وستستبدل أشجار Verkle أشجار Merkle لتوفير إثباتات بحجم O(1). التالي: تعدين إثبات العمل وصعوبة التعدين.