استكشاف 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 بت. لكن في STARKs ذات الحقول الأصغر، هناك حوالي 2 مليار قيمة r فقط للاختيار من بينها، وقد يتمكن المهاجم من كسرها من خلال التجربة.

هناك حلان:

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

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

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

FRN العادي

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

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 يفصل المعاملات الزوجية، و C يفصل المعاملات الفردية. إذا تم إعطاء B و C يمكن استعادة A. إذا كانت درجة A < 2^20، فإن درجات B و C ستكون على التوالي درجة A ودرجة A-1. D كتركيب خطي عشوائي، يجب أن تكون درجته درجة A.

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

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

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

مجال Mersenne31 مناسب لعمليات المعالجة على معالجات CPU/GPU البالغ 32 بت. خصائصه المودولية تجعل العديد من العمليات ممكنة باستخدام عمليات بت فعالة. في مجال 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) هو قاعدة مضاعفة النقاط.

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

FFTs الدائرية

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

إذا كانت متعددة الحدود P تساوي y1 عند x1 وتساوي y2 عند x2، اختر دالة التداخل L التي تساوي y1 عند x1 وتساوي y2 عند x2: L = ((y2 - y1) / (x2 - x1)) * (x - x1) + ذ1

ثم أثبت أن P - L يساوي صفرًا عند هاتين النقطتين، من خلال قسمة L على L لإثبات أن النتيجة Q هي متعددة الحدود.

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

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

في 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

يمكن اشتقاق كثيرات الحدود المفقودة من الدوال القابلة للطي: تستخدم STARK العادية x → x^2 بشكل متكرر، بينما تستخدم STARK الدائرية x → 2x^2 - 1 بشكل متكرر.

ترتيب عكسي

في STARKs، يتم عادةً ترتيب تقييمات多项式 في ترتيب عكسي. على سبيل المثال، عندما n=16: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

ترتيب كهذا يجعل قيم المجموعات المبكرة في عملية تقييم FRI متجاورة في الترتيب، مما يوفر المساحة.

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

حجم 16 ترتيب عكسي قابل للطي: {0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

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

الكفاءة

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

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

تكمن الأهمية في الكفاءة في الاستفادة الكاملة من مساحة تتبع الحسابات. حجم حقل Circle STARKs هو 2^31، مما يقلل من الهدر في المساحة.

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

الاستنتاج

دائرة STARKs ليست أكثر تعقيدًا للمطورين من STARKs. فهم دائرة FRI ودائرة FFTs يمكن أن يكون بمثابة وسيلة لفهم FFTs الخاصة الأخرى.

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

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

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