قياس أداء SNARK: الواجهات الأمامية والخلفية والمستقبل

تعد SNARK (الحجج غير التفاعلية المختصرة للمعرفة) أحد تطبيقات البحث الأولية الهامة للتشفير لتوسيع blockchain (على سبيل المثال ، مجموعات L2) والخصوصية. تسمح SNARKs لشخص ما أن يثبت لمدقق غير موثوق به V (على سبيل المثال ، Ethereum blockchain) أنهم يعرفون بعض البيانات (على سبيل المثال ، مجموعة من المعاملات الصالحة). هناك طريقة ساذجة لإثبات ذلك تتمثل في إرسال البيانات إلى V، الذي يمكنه بعد ذلك التحقق مباشرة من صحتها. يحقق SNARK الشيء نفسه ، ولكن بتكاليف أفضل لـ V. على وجه الخصوص ، يجب أن يكون إثبات SNARK أقصر من الدليل الساذج الذي يشتمل على البيانات نفسها. (لمزيد من التفاصيل ، انظر مسودة كتابي ، البراهين والحجج والمعرفة الصفرية. للحصول على مقدمة حول SNARKs ، راجع Sarah Meicklejohn's <font style="vertical-align: inherit;"> كمادة تطعيم في تجديد عيوب محيط بالذورة (الحنك) الكبيرة:</font> في تشفير a16z سلسلة أبحاث الصيف.)

يمكن أن تختلف تكاليف التحقق من SNARKs ، لكنها مفهومة جيدًا وغالبًا ما تكون جيدة جدًا. فمثلا، يرمى يلقى بقوة البراهين تكلف حوالي 290,000 غاز للتحقق من Ethereum ، بينما تكلف براهين StarkWare حوالي 5 ملايين غاز. من المحتمل أن تكون SNARKs قابلة للتطبيق في إعدادات متنوعة حتى خارج البلوكشين - على سبيل المثال تمكين استخدام سريع ولكن غير موثوق به الخوادم و خردوات. 

ولكن نظرًا لأن التحقق من SNARK رخيص عادةً ، فإن المحددات الرئيسية للتطبيق هي تكاليف مُثبِّت SNARK P. في هذا المنشور ، أشرح كيفية تقدير هذه التكاليف لتحديد متى يكون من المعقول استخدام SNARKs ، وكيف يمكن أن تتحسن SNARKs في المستقبل. من الجدير بالذكر أن هذه مساحة سريعة الحركة ، والعديد من المشاريع التي تمت مناقشتها في هذا المنشور تعمل بنشاط على تحسين أدائها.

لكن أولاً: كيف يتم نشر SNARKs

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

عادةً ما يكون IR هو نوع من مثيل إرضاء الدائرة يعادل ψ. هذا يعني أن الدائرة C يأخذ كمدخل للبيانات w، بالإضافة إلى بعض المدخلات الإضافية التي تسمى عادةً "نصيحة غير حتمية" ψ on w. يتم استخدام مدخلات المشورة للمساعدة C يجري ψ، مع الحفاظ C صغير. على سبيل المثال ، في كل مرة ψ يقسم رقمين x و y، الحاصل q والباقي r يمكن تقديمها كنصيحة ل Cو C يمكن ببساطة التحقق من ذلك x = qy + r. هذا الاختيار هو أقل تكلفة من صنع C تشغيل خوارزمية قسمة للحساب q و r من الصفر.

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

كما سنرى ، تزداد تكاليف المُثبِّت لواجهة SNARK الخلفية Cالصورة بحجم. حفظ C صغيرة يمكن أن تكون صعبة ، لأن الدوائر هي تنسيق محدود للغاية للتعبير عن عملية حسابية. تتكون من بوابات متصل بواسطة الأسلاك. كل بوابة g يتم تغذية بعض القيم ويطبق أ جدا وظيفة بسيطة لتلك القيم. يتم إدخال النتيجة بعد ذلك في بوابات "المصب" عبر الأسلاك المنبثقة منها g.

قابلية تطوير SNARK: ما هو الوقت الذي يستغرقه الأمر حقًا؟

السؤال الرئيسي هو ، ما مقدار الوقت الذي يستغرقه مثّل SNARK ، مقارنةً بإعادة التنفيذ ببساطة ψ على البيانات؟ الجواب هو المثل فوق من SNARK ، نسبة إلى فحص الشهود المباشر. يشير التعبير الأخير إلى حقيقة أنه ، في الدليل الساذج الذي فيه P يرسل w إلى V, V الشيكات wالصلاحية بالتنفيذ ψ على ذلك. 

من المفيد تقسيم المثل الأعلى إلى "الواجهة الأمامية" و "الخلفية العلوية". إذا كان تقييم الدائرة C البوابة هي F مرات أكثر تكلفة من الجري ψ، ثم نقول أن الواجهة الأمامية هي F. إذا تم تطبيق مَثْل الواجهة الخلفية على C is B مرات أكثر تكلفة من التقييم C بوابة تلو بوابة ، ثم نقول أن الواجهة الخلفية هي B. مجموع النفقات العامة هو المنتج، F·B. يمكن أن تكون هذه النفقات العامة المضاعفة كبيرة حتى لو F و B متواضعة بشكل فردي. 

في الممارسة العملية، F و B يمكن أن يكون كلاهما حوالي 1000 أو أكبر. هذا يعني أن إجمالي النفقات العامة المتعلقة بفحص الشهود المباشر يمكن أن تكون من مليون إلى 1 ملايين أو أكثر. يمكن أن يؤدي البرنامج الذي يتم تشغيله لمدة ثانية واحدة فقط على جهاز كمبيوتر محمول بسهولة إلى مُثبِّت SNARK الذي يتطلب عشرات أو مئات الأيام من وقت الحوسبة (مترابط واحد). لحسن الحظ ، هذا العمل عادة ما يكون متوازيًا بدرجات متفاوتة (اعتمادًا على SNARK). 

باختصار ، إذا كنت تريد استخدام SNARK في تطبيق اليوم ، فيجب أن يكون أحد الأشياء الثلاثة صحيحًا:

1. يستغرق فحص الشاهد المباشر أقل من ثانية واحدة على جهاز كمبيوتر محمول.
2. فحص الشاهد المباشر قابل بشكل خاص للتمثيل في الدائرة ، لذا فإن الواجهة الأمامية صغيرة.
3. أنت على استعداد للانتظار أيامًا حتى ينتهي مُثبِّت SNARK ، و / أو الدفع مقابل موارد حساب موازية ضخمة.

Tيشرح بقية هذا المنشور من أين تأتي النفقات العامة للواجهة الأمامية والخلفية ، وكيف أقدرها من أجل SNARKs المختلفة. سننتقل بعد ذلك إلى احتمالات التحسين. 

فصل الواجهات الأمامية والخلفية

قد يكون الفصل التام بين الواجهات الأمامية والخلفية أمرًا صعبًا لأن الخلفيات المختلفة تدعم أنواعًا مختلفة من الدوائر. وبالتالي ، يمكن أن تختلف الواجهات الأمامية اعتمادًا على الواجهة الخلفية التي يتوقعون التفاعل معها.

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

تدعم معظم الخلفيات في الواقع تعميمًا للدوائر الحسابية التي غالبًا ما تسمى مثيلات الرتبة الأولى للرضا القيد (R1CS). مع استثناء ملحوظ من جروث 16 وسابقاتها ، يمكن صنع هذه SNARKs لدعم الـ IRs الآخرين أيضًا. على سبيل المثال ، يستخدم StarkWare شيئًا يسمى التمثيل الجبري الوسيط (AIR) ، والذي يشبه أيضًا فكرة تسمى حساب PlonKish التي يمكن أن يدعمها PlonK والخلفيات الأخرى. يمكن لقدرة بعض الخلفيات على دعم الـ IRs الأكثر عمومية أن تقلل من عبء الواجهات الأمامية التي تنتج هؤلاء الـ IRs. 

تتنوع الخلفيات أيضًا من حيث الحقول المحدودة التي تدعمها أصلاً. سأناقش هذا بمزيد من التفصيل في القسم التالي.

طرق مختلفة للواجهات

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

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

على سبيل المثال ، StarkWare's القاهرة هي لغة تجميع محدودة للغاية تسمح فيها تعليمات التجميع تقريبًا بالإضافة والضرب على حقل محدود ، واستدعاءات الوظيفة ، والقراءة والكتابة في ذاكرة ثابتة (أي الكتابة مرة واحدة). إن Cairo VM هو عمارة فون نيومان ، مما يعني أن الدوائر التي تنتجها الواجهة الأمامية تأخذ بشكل أساسي برنامج القاهرة كمدخلات عامة و "تشغيل" البرنامج على الشاهد. لغة القاهرة هي Turing Complete - على الرغم من مجموعة التعليمات المحدودة ، يمكنها محاكاة المزيد من البنى القياسية ، على الرغم من أن القيام بذلك قد يكون مكلفًا. الواجهة الأمامية للقاهرة تحول تنفيذ برامج القاهرة T تعليمات بدائية فيما يسمى "درجة-2 AIR مع T الصفوف وحوالي 50 الأعمدة. " ماذا او ما هذا يعني بالضبط ليس مهمًا لهذا المنشور ، ولكن فيما يتعلق بأجهزة إثبات SNARK ، فإن هذا يتوافق مع الدوائر التي تحتوي على ما بين 50 و 100 بوابة لكل من T خطوات وحدة المعالجة المركزية بالقاهرة. 

RISC صفر نهجًا مشابهًا للقاهرة ، ولكن مع كون الآلة الافتراضية هي ما يسمى هندسة RISC-V، وهي بنية مفتوحة المصدر مع نظام بيئي ثري للبرامج تزداد شعبيتها. كمجموعة تعليمات بسيطة للغاية ، قد يكون تصميم واجهة SNARK الأمامية الفعالة التي تدعمها قابلة للتتبع نسبيًا (على الأقل بالنسبة للهياكل المعقدة مثل x86 أو ARM). اعتبارًا من مايو ، RISC Zero تحول البرامج تنفيذ T تعليمات RISC-V البدائية إلى درجة 5 AIRs مع 3T الصفوف و 160 الأعمدة. هذا يتوافق مع الدوائر على الأقل 500 بوابات لكل خطوة من وحدة المعالجة المركزية RISC-V. ومن المتوقع المزيد من التحسينات في المستقبل القريب.

تأخذ مشاريع zkEVM المختلفة (على سبيل المثال ، zkSync 2.0 ، Scroll ، Polygon zkEVM) الجهاز الظاهري ليكون (duh) جهاز Ethereum Virtual Machine. إن عملية تحويل كل تعليمات EVM إلى "أداة" مكافئة (أي ، دائرة محسّنة تنفذ التعليمات) هي عملية أكثر تعقيدًا بشكل كبير من أبسط هندسة القاهرة و RISC-V. لهذا ولأسباب أخرى, بعض مشاريع zkEVM لا تقوم بتنفيذ مجموعة تعليمات EVM بشكل مباشر ولكن تقوم بتجميع برامج Solidity عالية المستوى إلى لغات التجميع الأخرى قبل تحويلها إلى دوائر. نتائج الأداء من هذه المشاريع معلقة.

تنتج مشاريع "CPU emulator" مثل RISC-V و Cairo دائرة واحدة يمكنها التعامل مع جميع البرامج بلغة التجميع المرتبطة بها. الأساليب البديلة هي "مثل ASIC" ، وتنتج دوائر مختلفة لبرامج مختلفة. يمكن أن ينتج عن هذا النهج الشبيه بـ ASIC دوائر أصغر لبعض البرامج ، خاصةً عندما لا تعتمد تعليمات التجميع التي ينفذها البرنامج في كل خطوة على مدخلات البرنامج. على سبيل المثال ، من المحتمل أن يتجنب تحميل الواجهة الأمامية بالكامل لبرامج الخط المستقيم مثل ضرب المصفوفة الساذج. لكن نهج ASIC يبدو أيضًا محدودًا للغاية ؛ على حد علمي ، ليس معروفًا كيفية استخدامه لدعم الحلقات بدون حدود التكرار المحددة مسبقًا. 

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

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

هناك تطبيق SNARK واحد فقط ، الفرامل أسفل، التي تدعم بشكل أصلي العمليات الحسابية عبر الحقول التعسفية (كبيرة بما يكفي). جنبا إلى جنب مع أحفاد، لديه أسرع أداء معروف للمثبِّت الملموس حتى في المجالات التي تدعمها SNARKs الأخرى ، لكن البراهين الخاصة به حاليًا كبيرة جدًا بالنسبة للعديد من تطبيقات blockchain. آخر عمل يسعى إلى تحسين حجم الإثبات ، لكن المُثبَت أبطأ بشكل مقارب وهناك يبدو الحواجز إلى التطبيق العملي.

اختارت بعض المشاريع العمل في مجالات ذات عمليات حسابية سريعة بشكل خاص. فمثلا، لونكي 2 ويستخدم آخرون مجالًا مميزًا 2⁶⁴ - 2³² + 1 لأنه يمكن تنفيذ العمليات الحسابية في هذا المجال بشكل أسرع عدة مرات من الحقول الأقل تنظيمًا. ومع ذلك ، فإن استخدام مثل هذه الخاصية الصغيرة قد يؤدي إلى تحديات في التمثيل الحسابي للأعداد الصحيحة بكفاءة عبر العمليات الميدانية (على سبيل المثال ، قد يؤدي ضرب عددين صحيحين بدون إشارة 32 بت إلى نتيجة أكبر من خاصية المجال). 

 ولكن بغض النظر عن أي شيء ، بالنسبة لجميع SNARKs الشائعة اليوم لتحقيق 128 بتًا من الأمان (بدون زيادة كبيرة في تكاليف التحقق) ، يتعين عليهم العمل في مجال بحجم أكبر من 2¹²⁸. بقدر ما أستطيع أن أقول ، هذا يعني أن كل عملية ميدانية ستتطلب ما لا يقل عن عشرة عمليات مضاعفة للآلة 64 بت ، والمزيد من الإضافات والعمليات على مستوى البت. ومن ثم ، ينبغي للمرء أن يأخذ بعين الاعتبار على الأقل ترتيبًا من حيث الحجم للواجهة الأمامية بسبب الحاجة إلى الدوائر التي تعمل على الحقول المحدودة. 

للتلخيص ، فإن الواجهات الأمامية الحالية التي تستخدم تجريد آلة افتراضية تنتج دوائر بوابات 100x إلى 1000x لكل خطوة من الآلة الافتراضية ، وربما أكثر للأجهزة الافتراضية الأكثر تعقيدًا. علاوة على ذلك ، فإن حساب المجال المحدود يكون أبطأ بمقدار 10x على الأقل من الإرشادات المماثلة على المعالجات الحديثة (مع استثناءات محتملة إذا كان المعالج يحتوي على دعم مدمج لحقول معينة). قد يقلل "نهج الواجهة الأمامية لـ ASIC" من بعض هذه النفقات العامة ولكنه محدود حاليًا في أنواع البرامج التي يمكنه دعمها.

ما هي الاختناقات الخلفية؟

عادةً ما يتم تصميم SNARKs لإرضاء الدوائر من خلال الجمع بين بروتوكول آمن نظريًا للمعلومات يسمى "متعدد الحدود IOP"مع بروتوكول تشفير يسمى"مخطط التزام متعدد الحدود. " في معظم الحالات ، يكون عنق الزجاجة الملموس للمثل هو مخطط الالتزام متعدد الحدود. على وجه الخصوص ، فإن هذه SNARKs لها المُثبِت التي تلتزم بشكل مشفر بواحد أو أكثر من كثيرات الحدود التي تكون درجتها (على الأقل) |C|وهو عدد البوابات في الدائرة C. 

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

الالتزامات متعددة الحدود على أساس اللوغاريتم المنفصل

في الالتزامات متعددة الحدود القائمة على صلابة مشكلة اللوغاريتم المنفصلة في مجموعة التشفير G (KZG, Bulletproofs, دوريو Hyrax-الالتزام) ، يجب على المُثبِت أن يحسب أ التزام ناقل بيدرسن لمعاملات كثير الحدود. يتضمن هذا عددًا من الأسس ، بحجم يساوي درجة كثير الحدود. في SNARKs ، هذه الدرجة هي الحجم عادةً |C| من الدائرة C.

تم بسذاجة ، وهو متعدد الأس للحجم |C| يتطلب حوالي 1.5·|C|·سجل |G| ≈ 400·|C| عمليات المجموعة ، حيث |G| يشير إلى عدد العناصر في المجموعة G. ومع ذلك ، هناك نهج يسمى خوارزمية Pippenger ، والتي يمكن أن تقلل من هذا بعامل من السجل تقريبا |C|. للدوائر الكبيرة (على سبيل المثال ، |C| ≥ 225) ، هذا السجل |C| يمكن أن يكون العامل بشكل ملموس 25 أو أكثر ، أي بالنسبة للدوائر الكبيرة ، نتوقع أن يكون التزام ناقل بيدرسن قابلاً للحساب مع ما يزيد قليلاً عن 10·|C| عمليات المجموعة. تميل كل عملية جماعية بدورها إلى أن تكون (باعتبارها ملعبًا تقريبيًا للغاية) أبطأ بمقدار 10x من العمليات الميدانية المحدودة. استخدام SNARKs لهذه الالتزامات متعددة الحدود باهظ الثمن P حوالي 100·|C| عمليات ميدانية. 

لسوء الحظ ، تحتوي SNARKs الحالية على نفقات عامة إضافية أعلى عامل 100x أعلاه. فمثلا:

• إسبارطييجب أن يفعل المثل الذي يستخدم التزام Hyrax متعدد الحدود |C|^½ العديد من الأسس المتعددة لكل حجم |C|^½، مما يضعف التسريع من خوارزمية Pippenger بمعامل اثنين تقريبًا. 
• In جروث 16, P يجب أن تعمل على مجموعة صديقة للإقران ، والتي تكون عملياتها عادةً أبطأ مرتين على الأقل من المجموعات التي لا تتزاوج بشكل ودي. P يجب أن تؤدي أيضًا 3 أسي متعددة بدلاً من 1. مجتمعة ، ينتج عن ذلك عامل 6 إضافي على الأقل تباطؤ بالنسبة إلى 100·|C| تقدير أعلاه. 
• مارلن و يرمى يلقى بقوة تتطلب أيضًا أزواجًا ، وأن يلتزم المحققون بأكثر من 3 كثيرات الحدود. 
• لأي SNARK يستخدم Bulletproofs (على سبيل المثال، Halo2، وهو PlonK تقريبًا ولكن مع Bulletproofs بدلاً من KZG متعدد الحدود) ، يجب على المُثبِت أن يحسب لوغاريتميًا العديد من الأسس المتعددة خلال المرحلة "الافتتاحية" من مخطط الالتزام ، وهذا يمحو إلى حد كبير أي تسريع Pippenger. 

باختصار ، يبدو أن SNARKs المعروفة التي تستخدم التزامات المتجه Pedersen لها تكلفة خلفية لا تقل عن 200x وما يصل إلى 1000x أو أكثر. 

التزامات كثيرة الحدود أخرى

بالنسبة لـ SNARKs باستخدام التزامات كثيرة الحدود الأخرى (مثل جمعة و Ligero الالتزام) ، عنق الزجاجة هو أن المُثبِت يحتاج إلى أداء FFTs كبيرة. على سبيل المثال ، في الدرجة -2 AIRs التي تنتجها القاهرة (مع 51 عمودًا و T صف واحد في كل خطوة من وحدة المعالجة المركزية في القاهرة) ، يقوم المثل المنشور لـ StarkWare بعمل 2 FFTs على الأقل لكل عمود ، بطول يتراوح بين 16 ·T و 32 ·T. الثوابت 16 و 32 تعتمد على المعلمات الداخلية لـ FRI كما حددتها StarkWare ويمكن تقليلها - ولكن على حساب تكاليف التحقق المتزايدة. 

بتفاؤل ، FFT بطول 32·T يستغرق حوالي 64·T·تسجيل (32T) المضاعفات الميدانية. هذا يعني أنه حتى بالنسبة للقيم الصغيرة نسبيًا لـ T (على سبيل المثال، T ≥ 2²⁰) ، فإن عدد العمليات الميدانية لكل عمود لا يقل عن 64·25·T= 1600·T. لذلك يبدو أن النفقات العامة الخلفية هي على الأقل بالآلاف. علاوة على ذلك ، من الممكن أن تكون FFTs الكبيرة أكثر اختناقًا بسبب عرض النطاق الترددي للذاكرة أكثر من العمليات الميدانية. 

في بعض السياقات ، يمكن تخفيف الواجهة الخلفية لـ SNARKs التي تؤدي FFTs كبيرة باستخدام تقنية تسمى تجميع الإثبات. بالنسبة إلى التراكمية ، فإن هذا يعني ذلك P (خدمة التجميع) تقسم مجموعة كبيرة من المعاملات إلى ، على سبيل المثال ، 10 دفعات أصغر. لكل دفعة صغيرة i, P تنتج إثبات SNARK πi من صلاحية الدفعة. ولكن P لا تنشر هذه الأدلة على Ethereum ، حيث سيؤدي ذلك إلى زيادة تكاليف الغاز بمقدار 10 أضعاف تقريبًا. بدلاً من ذلك ، يتم تطبيق SNARK مرة أخرى ، هذه المرة لتقديم دليل π إثبات ذلك P يعرف π₁ ، ... ،π₁₀. هذا هو الشاهد P تدعي أن تعرف هي البراهين العشرة π₁،…، π₁₀، وفحص الشهود المباشر يطبق إجراء التحقق SNARK على كل من البراهين. هذا دليل واحد π تم نشره على Ethereum. 

في الالتزامات متعددة الحدود مثل FRI و Ligero-الالتزام ، هناك توتر قوي بين P الوقت و V التكاليف ، مع المعلمات الداخلية التي تعمل كمقبض يمكنه استبدال أحدهما بالآخر. حيث π₁ ،…، π₁₀ لم يتم نشرها على Ethereum ، يمكن ضبط المقبض بحيث تكون هذه البراهين كبيرة ، وإنتاجها أسرع. فقط في التطبيق النهائي لـ SNARK ، للتجميع π₁ ،…، π₁₀ في دليل واحد π, هل يحتاج مخطط الالتزام إلى التكوين لضمان دليل صغير. 

تخطط StarkWare لنشر تجميع الإثبات قريبا. هذا هو أيضا محور تركيز مشاريع مثل لونكي 2.

ما هي الاختناقات الأخرى أمام قابلية توسعة SNARK؟

ركز هذا المنشور على المثقف الوقت ، ولكن يمكن أن تكون تكاليف المُثبِت الأخرى أيضًا اختناقات قابلية التوسع. على سبيل المثال ، بالنسبة للعديد من خلفيات SNARK الخلفية ، يحتاج المُثبِّت إلى تخزين عدة عناصر ميدانية لكل بوابة في C، ويمكن أن تكون تكلفة هذه المساحة ضخمة. على سبيل المثال ، برنامج ψ يمكن أن يؤدي التشغيل في ثانية واحدة على جهاز كمبيوتر محمول ربما مليار عملية بدائية على معالج حديث. كما رأينا ، يجب أن يتوقع المرء بشكل عام C تتطلب أكثر من 100 بوابة لكل عملية من هذا القبيل. هذا يعني 100 مليار بوابة ، والتي ، اعتمادًا على SNARK ، يمكن أن تعني عشرات أو مئات تيرابايت من المساحة P. 

مثال آخر: العديد من SNARKs الشائعة (على سبيل المثال ، يرمى يلقى بقوة, مارلن, جروث 16) تتطلب "حفل إعداد موثوق به" معقدًا لإنشاء "مفتاح إثبات" منظم ، التي يجب أن يخزنها المثل. بقدر ما أعرف ، فإن أكبر حفل من هذا القبيل تم إنشاء مفتاح إثبات قادر على دعم الدوائر بحوالي 2²⁸≈250 مليون بوابة. يبلغ حجم مفتاح الإثبات عشرات الجيجابايت. 

في السياقات التي يكون فيها تجميع الإثبات ممكنًا ، يمكن تخفيف هذه الاختناقات بشكل كبير. 

استشراف المستقبل: احتمالات المزيد من SNARKs القابلة للتوسع

يمكن أن تكون النفقات العامة للواجهة الأمامية والخلفية ثلاثة أوامر من حيث الحجم أو أكثر. هل يمكننا توقع انخفاض كبير في هذه الأمور في المستقبل القريب؟ 

أعتقد أننا سنفعل - إلى حد ما. أولاً ، أسرع الخلفيات الخلفية اليوم (على سبيل المثال ، إسبارطي و الفرامل أسفل، و SNARKs الأخرى التي تجمع بين ملفات بروتوكول الاختيار المجموع مع التزامات كثيرة الحدود) براهين كبيرة - عادةً ما تكون الجذر التربيعي في حجم الدائرة - لذلك لا يستخدمها الناس حقًا. أتوقع أن يتم تقليل حجم الإثبات ووقت المدقق بشكل مفيد في المستقبل القريب عبر تكوين العمق الأول مع SNARKs الصغيرة. على غرار تجميع الإثبات ، هذا يعني أن المُثبِت سيولد أولاً إثبات SNARK π باستخدام SNARK "سريع الإثبات ، واقي من الحجم الكبير" ، ولكن لا يتم الإرسال π إلى V. بدلا، P سوف تستخدم SNARK الصغيرة لإنتاج دليل π' التي تعرفها π, وأرسل π' إلى V. هذا يمكن أن يحلق ترتيبًا من الحجم من الخلفية الخلفية لـ SNARKs التي تحظى بشعبية اليوم. 

ثانيًا ، يمكن أن يساعد تسريع الأجهزة. القاعدة العامة القاسية للغاية هي أن وحدات معالجة الرسومات يمكنها شراء تسريع 10x على وحدات المعالجة المركزية ، و ASICs تسريع 10x على وحدات معالجة الرسومات. ومع ذلك ، لدي ثلاثة مخاوف على هذه الجبهة. أولاً ، قد يتم اختناق FFTs الكبيرة من خلال عرض النطاق الترددي للذاكرة بدلاً من العمليات الميدانية ، لذلك قد تشهد SNARKs التي تؤدي مثل FFTs تسريعًا محدودًا من الأجهزة المتخصصة. ثانيًا ، بينما ركز هذا المنشور على عنق الزجاجة للالتزام متعدد الحدود ، تتطلب العديد من SNARKs من المُثبِف القيام بعمليات أخرى أقل تكلفة قليلاً. لذا فإن كسر عنق الزجاجة للالتزام متعدد الحدود (على سبيل المثال ، تسريع الأسس المتعددة في SNARKs المستندة إلى السجل المنفصل) قد تترك عملية عنق زجاجة جديدة ليست أفضل بكثير من العملية القديمة. (على سبيل المثال ، تحتوي SNARKs بما في ذلك Groth16 و Marlin و PlonK أيضًا على المثل الذي يقوم به FFTs ، بالإضافة إلى الأسس المتعددة.) أخيرًا ، قد تستمر الحقول والمنحنيات الإهليلجية التي تؤدي إلى SNARKs الأكثر كفاءة في التطور لبعض الوقت ، وقد يخلق ذلك تحديات لتسريع المثقف القائم على ASIC.

على الجانب الأمامي ، قد نجد بشكل متزايد أن نهج "CPU emulator" لمشاريع مثل Cairo ، و RISC Zero ، و zkEVMs ، وغيرها يتوسع بشكل جيد (من حيث الأداء) مع تعقيد مجموعات تعليمات وحدة المعالجة المركزية. في الواقع ، هذا هو بالضبط أمل العديد من مشاريع zkEVM. قد يعني هذا أنه في حين أن الواجهة الأمامية تظل ثلاثة أوامر من حيث الحجم أو أكثر ، فإن الواجهات الأمامية تمكنت من دعم الأجهزة الافتراضية التي تتطابق بشكل متزايد مع بنى وحدة المعالجة المركزية الحقيقية. يتمثل أحد المخاوف التعويضية في أن الواجهات الأمامية قد تزداد تعقيدًا ويصعب تدقيقها ، حيث تنتشر الأدوات المشفرة يدويًا والتي تنفذ تعليمات معقدة بشكل متزايد. من المحتمل أن تلعب طرق التحقق الرسمية دورًا مهمًا في معالجة هذا القلق. 

أخيرًا ، على الأقل في تطبيقات blockchain ، قد نجد أن معظم العقود الذكية التي تظهر في البرية تستخدم بشكل أساسي تعليمات بسيطة وسهلة الاستخدام. قد يؤدي ذلك إلى تمكين النفقات العامة المنخفضة للواجهة الأمامية في الممارسة العملية مع الاحتفاظ بالعمومية وتجربة المطور المحسنة التي تأتي مع دعم لغات البرمجة عالية المستوى مثل Solidity ومجموعات التعليمات الغنية بما في ذلك تلك الخاصة بـ EVM. 

***

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

***

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

***

الآراء المعبر عنها هنا هي آراء أفراد AH Capital Management، LLC ("a16z") المقتبس منهم وليست آراء a16z أو الشركات التابعة لها. تم الحصول على بعض المعلومات الواردة هنا من مصادر خارجية ، بما في ذلك من شركات محافظ الصناديق التي تديرها a16z. على الرغم من أنه مأخوذ من مصادر يُعتقد أنها موثوقة ، لم تتحقق a16z بشكل مستقل من هذه المعلومات ولا تقدم أي تعهدات حول الدقة الدائمة للمعلومات أو ملاءمتها لموقف معين. بالإضافة إلى ذلك ، قد يتضمن هذا المحتوى إعلانات جهات خارجية ؛ لم تقم a16z بمراجعة مثل هذه الإعلانات ولا تصادق على أي محتوى إعلاني وارد فيها.

يتم توفير هذا المحتوى لأغراض إعلامية فقط ، ولا ينبغي الاعتماد عليه كمشورة قانونية أو تجارية أو استثمارية أو ضريبية. يجب عليك استشارة مستشاريك بخصوص هذه الأمور. الإشارات إلى أي أوراق مالية أو أصول رقمية هي لأغراض توضيحية فقط ، ولا تشكل توصية استثمارية أو عرضًا لتقديم خدمات استشارية استثمارية. علاوة على ذلك ، هذا المحتوى غير موجه أو مخصص للاستخدام من قبل أي مستثمرين أو مستثمرين محتملين ، ولا يجوز الاعتماد عليه تحت أي ظرف من الظروف عند اتخاذ قرار بالاستثمار في أي صندوق تديره a16z. (سيتم تقديم عرض للاستثمار في صندوق a16z فقط من خلال مذكرة الاكتتاب الخاص واتفاقية الاشتراك والوثائق الأخرى ذات الصلة لأي صندوق من هذا القبيل ويجب قراءتها بالكامل.) أي استثمارات أو شركات محفظة مذكورة ، يشار إليها ، أو الموصوفة لا تمثل جميع الاستثمارات في السيارات التي تديرها a16z ، ولا يمكن أن يكون هناك ضمان بأن الاستثمارات ستكون مربحة أو أن الاستثمارات الأخرى التي تتم في المستقبل سيكون لها خصائص أو نتائج مماثلة. قائمة الاستثمارات التي أجرتها الصناديق التي يديرها Andreessen Horowitz (باستثناء الاستثمارات التي لم يمنحها المُصدر إذنًا لـ a16z للإفصاح علنًا عن الاستثمارات غير المعلنة في الأصول الرقمية المتداولة علنًا) على https://a16z.com/investments /.

الرسوم البيانية والرسوم البيانية المقدمة في الداخل هي لأغراض إعلامية فقط ولا ينبغي الاعتماد عليها عند اتخاذ أي قرار استثماري. الأداء السابق ليس مؤشرا على النتائج المستقبلية. المحتوى يتحدث فقط اعتبارًا من التاريخ المشار إليه. أي توقعات وتقديرات وتنبؤات وأهداف وآفاق و / أو آراء معبر عنها في هذه المواد عرضة للتغيير دون إشعار وقد تختلف أو تتعارض مع الآراء التي يعبر عنها الآخرون. يرجى الاطلاع على https://a16z.com/disclosures للحصول على معلومات إضافية مهمة.