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

1. المقدمة

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

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

بالمقارنة مع Goldilocks و BabyBear و Mersenne31 وغيرها من الاكتشافات الجديدة في السنوات الأخيرة في الحقول المحدودة، فإن أبحاث الحقول الثنائية تعود إلى الثمانينات من القرن الماضي. في الوقت الحالي، أصبحت الحقول الثنائية مستخدمة على نطاق واسع في علم التشفير، ومن الأمثلة النموذجية على ذلك:

• معيار التشفير المتقدم (AES)، مبني على مجال F28؛

• Galois رمز التحقق من الرسالة ( GMAC ) ، يعتمد على مجال F2128 ؛

• رمز الاستجابة السريعة، يستخدم تشفير ريد-سولومون القائم على F28؛

• بروتوكول FRI الأصلي و zk-STARK ، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى المرحلة النهائية من SHA-3 ، والتي تستند إلى مجال F28 ، وهي خوارزمية تجزئة ملائمة للغاية للتكرار.

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

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

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

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

عادة ما يتكون بناء معظم أنظمة SNARKs الحالية من قسمين:

• إثباتات Oracle تفاعلية متعددة الحدود من حيث المعلومات (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): يُعتبر PIOP جوهر نظام الإثبات، حيث يقوم بتحويل العلاقات الحسابية المدخلة إلى معادلات متعددة الحدود يمكن التحقق منها. تسمح بروتوكولات PIOP المختلفة من خلال التفاعل مع المدقق، للمثبت بإرسال المتعددات بشكل تدريجي، بحيث يمكن للمدقق التحقق مما إذا كانت الحسابات صحيحة من خلال استعلام نتائج تقييم عدد قليل من المتعددات. تشمل بروتوكولات PIOP الحالية: PLONK PIOP و Spartan PIOP و HyperPlonk PIOP، والتي تختلف في كيفية معالجة تعبيرات المتعددات، مما يؤثر على أداء وكفاءة نظام SNARK بأكمله.

• مخطط الالتزام المتعدد الحدود (Polynomial Commitment Scheme, PCS): يُستخدم مخطط الالتزام المتعدد الحدود لإثبات ما إذا كانت المعادلات المتعددة الحدود التي ينتجها PIOP صحيحة. PCS هي أداة تشفيرية، من خلالها يمكن للمُثبت الالتزام بمقدار متعدد الحدود والتحقق لاحقًا من نتائج تقييم هذا المقدار، مع إخفاء معلومات أخرى عن المقدار المتعدد الحدود. تشمل مخططات الالتزام المتعدد الحدود الشائعة KZG وBulletproofs وFRI (Fast Reed-Solomon IOPP) وBrakedown وغيرها. تتمتع PCS المختلفة بأداء وأمان وسيناريوهات تطبيق مختلفة.

بناءً على الاحتياجات المحددة، اختر PIOP و PCS المختلفة، ودمجها مع الحقول المحدودة المناسبة أو المنحنيات البيانية، يمكن بناء أنظمة إثبات ذات خصائص مختلفة. على سبيل المثال:

• Halo2: تم دمجه من PLONK PIOP و Bulletproofs PCS ، ويستند إلى منحنى Pasta. تم تصميم Halo2 مع التركيز على القابلية للتوسع وإزالة إعداد موثوق به في بروتوكول ZCash.

• Plonky2: يعتمد على PLONK PIOP وFRI PCS ويستند إلى مجال Goldilocks. تم تصميم Plonky2 لتحقيق تكرار فعال. عند تصميم هذه الأنظمة، يجب أن تتطابق PIOP وPCS المختارة مع المجال المحدود أو المنحنيات البيانية المستخدمة لضمان صحة النظام وأدائه وأمانه. لا تؤثر هذه الاختيارات على حجم دليل SNARK وكفاءة التحقق فحسب، بل تحدد أيضًا ما إذا كان من الممكن تحقيق الشفافية دون إعداد موثوق، وما إذا كان يمكن دعم ميزات التوسع مثل دليل التكرار أو دليل التجميع.

بينيوس: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي. على وجه التحديد ، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وسلامته. بادئ ذي بدء ، يشكل الحساب القائم على أبراج الحقول الثنائية أساس حساباته ، والتي يمكن أن تحقق عمليات مبسطة في الحقول الثنائية. ثانيا ، في بروتوكول Oracle Proof التفاعلي (PIOP) ، قام Binius بتكييف منتج HyperPlonk وفحص التقليب لضمان فحص الاتساق الآمن والفعال بين المتغيرات وتبديلها. ثالثا ، يقدم البروتوكول وسيطة إزاحة جديدة متعددة الخطوط لتحسين كفاءة التحقق من العلاقة متعددة الخطوط في مجال صغير. رابعا ، يتبنى Binius نسخة محسنة من وسيطة البحث Lasso ، والتي توفر المرونة والأمان القوي لآلية البحث. أخيرا ، يستخدم البروتوكول مخطط التزام متعدد الحدود للمجال الصغير (PCS للمجال الصغير) ، والذي يمكنه من تنفيذ نظام إثبات فعال على المجال الثنائي وتقليل النفقات العامة المرتبطة عادة بالمجالات الكبيرة.

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

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

"canonical" تشير إلى الطريقة الفريدة والمباشرة لتمثيل العناصر في الحقل الثنائي. على سبيل المثال، في الحقل الثنائي الأساسي F2، يمكن أن يتم تمثيل أي سلسلة بطول k مباشرة كعنصر في الحقل الثنائي بطول k. هذا يختلف عن الحقول الأولية، حيث لا يمكن للحقل الأولي أن يوفر هذا التمثيل القياسي ضمن عدد محدد من البتات. على الرغم من أن الحقل الأولي المكون من 32 بت يمكن أن يحتوي على 32 بت، إلا أنه ليس كل سلسلة مكونة من 32 بت يمكن أن تتوافق بشكل فريد مع عنصر في الحقل، بينما يوفر الحقل الثنائي هذه الميزة في التوافق الواحد لواحد. في الحقل الأولي Fp، تشمل طرق الاختزال الشائعة اختزال باريرت، اختزال مونتغومري، وطرق الاختزال الخاصة للحقول المحدودة مثل Mersenne-31 أو Goldilocks-64. في الحقل الثنائي F2k، تشمل طرق الاختزال الشائعة الاختزال الخاص (مثل المستخدم في AES)، اختزال مونتغومري (مثل المستخدم في POLYVAL) والاختزال التكراري (مثل Tower). تشير الورقة "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" إلى أن الحقل الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية التربيع في الحقل الثنائي فعالة للغاية لأنها تتبع قاعدة التبسيط (X + Y )2 = X2 + Y 2.

كما هو موضح في الشكل 1، سلسلة بطول 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق المجال الثنائي. يمكن اعتبارها عنصرًا فريدًا في المجال الثنائي بطول 128 بت، أو يمكن تحليلها إلى عنصرين في مجال البرج بطول 64 بت، أربعة عناصر في مجال البرج بطول 32 بت، 16 عنصرًا في مجال البرج بطول 8 بت، أو 128 عنصرًا في مجال F2. هذه المرونة في التمثيل لا تتطلب أي تكاليف حسابية، بل هي مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة للاهتمام ومفيدة للغاية. في الوقت نفسه، يمكن حزم عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى تكاليف حسابية إضافية. تستفيد بروتوكول Binius من هذه الميزة لتحسين الكفاءة الحسابية. بالإضافة إلى ذلك، تستكشف الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحسابات لعمليات الضرب والتربيع والعكس في المجال الثنائي البرجي بطول n (يمكن تفكيكه إلى مجالات فرعية بطول m).

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

2.2 PIOP: النسخة المعدلة من منتج HyperPlonk وPermutationCheck------المناسبة للحقل الثنائي

استند تصميم PIOP في بروتوكول Binius إلى HyperPlonk، حيث اعتمد على مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمتغيرات المتعددة. تشمل هذه الفحوصات الأساسية:

1. GateCheck: تحقق من أن الشهادة السرية ω والمدخل العام x يلبيان علاقة العملية الدائرية C(x,ω)=0، لضمان تشغيل الدائرة بشكل صحيح.

2. PermutationCheck: تحقق مما إذا كانت نتائج تقييم كثيرات الحدود المتعددة المتغيرات f و g على مكعب بولي هي علاقة تبديل f(x) = f(π(x)) لضمان اتساق التباديل بين متغيرات كثيرات الحدود.

3. LookupCheck: التحقق من أن تقييم متعددة الحدود موجود في جدول البحث المعطى، أي f(Bµ) ⊆ T(Bµ)، لضمان أن بعض القيم ضمن النطاق المحدد.

4. MultisetCheck: تحقق مما إذا كانت مجموعتان متعددتان متساويتان، أي {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H، لضمان التناسق بين المجموعات المتعددة.

5. ProductCheck: التحقق مما إذا كانت قيمة كثيرات الحدود منطقية على مكعب بولي على أنها تساوي قيمة معينة ∏x∈Hµ f(x) = s، لضمان صحة حاصل ضرب كثيرات الحدود.

6. ZeroCheck: التحقق مما إذا كانت دالة متعددة المتغيرات على مكعب بولياني عند أي نقطة صفرية ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ، لضمان توزيع نقاط الصفر في الدالة.

7. SumCheck: يتحقق مما إذا كانت قيمة مجموع متعددة المتغيرات للحدود هي القيمة المعلنة ∑x∈Hµ f(x) = s. من خلال تحويل مشكلة تقييم متعددة الحدود متعددة المتغيرات إلى تقييم متعددة الحدود ذات المتغير الواحد، يتم تقليل تعقيد الحساب لطرف التحقق. بالإضافة إلى ذلك، يسمح SumCheck أيضًا بالمعالجة الدفعة، من خلال إدخال أرقام عشوائية، لبناء تركيبات خطية لتحقيق المعالجة الدفعة لعدة أمثلة من التحقق من المجموع.

8. BatchCheck: يعتمد على SumCheck للتحقق من صحة تقييمات متعددة للمتعددات المتغيرة المتعددة، لزيادة كفاءة البروتوكول.

على الرغم من أن Binius و HyperPlonk لديهما العديد من أوجه التشابه في تصميم البروتوكول، إلا أن Binius قد حقق تحسينات في 3 مجالات التالية:

• تحسين ProductCheck: في HyperPlonk، تتطلب ProductCheck أن يكون المقام U غير صفري في كل مكان على المكعب الفائق، ويجب أن تكون النتيجة مساوية لقيمة محددة؛ قامت Binius بتبسيط هذه العملية من خلال تخصيص هذه القيمة إلى 1، مما يقلل من تعقيد الحساب.

• معالجة مشكلة القسمة على الصفر: لم تتمكن HyperPlonk من التعامل بشكل كافٍ مع حالات القسمة على الصفر، مما أدى إلى عدم القدرة على التأكيد على أن U غير صفر في المكعب الفائق؛ عالجت Binius هذه المشكلة بشكل صحيح، حتى في حالة كون المقام صفراً، يمكن لـ ProductCheck الخاص بـ Binius الاستمرار في المعالجة، مما يسمح بالتوسع إلى أي قيمة حاصل ضرب.

• فحص التبديل عبر الأعمدة: لا تحتوي HyperPlonk على هذه الميزة؛ يدعم Binius إجراء فحص التبديل بين عدة أعمدة، مما يمكّن Binius من التعامل مع حالات ترتيب متعددة الحدود الأكثر تعقيدًا.

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

2.3 PIOP: حجة التحويل المتعدد الخطوط الجديدة ------ مناسبة للهيبرمكعب البولياني

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

• التعبئة: هذه الطريقة تقوم من خلال وضع الأصغر في المواقع المجاورة في الترتيب القاموسي