تحليل Binius STARKs وتحسينه

1. المقدمة

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

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

تستخدم Binius تقنيات مثل حسابات مُحسّنة من HyperPlonk، وفحص المنتجات والتباديل، والتعهدات المتعددة الحقول، القائمة على النطاق الثنائي البرجي، لتعزيز الكفاءة من جميع الزوايا.

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

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

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

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

2.1 المعالجة الرياضية على أساس مجال ثنائي العمود

يدعم مجال ثنائي البرج عمليات حسابية فعالة وعملية حسابية مبسطة. يمكن أن يتم توجيه عناصر المجال الثنائي مباشرة إلى سلسلة من k بت، مما يوفر سهولة التوجيه بواحد إلى واحد.

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

2.2 نسخة معدلة من فحص حاصل ضرب HyperPlonk والتبديل

استفادت Binius من آلية التحقق الأساسية لـ HyperPlonk، بما في ذلك GateCheck و PermutationCheck و LookupCheck، وقد قامت بتحسينات في الجوانب التالية:

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

2.3 نظرية التحويل المتعدد الخطوط الجديدة

أدخلت Binius طريقتين رئيسيتين هما Packing وموحدات التبديل لبناء ومعالجة متعددة الحدود الافتراضية.

2.4 نسخة معدلة من نظرية البحث Lasso

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

2.5 الالتزام متعدد الحدود الصغير

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

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

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

3.1 PIOP المستندة إلى GKR

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

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

3.2 تحسين ZeroCheck PIOP

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

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

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

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

قدم إنغونياما اقتراحًا لتحسين بروتوكول Sumcheck القائم على النطاقات الصغيرة، مع التركيز على اختيار جولة التبديل t.

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

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

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

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

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

4. ملخص

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

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

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