1. المقدمةمتميزة عن SNARKs القائمة على منحنى البيضاوي، يمكن النظر إلى STARKs على أنها SNARKs قائمة على التجزئة. واحدة من التحديات الرئيسية التي تسهم في الكفاءة الحالية ل STARKs هو أن معظم القيم في البرامج الفعلية صغيرة نسبيا، مثل المؤشرات في حلقات البرمجة، وقيم بوليانية، وعدادات. ومع ذلك، لضمان أمان البراهين القائمة على شجرة Merkle، يتم استخدام ترميز Reed-Solomon لتوسيع البيانات، مما يؤدي إلى العديد من القيم الزائدة التي تشغل المجال بأكمله، حتى عندما تكون القيم الأصلية أنفسها صغيرة. معالجة هذه الكفاءة، وتقليل حجم المجال أصبحت استراتيجية رئيسية.
كما هو موضح في الجدول 1، كان لدى الجيل الأول من STARKs عرض ترميزي يبلغ 252 بتًا، والجيل الثاني 64 بتًا، والجيل الثالث 32 بتًا. على الرغم من العرض الترميزي المخفض في الجيل الثالث، إلا أن هناك مساحة ضائعة كبيرة. على العكس من ذلك، تسمح الحقول الثنائية بالتلاعب المباشر على مستوى البت، مما يتيح الترميز المدمج والفعال مع الحد الأدنى من الفاقد. يتم تحقيق هذه الكفاءة في الجيل الرابع من STARKs.
الجدول 1: مسار استقراربالمقارنة مع المجالات المحدودة مثل Goldilocks و BabyBear و Mersenne31 التي اكتسبت اهتمامًا مؤخرًا، تعود أبحاث المجالات الثنائية إلى الثمانينيات. اليوم، يتم استخدام المجالات الثنائية على نطاق واسع في التشفير، مع أمثلة ملحوظة بما في ذلك:
- معيار التشفير المتقدم (AES)، استنادًا إلى- 𝐹28- حقل؛- رمز المصادقة الرسالية جالوا (GMAC)، المعتمد على الـ gate- 𝐹2128- حقل;- رموز الاستجابة السريعة، التي تستخدم ترميز Reed-Solomon استنادًا إلى ال- إف 28- حقل;- البروتوكولات الأصلية FRI و zk-STARK، وكذلك وظيفة التجزئة Grøstl، وهي وظيفة نهائية في منافسة SHA-3، والتي تعتمد على - 𝐹28- حقل ومناسب تماماً لخوارزميات التجزئة التكرارية.عند استخدام حقول أصغر، تصبح عمليات توسيع الحقل أكثر أهمية لضمان الأمان. يعتمد الحقل الثنائي المستخدم من قبل Binius بالكامل على توسيع الحقل لضمان الأمان والقابلية العملية. معظم عمليات حسابات الجداول الأحادية المتضمنة في عمليات Prover لا تحتاج إلى دخول الحقل الموسع، حيث أنها تحتاج فقط للعمل في الحقل الأساسي، مما يحقق كفاءة عالية في الحقل الصغير. ومع ذلك، يجب أن تُجرى لا تزال عمليات التحقق من النقطة العشوائية وحسابات FRI في حقل موسع أكبر لضمان المستوى الضروري من الأمان.
هناك تحديان عمليان عند بناء نظام دليل يعتمد على حقول ثنائية: الأول، يجب أن يكون حجم الحقل المستخدم لتمثيل التتبع في STARKs أكبر من درجة الدالة. الثاني، يجب أن يكون حجم الحقل المستخدم للتزام شجرة Merkle في STARKs أكبر من الحجم بعد تمديد الترميز Reed-Solomon.
بينيوس هو حلاً مبتكرًا لمعالجة هذين المشكلتين عن طريق تمثيل نفس البيانات بطريقتين مختلفتين: أولاً، من خلال استخدام الدوال الجبرية المتعددة (وتحديداً الدوال الجبرية المتعددة الخطية) بدلاً من الدوال الجبرية الأحادية، التي تمثل سجل الحساب بأكمله من خلال تقييماتها على "الهايبركيوبس". ثانياً، نظرًا لأن كل بُعد من أبعاد الهايبركيوب له طول يبلغ 2، فإنه ليس من الممكن أداء تمديدات Reed-Solomon القياسية مثل في STARKs، ولكن يمكن معالجة الهايبركيوب على أنه مربع، ويمكن إجراء تمديد Reed-Solomon استنادًا إلى هذا المربع. هذه الطريقة لا تضمن الأمان فحسب، بل تعزز بشكل كبير من كفاءة الترميز والأداء الحسابي.
مبادئ بينيوس 2.بناء معظم أنظمة SNARK الحديثة عادة يتكون من المكونين التاليين:
-
إثبات أوراكل التفاعلي متعدد الحدود متعدد الحدود (PIOP): باعتباره جوهر نظام الإثبات ، يحول PIOP العلاقات الحسابية من المدخلات إلى معادلات متعددة الحدود يمكن التحقق منها. تسمح بروتوكولات PIOP المختلفة للبروفير بإرسال كثيرات الحدود بشكل تدريجي من خلال التفاعلات مع المدقق. يتيح ذلك للمدقق تأكيد صحة الحساب عن طريق الاستعلام عن عدد صغير فقط من التقييمات متعددة الحدود. تتعامل بروتوكولات PIOP المختلفة ، مثل PLONK PIOP و Spartan PIOP و HyperPlonk PIOP ، مع التعبيرات متعددة الحدود بشكل مختلف ، مما يؤثر على أداء وكفاءة نظام SNARK العام.- نظام الالتزام بالمتعددات الحدود (PCS): PCS هو أداة تشفيرية تستخدم لإثبات صحة المعادلات المتعددة التي يولدها PIOP. يتيح للمثبت الالتزام بمتعدد والتحقق من تقييماته دون الكشف عن معلومات إضافية حول المتعدد. تشمل أمثلة نظم PCS KZG و Bulletproofs و FRI (Fast Reed-Solomon IOPP) و Brakedown ، والتي تقدم خصائص أداء متميزة وضمانات أمان وسيناريوهات قابلة للتطبيق.من خلال اختيار برامج PIOPs و PCS المختلفة ودمجها مع حقول متناهية المناسب أو المنحنيات البيضاوية، يمكن للشخص بناء أنظمة إثبات بخصائص متميزة. على سبيل المثال:
-
Halo2: يجمع بين PLONK PIOP مع Bulletproofs PCS ويعمل على منحنى الباستا. تم تصميم Halo2 مع القابلية للتوسع في الاعتبار ويقضي على الإعداد الموثوق المستخدم سابقًا في بروتوكول ZCash.- Plonky2: يجمع بين PLONK PIOP مع FRI PCS ويستند إلى مجال جولديلوكس. Plonky2 محسنة للتكرار الفعال.عند تصميم هذه الأنظمة، تعد التوافقية بين PIOP و PCS والحقل المحدد أو المنحنى البيضاوي أمرًا حاسمًا لضمان الصحة والأداء والأمان. تؤثر هذه التركيبات على حجم دليل SNARK، وكفاءة التحقق، وتحدد ما إذا كان يمكن للنظام تحقيق الشفافية بدون إعداد موثوق به، بالإضافة إلى دعم ميزات متقدمة مثل البراهين التكرارية أو تجميع البراهين.
يجمع Binius بين HyperPlonk PIOP مع Brakedown PCS ويعمل في حقل ثنائي. على وجه التحديد ، يدمج Binius خمس تقنيات رئيسية لتحقيق الكفاءة والأمان:
- الحسابات الحسابية القائمة على أبراج الحقول الثنائية: تشكل الأساس الحسابي لـ Binius، مما يسمح بالعمليات المبسطة داخل الحقل الثنائي.- فحوصات منتج HyperPlonk والتحويل: يقوم Binius بتكييف فحوصات منتج HyperPlonk والتحويل في PIOP الخاص به لضمان الاتساق الآمن والفعال بين المتغيرات وتحويلاتها.- حجة تحويلية متعددة الخطوط جديدة: تحسين هذا الأمر يعزز التحقق من العلاقات المتعددة الخطوط داخل الحقول الصغيرة، مما يعزز الكفاءة العامة.- حجة بحث لاسو المحسنة: يتضمن البروتوكول آلية بحث أكثر مرونة وأمانًا مع هذه الحجة المتقدمة.- نظام الالتزام بمتعهد الشرط الرياضي الحقل الصغير (PCS): يستخدم Binius PCS مصمم خصيصًا للحقول الصغيرة ، مما يقلل من الفوائض المرتبطة عادة بالحقول الأكبر حجمًا ويمكن نظام إثبات فعال في الحقل الثنائي.تمكن هذه الابتكارات بينيوس من تقديم نظام SNARK صغير الحجم وعالي الأداء ، محسن للحقول الثنائية مع الحفاظ على الأمان والقابلية للتوسعة القوية.
2.1 الحقول المحدودة: الحسابات المبنية على أبراج الحقول الثنائيةأبراج الحقول الثنائية تلعب دورًا حاسمًا في تحقيق الحسابات السريعة والقابلة للتحقق بسبب عاملين أساسيين: الحساب الفعال والتعميم الفعال. تدعم الحقول الثنائية بشكل جوهري عمليات الحساب الفعالة للغاية، مما يجعلها مثالية لتطبيقات التشفير الحساسة للأداء. علاوة على ذلك، تسمح هيكلتها بعملية تعميم مبسطة، حيث يمكن تمثيل العمليات المنفذة في الحقول الثنائية بأشكال جبرية مدمجة وسهلة التحقق. هذه الخصائص، جنبًا إلى جنب مع الهيكل الهرمي لأبراج الحقول الثنائية، يجعلها مناسبة بشكل خاص لأنظمة الإثبات المقياسة مثل Binius.
يشير مصطلح "الكانوني" إلى التمثيل الفريد والمباشر للعناصر في مجال ثنائي. على سبيل المثال، في أبسط مجال ثنائي $\mathbb{F}2
,anyk−bitstringcanbedirectmappedtoak−bitbinaryfieldelement.Thisdiffersfromprimefields,whichdonotoffersuchacanonicalrepresentationwithinagivennumberofbits.Althougha32−bitprimefieldcanfitin32bits,notevery32−bitstringcanuniquelycorrespondtoafieldelement,wherebinaryfieldsprovidethisone−to-onemapping.Inprimefields
في الحقول المحددة $\mathbb{F}_p$ ، تشمل أساليب التقليل الشائعة تقليل باريت ، تقليل مونتغمري ، بالإضافة إلى أساليب تقليل متخصصة لبعض الحقول المحددة مثل Mersenne-31 أو Goldilocks-64. في الحقول الثنائية $\mathbb{F}{2^k}$ ، تشمل أساليب التقليل الشائعة التقليل الخاص (كما يتم استخدامه في AES) ، وتقليل مونتغمري (كما يتم استخدامه في POLYVAL) ، والتقليل العودي (كما يتم استخدامه في حقول البرج). الورقة استكشاف مساحة التصميم لتنفيذات الأجهزة لمجال الأعداد الأولية مقابل مجال الأعداد الثنائية للتشفير الأحادي القطبملاحظات أن حقول الباينري لا تتطلب نقل الرفع في الجمع أو الضرب ، والتربيع في حقول الباينري فعال جدًا بسبب قاعدة التبسيط.
(𝑋+𝑌)2=𝑋2+𝑌2
.
الشكل 1. أبراج الحقل الثنائي
كما هو موضح في الشكل 1، يمكن تفسير سلسلة بت بطول 128 بت بطرق متعددة داخل سياق حقل ثنائي. يمكن رؤيتها كعنصر فريد في حقل بت بطول 128 بت، أو يمكن تفسيرها كعنصري حقل بت بطول 64 بت، أو أربع عناصر حقل بت بطول 32 بت، أو ستة عشر عنصر حقل بت بطول 8 بت، أو 128 عنصر من
𝐹2
. هذه المرونة في التمثيل لا تؤدي إلى أي تكاليف حسابية، حيث أنها مجرد تحويل لنوع السلسلة الثنائية. هذه خاصية مثيرة للاهتمام ومفيدة جدًا، حيث يمكن تعبئة عناصر الحقل الأصغر حجمًا في عناصر الحقل الأكبر دون أي تكلفة حسابية إضافية. يستفيد بروتوكول بينيوس من هذه الخاصية لتعزيز كفاءة الحوسبة. وعلاوة على ذلك، الورقة في التحويل الفعال في حقول البرج من الطابع الثانييستكشف تعقيد الحساب في الضرب والتربيع والانقلاب في
𝑛
- حقول البت الثنائية في برج (يمكن تحليلها إلى
𝑚
2.2 PIOP: منتج HyperPlonk المكيف والتحقق من التبديل - مناسب للحقول الثنائيةتستلهم تصميم PIOP في بروتوكول Binius من HyperPlonk وتدمج سلسلة من الفحوصات الأساسية للتحقق من صحة البولينومات والمجموعات المتعددة المتغيرات. تعد هذه الفحوصات أساسية لضمان سلامة الحسابات داخل نظام البرهان ، خاصةً عند العمل في حقول ثنائية. تشمل الفحوص الرئيسية:
-
gateCheck: يضمن أن الشاهد الخاص- 𝜔- والمدخلات العامة- 𝑥- يُرضي علاقة عملية الدائرة- 𝐶(𝑥,𝜔)=0- ، التحقق من تنفيذ الدائرة بشكل صحيح.- PermutationCheck: يتحقق من نتائج التقييم لمتعددات الحدود الجبرية لمتعددين- 𝑓- و- 𝑔- على مكعب بولياني تشكيل علاقة تبعيض- f (x) = f (π (x))- ، مما يضمن تماسك المتغيرات الكثيرية.- LookupCheck: يتحقق مما إذا كان تقييم متعدد الحدود ضمن جدول بحث معين، أي، - 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)- ، مع ضمان أن بعض القيم تقع ضمن نطاق محدد.- MultisetCheck: يؤكد ما إذا كانت مجموعتين متعددة المتغيرات متساويتين، أي ${(x*{1,i},x*{2, i})} {i \in H} = {(y{1, i}, y*{2، i})}*{i \in H}$، مما يضمن التوافق بين مجموعات مختلفة.- ProductCheck: يضمن أن تساوي تقييم متعدد الحدود النسبي على المكعب البولياني قيمة معلن عنها، أي،- ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- ، مؤكدا صحة منتج الجداء العلمي.- ZeroCheck: يتحقق مما إذا كان متعدد المتغيرات الجملة يقيم إلى الصفر في أي نقطة على المكعب البولياني ، أي ، - ∏𝑥∈𝐻𝜇𝑓(𝑥)=0- للجميع- 𝑥∈𝐵𝜇- ، ضمان توزيع صحيح للأصفار في العديد الجبري.- SumCheck: يؤكد ما إذا كان مجموع تقييمات متعددة الحدود متساويًا مع القيمة المعلنة، أي،- ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- . من خلال تقليل تقييم متعدد المتغيرات إلى تقييم متعدد المتغيرات، يقلل من تعقيد الحساب للتحقق. يسمح SumCheck أيضًا بالدُفعة، والتي تُنشئ مجموعات خطية باستخدام أرقام عشوائية لمعالجة مجموعات متعددة.- BatchCheck: إضافة لـ SumCheck، يتحقق من صحة تقييمات الجبر المتعددة المتعددة، مما يزيد كفاءة البروتوكول.بينيوس وهايبربلونك يشاركان العديد من التشابهات في تصميم بروتوكولهما، ولكن بينيوس يقدم التحسينات الرئيسية التالية:
-
تحسين فحص المنتج: في هايبربلونك، يتطلب فحص المنتج المقام- 𝑈- أن يكون غير صفر عبر المكعب الفائق بأكمله، وأن يتطابق المنتج مع قيمة محددة. يبسط بينيوس هذا الفحص عن طريق تعيين قيمة المنتج إلى 1، مما يقلل من تعقيد الحساب العام.- معالجة مشكلات القسمة على الصفر: لا يتعامل HyperPlonk بشكل فعال مع مشاكل القسمة على الصفر ، مما يجعل من الصعب ضمان أن - 𝑈- يظل غير الصفر عبر الهايبركيوب. يقوم بينيوس بحل هذا الأمر عن طريق التعامل مع سيناريوهات قسمة الصفر بشكل مناسب، مما يتيح لـ ProductCheck العمل حتى عندما يكون المقام صفرًا، مما يسمح بالتوسع إلى قيم المنتجات التعسفية.- التحقق من تبديل الأعمدة المتقاطعة: هايبربلونك لا يدعم التحقق من تبديل الأعمدة المتقاطعة. يعالج بينيوس هذا القيد من خلال إدخال دعم للتحقق من تبديل الأعمدة المتقاطعة ، مما يمكّن البروتوكول من إدارة تبديلات متعددة المعاملات أكثر تعقيدًا عبر عدة أعمدة.وبالتالي، يعزز بينيوس مرونة وكفاءة البروتوكول من خلال تحسين آلية التحقق من PIOP SumCheck الحالية، لا سيما من خلال توفير وظائف أقوى للتحقق من المتعددات الأكثر تعقيدا. هذه التحسينات لا تعالج فقط القيود المتعلقة بـ HyperPlonk بل تؤسس أيضا لأنظمة مستقبلية مقاومة مستندة إلى حقول ثنائية.
2.3 PIOP: حجة تحويلية جديدة متعددة الخطوط - قابلة لتطبيق الهيبركيوب البوليانيفي بروتوكول بينيوس، تلعب عملية التلاعب وبناء الجمل السياسية الافتراضية دورًا حاسمًا في تمكين التعامل الفعال مع الجمل السياسية. يتم استخدام تقنيتين رئيسيتين لهذه العمليات:
- التعبئة: تحسين طريقة التعامل مع العناصر الأصغر من خلال تجميعها معًا في مجال أكبر. على وجه التحديد ، يتم تعبئة العناصر المجاورة في ترتيب لغوي في كتل أكبر ، عادةً بحجم- 2𝜅- . بالاستفادة من تمديد متعدد الخطوط (MLE)، يتم تحويل العناصر المعبأة إلى متعدد الحدود الجديد، والذي يمكن تقييمه ومعالجته بكفاءة. تعزز هذه الطريقة أداء العمليات على المكعب البولياني من خلال إعادة هيكلة الوظيفة - 𝑡- إلى شكل فعال حسابياً.- مشغل الانتقال: يقوم مشغل الانتقال بإعادة ترتيب العناصر داخل كتلة بتحويل تحويل دوري لها استنادًا إلى الإزاحة المعطاة- 𝑜- . ينطبق هذا التحول على كتل بحجم - 2𝑏- ، مما يضمن أن جميع العناصر في الكتلة تتحرك بشكل موحد وفقًا للإزاحة المحددة مسبقًا. يكون هذا المشغل مفيدًا بشكل خاص عند التعامل مع البولينوميات الافتراضية في الفضاء ذي الأبعاد العالية، حيث يزيد تعقيده بشكل خطي مع حجم الكتلة، مما يجعله تقنية مثالية لمجموعات البيانات الكبيرة أو الحسابات المعقدة للهايبركيوب بوليانية.### 2.4 PIOP: وسيط تحقق آرجومنت معدل لاسو - قابل للتطبيق على الحقول الثنائيةيوفر بروتوكول Lasso في Binius طريقة فعالة للغاية لإثبات أن العناصر في الفيكتور.
𝑎∈𝐹𝑚
تحتوي على جدول محدد مسبقاً
𝑡∈𝐹𝑛
يقدم هذا الوسيط وسيلة لفهم مفهوم "الاستدلال الفريد" وهو مناسب تمامًا لمخططات الالتزام الجبرية متعددة الأبعاد. تُسلط الضوء على كفاءة لاسو في جانبين رئيسيين:
-
كفاءة الإثبات: عند القيام ب- 𝑚- البحث في جدول بحجم - 𝑛- ، يحتاج المثبت فقط إلى الالتزام بـ- 𝑚+𝑛- عناصر حقل صغيرة، بحجم الحقل المستخرج من المجموعة- 0،…،𝑚- . في الخوارزميات التشفيرية التي تعتمد على التربيع، تكلفة المثبت هي - 𝑂(𝑚+𝑛)- العمليات الجماعية (مثل إضافة نقطة المنحنى البيضائي). تأتي هذه الكفاءة بالإضافة إلى تكلفة التحقق مما إذا كان متعدد الخطوط العريضة محددًا على الفضاء الهايبر مطابقًا لعنصر الجدول.- عدم التزام بالجداول الكبيرة: إذا كانت الجدول- 𝑡- هيكل متين، لا تتطلب لاسو التزامًا مباشرًا بالجدول، مما يجعل من الممكن التعامل مع الجداول الكبيرة جدًا (على سبيل المثال، - 2128- أو أكثر). يعتمد وقت تشغيل البرهان على الإدخالات المحددة التي تم الوصول إليها في الجدول. بالنسبة لأي معلمة صحيحة،- 𝑐>1- , تتضمن التكلفة الرئيسية حجم الدليل، الذي يزداد كما ينمو- 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐- عناصر الحقل الملتزمة. هذه العناصر صغيرة أيضًا، مستمدة من المجموعة - 0,…، max𝑚، 𝑛1/𝑐، 𝑞−1- ، حيث - 𝑞- هو أكبر قيمة في الفيكتور- 𝑎- .يتكون بروتوكول لاسو من ثلاث مكونات أساسية:
-
تجريد متعدد الحدود للجداول الكبيرة: يجمع بروتوكول الحبل البولينومي الافتراضي بين البولينومات الظاهرية لتمكين البحث والعمليات الفعالة على الجداول الكبيرة، مما يضمن القابلية للتوسع دون التأثير على الأداء.- البحث في الجدول الصغير: في قلب لاسو يكمن البحث في الجدول الصغير، الذي يتحقق مما إذا كان مضلع متعدد الحدود افتراضي يقيم على مكعب بولينوميالي بولينومي آخر. هذه العملية تشبه الكشف عن الذاكرة في وضع عدم الاتصال وتنحصر في مهمة كشف مجموعة متعددة.- التحقق من الطرد المتعدد: يتضمن البروتوكول أيضًا آلية افتراضية لإجراء فحوصات للطرد المتعدد، مما يضمن أن مجموعتين من العناصر إما تتطابق أو تفي بشروط محددة مسبقًا.يقوم بروتوكول Binius بتكييف Lasso لعمليات الحقل الثنائي ، بافتراض أن الحقل الحالي هو حقل رئيسي ذو خاصية كبيرة (أكبر بكثير من طول العمود الذي يتم البحث عنه). يقدم Binius نسخة مضاعفة من بروتوكول Lasso ، مما يتطلب من prover و verifier زيادة عملية "عداد الذاكرة" للبروتوكول ليس فقط عن طريق إضافة 1 ولكن عن طريق الزيادة باستخدام مولد مضاعف داخل الحقل الثنائي. ومع ذلك ، فإن هذا التكيف المضاعف يقدم تعقيدا إضافيا: على عكس الزيادة المضافة ، لا يزداد المولد الضربي في جميع الحالات ، وبدلا من ذلك يكون له مدار واحد عند 0 ، مما قد يمثل متجه هجوم. للتخفيف من هذا الهجوم المحتمل ، يجب على البروفير الالتزام بناقل عداد قراءة غير صفري في كل مكان لضمان أمان البروتوكول.
2.5 PCS: الكسر المكيف للحقل PCS - ينطبق على الحقول الصغيرةالفكرة الأساسية وراء إنشاء بنيوس PCS (نظام الالتزام بالمتعددات الجذرية) هي التعبئة. يقدم ورقة بنيوس اثنين من مخططات Brakedown PCS استنادًا إلى حقول ثنائية: واحدة تم تنفيذها باستخدام رموز متسلسلة، وأخرى باستخدام ترميز على مستوى الكتلة، والتي تدعم استخدام Reed-Solomon codes بشكل منفصل. يبسط المخطط الثاني لـ Brakedown PCS عملية البرهان والتحقق، على الرغم من أنه ينتج حجمًا أكبر قليلاً من البرهان الأول؛ ومع ذلك، فإن هذا التضحية تستحقها بسبب التبسيط وفوائد التنفيذ التي يقدمها.
تستخدم التزام الجذري للجمع الثنائي بشكل أساسي التزام الجذري للمجال الصغير مع التقييمات في مجال موسع، والبناء العالمي للمجال الصغير، وترميز على مستوى الكتلة باستخدام تقنيات رمز ريد-سولومون.
تعهيدات متعددة الحقول الصغيرة بتقييم مدد الحقول الموسعة في بروتوكول Binius ، يتم تنفيذ التزامات الجملة فوق حقل صغير
𝐾
، مع إجراء التقييم في مجال موسع
L / ك
. تضمن هذه الطريقة أن متعدد الحدود متعدد الحدود
𝑡(𝑋0،…،𝑋ℓ−1)
ينتمي إلى المجال
𝐾[𝑋0،…،𝑋ℓ−1]
, بينما نقاط التقييم في المجال الأكبر
𝐿
. تمكّن هيكلية الالتزام هذه من استفسارات فعالة داخل الحقل الموسع، مع التوازن بين الأمان والكفاءة الحسابية.
البناء العالمي للحقل الصغير يحدد هذا البناء معلمات رئيسية مثل الحقل
𝐾
، أبعادها
ℓ
, ورمز الكتلة الخطية المرتبطة
𝐶
, مع ضمان الحقل الموسع
𝐿
كبير بما فيه الكفاية لتقييمات آمنة. من خلال الاستفادة من خصائص الحقل الموسع، يحقق بينيوس التزامات قوية من خلال رموز الكتل الخطية، محافظاً على توازن بين الكفاءة الحسابية والأمان.
ترميز مستوى الكتلة مع رموز ريد-سولومون للمتعددات المعرفة على حقول صغيرة مثل $\mathbb{F}2
,𝑡ℎ𝑒𝐵𝑖𝑛𝑖𝑢𝑠𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙𝑒𝑚𝑝𝑙𝑜𝑦𝑠𝑏𝑙𝑜𝑐𝑘−𝑙𝑒𝑣𝑒𝑙𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑢𝑠𝑖𝑛𝑔𝑅𝑒𝑒𝑑−𝑆𝑜𝑙𝑜𝑚𝑜𝑛𝑐𝑜𝑑𝑒𝑠.𝑇ℎ𝑖𝑠𝑠𝑐ℎ𝑒𝑚𝑒𝑎𝑙𝑙𝑜𝑤𝑠𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑜𝑓𝑠𝑚𝑎𝑙𝑙−𝑓𝑖𝑒𝑙𝑑𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙𝑠𝑏𝑦𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑡ℎ𝑒𝑚𝑟𝑜𝑤−𝑏𝑦−𝑟𝑜𝑤𝑖𝑛𝑡𝑜𝑙𝑎𝑟𝑔𝑒𝑟𝑓𝑖𝑒𝑙𝑑𝑠(𝑠𝑢𝑐ℎ𝑎𝑠
\mathbb{F}{2^{16}}$) ، مستفيدين من كفاءة وخصائص الفصل الأقصى للمسافة لأكواد ريد-سولومون. بعد الترميز ، يتم الالتزام بهذه الصفوف باستخدام شجرة ميركل ، مما يبسط تعقيد العمليات المرتبطة بالتزامات متعددة الحقول الصغيرة. يسمح هذا النهج بالتعامل الفعال مع متعددات الحدود في حقول صغيرة بدون الأعباء الحسابية المرتبطة عادة بالحقول الأكبر.
3. تحسينات بينيوسلتحسين الأداء بشكل أفضل، يتضمن بينيوس أربع تحسينات رئيسية:
- بروتوكول GKR PIOP: يتم استخدام بروتوكول GKR (Goldreich-Kalai-Rothblum) لاستبدال خوارزمية البحث بواسطة الحبل في عملية ضرب الحقل الثنائي، مما يقلل بشكل كبير من العبء في عملية الالتزام.- تحسين ZeroCheck PIOP: يتناول هذا التحسين التوازن بين تكاليف الحاسب للمثبت والتحقق، مما يجعل عملية ZeroCheck أكثر كفاءة من خلال توزيع عبء العمل بشكل أكثر فعالية.- تحسين Sumcheck PIOP: من خلال تحسين عملية Sumcheck في الحقل الصغير، يقلل Binius من العبء الحسابي الشامل عند العمل في الحقول الصغيرة.- التحسينات على PCS: باستخدام FRI-Binius (Fast Reed-Solomon Interactive Oracle Proofs of Proximity)، يقلل Binius من حجم الدليل ويعزز أداء البروتوكول، مما يحسن الكفاءة العامة في إنتاج الدليل والتحقق.### 3.1 GKR-based PIOP: عملية ضرب حقل ثنائي باستخدام GKRفي بروتوكول بينيوس الأصلي ، يتم التعامل مع ضرب الحقول الثنائية من خلال نظام يعتمد على البحث ، والذي يربط الضرب بعمليات الجمع الخطية على أساس عدد الأطراف في كلمة واحدة. على الرغم من أن هذه الطريقة تحسن ضرب الأعداد الثنائية إلى حد ما ، إلا أنها تقدم لا يزال التزامات مساعدة ذات علاقة خطية بعدد الأطراف. من خلال اعتماد نهج قائم على GKR ، يمكن لبروتوكول بينيوس تقليل بشكل كبير عدد الالتزامات المطلوبة ، مما يؤدي إلى مزيد من الكفاءة في عمليات ضرب الحقول الثنائية.
الفكرة الأساسية لبروتوكول GKR (Goldwasser-Kalai-Rothblum) هي تحقيق اتفاق بين البروفير (P) والتحقق (V) على دارة حسابية متدرجة على ميدان محدد
𝐹
. كل عقدة في هذا الدائرة لديها إدخالان لحساب الوظيفة المطلوبة. لتقليل تعقيد الحاسوب الخاص بالتحقق ، يستخدم البروتوكول بروتوكول SumCheck الذي يقلل تدريجياً من المطالبات حول قيم بوابات إخراج الدائرة إلى قيم بوابات الطبقة الأدنى ، مما يبسط المطالبات في النهاية إلى بيانات حول المدخلات. بهذه الطريقة ، يحتاج المحقق فقط إلى التحقق من صحة مدخلات الدائرة.
البوابةخوارزمية ضرب الأعداد الصحيحة بناءً على GKRفي Binius يحول التحقق مما إذا كانت هناك اثنين من الأعداد الصحيحة المكونة من 32 بت
𝐴
و
𝐵
راضٍ
A⋅B=?C
في التحقق مما
(gA)B=?gC
يحتفظ في
𝐹264∗
. تقلل هذه التحويلة بشكل كبير من الجهد المرتبط بالتزامن مع بروتوكول GKR. بالمقارنة مع نظام البحث السابق القائم على Binius، يتطلب النهج المبني على GKR لضرب الأعداد فقط التزامًا مساعدًا واحدًا ويقلل من تكلفة SumChecks، مما يجعل الخوارزمية أكثر كفاءة، خاصة في الحالات التي تكون فيها SumChecks أكثر اقتصادية من التزامات إضافية. يصبح هذا الأسلوب حلاً واعدًا لتقليل تكاليف التزامن مع معالجة Binius.
تحسين ZeroCheck PIOP 3.2: توازن تكاليف الحوسبة بين المثبت والتحققالورقةبعض التحسينات لـ PIOP لـ ZeroCheck يقترح استراتيجيات لموازنة التكاليف الحسابية بين Prover (P) و Verifier (V) ، مع التركيز على تقليل نقل البيانات والتعقيد الحسابي. فيما يلي تقنيات التحسين الرئيسية:
- الحد من نقل بيانات Proverمن خلال تحويل بعض العبء الحسابي إلى المحقق ، يمكن تقليل عملية نقل البيانات للمثبت. على سبيل المثال ، في الجولة
𝑖
، يرسل المثبت
𝑣𝑖+1(𝑋)
لـ
𝑋=0,…,𝑑+1
، ويتحقق المدقق مما إذا كان
𝑣𝑖=𝑣𝑖+1(0)+𝑣𝑖+1(1)
يحتفظ.
تحسين: يمكن للمثبت تجنب إرسالها
𝑣𝑖+1(1)
، حيث يمكن للمدقق حسابه على أنه
vi+1(1)=vi−vi+1(0)
.
في الجولة الأولى ، يرسل Prover
𝑣1(0)=𝑣1(1)=0
، مما يقلل من بعض حسابات التقييم، مما يقلل من التكاليف الحسابية وتكاليف النقل
𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺
.
- تقليل عدد نقاط التقييم للمثبتخلال جولة
𝑖
، يجب على الباحث إرسال
𝑣𝑖+1(𝑋)
، المحسوبة كـ
𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)
تحسين: بدلاً من ذلك، يمكن للمثبت أن يرسل
𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),
حيث $v_i(X) = v_i'(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))
.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜
\alpha
𝑎𝑛𝑑
r
,𝑡ℑ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓
v_i’(X)
𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓
v_i(X)
,𝑟𝑒𝑑𝑢𝑐𝑖𝑛𝑔𝑡ℎ𝑒𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛𝑝𝑜𝑖𝑛𝑡𝑠.𝑇ℎ𝑒𝑖𝑛𝑡𝑒𝑟−𝑟𝑜𝑢𝑛𝑑𝑐ℎ𝑒𝑐𝑘𝑐𝑎𝑛𝑡ℎ𝑒𝑛𝑏𝑒𝑠𝑖𝑚𝑝𝑙𝑖𝑓𝑖𝑒𝑑𝑎𝑠
(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),
𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑦
2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.
𝐹𝑜𝑟
d = 3 $ ، تؤدي هذه التحسينات إلى خفض التكلفة بعامل 5/3.
- الجبر التكميلي الأمثلبالنسبة لبروفير صادق ، فإن كثير الحدود
𝐶(𝑥0,…,𝑥𝑛−1)
صفر في
𝐻𝑛
ويمكن التعبير عنها على أنها
𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)
. حيث
𝑄𝑖
يتم حسابها من خلال القسمة الجبرية المرتبة، بدءًا من
𝑅𝑛=𝐶
. تقسيم متسلسل عن طريق
𝑥𝑖(𝑥𝑖−1)
يحسب
𝑄𝑖
و
𝑅𝑖
، مع
𝑅0
تمثيل التمديد المتعدد الخطي لـ
𝐶
على
𝐻𝑛
، يفترض أنها صفر.
تحليل درجات
𝑄𝑖
. لـ
ج>أ
,
𝑸𝒋
يحتفظ بنفس الدرجة في
𝑥𝑖
كما
𝐶
. ل
𝑗=𝑖
، يتم تخفيض الدرجة بمقدار 2، ولـ
𝑗- تأثير جولات التبديل وعوامل التحسين يتوقف تحسين بروتوكول Sumcheck للحقل الصغير على اختيار جولة التبديل الأمثل.𝑡
، وهو يشير إلى اللحظة التي يعود فيها البروتوكول من النسخة المحسنة إلى الخوارزمية البسيطة. تشير التجارب إلى أن عامل التحسين يصل إلى ذروته في نقطة التبديل المثلى ثم يتبع اتجاهًا قطعيًا. عند تجاوز هذه النقطة ، يتناقص الكفاءة لأن نسبة ضرب حقل الأساس وحقل الامتداد أكبر في الحقول الأصغر ، مما يستدعي العودة في الوقت المناسب إلى الخوارزمية البسيطة.
بالنسبة لتطبيقات معينة ، مثل Cubic Sumcheck (
د = 3
), يوفر بروتوكول Sumcheck للحقل الصغير تحسينًا بدرجة الطاقة العشرية عن الطريقة الساذجة. على سبيل المثال ، في الحقل الأساسي
𝐺𝐹[2]2. تأثير حجم الحقل الأساسي على الأداء حقول الأساس الأصغر (على سبيل المثال،
، تتفوق الخوارزمية 4 على الخوارزمية الساذجة بحوالي 30 مرة.
𝐺𝐹[2]
) تعزيز كفاءة الخوارزمية المحسنة بشكل كبير بسبب الفرق الأكبر بين تكاليف حقول التمديد وضرب الحقول الأساسية. وهذا يؤدي إلى عامل تحسين أكبر للخوارزمية المحسنة.
- المكاسب الأمثل من خوارزمية كاراتسوبا يلعب خوارزمية كاراتسوبا دورًا حاسمًا في تحسين أداء بروتوكول Sumcheck للمجال القاعدي. بالنسبة لمجال قاعدة𝐺𝐹[2]
, يحقق الخوارزمية 4 عوامل تحسين قصوى تبلغ 6 للخوارزمية 3 و 30 للخوارزمية 4، مما يشير إلى أن الخوارزمية 4 أكثر كفاءة بخمس مرات من الخوارزمية 3. تعزز خوارزمية كاراتسوبا كفاءة وقت التشغيل وتحسن نقطة الانتقال لكلا الخوارزميات، مع النقاط الأمثل في
𝑡=5
للخوارزمية 3 و
ر = 8
للخوارزمية 4.
- تحسين كفاءة الذاكرة يعزز بروتوكول Sumcheck الحقل الصغير أيضًا كفاءة الذاكرة. يتطلب الخوارزمية 4𝑂(𝑑⋅𝑡)
الذاكرة، بينما يحتاج Algorithm 3 إلى
O(2d⋅t)
الذاكرة. ل
𝑡=8
يستخدم الخوارزمية 4 فقط 0.26 ميجابايت من الذاكرة ، بالمقارنة مع 67 ميجابايت المطلوبة من الخوارزمية 3. هذا يجعل الخوارزمية 4 مناسبة بشكل خاص للبيئات المحدودة للذاكرة ، مثل إثبات العميل على الجانب الناقص من الموارد.
تحسين PCS 3.4: FRI-Binius تقليل حجم دليل Binius Proofأحد التحديات الرئيسية لبروتوكول Binius هو حجم الإثبات الكبير نسبيا ، والذي يتدرج مع الجذر التربيعي لحجم الشاهد عند
O(N)
. يحد مقياس الجذر التربيعي هذا من قدرته التنافسية عند مقارنته بالأنظمة التي تقدم أدلة أكثر إيجازا. في المقابل ، تعد أحجام الإثبات متعددة اللوغاريتمات ، كما تحققها الأنظمة المتقدمة مثل Plonky3 من خلال تقنيات مثل FRI ، ضرورية لضمان المدققين "الموجزين" حقا. يهدف تحسين FRI-Binius إلى تقليل حجم إثبات Binius وتحسين أدائه العام مقارنة بالأنظمة الأكثر كفاءة.
الورقةالبراهين اللوغاريتمية للتعدد عبر الأبراج الثنائية, المشار إليه باسم FRI-Binius، يقدم آلية طي FRI (برهان بروكسيميتي ريد-سولومون التفاعلي السريع) القائمة على حقل ثنائي جديد مع أربع ابتكارات رئيسية:
- المعادلات المعترضة: تحويل المعادلة متعددة الخطوط الأولية إلى أساس معادلة متعددة الخطوط ذات ارتفاع رمز منخفض (LCH) للحساب المحسن.- المتغيرات الفاقدة في الفضاء: يستخدم هذه المتعددات الفطرية بالتزامن مع NTT (تحويل نظري للأعداد) الجمعي لتمكين تحليل فورييه سريع المثلثات، وتحسين العمليات على مجال المعاملات.- حزمة الأساس الجبري: يسهل تجميع البيانات بكفاءة، مما يقلل من الاستخدام الزائد للبروتوكول المتعلق بالتضمين.- Ring-Switching SumCheck: أحدث تحسين لـ SumCheck باستخدام تقنيات التبديل الدائري لتعزيز الأداء بشكل أكبر.عملية النواة لنظام FRI-Binius للتعهد بالمتعدد الخطي للمعادلات التعبيرية (PCS)
يقوم بروتوكول FRI-Binius بتحسين مخططات الالتزام العديدية الخطية للحقول الثنائية (PCS) من خلال تحويل المتعدد الخطي الأولي، المحدد فوق الحقل الثنائي
𝐹2
، إلى كثير حدود متعدد الخطوط على حقل أكبر
𝐾
.
- مرحلة الالتزام تحوّل مرحلة الالتزام - ℓ- -متعددة المتغيرات متعددة الحدود الجملية (على $ \ mathbb {F} 2- )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑- \ell’- −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟- \mathbb{F}{2^{128}}$ ). يقلل هذا العملية من عدد المعاملات بمقدار 128، مما يسمح بجيل أكثر كفاءة للبرهان.- في مرحلة التقييم ، يقوم المثبت والتحقق بتنفيذ- ℓ′- جولات من برتوكول التحقق المشترك للحلقة المتقاطعة مع دليل أوراق عمل تفاعلي لإثبات القرب (IOPP). تشمل التفاصيل الرئيسية:FRI Opening Proofs: تشكل هذه الأدلة معظم حجم البرهان وتتم معالجتها بشكل مماثل لبراهين FRI القياسية عبر الحقول الكبيرة.- تكلفة SumCheck للبروفر: قابلة للمقارنة مع تكلفة تنفيذ SumCheck في مجال كبير.- تكلفة Prover's FRI: تطابق تكاليف FRI القياسية المشاهدة في تنفيذات المجال الكبيرة.- عمليات المحقق: يتلقى المحقق 128 عنصرًا من - 𝐹2128- ويقوم بـ 128 ضربة إضافية، مما يسمح بالتحقق الفعال.فوائد FRI-Binius
من خلال تطبيق هذه الطريقة، يمكن لـ Binius تقليل حجم البرهان بدرجة، مما يجعلها أقرب إلى أداء الأنظمة التشفيرية على آخر حال، مع البقاء متوافقة مع الحقول الثنائية. تساعد طريقة طي FRI المحسنة للحقول الثنائية، بالإضافة إلى التعبئة الجبرية وتحسينات SumCheck، Binius على إنشاء براهين أصغر دون المساس بكفاءة التحقق.
تعتبر هذه التحولات خطوة هامة نحو تحسين حجم الإثبات في بينيوس، مما يضمن أنها تصبح أكثر تنافسية مع الأنظمة الحديثة الأخرى، وخاصة تلك المركزة على أحجام الإثبات اللوغاريتمية.
الجدول 2: مقارنة حجم البرهان بينيوس مقابل FRI-Binius
الجدول 3: مقارنة بلونكي 3 FRI مقابل FRI-Binius## 4. الاستنتاجتكمن مقترحات قيمة Binius بأكملها في قدرتها على استخدام حجم حقل أقل قوة من اثنين للشهود، واختيار حجم الحقل حسب الحاجة. Binius هو نظام تصميم مشترك لـ "بروتوكولات Sumcheck المسرعة للأجهزة الأساسية والبرمجيات وFPGA"، مما يتيح إثباتات سريعة بتكاليف ذاكرة منخفضة جدًا.
نظم البرهان مثل Halo2 و Plonky3 تنطوي على أربع خطوات رئيسية تستهلك الكثير من الوقت الحسابي: إنشاء بيانات الشاهد ، والتعهد ببيانات الشاهد ، وإجراء حجة الاختفاء ، وإنشاء برهان الفتح.
على سبيل المثال ، مع وظيفة تجزئة Keccak في Plonky3 ووظيفة تجزئة Grøstl في Binius ، يتم توضيح توزيع الحسابات لهذه الخطوات الأربعة الرئيسية في الشكل 3.
الشكل 3. تكلفة الالتزام الأصغر
تظهر هذه المقارنة أن Binius قد أزال بشكل أساسي عنق الزجاجة في التزام prover. عنق الزجاجة الجديد هو بروتوكول Sumcheck ، حيث يمكن معالجة مشكلات مثل العديد من التقييمات متعددة الحدود وضرب الحقول بكفاءة باستخدام أجهزة متخصصة.
يوفر نظام FRI-Binius، وهو نوع من FRI، خيارًا جذابًا للغاية من خلال إزالة الأتعاب المضافة من طبقة إثبات الحقل دون تسبب في زيادة كبيرة في التكلفة في طبقة الإثبات المجمعة.
حاليا ، يقوم الفريق غير القابل للاختزال بتطوير طبقته العودية ولديه أعلن عن شراكة مع فريق بوليجون لبناء zkVM مبني على بينيوس; البوابة تتحول Jolt zkVM من Lasso إلى Binius لتعزيز أدائها العوديو؛ والفريق إنجونياما يقوم بتنفيذ نسخة FPGA من بينيوس.
