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

1 المقدمة

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

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

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

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

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

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

بينيوس: 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، تشمل طرق الاختزال الشائعة اختزال Barrett، واختزال Montgomery، وطرق اختزال خاصة لمجالات محدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال الشائعة اختزال خاص ( كما هو مستخدم في AES )، واختزال Montgomery ( كما هو مستخدم في POLYVAL )، واختزال تكراري ( كما هو في Tower ). تشير الورقة "استكشاف مساحة تصميم تنفيذات الأجهزة ECC لمجالات الأعداد الأولية مقابل المجالات الثنائية" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية تربيع المجال الثنائي فعالة للغاية، لأنها تتبع القاعدة المبسطة (X + Y )2 = X2 + Y2.

كما هو موضح في الشكل 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 والتفكير الأمثل])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 مجالات التالية:

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

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

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

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

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

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

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