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

1 المقدمة

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

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

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

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

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

• رمز الاستجابة السريعة، يستخدم ترميز ريد-سولومون المعتمد على F28؛

• بروتوكولات FRI الأصلية و zk-STARK، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى النهائي في SHA-3، وهي دالة تعتمد على مجال F28، وتعتبر خوارزمية تجزئة مناسبة جدًا للتكرار.

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

عند بناء نظام إثبات يعتمد على مجال ثنائي، هناك مشكلتان عمليتان: عند حساب تمثيل trace في STARKs، يجب أن يكون حجم المجال المستخدم أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة Merkle في STARKs، يجب إجراء ترميز Reed-Solomon، ويجب أن يكون حجم المجال المستخدم أكبر من حجم التمديد الترميزي.

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

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

كما هو موضح في الشكل 1، سلسلة من 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق المجال الثنائي. يمكن اعتبارها عنصراً فريداً في مجال ثنائي 128 بت، أو يمكن تحليلها إلى عنصرين من مجال البرج 64 بت، أو أربعة عناصر من مجال البرج 32 بت، أو 16 عنصراً من مجال البرج 8 بت، أو 128 عنصراً من مجال F2. هذه المرونة في التمثيل لا تتطلب أي تكلفة حسابية، بل هي مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة جداً ومفيدة. في الوقت نفسه، يمكن حزم عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى تكلفة حسابية إضافية. يستفيد بروتوكول Binius من هذه الخاصية لتحسين كفاءة الحساب. بالإضافة إلى ذلك، تستكشف الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحسابات لعمليات الضرب والتربيع والعكس في مجال برج ثنائي 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µ، للتأكد من توزيع نقاط الصفر للمتعددات.

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

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