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

1. المقدمة

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

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

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

قدمت Binius حلاً مبتكرًا: أولاً، باستخدام متعدد المتغيرات (بشكل محدد متعدد الحدود متعدد الخطوط) بدلاً من متعدد الحدود أحادي المتغير، من خلال قيمته على "المكعبات الفائقة" (hypercubes) لتمثيل المسار الحسابي بالكامل؛ ثانيًا، نظرًا لأن طول كل بُعد من أبعاد المكعب الفائق هو 2، فإنه لا يمكن توسيع Reed-Solomon القياسي مثل STARKs، ولكن يمكن اعتبار المكعب الفائق بمثابة مربع (square)، ويتم توسيع Reed-Solomon بناءً على هذا المربع.

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

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

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

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

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

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

• حساب فعال: المجال الثنائي يدعم بشكل أساسي عمليات حسابية فعالة للغاية
• الحسابية الفعالة: هيكل المجال الثنائي يدعم عملية حسابية مبسطة
• التمثيل القياسي: تحتوي عناصر المجال الثنائي على طريقة تمثيل فريدة ومباشرة.

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

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

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

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

آلية الفحص الأساسية لـ Binius PIOP:

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

تحسينات Binius على HyperPlonk:

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

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

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

• التعبئة: تحسين العمليات من خلال تعبئة العناصر المجاورة
• عامل الإزاحة: إعادة ترتيب عناصر الكتلة

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

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

مكونات بروتوكول Lasso:

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

تعديل Binius على Lasso:

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

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

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

خياران من خطط التزام كثيرات الحدود المعتمدة على المجالات الثنائية:

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

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

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

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

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

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

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

مقارنةً بمزايا خطة Binius lookup:

• فقط تعهد مساعد واحد
• تقليل تكلفة Sumchecks

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

طرق التحسين:

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

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

نقاط رئيسية:

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

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

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

FRI-Binius أربعة ابتكارات:

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

عملية FRI-Binius PCS:

• مرحلة الالتزام
• مرحلة التقييم

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

4. ملخص

القيمة المقترحة لـ Binius:

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

محلول FRI-Binius:

• إزالة تكاليف الإدماج من طبقة إثبات المجال
• لن يؤدي إلى زيادة حادة في تكلفة طبقة إثبات التجميع

التقدم الحالي:

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

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

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