استكشاف Circle STARKs

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

هذا التحول عزز سرعة الإثبات، على سبيل المثال، يمكن لـ Starkware إثبات 620,000 قيمة هاش من Poseidon2 في الثانية على جهاز كمبيوتر محمول من نوع M3. هذا يعني أنه طالما كنا على استعداد للاعتماد على Poseidon2 كدالة هاش، يمكننا حل التحديات في تطوير ZK-EVM الفعال. كيف تعمل هذه التقنيات إذن؟ كيف تُبنى هذه الإثباتات على مجالات أصغر؟ كيف تقارن هذه البروتوكولات بحلول مثل Binius؟ ستستكشف هذه المقالة هذه التفاصيل مع التركيز بشكل خاص على حل يسمى Circle STARKs، والذي يمتلك خصائص فريدة متوافقة مع مجال Mersenne31.

! عمل فيتاليك الجديد: استكشاف ستارك الدائرة

المشاكل الشائعة عند استخدام حقول رياضية أصغر

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

لمنع الهجمات، نحتاج إلى اختيار r بعد أن يقدم المهاجم A. تعتبر تقنية Fiat-Shamir وسيلة لتعزيز أمان البروتوكولات من خلال تعيين بعض المعلمات إلى قيمة هاش معينة لتجنب الهجمات. يجب أن تأتي المعلمات المختارة من مجموعة كبيرة بما يكفي لضمان عدم قدرة المهاجم على التنبؤ أو التخمين بهذه المعلمات، مما يعزز أمان النظام.

في البروتوكولات المستندة إلى المنحنيات البيضاوية وSTARKs من فترة 2019، كانت هذه المشكلة بسيطة: كانت جميع العمليات الرياضية لدينا تتم على أرقام ب256 بت، لذا يمكننا اختيار r كرقم عشوائي ب256 بت، وهذا يكفي. ومع ذلك، في STARKs على الحقول الأصغر، واجهنا مشكلة: هناك حوالي 2 مليار قيمة محتملة لـ r للاختيار من بينها، لذا فإن المهاجم الذي يريد تزوير الإثبات يحتاج فقط إلى المحاولة 2 مليار مرة، على الرغم من أن العبء كبير، لكنه لا يزال ممكنًا تمامًا للمهاجم المصمم!

هذه المسألة لها حلان:

• إجراء فحوصات عشوائية متعددة
• حقل موسع

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

هذا يؤدي إلى حل آخر: مجال التمديد، مجال التمديد مشابه للأعداد المركبة ولكنه يعتمد على المجالات المحدودة. نقدم قيمة جديدة، نرمز لها بـ α، ونعلن أنها تلبي علاقة معينة، مثل α2 = قيمة معينة. بهذه الطريقة، نخلق هيكلًا رياضيًا جديدًا يمكنه إجراء عمليات أكثر تعقيدًا على المجالات المحدودة. في هذا المجال الموسع، تصبح حسابات الضرب باستخدام القيمة الجديدة α. يمكننا الآن العمل على أزواج القيم في المجال الموسع، وليس مجرد أرقام فردية. على سبيل المثال، إذا كنا نعمل على حقول مثل Mersenne أو BabyBear، فإن مثل هذا التمديد يسمح لنا بوجود المزيد من الخيارات للقيم، مما يزيد من الأمان. لزيادة حجم الحقول بشكل أكبر، يمكننا تطبيق نفس التقنية مرة أخرى. نظرًا لأننا قد استخدمنا α، فإننا بحاجة إلى تعريف قيمة جديدة، مما يظهر في Mersenne31 كاختيار α بحيث أن α2 = قيمة معينة.

! عمل فيتاليك الجديد: استكشاف ستارك الدائرة

من خلال توسيع المجال، لدينا الآن عدد كافٍ من القيم للاختيار من بينها لتلبية احتياجاتنا الأمنية. إذا كان المعالج يتعامل مع متعددة الحدود بدرجة أقل من d، يمكن لكل جولة أن توفر أماناً بمقدار 104 بت. وهذا يعني أننا نملك ضمانات أمان كافية. إذا كان من الضروري الوصول إلى مستوى أمان أعلى، مثل 128 بت، يمكننا إضافة بعض الأعمال الحسابية الإضافية في البروتوكول لتعزيز الأمان.

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

FRI العادي

عند بناء SNARK أو STARK، تكون الخطوة الأولى عادة هي التحويل إلى صيغة رياضية. وهذا يعني تحويل أي مشكلة حسابية إلى معادلة، حيث تكون بعض المتغيرات والمعاملات متعددة الحدود. على وجه التحديد، ستبدو هذه المعادلة عادةً مثل P(X,Y,Z)=0، حيث P هو متعدد الحدود، وX وY وZ هي المعلمات المعطاة، بينما يحتاج المحلل إلى تقديم قيم لـ X وY. بمجرد الحصول على مثل هذه المعادلة، فإن حلها يتوافق مع حل المشكلة الحسابية الأساسية.

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

• افترض أن لديك قيمة تقييم متعددة الحدود A، وتريد إثبات أن درجته أقل من 2^20
• اعتبر كثير الحدود B(x^2) = A(x) + A(-x) ، C(x^2) = (A(x) - A(-x))/x
• D هو مزيج خطي عشوائي من B و C، أي D=B+rC حيث r هو معامل عشوائي.

جوهر ما يحدث هو أن B يعزل معاملات الزوجية A، و C يعزل معاملات الفردية. بالنظر إلى B و C، يمكنك استعادة كثير الحدود الأصلي A: A(x) = B(x^2) + xC(x^2). إذا كانت درجة A بالفعل أقل من 2^20، فإن درجات B و C ستكون على التوالي درجة A ودرجة A ناقص 1. لأن الجمع بين الحدود الزوجية والفردية لن يزيد من الدرجة. نظرًا لأن D هو مجموعة خطية عشوائية من B و C، يجب أن تكون درجة D أيضًا درجة A، مما يتيح لك التحقق من مدى توافق درجة A مع المتطلبات من خلال درجة D.

! عمل فيتاليك الجديد: استكشاف Circle STARKs

أولاً، قام FRI بتبسيط عملية التحقق عن طريق تقليل مشكلة إثبات درجة متعددة الحدود إلى درجة d إلى مشكلة إثبات درجة متعددة الحدود إلى درجة d/2. يمكن تكرار هذه العملية عدة مرات، بحيث يتم تقليل المشكلة إلى النصف في كل مرة.

إن مبدأ عمل FRI هو تكرار هذه العملية المبسطة. على سبيل المثال، إذا بدأت من إثبات أن درجة متعددة الحدود هي d، من خلال سلسلة من الخطوات، ستثبت في النهاية أن درجة متعددة الحدود هي d/2. بعد كل تبسيط، تتناقص درجة متعددة الحدود الناتجة تدريجياً. إذا لم يكن ناتج مرحلة معينة هو درجة متعددة الحدود المتوقعة، فستفشل هذه الجولة من الفحص. إذا حاول شخص ما دفع متعددة حدود ليست درجة d بهذه التقنية، فسيكون هناك احتمال معين أن درجة الناتج في الجولة الثانية لن تتوافق مع التوقعات، وسيكون من الأرجح أن يحدث عدم التوافق في الجولة الثالثة، مما يؤدي إلى فشل الفحص النهائي. يمكن أن يكشف هذا التصميم بفعالية ويرفض المدخلات غير المطابقة للمتطلبات. إذا كانت مجموعة البيانات في معظم الأماكن تساوي متعددة حدود بدرجة d، فمن المحتمل أن تمر مجموعة البيانات هذه عبر تحقق FRI. ومع ذلك، لبناء مجموعة بيانات مثل هذه، يحتاج المهاجم إلى معرفة متعددة الحدود الفعلية، لذا حتى مع وجود عيب طفيف في الإثبات، فهذا يدل على أن المُثبِت قادر على توليد "إثبات حقيقي".

دعونا نتعرف بمزيد من التفاصيل على ما يحدث هنا، والخصائص المطلوبة لجعل كل شيء يعمل بشكل طبيعي. في كل خطوة، نقلل درجة كثير الحدود إلى النصف، بينما نقلل أيضًا مجموعة النقاط (مجموعة النقاط التي نهتم بها) إلى النصف. الأولى هي المفتاح الذي يسمح لبروتوكول FRI بالعمل بشكل صحيح. بينما الثانية تجعل خوارزمية تعمل بسرعة كبيرة: نظرًا لأن حجم كل جولة يقل إلى النصف مقارنة بالجولة السابقة، فإن التكلفة الحسابية الإجمالية هي O(N)، بدلاً من O(N*log(N)).

لتحقيق التناقص التدريجي في النطاق، تم استخدام ترميز ثنائي إلى واحد، حيث يتم ترميز كل نقطة إلى واحدة من نقطتين. يسمح هذا الترميز بتقليل حجم مجموعة البيانات إلى النصف. ومن المزايا المهمة لهذا الترميز الثنائي إلى واحد أنه قابل للتكرار. بمعنى آخر، عندما نطبق هذا الترميز، تظل مجموعة النتائج المحتملة تحتفظ بنفس الخصائص. لنفترض أننا بدأنا من مجموعة جزئية ضربية. هذه المجموعة الجزئية هي مجموعة S، حيث يوجد لكل عنصر x مضاعفه 2x في المجموعة. إذا قمنا بتطبيق عملية التربيع على المجموعة S (أي ترميز كل عنصر x إلى x^2)، فإن المجموعة الجديدة S^2 ستحتفظ بنفس الخصائص. يسمح لنا هذا النوع من العمليات بالاستمرار في تقليل حجم مجموعة البيانات، حتى يتبقى في النهاية قيمة واحدة فقط. على الرغم من أنه من الناحية النظرية يمكننا تقليص مجموعة البيانات لتبقى قيمة واحدة فقط، إلا أنه في الممارسة العملية، غالبًا ما نتوقف قبل الوصول إلى مجموعة أصغر.

يمكنك تصور هذه العملية على أنها عملية تمديد خط (مثل قطعة مستقيمة أو قوس) على محيط دائرة، مما يجعلها تدور حول المحيط مرتين. على سبيل المثال، إذا كان نقطة على المحيط تقع في موقع x درجة، بعد إجراء هذه العملية، ستتحرك إلى موقع 2x درجة. كل نقطة على المحيط من 0 إلى 179 درجة لديها نقطة مقابلة في الموقع من 180 إلى 359 درجة، وهاتان النقطتان ستتطابقان. هذا يعني أنه عندما تقوم بتعيين نقطة من x درجة إلى 2x درجة، فإنها ستتطابق مع نقطة تقع في x + 180 درجة. هذه العملية يمكن تكرارها. بعبارة أخرى، يمكنك تطبيق هذه العملية التحويلية عدة مرات، حيث يتم تحريك النقاط على المحيط إلى مواقعها الجديدة في كل مرة.

! عمل فيتاليك الجديد: استكشاف الدائرة الدائرية

لجعل تقنية التعيين فعالة، يجب أن يكون حجم المجموعة الفرعية الضربية الأصلية له عامل كبير من قوى 2. BabyBear هو نظام له عدد محدد، حيث يكون هذا العدد بحيث تحتوي أكبر مجموعة فرعية ضربية على جميع القيم غير الصفرية، وبالتالي يكون حجم المجموعة الفرعية 2k−1 (حيث k هو عدد بتات العدد). حجم المجموعة الفرعية هذا مناسب جدًا للتقنية المذكورة أعلاه، لأنه يسمح بتقليل درجة كثيرات الحدود بشكل فعال من خلال تطبيق عمليات التعيين المتكررة. في BabyBear، يمكنك اختيار مجموعة فرعية بحجم 2^k (أو استخدام المجموعة الكاملة مباشرة)، ثم تطبيق طريقة FRI لتقليل درجة كثير الحدود تدريجياً إلى 15، وفي النهاية فحص درجة كثير الحدود. هذه الطريقة تستفيد من خصائص العدد وحجم المجموعة الفرعية الضربية، مما يجعل عملية الحساب فعالة للغاية. Mersenne31 هو نظام آخر، حيث يكون عدده بحيث يكون حجم المجموعة الفرعية الضربية 2^31 - 1. في هذه الحالة، يكون حجم المجموعة الفرعية الضربية يحتوي على قوة واحدة فقط من 2 كعامل، مما يعني أنه يمكن قسمته على 2 مرة واحدة فقط. المعالجة اللاحقة لم تعد مناسبة للتقنية المذكورة أعلاه، مما يعني أنه لا يمكن استخدام FFT بشكل فعال لتقليل درجة كثيرات الحدود كما هو الحال في BabyBear.

مجال Mersenne31 مناسب جدًا لإجراء العمليات الحسابية على وحدات المعالجة المركزية/وحدات معالجة الرسوميات 32 بت الموجودة. لأن خصائص المودولوس الخاص بها (مثل 2^31 - 1) تجعل العديد من العمليات يمكن أن تُنجز باستخدام عمليات بت فعالة: إذا تجاوزت نتيجة جمع رقمين المودولوس، يمكن تقليلها إلى النطاق المناسب من خلال إجراء عمليات إزاحة مع المودولوس. تعتبر عمليات الإزاحة عمليات فعالة جدًا. في عمليات الضرب، يمكن استخدام تعليمات CPU محددة (تُعرف عادةً بتعليمات الإزاحة العالية) لمعالجة النتائج. هذه التعليمات يمكن أن تحسب بكفاءة الجزء العالي من الضرب، مما يزيد من كفاءة العمليات. في مجال Mersenne31، بسبب الخصائص المذكورة أعلاه، العمليات الحسابية أسرع بحوالي 1.3 مرة مقارنةً بمجال BabyBear. يوفر Mersenne31 كفاءة حسابية أعلى. إذا كان من الممكن تنفيذ FRI في مجال Mersenne31، فسوف يعزز ذلك كفاءة الحساب بشكل كبير، مما يجعل FRI يعتمد على