دوال العشوائية القابلة للتحقق في الإجماع

تتطلب بروتوكولات الإجماع العشوائية لانتخاب القائد واختيار اللجان وتعيين الأجزاء. ويجب أن تحقق العشوائية ثلاث خصائص: عدم قابلية التنبؤ (ألا يستطيع أحد التنبؤ بالمخرج قبل كشفه)، وعدم قابلية الانحياز (ألا يستطيع أي مشارك التلاعب بالمخرج لمصلحته)، وقابلية التحقق العلني (أن يتمكن أي شخص من التحقق من صحة المخرج دون الثقة بمولّده). وتفشل الأساليب الساذجة؛ إذ يمكن التلاعب بالرقم العشوائي الناتج عن عقدة واحدة، كما تسمح مخططات commit-reveal بانحياز آخر من يكشف قيمته. وتحل الدوال العشوائية القابلة للتحقق (VRFs) هذه المتطلبات الثلاثة.

الدالة العشوائية القابلة للتحقق (VRF)، التي قدمها Micali وRabin وVadhan عام 1999، هي دالة شبه عشوائية توفر برهانًا على صحتها. وتضم VRF ثلاث خوارزميات: تولّد KeyGen زوج مفاتيح (SK, PK)؛ وتنتج Prove(SK, alpha) الزوج (beta, pi)، حيث يكون beta هو المخرج وpi هو البرهان؛ وتعيد Verify(PK, alpha, beta, pi) القيمة valid أو invalid. ويكون المخرج beta غير قابل للتمييز عن العشوائي بالنسبة إلى من لا يعرف SK (شبه العشوائية في VRF)، ويستحيل تزوير البرهان pi (وحدانية VRF). ويبلغ حجم البرهان O(1)، أي ثابتًا بغض النظر عن الإدخال.

أكثر إنشاءات VRF انتشارًا في الاستخدام هو ECVRF (IETF RFC 9381)، ويعتمد على صعوبة مسألة اللوغاريتم المتقطع على المنحنيات الإهليلجية. عند توفر مفتاح خاص x وإدخال alpha، يحسب المُثبت H = hash-to-curve(PK, alpha) (بتعيين alpha إلى نقطة على المنحنى)، ثم gamma = x * H (الضرب القياسي). ويكون مخرج VRF هو beta = keccak(gamma). ويستخدم البرهان pi حجة معرفة صفرية شبيهة بـ Schnorr: يلتزم المُثبت بقيمة عشوائية k، ويحسب التحدي c = hash(H, gamma, k*G, k*H)، ثم الاستجابة s = k - c*x، ويُخرج pi = (gamma, c, s). ويتحقق التحقق من معادلات Schnorr ويعيد حساب beta.

كانت Algorand (Silvio Micali وآخرون، 2017) رائدةً في استخدام VRF ضمن إجماع سلاسل الكتل. في كل جولة، يقيّم كل مدقّق VRF(SK, round || seed) سراً للحصول على خرج عشوائي. يُقارَن الخرج بعتبة: فإذا كان VRF_output < stake_fraction * threshold، يُختار المدقّق عضواً في اللجنة أو مُقترِحاً للكتلة. لا يعلم المدقّق وحده أنه اختير إلا بعد أن يبث كتلته أو تصويته مرفقاً ببرهان VRF. يلغي هذا الاختيار الذاتي التشفيري الحاجة إلى انتخاب قائد علني، مما يجعل Algorand مقاومةً لهجمات حجب الخدمة الموجّهة ضد القادة المعروفين مسبقاً.

يستخدم Ouroboros Praos الخاص بـ Cardano (الإصدار المنشور حالياً) VRFs لانتخاب قادة الخانات الزمنية. في كل حقبة، تُشتق بذرة عشوائية جديدة من سلسلة الكتل. يقيّم كل مشغّل لمجمّع الحصص (SPO) ‏VRF(SK, slot || epoch_seed) لكل خانة زمنية في الحقبة. فإذا كان الخرج أدنى من عتبة تتناسب مع حصته، يصبح المشغّل قائد الخانة الزمنية ويجوز له إنتاج كتلة. يُضمَّن برهان VRF في ترويسة الكتلة، مما يتيح لأي طرف التحقق من أن SPO انتُخب بصورة مشروعة. ويمنح ذلك Cardano أماناً قابلاً للإثبات ضد الخصوم المتكيفين الذين يتعلمون جدول القادة في منتصف الحقبة.

تستخدم Ethereum‏ RANDAO (تواقيع BLS المتراكمة) بدلاً من VRFs لمنارة العشوائية. تُعد RANDAO أبسط، إذ لا تحتاج إلى بدائية تشفيرية إضافية تتجاوز BLS، لكنها عرضة لانحياز الكاشف الأخير: فقد يتنبأ مُقترِح كتلة بأن مساهمته في RANDAO ستنتج نتيجة غير مواتية، فيحجب كتلته (مقابل خسارة مكافأة الكتلة). يخفي الانتخاب القائم على VRF هوية المُنتخَب حتى يكشفها، مما يلغي هذا المسار تماماً. أما المفاضلة فهي أن VRF يضيف تعقيداً تشفيرياً (التحويل من الهاش إلى منحنى وتوليد البرهان)، في حين تعيد RANDAO استخدام البنية التحتية الحالية لـ BLS.

يوفّر Chainlink VRF العشوائية القابلة للتحقق بوصفها خدمةً للعقود الذكية. يطلب عقد مستهلك العشوائيةَ عبر دفع رموز LINK. ويحتفظ عقدة أوراكل من Chainlink بزوج مفاتيح VRF. تقيّم العقدة ECVRF(SK, seed)، حيث تُشتق seed من تجزئة الكتلة وnonce يقدمه المستخدم، ثم ترسل (beta, pi) إلى السلسلة. يتحقق عقد منسّق VRF من البرهان قبل تمرير الخرج العشوائي إلى المستهلك. ويتيح ذلك للعقود الذكية الوصول إلى عشوائية مقاومة للتلاعب من دون أن تتطلب السلسلة تنفيذ منارة VRF أصلية، وهو مفيد لسكّ NFT واليانصيب والألعاب.

يستخدم Signal Protocol‏ VXEdDSA (Verifiable X25519 EdDSA)، وهو بناء VRF فوق Curve25519. عند إنشاء المرسل توقيعاً لمفتاح تمهيدي أحادي الاستخدام، يُستخدم VRF لإنتاج قيمة nonce حتمية ولكن غير قابلة للتنبؤ انطلاقاً من الرسالة ومفتاح المرسل. ويمنع ذلك إعادة استخدام nonce، التي من شأنها كسر أمان EdDSA، مع إبقاء التواقيع قابلةً للتحقق. يتيح برهان VRF للمستلم التحقق من اشتقاق nonce بصورة صحيحة، مما يمنع المرسل من اختيار nonce خبيثة قد تتيح هجمات استعادة المفتاح. يبرهن VXEdDSA على أن VRFs أداة تشفيرية عامة تتجاوز نطاق الإجماع.

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

يوفّر اختيار VRF تحسناً أمنياً مهماً في مواجهة الخصوم المتكيفين. ففي PBFT وTendermint، تكون هوية القائد معروفة مسبقاً (وفق جدول التناوب الدائري)، مما يتيح للخصم شن هجوم DDoS على القائد التالي قبل أن يقترح كتلته. أما الاختيار القائم على VRF (في Algorand وCardano) فيُبقي هوية القائد سرية حتى بث الكتلة؛ وعندها تكون الكتلة قد اقتُرحت بالفعل، فيأتي هجوم DDoS متأخراً. ويُسمى ذلك الأمان التكيفي أو انتخاب القائد غير القابل للتنبؤ. والخاصية التشفيرية التي تتيح ذلك هي أن خرج VRF يبدو شبه عشوائي لأي طرف لا يملك المفتاح الخاص.

يتطلب تنفيذ VRFs بصورة صحيحة مراعاة عدة نقاط. يجب أن يستخدم التحويل من الهاش إلى منحنى خوارزمية موحّدة بزمن ثابت (يحدد IETF RFC 9380 أساليب قياسية لمنع تسريبات التوقيت). يجب اشتقاق قيمة VRF nonce‏ k في البرهان حتمياً من (SK, alpha) باستخدام RFC 6979؛ إذ إن إعادة استخدام k أو استخدام قيمة k عشوائية ضعيفة يسرّب المفتاح السري (وهي الثغرة نفسها الناتجة عن إعادة استخدام nonce في ECDSA). يبلغ حجم البرهان في ECVRF-P256-SHA256-TAI‏ 80 بايتاً، ويبلغ في ECVRF-ED25519-SHA512-ELL2‏ 80 بايتاً أيضاً، وكلاهما مناسب للتضمين على السلسلة. وتضمن خاصية تفرد VRF عدم وجود برهانين صالحين لنفس الزوج (SK, alpha).

تنتج VRFs مخارج شبه عشوائية مرفقة ببراهين تشفيرية على صحتها، محققةً خصائص عدم قابلية التنبؤ، وعدم قابلية الانحياز، وقابلية التحقق العلني. ويُعد ECVRF (RFC 9381) البناءَ القياسي فوق المنحنيات الإهليلجية. تستخدم Algorand الاختيار الذاتي التشفيري القائم على VRF لمقاومة الخصوم المتكيفين. ويستخدم Cardano Ouroboros Praos‏ VRFs لانتخاب قائد لكل خانة زمنية. ويوفّر Chainlink VRF العشوائية القابلة للتحقق للعقود الذكية. وتتوافق VRFs مع VDFs (التي تعالج انحياز الكاشف الأخير)، وتختلف عن RANDAO (التي تستخدم تواقيع BLS المتراكمة مع ضعف معروف يتعلق بالكاشف الأخير).