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

1. المقدمة

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

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

تستخدم الحقول الثنائية على نطاق واسع في علم التشفير، مثل AES(F28)، GMAC(F2128)، ورموز QR(F28) وغيرها. عندما يتم استخدام حقول أصغر، تصبح عمليات توسيع الحقول أكثر أهمية لضمان الأمان. تعتمد الحقول الثنائية المستخدمة من قبل Binius تمامًا على توسيع الحقول لضمان الأمان والقابلية للاستخدام. تعمل معظم حسابات Prover تحت الحقل الأساسي، بكفاءة؛ تحتاج فحوصات النقاط العشوائية وحسابات FRI إلى التعمق في توسيع حقل أكبر لضمان الأمان.

حلول Binius المبتكرة:

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

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

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

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

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

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

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

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

• حساب فعال: المجال الثنائي يدعم عمليات حسابية فعالة
• الحساب الفعال: هيكل المجال الثنائي يدعم تبسيط عملية الحساب
• الاستفادة الكاملة من الخصائص الهرمية من خلال الهيكل البرجي

سلسلة مكونة من 128 حرف يمكن تفسيرها بشكل مرن:

• عنصر فريد في حقل ثنائي 128 بت
• عنصرين من مجال البرج 64 بت
• أربعة عناصر من مجال البرج 32 بت
• 16 عنصر من مجال البرج 8 بت
• 128 عنصر من مجال F2

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

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

آلية الفحص الأساسية لبينيوس:

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

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

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

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

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

• التعبئة: دمج العناصر الصغيرة المجاورة في عناصر أكبر
• مشغل التحويل: إعادة ترتيب العناصر داخل الكتلة

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

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

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

• كفاءة الإثبات العالية: تعهد m+n من عناصر المجال
• لا حاجة لالتزام الجدول الكبير: يمكن معالجة الجداول الكبيرة جدًا

Binius قدمت بروتوكول Lasso النسخة المضاعفة:

• توليد "عداد الذاكرة" المتزايد من خلال ضرب مجالات ثنائية
• تؤكد الجهة المصدقة التزامها بعدم وجود صفر في متجه عد القراءات لضمان الأمان

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

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

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

خياران:

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

التعهدات متعددة الحدود في الحقول الصغيرة وتقييم الحقول الموسعة:

• الالتزام في المجال الصغير K على
• تقييم في نطاق التوسع الأكبر L/K

تشفير الكتل ورمز ريد-سولومون:

• السماح لنطاق صغير ( مثل F2) متعدد الحدود باستخدام أبجدية كبيرة ( مثل F216) رموز ريد-سولومون التزام فعال

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

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

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

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

قم بتحويل "تحقق A·B =? C" إلى "تحقق (gA)B =? gC"

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

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

طرق التحسين:

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

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

تحسين النقاط:

• تغيير اختيار الجولة t
• تأثير حجم المجال
• تحسين خوارزمية كاراتسوبا
• تحسين كفاءة الذاكرة

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

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

أربع ابتكارات:

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

يمكن لـ FRI-Binius تقليل حجم إثبات Binius بمقدار مرتبة واحدة.

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

4. ملخص

مزايا Binius:

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

الاختناق الجديد: بروتوكول Sumcheck

• يمكن استخدام الأجهزة الخاصة لحل المشكلة بكفاءة

الجمعة بينيوس:

• إزالة تكلفة الإدماج في طبقة إثبات المجال
• لا تسبب زيادة كبيرة في تكلفة طبقة إثبات التجميع

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

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

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