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

1 المقدمة

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

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

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

| الجبر | عرض ترميز البتات | نظام التمثيل | |------|----------|----------| | الجيل الأول | 252 بت | ستارك وير | | الجيل الثاني | 64بت | Plonky2 | | الجيل الثالث | 32 بت | BabyBear | | الجيل الرابع | مجال ثنائي | Binius |

بالمقارنة مع 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 الحالية من جزئين:

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

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

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

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

"canonical" تشير إلى الشكل الفريد والمباشر لعناصر المجال الثنائي. على سبيل المثال، في أبسط مجال ثنائي F2، يمكن لأي سلسلة بطول k أن تتطابق مباشرة مع عنصر من المجال الثنائي بطول k. وهذا يختلف عن المجالات الأولية التي لا يمكنها تقديم هذا التمثيل القياسي ضمن عدد محدد من البتات. على الرغم من أن المجال الأولي المكون من 32 بت يمكن أن يتضمن في 32 بت، إلا أن ليس كل سلسلة من 32 بت يمكن أن تتطابق بشكل فريد مع عنصر من المجال، بينما يوفر المجال الثنائي هذه الملاءمة من التطابق الثنائي. تشمل طرق الاختزال الشائعة في المجال الأولي Fp طرق مثل اختزال بارّيت، اختزال مونتغومري، بالإضافة إلى طرق اختزال خاصة للمجالات المحدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال الشائعة اختزال خاص ( كما هو مستخدم في AES باستخدام )، واختزال مونتغومري ( كما هو مستخدم في POLYVAL باستخدام )، واختزال متكرر ( كما هو مستخدم في Tower ). تشير الورقة العلمية "استكشاف مساحة تصميم ECC-Hardware Implementations للمجال الأولي مقابل المجال الثنائي" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية التربيع في المجال الثنائي فعالة للغاية، لأنها تتبع القاعدة المبسطة (X + Y )2 = X2 + Y 2.

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

! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.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 قد قام بتحسينات في 3 مجالات التالية:

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

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

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

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

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

في بروتوكول Binius، الخيال