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

1 المقدمة

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

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

تم استخدام المجال الثنائي على نطاق واسع في علم التشفير ، ومن الأمثلة النموذجية:

• معيار التشفير المتقدم ( AES ) ، بناءً على مجال F28
• Galois رمز التحقق ( GMAC ) ، يعتمد على مجال F2128
• رمز الاستجابة السريعة، استخدام ترميز ريد-سولومون القائم على F28
• بروتوكول FRI الأصلي و zk-STARK ، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى النهائيات في SHA-3

عند استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. المجال الثنائي المستخدم من قبل Binius يعتمد بالكامل على توسيع المجال لضمان أمانه وقابليته للاستخدام العملي.

قدمت Binius حلاً مبتكرًا:

• استخدم المتعدد المتغيرات (بالتحديد المتعدد الخطي) كبديل للمتعدد المتغير الواحد، من خلال قيمته على "الهيكل الفائق" لتمثيل المسار الكامل للحساب.
• اعتبر المكعب الفائق مربعًا، وقم بتوسيع Reed-Solomon بناءً على هذا المربع

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

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

Binius = HyperPlonk PIOP + Brakedown PCS + المجال الثنائي

Binius يتضمن خمس تقنيات رئيسية:

1. الحسابية المستندة إلى مجال ثنائي البرج
2. نسخة معدلة من فحص المنتج والاستبدال لـ HyperPlonk
3. نظرية التحويل المتعدد الخطوط الجديدة
4. نسخة محسنة من نظرية بحث Lasso
5. خطة الالتزام متعددة الحدود في المجال الصغير

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

مزايا مجال ثنائي البرج:

• حساب فعال: المجال الثنائي يدعم في جوهره عمليات حسابية فعالة للغاية
• العمليات الحسابية الفعالة: هيكل المجال الثنائي يدعم عمليات حسابية مبسطة
• تمثيل مرن: يمكن تفسير نفس السلسلة بطرق متعددة في سياق المجال الثنائي
• لا حاجة للتقليص: لا حاجة لإدخال النقل في العمليات الحسابية في الحقل الثنائي سواء في الجمع أو الضرب
• العمليات المربعة الفعالة: (X + Y)2 = X2 + Y2

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

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

آلية الفحص الأساسية:

1. فحص البوابة
2. التقليب التحقق
3. فحص البحث
4. MultisetCheck
5. فحص المنتج
6. زيرو تشيك
7. SumCheck
8. فحص الدفعة

مقارنةً مع تحسينات HyperPlonk:

• تحسين ProductCheck
• معالجة مسألة القسمة على الصفر
• تحقق من التبديل عبر الأعمدة

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

الطريقة الأساسية:

• التعبئة: تحسين العملية عن طريق تجميع العناصر الأصغر الموجودة في المواقع المجاورة في الترتيب القاموسي في عناصر أكبر.
• عامل الإزاحة: إعادة ترتيب عناصر الكتلة بناءً على إزاحة معينة.

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

2.4 PIOP: النسخة المعدلة من حجة بحث Lasso

مزايا بروتوكول Lasso:

• إثبات فعال: بالنسبة لعدد m من عمليات البحث في جدول بحجم n، يكفي الالتزام بـ m+n من عناصر المجال.
• لا حاجة لالتزام جدول كبير: إذا كان الجدول t هيكلية، فلا حاجة للاحتفاظ بها، يمكن معالجة الجداول الكبيرة جداً

تكوين بروتوكول Lasso:

• التجريد الافتراضي للحدود المتعددة الكبيرة
• البحث عن الجدول الصغير
• فحص المجموعات المتعددة

تعديل Binius على Lasso:

• إدخال نسخة الضرب من بروتوكول Lasso
• تتطلب إثبات الطرف التزامًا بمتجه عد قراءات غير صفري في كل مكان

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

الفكرة الأساسية: packing

الخياران:

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

التقنية الرئيسية:

• الالتزام متعدد الحدود في المجال الصغير وتقييم المجال الموسع
• بناء صغيرة عامة
• الترميز الكتلي ورمز ريد-سولومون

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

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

أربعة نقاط تحسين رئيسية:

1. PIOP المعتمد على GKR: العمليات الحسابية الضربية في المجال الثنائي
2. تحسين ZeroCheck PIOP: موازنة تكاليف حساب Prover و Verifier
3. تحسين PIOP Sumcheck: بروتوكول Sumcheck القائم على المجال الصغير
4. تحسين PCS: FRI-Binius يقلل من حجم إثبات Binius

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

الفكرة الأساسية:

"تحقق مما إذا كان العددين الصحيحين A و B اللذين يبلغ كل منهما 32 بت يحققان A·B =? C" تحويل إلى
"التحقق من (gA)B =? gC هل هو صحيح"

الميزات:

• تحتاج فقط إلى التزام مساعد
• تقليل نفقات Sumchecks

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

3.2 تحسين ZeroCheck PIOP

اتجاه التحسين:

• تقليل نقل البيانات من جهة الإثبات
• تقليل عدد نقاط تقييم الطرف المدلل
• تحسين الاستيفاء الجبري

3.3 فحص المجموع تحسين PIOP

تحسين النقاط الرئيسية:

• اختيار تبديل الجولات
• تأثير حجم المجال على الأداء
• فوائد تحسين خوارزمية كاراتسوبا
• تحسين كفاءة الذاكرة

النتائج المحددة:

• في حالة كون حقل الأساس هو GF[2]، فإن أداء الخوارزمية 4 يتفوق على الخوارزمية البسيطة بنحو 30 مرة.
• يحتاج الخوارزم 4 إلى 0.26 ميغابايت فقط من الذاكرة، بينما يحتاج الخوارزم 3 إلى 67 ميغابايت.

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

تحسين ### 3.4 قطعة: FRI-Binius

أربع نقاط ابتكارية:

1. متعددة الحدود المسطحة
2. متعددة الحدود لاختفاء الفضاء الفرعي
3. تجميع الأساس الجبري
4. تبادل الحلقة SumCheck

الفعالية: خفض حجم إثبات Binius بمقدار درجة واحدة

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

4 ملخص

مزايا Binius:

• يمكن استخدام أقل مجال من القوة الثانية كـ witnesses
• انخفاض استهلاك الذاكرة، إثبات سريع
• تمت إزالة عنق الزجاجة في التزام Prover بالكامل تقريبًا

محلول FRI-Binius: إزالة تكاليف الإدماج من طبقة إثبات المجال دون التسبب في زيادة كبيرة في تكاليف طبقة الإثبات المجمعة

آخر التقدم:

• فريق Irreducible يقوم بتطوير طبقته التكرارية، ويتعاون مع فريق Polygon لبناء zkVM القائم على Binius
• JoltzkVM يتحول من Lasso إلى Binius لتحسين أدائه التكراري
• فريق إنغونياما يعمل على تنفيذ نسخة FPGA من بينوس

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