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

1 المقدمة

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

عرض عرض الترميز من الجيل الأول من 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 في مجالات توسيع أكبر لضمان الأمان المطلوب.

عند بناء نظام إثبات على أساس المجال الثنائي، هناك مشكلتان عمليتان: يجب أن يكون حجم المجال المستخدم عند حساب تمثيل المسار في 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 وكفاءة التحقق، بل تحدد أيضًا ما إذا كان يمكن للنظام تحقيق الشفافية دون الحاجة إلى إعداد موثوق، وما إذا كان يمكن أن يدعم ميزات توسيع مثل إثباتات التكرار أو الإثباتات المجمعة.

Binius: HyperPlonk PIOP + Brakedown PCS + المجال الثنائي. بشكل أكثر تحديدًا، يتضمن Binius خمس تقنيات رئيسية لتحقيق كفاءته وأمانه. أولاً، يتكون الحساب القائم على الأبراج من المجالات الثنائية (towers of binary fields) من أساس حساباته، مما يمكنه من تنفيذ العمليات المبسطة ضمن المجال الثنائي. ثانيًا، قام Binius بتكييف فحص الضرب والاستبدال في بروتوكول إثبات Oracle التفاعلي الخاص به (PIOP) لضمان التحقق من الاتساق بشكل آمن وفعال بين المتغيرات واستبدالاتها. ثالثًا، يقدم البروتوكول إثباتًا جديدًا للنقل متعدد الخطوط، مما يحسن كفاءة التحقق من العلاقات متعددة الخطوط على المجالات الصغيرة. رابعًا، يعتمد Binius على إصدار محسّن من إثبات البحث Lasso، مما يوفر مرونة وأمانًا قويًا لآلية البحث. أخيرًا، يستخدم البروتوكول مخطط التزام متعدد الحدود على المجالات الصغيرة (Small-Field 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 + Y2.

كما هو موضح في الشكل 1، سلسلة بطول 128 بت: يمكن تفسير هذه السلسلة بعدة طرق في سياق مجال ثنائي. يمكن اعتبارها عنصرًا فريدًا في مجال ثنائي بطول 128 بت، أو يمكن تحليلها إلى عنصرين في مجال بطول 64 بت، أربعة عناصر في مجال بطول 32 بت، ستة عشر عنصرًا في مجال بطول 8 بت، أو 128 عنصرًا في مجال F2. هذه المرونة في التمثيل لا تتطلب أي عبء حسابي، بل هي مجرد تحويل نوع لسلسلة البتات (typecast)، وهي خاصية مثيرة للاهتمام ومفيدة جدًا. في الوقت نفسه، يمكن تعبئة العناصر الصغيرة في مجال أكبر بدون أي عبء حسابي إضافي. يستفيد بروتوكول Binius من هذه الخاصية لتحسين الكفاءة الحاسوبية. بالإضافة إلى ذلك، تستكشف الورقة البحثية "On Efficient Inversion in Tower Fields of Characteristic Two" تعقيد الحسابات في إجراء الضرب، التربيع، وحساب العكس في مجال ثنائي بطول n (يمكن تحليله إلى مجالات فرعية بطول m).

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

2.2 PIOP: النسخة المعدلة من HyperPlonk Product و 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: حجة التحول المتعدد الخطوط الجديدة ------ تنطبق على الهيبر كوبي البولياني

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

• التعبئة: تقوم هذه الطريقة بتحسين العمليات من خلال تعبئة العناصر الأصغر المجاورة في ترتيب القاموس إلى عناصر أكبر. يتم استهداف عملية التعبئة لكتل بحجم 2κ وتقوم بدمجها.