استكشاف Circle STARKs

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

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

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

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

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

على سبيل المثال، افترض أن نظام إثبات يتطلب منك إنشاء التزام لعدة حدود، A، يجب أن يلبي A^3(x) + x - A(ωx) = x^N(، وهو نوع شائع جدًا من الإثباتات في بروتوكول ZK-SNARK). يمكن أن يتطلب البروتوكول منك اختيار نقطة عشوائية r وإثبات أن A(r) + r - A(ωr) = r^N. ثم تستطيع استنتاج A(r) = c، وقد أثبت أنك Q = (A - c)/(X - r) هو متعددة الحدود.

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

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

هذه المشكلة لها حلان:

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

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

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

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

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

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

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

FRI العادي

عند بناء SNARK أو STARK، تكون الخطوة الأولى عادةً هي arithmetization. هذه هي تحويل مشكلة حسابية عشوائية إلى معادلة حيث تكون بعض المتغيرات والمعاملات عبارة عن كثيرات الحدود. على وجه التحديد، ستبدو هذه المعادلة عادةً مثل 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.

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

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

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

دعونا نتعرف بمزيد من التفاصيل على ما يحدث هنا، وكذلك الخصائص المطلوبة لتشغيل كل شيء بشكل طبيعي. في كل خطوة، نقلل من درجة كثيرات الحدود إلى النصف، بينما نقلل أيضاً مجموعة النقاط ( التي نهتم بها إلى النصف. الأول هو المفتاح لجعل بروتوكول FRI) Fast Reed-Solomon Interactive( يعمل بشكل صحيح. الثاني يجعل خوارزمية تعمل بسرعة كبيرة: حيث أن حجم كل جولة يقل إلى النصف مقارنة بالجولة السابقة، فإن إجمالي تكلفة الحساب هو 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 هو نظام له عدد صحيح معين، حيث أن عدده يجعل مجموعة الضرب القصوى تشمل جميع القيم غير الصفرية، وبالتالي يكون حجم المجموعة 2^k - 1( حيث k هو عدد بتات العدد ). حجم المجموعة هذا مناسب جداً للتقنية المذكورة أعلاه، لأنه يسمح بتقليل درجة كثير الحدود بكفاءة من خلال تطبيق عمليات الخرائط بشكل متكرر. في BabyBear، يمكنك اختيار مجموعة بحجم 2^k ( أو استخدام المجموعة الكاملة ) مباشرة، ثم تطبيق طريقة FRI لتقليل درجة كثير الحدود تدريجياً إلى 15، وفي النهاية التحقق من درجة كثير الحدود. تستفيد هذه الطريقة من خصائص العدد وخصائص مجموعة الضرب، مما يجعل عملية الحساب فعالة جداً. Mersenne31 هو نظام آخر، حيث أن عدده يجعل حجم مجموعة الضرب 2^31 - 1. في هذه الحالة، يكون حجم مجموعة الضرب يحتوي فقط على عامل واحد من 2، مما يجعله قابلًا للقسمة على 2 مرة واحدة فقط. المعالجة بعد ذلك لم تعد صالحة للتقنية المذكورة أعلاه، أي أنه لا يمكن استخدام FFT بشكل فعال لتقليل درجة كثير الحدود كما هو الحال في BabyBear.

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