السبب الرئيسي لانخفاض كفاءة STARKs هو: أن معظم القيم في البرامج الفعلية صغيرة، مثل الفهارس في الحلقات التكرارية، والقيم المنطقية، والعدادات، وغيرها. ومع ذلك، لضمان أمان الإثباتات المستندة إلى أشجار ميركل، عند استخدام ترميز ريد-سولومون لتوسيع البيانات، ستشغل العديد من القيم الزائدة الإضافية المجال بأكمله، حتى لو كانت القيم الأصلية صغيرة جدًا. لحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تبلغ عرض ترميز STARKs الجيل الأول 252 بت، بينما يبلغ عرض ترميز STARKs الجيل الثاني 64 بت، ويبلغ عرض ترميز STARKs الجيل الثالث 32 بت، ومع ذلك لا يزال هناك الكثير من المساحة المهدرة في عرض ترميز 32 بت. بالمقارنة، يسمح المجال الثنائي بالعمليات المباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا بدون أي مساحة مهدرة، وهو الجيل الرابع من STARKs.
بالمقارنة مع Goldilocks و BabyBear و Mersenne31 وغيرها من الاكتشافات البحثية الجديدة في السنوات الأخيرة في النطاقات المحدودة، فإن البحث في النطاقات الثنائية يعود إلى الثمانينات من القرن الماضي. في الوقت الحالي، تم تطبيق النطاقات الثنائية على نطاق واسع في علم التشفير، ومن الأمثلة النموذجية على ذلك:
معيار التشفير المتقدم ( AES ) ، يعتمد على مجال F28؛
Galois رمز التحقق من الرسالة ( GMAC ) ، بناءً على مجال F2128 ؛
رمز الاستجابة السريعة، يستخدم ترميز ريد-سولومون القائم على F28؛
البروتوكولات الأصلية FRI و zk-STARK، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى نهائيات SHA-3، والتي تستند إلى مجال F28، وهي خوارزمية تجزئة مناسبة للغاية للتكرار.
عند استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. بينما يعتمد المجال الثنائي المستخدم من قبل Binius تمامًا على توسيع المجال لضمان أمانه وقابليته للاستخدام الفعلي. معظم الحدود متعددة الحدود المتعلقة بحساب Prover لا تحتاج للدخول في توسيع المجال، بل يمكن أن تعمل فقط ضمن المجال الأساسي، مما يحقق كفاءة عالية في المجالات الصغيرة. ومع ذلك، لا يزال يتعين على فحص النقاط العشوائية وحساب FRI التعمق إلى مجالات توسيع أكبر لضمان الأمان المطلوب.
عند بناء نظام إثبات قائم على المجال الثنائي، هناك مشكلتان عمليتان: عند حساب تمثيل trace في STARKs، يجب أن يكون حجم المجال أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة 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 خمس تقنيات رئيسية لتحقيق كفاءته وسلامته. بادئ ذي بدء ، يشكل الحساب القائم على أبراج الحقول الثنائية أساس حساباته ، والتي يمكن أن تحقق عمليات مبسطة في الحقول الثنائية. ثانيا ، في بروتوكول Oracle Proof التفاعلي (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 لمجال الأعداد الأولية مقابل المجال الثنائي" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية مربع المجال الثنائي فعالة للغاية، لأنها تتبع القاعدة المبسطة (X + Y )2 = X2 + Y 2.
كما هو موضح في الشكل 1، سلسلة بطول 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق مجال ثنائي. يمكن اعتبارها عنصرًا فريدًا في مجال ثنائي من 128 بت، أو يمكن تحليلها إلى عنصرين من مجال برج بطول 64 بت، أو أربعة عناصر من مجال برج بطول 32 بت، أو ستة عشر عنصرًا من مجال برج بطول 8 بت، أو 128 عنصرًا من مجال F2. إن مرونة هذا التمثيل لا تتطلب أي تكلفة حسابية، بل هي مجرد تحويل نوع لسلسلة البتات، وهي خاصية مثيرة للاهتمام ومفيدة للغاية. في الوقت نفسه، يمكن تعبئة عناصر المجال الصغيرة في عناصر مجال أكبر دون الحاجة إلى تكلفة حسابية إضافية. يستفيد بروتوكول Binius من هذه الخاصية لتعزيز كفاءة الحساب. بالإضافة إلى ذلك، تستكشف الورقة البحثية "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحساب لعمليات الضرب والتربيع والعكس في مجال ثنائي برج بطول n (يمكن تقسيمه إلى مجال فرعي بطول m).
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µ، لضمان توزيع نقاط الصفر للحد polynomial.
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 من خلال تحسين آلية PIOPSumCheck الحالية، بزيادة مرونة وكفاءة البروتوكول، وخاصة عند التعامل مع التحقق من المتعددات المتغيرة المعقدة، حيث قدمت دعمًا وظيفيًا أقوى. لم تحل هذه التحسينات فقط قيود HyperPlonk، بل وضعت أيضًا الأساس لأنظمة الإثبات المستندة إلى المجال الثنائي في المستقبل.
2.3 PIOP：حجة التحول المتعدد الخطوط الجديدة------تنطبق على المكعبات البوليانية
في بروتوكول Binius، يعد بناء ومعالجة متعددات الحدود الافتراضية واحدًا من التقنيات الرئيسية، حيث يمكنه بشكل فعال توليد ومعالجة المتعددات المستمدة من مقبض الإدخال أو متعددات الحدود الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان:
التعبئة: تقوم هذه الطريقة بتحسين العمليات عن طريق تعبئة العناصر الأصغر المجاورة في ترتيب القاموس في عناصر أكبر. عملية Pack تستهدف العمليات على كتل بحجم 2κ وتقوم بتعبئتها
شاهد النسخة الأصلية
قد تحتوي هذه الصفحة على محتوى من جهات خارجية، يتم تقديمه لأغراض إعلامية فقط (وليس كإقرارات/ضمانات)، ولا ينبغي اعتباره موافقة على آرائه من قبل Gate، ولا بمثابة نصيحة مالية أو مهنية. انظر إلى إخلاء المسؤولية للحصول على التفاصيل.
تحليل مبادئ Binius STARKs: بناء نظام إثبات فعال في المجال الثنائي
تحليل مبادئ Binius STARKs والتفكير في تحسينها
1 المقدمة
السبب الرئيسي لانخفاض كفاءة STARKs هو: أن معظم القيم في البرامج الفعلية صغيرة، مثل الفهارس في الحلقات التكرارية، والقيم المنطقية، والعدادات، وغيرها. ومع ذلك، لضمان أمان الإثباتات المستندة إلى أشجار ميركل، عند استخدام ترميز ريد-سولومون لتوسيع البيانات، ستشغل العديد من القيم الزائدة الإضافية المجال بأكمله، حتى لو كانت القيم الأصلية صغيرة جدًا. لحل هذه المشكلة، أصبح تقليل حجم المجال استراتيجية رئيسية.
تبلغ عرض ترميز STARKs الجيل الأول 252 بت، بينما يبلغ عرض ترميز STARKs الجيل الثاني 64 بت، ويبلغ عرض ترميز STARKs الجيل الثالث 32 بت، ومع ذلك لا يزال هناك الكثير من المساحة المهدرة في عرض ترميز 32 بت. بالمقارنة، يسمح المجال الثنائي بالعمليات المباشرة على البتات، مما يجعل الترميز مضغوطًا وفعالًا بدون أي مساحة مهدرة، وهو الجيل الرابع من STARKs.
بالمقارنة مع Goldilocks و BabyBear و Mersenne31 وغيرها من الاكتشافات البحثية الجديدة في السنوات الأخيرة في النطاقات المحدودة، فإن البحث في النطاقات الثنائية يعود إلى الثمانينات من القرن الماضي. في الوقت الحالي، تم تطبيق النطاقات الثنائية على نطاق واسع في علم التشفير، ومن الأمثلة النموذجية على ذلك:
معيار التشفير المتقدم ( AES ) ، يعتمد على مجال F28؛
Galois رمز التحقق من الرسالة ( GMAC ) ، بناءً على مجال F2128 ؛
رمز الاستجابة السريعة، يستخدم ترميز ريد-سولومون القائم على F28؛
البروتوكولات الأصلية FRI و zk-STARK، بالإضافة إلى دالة التجزئة Grøstl التي وصلت إلى نهائيات SHA-3، والتي تستند إلى مجال F28، وهي خوارزمية تجزئة مناسبة للغاية للتكرار.
عند استخدام مجالات أصغر، تصبح عملية توسيع المجال أكثر أهمية لضمان الأمان. بينما يعتمد المجال الثنائي المستخدم من قبل Binius تمامًا على توسيع المجال لضمان أمانه وقابليته للاستخدام الفعلي. معظم الحدود متعددة الحدود المتعلقة بحساب Prover لا تحتاج للدخول في توسيع المجال، بل يمكن أن تعمل فقط ضمن المجال الأساسي، مما يحقق كفاءة عالية في المجالات الصغيرة. ومع ذلك، لا يزال يتعين على فحص النقاط العشوائية وحساب FRI التعمق إلى مجالات توسيع أكبر لضمان الأمان المطلوب.
عند بناء نظام إثبات قائم على المجال الثنائي، هناك مشكلتان عمليتان: عند حساب تمثيل trace في STARKs، يجب أن يكون حجم المجال أكبر من درجة كثير الحدود؛ وعند الالتزام بشجرة 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 خمس تقنيات رئيسية لتحقيق كفاءته وسلامته. بادئ ذي بدء ، يشكل الحساب القائم على أبراج الحقول الثنائية أساس حساباته ، والتي يمكن أن تحقق عمليات مبسطة في الحقول الثنائية. ثانيا ، في بروتوكول Oracle Proof التفاعلي (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 لمجال الأعداد الأولية مقابل المجال الثنائي" إلى أن المجال الثنائي لا يحتاج إلى إدخال حمل في عمليات الجمع والضرب، وأن عملية مربع المجال الثنائي فعالة للغاية، لأنها تتبع القاعدة المبسطة (X + Y )2 = X2 + Y 2.
كما هو موضح في الشكل 1، سلسلة بطول 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق مجال ثنائي. يمكن اعتبارها عنصرًا فريدًا في مجال ثنائي من 128 بت، أو يمكن تحليلها إلى عنصرين من مجال برج بطول 64 بت، أو أربعة عناصر من مجال برج بطول 32 بت، أو ستة عشر عنصرًا من مجال برج بطول 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، ويستخدم مجموعة من آليات الفحص الأساسية للتحقق من صحة المتعددات والمجموعات المتعددة المتغيرات. تشمل هذه الفحوصات الأساسية:
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µ، لضمان توزيع نقاط الصفر للحد polynomial.
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 من خلال تحسين آلية PIOPSumCheck الحالية، بزيادة مرونة وكفاءة البروتوكول، وخاصة عند التعامل مع التحقق من المتعددات المتغيرة المعقدة، حيث قدمت دعمًا وظيفيًا أقوى. لم تحل هذه التحسينات فقط قيود HyperPlonk، بل وضعت أيضًا الأساس لأنظمة الإثبات المستندة إلى المجال الثنائي في المستقبل.
2.3 PIOP：حجة التحول المتعدد الخطوط الجديدة------تنطبق على المكعبات البوليانية
في بروتوكول Binius، يعد بناء ومعالجة متعددات الحدود الافتراضية واحدًا من التقنيات الرئيسية، حيث يمكنه بشكل فعال توليد ومعالجة المتعددات المستمدة من مقبض الإدخال أو متعددات الحدود الافتراضية الأخرى. فيما يلي طريقتان رئيسيتان: