تحليل مبادئ 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، يجب أن يكون حجم المجال أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة ميركل في 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) ليكون أساساً لحساباتها، مما يمكنها من تنفيذ عمليات مبسطة ضمن المجال الثنائي. ثانياً، في بروتوكول إثبات أوراكل التفاعلي (PIOP)، تعدل بينياس فحص المنتج والاستبدال الخاص بها باستخدام هايبربلونك، مما يضمن فحص التوافق الآمن والكفء بين المتغيرات والاستبدالات. ثالثاً، يقدم البروتوكول إثباتاً جديداً للانتقال المتعدد، مما يحسن من كفاءة التحقق من العلاقات المتعددة في المجالات الصغيرة. رابعاً، تعتمد بينياس نسخة محسنة من إثبات البحث باستخدام Lasso، مما يوفر مرونة وقوة أمان لآلية البحث. أخيراً، يستخدم البروتوكول خطة التزام متعددات الحدود للمجالات الصغيرة (Small-Field 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 والتفكير الأمثل

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

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