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

1 المقدمة

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

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

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

| الأجيال | عرض التشفير | النظام الممثل | |------|----------|----------| | الجيل الأول | 252 بت | StarkWare STARKs | | الجيل الثاني | 64 بت | Plonky2 | | الجيل الثالث | 32 بت | BabyBear | | الجيل الرابع | 1 بت | Binius |

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

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

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

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

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: جديد حجة التحويل المتعدد الخطوط------تنطبق