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

1 المقدمة

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

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

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

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

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

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

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

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

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

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

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

2.3 PIOP：حجة التحول المتعدد الخطوط الجديدة------مناسبة للتكعيب الثنائي

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

• التعبئة：