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

1 مقدمة

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

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

الجدول 1: مسار تفرع STARKs

| ميزة | الجيل الأول من STARKs | الجيل الثاني من STARKs | الجيل الثالث من STARKs | الجيل الرابع STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | عرض بت التعليمات البرمجية | 252 بت | 64 بت | 32 بت | 1 بت | | النظام التمثيلي | ستاركوير | [بلونكي2] | بيبي بير | بينيوس |

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

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

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

• رمز الاستجابة السريعة، يستخدم ترميز Reed-Solomon القائم على F28؛

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

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

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

يقترح بينيوس حلا مبتكرا يتعامل مع هاتين المشكلتين بشكل منفصل ويفعل ذلك من خلال تمثيل نفس البيانات بطريقتين مختلفتين: أولا ، استخدام كثيرات الحدود متعددة المتغيرات (على وجه التحديد ، متعددة الخطوط) بدلا من كثيرات الحدود أحادية المتغير ، وتمثيل المسار الحسابي بأكمله بقيمته على "المكعبات الفائقة". ثانيا ، نظرا لأن طول كل بعد من أبعاد المكعب الفائق هو 2 ، فلا يمكن عمل امتداد Reed-Solomon القياسي مثل STARKs ، ولكن يمكن التعامل مع المكعب الفائق على أنه مربع يعتمد على امتداد Reed-Solomon. تعمل هذه الطريقة على تحسين كفاءة الترميز وأداء الحوسبة بشكل كبير مع ضمان الأمان.

2 تحليل المبدأ

يتكون بناء معظم أنظمة SNARKs الحالية عادة من الجزأين التاليين:

• إثبات أوراكل التفاعلي متعدد الحدود النظري للمعلومات (PIOP) :P IOP كجوهر نظام الإثبات ، مما يحول العلاقات الحسابية للمدخلات إلى معادلات متعددة الحدود يمكن التحقق منها. تسمح بروتوكولات PIOP المختلفة للبروفير بإرسال كثيرات الحدود خطوة بخطوة من خلال التفاعل مع المدقق ، مما يسمح للمدقق بالتحقق من صحة الحساب عن طريق الاستعلام عن نتائج التقييم لعدد صغير من كثيرات الحدود. تتضمن بروتوكولات PIOP الحالية PLONK PIOP و Spartan PIOP و HyperPlonk PIOP ، وكلها تتعامل مع التعبيرات متعددة الحدود بشكل مختلف ، مما يؤثر على أداء وكفاءة نظام SNARK بأكمله.

• مخطط الالتزام متعدد الحدود (PCS): يستخدم مخطط الالتزام متعدد الحدود لإثبات ما إذا كانت المعادلة متعددة الحدود التي تم إنشاؤها بواسطة PIOP صحيحة. PCS هي أداة تشفير يمكن من خلالها للمحترف الالتزام بكثير الحدود معين والتحقق لاحقا من نتائج تقييم هذا كثيرة الحدود ، مع إخفاء معلومات أخرى حول كثيرة الحدود. تشمل مخططات الالتزام متعددة الحدود الشائعة KZG و Bulletproofs و FRI (Fast Reed-Solomon IOPP) و Brakedown. تحتوي أجهزة الكمبيوتر المختلفة على سيناريوهات مختلفة للأداء والأمان والتطبيق.

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

• Halo2: مدعوم من PLONK PIOP جنبا إلى جنب مع Bulletproofs PCS ويعتمد على منحنيات المعكرونة. تم تصميم Halo2 مع وضع قابلية التوسع في الاعتبار ، بالإضافة إلى إزالة الإعداد الموثوق به من بروتوكول ZCash.

• Plonky2: يجمع بين PLONK PIOP و FRI PCS ويستند إلى مجال Goldilocks. Plonky2 مخصص للعودية الفعالة. عند تصميم هذه الأنظمة ، يجب أن يتطابق PIOP و PCS المحددان مع المجال المحدود أو المنحنى الإهليلجي المستخدم لضمان صحة النظام وأدائه وسلامته. لا يؤثر اختيار هذه المجموعات على حجم الإثبات وكفاءة التحقق من SNARKs فحسب ، بل يحدد أيضا ما إذا كان بإمكان النظام تحقيق الشفافية دون الحاجة إلى إعدادات موثوقة ، وما إذا كان بإمكانه دعم الوظائف الموسعة مثل البراهين المتكررة أو البراهين المجمعة.

بينيوس: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي. على وجه التحديد ، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وسلامته. بادئ ذي بدء ، يشكل الحساب القائم على أبراج الحقول الثنائية أساس حساباته ، والتي يمكن أن تحقق عمليات مبسطة في الحقول الثنائية. ثانيا ، في بروتوكول Oracle Proof التفاعلي (PIOP) ، قام Binius بتكييف منتج HyperPlonk وفحص التقليب لضمان فحص الاتساق الآمن والفعال بين المتغيرات وتبديلها. ثالثا ، يقدم البروتوكول وسيطة إزاحة جديدة متعددة الخطوط لتحسين كفاءة التحقق من العلاقة متعددة الخطوط في مجال صغير. رابعا ، يتبنى Binius نسخة محسنة من وسيطة البحث Lasso ، والتي توفر المرونة والأمان القوي لآلية البحث. أخيرا ، يستخدم البروتوكول مخطط التزام متعدد الحدود للمجال الصغير (PCS للمجال الصغير) ، والذي يمكنه من تنفيذ نظام إثبات فعال على المجال الثنائي وتقليل النفقات العامة المرتبطة عادة بالمجالات الكبيرة.

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

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

حيث تشير كلمة "canonical" إلى تمثيل فريد ومباشر لعنصر في المجال الثنائي. على سبيل المثال ، في المجال الثنائي الأساسي F2 ، يمكن تعيين أي سلسلة k-bit مباشرة إلى عنصر مجال ثنائي k-bit. هذا على النقيض من حقل الأعداد الأولية ، الذي لا يمكنه توفير مثل هذا التمثيل الكنسي داخل الموضع المحدد. على الرغم من أنه يمكن احتواء حقل عدد أولي 32 بت في نظام 32 بت ، إلا أنه لا تتوافق كل سلسلة 32 بت بشكل فريد مع عنصر المجال ، وتتمتع الحقول الثنائية براحة هذا التعيين الفردي. في المجال الرئيسي FP ، تشمل طرق الاختزال الشائعة تقليل Barrett ، وتقليل Montgomery ، وطرق الاختزال الخاصة للحقول المحدودة المحددة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k ، تشمل طرق الاختزال شائعة الاستخدام اختزال خاص (على سبيل المثال ، يستخدم في AES) ، واختزال مونتغمري (على سبيل المثال ، يستخدم في POLYVAL) ، والاختزال المتكرر (على سبيل المثال ، البرج). تشير الورقة البحثية "استكشاف مساحة تصميم الحقل الأولي مقابل تطبيقات أجهزة ECC للحقل الثنائي" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في كل من الجمع والضرب ، وأن العملية التربيعية للمجال الثنائي فعالة للغاية لأنها تتبع (X + Y )2 = X2 + Y 2.

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

كما هو موضح في الشكل 1 ، سلسلة 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق المجال الثنائي. يمكن اعتباره عنصرا فريدا في مجال ثنائي 128 بت ، أو يمكن حله كعنصرين برجيين 64 بت ، أو أربعة عناصر برج 32 بت ، أو 16 عنصرا برجيا 8 بت ، أو 128 عنصرا من عناصر مجال F2. لا تتطلب مرونة هذا التمثيل أي نفقات حسابية ، فقط مجموعة من سلاسل البتات ، وهي خاصية مثيرة للاهتمام ومفيدة للغاية. في الوقت نفسه ، يمكن تجميع عناصر المجال الصغيرة في عناصر مجال أكبر دون نفقات حسابية إضافية. يستفيد بروتوكول Binius من هذه الميزة لتحسين الكفاءة الحسابية. بالإضافة إلى ذلك ، تستكشف الورقة البحثية "حول الانعكاس الفعال في حقول البرج ذات الخاصية الثانية" التعقيد الحسابي للضرب والتربيع وعمليات الانعكاس في مجال ثنائي برج n-bit يمكن أن يتحلل إلى نطاقات فرعية m-bit.

2.2 PIOP: منتج HyperPlonk المعدل وفحص التقليب ------ للمجالات الثنائية

يستعير تصميم PIOP في بروتوكول Binius من HyperPlonk ويستخدم سلسلة من آليات الفحص الأساسية للتحقق من صحة كثيرات الحدود والمجموعات متعددة المتغيرات. تشمل هذه الاختبارات الأساسية ما يلي:

1. GateCheck: تحقق مما إذا كان الشاهد السري ω والمدخلات العامة x تفي بعلاقة تشغيل الدائرة C(x ، ω) = 0 لضمان التشغيل الصحيح للدائرة.

2. التحقق من التقليب: تحقق من أن نتائج تقييم كثيرات الحدود متعددة المتغيرات 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 في المعالجة حتى عندما يكون المقام صفرا ، مما يسمح بالتعميمات على قيم المنتج التعسفية.

• PermutationCheck: هذه الميزة غير متوفرة في HyperPlonk. يدعم Binius PermutationCheck بين أعمدة متعددة ، مما يسمح ل Binius بالتعامل مع التباديل متعدد الحدود الأكثر تعقيدا.

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