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

1 المقدمة

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

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

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

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

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

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

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

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

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

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µ، لضمان توزيع نقاط الصفر للحد polynomial.

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

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

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

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

• التعبئة: تستخدم هذه الطريقة العناصر الأصغر في المواقع المجاورة في ترتيب القاموس