تحليل مبادئ Binius STARKs وتأملات في تحسينها

1. المقدمة

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

الجيل الأول من تشفير STARKs بعرض 252 بت، والجيل الثاني بعرض 64 بت، والجيل الثالث بعرض 32 بت، لكن عرض 32 بت لا يزال يحتوي على مساحة هائلة من الهدر. بالمقارنة، يسمح المجال الثنائي بالتحكم المباشر في البتات، مما يجعل التشفير مضغوطًا وفعالًا دون أي هدر، وهو الجيل الرابع من STARKs.

بالمقارنة مع المجالات المحدودة التي تم البحث فيها في السنوات الأخيرة مثل Goldilocks وBabyBear وMersenne31، يمكن تتبع أبحاث المجالات الثنائية إلى الثمانينيات، وقد تم استخدامها على نطاق واسع في علم التشفير، مثل AES(F28 المجال )، GMAC(F2128 المجال )، رموز QR(F28 المجال ترميز Reed-Solomon ) وغيرها.

تستخدم Binius مجال ثنائي، مما يتطلب الاعتماد الكامل على المجال الموسع لضمان الأمان والقابلية للاستخدام. تعمل معظم حسابات Prover بكفاءة تحت المجال الأساسي، وتتطلب فحوصات النقاط العشوائية وحسابات FRI التعمق في المجال الموسع لضمان الأمان.

يستخدم Binius المتعدد المتغيرات المتعدد الحدود لتحديد القيم على "الهيكل الفائق" لتمثيل مسارات الحساب، حيث يتم اعتبار الهيكل الفائق على أنه مربع لإجراء توسيع Reed-Solomon، مما يضمن الأمان مع تحسين كبير في كفاءة الترميز وأداء الحساب.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

2. تحليل المبدأ

بينيوس: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي.

تشمل خمس تقنيات رئيسية:

1. الأساس الحسابي المبني على مجال ثنائي برج

2. تعديل تحقق من ناتج HyperPlonk والتحويل، لضمان تطابق المتغيرات والتحقق من التبديل

3. إثبات التحويل المتعدد الخطوط الجديد، تحسين كفاءة التحقق من العلاقات المتعددة الخطوط في المجالات الصغيرة

4. نسخة محسّنة من نظرية بحث Lasso، لتوفير المرونة والأمان لآلية البحث

5. خطة الالتزام متعددة الحدود الصغيرة، تحقق نظام إثبات فعال على حقل ثنائي

2.1 الحقول المحدودة: الرياضيات المستندة إلى أبراج الحقول الثنائية

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

يمكن اعتبار سلسلة مكونة من 128 بت كعنصر فريد في مجال ثنائي مكون من 128 بت، أو تحليلها إلى عنصرين من مجال 64 بت، أربعة عناصر من مجال 32 بت، 16 عنصرًا من مجال 8 بت، أو 128 عنصرًا من مجال F2. هذه المرونة لا تتطلب أي تكلفة حسابية، بل هي مجرد تحويل نوع لسلسلة البت.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثلي

2.2 PIOP: النسخة المعدلة من منتج HyperPlonk وPermutationCheck

استعانت Binius PIOP بـ HyperPlonk، واعتمدت آلية فحص أساسية للتحقق من صحة المتعددات الحدودية ومجموعات المتغيرات المتعددة، بما في ذلك GateCheck وPermutationCheck وLookupCheck وMultisetCheck وProductCheck وZeroCheck وSumCheck وBatchCheck.

بينياس قام بتحسين في 3 مجالات التالية:

• تحسين ProductCheck: تخصيص القيمة إلى 1، تبسيط عملية الفحص وتقليل التعقيد الحسابي

• معالجة مشكلة القسمة على صفر: معالجة صحيحة لحالات القسمة على صفر، والسماح بالتعميم إلى أي قيمة مضاعفة

• فحص التبديل عبر الأعمدة: يدعم فحص التبديل بين عدة أعمدة، ويعالج حالات ترتيب متعددة الحدود الأكثر تعقيدًا

2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة

بينياس بناء ومعالجة متعددات الحدود الافتراضية هي تقنية رئيسية:

• التعبئة: دمج العناصر ذات المواقع المجاورة الأصغر في القاموس لتصبح عناصر أكبر لتحسين العملية

• مشغل الإزاحة: إعادة ترتيب عناصر الكتلة بناءً على إزاحة معينة

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

2.4 PIOP: نسخة معدلة من حجة Lasso lookup

بروتوكول Lasso يسمح للجهة المثبتة بالتعهد بالمتجه a ∈ Fm وإثبات أن جميع العناصر موجودة في جدول محدد مسبقًا t ∈ Fn.

قام Binius بتكييف Lasso لعمليات حقل ثنائي، حيث تم تقديم إصدار الضرب من بروتوكول Lasso، الذي يتطلب من الطرف المُثبت والطرف المُحقق تنفيذ بروتوكول "عد الذاكرة" بشكل مشترك، من خلال الضرب في حقل ثنائي لتوليد زيادة مولد.

2.5 PCS:نسخة معدلة من Brakedown PCS

فكرة بناء BiniusPCS هي packing. يوفر نظامين من التزام متعدد الحدود Brakedown المعتمد على المجال الثنائي:

1. استخدام نموذج الشيفرة المجمعة

2. استخدام تقنية ترميز مستوى الكتلة، يدعم استخدام رموز ريد-سولومون بشكل منفصل

الخيار الثاني يبسط عملية الإثبات والتحقق، حجم الإثبات أكبر قليلاً ولكن مزايا التبسيط والتنفيذ تستحق.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

3. تحسين التفكير

3.1 PIOP القائم على GKR: ضرب المجال الثنائي القائم على GKR

تحويل "تحقق مما إذا كانت الأعداد الصحيحة 32 بت A و B تحقق A·B =? C" إلى "تحقق مما إذا كانت (gA)B =? gC صحيحة"، مع الاستعانة ببروتوكول GKR لتقليل تكلفة الالتزام بشكل كبير.

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

3.2 ZeroCheck PIOP تحسين: التوازن بين تكلفة Prover و Verifier

تقليل نقل بيانات الطرف الموثق: نقل جزء من العمل إلى الطرف المصدق، مما يقلل من كمية البيانات المرسلة من الطرف الموثق.

تقليل عدد نقاط تقييم الطرف المثبت: تعديل طريقة إرسال متعددة الحدود، وتقليل عدد نقاط التقييم.

تحسين الاستيفاء الجبري: بناء التحلل المرتب من خلال قسمة متعددة الحدود الطويلة لتحقيق تحسين الاستيفاء.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

3.3 تحسين PIOP Sumcheck: بروتوكول Sumcheck القائم على المجال الصغير

تأثير التحويل بين الجولات وعوامل التحسين: اختيار جولة التحويل t يؤثر على الأداء، وتصل عوامل تحسين النقطة المثلى إلى أقصى قيمة.

تأثير حجم المجال الأساسي على الأداء: يصبح ميزة خوارزمية التحسين أكثر وضوحًا بالنسبة للمجال الأساسي الأصغر ( مثل GF[2]).

تحسين عائدات خوارزمية كاراتسوبا: تحسين كبير في أداء Sumcheck القائم على المجال الصغير، الخوارزمية 4 أكثر كفاءة بخمسة أضعاف من الخوارزمية 3.

تحسين كفاءة الذاكرة: متطلبات الذاكرة للخوارزمية 4 O(d·t)، والخوارزمية 3 O(2d·t)، مناسبة للبيئات ذات الموارد المحدودة.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

3.4 PCS تحسين:FRI-Binius تقليل حجم إثبات Binius

تحقق FRI-Binius آلية طي FRI في المجال الثنائي، مما يحقق 4 ابتكارات:

• متعددة الحدود المسطحة
• كثيرة الحدود لاختفاء الفضاءات الفرعية
• حزمة الأساس الجبري
• تبادل الحلقة SumCheck

بفضل FRI-Binius، يمكن تقليل حجم إثبات Binius بمقدار درجة واحدة، مما يقترب من الأنظمة المتقدمة.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

4. ملخص

لقد أزال Binius أساسًا عنق الزجاجة في التزام Prover، والآن العنق الزجاجة الجديد يتعلق ببروتوكول Sumcheck. خطة FRI-Binius هي نسخة معدلة من FRI ويمكنها إزالة تكاليف التضمين من طبقة إثبات المجال.

فريق Irreducible يقوم بتطوير طبقة تكرارية، بالتعاون مع Polygon لبناء zkVM قائم على Binius. JoltzkVM ينتقل من Lasso إلى Binius لتحسين أداء التكرار. Ingonyama يحقق إصدار FPGA من Binius.

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل