أحد الأسباب الرئيسية لعدم كفاءة STARKs هو أن معظم القيم في البرنامج الفعلي صغيرة نسبيًا، ولكن لضمان أمان الإثبات القائم على شجرة ميركل، عندما يتم توسيع البيانات باستخدام ترميز ريد-سولومون، فإن العديد من القيم الزائدة ستشغل المجال بالكامل. لحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تتميز الجيل الأول من تشفير STARKs بعرض بت يبلغ 252 بت، والجيل الثاني بعرض 64 بت، والجيل الثالث بعرض 32 بت، ولكن لا يزال هناك الكثير من المساحة المهدرة في عرض 32 بت. بالمقارنة، يسمح المجال الثنائي بالعمليات المباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا دون أي مساحة مهدرة، وهو ما يُعرف بالجيل الرابع من STARKs.
عندما يتم استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. وتعتمد المجالات الثنائية المستخدمة من قبل Binius بالكامل على توسيع المجال لضمان أمانها وقابليتها للاستخدام الفعلي. معظم الحدود المتضمنة في حسابات Prover لا تحتاج إلى الدخول في توسيع المجال، بل يمكنها العمل فقط في المجال الأساسي، مما يحقق كفاءة عالية في المجالات الصغيرة. ومع ذلك، لا يزال يتعين على فحص النقاط العشوائية وحساب FRI التعمق في مجال توسيع أكبر لضمان الأمان المطلوب.
عند بناء نظام إثبات يعتمد على المجال الثنائي، يوجد مشكلتان عمليتان: عند حساب تمثيل المسار في STARKs، يجب أن تكون حجم المجال المستخدم أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة ميركل في STARKs، يجب إجراء ترميز ريد-سولومون، ويجب أن تكون حجم المجال المستخدم أكبر من الحجم بعد التوسيع الترميزي.
اقترح Binius حلاً مبتكراً يعالج هذين الأمرين بشكل منفصل، ويحقق ذلك من خلال تمثيل نفس البيانات بطريقتين مختلفتين: أولاً، باستخدام متعددات الحدود متعددة المتغيرات (وبالتحديد متعددة الحدود متعددة الخطوط) بدلاً من متعددة الحدود أحادية المتغير، من خلال قيمها على "المكعبات الفائقة" (hypercubes) لتمثيل المسار الحسابي بالكامل؛ ثانياً، نظراً لأن طول كل بعد من أبعاد المكعبات الفائقة هو 2، فإنه لا يمكن إجراء توسيع Reed-Solomon القياسي كما في STARKs، ولكن يمكن اعتبار المكعب الفائق مربعاً (square)، بناءً على هذا المربع يتم إجراء توسيع Reed-Solomon. هذه الطريقة تضمن الأمان في الوقت الذي تعزز فيه بشكل كبير كفاءة الترميز وأداء الحساب.
إثبات الOracle التفاعلي المتعدد الحدود القائم على نظرية المعلومات (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP)
مخطط الالتزام المتعدد الحدود (Polynomial Commitment Scheme, PCS)
Binius: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي. على وجه التحديد، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وأمانه:
الحساب على أساس مجال ثنائي برجي
النسخة المعدلة من فحص ضرب HyperPlonk والاستبدال
نظرية التحول المتعدد الخطوط الجديدة
النسخة المحسنة من إثبات البحث Lasso
خطة الالتزام متعدد الحدود الصغير
2.1 النطاقات المحدودة: حسابات قائمة على أبراج الحقول الثنائية
حقل ثنائي الشكل هو المفتاح لتحقيق حسابات سريعة قابلة للتحقق، ويرجع ذلك بشكل أساسي إلى جانبين: الحسابات الفعالة والتعويض الفعال. يدعم الحقل الثنائي بشكل جوهري عمليات حسابية فعالة للغاية، مما يجعله خيارًا مثاليًا للتطبيقات التشفيرية التي تتطلب حساسية عالية للأداء. بالإضافة إلى ذلك، يدعم هيكل الحقل الثنائي عملية تعويض مبسطة، مما يعني أن العمليات المنفذة على الحقل الثنائي يمكن تمثيلها بشكل جبرية مضغوط وسهل التحقق.
في مجال الأعداد الأولية Fp، تشمل طرق الاختزال الشائعة اختزال باركيت، اختزال مونتغومري، بالإضافة إلى طرق الاختزال الخاصة لبعض الحقول المحدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال المستخدمة عادةً الاختزال الخاص (مثل المستخدم في AES)، اختزال مونتغومري (كما هو مستخدم في POLYVAL) والاختزال التكراري (مثل Tower).
المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، كما أن عمليات التربيع في المجال الثنائي فعالة جداً، لأنها تتبع قاعدة التبسيط (X + Y )2 = X2 + Y 2.
2.2 PIOP: النسخة المعدلة من منتج HyperPlonk وPermutationCheck
استوحى تصميم PIOP في بروتوكول Binius من HyperPlonk ، حيث يعتمد على مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمجموعات متعددة المتغيرات. تشمل هذه الفحوصات الأساسية:
فحص البوابة
التقليب التحقق
فحص البحث
MultisetCheck
فحص المنتج
زيرو تشيك
SumCheck
فحص الدفعة
قدمت Binius التحسينات التالية مقارنة بـ HyperPlonk:
تحسين ProductCheck
معالجة مشكلة القسمة على صفر
فحص التبديل عبر الأعمدة
2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة
في بروتوكول Binius، يعتبر بناء ومعالجة كثيرات الحدود الافتراضية من التقنيات الأساسية، حيث يمكنها بشكل فعال توليد والتعامل مع كثيرات الحدود المستمدة من مقبض الإدخال أو كثيرات الحدود الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان:
التعبئة
مشغل الإزاحة
2.4 PIOP：نسخة معدلة من حجة البحث Lasso
بروتوكول Lasso يسمح للجهة المثبتة بالتعهد بمتجه a ∈ Fm، وإثبات أن جميع عناصره موجودة في جدول محدد مسبقًا t ∈ Fn. يتكون بروتوكول Lasso من ثلاثة مكونات:
التجريد متعدد الحدود الافتراضي للجدول الكبير
بحث عن الجدول الصغير
فحص متعدد التجمعات
تتكيف بروتوكول Binius مع عمليات المجال الثنائي باستخدام بروتوكول Lasso ، مما يقدم نسخة الضرب من بروتوكول Lasso.
2.5 PCS：نسخة معدلة من Brakedown PCS
الهدف الرئيسي من بناء BiniusPCS هو packing. يوفر بحث Binius نوعين من خطط الالتزام متعددة الحدود القائمة على المجال الثنائي:
استخدم الكود المدمج للتجسيد
استخدام تقنية ترميز المستوى الكتلي، يدعم استخدام رموز ريد-سولومون بشكل منفصل
تستخدم التزامات Binius المتعددة بشكل رئيسي التقنيات التالية:
الالتزامات متعددة الحدود على المجال الصغير وتقييم المجال الموسع
لزيادة تحسين أداء بروتوكول Binius، يقترح هذا المقال أربعة نقاط تحسين رئيسية:
PIOP القائم على GKR: لعمليات الضرب في مجال ثنائي
تحسين ZeroCheck PIOP: موازنة تكاليف الحساب بين Prover و Verifier
تحسين PIOP Sumcheck: تحسين لـ Sumcheck في المجالات الصغيرة
تحسين PCS: من خلال تحسين FRI-Binius
3.1 PIOP المعتمد على GKR: الضرب في مجال ثنائي المعتمد على GKR
خوارزمية ضرب الأعداد الصحيحة المعتمدة على GKR، من خلال تحويل "التحقق مما إذا كانت الأعداد الصحيحة A و B بحجم 32 بت تحقق A·B =؟ C" إلى "التحقق مما إذا كانت (gA)B =؟ gC صحيحة"، مما يقلل بشكل كبير من تكلفة الالتزام بفضل بروتوكول GKR.
3.2 ZeroCheck PIOP تحسين: توازن تكاليف Prover و Verifier
تقدم الورقة "Some Improvements for the PIOP for ZeroCheck" مجموعة من الحلول التحسينية لتوزيع عبء العمل بين الطرف المثبت (P) والطرف المصدق (V) ، مع تقديم عدة خيارات تحسين للتوازن بين التكاليف. تشمل التحسينات الرئيسية:
3.4 PCS تحسين: FRI-Binius يقلل من حجم إثبات Binius
الورقة البحثية «إثباتات متعددة اللوغاريتمات للمتعددات على أبراج ثنائية»، المختصرة بـ FRI-Binius، تحقق آلية طي FRI في الحقل الثنائي، مما يجلب 4 جوانب من الابتكار:
متعددة الحدود المسطحة
*多项式 اختفاء الفضاء الفرعي
حزمة الأساس الجبري
تبادل حلقات SumCheck
بفضل FRI-Binius، يمكن تقليل حجم إثبات Binius بمقدار درجة واحدة.
Binius هو "حل التصميم التعاوني باستخدام الأجهزة والبرامج وبروتوكول Sumcheck المعجل في FPGA"، ويمكنه إثبات سريع بمعدل استخدام ذاكرة منخفض للغاية. لقد تمت إزالة الاختناق الناتج عن الالتزام Prover تمامًا تقريبًا في Binius، والاختناق الجديد يكمن في بروتوكول Sumcheck، حيث يمكن حل العديد من مشكلات تقييم متعددات الحدود وضرب النطاق بكفاءة باستخدام أجهزة متخصصة.
يوفر مخطط FRI-Binius ، وهو نوع مختلف من FRI ، خيارا جذابا للغاية للتخلص من النفقات العامة المضمنة من طبقة التصديق بالمجال دون التسبب في ارتفاع تكلفة طبقة التصديق الإجمالية. حاليا ، يعمل فريق Unreductible على طبقته المتكررة وأعلن عن تعاون مع فريق Polygon لبناء zkVM قائم على Binius. ينتقل JoltzkVM من Lasso إلى Binius لتحسين أدائها المتكرر. يقوم فريق Ingonyama بتنفيذ إصدار FPGA من Binius.
قد تحتوي هذه الصفحة على محتوى من جهات خارجية، يتم تقديمه لأغراض إعلامية فقط (وليس كإقرارات/ضمانات)، ولا ينبغي اعتباره موافقة على آرائه من قبل Gate، ولا بمثابة نصيحة مالية أو مهنية. انظر إلى إخلاء المسؤولية للحصول على التفاصيل.
تسجيلات الإعجاب 26
أعجبني
26
8
إعادة النشر
مشاركة
تعليق
0/400
AirdropF5Bro
· منذ 8 س
أوه هوه، هذه هي صورة ستارك نت.
شاهد النسخة الأصليةرد0
¯\_(ツ)_/¯
· 08-12 16:41
هذا التحسين قوي جداً، من 252 إلى النظام الثنائي
شاهد النسخة الأصليةرد0
SerumSquirter
· 08-10 20:16
تزداد الكفاءة وتصبح المجالات أصغر
شاهد النسخة الأصليةرد0
GateUser-afe07a92
· 08-10 09:35
ممل جداً التالي
شاهد النسخة الأصليةرد0
ForkTongue
· 08-10 09:20
كتابة جيدة جدًا لكن لم أفهمها بشكل احترافي...
شاهد النسخة الأصليةرد0
NullWhisperer
· 08-10 09:16
همم... يبدو أن تحسين الحقل الثنائي أنيق من الناحية النظرية، لكن دعنا نتحدث عن تلك الحالات الحدية في عمليات الحقل الممتد...
شاهد النسخة الأصليةرد0
HalfBuddhaMoney
· 08-10 09:15
لم أترجم مجال العرض الصفري منذ فترة طويلة، هذه المرة سأوضح بشكل جيد.
شاهد النسخة الأصليةرد0
NonFungibleDegen
· 08-10 09:08
سر هذا الشيء القاسي يعتمد على... الثنائيات = رقم يرتفع، أخيراً بعض الألفا الحقيقي وليس هذا التظاهر بشجرة ميركل
تحليل مبادئ Binius STARKs: تحسين المجال الثنائي والتعهدات متعددة الحدود الفعالة
تحليل مبادئ Binius STARKs وأفكار تحسينها
1 المقدمة
أحد الأسباب الرئيسية لعدم كفاءة STARKs هو أن معظم القيم في البرنامج الفعلي صغيرة نسبيًا، ولكن لضمان أمان الإثبات القائم على شجرة ميركل، عندما يتم توسيع البيانات باستخدام ترميز ريد-سولومون، فإن العديد من القيم الزائدة ستشغل المجال بالكامل. لحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تتميز الجيل الأول من تشفير STARKs بعرض بت يبلغ 252 بت، والجيل الثاني بعرض 64 بت، والجيل الثالث بعرض 32 بت، ولكن لا يزال هناك الكثير من المساحة المهدرة في عرض 32 بت. بالمقارنة، يسمح المجال الثنائي بالعمليات المباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا دون أي مساحة مهدرة، وهو ما يُعرف بالجيل الرابع من STARKs.
عندما يتم استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. وتعتمد المجالات الثنائية المستخدمة من قبل Binius بالكامل على توسيع المجال لضمان أمانها وقابليتها للاستخدام الفعلي. معظم الحدود المتضمنة في حسابات Prover لا تحتاج إلى الدخول في توسيع المجال، بل يمكنها العمل فقط في المجال الأساسي، مما يحقق كفاءة عالية في المجالات الصغيرة. ومع ذلك، لا يزال يتعين على فحص النقاط العشوائية وحساب FRI التعمق في مجال توسيع أكبر لضمان الأمان المطلوب.
عند بناء نظام إثبات يعتمد على المجال الثنائي، يوجد مشكلتان عمليتان: عند حساب تمثيل المسار في STARKs، يجب أن تكون حجم المجال المستخدم أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة ميركل في STARKs، يجب إجراء ترميز ريد-سولومون، ويجب أن تكون حجم المجال المستخدم أكبر من الحجم بعد التوسيع الترميزي.
اقترح Binius حلاً مبتكراً يعالج هذين الأمرين بشكل منفصل، ويحقق ذلك من خلال تمثيل نفس البيانات بطريقتين مختلفتين: أولاً، باستخدام متعددات الحدود متعددة المتغيرات (وبالتحديد متعددة الحدود متعددة الخطوط) بدلاً من متعددة الحدود أحادية المتغير، من خلال قيمها على "المكعبات الفائقة" (hypercubes) لتمثيل المسار الحسابي بالكامل؛ ثانياً، نظراً لأن طول كل بعد من أبعاد المكعبات الفائقة هو 2، فإنه لا يمكن إجراء توسيع Reed-Solomon القياسي كما في STARKs، ولكن يمكن اعتبار المكعب الفائق مربعاً (square)، بناءً على هذا المربع يتم إجراء توسيع Reed-Solomon. هذه الطريقة تضمن الأمان في الوقت الذي تعزز فيه بشكل كبير كفاءة الترميز وأداء الحساب.
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
2 تحليل المبدأ
تتكون معظم أنظمة SNARKs الحالية عادة من جزئين:
Binius: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي. على وجه التحديد، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وأمانه:
2.1 النطاقات المحدودة: حسابات قائمة على أبراج الحقول الثنائية
حقل ثنائي الشكل هو المفتاح لتحقيق حسابات سريعة قابلة للتحقق، ويرجع ذلك بشكل أساسي إلى جانبين: الحسابات الفعالة والتعويض الفعال. يدعم الحقل الثنائي بشكل جوهري عمليات حسابية فعالة للغاية، مما يجعله خيارًا مثاليًا للتطبيقات التشفيرية التي تتطلب حساسية عالية للأداء. بالإضافة إلى ذلك، يدعم هيكل الحقل الثنائي عملية تعويض مبسطة، مما يعني أن العمليات المنفذة على الحقل الثنائي يمكن تمثيلها بشكل جبرية مضغوط وسهل التحقق.
في مجال الأعداد الأولية Fp، تشمل طرق الاختزال الشائعة اختزال باركيت، اختزال مونتغومري، بالإضافة إلى طرق الاختزال الخاصة لبعض الحقول المحدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال المستخدمة عادةً الاختزال الخاص (مثل المستخدم في AES)، اختزال مونتغومري (كما هو مستخدم في POLYVAL) والاختزال التكراري (مثل Tower).
المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، كما أن عمليات التربيع في المجال الثنائي فعالة جداً، لأنها تتبع قاعدة التبسيط (X + Y )2 = X2 + Y 2.
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثلي
2.2 PIOP: النسخة المعدلة من منتج HyperPlonk وPermutationCheck
استوحى تصميم PIOP في بروتوكول Binius من HyperPlonk ، حيث يعتمد على مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمجموعات متعددة المتغيرات. تشمل هذه الفحوصات الأساسية:
قدمت Binius التحسينات التالية مقارنة بـ HyperPlonk:
2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة
في بروتوكول Binius، يعتبر بناء ومعالجة كثيرات الحدود الافتراضية من التقنيات الأساسية، حيث يمكنها بشكل فعال توليد والتعامل مع كثيرات الحدود المستمدة من مقبض الإدخال أو كثيرات الحدود الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان:
2.4 PIOP：نسخة معدلة من حجة البحث Lasso
بروتوكول Lasso يسمح للجهة المثبتة بالتعهد بمتجه a ∈ Fm، وإثبات أن جميع عناصره موجودة في جدول محدد مسبقًا t ∈ Fn. يتكون بروتوكول Lasso من ثلاثة مكونات:
تتكيف بروتوكول Binius مع عمليات المجال الثنائي باستخدام بروتوكول Lasso ، مما يقدم نسخة الضرب من بروتوكول Lasso.
2.5 PCS：نسخة معدلة من Brakedown PCS
الهدف الرئيسي من بناء BiniusPCS هو packing. يوفر بحث Binius نوعين من خطط الالتزام متعددة الحدود القائمة على المجال الثنائي:
تستخدم التزامات Binius المتعددة بشكل رئيسي التقنيات التالية:
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
3 تحسين التفكير
لزيادة تحسين أداء بروتوكول Binius، يقترح هذا المقال أربعة نقاط تحسين رئيسية:
3.1 PIOP المعتمد على GKR: الضرب في مجال ثنائي المعتمد على GKR
خوارزمية ضرب الأعداد الصحيحة المعتمدة على GKR، من خلال تحويل "التحقق مما إذا كانت الأعداد الصحيحة A و B بحجم 32 بت تحقق A·B =؟ C" إلى "التحقق مما إذا كانت (gA)B =؟ gC صحيحة"، مما يقلل بشكل كبير من تكلفة الالتزام بفضل بروتوكول GKR.
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
3.2 ZeroCheck PIOP تحسين: توازن تكاليف Prover و Verifier
تقدم الورقة "Some Improvements for the PIOP for ZeroCheck" مجموعة من الحلول التحسينية لتوزيع عبء العمل بين الطرف المثبت (P) والطرف المصدق (V) ، مع تقديم عدة خيارات تحسين للتوازن بين التكاليف. تشمل التحسينات الرئيسية:
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
3.3 تحسين Sumcheck PIOP: بروتوكول Sumcheck القائم على المجال الصغير
Ingonyama قدمت في عام 2024 اقتراحًا لتحسين بروتوكول Sumcheck القائم على المجالات الصغيرة ، وقامت بفتح مصدر رمز التنفيذ. تشمل التحسينات الرئيسية:
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
3.4 PCS تحسين: FRI-Binius يقلل من حجم إثبات Binius
الورقة البحثية «إثباتات متعددة اللوغاريتمات للمتعددات على أبراج ثنائية»، المختصرة بـ FRI-Binius، تحقق آلية طي FRI في الحقل الثنائي، مما يجلب 4 جوانب من الابتكار:
بفضل FRI-Binius، يمكن تقليل حجم إثبات Binius بمقدار درجة واحدة.
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل
4 ملخص
Binius هو "حل التصميم التعاوني باستخدام الأجهزة والبرامج وبروتوكول Sumcheck المعجل في FPGA"، ويمكنه إثبات سريع بمعدل استخدام ذاكرة منخفض للغاية. لقد تمت إزالة الاختناق الناتج عن الالتزام Prover تمامًا تقريبًا في Binius، والاختناق الجديد يكمن في بروتوكول Sumcheck، حيث يمكن حل العديد من مشكلات تقييم متعددات الحدود وضرب النطاق بكفاءة باستخدام أجهزة متخصصة.
يوفر مخطط FRI-Binius ، وهو نوع مختلف من FRI ، خيارا جذابا للغاية للتخلص من النفقات العامة المضمنة من طبقة التصديق بالمجال دون التسبب في ارتفاع تكلفة طبقة التصديق الإجمالية. حاليا ، يعمل فريق Unreductible على طبقته المتكررة وأعلن عن تعاون مع فريق Polygon لبناء zkVM قائم على Binius. ينتقل JoltzkVM من Lasso إلى Binius لتحسين أدائها المتكرر. يقوم فريق Ingonyama بتنفيذ إصدار FPGA من Binius.
! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل