1. مقدمة

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

2. استعلام قابل للتحقق

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

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

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

3. أشجار ميركل

3.1. تعريف وسمات الأشجار الميركل

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

الأشجار ميركل لديها خاصيتان مهمتان:

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

3.2. كيفية بناء دليل Merkle؟

في سيناريو الاستعلام قابل للتحقق الشائع، هناك مثبت ومحقق. يحتاج المثبت إلى إنشاء دليل وإرساله إلى المحقق. المقابل لشبكة إثيريوم، سيناريو التطبيق النموذجي هو حيث يستفسر العقد الخفيف (عميل يخزن فقط رؤوس الكتل) بيانات المعاملة من عقد كامل أو عقد أرشيف (عملاء لديهم جميع البيانات) ويحصل على دليل ميركل للتحقق محليًا مما إذا كانت نتيجة الاستعلام صحيحة.

يتكون دليل Merkle من الأجزاء الثلاثة التالية:

1. الجذر التجذري لشجرة ميركل لمجموعة البيانات الكاملة.
2. الكتلة البيانات التي يجب إثبات سلامتها.
3. المسار ميركل، الذي يتضمن قيم جميع العقد الشقيقة على المسار من العقدة الورقية إلى العقدة الجذرية.

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

أدناه مثال محدد: عندما يحتاج البرهان إلى إثبات للتحقق من أن "4" هو كتلة بيانات موجودة في مجموعة البيانات، ويحمل المحقق الجذر الموثوق به "1d25" من شجرة Merkle الكاملة للمجموعة البيانات، ثم يحتاج البرهان فقط إلى توفير جميع البيانات المُعلم عليها. بفرض وجود n قطعة بيانات في المجموعة، يتطلب التحقق من صحة أي كتلة بيانات على الأكثر 𝘭𝘰𝘨₂(𝘯) عمليات تجزئة هاش.

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

3.3. أصناف أشجار ميركل

بناء على أساس أشجار Merkle، يمكن دمجها وتعديلها مع هياكل بيانات أخرى لتحقيق خصائص جديدة استنادًا إلى أهداف مختلفة. لتلبية سيناريوهات الاستعلام التحقق المختلفة، يمكن توسيع أشجار Merkle إلى هياكل بيانات مُفَهَرَسَة مختلفة، مثل أشجار Merkle-B (MBT). من أجل تنفيذ كفء لعمليات مثل الإدراج والحذف والاستعلام، اقترح فريق Ethereum شجرة Merkle Patricia (MPT).

3.3.1. شجرة ميركل-بي

شجرة Merkle-B (MBT) تستخدم بشكل رئيسي للتعامل مع استعلامات النطاق قابلة للتحقق. دع 𝑓 يكون عدد الفروع الرئيسية لـ MBT (عدد العقد الفرعية لكل عقد). استنادًا إلى هيكل شجرة B+، يحتفظ كل عقد داخلي في MBT، بالإضافة إلى تخزين 𝑓-1 مفاتيح فهرسة ومؤشرات إلى 𝑓 عقد فرعي، أيضًا بقيم الهاش لجميع عقدة الأطفال بشكل ملخص. أدناه يوجد تمثيل لهيكل عقد الأوراق والأعقد الداخلية في MBT.

عندما يكون من الضروري إثبات أن البيانات المُعادة من استعلام نطاق معين تتوافق مع النطاق المحدد، يجب على الخادم الذي يحسب كائن التحقق (VO) أن يُجري أولاً عمليتي بحث من الأعلى إلى الأسفل للعثور على الحدود اليسرى واليمنى. يجب أيضاً عليه أن يُعيد جميع البيانات داخل هذه الحدود وكذلك التجزئات الخاصة بكل الفروع اللازمة لبناء المسار إلى جذر التجزئة.

عيب هذه الهيكلة البيانات هو أن الـVO المُرجع يمكن أن يثبت فقط أن نتائج الاستعلام تقع ضمن نطاق الاستعلام المطلوب، ولكنه لا يمكن أن يثبت أن النتائج المرجعة كاملة.

3.3.2. شجرة ميركل باتريشيا

إذا تم استخدام شجرة Merkle بريئة لتوفير الاستعلامات التي يمكن التحقق منها، فقد يصبح العملية الزمنية لإعادة إنشاء جذر شجرة Merkle بعد كل إدراج أو حذف للبيانات مهمة. بالإضافة إلى ذلك، فإنه يتطلب الحفاظ على شجيرات بيانات إضافية للتخزين. تجمع شجرة Merkle Patricia (MPT) بين صفات شجرة Radix (شجرة بادئة مضغوطة) وشجرة Merkle، مما يتيح لها أداء عمليات الإدراج والحذف والاستعلامات في وقت O(log(N)). لفهم كامل لـ MPT، يمكن للقراء الرجوع إلى مقالات تقنية مفصلة عن الموضوع. سيقوم هذا المقال فقط بتقديم بعض التعريفات الأساسية وتوفير أمثلة لمساعدة القراء في فهم MPT بسرعة.

الهيكل الأساسي لإيثيريوم يستخدم قاعدة بيانات مفتاح-قيمة للتخزين، مما يعني أن البيانات تُخزن في شكل أزواج مفتاح-قيمة. كما يتم تحليل شجرة الطرق المتعددة إلى أزواج مفتاح-قيمة للتخزين. نحدد الهيكل اللوجي لعقد MPT على النحو التالي:

• فهرس
• مسار
• البيانات

في سياق شجرة Merkle Patricia (MPT)، يشير "الفهرس" إلى مفتاح زوج القيمة، بينما تتكون "المسار" جنبًا إلى جنب مع "البيانات" من قيمة زوج المفتاح والقيمة. يقوم الفهرس في الواقع بتخزين تجزئة عقد شجرة Merkle، والمسار يتوافق مع سلسلة المسار المستخدمة في شجرة البادئة للعثور على العقد المستهدف. يستخدم Ethereum سلاسل سداسية باعتبارها سلاسل مسار، وبالتالي عرض MPT هو 16. البيانات هي البيانات المستهدفة المتوافقة مع المسار.

أدناه مثال على MPT الذي تم تحسينه بالبادئات المضغوطة، مخزنًا البيانات الزوج المفتاح القيمة التالية:

{

'cab8': 'كلب',

‘cabe’: ‘cat’,

‘39’: ‘دجاجة’,

"395": "بطة" ،

'56f0': 'حصان'

}

للعثور على البيانات "duck" باستخدام المسار "395"، ستبدأ من الجذر وتستمر عبر hashA وhashC وhashD للوصول في النهاية إلى البيانات المستهدفة. إليك دليل خطوة بخطوة:

1. جذر التجزئة: هذه هي نقطة الدخول إلى شجرة ميركل باتريشيا (MPT)، وستستخدمها للعثور على أول عقدة.
2. hashA: بناءً على الجذر الهاش، ستسترد العقدة أو المحتوى المحدد بواسطة الهاش A. نظرًا لأن المسار هو '395'، فأنت تبحث عن جزء من الشجرة سيقودك إلى '3'.
3. hashC: بعد الوصول إلى محتوى hashA، تواصل متابعة المسار. القطاع التالي، "9"، يقودك إلى hashC.
4. hashD: في النهاية، مستمراً في الطريق، يشير القطاع الأخير '5' إلى hashD، الذي يحتوي على القيمة 'duck'.

في كل خطوة في المسار، يستفيد MPT من خصائص كل من شجرة Radix، للعثور على المسار الصحيح بناءً على المفتاح، وشجرة Merkle، لضمان سلامة البيانات من خلال روابط التجزئة. يتم تمثيل "المسارات" في الشجرة عادةً بترميز سداسي عشري، الذي يتوافق مع عامل تفرع الشجرة البالغ 16. يشتمل كل عقد في المسار على مؤشرات تجزئة كافية (لعقد الأطفال) وقيم للتحقق من سلامة البيانات وللتنقل من خلال الشجرة.

يرجى ملاحظة أنه في MPT الحقيقي، سيتم ترميز المسارات والبيانات وتخزينها في تنسيق محدد، وأن أنواعًا إضافية من العقد (مثل عقد الامتداد وعقد الورقة) تساعد في تحسين الهيكل لتحقيق الكفاءة في سيناريوهات مختلفة.

4. الالتزام الناقل

تعتبر خطط الالتزامات[1] من البراهين التشفيرية التي تضمن خصوصية وسلامة البيانات. وهي تستخدم على نطاق واسع في سيناريوهات مثل البراهين بدون معرفة والحساب التشاركي الآمن. تنقسم خطة الالتزام الأساسية إلى مرحلتين: مرحلة الالتزام ومرحلة الكشف (أو الفتح).

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

التزام الاتجاه هو نوع خاص من نظام الالتزام المقترح من قبل Catalano وآخرون [2] الذي يسمح للملتزم بالتزام بمجموعة مرتبة من الرسائل 𝑚 = ⟨𝑚1, 𝑚2, …, 𝑚𝑞 ⟩ وبالكشف (فتح) في أي موضع محدد لإثبات أن الرسالة 𝑚𝑖 هي الرسالة الملتزمة الثانية. في الالتزامات الاتجاهية، الربط يعني أنه لا يمكن لأحد أن يفتح نفس الموضع لكشف رسائل مختلفة.

نظام الالتزام بالناقل النمطي عادة ما يتكون من الخوارزميات التالية:

5. أشجار Verkle

5.1. تعريف وخصائص أشجار Verkle

التعريف: شجرة فيركل = التزامات الفيكتور + شجرات ميركل.

يرجى ملاحظة: فيتاليك بوتيرين، مؤسس إيثيريوم، لديه مدونةمشاركة مخصصة خصيصًا لتقديم أشجار Verkle. يضيف هذا الفصل بعض الخلفية والمعرفة الرياضية استنادًا إلى مدونته. تم استمداد بعض البيانات والرسوم التوضيحية الموجودة في النص التالي من مدونته.

تتميز أشجار Verkle (VTs) بتوفير دلائل أصغر بالمقارنة مع أشجار Merkle. بالنسبة للبيانات على نطاق مليارات الإدخالات، قد تولد شجرة Merkle دلائل بحجم حوالي 1 كيلوبايت، في حين يمكن أن تكون دلائل شجرة Verkle أقل من 150 بايت. حجم الدليل المدمج هذا مفيد لتنفيذعملاء بلا حالة”.

هيكل شجرة Verkle مماثل إلى حد ما لشجرة Merkle Patricia (MPT). إليك مثالاً على هيكله. يمكن أن تكون عقد شجرة Verkle: (i) فارغة، (ii) عقد أوراق يحتوي على مفتاح وقيمته المقابلة، أو (iii) عقد داخلي يحتوي على عدد ثابت من عقد الأطفال. يُشار أيضًا إلى هذا العدد من الأطفال بـ "العرض" للشجرة.

الفارق بين VT (أشجار Verkle) و MPT (أشجار Merkle Patricia) يكمن في المقام الأول في كيفية تأثير عرض الشجرة (أو عدد العقد الفرعية التي يحتويها عقد في الشجرة) على كفاءتهم. في حالة MPT، إذا كان العرض أكبر، فإنه يميل إلى أن يكون أقل كفاءة لأن عرض أكبر يعني وجود مزيد من العقد الشقيقة، مما قد يؤدي إلى زمن تحديث أطول لـ MPT وحجم أدلة أكبر. وعلى العكس من ذلك، بالنسبة لـ VT، يؤدي عرض شجرة أوسع إلى أدلة أصغر. القيد الوحيد هو أنه إذا كان العرض مرتفعًا للغاية، فإن الوقت الذي يستغرقه إنشاء دليل يمكن أن يصبح أطول.

في إثيريوم@vbuterin/verkle_tree_eip">تقترح تصاميم لـ VTs عرضًا يبلغ 256، وهو أكبر بكثير من الحالي 16 لـ MPT. يعد هذا العرض الكبير جدًا ممكنًا في VTs بفضل استخدام تقنيات التشفير المتقدمة، مثل التزامات الناقلات، التي تتيح إثباتات مدمجة بغض النظر عن عرض الشجرة. تسمح هذه التقنية بالضغط بمزيد من الكفاءة في حجم الإثباتات لأشجار Verkle. سيشرح النص التالي الميزات المذكورة أعلاه بمزيد من التفصيل.

5.2. الالتزام وإثبات أشجار Verkle

لنرى كيف يتم إنشاء الأدلة في MPT: تحتاج الأدلة إلى تضمين قيم التجزئة لجميع العقد الجانبية (أو العقد الشقيقة) على المسار من العقد الجذري إلى عقد الورقة المستهدفة. باعتبار "4ce" مثالًا، الأجزاء المُحدّدة باللون الأحمر في الرسم البياني أدناه هي العقد التي يجب تضمينها في الأدلة المُرجَعة.

في أشجار Verkle ، لا تحتاج إلى تقديم عقد الأخوة. بدلاً من ذلك ، تحتاج فقط إلى تقديم المسار مع بعض البيانات الإضافية كدليل.

فكيف يمكن إنشاء التزامات لفت؟ تستخدم وظيفة التجزئة للحساب ليست تجزئة تقليدية ولكنها تستخدم التزامات الناقل.

بعد استبدال وظيفة الهاش بخوارزمية تكوين التزام من التزامات الناقلات، أصبح الهاش الجذري الذي يسمى الآن تزام جذري. إذا تم تزوير بيانات أي عقد، فسيؤثر في النهاية على التزام الجذر.

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

في التنفيذات العملية، يتم استخدام التزامات الجذرية (التي يمكن تنفيذها ببساطة وكفاءة لالتزامات الناقلات)، مما يسمح بالالتزام بمتعدد الحدود. أكثر نظامين لالتزامات متعددة الحدود ودية للمستخدمين هماالتزامات KZG” و “التزامات متعددة الحدود بنمط غير قابل للاختراق(السابق له حجم تعهد يبلغ 48 بايت، بينما الأخير 32 بايت).

إذا استخدمت التزامات KZG والأدلة، فإن الدليل على كل عقد وسيطي هو مجرد 96 بايت، مما يمثل توفيرًا في المساحة تقريبًا ثلاث مرات مقارنة بشجرة Merkle الأساسية (بافتراض عرض 256).

التعقيد الزمني النظري لعمليات على أشجار ميركل وأشجار فيركل كما يلي:

إن مخطط البرهان فيركل المقدم حتى الآن أمر أساسي تمامًا؛ في الواقع، هناك استراتيجيات تحسين متقدمة أخرى متاحة.

5.3. الأمثلية: دمج البراهين

5.3.1. فكرة

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

5.3.2. الاشتقاق الرياضي

أولاً، دعونا نقدم بعض المفاهيم الأساسية حول الجذور التربيعية في الرياضيات: كيف نقوم بتقليص متعددات الحدود، المعروف أيضاً باسم تقليل الدرجة لمتعددة الحدود؟

بفرض أننا نعرف متعددًا 𝑃(𝑥) وقيمتها 𝑦₁ في 𝑥₁، أي أن 𝑃(𝑥₁) = 𝑦₁.

الآن، اعتبر متعددًا جديدًا 𝑃(𝑥) - 𝑦₁ ، الذي يكون له قيمة صفرية في (𝑥 = 𝑥₁) ، لأن 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

لذلك، يحتوي متعدد الحدود ​​𝑃(𝑥) - 𝑦₁ على جذر في 𝑥 = 𝑥₁ ، مما يعني أن (𝑥 - 𝑥₁ ) هو عامل لـ 𝑃(𝑥) - 𝑦₁ .

بعبارة أخرى، يمكننا التعبير عنها في الشكل التالي: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) هو متعددة حقيقية أخرى يكون درجتها أقل بواحد من تلك التي لدى 𝑃(𝑥). هذا يرجع إلى أن (𝑥 -𝑥₁ ) هو عامل من الدرجة الأولى، مما يقلل من الدرجة الإجمالية للمتعددة.

كيفية استخدام KZG لإثبات قيمة واحدة في الفيكتور؟

خذ التزام KZG10 كمثال، بالنسبة للدالة العلمية 𝑃(𝑥) ، فلنفترض أن التزام الدالة العلمية لها هو [ 𝑃(𝑠) ]₁ .

كما شرح سابقا، بالنسبة للمتعدد الحاصلي 𝑃(𝑥)، إذا كانت 𝑃(𝑧) = 𝑦، فإن لدينا 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)

الآن، يمكن للمثبت إنتاج دليل على أن المتعدد الحدودي 𝑃(𝑥) يرضي 𝑃(𝑧) = 𝑦 : حساب [ 𝑄(𝑠) ]₁ وإرساله إلى المحقق.

يحتاج المحقق إلى التحقق من 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

كيفية استخدام KZG لإثبات قيم متعددة في متجه؟

يمكننا بناء دليل لإظهار قيم متعددة في متجه كما يلي:

باستخدام هذه الطريقة، بغض النظر عن عدد نقاط البيانات في نفس الاتجاه الذي يجب التحقق منها، يُطلب فقط دليل ذو حجم ثابت.

الآن دعونا نلقي نظرة على مخطط Verkle Tree بدون تحسين من منظور خوارزمية الالتزام KZG.

باستخدام طريقة البناء من القسم "كيفية استخدام KZG لإثبات قيمة واحدة في متجه"، يمكن للتحقق بناء التزامات للمتعددة والحاصلة لكل متعدد 𝑓ᵢ(𝑥)، مما يؤدي إلى مجموع 𝟐﹡𝑚 التزامات KZG. يرسل المحقق كل هذه التزامات كدليل للتحقق.

ومع ذلك، كما ذكر سابقا، تتطلب هذه الطريقة توليد عدة دلائل، ويحتاج المحقق أيضا إلى أداء عدة عمليات تحقق. نحتاج إلى إيجاد طريقة لضغط عدة دلائل على التزام.

دمج الأدلة

يُرسل الدليل [ 𝑞( 𝑠 )]₁ إلى المحقق للتحقق.

يتكون الدليل الذي ينتجه هذا النظام من التزام واحد واثنين من الأدلة وقيمة واحدة، بحجم بيانات ثابت. في نهاية المطاف، بعد الأمثلة الدمج في شجرة Verkle، يتضمن الكائن القابل للتحقق الذي يتم إرساله إلى المحقق ما يلي:

1. دليل حجم ثابت
2. بيانات الأوراق التي يجب إثباتها (أزواج المفتاح والقيمة)
3. قيم الالتزام لجميع العقد على المسار من الورقة إلى الجذر (بفرض عرض شجرة يبلغ 256 مع 2³² عقدة، فإن العمق المتوسط ​​هو 4، مما يتطلب قيم الالتزام 3 فقط)

لاحظ أن 𝑥ᵢ و𝑦ᵢ لا يجب أن يتم توفيرها بشكل صريح؛ يمكن حسابها جميعًا.

5.3.3. الأداء

بالنسبة لمخطط دمج البرهان لأشجار Verkle، فإن الحجم المحدد للبرهان المولد هو كما يلي (وحدة الصف هي مليار).

تفترض البيانات أعلاه استخدام شجرة عرضها 256، واستخدام نظام التزام KZG (بحجم التزام 48 بايت)، ويزيد استخدام الشجرة. في الواقع، لتوزيعات معلومات عشوائية تمامًا، سيزيد عمق الشجرة بحوالي 60٪، وسيزداد حجم كل عنصر بمقدار 30 بايت. إذا تم استخدام نظام العنصر الناري، فسيكون حجم التزامه 32 بايت.

5.4. حمل الحساب للبرهان والتحقق

1. إنشاء الدليل: ترتبط تكلفة إنشاء الأدلة بواسطة البرهان بعرض الشجرة، ولكن كل عملية ذرية تتطلب تكلفة حسابية منخفضة نسبيًا، لذلك تؤدي أشجار Verkle بأعرض بين 256 و 1024 بشكل جيد من حيث الخوارزميات.
2. التحقق من البرهان: أشار فيتاليك إلى أن خوارزمية التحقق سريعة للغاية ويمكن أن تكتمل عادة في غضون 100 مللي ثانية، حتى عند وجود عدة آلاف من القيم للتحقق منها.
3. عند تحديث أشجار Verkle: يتطلب تحديث الشجرة إعادة حساب جميع قيم الالتزام الوسيطة على طول المسار بسبب التغييرات في القيم أو الهيكل. ومع ذلك، أشار فيتاليك إلى أنه بفضل بعض خصائص خوارزمية الالتزام الكثيري، من الممكن تصميم طريقة تقوم بحساب قيم الالتزام البديلة مسبقًا وتخزينها، مما يقلل من تكلفة الوقت الحسابي أثناء التحديثات، والتي تتبادل في الأساس المساحة مقابل الوقت.

6. الاستنتاجات

ما يلي هي الكلمات الأصلية لمدونة فيتاليك، قمنا بإضافة فقرة في النهاية كإضافة.

تعد أشجار Verkle ترقية قوية لبراهين Merkle التي تسمح بأحجام إثبات أصغر بكثير. بدلا من الحاجة إلى توفير جميع "العقد الشقيقة" في كل مستوى ، يحتاج البروفير فقط إلى تقديم دليل واحد يثبت جميع العلاقات بين الوالدين والطفل بين جميع الالتزامات على طول المسارات من كل عقدة ورقة إلى الجذر. يسمح هذا بتقليل أحجام الإثبات بعامل ~ 6-8 مقارنة بأشجار Merkle المثالية ، وبعامل يزيد عن 20-30 مقارنة بأشجار باتريشيا السداسية التي تستخدمها Ethereum اليوم (!!).

إنها تتطلب تشفيرا أكثر تعقيدا لتنفيذها ، لكنها توفر الفرصة لتحقيق مكاسب كبيرة لقابلية التوسع. على المدى المتوسط ، يمكن ل SNARKs تحسين الأمور بشكل أكبر: يمكننا إما SNARK مدقق إثبات Verkle الفعال بالفعل لتقليل حجم الشاهد إلى ما يقرب من الصفر ، أو العودة إلى براهين SNARKed Merkle إذا / عندما تتحسن SNARKs كثيرا (على سبيل المثال من خلال GKR ، أو وظائف التجزئة الصديقة ل SNARK ، أو ASICs). علاوة على ذلك ، فإن ظهور الحوسبة الكمومية سيجبر على تغيير براهين STARKed Merkle مع التجزئة لأنه يجعل التماثل الخطي الذي تعتمد عليه أشجار Verkle غير آمن. لكن في الوقت الحالي ، يمنحوننا نفس مكاسب التوسع التي سنحصل عليها مع مثل هذه التقنيات الأكثر تقدما ، ولدينا بالفعل جميع الأدوات التي نحتاجها لتنفيذها بكفاءة.

حاليًا، قد قدم العديد من عملاء إثيريوم تنفيذ شجرة Verkle وشبكات الاختبار ذات الصلة. لا تزال المجتمع يناقش الوقت الذي ستتم فيه إطلاق أشجار Verkle على الشبكة الرئيسية. من المرجح أن يتم تنفيذ ذلك في ترقية الشوكة الصعبة في عام 2024 أو 2025. للحصول على معلومات مفصلة حول أشجار Verkle على إثيريوم، انظر https://verkle.info/ .

7. المرجع

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. الحد الأدنى من إثباتات الكشف عن المعرفة[J]. مجلة علوم الحاسوب والأنظمة، 1988، 37(2): 156–189.

[2]. CATALANO D, FIORE D. التزامات الفيكتور وتطبيقاتها [C] // التشفير العام - PKC 2013: المؤتمر الدولي السادس عشر حول الممارسة والنظرية في التشفير العام ، نارا، اليابان ، 26 فبراير - 1 مارس 2013. الإجراءات 16. سبرينغر ، 2013: 55-72.

تنصل:

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