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

1 المقدمة

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

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

قدمت Binius حلاً مبتكراً يعالج هذين المشكلتين بشكل منفصل، ويمثل نفس البيانات بطريقتين مختلفتين: أولاً، باستخدام متعدد المتغيرات ( وهو في الواقع متعددات الحدود متعددة الخطوط ) بدلاً من متعدد الحدود أحادي المتغير، من خلال قيمته على "hyper-cubes" ( لتمثيل المسار الحسابي الكامل؛ ثانياً، نظراً لأن طول كل بعد من أبعاد hyper-cube هو 2، فلا يمكن توسيع Reed-Solomon القياسي كما في STARKs، ولكن يمكن اعتبار hyper-cube كـ ) مربع (، واستناداً إلى هذا المربع يمكن إجراء توسيع 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 وكفاءة التحقق، بل يحدد أيضًا ما إذا كان النظام قادرًا على تحقيق الشفافية دون الحاجة إلى إعداد موثوق، وما إذا كان يمكن أن يدعم ميزات ممتدة مثل إثباتات إعادة الاستدعاء أو إثباتات التجميع.

بينياس: هايبر بلونك PIOP + بريكدون PCS + مجال ثنائي. بالتحديد، يتضمن بينياس خمس تقنيات رئيسية لتحقيق كفاءته وأمانه. أولاً، يعتمد على بنية حسابية لمجالات ثنائية )towers of binary fields( التي تشكل أساس حساباته، مما يمكنه من تحقيق عمليات مبسطة ضمن المجال الثنائي. ثانياً، في بروتوكول إثبات الأوراكل التفاعلي الخاص به )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 لحقل الأعداد الأولية مقابل الحقل الثنائي" إلى أن الحقل الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية تربيع الحقل الثنائي فعالة للغاية، لأنها تتبع القاعدة المبسطة )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 والتفكير الأمثل

( 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 والتفكير الأمثلي

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

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

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