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

1 المقدمة

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

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

| الوقت | STARKs | عرض الترميز | |------|--------|----------| | 2018 | الجيل الأول | 252bit | | 2021 | الجيل الثاني | 64بت | | 2022 | الجيل الثالث | 32bit | | 2023 | الجيل الرابع | 1bit |

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

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

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

• Galois رمز تحقق الرسالة ( GMAC )، يعتمد على مجال F2128؛

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

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

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

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

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

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

عادة ما تتكون معظم أنظمة SNARKs الحالية من جزئين رئيسيين:

• إثباتات Oracle التفاعلية متعددة الحدود القائمة على نظرية المعلومات ( 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، تشمل طرق التخفيف الشائعة تخفيف بارّيت، وتخفيف مونتغومري، بالإضافة إلى طرق تخفيف خاصة لبعض الحقول المحدودة مثل Mersenne-31 أو Goldilocks-64. في الحقل الثنائي F2k، تشمل طرق التخفيف الشائعة تخفيف خاص ( كما هو مستخدم في AES )، وتخفيف مونتغومري ( كما هو مستخدم في POLYVAL )، والتخفيف التكراري ( كما هو الحال في Tower ). تشير الورقة البحثية "استكشاف مساحة تصميم الحقل الأولي مقابل تطبيقات الأجهزة ECC للحقل الثنائي" إلى أن الحقل الثنائي لا يحتاج إلى إدخال حمل في العمليات الجمع والضرب، وأن عملية التربيع في الحقل الثنائي فعالة جدًا، لأنها تتبع القواعد المبسطة (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 ).

! برج ثنائي المجال

الشكل 1: مجال ثنائي البرج

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: حجة التحويل المتعدد الخطوط الجديدة ------ مناسبة لمكعب Boolean

في بروتوكول Binius، فإن بناء ومعالجة متعددات الحدود الافتراضية هي قضايا