في السنوات الأخيرة، كانت هناك اتجاهات في تصميم بروتوكولات STARKs نحو استخدام حقول أصغر. كانت أول تنفيذات إنتاجية لـ STARKs تستخدم حقلاً بحجم 256 بت، أي إجراء عمليات المود على الأرقام الكبيرة. لكن هذا التصميم كان ذو كفاءة منخفضة، حيث أن معالجة الأرقام الكبيرة كان يستهلك الكثير من قوة الحوسبة. لحل هذه المشكلة، بدأت STARKs في استخدام حقول أصغر: أولاً Goldilocks، ثم Mersenne31 و BabyBear.
هذا التحول زاد بشكل كبير من سرعة الإثبات. على سبيل المثال، يمكن لـ Starkware الآن إثبات 620,000 تجزئة Poseidon2 في الثانية على جهاز كمبيوتر محمول من نوع M3. هذا يعني أنه طالما نثق في Poseidon2 كدالة تجزئة، يمكننا حل مشكلة تطوير ZK-EVM بكفاءة. كيف تعمل هذه التقنيات؟ كيف يتم بناء الإثباتات على الحقول الصغيرة؟ ستتناول هذه المقالة هذه التفاصيل، مع التركيز بشكل خاص على Circle STARKs، وهو حل متوافق مع حقل Mersenne31.
عند إنشاء دليل قائم على التجزئة، فإن إحدى الحيل المهمة هي التحقق بشكل غير مباشر من خصائص متعددة الحدود من خلال تقييمها عند نقاط عشوائية. يمكن أن يبسط ذلك بشكل كبير عملية الإثبات.
على سبيل المثال، افترض أن البروتوكول يتطلب منك إنشاء التزام متعدد الحدود A، بحيث يكون A^3(x) + x - A(ωx) = x^N. يمكن أن يطلب البروتوكول منك اختيار إحداثيات عشوائية r وإثبات أن A(r)^3 + r - A(ωr) = r^N. ثم استنتاج A(r) = c، وتثبت أن Q = (A - c)/(X - r) هو متعدد الحدود.
لمنع الهجمات، نحتاج إلى اختيار r بعد أن يقدم المهاجم A. في البروتوكولات القائمة على المنحنيات البيانية، يكون هذا بسيطًا: يمكننا اختيار رقم عشوائي مكون من 256 بت كـ r. ولكن في STARKs ذات الحقول الصغيرة، يوجد حوالي 2 مليار خيار فقط لـ r، وقد يتمكن المهاجم من كسرها عن طريق التجربة والخطأ.
هذه المشكلة لها حلان:
إجراء فحص عشوائي عدة مرات
الحقول الموسعة
الفحص العشوائي المتكرر بسيط وفعال، لكن قد تكون هناك مشاكل في الكفاءة. يمتد المجال بشكل مشابه للأعداد المركبة، لكنه يعتمد على مجال محدود. نقدم قيمة جديدة α، ونصرح بأن α^2 = قيمة معينة. وهكذا تم إنشاء بنية رياضية جديدة قادرة على إجراء عمليات أكثر تعقيدًا على المجال المحدود.
من خلال توسيع المجال، لدينا عدد كافٍ من القيم للاختيار من بينها لتلبية متطلبات الأمان. لا تزال معظم العمليات الرياضية تتم على الحقول الأساسية، ويتم استخدام الحقول الأكبر فقط عند الحاجة لتعزيز الأمان.
FRI (Fast Reed-Solomon Interactive) البروتوكول هو خطوة مهمة في بناء SNARK أو STARK. إنه يبسط عملية التحقق من خلال تقليل مشكلة إثبات متعددة الحدود من الدرجة d إلى مشكلة إثبات من الدرجة d/2. يمكن تكرار هذه العملية عدة مرات، حيث يتم تبسيط المشكلة في كل مرة إلى النصف.
يعمل FRI عن طريق تكرار عملية التبسيط. يبدأ من إثبات أن درجة البولينيوم هي d، ومن خلال سلسلة من الخطوات، يتم إثبات أن الدرجة هي d/2 في النهاية. بعد كل تبسيط، تنخفض درجة البولينيوم الناتج تدريجياً. إذا كانت المخرجات في مرحلة معينة لا تتوافق مع التوقعات، فإن تلك الجولة من الفحص ستفشل.
لتقليل النطاق تدريجياً، تم استخدام ترميز ثنائي إلى واحد. يسمح هذا الترميز بتقليل حجم مجموعة البيانات إلى النصف مع الاحتفاظ بنفس الخصائص. يمكن تصور هذه العملية كعملية تمديد مقاطع الخط على محيط الدائرة على طول المحيط لدورتين.
لجعل تقنية التعيين فعالة، يجب أن يكون حجم مجموعة الضرب الأصلية له عامل كبير من 2. تجعل معامل BabyBear أكبر مجموعة ضرب تحتوي على جميع القيم غير الصفرية، مما يجعلها مناسبة تمامًا لهذه التقنية. حجم مجموعة الضرب لـ Mersenne31 يحتوي فقط على عامل واحد من 2، مما يحد من نطاق تطبيقه.
مجال Mersenne31 مناسب جداً لإجراء العمليات الحسابية على معالجات 32 بت/ GPU، أسرع بحوالي 1.3 مرة من مجال BabyBear. إذا تم تنفيذ FRI في مجال Mersenne31، فسوف تعزز كفاءة الحساب بشكل كبير.
تتميز Circle STARKs بأنه، بالنظر إلى عدد أولي p، يمكن العثور على مجموعة بحجم p تمتلك خصائص ثنائية مماثلة. تتكون هذه المجموعة من النقاط التي تلبي شروطًا معينة، مثل مجموعة النقاط التي يكون فيها x^2 mod p يساوي قيمة معينة.
تتبع هذه النقاط قاعدة الجمع: (x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1)
الصيغة المزدوجة هي: 2 * (x,y) = (2x^2 - 1, 2xy)
تقوم دائرة FRI أولاً بتقريب جميع النقاط إلى خط مستقيم، ثم تقوم بعملية دمج خطي عشوائي للحصول على متعددة الحدود أحادية البعد P(x). بدءًا من الجولة الثانية، يتحول الإرسال إلى: f0(2x^2-1) = (F(x) + F(-x))/2
تقوم هذه الخريطة بتقليل حجم المجموعة إلى النصف في كل مرة، وتحويل إحداثيات x لنقطتين متقابلتين على الدائرة إلى إحداثيات x للنقطة المضاعفة. كان من الممكن القيام بذلك في الفضاء ثنائي الأبعاد، ولكن العمليات الأحادية البعد أكثر كفاءة.
تدعم مجموعة Circle أيضًا FFT، وطريقة البناء مشابهة لـ FRI. الكائنات التي تعالجها Circle FFT هي فضاء Riemann-Roch، وليس مجرد متعددات الحدود بشكل صارم. المعاملات الناتجة عن Circle FFT هي أساس خاص بـ Circle FFT.
بصفتك مطورًا، يمكنك تجاهل هذه النقطة تقريبًا. تحتاج STARKs فقط إلى تخزين كثيرات الحدود كمجموعة من قيم التقييم. المكان الوحيد الذي تحتاج فيه إلى FFT هو إجراء التمديد المنخفض: بالنظر إلى N قيمة، يتم إنتاج k*N قيمة على نفس كثير الحدود.
في Circle STARKs، نظرًا لعدم وجود دالة خطية يمكن أن تمر عبر نقطة واحدة، فإننا بحاجة إلى استخدام تقنيات مختلفة بدلاً من العمليات التجارية التقليدية. نحن مضطرون لإثبات إضافة نقطة افتراضية من خلال التقييم في نقطتين.
إذا كان كثير الحدود P يساوي y1 عند x1، و y2 عند x2، فإننا نختار دالة الاستيفاء L بحيث تتساوى عند هاتين النقطتين. ثم نثبت أن P-L يكون صفرًا عند هاتين النقطتين، ومن خلال قسمة L على L نثبت أن الناتج Q هو كثير حدود.
في Circle STARKs، يكون كثير الحدود المفقود هو:
Z1)x,y( = y
Z2)x,y( = x
Zn+1)x,y( = )2 * Zn(x,y(^2) - 1
يمكن اشتقاق هذا من دالة الطي: في Circle STARKs يتم استخدام x → 2x^2 - 1 بشكل متكرر. تتطلب الجولة الأولى معالجة خاصة.
عكس ترتيب البتات
تستخدم Circle STARKs ترتيب عكسي معدل، حيث يتم عكس كل بت ما عدا الأخير، ويستخدم البت الأخير لتحديد ما إذا كان يجب عكس البتات الأخرى. وهذا يعكس الهيكل المميز ل Circle STARKs.
العمليات الحسابية الأصلية: مستخدمة في التشفير ) مثل تجزئة بوسيدون (
البحث عن المعلمات: تنفيذ حسابات متنوعة من خلال جدول القيم
تستفيد دائرة STARKs بشكل كامل من المساحة الحسابية، مع هدر أقل. إنها أقل قليلاً من Binius، لكن المفهوم أبسط.
الخاتمة
لا تعتبر Circle STARKs أكثر تعقيدًا بالنسبة للمطورين من STARKs التقليدية. يمكن أن تساعد فهم Circle FRI وFFTs في فهم FFTs الخاصة الأخرى. حاليًا، كفاءة طبقة STARKs الأساسية قريبة من الحد الأقصى، وقد تشمل اتجاهات التحسين المستقبلية:
تعظيم كفاءة العمليات الرياضية لدالة التجزئة والتوقيع
قد تحتوي هذه الصفحة على محتوى من جهات خارجية، يتم تقديمه لأغراض إعلامية فقط (وليس كإقرارات/ضمانات)، ولا ينبغي اعتباره موافقة على آرائه من قبل Gate، ولا بمثابة نصيحة مالية أو مهنية. انظر إلى إخلاء المسؤولية للحصول على التفاصيل.
تسجيلات الإعجاب 17
أعجبني
17
4
إعادة النشر
مشاركة
تعليق
0/400
NftBankruptcyClub
· منذ 22 س
صغر الخط زاد من الكفاءة...666
شاهد النسخة الأصليةرد0
GasWhisperer
· منذ 22 س
همم... الحقول الأصغر = إثباتات أسرع، لكن هل يمكننا الوثوق بـ poseidon2؟ أشعر بالت conflicted حول هذه المعادلة بين الكفاءة/الأمان بصراحة
شاهد النسخة الأصليةرد0
alpha_leaker
· منذ 22 س
Stark يبدو مخيفًا بعض الشيء
شاهد النسخة الأصليةرد0
ChainDetective
· منذ 23 س
فقط فهمت، بشكل أساسي هو تقليل الحجم والحساب بسرعة.
Circle STARKs: استكشافات وانتصارات إثبات ZK الفعال في الحقول الصغيرة
استكشاف Circle STARKs
في السنوات الأخيرة، كانت هناك اتجاهات في تصميم بروتوكولات STARKs نحو استخدام حقول أصغر. كانت أول تنفيذات إنتاجية لـ STARKs تستخدم حقلاً بحجم 256 بت، أي إجراء عمليات المود على الأرقام الكبيرة. لكن هذا التصميم كان ذو كفاءة منخفضة، حيث أن معالجة الأرقام الكبيرة كان يستهلك الكثير من قوة الحوسبة. لحل هذه المشكلة، بدأت STARKs في استخدام حقول أصغر: أولاً Goldilocks، ثم Mersenne31 و BabyBear.
هذا التحول زاد بشكل كبير من سرعة الإثبات. على سبيل المثال، يمكن لـ Starkware الآن إثبات 620,000 تجزئة Poseidon2 في الثانية على جهاز كمبيوتر محمول من نوع M3. هذا يعني أنه طالما نثق في Poseidon2 كدالة تجزئة، يمكننا حل مشكلة تطوير ZK-EVM بكفاءة. كيف تعمل هذه التقنيات؟ كيف يتم بناء الإثباتات على الحقول الصغيرة؟ ستتناول هذه المقالة هذه التفاصيل، مع التركيز بشكل خاص على Circle STARKs، وهو حل متوافق مع حقل Mersenne31.
! عمل فيتاليك الجديد: استكشاف ستارك الدائرة
الأسئلة الشائعة عند استخدام الحقول الصغيرة
عند إنشاء دليل قائم على التجزئة، فإن إحدى الحيل المهمة هي التحقق بشكل غير مباشر من خصائص متعددة الحدود من خلال تقييمها عند نقاط عشوائية. يمكن أن يبسط ذلك بشكل كبير عملية الإثبات.
على سبيل المثال، افترض أن البروتوكول يتطلب منك إنشاء التزام متعدد الحدود A، بحيث يكون A^3(x) + x - A(ωx) = x^N. يمكن أن يطلب البروتوكول منك اختيار إحداثيات عشوائية r وإثبات أن A(r)^3 + r - A(ωr) = r^N. ثم استنتاج A(r) = c، وتثبت أن Q = (A - c)/(X - r) هو متعدد الحدود.
لمنع الهجمات، نحتاج إلى اختيار r بعد أن يقدم المهاجم A. في البروتوكولات القائمة على المنحنيات البيانية، يكون هذا بسيطًا: يمكننا اختيار رقم عشوائي مكون من 256 بت كـ r. ولكن في STARKs ذات الحقول الصغيرة، يوجد حوالي 2 مليار خيار فقط لـ r، وقد يتمكن المهاجم من كسرها عن طريق التجربة والخطأ.
هذه المشكلة لها حلان:
الفحص العشوائي المتكرر بسيط وفعال، لكن قد تكون هناك مشاكل في الكفاءة. يمتد المجال بشكل مشابه للأعداد المركبة، لكنه يعتمد على مجال محدود. نقدم قيمة جديدة α، ونصرح بأن α^2 = قيمة معينة. وهكذا تم إنشاء بنية رياضية جديدة قادرة على إجراء عمليات أكثر تعقيدًا على المجال المحدود.
من خلال توسيع المجال، لدينا عدد كافٍ من القيم للاختيار من بينها لتلبية متطلبات الأمان. لا تزال معظم العمليات الرياضية تتم على الحقول الأساسية، ويتم استخدام الحقول الأكبر فقط عند الحاجة لتعزيز الأمان.
! عمل فيتاليك الجديد: استكشاف ستارك الدائرة
FRI العادي
FRI (Fast Reed-Solomon Interactive) البروتوكول هو خطوة مهمة في بناء SNARK أو STARK. إنه يبسط عملية التحقق من خلال تقليل مشكلة إثبات متعددة الحدود من الدرجة d إلى مشكلة إثبات من الدرجة d/2. يمكن تكرار هذه العملية عدة مرات، حيث يتم تبسيط المشكلة في كل مرة إلى النصف.
يعمل FRI عن طريق تكرار عملية التبسيط. يبدأ من إثبات أن درجة البولينيوم هي d، ومن خلال سلسلة من الخطوات، يتم إثبات أن الدرجة هي d/2 في النهاية. بعد كل تبسيط، تنخفض درجة البولينيوم الناتج تدريجياً. إذا كانت المخرجات في مرحلة معينة لا تتوافق مع التوقعات، فإن تلك الجولة من الفحص ستفشل.
لتقليل النطاق تدريجياً، تم استخدام ترميز ثنائي إلى واحد. يسمح هذا الترميز بتقليل حجم مجموعة البيانات إلى النصف مع الاحتفاظ بنفس الخصائص. يمكن تصور هذه العملية كعملية تمديد مقاطع الخط على محيط الدائرة على طول المحيط لدورتين.
لجعل تقنية التعيين فعالة، يجب أن يكون حجم مجموعة الضرب الأصلية له عامل كبير من 2. تجعل معامل BabyBear أكبر مجموعة ضرب تحتوي على جميع القيم غير الصفرية، مما يجعلها مناسبة تمامًا لهذه التقنية. حجم مجموعة الضرب لـ Mersenne31 يحتوي فقط على عامل واحد من 2، مما يحد من نطاق تطبيقه.
مجال Mersenne31 مناسب جداً لإجراء العمليات الحسابية على معالجات 32 بت/ GPU، أسرع بحوالي 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)
تقوم دائرة FRI أولاً بتقريب جميع النقاط إلى خط مستقيم، ثم تقوم بعملية دمج خطي عشوائي للحصول على متعددة الحدود أحادية البعد P(x). بدءًا من الجولة الثانية، يتحول الإرسال إلى: f0(2x^2-1) = (F(x) + F(-x))/2
تقوم هذه الخريطة بتقليل حجم المجموعة إلى النصف في كل مرة، وتحويل إحداثيات x لنقطتين متقابلتين على الدائرة إلى إحداثيات x للنقطة المضاعفة. كان من الممكن القيام بذلك في الفضاء ثنائي الأبعاد، ولكن العمليات الأحادية البعد أكثر كفاءة.
! عمل فيتاليك الجديد: استكشاف الدائرة الدائرية
FFTs الدائرية
تدعم مجموعة Circle أيضًا FFT، وطريقة البناء مشابهة لـ FRI. الكائنات التي تعالجها Circle FFT هي فضاء Riemann-Roch، وليس مجرد متعددات الحدود بشكل صارم. المعاملات الناتجة عن Circle FFT هي أساس خاص بـ Circle FFT.
بصفتك مطورًا، يمكنك تجاهل هذه النقطة تقريبًا. تحتاج STARKs فقط إلى تخزين كثيرات الحدود كمجموعة من قيم التقييم. المكان الوحيد الذي تحتاج فيه إلى FFT هو إجراء التمديد المنخفض: بالنظر إلى N قيمة، يتم إنتاج k*N قيمة على نفس كثير الحدود.
! عمل فيتاليك الجديد: استكشاف ستاركس الدائرة
تقسيم
في Circle STARKs، نظرًا لعدم وجود دالة خطية يمكن أن تمر عبر نقطة واحدة، فإننا بحاجة إلى استخدام تقنيات مختلفة بدلاً من العمليات التجارية التقليدية. نحن مضطرون لإثبات إضافة نقطة افتراضية من خلال التقييم في نقطتين.
إذا كان كثير الحدود P يساوي y1 عند x1، و y2 عند x2، فإننا نختار دالة الاستيفاء L بحيث تتساوى عند هاتين النقطتين. ثم نثبت أن P-L يكون صفرًا عند هاتين النقطتين، ومن خلال قسمة L على L نثبت أن الناتج Q هو كثير حدود.
! [عمل فيتاليك الجديد: استكشاف ستارك الدائرة](https://img-cdn.gateio.im/webp-social/moments-0277731a7327da529c85417a01718c59.webp019283746574839201
المتعددات الحدودية المتلاشية
في Circle STARKs، يكون كثير الحدود المفقود هو: Z1)x,y( = y Z2)x,y( = x Zn+1)x,y( = )2 * Zn(x,y(^2) - 1
يمكن اشتقاق هذا من دالة الطي: في Circle STARKs يتم استخدام x → 2x^2 - 1 بشكل متكرر. تتطلب الجولة الأولى معالجة خاصة.
عكس ترتيب البتات
تستخدم Circle STARKs ترتيب عكسي معدل، حيث يتم عكس كل بت ما عدا الأخير، ويستخدم البت الأخير لتحديد ما إذا كان يجب عكس البتات الأخرى. وهذا يعكس الهيكل المميز ل Circle STARKs.
! [عمل فيتاليك الجديد: استكشاف ستارك الدائرة])https://img-cdn.gateio.im/webp-social/moments-13da9460855ee8c504c44696efc2164c.webp(
الكفاءة
Circle STARKs فعالة للغاية. تتضمن الحسابات عادةً:
تستفيد دائرة STARKs بشكل كامل من المساحة الحسابية، مع هدر أقل. إنها أقل قليلاً من Binius، لكن المفهوم أبسط.
الخاتمة
لا تعتبر Circle STARKs أكثر تعقيدًا بالنسبة للمطورين من STARKs التقليدية. يمكن أن تساعد فهم Circle FRI وFFTs في فهم FFTs الخاصة الأخرى. حاليًا، كفاءة طبقة STARKs الأساسية قريبة من الحد الأقصى، وقد تشمل اتجاهات التحسين المستقبلية:
! [إبداع فيتاليك الجديد: استكشاف ستارك الدائرة])https://img-cdn.gateio.im/webp-social/moments-972d4e51e7d92462c519ef900358a6af.webp(