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

1 المقدمة

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

يبلغ عرض ترميز الجيل الأول من STARKs 252 بت، بينما يبلغ عرض ترميز الجيل الثاني 64 بت، ويبلغ عرض ترميز الجيل الثالث 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، فإنه لا يمكن توسيعها بالطريقة القياسية لـ STARKs مثل توسيع Reed-Solomon، ولكن يمكن اعتبار الهيبركيوب بمثابة مربع (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) لضمان فحص متسق وآمن وفعال بين المتغيرات والاستبدالات. ثالثاً، يقدم البروتوكول إثباتاً جديداً متعدد الخطوط، مما يحسن من كفاءة التحقق من العلاقات متعددة الخطوط في المجالات الصغيرة. رابعاً، اعتمدت بينيوس نسخة محسّنة من إثبات البحث Lasso، مما يوفر مرونة وأماناً قوياً لآلية البحث. أخيراً، يستخدم البروتوكول خطة التزام متعددة الحدود في المجالات الصغيرة (Small-Field PCS)، مما يمكنه من تنفيذ نظام إثبات فعال في المجال الثنائي، ويقلل من المصاريف المرتبطة عادةً بالمجالات الكبيرة.

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

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

"canonical" تشير إلى التمثيل الفريد والمباشر للعناصر في المجال الثنائي. على سبيل المثال، في المجال الثنائي الأساسي F2، يمكن لأي سلسلة مكونة من k بت أن يتم ربطها مباشرة بعنصر في المجال الثنائي مكون من k بت. وهذا يختلف عن المجال الأولي، حيث لا يمكن للمجال الأولي توفير هذا التمثيل القائم على عدد محدد من البتات. على الرغم من أن المجال الأولي المكون من 32 بت يمكن أن يحتوي على 32 بت، إلا أنه ليس كل سلسلة مكونة من 32 بت يمكن أن تتطابق بشكل فريد مع عنصر في المجال، بينما يمتاز المجال الثنائي بسهولة الربط الواحد إلى الواحد. في المجال الأولي Fp، تشمل طرق التخفيف الشائعة تخفيف بارينت، وتخفيف مونتغومري، وطرق تخفيف خاصة لمجالات محدودة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق التخفيف المستخدمة التخفيف الخاص ( كما هو مستخدم في AES )، وتخفيف مونتغومري ( كما هو مستخدم في 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 والتفكير الأمثل

2.2 PIOP: إصدار مُعدَّل من HyperPlonk Product و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، بل وضعت أيضًا الأساس لنظم الإثبات المعتمدة على الحقول الثنائية في المستقبل.

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

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

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