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

1 المقدمة

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

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

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

| الترتيب | عرض البت | الوصف | |------|------|------| | الجيل الأول | 252 بت | بناءً على مجال الأعداد الأولية | | الجيل الثاني | 64 بت | مجال Goldilocks | | الجيل الثالث | 32 بت | مجال Babybear | | الجيل الرابع | 1bit | مجال ثنائي |

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

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

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

• رمز الاستجابة السريعة، يستخدم ترميز ريد-سولومون القائم على 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-Hardware لحقل أولي مقابل حقل ثنائي" إلى أن الحقل الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية التربيع في الحقل الثنائي فعالة جداً، لأنها تتبع القاعدة المبسطة (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 والتفكير الأمثل])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، متعددة الافتراضية