أشجار Merkle: كيف تتذكر البلوكشين كل ملاحظة

بحث أصلي من Annkkitaaa

تلخيص ملايين الالتزامات في بصمة صغيرة واحدة

السلسلة: Zcash from First Principles . المقالة 4 . أشجار Merkle الجمهور: المبتدئون. نبني على المقالة 3 (التجزئة والالتزامات). إذا كنت تعرف ما هي البصمة وما هو الالتزام، فأنت جاهز. ما الذي ستخرج به: تصور حدسي وصحيح لأشجار Merkle، وكيفية إثبات العضوية دون كشف العنصر الذي تقصده، وكيف يصبح هذا بالضبط شجرة التزامات الملاحظات في Zcash.

وصفت المقالة 0 "لوحًا عامًا" يحتفظ بكل ملاحظة أُنشئت على الإطلاق ولا يتوقف إلا عن النمو. وبحلول الآن يمكنك أن تتخيل ما المُثبت عليه: الالتزامات (المقالة 3)، أي الأظرف المختومة. لكن اللوح الحقيقي سيحتوي على مئات الملايين منها. فكيف تخزن الشبكة ذلك، وتتحقق منه، وتتيح لك إثبات أن ظرفك موجود على اللوح دون الإشارة إليه؟ الجواب هو أحد أكثر البنى أناقة في علوم الحاسوب: شجرة Merkle.

1. لماذا ينبغي أن يهمك هذا؟

تظهر مشكلتان فور امتلاكك قائمة عامة ضخمة من الالتزامات.

المشكلة الأولى: السلامة على نطاق واسع. إذا كانت القائمة تضم 300 مليون مُدخل، فكيف يستطيع أي شخص التأكد من أنه لم يُعدَّل ولا واحد منها سرًا؟ إن إعادة التحقق من 300 مليون عنصر في كل نظرة أمر ميؤوس منه.

المشكلة الثانية: العضوية الخاصة. لكي تنفق ملاحظة (المقالة 0)، يجب أن تثبت أن التزامك موجود فعلًا على اللوح. لكن إذا أشرت إليه ("إنه المُدخل رقم 4,201,337!")، فقد أزلت هويتك المجهولة بنفسك. أنت بحاجة إلى إثبات أن "ظرفي موجود في مكان ما على هذا اللوح" دون كشف أيّ ظرف هو.

تحل شجرة Merkle كلتا المشكلتين دفعة واحدة. فهي تضغط القائمة بأكملها في بصمة واحدة، وتتيح لك إثبات العضوية بإثبات صغير يُخفي الموضع.

2. الفكرة الحدسية: بطولة إقصائية من البصمات

تخيل جدول بطولة إقصائية، لكن بدلًا من تقدّم اللاعبين، تُدمج البصمات.

• في الأسفل، تحصل كل قطعة بيانات على بصمتها الخاصة (تجزئتها من المقالة 3). هذه هي الأوراق.
• اجمعها في أزواج. تُجزَّأ بصمتا كل زوج معًا لتكوين بصمة أب واحدة.
• اجمع الآباء في أزواج، وجزّئ كل زوج معًا، وهكذا.
• استمر حتى تستقر بصمة واحدة في القمة. ذلك البطل هو جذر Merkle.

أهم خاصية على الإطلاق تنتج مباشرة من تأثير الانهيار الجليدي (المقالة 3):

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

3. شجرة حقيقية، محسوبة بدقة

لنَبْنِ الشجرة ذات الأوراق الأربع أعلاه باستخدام بصمات SHA-256 حقيقية على الأوراق A, B, C, D (أُظهرت القيم المختصرة لتسهيل القراءة):

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

كل شيء ببساطة هو "جزّئ شيئًا، ثم جزّئ أزواجًا من التجزئات." لا شيء أكثر غرابة من المقالة 3، لكنه مرتب في هيئة شجرة.

4. الجزء الذكي: إثبات العضوية دون كشف الموضع

والآن إلى المشكلة الثانية. لنفترض أنك تريد أن تثبت أن الورقة C موجودة في الشجرة لشخص لا يعرف سوى الجذر. أنت لا تعطيه الشجرة كلها. بل تعطيه فقط البصمات اللازمة للصعود من C إلى الجذر، وتسمى مسار الاستيثاق (أو إثبات Merkle):

لإثبات أن C موجودة في الشجرة، قدّم:

• شقيقتها hD، و
• عمّها hAB.

يقوم المُتحقِّق، وهو لا يعرف سوى الجذر، بإعادة حساب الصعود:

step 1:  H(hC , hD)        = hCD       (combine C with its sibling)
step 2:  H(hAB , hCD)      = ROOT?     (combine with the uncle)

وعند الحساب الفعلي: ينتج عن ذلك 1b3faa3fcc5e...، وهو يطابق الجذر. بذلك يثبت أن الورقة موجودة في الشجرة.

هناك أمران يجعلان هذا قويًا:

• إنه صغير جدًا. بالنسبة إلى 4 أوراق، قدّمت 2 من التجزئات. وبالنسبة إلى شجرة فيها n ورقة، فأنت تقدّم فقط نحو log_2(n) من التجزئات. ولشجرة تضم مليار ورقة، فهذا يقارب 30 تجزئة فقط، لا مليارًا. يكاد حجم الإثبات لا ينمو بينما تنفجر الشجرة في الحجم.
• إنها بذرة الخصوصية. يُظهر الإثبات أن ورقتك موجودة في مكان ما داخل الشجرة. وعندما يُنفَّذ هذا التحقق نفسه داخل إثبات معرفة صفرية (المقالة 5)، يُخفى حتى المسار نفسه، فتثبت أن "ملاحظتي موجودة في الشجرة" من دون كشف لا الملاحظة ولا موضعها. وهذا يحل المشكلة الثانية بالكامل.

5. من شجرة Merkle إلى شجرة التزامات الملاحظات في Zcash

الآن يمكننا أن نذكر بدقة ما هو "اللوح العام" في المقالة 0 حقًا:

شجرة التزامات الملاحظات هي شجرة Merkle تكون أوراقها هي التزامات الملاحظات. في كل مرة تُنشأ فيها ملاحظة في أي مكان في العالم، يُلحَق التزامها بوصفه الورقة التالية، ويُحدَّث الجذر.

بعض التفاصيل الحقيقية:

• إنها تنمو فقط. تُلحَق الأوراق ولا تُزال أبدًا. ويُسمّى هذا شجرة Merkle تزايدية. (وهذا يطابق عبارة المقالة 0: "اللوح لا يمزق أي شيء أبدًا.")
• يُسمّى الجذر المرساة. عندما تنفق، تشير معاملتك إلى مرساة حديثة وتثبت، بمعرفة صفرية، أن التزام ملاحظتك موجود في الشجرة ذات ذلك الجذر.
• عمق ثابت. يبلغ عمق الأشجار المحمية في Zcash 32، ما يعني أنها تستطيع احتواء ما يصل إلى 2^(32) (أكثر من أربعة مليارات) ملاحظة.
• تجزئة ملائمة لإثباتات المعرفة الصفرية. لا تُبنى الشجرة باستخدام SHA-256. تستخدم Sapling Pedersen hashes لتجزئة الشجرة، وتستخدم Orchard Sinsemilla (وكلاهما من المقالة 3)، وذلك تحديدًا لكي يكون إثبات مسار العضوية رخيصًا داخل الدارة.

شيء واحد لا تتكفّل به الشجرة ليس: الإنفاق المزدوج

تُثبت الشجرة أن المذكرة موجودة. لكنها لا تمنعك، بمفردها، من إنفاق المذكرة نفسها مرتين. تلك المهمة تخص مجموعة nullifier من المقالة 0: وهي مجموعة منفصلة من "رموز الإبطال". عندما تُنفق، تنشر الـ nullifier الخاص بالمذكرة، وترفض الشبكة أي nullifier سبق أن رأته.

لذا فإن البنيتين العامتين تؤديان دورين متكاملين، وإبقاؤهما منفصلتين هو بالضبط ما يقطع الصلة بين ولادة المذكرة وموتها:

6. إخلاء مسؤولية صريح

هناك تبسيطات، كالمعتاد. أشجار Merkle التزايدية الحقيقية تتتبّع عقد "frontier" بحيث يمكن تحديث الجذر من دون إعادة بناء كل شيء؛ وتحتفظ الشبكة بنافذة من الـ anchors الحديثة، لا بأحدث واحد فقط، حتى لا تتعطل المحافظ مع كل كتلة جديدة؛ كما أن الأوراق الفارغة تستخدم قيمة حشو معرّفة. وقد رسمنا أيضًا أشجارًا ثنائية ذات قوى مرتبة للعدد اثنين. لا يغيّر أيّ من ذلك الحدس الأساسي: أوراق من الالتزامات، تُهشّ في أزواج صعودًا إلى جذر واحد، مع براهين عضوية قصيرة. وتعود التفاصيل الدقيقة للمحاسبة في مقالة البروتوكول.

7. الخلاصة

• تقوم شجرة Merkle بتهشير البيانات إلى أوراق، ثم تقوم بتهشير الأزواج صعودًا حتى يبقى جذر واحد فقط.
• بفضل تأثير الانهيار الجليدي، فإن الجذر هو بصمة للقائمة بأكملها: غيّر ورقة واحدة وسيتغير الجذر. قيمة صغيرة واحدة تصدّق على مجموعة بيانات ضخمة.
• إن برهان العضوية (مسار التحقق) هو ببساطة قيم الأشقاء على طول الصعود إلى الجذر، أي نحو log_2(n) من قيم الهاش، لذا تبقى البراهين صغيرة جدًا حتى مع مليارات الأوراق.
• عند تنفيذ فحص العضوية داخل برهان عدم المعرفة، فإنه يُخفي أيَّ ورقة تقصدها، فيُثبت أن "مذكرتي موجودة في الشجرة" من دون كشف المذكرة أو موضعها.
• إن شجرة التزامات الملاحظات في Zcash هي شجرة Merkle تزايدية لالتزامات الملاحظات، بعمق 32، ويُسمّى جذرها anchor؛ تستخدم Sapling فيها Pedersen وتستخدم Orchard Sinsemilla.
• تُثبت الشجرة الوجود؛ بينما تمنع مجموعة nullifier المنفصلة الإنفاق المزدوج. وإبقاؤهما منفصلتين هو ما يفصل بين ولادة المذكرة وموتها.

مسرد المصطلحات

الأسئلة الشائعة

لماذا شجرة وليست مجرد قائمة طويلة من قيم الهاش؟ القائمة المسطحة ستجبرك على كشف كل إدخال أو معالجته لإثبات العضوية. أمّا الشجرة فتعطيك براهين بحجم لوغاريتمي وجذرًا واحدًا لضمان السلامة.

هل يحتاج المتحقق إلى الشجرة كاملة؟ لا. المتحقق يحتاج فقط إلى الجذر إضافةً إلى مسار التحقق القصير الخاص بك. هذه هي الفكرة كلها.

لماذا العمق 32 تحديدًا؟ لأنه يحدّ الشجرة عند نحو أربعة مليارات مذكرة، وهو هامش واسع جدًا، مع إبقاء برهان العضوية (وتكلفته داخل الدارة) بحجم ثابت يمكن التحكم فيه.

إذا كان الجذر يتغير مع كل مذكرة جديدة، فكيف تبقى البراهين القديمة صالحة؟ تتذكر الشبكة نافذة من الجذور الحديثة (anchors)، لذلك يظل البرهان المُنشأ على anchor أقدم قليلًا قابلًا للتحقق. وتوضح مقالة البروتوكول هذا بدقة.

اختبر حدسك

في شجرتنا ذات الأوراق الأربع، افترض أن مهاجمًا استبدل سرًا الورقة C بقيمة مختلفة لكنه أبقى الجذر المنشور دون تغيير. ما الذي يختلّ بالنسبة له، ولماذا لا يستطيع إصلاح ذلك بهدوء؟ (الإجابة أدناه.)

ما التالي

المقالة 5 . براهين عدم المعرفة: الذروة. لقد بنينا الآن الملاحظات والالتزامات والشجرة، ونواصل القول إنها "مثبتة ضمن عدم المعرفة". تشرح المقالة 5 أخيرًا كيف يمكنك إثبات أن عبارة ما صحيحة، وأن مذكرتك موجودة في الشجرة، وأن الـ nullifier الخاص بك صحيح، وأن الأموال متوازنة، من دون كشف أي شيء من ذلك.

جزء من سلسلة Zcash from First Principles لصالح ZecHub. مرخّص بموجب CC BY-SA 4.0.