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

1. المقدمة

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

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

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

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

• Galois رمز مصادقة الرسائل ( GMAC )، مستند إلى مجال F2128؛

• رمز QR، يستخدم ترميز ريد-سولومون القائم على F28؛

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

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

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

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

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

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

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