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

1 المقدمة

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

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

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

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

يشير "canonical" إلى التمثيل الفريد والمباشر للعناصر في مجال ثنائي. على سبيل المثال، في المجال الثنائي الأساسي F2، يمكن أن يتم تعيين أي سلسلة من k بت مباشرة إلى عنصر من عناصر المجال الثنائي بمقدار k بت. هذا يختلف عن المجال الأولي، حيث لا يمكن للمجال الأولي أن يوفر هذا التمثيل القياسي في عدد محدد من البتات. على الرغم من أن المجال الأولي المكون من 32 بت يمكن أن يحتوي على 32 بت، إلا أنه ليس كل سلسلة من 32 بت يمكن أن تتوافق بشكل فريد مع عنصر من عناصر المجال، بينما يتمتع المجال الثنائي بهذه السهولة في التعيين الواحد لواحد. في المجال الأولي Fp، تشمل طرق الاختزال الشائعة اختزال Barrett، واختزال Montgomery، وطرق اختزال خاصة لمجالات محدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال الشائعة الاختزال الخاص (مثل الذي يستخدم في AES)، واختزال Montgomery (مثل الذي يستخدم في 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. إن مرونة هذا التمثيل لا تتطلب أي تكاليف حسابية، بل مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة جداً ومفيدة. في نفس الوقت، يمكن تعبئة عناصر المجال الصغيرة كعناصر مجال أكبر دون الحاجة إلى تكاليف حسابية إضافية. بروتوكول Binius يستفيد من هذه الميزة لتحسين كفاءة الحساب. بالإضافة إلى ذلك، تستكشف الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحسابات لمضاعفة، وتربيع، وعمليات عكس في مجال البرج ثنائي النمط (يمكن تحليله إلى مجال فرعي 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 قد أجرى تحسينات في 3 مجالات التالية:

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

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

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

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

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

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

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