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

1 المقدمة

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

تبلغ عرض ترميز 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 الحالية عادةً على قسمين رئيسيين:

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

بينيوس: هايبر بلونك PIOP + بركداون PCS + المجالات الثنائية. على وجه التحديد، تشمل بينيوس خمس تقنيات رئيسية لتحقيق كفاءتها وأمانها. أولاً، يعتمد على حسابات المجالات الثنائية (towers of binary fields) كأساس لحساباته، مما يسمح بإجراء عمليات مبسطة داخل المجالات الثنائية. ثانياً، في بروتوكول إثبات Oracle التفاعلي الخاص بها (PIOP)، قامت بتكييف فحص المنتجات والاستبدالات من هايبر بلونك، لضمان تناسق آمن وفعال بين المتغيرات واستبدالاتها. ثالثاً، يقدم البروتوكول إثبات انتقال متعدد الخطوط جديد، مما يحسن كفاءة التحقق من العلاقات متعددة الخطوط على المجالات الصغيرة. رابعاً، تستخدم بينيوس نسخة محسنة من إثبات البحث Lasso، مما يوفر مرونة وأماناً قوياً لآلية البحث. أخيراً، يعتمد البروتوكول على نظام التزام متعدد الحدود في المجالات الصغيرة (Small-Field PCS)، مما يمكنه من تنفيذ نظام إثبات فعال على المجالات الثنائية، وتقليل النفقات المرتبطة عادةً بالمجالات الكبيرة.

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

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

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

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

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

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

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

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

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

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

• Packing:تتم هذه الطريقة من خلال