هل من الممكن توليد أرقام عشوائية إذا كنا لا نثق ببعضنا البعض؟ الجزء 1

يا هبر!

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

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

عندما نقوم بتصميم بروتوكول توليد أرقام عشوائية موزعة، نريد أن يكون له ثلاث خصائص:

1. يجب أن يكون غير متحيز. بمعنى آخر، لا ينبغي لأي مشارك بأي شكل من الأشكال أن يؤثر على نتيجة مولد الأرقام العشوائية.

2. يجب أن يكون غير متوقع. بمعنى آخر، لا ينبغي لأي مشارك أن يكون قادرًا على التنبؤ بالرقم الذي سيتم إنشاؤه (أو استنتاج أي من خصائصه) قبل إنشائه.

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

في هذه المقالة، سننظر في طريقتين: RANDAO + VDF ونهج رمز المحو. في الجزء التالي، سوف نلقي نظرة فاحصة على نهج توقيعات العتبة.

لكن أولاً، دعونا نحلل خوارزمية بسيطة وشائعة الاستخدام تكون قابلة للتطبيق، ولا يمكن التنبؤ بها، ولكنها متحيزة.

رانداو

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

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

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

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

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

راندو + في دي إف

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

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

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

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

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

بالنسبة لعائلة VDF المذكورة أعلاه، يمكن أن يكون أداء ASIC المخصص أسرع بما يزيد عن 100 مرة من الأجهزة التقليدية. وبالتالي، إذا استمرت مرحلة النشر 10 ثوانٍ، فإن VDF المحسوب على ASIC يجب أن يستغرق أكثر من 100 ثانية للحصول على هامش أمان 10x، وبالتالي فإن نفس VDF المحسوب على الأجهزة التقليدية يجب أن يستغرق 100 × 100 ثانية = ~ 3 ساعات .

تخطط مؤسسة Ethereum لحل هذه المشكلة عن طريق إنشاء أجهزة ASIC مجانية متاحة للعامة. بمجرد حدوث ذلك، يمكن لجميع البروتوكولات الأخرى أيضًا الاستفادة من هذه التقنية، ولكن حتى ذلك الحين، لن يكون نهج RANDAO + VDF قابلاً للتطبيق بالنسبة للبروتوكولات التي لا يمكنها الاستثمار في تطوير ASICs الخاصة بها.

يتم جمع العديد من المقالات ومقاطع الفيديو وغيرها من المعلومات حول VDF هذا الموقع.

استخدام رموز المحو

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

الفكرة الرئيسية للبروتوكول هي كما يلي. من أجل التبسيط، لنفترض أن لديها 100 عضو بالضبط. لنفترض أيضًا أن جميع المشاركين محليًا لديهم بعض المفاتيح الخاصة، وأن المفاتيح العامة لجميع المشاركين معروفة لجميع المشاركين:

1. يخترع كل مشارك محليًا سلسلة طويلة، ويقسمها إلى 67 جزءًا، ويولد رموز المسح للحصول على 100 مشاركة بحيث تكون أي 67 كافية لاستعادة السلسلة، ويخصص كل مشاركة من الـ 100 مشاركة لأحد المشاركين، ويقوم بتشفيرها باستخدام نفس المفتاح العام للمشارك. ثم يتم نشر كافة المشاركات المشفرة.

2. يستخدم المشاركون بعض الإجماع للتوصل إلى اتفاق بشأن مجموعات مشفرة من 67 مشاركًا محددًا.

3. بمجرد التوصل إلى الإجماع، يأخذ كل مشارك المشاركات المشفرة في كل مجموعة من المجموعات الـ 67 المشفرة بمفتاحه العام، ويفك تشفير كل هذه المشاركات، وينشر كل هذه المشاركات التي تم فك تشفيرها.

4. بمجرد إكمال 67 مشاركًا للخطوة (3)، يمكن فك تشفير جميع المجموعات المتطابقة وإعادة بنائها بالكامل نظرًا لخصائص رموز المسح، ويمكن الحصول على الرقم النهائي كـ XOR للسطور الأولية التي بدأ منها المشاركون (1). ).

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

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

عندما يقوم المشارك في الخطوة (4) بفك رموز 67 نبضة لبعض السلسلة، ويحاول استعادة السلسلة الأصلية منها، يكون أحد الخيارات ممكنًا:

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

2. تتم استعادة الصف، لكن الجذر المحسوب محليًا لا يتطابق مع الجذر المتفق عليه.

3. لم يتم استعادة الخط.

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

توقيعات عتبة

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

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

الاستخدام الشائع لتوقيعات BLS في بروتوكولات blockchain، بصرف النظر عن إنشاء الأرقام العشوائية، هو التوقيع الجماعي في بروتوكولات BFT. لنفترض أن 100 مشارك قاموا بإنشاء كتل، وتعتبر الكتلة نهائية إذا قام 67 منهم بالتوقيع عليها. يمكنهم جميعًا إرسال الأجزاء الخاصة بهم من توقيع BLS واستخدام بعض خوارزميات الإجماع للموافقة على 67 منها ثم دمجها في توقيع BLS واحد. يمكن استخدام أي 67 جزءًا (أو أكثر) لإنشاء التوقيع النهائي، والذي سيعتمد على التوقيعات الـ 67 التي تم دمجها بالضبط، وبالتالي قد تختلف، ولكن على الرغم من أن الاختيار المختلف لـ 67 مشاركًا سيخلق توقيعًا مختلفًا، فإن أي سيكون هذا التوقيع بمثابة توقيع كتلة صالح. ويكفي بعد ذلك لبقية المشاركين تلقي والتحقق من توقيع واحد فقط لكل كتلة، بدلاً من 67، مما يقلل بشكل كبير من الحمل على الشبكة.

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

يكون هذا النهج تجاه العشوائية قابلاً للتطبيق إذا كان ما لا يقل عن ⅔ من المشاركين متصلين بالإنترنت ويتبعون البروتوكول، ويكون غير متحيز ولا يمكن التنبؤ به طالما أن ما لا يقل عن ⅓ من المشاركين يتبعون البروتوكول. من المهم ملاحظة أن المهاجم الذي يتحكم في أكثر من ⅓ ولكن أقل من ⅔ من المشاركين يمكنه إيقاف البروتوكول، ولكن لا يمكنه التنبؤ بمخرجاته أو التأثير عليها.

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

في الختام

هذه المقالة هي الأولى في سلسلة مقالات المدونة التقنية. قريب. NEAR هو بروتوكول blockchain ومنصة تطوير التطبيقات اللامركزية مع التركيز على سهولة التطوير وسهولة الاستخدام للمستخدمين النهائيين.

رمز البروتوكول مفتوح، وتنفيذنا مكتوب بلغة Rust، ويمكن العثور عليه هنا.

يمكنك أن ترى كيف يبدو التطوير ضمن NEAR، ويمكنك تجربة IDE عبر الإنترنت هنا.

يمكنك متابعة جميع الأخبار باللغة الروسية في المجموعة في برقية و المجموعة على فكونتاكتي، وباللغة الإنجليزية في الرسمية تغريد.

اراك قريبا!

المصدر: www.habr.com