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

1 المقدمة

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

في الجيل الأول من ترميز STARKs، كانت عرض البت 252 بت، وفي الجيل الثاني كانت عرض البت 64 بت، بينما في الجيل الثالث كانت عرض البت 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 بحاجة إلى التعمق في مجال توسيع أكبر لضمان الأمان المطلوب.

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

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

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

! أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل

كما هو موضح في الشكل 1، سلسلة مكونة من 128 بت: يمكن تفسير هذه السلسلة بطرق متعددة في سياق المجالات الثنائية. يمكن اعتبارها عنصراً فريداً في مجال ثنائي مكون من 128 بت، أو يمكن تحليلها إلى عنصرين في مجال برج مكون من 64 بت، أو أربعة عناصر في مجال برج مكون من 32 بت، أو 16 عنصراً في مجال برج مكون من 8 بت، أو 128 عنصراً في مجال F2. إن مرونة هذا التمثيل لا تتطلب أي تكلفة حسابية، بل هي مجرد تحويل نوع لسلسلة البتات (typecast)، وهي خاصية مثيرة جداً ومفيدة. في الوقت نفسه، يمكن حزم عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى تكلفة حسابية إضافية. يستفيد بروتوكول Binius من هذه الميزة لتحسين كفاءة الحساب. بالإضافة إلى ذلك، تستكشف الورقة البحثية "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحساب لعمليات الضرب، والتربيع، والعكس في المجالات الثنائية البرجية ذات n بت (التي يمكن تفكيكها إلى مجالات فرعية m بت).

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κ ويجمعها.