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

1 مقدمة

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

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

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

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

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

• رمز الاستجابة السريعة، يستخدم ترميز Reed-Solomon المعتمد على F28؛

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

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

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

قدم 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 وكفاءة التحقق، بل تحدد أيضًا ما إذا كان النظام يمكن أن يحقق الشفافية دون الحاجة إلى إعداد موثوق، وما إذا كان يمكنه دعم ميزات موسعة مثل إثبات الاستدعاء أو الإثبات المجمع.

Binius: HyperPlonk PIOP + Brakedown PCS + 二进制域. بشكل أكثر تحديدًا، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وأمانه. أولاً، تعتمد حساباته على بنية حسابية تعتمد على أبراج الحقول الثنائية (towers of binary fields)، مما يمكنه من إجراء عمليات مبسطة داخل الحقول الثنائية. ثانيًا، قام Binius بتعديل فحص المنتج والاستبدال في بروتوكول إثبات Oracle التفاعلي (PIOP)، مما يضمن التحقق الآمن والفعال من التناسق بين المتغيرات واستبدالاتها. ثالثًا، يقدم البروتوكول إثباتًا جديدًا لتحويل متعدد الخطوط، مما يحسن من كفاءة التحقق من العلاقات متعددة الخطوط على المجالات الصغيرة. رابعًا، يعتمد Binius على إثبات بحث محسّن من نوع Lasso، مما يوفر المرونة والأمان القوي لآلية البحث. أخيرًا، يستخدم البروتوكول خطة التزام متعدد الحدود على الحقول الصغيرة (Small-Field 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 + Y2.

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

! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 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 قد حقق تحسينات في الجوانب الثلاثة التالية:

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

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

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

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

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

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

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