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

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

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

• التعبئة: