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

1 المقدمة

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

عرض عرض الترميز من الجيل الأول من 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، يجب أن يكون حجم المجال المستخدم أكبر من درجة متعددة الحدود؛ عند الالتزام لشجرة Merkle في STARKs، يجب القيام بتشفير Reed-Solomon، ويجب أن يكون حجم المجال المستخدم أكبر من الحجم بعد التمديد للتشفير.

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

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

عادةً ما يتكون بناء معظم أنظمة SNARKs الحالية من جزئين:

• نظرية المعلومات برهان تفاعلي متعدد الحدود ( 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 خمس تقنيات رئيسية لتحقيق كفاءته وسلامته. أولا, يشكل الحساب المستند إلى (towers المجال الثنائي للبرج من fields) الثنائي أساس حسابه, التي يمكن أن تحقق عمليات مبسطة في المجال الثنائي. ثانيا ، في بروتوكول إثبات Oracle التفاعلي (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. تعكس هذه المرونة في التمثيل عدم الحاجة إلى أي تكلفة حسابية، فهي مجرد تحويل نوع لسلسلة البتات (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 قد قام بتحسينات في 3 مجالات التالية:

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

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

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

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

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

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

• التعبئة: تُحسن هذه الطريقة العملية من خلال تعبئة العناصر الأصغر المجاورة في ترتيب القاموس لتصبح عناصر أكبر. تستهدف عملية التعبئة الكتل بحجم 2κ وتجمعها في مجال متعدد الأبعاد.