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

1 المقدمة

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

كما هو موضح في الجدول 1، عرض الترميز للجيل الأول من STARKs هو 252 بت، عرض الترميز للجيل الثاني من STARKs هو 64 بت، وعرض الترميز للجيل الثالث من STARKs هو 32 بت، ولكن لا يزال هناك الكثير من المساحة المهدرة في عرض الترميز 32 بت. بالمقارنة، يسمح المجال الثنائي بالتعامل المباشر مع البتات، مما يجعل الترميز مضغوطًا وفعالًا دون أي مساحة مهدرة، أي الجيل الرابع من STARKs.

الجدول 1: مسار تطور STARKs

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

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

• معيار التشفير المتقدم (AES)، قائم على مجال F28؛

• Galois رمز التحقق من الرسائل ( GMAC ) ، يعتمد على مجال F2128؛

• رمز الاستجابة السريعة، يستخدم ترميز ريد-سولومون القائم على F28؛

• بروتوكولات FRI الأصلية و zk-STARK، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى نهائيات SHA-3، والتي تعتمد على مجال F28، هي خوارزمية تجزئة مناسبة جداً للتكرار.

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

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

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

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

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

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. هذه المرونة في التمثيل لا تتطلب أي نفقات حسابية، بل مجرد تحويل نوع سلسلة البتات (typecast)، وهي خاصية مثيرة جدًا ومفيدة. في الوقت نفسه، يمكن حزم عناصر الحقل الصغيرة في عناصر حقل أكبر دون الحاجة إلى نفقات حسابية إضافية. بروتوكول بينيوس يستفيد من هذه الميزة لتحسين الكفاءة الحسابية. بالإضافة إلى ذلك، تناقش الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد حساب عمليات الضرب، والتربيع، والعكس في حقل ثنائي برج n بت يمكن تفكيكه إلى حقل فرعي m بت (.

الشكل 1: مجال ثنائي شبيه بالبرج

! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.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، بل وضعت أيضًا أساسًا لأنظمة الإثبات المعتمدة على الحقل الثنائي في المستقبل.

) 2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة------ينطبق على