على عكس SNARKs المعتمدة على المنحنيات البيضاوية، يمكن اعتبار STARKs كـ SNARKs المعتمدة على التجزئة. أحد الأسباب الرئيسية لانخفاض كفاءة STARKs في الوقت الحالي هو: أن معظم القيم العددية في البرامج الفعلية تكون صغيرة، مثل فهارس الحلقات والقيم البوليانية والعدادات، وما إلى ذلك. ومع ذلك، لضمان أمان إثباتات شجرة ميركل، عند توسيع البيانات باستخدام ترميز ريد-سولومون، ستشغل العديد من القيم الزائدة المجال بأكمله، حتى لو كانت القيم الأصلية صغيرة. ولحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تتمتع النسخة الأولى من ترميز STARKs بعرض ترميز يبلغ 252 بت، بينما تبلغ النسخة الثانية 64 بت، والنسخة الثالثة 32 بت، ولكن لا يزال هناك الكثير من المساحة المهدرة في الترميز 32 بت. بالمقارنة، يسمح المجال الثنائي بإجراء عمليات مباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا دون هدر، ويمكن اعتباره الجيل الرابع من STARKs.
تعود دراسة الحقول الثنائية إلى الثمانينيات، مقارنة بالاكتشافات الأخيرة مثل Goldilocks و BabyBear و Mersenne31. في الوقت الحالي، تم تطبيق الحقول الثنائية على نطاق واسع في علم التشفير، مثل حقل AES(F28، وحقل GMAC)F2128، وترميز Reed-Solomon لرموز QR(F28. كما أن بروتوكولات FRI الأصلية و zk-STARK، بالإضافة إلى دالة تجزئة Grøstl التي وصلت إلى المرحلة النهائية من SHA-3، تستند أيضًا إلى حقل F28.
عند استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. يعتمد المجال الثنائي الذي يستخدمه بينيوس بالكامل على توسيع المجال لضمان الأمان والقابلية للاستخدام. تتطلب معظم الحسابات المتعلقة بـ Prover أن تتم العمليات على المجال الأساسي، مما يحقق كفاءة عالية في المجال الصغير. ولكن لا تزال عمليات التحقق من النقاط العشوائية وحساب FRI تحتاج إلى أن تتم في مجال أوسع لضمان الأمان المطلوب.
عند بناء نظام إثبات يعتمد على مجال ثنائي، توجد مشكلتان عمليتان:
عند حساب تمثيل trace في STARKs، يجب أن تكون حجم المجال أكبر من درجة كثير الحدود.
في STARKs، يجب القيام بترميز Reed-Solomon عند الالتزام بشجرة Merkle، ويجب أن يكون حجم المجال المستخدم أكبر من الحجم بعد توسيع الترميز.
قدمت Binius حلولًا مبتكرة لمعالجة هذين المشكلتين على حدة:
استخدم متعدد المتغيرات ) متعدد الخطوط ( متعدد الحدود بدلاً من متعدد الحدود أحادي المتغير، من خلال قيمته على "المكعب الفائق" لتمثيل المسار الحسابي بأكمله.
نظرًا لأن طول كل بُعد من المكعب الفائق هو 2، لا يمكن توسيعها باستخدام Reed-Solomon القياسي مثل STARKs، ولكن يمكن اعتبار المكعب الفائق مربعًا، والاعتماد على هذا المربع لتوسيع Reed-Solomon.
تضمن هذه الطريقة الأمان في نفس الوقت الذي تعزز فيه بشكل كبير من كفاءة الترميز وأداء الحساب.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 تحليل المبدأ
تتكون معظم أنظمة SNARKs الحالية عادةً من جزئين:
إثبات آلة التنبؤ التفاعلية متعددة الحدود في نظرية المعلومات ) PIOP (:
كجزء أساسي من نظام الإثبات، يتم تحويل العلاقات الحسابية المدخلة إلى معادلات متعددة الحدود قابلة للتحقق. من خلال التفاعل مع المدقق، يقوم المثبت بإرسال متعددة الحدود بشكل تدريجي، مما يسمح للمدقق بالتحقق من صحة الحساب من خلال استعلام عدد قليل من تقييمات متعددة الحدود. تشمل بروتوكولات PIOP الحالية بروتوكولات PLONK PIOP و Spartan PIOP و HyperPlonk PIOP.
مخطط الالتزام متعدد الحدود )PCS(:
تُستخدم لإثبات ما إذا كانت معادلات متعددة الحدود التي تم إنشاؤها بواسطة PIOP صحيحة أم لا. PCS هي أداة تشفير، حيث يمكن للمدعي الالتزام بمعدل متعدد الحدود والتحقق من نتيجة تقييمه لاحقًا، بينما يخفي معلومات أخرى عن المعدل المتعدد الحدود. تشمل PCS الشائعة KZG و Bulletproofs و FRI و Brakedown.
يمكن بناء أنظمة إثبات ذات خصائص مختلفة من خلال اختيار PIOP و PCS مختلفين وفقًا للاحتياجات، ودمجها مع مجالات محدودة أو منحنيات بيانية مناسبة. على سبيل المثال:
Halo2: PLONK PIOP + أجهزة الكمبيوتر المضادة للرصاص + منحنى المعكرونة
Plonky2: PLONK PIOP + FRI PCS + مجالات Goldilocks
بينيوس: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي
Binius يتضمن خمس تقنيات رئيسية:
الحساب القائم على مجال ثنائي البرج: يشكل أساس الحساب، ويحقق العمليات المبسطة ضمن المجال الثنائي
إعادة صياغة فحص المنتج والاستبدال لـ HyperPlonk: ضمان فحص الكفاءة المتسقة بين المتغيرات والاستبدالات
برهان التحول المتعدد الخطي الجديد: تحسين كفاءة التحقق من العلاقات المتعددة الخطية على مجالات صغيرة
تحسين دليل بحث Lasso: توفير المرونة والأمان لآلية البحث
نظام الالتزام متعدد الحدود في المجال الصغير: تحقيق نظام إثبات فعال في المجال الثنائي، وتقليل النفقات المتعلقة بالمجال الكبير
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثلي])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 الحقول المحدودة: الحساب القائم على أبراج الحقول الثنائية
النطاق الثنائي البرجي هو مفتاح لتحقيق حسابات سريعة قابلة للتحقق، وذلك بسبب الكفاءة العالية في الحسابات والكفاءة العالية في الحسابات الرياضية. يدعم النطاق الثنائي بشكل أساسي عمليات حسابية عالية الكفاءة، مما يجعله الخيار المثالي لتطبيقات التشفير الحساسة للأداء. تدعم بنية النطاق الثنائي عملية حسابية مبسطة، حيث يمكن تمثيل العمليات المنفذة على النطاق الثنائي بشكل جبرية مضغوطة وسهلة التحقق. هذه الخصائص، بالإضافة إلى القدرة على الاستفادة الكاملة من خصائصها الهرمية من خلال الهيكل البرجي، تجعل النطاق الثنائي مناسبًا بشكل خاص لأنظمة الإثبات القابلة للتوسع مثل Binius.
"canonical" تشير إلى طريقة العرض الفريدة والمباشرة لعناصر المجال الثنائي. على سبيل المثال، في المجال الثنائي الأساسي F2، يمكن أن يتم ربط أي سلسلة مكونة من k بت مباشرة بعنصر من عناصر المجال الثنائي المكون من k بت. هذا يختلف عن المجال الأولي، حيث لا يمكن للمجال الأولي أن يقدم هذا النوع من العرض القياسي ضمن عدد محدد من البتات. على الرغم من أن المجال الأولي المكون من 32 بت يمكن أن يتضمن ضمن 32 بت، إلا أنه ليس كل سلسلة مكونة من 32 بت يمكن أن تتوافق بشكل فريد مع عنصر من عناصر المجال، بينما يتمتع المجال الثنائي بهذه السهولة في الربط الواحد لواحد.
في مجال الأعداد الأولية Fp، تشمل طرق الاختزال الشائعة اختزال Barrett، واختزال Montgomery، بالإضافة إلى طرق الاختزال الخاصة المحددة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال الشائعة اختزال خاص ( مثل AES يستخدم )، واختزال Montgomery ### مثل POLYVAL يستخدم (، واختزال متكرر ) مثل Tower (.
تشير الورقة "استكشاف مساحة تصميم تنفيذات الأجهزة ECC في الحقول الأولية مقابل الحقول الثنائية" إلى أنه لا حاجة لإدخال الحمل في عمليات الجمع والضرب في الحقل الثنائي، وأن عملية التربيع في الحقل الثنائي فعالة للغاية، لأنها تتبع قاعدة التبسيط )X + Y(2 = X2 + Y2.
يمكن تفسير سلسلة مكونة من 128 بت بطرق متعددة في سياق مجال ثنائي. يمكن اعتبارها عنصرًا فريدًا في مجال ثنائي مكون من 128 بت، أو تحليلها إلى عنصرين من عناصر مجال البرج بحجم 64 بت، أو أربعة عناصر من عناصر مجال البرج بحجم 32 بت، أو ستة عشر عنصرًا بحجم 8 بت، أو 128 عنصرًا من عناصر مجال F2. هذه المرونة في التمثيل لا تتطلب أي نفقات حسابية، بل هي مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة للاهتمام ومفيدة. في الوقت نفسه، يمكن تعبئة عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى نفقات حسابية إضافية. يستفيد بروتوكول Binius من هذه الميزة لتعزيز كفاءة الحساب.
تناقش الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد حساب عمليات الضرب والتربيع والعكس في النطاقات الثنائية البرجية ذات n بت، حيث يمكن تحليل ) إلى نطاق فرعي m بت (.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: نسخة معدلة من منتج HyperPlonk وPermutationCheck------مناسبة للمجال الثنائي
استلهم تصميم PIOP في بروتوكول Binius من HyperPlonk، حيث يعتمد على مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمجموعات المتعددة المتغيرات:
GateCheck: التحقق من أن الشهادة السرية ω والمدخلات العامة x تستوفي علاقة عمليات الدائرة C(x,ω)=0، لضمان التشغيل الصحيح للدائرة.
PermutationCheck: التحقق من ما إذا كانت نتائج تقييم كثيرات الحدود المتعددة المتغيرات f و g على المكعب الكبير البولياني هي علاقة تبديلية f###x( = f)π(x)(، لضمان اتساق ترتيب المتغيرات في كثيرات الحدود.
LookupCheck: التحقق من أن تقييم متعددة الحدود موجود في جدول البحث المعطى، أي f(Bμ) ⊆ T)Bμ(، لضمان أن بعض القيم ضمن النطاق المحدد.
MultisetCheck: تحقق من ما إذا كانت مجموعتان متعددتان متساويتان، أي {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H، لضمان التناسق بين المجموعات المتعددة.
ProductCheck: تحقق مما إذا كان تقييم كثيرات الحدود الجذرية على مكعب بولي يساوي قيمة معينة تم الإعلان عنها ∏x∈Hμ f)x( = s، تأكد من صحة حاصل الضرب كثيرات الحدود.
ZeroCheck: تحقق مما إذا كانت أي نقطة متعددة المتغيرات متعددة الحدود على مكعب بولي هي صفر ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, لضمان توزيع نقاط الصفر للمتعددات الحدودية.
SumCheck: التحقق من ما إذا كانت قيمة مجموع المتعددات المتغيرة تساوي القيمة المعلنة ∑x∈Hμ f)x( = s. من خلال تحويل مشكلة تقييم المتعددات المتغيرة إلى تقييم متعددات المتغيرات البسيطة، يتم تقليل تعقيد الحساب للجهة التي تتحقق. بالإضافة إلى ذلك، يسمح SumCheck أيضًا بالمعالجة الجماعية، من خلال إدخال أرقام عشوائية، لبناء تركيبات خطية لتحقيق المعالجة الجماعية لعدة حالات من التحقق من المجموع.
BatchCheck: استنادًا إلى SumCheck، للتحقق من صحة تقييمات متعددة للعديد من المتغيرات المتعددة، من أجل تحسين كفاءة البروتوكول.
على الرغم من أن Binius و HyperPlonk لديهما العديد من أوجه التشابه في تصميم البروتوكول، إلا أن Binius قد أحدث تحسينات في 3 مجالات التالية:
تحسين ProductCheck: في HyperPlonk، يتطلب ProductCheck أن يكون المقام U غير صفري في كل مكان على المكعب الفائق، ويجب أن يكون الناتج مساوياً لقيمة معينة؛ قام Binius بتبسيط هذه العملية عن طريق تخصيص هذه القيمة إلى 1، مما يقلل من تعقيد الحساب.
معالجة مشكلة القسمة على الصفر: لم تتمكن HyperPlonk من معالجة حالات القسمة على الصفر بشكل كافٍ، مما أدى إلى عدم القدرة على التأكيد على أن U غير صفري على الهيكل الفائق؛ عالجت Binius هذه المشكلة بشكل صحيح، حتى في حالة كون المقام صفراً، حيث يمكن لـ ProductCheck من Binius الاستمرار في المعالجة، مما يسمح بالتعميم إلى أي قيمة حاصل ضرب.
فحص التبديل بين الأعمدة: HyperPlonk لا يدعم هذه الخاصية؛ بينما يدعم Binius إجراء فحص التبديل بين عدة أعمدة، مما يمكّن Binius من التعامل مع حالات ترتيب متعددة الحدود الأكثر تعقيدًا.
لذلك، قامت Binius من خلال تحسين آلية PIOP SumCheck الحالية، بزيادة مرونة وكفاءة البروتوكول، خاصة عند معالجة التحقق من متعددات الحدود المتعددة المتغيرات الأكثر تعقيدًا، مما يوفر دعمًا وظيفيًا أقوى. لم تحل هذه التحسينات فقط قيود HyperPlonk، بل وضعت أيضًا أساسًا لأنظمة الإثبات القائمة على الحقول الثنائية في المستقبل.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp(
) 2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة ------ تنطبق على الهيبركيوب البولياني
في بروتوكول Binius، يعد بناء ومعالجة البولينومات الافتراضية واحدة من التقنيات الرئيسية، حيث يمكنها بشكل فعال توليد ومعالجة البولينومات المشتقة من مقبض الإدخال أو البولينومات الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان:
Packing: هذه الطريقة تعمل على تحسين العمليات من خلال تعبئة العناصر الأصغر المجاورة في ترتيب القاموس لخلق عناصر أكبر. يتم استهداف عملية Pack لكتل بحجم 2κ، وتجمعها في عنصر واحد في مجال عالي الأبعاد. من خلال التمديد المتعدد الخطوط (Multilinear Extension، MLE)، يمكن تقييم هذا متعدد الحدود الافتراضي ومعالجته بكفاءة، مما يحول الدالة t إلى متعدد حدود آخر، وبالتالي يعزز أداء الحوسبة.
عوامل الإزاحة: تعيد عوامل الإزاحة ترتيب عناصر الكتل، بناءً على إزاحة معينة o، وتقوم بإزاحة دورانية. هذه الطريقة مناسبة للكتل بحجم 2b، حيث يتم تنفيذ الإزاحة لكل كتلة بناءً على الإزاحة. يتم تعريف عوامل الإزاحة من خلال دعم وظيفة الكشف، لضمان الاتساق والكفاءة عند معالجة متعددة الحدود الافتراضية. تنمو تعقيد تقييم هذا البناء خطيًا مع حجم الكتلة، مما يجعلها مناسبة بشكل خاص لمعالجة مجموعات البيانات الكبيرة أو المشاهد عالية الأبعاد في فرط مكعب البولي.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل]###https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp(
) 2.4 PIOP: إصدار معدّل حجة بحث Lasso ------ مناسب لنطاق ثنائي
تسمح بروتوكولات Lasso للجهة المثبتة بالتعهد بمتجه a ∈ Fm، وإثبات أن جميع عناصره موجودة في جدول محدد مسبقًا t ∈ Fn. يفتح Lasso مفهوم "البحث عن الشذوذ" (lookup singularities)، ويمكن تطبيقه على مخططات التعهدات متعددة الحدود متعددة الخطوط. تظهر كفاءته في الجانبين التاليين:
كفاءة الإثبات: بالنسبة لعمليات البحث m في جدول بحجم n، يحتاج إثبات الجهة فقط إلى الالتزام بـ m+n عنصر من المجال. هذه العناصر صغيرة، جميعها تقع في مجموعة {0,...,m}. في خطة الالتزام المستندة إلى عمليات القوة المتعددة، تكون تكلفة حساب الجهة المثبتة O###m + n( من عمليات المجموعة) مثل
شاهد النسخة الأصلية
قد تحتوي هذه الصفحة على محتوى من جهات خارجية، يتم تقديمه لأغراض إعلامية فقط (وليس كإقرارات/ضمانات)، ولا ينبغي اعتباره موافقة على آرائه من قبل Gate، ولا بمثابة نصيحة مالية أو مهنية. انظر إلى إخلاء المسؤولية للحصول على التفاصيل.
Binius: تحسينات وابتكارات STARKs المعتمدة على مجال ثنائي
تحليل مبادئ Binius STARKs وأفكار تحسينها
1 المقدمة
على عكس SNARKs المعتمدة على المنحنيات البيضاوية، يمكن اعتبار STARKs كـ SNARKs المعتمدة على التجزئة. أحد الأسباب الرئيسية لانخفاض كفاءة STARKs في الوقت الحالي هو: أن معظم القيم العددية في البرامج الفعلية تكون صغيرة، مثل فهارس الحلقات والقيم البوليانية والعدادات، وما إلى ذلك. ومع ذلك، لضمان أمان إثباتات شجرة ميركل، عند توسيع البيانات باستخدام ترميز ريد-سولومون، ستشغل العديد من القيم الزائدة المجال بأكمله، حتى لو كانت القيم الأصلية صغيرة. ولحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تتمتع النسخة الأولى من ترميز STARKs بعرض ترميز يبلغ 252 بت، بينما تبلغ النسخة الثانية 64 بت، والنسخة الثالثة 32 بت، ولكن لا يزال هناك الكثير من المساحة المهدرة في الترميز 32 بت. بالمقارنة، يسمح المجال الثنائي بإجراء عمليات مباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا دون هدر، ويمكن اعتباره الجيل الرابع من STARKs.
تعود دراسة الحقول الثنائية إلى الثمانينيات، مقارنة بالاكتشافات الأخيرة مثل Goldilocks و BabyBear و Mersenne31. في الوقت الحالي، تم تطبيق الحقول الثنائية على نطاق واسع في علم التشفير، مثل حقل AES(F28، وحقل GMAC)F2128، وترميز Reed-Solomon لرموز QR(F28. كما أن بروتوكولات FRI الأصلية و zk-STARK، بالإضافة إلى دالة تجزئة Grøstl التي وصلت إلى المرحلة النهائية من SHA-3، تستند أيضًا إلى حقل F28.
عند استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. يعتمد المجال الثنائي الذي يستخدمه بينيوس بالكامل على توسيع المجال لضمان الأمان والقابلية للاستخدام. تتطلب معظم الحسابات المتعلقة بـ Prover أن تتم العمليات على المجال الأساسي، مما يحقق كفاءة عالية في المجال الصغير. ولكن لا تزال عمليات التحقق من النقاط العشوائية وحساب FRI تحتاج إلى أن تتم في مجال أوسع لضمان الأمان المطلوب.
عند بناء نظام إثبات يعتمد على مجال ثنائي، توجد مشكلتان عمليتان:
قدمت Binius حلولًا مبتكرة لمعالجة هذين المشكلتين على حدة:
تضمن هذه الطريقة الأمان في نفس الوقت الذي تعزز فيه بشكل كبير من كفاءة الترميز وأداء الحساب.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 تحليل المبدأ
تتكون معظم أنظمة SNARKs الحالية عادةً من جزئين:
إثبات آلة التنبؤ التفاعلية متعددة الحدود في نظرية المعلومات ) PIOP (: كجزء أساسي من نظام الإثبات، يتم تحويل العلاقات الحسابية المدخلة إلى معادلات متعددة الحدود قابلة للتحقق. من خلال التفاعل مع المدقق، يقوم المثبت بإرسال متعددة الحدود بشكل تدريجي، مما يسمح للمدقق بالتحقق من صحة الحساب من خلال استعلام عدد قليل من تقييمات متعددة الحدود. تشمل بروتوكولات PIOP الحالية بروتوكولات PLONK PIOP و Spartan PIOP و HyperPlonk PIOP.
مخطط الالتزام متعدد الحدود )PCS(: تُستخدم لإثبات ما إذا كانت معادلات متعددة الحدود التي تم إنشاؤها بواسطة PIOP صحيحة أم لا. PCS هي أداة تشفير، حيث يمكن للمدعي الالتزام بمعدل متعدد الحدود والتحقق من نتيجة تقييمه لاحقًا، بينما يخفي معلومات أخرى عن المعدل المتعدد الحدود. تشمل PCS الشائعة KZG و Bulletproofs و FRI و Brakedown.
يمكن بناء أنظمة إثبات ذات خصائص مختلفة من خلال اختيار PIOP و PCS مختلفين وفقًا للاحتياجات، ودمجها مع مجالات محدودة أو منحنيات بيانية مناسبة. على سبيل المثال:
Binius يتضمن خمس تقنيات رئيسية:
الحساب القائم على مجال ثنائي البرج: يشكل أساس الحساب، ويحقق العمليات المبسطة ضمن المجال الثنائي
إعادة صياغة فحص المنتج والاستبدال لـ HyperPlonk: ضمان فحص الكفاءة المتسقة بين المتغيرات والاستبدالات
برهان التحول المتعدد الخطي الجديد: تحسين كفاءة التحقق من العلاقات المتعددة الخطية على مجالات صغيرة
تحسين دليل بحث Lasso: توفير المرونة والأمان لآلية البحث
نظام الالتزام متعدد الحدود في المجال الصغير: تحقيق نظام إثبات فعال في المجال الثنائي، وتقليل النفقات المتعلقة بالمجال الكبير
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثلي])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 الحقول المحدودة: الحساب القائم على أبراج الحقول الثنائية
النطاق الثنائي البرجي هو مفتاح لتحقيق حسابات سريعة قابلة للتحقق، وذلك بسبب الكفاءة العالية في الحسابات والكفاءة العالية في الحسابات الرياضية. يدعم النطاق الثنائي بشكل أساسي عمليات حسابية عالية الكفاءة، مما يجعله الخيار المثالي لتطبيقات التشفير الحساسة للأداء. تدعم بنية النطاق الثنائي عملية حسابية مبسطة، حيث يمكن تمثيل العمليات المنفذة على النطاق الثنائي بشكل جبرية مضغوطة وسهلة التحقق. هذه الخصائص، بالإضافة إلى القدرة على الاستفادة الكاملة من خصائصها الهرمية من خلال الهيكل البرجي، تجعل النطاق الثنائي مناسبًا بشكل خاص لأنظمة الإثبات القابلة للتوسع مثل Binius.
"canonical" تشير إلى طريقة العرض الفريدة والمباشرة لعناصر المجال الثنائي. على سبيل المثال، في المجال الثنائي الأساسي F2، يمكن أن يتم ربط أي سلسلة مكونة من k بت مباشرة بعنصر من عناصر المجال الثنائي المكون من k بت. هذا يختلف عن المجال الأولي، حيث لا يمكن للمجال الأولي أن يقدم هذا النوع من العرض القياسي ضمن عدد محدد من البتات. على الرغم من أن المجال الأولي المكون من 32 بت يمكن أن يتضمن ضمن 32 بت، إلا أنه ليس كل سلسلة مكونة من 32 بت يمكن أن تتوافق بشكل فريد مع عنصر من عناصر المجال، بينما يتمتع المجال الثنائي بهذه السهولة في الربط الواحد لواحد.
في مجال الأعداد الأولية Fp، تشمل طرق الاختزال الشائعة اختزال Barrett، واختزال Montgomery، بالإضافة إلى طرق الاختزال الخاصة المحددة مثل Mersenne-31 أو Goldilocks-64. في المجال الثنائي F2k، تشمل طرق الاختزال الشائعة اختزال خاص ( مثل AES يستخدم )، واختزال Montgomery ### مثل POLYVAL يستخدم (، واختزال متكرر ) مثل Tower (.
تشير الورقة "استكشاف مساحة تصميم تنفيذات الأجهزة ECC في الحقول الأولية مقابل الحقول الثنائية" إلى أنه لا حاجة لإدخال الحمل في عمليات الجمع والضرب في الحقل الثنائي، وأن عملية التربيع في الحقل الثنائي فعالة للغاية، لأنها تتبع قاعدة التبسيط )X + Y(2 = X2 + Y2.
يمكن تفسير سلسلة مكونة من 128 بت بطرق متعددة في سياق مجال ثنائي. يمكن اعتبارها عنصرًا فريدًا في مجال ثنائي مكون من 128 بت، أو تحليلها إلى عنصرين من عناصر مجال البرج بحجم 64 بت، أو أربعة عناصر من عناصر مجال البرج بحجم 32 بت، أو ستة عشر عنصرًا بحجم 8 بت، أو 128 عنصرًا من عناصر مجال F2. هذه المرونة في التمثيل لا تتطلب أي نفقات حسابية، بل هي مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة للاهتمام ومفيدة. في الوقت نفسه، يمكن تعبئة عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى نفقات حسابية إضافية. يستفيد بروتوكول Binius من هذه الميزة لتعزيز كفاءة الحساب.
تناقش الورقة "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد حساب عمليات الضرب والتربيع والعكس في النطاقات الثنائية البرجية ذات n بت، حيث يمكن تحليل ) إلى نطاق فرعي m بت (.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(
) 2.2 PIOP: نسخة معدلة من منتج HyperPlonk وPermutationCheck------مناسبة للمجال الثنائي
استلهم تصميم PIOP في بروتوكول Binius من HyperPlonk، حيث يعتمد على مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمجموعات المتعددة المتغيرات:
GateCheck: التحقق من أن الشهادة السرية ω والمدخلات العامة x تستوفي علاقة عمليات الدائرة C(x,ω)=0، لضمان التشغيل الصحيح للدائرة.
PermutationCheck: التحقق من ما إذا كانت نتائج تقييم كثيرات الحدود المتعددة المتغيرات f و g على المكعب الكبير البولياني هي علاقة تبديلية f###x( = f)π(x)(، لضمان اتساق ترتيب المتغيرات في كثيرات الحدود.
LookupCheck: التحقق من أن تقييم متعددة الحدود موجود في جدول البحث المعطى، أي f(Bμ) ⊆ T)Bμ(، لضمان أن بعض القيم ضمن النطاق المحدد.
MultisetCheck: تحقق من ما إذا كانت مجموعتان متعددتان متساويتان، أي {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H، لضمان التناسق بين المجموعات المتعددة.
ProductCheck: تحقق مما إذا كان تقييم كثيرات الحدود الجذرية على مكعب بولي يساوي قيمة معينة تم الإعلان عنها ∏x∈Hμ f)x( = s، تأكد من صحة حاصل الضرب كثيرات الحدود.
ZeroCheck: تحقق مما إذا كانت أي نقطة متعددة المتغيرات متعددة الحدود على مكعب بولي هي صفر ∏x∈Hμ f)x( = 0, ∀x ∈ Bμ, لضمان توزيع نقاط الصفر للمتعددات الحدودية.
SumCheck: التحقق من ما إذا كانت قيمة مجموع المتعددات المتغيرة تساوي القيمة المعلنة ∑x∈Hμ f)x( = s. من خلال تحويل مشكلة تقييم المتعددات المتغيرة إلى تقييم متعددات المتغيرات البسيطة، يتم تقليل تعقيد الحساب للجهة التي تتحقق. بالإضافة إلى ذلك، يسمح SumCheck أيضًا بالمعالجة الجماعية، من خلال إدخال أرقام عشوائية، لبناء تركيبات خطية لتحقيق المعالجة الجماعية لعدة حالات من التحقق من المجموع.
BatchCheck: استنادًا إلى SumCheck، للتحقق من صحة تقييمات متعددة للعديد من المتغيرات المتعددة، من أجل تحسين كفاءة البروتوكول.
على الرغم من أن Binius و HyperPlonk لديهما العديد من أوجه التشابه في تصميم البروتوكول، إلا أن Binius قد أحدث تحسينات في 3 مجالات التالية:
تحسين ProductCheck: في HyperPlonk، يتطلب ProductCheck أن يكون المقام U غير صفري في كل مكان على المكعب الفائق، ويجب أن يكون الناتج مساوياً لقيمة معينة؛ قام Binius بتبسيط هذه العملية عن طريق تخصيص هذه القيمة إلى 1، مما يقلل من تعقيد الحساب.
معالجة مشكلة القسمة على الصفر: لم تتمكن HyperPlonk من معالجة حالات القسمة على الصفر بشكل كافٍ، مما أدى إلى عدم القدرة على التأكيد على أن U غير صفري على الهيكل الفائق؛ عالجت Binius هذه المشكلة بشكل صحيح، حتى في حالة كون المقام صفراً، حيث يمكن لـ ProductCheck من Binius الاستمرار في المعالجة، مما يسمح بالتعميم إلى أي قيمة حاصل ضرب.
فحص التبديل بين الأعمدة: HyperPlonk لا يدعم هذه الخاصية؛ بينما يدعم Binius إجراء فحص التبديل بين عدة أعمدة، مما يمكّن Binius من التعامل مع حالات ترتيب متعددة الحدود الأكثر تعقيدًا.
لذلك، قامت Binius من خلال تحسين آلية PIOP SumCheck الحالية، بزيادة مرونة وكفاءة البروتوكول، خاصة عند معالجة التحقق من متعددات الحدود المتعددة المتغيرات الأكثر تعقيدًا، مما يوفر دعمًا وظيفيًا أقوى. لم تحل هذه التحسينات فقط قيود HyperPlonk، بل وضعت أيضًا أساسًا لأنظمة الإثبات القائمة على الحقول الثنائية في المستقبل.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل])https://img-cdn.gateio.im/webp-social/moments-d74bdd8bc21dcfc05e21f9c0074461c3.webp(
) 2.3 PIOP: حجة التحول المتعدد الخطوط الجديدة ------ تنطبق على الهيبركيوب البولياني
في بروتوكول Binius، يعد بناء ومعالجة البولينومات الافتراضية واحدة من التقنيات الرئيسية، حيث يمكنها بشكل فعال توليد ومعالجة البولينومات المشتقة من مقبض الإدخال أو البولينومات الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان:
Packing: هذه الطريقة تعمل على تحسين العمليات من خلال تعبئة العناصر الأصغر المجاورة في ترتيب القاموس لخلق عناصر أكبر. يتم استهداف عملية Pack لكتل بحجم 2κ، وتجمعها في عنصر واحد في مجال عالي الأبعاد. من خلال التمديد المتعدد الخطوط (Multilinear Extension، MLE)، يمكن تقييم هذا متعدد الحدود الافتراضي ومعالجته بكفاءة، مما يحول الدالة t إلى متعدد حدود آخر، وبالتالي يعزز أداء الحوسبة.
عوامل الإزاحة: تعيد عوامل الإزاحة ترتيب عناصر الكتل، بناءً على إزاحة معينة o، وتقوم بإزاحة دورانية. هذه الطريقة مناسبة للكتل بحجم 2b، حيث يتم تنفيذ الإزاحة لكل كتلة بناءً على الإزاحة. يتم تعريف عوامل الإزاحة من خلال دعم وظيفة الكشف، لضمان الاتساق والكفاءة عند معالجة متعددة الحدود الافتراضية. تنمو تعقيد تقييم هذا البناء خطيًا مع حجم الكتلة، مما يجعلها مناسبة بشكل خاص لمعالجة مجموعات البيانات الكبيرة أو المشاهد عالية الأبعاد في فرط مكعب البولي.
! [أبحاث Bitlayer: تحليل مبدأ Binius STARKs والتفكير الأمثل]###https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp(
) 2.4 PIOP: إصدار معدّل حجة بحث Lasso ------ مناسب لنطاق ثنائي
تسمح بروتوكولات Lasso للجهة المثبتة بالتعهد بمتجه a ∈ Fm، وإثبات أن جميع عناصره موجودة في جدول محدد مسبقًا t ∈ Fn. يفتح Lasso مفهوم "البحث عن الشذوذ" (lookup singularities)، ويمكن تطبيقه على مخططات التعهدات متعددة الحدود متعددة الخطوط. تظهر كفاءته في الجانبين التاليين: