استكشاف Circle STARKs

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

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

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

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

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

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

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

هناك حلان:

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

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

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

FRI العادي

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

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

B يفصل معامل A الزوجي، وC يفصل المعامل الفردي. إذا تم إعطاء B وC يمكن استعادة A: A(x) = B(x^2) + xC(x^2). إذا كان درجة A < 2^20، فإن درجتي B وC تكونان على التوالي درجة A ودرجة A - 1. D كتركيب عشوائي، يجب أن تكون درجة A.

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

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

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

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

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

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

دائرة FRI

تكمن براعة Circle STARKs في أنه، بالنظر إلى عدد أولي p، يمكن العثور على مجموعة بحجم p تتمتع بخصائص مشابهة للزوجي الواحد. تتكون هذه المجموعة من النقاط التي تلبي شروطًا معينة، مثل مجموعة النقاط التي يكون فيها x^2 mod p مساويًا لقيمة معينة.

هذه النقاط تتبع قاعدة الجمع: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) الصيغة المزدوجة:2*(x,y) = (2x^2 - 1, 2xy)

نحن نركز على النقاط في المواقع الفردية على الدائرة. أولاً، نقوم بتجميع جميع النقاط في خط مستقيم: f0(x) = (F(x,y) + F(x,- y))/2

ثم قم بإجراء تركيبة خطية عشوائية ، واحصل على متعدد الحدود الأحادي P(x).

من الجولة الثانية فصاعدًا، يصبح التمثيل: f0(2x^2-1) = (F(x) + F(-x))/2

هذا التحويل يقلل من حجم المجموعة في كل مرة إلى النصف. كل x يمثل نقطتين: (x,y) و (x,-y). (x → 2x^2 - 1) هي قاعدة مضاعفة النقاط. نحن نحول إحداثيات x لنقطتين متقابلتين على الدائرة إلى إحداثيات x لنقاط مضاعفة.

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

FFTs الدائرية

تدعم مجموعة الدائرة أيضًا FFT، وطريقة البناء مشابهة لـ FRI. الفارق الرئيسي هو أن Circle FFT لا تعالج متعددة الحدود الصارمة، وإنما مساحة Riemann-Roch: متعددة الحدود mod الدائرة (x^2 + y^2 - 1 = 0).

مخرجات FFT الدائرية هي معاملات أساسية محددة: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

يمكن للمطورين تجاهل هذه النقطة تقريبًا. تحتاج STARKs فقط إلى تخزين متعددة الحدود كمجموعة من قيم التقييم. تُستخدم FFT فقط للتوسع منخفض الدرجة: بالنظر إلى N قيمة، يتم إنشاء k*N من القيم على نفس متعددة الحدود.

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

العمليات التجارية

العمليات الشائعة في STARK هي إجراء عمليات تجارية على نقاط معينة. على سبيل المثال، يمكن إثبات P(x)=y من خلال الخطوات التالية:

1. حساب النسبة: Q = (P - y)/(X - x)
2. إثبات أن Q هو متعدد الحدود وليس كسر

في مجموعة STARK الدائرية، نظرًا لعدم وجود دالة خطية من نقطة واحدة، هناك حاجة إلى تقنيات مختلفة. يمكن بناء دالة المماس، لكنها تمتلك عددًا مكررًا 2 عند النقطة. لذلك يجب التقييم عند نقطتين لإثبات ذلك.

إذا كانت P تساوي y1 عند x1 وتساوي y2 عند x2، فإننا نختار دالة التداخل L بحيث تتساوى عند هاتين النقطتين. ثم نثبت أن P - L تساوي صفر عند هاتين النقطتين، من خلال قسمة L على L لإثبات أن الكسر Q هو متعدد الحدود.

متعددة الحدود المختفية

المعادلات متعددة الحدود التي تحاول STARK إثباتها عادةً تأخذ الشكل C(P(x), P(next(x))) = Z(x) · H(x), Z(x) تساوي صفرًا في مجال التقييم الأصلي.

في STARK الدائري، الدالة المعنية هي: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1

! [عمل فيتاليك الجديد: استكشاف ستارك الدائرة](https://img-cdn.gateio.im/webp-social/moments-0277731a7327da529c85417a01718c59.webp019283746574839201

ترتيب عكسي

تقييمات متعددة الحدود في STARKs عادة ما تكون مرتبة بترتيب عكسي. في STARKs الدائرية، الهيكل المطوي مختلف قليلاً:

• الخطوة الأولى: )x,y( و )x,-y( متطابقان
• الخطوة الثانية: اقتران x مع -x
• الخطوات التالية: اقتران p و q، بحيث Q^i)p( = -Q^i)q(

لتعديل ترتيب العكس، يجب عكس كل رقم ما عدا الرقم الأخير، واستخدام الرقم الأخير لتحديد ما إذا كان ينبغي قلب الأرقام الأخرى.

! [عمل فيتاليك الجديد: استكشاف ستارك الدائرة])https://img-cdn.gateio.im/webp-social/moments-13da9460855ee8c504c44696efc2164c.webp(

الكفاءة

Circle STARKs فعالة للغاية. الحسابات عادة ما تتضمن:

1. الحسابات الأصلية: تستخدم في المنطق التجاري
2. الحساب الأصلي: يستخدم في التشفير ) مثل تجزئة بوسيدون (
3. البحث عن المعلمات: طرق حسابية عامة فعالة

تكمن السرعة الفعالة في الاستفادة الكاملة من مساحة تتبع الحساب. هنا حجم الحقل هو 2^31، والهدر في المساحة ليس كبيرًا. تستخدم عمليات التجزئة مثل Poseidon كل بت من كل رقم بشكل كامل في أي حقل.

تقوم Binius بتحقيق حزم بت أعلى كفاءة من خلال مزج حقول بأحجام مختلفة، لكن الثمن هو أن المفهوم أكثر تعقيدًا. مفاهيم Circle STARKs هي نسبياً بسيطة.

الاستنتاج

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

فهم Circle FRI و FFTs يمكن أن يكون وسيلة لفهم FFTs الخاصة الأخرى، مثل FFTs في المجالات الثنائية و FFTs في المنحنيات البيضاوية.

بدمج تقنيات مثل Mersenne31 و BabyBear و Binius، نحن نقترب من الحد الأقصى لكفاءة الطبقة الأساسية لـ STARKs. قد تركز التحسينات المستقبلية على:

1. تعظيم كفاءة الحسابات مثل دوال التجزئة والتوقيعات
2. بناء متكرر لتمكين المزيد من التوازي
3. آلة افتراضية حسابية لتحسين تجربة المطورين

! [إبداع فيتاليك الجديد: استكشاف ستارك الدائرة])https://img-cdn.gateio.im/webp-social/moments-972d4e51e7d92462c519ef900358a6af.webp(