إطار Shoal: كيف يمكن تقليل تأخير Bullshark على Aptos؟

نظرة عامة

حل مختبرات Aptos مشكلتين مفتوحتين مهمتين في DAG BFT، مما قلل بشكل كبير من التأخير، وأزال لأول مرة الحاجة إلى التوقف في بروتوكول الحتمية الفعلي. بشكل عام، تم تحسين تأخير Bullshark بنسبة 40% في حالة عدم وجود أعطال، و80% في حالة وجود أعطال.

Shoal هو إطار عمل يعزز بروتوكول الإجماع القائم على Narwhal من خلال خط الأنابيب وسمعة القادة ( مثل DAG-Rider و Tusk و Bullshark ). يعمل خط الأنابيب على تقليل تأخير ترتيب DAG من خلال تقديم نقاط مرجعية في كل جولة، بينما تعمل سمعة القادة على تحسين مشكلة التأخير من خلال ضمان ارتباط النقاط المرجعية بأسرع عقد التحقق. علاوة على ذلك، تتيح سمعة القادة لـ Shoal الاستفادة من بناء DAG غير المتزامن للقضاء على جميع السيناريوهات التي تتضمن انتهاء الوقت. وهذا يسمح لـ Shoal بتوفير خاصية الاستجابة العالمية، التي تحتوي على الاستجابة المتفائلة التي تحتاجها عادةً.

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

الدافع

عند السعي لتحقيق أداء عالٍ لشبكات البلوك تشين، كان الناس دائمًا يهتمون بتقليل تعقيد الاتصال. ومع ذلك، لم تؤدِ هذه الطريقة إلى زيادة ملحوظة في الإنتاجية. على سبيل المثال، حقق نظام Hotstuff المطبق في الإصدارات المبكرة من Diem فقط 3500 TPS، وهو أقل بكثير من الهدف البالغ 100k+ TPS.

تأتي الاختراقات الأخيرة من فهم أن انتشار البيانات هو العائق الرئيسي القائم على بروتوكول القادة، ويمكن الاستفادة من التوازي. يفصل نظام Narwhal انتشار البيانات عن منطق الإجماع الأساسي، مما يقدم هيكلًا حيث يقوم جميع الموثقين بنشر البيانات في نفس الوقت، بينما تقوم مكونات الإجماع بترتيب كمية صغيرة من البيانات الوصفية. وقد أبلغت ورقة Narwhal عن قدرة معالجة تبلغ 160,000 TPS.

المتجر Quorum الذي تم تقديمه سابقًا حقق الفصل بين نشر البيانات والتوافق، لتوسيع بروتوكول التوافق الحالي Jolteon. Jolteon هو بروتوكول قائم على القيادة، يجمع بين المسار السريع الخطي لـ Tendermint وتغيير العرض بأسلوب PBFT، مما يقلل تأخير Hotstuff بنسبة 33%. ومع ذلك، فإن بروتوكول التوافق القائم على القيادة لا يمكنه الاستفادة الكاملة من إمكانيات نقل البيانات لنظام Narwhal. على الرغم من فصل نشر البيانات عن التوافق، إلا أن القائد في Hotstuff/Jolteon لا يزال مقيدًا مع زيادة الإنتاجية.

لذلك، تم نشر Bullshark، وهو بروتوكول إجماع بدون تكلفة اتصال، فوق Narwhal DAG. لسوء الحظ، فإن الهيكل DAG الذي يدعم Bullshark عالي الإنتاجية يأتي بتكلفة تأخير بنسبة 50% مقارنةً بـ Jolteon.

تتناول هذه المقالة كيفية تقليل Shoal بشكل كبير من تأخير Bullshark.

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

خلفية DAG-BFT

كل قمة في Narwhal DAG مرتبطة بدورة. عند الدخول إلى الدورة r، يجب على المصادقين أولاً الحصول على n-f من القمم في الدورة r-1. يمكن لكل مصادق في كل دورة بث قمة واحدة، ويجب أن تشير كل قمة إلى n-f من القمم في الدورة السابقة على الأقل. نظرًا للاختلاف الزمني في الشبكة، قد يلاحظ المصادقون المختلفون وجهات نظر محلية مختلفة لـ DAG في أي نقطة زمنية.

خاصية رئيسية لـ DAG ليست غامضة: إذا كان لدى عقدتين تحققيتين نفس القمة v في العرض المحلي لـ DAG، فإن لهما نفس تاريخ السبب v تمامًا.

الترتيب العام

يمكن التوصل إلى توافق حول الترتيب الكلي لجميع رؤوس DAG دون أي تكاليف اتصال إضافية. لهذا، فإن المدققين في DAG-Rider وTusk وBullshark يفسرون هيكل DAG كبروتوكول إجماع، حيث تمثل الرؤوس الاقتراحات، وتمثل الحواف الأصوات.

على الرغم من أن منطق التقاطع الجماعي في هيكل DAG مختلف، إلا أن جميع بروتوكولات الإجماع القائمة على Narwhal الحالية تتسم بالهيكل التالي:

1. النقطة المرجعية المحددة: كل بضع جولات سيكون هناك قائد محدد مسبقًا، وتسمى قمته النقطة المرجعية.

2. نقاط الربط المرتبة: يقرر المدققون بشكل مستقل ولكن حتمي أي نقاط ربط يجب ترتيبها أو تخطيها.

3. تاريخ السبب والنتيجة المرتب: يقوم المدققون بمعالجة قائمة النقاط المرجعية المرتبة واحدة تلو الأخرى، وترتيب الرؤوس غير المرتبة السابقة في تاريخ السبب والنتيجة لكل نقطة مرجعية.

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

وافق جميع المدققين على أول نقطة ربط مرتبة.

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

تأخير Bullshark

تعتمد تأخيرات Bullshark على عدد الدورات بين النقاط الثابتة المرتبة في DAG. على الرغم من أن النسخة المتزامنة الأكثر عملية لـ Bullshark لديها تأخير أفضل من النسخة غير المتزامنة، إلا أنها لا تزال بعيدة عن كونها مثالية.

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

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

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

إطار Shoal

حلت Shoal مشكلتين من مشكلات التأخير هاتين، حيث تعزز Bullshark ( أو أي بروتوكول BFT قائم على Narwhal ) من خلال خطوط الإنتاج، مما يسمح بوجود نقطة ربط في كل جولة، ويقلل من تأخير جميع القمم غير المرتبطة في DAG إلى ثلاث جولات. كما قدمت Shoal آلية سمعة القائد بدون تكلفة في DAG، حيث يتم اختيار القادة بسرعة.

التحدي

في سياق بروتوكول DAG ، تعتبر خطوط الأنابيب وسمعة القادة مسائل صعبة ، للأسباب التالية:

1. كانت المحاولات السابقة لتعديل منطق Bullshark الأساسي على خط الإنتاج، ولكن يبدو أن هذا غير ممكن من حيث الجوهر.

2. تم إدخال سمعة القادة في DiemBFT وتم توثيقها رسميًا في Carousel، حيث يتم اختيار القادة المستقبليين بشكل ديناميكي بناءً على الأداء السابق للمدققين ( الرمز المميز في Bullshark ). على الرغم من أن وجود اختلافات في هوية القادة لا ينتهك أمان هذه البروتوكولات، إلا أنه قد يؤدي إلى ترتيب مختلف تمامًا في Bullshark، مما يثير القضية الأساسية: إن اختيار الرموز الدوارة بشكل ديناميكي وحتمي ضروري لحل الإجماع، حيث يحتاج المدققون إلى الاتفاق على التاريخ المرتب لاختيار الرموز المستقبلية.

كدليل على صعوبة المشكلة، فإن تنفيذ Bullshark ( لا يشمل الميزات التي لا تدعمها التنفيذات الحالية في بيئة الإنتاج ).

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

اتفاقية

على الرغم من التحديات المذكورة أعلاه، إلا أن الحلول مخفية في البساطة.

في Shoal، نعتمد على القدرة على تنفيذ الحسابات المحلية على DAG لتحقيق القدرة على حفظ وإعادة تفسير المعلومات من الجولات السابقة. بفضل الفهم الأساسي الذي يتفق عليه جميع المدققين حول أول نقطة ربط مرتبة، تقوم Shoal بدمج عدة حالات من Bullshark بشكل متسلسل لمعالجة خطوط الأنابيب، مما يجعل ( أول نقطة ربط مرتبة هي نقطة التبديل للحالات، ) تُستخدم القصة السببية لنقطة الربط لحساب سمعة القائد.

خط الإنتاج

V تربط الجولات بالقادة. تقوم Shoal بتشغيل مثيلات Bullshark واحدة تلو الأخرى، ويتم تحديد ربط كل مثيل مسبقًا بواسطة الخريطة F. يطلب كل مثيل رباطًا، مما يؤدي إلى الانتقال إلى المثيل التالي.

في البداية، قامت Shoal بتشغيل أول نموذج لـ Bullshark في الجولة الأولى من DAG واستمرت حتى تم تحديد أول نقطة ربط مرتبة، مثل في الجولة r. وافق جميع المدققين على هذه النقطة الربط. لذلك، يمكن لجميع المدققين أن يتفقوا بشكل مؤكد على إعادة تفسير DAG بدءًا من الجولة r+1. Shoal فقط بدأت نموذج Bullshark جديد في الجولة r+1.

في أفضل الحالات، يسمح هذا لـ Shoal بطلب رصيف واحد في كل جولة. يتم ترتيب نقاط الرصيف في الجولة الأولى حسب النموذج الأول. ثم، يبدأ Shoal نموذجًا جديدًا في الجولة الثانية، والذي لديه نقطة رصيف خاصة به، يتم ترتيبها بواسطة هذا النموذج، وبعد ذلك، يتم طلب نقطة رصيف جديدة في الجولة الثالثة، وتستمر العملية.

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

سمعة القادة

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

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

في Shoal، يمكن دمج خطوط الإنتاج وسمعة القيادة بشكل طبيعي، لأن كلاهما يستخدم نفس التقنية الأساسية، وهي إعادة تفسير DAG بعد التوصل إلى توافق بشأن أول نقطة ربط مرتبة.

في الواقع، الاختلاف الوحيد هو أنه بعد تصنيف نقاط الربط في الجولة r، يحتاج المُصادقون فقط إلى حساب التعيين الجديد F' بدءًا من الجولة r+1 بناءً على التاريخ السببي للنقاط المرتبطة المرتبة في الجولة r. ثم، يبدأ عقد التحقق في تنفيذ مثال جديد لـ Bullshark باستخدام وظيفة اختيار النقاط المحدثة F' بدءًا من الجولة r+1.

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

لا مزيد من المهلات

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

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

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

في Bullshark، يُستخدم المهلة لبناء DAG، لضمان أن القادة الأمناء سيضيفون النقاط المرجعية إلى DAG خلال فترة المزامنة.