كيف تشكل الخوارزمية الجشعة مكافآت المنقبين في شبكات البلوكشين

جدول الروابط

نبذة مختصرة و1. مقدمة

1.1 نهجنا

1.2 نتائجنا وخارطة الطريق

1.3 الأعمال ذات الصلة

1. النموذج والتمهيد و2.1 نموذج البلوكشين

   2.2 المنقب

   2.3 نموذج اللعبة

   2.4 التمهيد: وظيفة التخصيص الجشعة

2. الحالة الحتمية و3.1 الحد الاعلى الحتمي

   3.2 فئة وظيفة التخصيص المتحيزة للفورية

3. الحالة العشوائية

4. المناقشة والمراجع

• أ. البراهين المفقودة للأقسام 2، 3
• ب. البراهين المفقودة للقسم 4
• ج. المعجم

\

2.3 نموذج اللعبة

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

\ \

\ \ \

2.4 التمهيد: وظيفة التخصيص الجشعة

وظيفة التخصيص الجشعة، المحددة في التعريف 2.6، هي ربما خوارزمية كلاسيكية لمشكلة جدولة الحزم، وتم استكشافها من قبل الأدبيات السابقة للحالة غير المخصومة. علاوة على ذلك، تشير الأدلة التجريبية إلى أن معظم المنقبين يخصصون المعاملات للكتل بشكل جشع. تظهر الأعمال السابقة أنه في بيتكوين والإيثريوم، عادة ما يكون للمعاملات التي تدفع رسومًا أعلى وقت انتظار أقل في مجمع الذاكرة، مما يعني أنه يتم تضمينها بسرعة نسبية في الكتل [MACG20; PORH22; TFWM21; LLNZZZ22]. في الواقع، تعطي خوارزميات اختيار المعاملات الافتراضية لـ Bitcoin Core (التنفيذ المرجعي لعملاء بيتكوين) و geth (عميل التنفيذ الأكثر شعبية للإيثريوم) الأولوية للمعاملات بناءً على رسومها، على الرغم من أنه يمكن تجاوز السلوك الافتراضي لكليهما. لذلك من المثير للاهتمام رؤية أداء هذا النهج.

\ التعريف 2.6 (وظيفة التخصيص الجشعة). بالنظر إلى مجموعة المعاملات S، تختار وظيفة التخصيص الجشعة المعاملة ذات الدفع الأعلى الموجودة في المجموعة S، بغض النظر عن TTL:

\

\ في حالة وجود معاملات متعددة بنفس الرسوم، يتم تفضيل تلك ذات أدنى TTL.

\ في المثال 2.7، نوضح كيف قد يعتمد أداء الجشع على معدل الخصم.

\ مثال 2.7. ندرس أداء الجشع بالنظر إلى الخصم التالي ψ.

\

\ يتم تصوير الجدول الزمني للمعاملات المحدد بواسطة ψ في الشكل 1. في الدور 1، يبث الخصم معاملتين: (1، 2) التي تنتهي في نهاية الدور ولها رسوم قدرها 2، و(2، 4) التي تدفع رسومًا تساوي 4 وتنتهي في نهاية الدور التالي. نظرًا لأن الجشع يعطي الأولوية للمعاملات ذات الرسوم الأعلى، فسوف يخصص (2، 4)، بينما يدع المعاملة الأخرى تنتهي. في الدور التالي، يبث الخصم معاملة واحدة بـ TTL يبلغ 2 ورسوم تبلغ 6، وهي المعاملة الوحيدة المتاحة للجشع في ذلك الدور، وبالتالي سيتم تخصيصها. في الخطوة 3، لا يصدر الخصم أي معاملات، وفي الخطوة 4، يتم بث معاملة (1، 8) ثم يخصصها الجشع.

\

\

\ في اللما 2.8، نحدد النسبة التنافسية للجشع، كدالة لمعدل الخصم.

\

\

\

\

:::info المؤلفون:

(1) يوتام غافني، معهد وايزمان (yotam.gafni@gmail.com);

(2) أفيف يعيش، الجامعة العبرية، القدس (aviv.yaish@mail.huji.ac.il).

:::

:::info هذه الورقة متاحة على arxiv تحت ترخيص CC BY 4.0 DEED.

:::

\