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

1 المقدمة

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

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

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

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

• Galois رمز المصادقة ( GMAC ) ، بناءً على مجال F2128 ؛

• رمز QR، يستخدم ترميز Reed-Solomon القائم على F28؛

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

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

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

قدمت Binius حلاً مبتكراً يعالج هذين المشكلتين بشكل منفصل، ويحقق ذلك من خلال تمثيل نفس البيانات بطرق مختلفة: أولاً، باستخدام متغيرات متعددة (، وهي في الواقع متعددة الحدود متعددة الخطوط )، بدلاً من متعددة الحدود ذات المتغير الواحد، من خلال قيمتها على "الهيبركيوب" ( hybercubes ) لتمثيل المسار الحسابي الكامل؛ ثانياً، نظراً لأن طول كل بُعد في الهيبركيوب هو 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-bit مباشرة إلى عنصر مجال ثنائي k-bit. هذا على النقيض من حقل الأعداد الأولية ، الذي لا يمكنه توفير مثل هذا التمثيل الكنسي داخل الموضع المحدد. على الرغم من أنه يمكن احتواء حقل عدد أولي 32 بت في نظام 32 بت ، إلا أنه لا تتوافق كل سلسلة 32 بت بشكل فريد مع عنصر المجال ، وتتمتع الحقول الثنائية براحة هذا التعيين الفردي. في المجال الرئيسي FP ، تشمل طرق الاختزال الشائعة تقليل Barrett ، وتقليل Montgomery ، وطرق الاختزال الخاصة للحقول المحدودة المحددة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k ، تتضمن طرق الاختزال شائعة الاستخدام ( اختزال خاصة مثل استخدام ) في AES ، تستخدم ( الاختزال في مونتغمري مثل POLYVAL ) والاختزال المتكرر ( مثل Tower). تشير الورقة البحثية "استكشاف مساحة تصميم الحقل الأولي مقابل تطبيقات أجهزة ECC للحقل الثنائي" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في كل من الجمع والضرب ، وأن العملية التربيعية للمجال الثنائي فعالة للغاية لأنها تتبع (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 قد أجرى تحسينات في المجالات الثلاثة التالية:

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

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

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

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

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

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

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