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

1 المقدمة

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

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

تم تطبيق مجال الثنائي على نطاق واسع في علم التشفير، مثل AES و GMAC و رموز QR و FRI الأصلية وبروتوكولات zk-STARK وغيرها.

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

بينياس قدم حلول مبتكرة:

1. استخدام متعددة المتغيرات متعددة الحدود بدلاً من متعددة الحدود ذات المتغير الواحد، من خلال قيمتها على "المكعب الفائق" لتمثيل المسار الحسابي بأكمله.
2. اعتبر المكعب الفائق كشكلة مربعة لتوسيع ريد-سولومون

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

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

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

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

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

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

يدعم مجال ثنائي البرج عمليات حسابية عالية الكفاءة وعملية حسابية مبسطة.

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

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

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

تصميم PIOP في بروتوكول Binius يستلهم من HyperPlonk، ويعتمد على مجموعة من آليات الفحص الأساسية:

• جيت تشيك
• التحقق من التقليب
• فحص البحث
• فحص متعدد المجموعات
• فحص المنتج
• زيرو تشيك
• SumCheck
• فحص الدفعة

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

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

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

الطرق الأساسية لبناء ومعالجة المتعددات الافتراضية في بروتوكول بينياس:

• التعبئة
• عامل الإزاحة

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

يتكون بروتوكول Lasso من ثلاثة مكونات:

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

تكييف بروتوكول Binius بروتوكول Lasso ليعمل في المجال الثنائي، حيث تم تقديم النسخة الضربية من بروتوكول Lasso.

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

تقدم ورقة Binius مخططين من التزام متعدد الحدود Brakedown بناءً على المجالات الثنائية:

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

تستخدم تقنيات مثل الالتزام متعدد الحدود في المجال الصغير والتقييم في المجال الموسع، والبناء العام في المجال الصغير، والترميز على مستوى الكتل مع رموز ريد-سولومون لبناء الالتزام متعدد الحدود لبينيوس.

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

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

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

1. PIOP القائم على GKR: يتعلق بعمليات ضرب المجال الثنائي، باستخدام بروتوكول GKR لاستبدال خوارزمية Lasso Lookup.

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

3. تحسين Sumcheck PIOP: تحسين للـ Sumcheck في النطاقات الصغيرة

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

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

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

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

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

الاتجاهات الرئيسية للتحسين:

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

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

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

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

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

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

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

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

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

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

4 ملخص

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

يعد FRI-Binius حلاً لـ FRI المتغير، حيث يمكنه إزالة تكاليف الإدراج من طبقة إثبات المجال دون التسبب في زيادة حادة في تكاليف طبقة الإثبات المجمعة.

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

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