وجهة نظرنا الذاتية للغاية حول تاريخ إثباتات المعرفة الصفرية

تعد حجج المعرفة الصفرية والموجزة وغير التفاعلية (zk-SNARKs) من أوليات التشفير القوية التي تسمح لطرف واحد، المبرهن، بإقناع طرف آخر، المتحقق، بأن عبارة معينة صحيحة دون الكشف عن أي شيء آخر غير صحة البيان. لقد اكتسبت اهتمامًا واسع النطاق بسبب تطبيقاتها في الحوسبة الخاصة التي يمكن التحقق منها، مما يوفر دليلاً على صحة تنفيذ برامج الكمبيوتر والمساعدة في توسيع نطاق blockchain. نعتقد أن SNARKs سيكون لها تأثير كبير في تشكيل عالمنا، كما وصفنا ذلك في منشورنا. تعمل SNARKs كمظلة لأنواع مختلفة من أنظمة الإثبات، باستخدام مخططات التزام متعددة الحدود (PCS)، أو مخططات حسابية، أو براهين أوراكل تفاعلية (IOP) أو براهين قابلة للتحقق احتماليًا (PCP). ومع ذلك، فإن الأفكار والمفاهيم الأساسية تعود إلى منتصف الثمانينات. تسارع التطوير بشكل ملحوظ بعد تقديم Bitcoin وEthereum، والتي أثبتت أنها حالة استخدام مثيرة وقوية حيث يمكنك توسيع نطاقها باستخدام إثباتات المعرفة الصفرية (تسمى عمومًا إثباتات الصلاحية لحالة الاستخدام هذه تحديدًا). تعد SNARKs أداة أساسية لقابلية التوسع في blockchain. وكما يصف بن ساسون، فقد شهدت السنوات الأخيرة انفجارًا كمبريًا لإثباتات التشفير. يقدم كل نظام إثبات مزايا وعيوب، وقد تم تصميمه مع أخذ بعض المفاضلات في الاعتبار. يؤدي التقدم في الأجهزة والخوارزميات الأفضل والوسائط الجديدة والأدوات الذكية إلى تحسين الأداء وولادة أنظمة جديدة. يتم استخدام الكثير منها في الإنتاج، ونحن نواصل تجاوز الحدود. هل سيكون لدينا نظام إثبات عام لجميع التطبيقات أم عدة أنظمة تناسب الاحتياجات المختلفة؟ نعتقد أنه من غير المرجح أن يحكمهم نظام إثبات واحد للأسباب التالية:

1. تنوع التطبيقات.
2. أنواع القيود لدينا (فيما يتعلق بالذاكرة، أوقات التحقق، أوقات الإثبات).
3. الحاجة إلى المتانة (إذا تم كسر نظام إثبات واحد، فلا يزال لدينا أنظمة أخرى).

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

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

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

الأساسيات

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

براهين المعرفة الصفرية: الأصول (1985/1989)

ظهر مجال إثباتات المعرفة الصفرية في الأدبيات الأكاديمية من خلال ورقة بحثية كتبها جولدفاسر وميكالي وراكوف. وللحديث عن الأصول يمكنك مشاهدة الفيديو التالي. قدمت الورقة مفاهيم الاكتمال والسلامة والمعرفة الصفرية، وقدمت هياكل للبقايا التربيعية وعدم الثبات التربيعي.

بروتوكول فحص المبلغ (1992)

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

جولدفاسر كالاي روثبلوم (جي كي آر) (2007)

بروتوكول GKR هو بروتوكول تفاعلي يحتوي على مُثبِّت يعمل خطيًا في عدد بوابات الدائرة، بينما يعمل المُحقِّق بشكل خطي في حجم الدائرة. في البروتوكول، يتفق المثبت والمتحقق على دائرة حسابية مكونة من مروحة في اثنين على مجال محدود من العمق d، مع الطبقة d المقابلة لطبقة الإدخال والطبقة 0 هي طبقة الإخراج. يبدأ البروتوكول بمطالبة بخصوص مخرجات الدائرة، والتي يتم تقليلها إلى مطالبة بقيم الطبقة السابقة. باستخدام التكرار، يمكننا تحويل هذا إلى مطالبة بمدخلات الدائرة، والتي يمكن التحقق منها بسهولة. يتم تحقيق هذه التخفيضات عبر بروتوكول sumcheck.

مخطط الالتزام متعدد الحدود KZG (2010)

قدمت كيت وزافيروتشا وغولدبرغ في عام 2010 خطة التزام لكثيرات الحدود باستخدام مجموعة الاقتران الثنائية الخطية. يتكون الالتزام من عنصر مجموعة واحدة، ويمكن للملتزم أن يفتح الالتزام بكفاءة لأي تقييم صحيح لكثيرة الحدود. علاوة على ذلك، وبسبب تقنيات التجميع، يمكن فتح العديد من التقييمات. قدمت التزامات KZG إحدى لبنات البناء الأساسية للعديد من SNARKs الفعالة، مثل Pinocchio وGroth16 وPlonk. وهو أيضًا موجود في قلب EIP-4844. للحصول على فكرة عن تقنيات التجميع، يمكنك رؤية منشورنا على جسر Mina-Ethereum.

SNARKs العملية باستخدام المنحنيات الإهليلجية

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

1. احصل على مُثبتين أكثر كفاءة.
2. تقليل كمية المعالجة المسبقة.
3. وجود إعدادات عالمية وليست خاصة بالدائرة.
4. تجنب وجود الاجهزة الموثوقة.
5. تطوير طرق لوصف الدوائر باستخدام لغة عالية المستوى، بدلا من كتابة القيود متعددة الحدود يدويا.

بينوكيو (2013)

بينوكيو هو أول zk-SNARK عملي وقابل للاستخدام. يعتمد SNARK على البرامج الحسابية التربيعية (QAP). كان حجم الدليل في الأصل 288 بايت. قدمت سلسلة أدوات بينوكيو مترجمًا من كود C إلى الدوائر الحسابية، والتي تم تحويلها أيضًا إلى QAP. يتطلب البروتوكول أن يقوم المدقق بإنشاء المفاتيح الخاصة بالدائرة. واستخدمت أزواج المنحنى الإهليلجي للتحقق من المعادلات. كانت الخطوط المقاربة لتوليد الإثبات وإعداد المفتاح خطية في حجم الحساب، وكان وقت التحقق خطيًا في حجم المدخلات والمخرجات العامة.

جروث 16 (2016)

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

مضادات الرصاص وIPA (2016)

إحدى نقاط الضعف في KZG PCS هي أنها تتطلب إعدادًا موثوقًا به. بوتل وآخرون. قدم نظامًا فعالاً لحجة المعرفة الصفرية لفتحات التزامات بيدرسن التي تلبي علاقة المنتج الداخلية. تحتوي حجة المنتج الداخلي على مُثبت خطي، مع اتصال وتفاعل لوغاريتمي، ولكن مع التحقق من الوقت الخطي. كما قاموا بتطوير مخطط التزام متعدد الحدود لا يتطلب إعدادًا موثوقًا به. يتم استخدام أجهزة الكمبيوتر التي تستخدم هذه الأفكار بواسطة Halo 2 وKimchi.

سونيك ومارلين وبلونك (2019)

تعمل كل من Sonic و Plunk و Marlin على حل مشكلة الإعداد الموثوق به لكل برنامج الذي كان لدينا في Groth16، من خلال تقديم سلاسل مرجعية منظمة عالمية وقابلة للتحديث. يوفر Marlin نظام إثبات يعتمد على R1CS وهو جوهر Aleo.

قدم بلونك مخططًا حسابيًا جديدًا (سمي لاحقًا بلونكيش) واستخدام فحص المنتج الكبير لقيود النسخ. كما سمح بلونكيش بإدخال بوابات متخصصة لعمليات معينة، ما يسمى بالبوابات المخصصة. تحتوي العديد من المشاريع على إصدارات مخصصة من Plonk، بما في ذلك Aztec وzkSync وPolygon ZKEVM وMina's Kimchi وPlonky2 وHalo 2 وScroll وغيرها.

عمليات البحث (2018/2020)

قدم غابيزون ووليامسون نظام plookup في عام 2020، باستخدام الفحص الكبير للمنتج لإثبات أن القيمة مدرجة في جدول القيمة المحسوب مسبقًا. على الرغم من أن وسيطات البحث قد تم تقديمها سابقًا في آريا ، إلا أن البناء يتطلب تحديد التعدديات لعمليات البحث، مما يجعل البناء أقل كفاءة. أظهرت ورقة PlunkUp كيفية تقديم وسيطة plookup إلى Plunk. المشكلة في حجج البحث هذه هي أنها أجبرت المُثبِّت على دفع ثمن الجدول بأكمله، بغض النظر عن عدد عمليات البحث التي أجراها. وهذا يعني تكلفة كبيرة للجداول الكبيرة، وقد تم تكريس الكثير من الجهد لتقليل تكلفة المُثبِّت إلى عدد عمليات البحث التي يستخدمها فقط.
قدم هابوك LogUp ، الذي يستخدم المشتق اللوغاريتمي لتحويل فحص المنتج الكبير إلى مجموع المقلوبات. يعد LogUp أمرًا بالغ الأهمية للأداء في Polygon ZKEVM ، حيث يحتاجون إلى تقسيم الجدول بأكمله إلى عدة وحدات STARK. يجب ربط هذه الوحدات بشكل صحيح، وتفرض عمليات البحث عبر الجداول ذلك. يستخدم إدخال LogUp-GKR بروتوكول GKR لزيادة أداء LogUp. كان Caulk هو المخطط الأول الذي يحتوي على وقت إثبات خطي في حجم الجدول باستخدام وقت المعالجة المسبقة O(NlogN) والتخزين O(N)، حيث N هو حجم الجدول. تم اتباع العديد من المخططات الأخرى، مثل Baloo و fookup و cq و caulk+. يقدم Lasso العديد من التحسينات، مع تجنب الالتزام بالجدول إذا كان له هيكل معين. علاوة على ذلك، فإن مُثبت Lasso يدفع فقط مقابل إدخالات الجدول التي يتم الوصول إليها من خلال عمليات البحث. يستخدم Jolt Lasso لإثبات تنفيذ جهاز افتراضي من خلال عمليات البحث.

المتقشف (2019)

يوفر Spartan IOP للدوائر الموصوفة باستخدام R1CS، مع الاستفادة من خصائص متعددات الحدود متعددة المتغيرات وبروتوكول فحص المجموع. وباستخدام مخطط التزام متعدد الحدود مناسب، فإنه يؤدي إلى SNARK شفاف مع مُثبت زمني خطي.

هايبربلونك (2022)

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

مخططات قابلة للطي (2008/2021)

تقدم نوفا فكرة مخطط الطي، وهو نهج جديد لتحقيق حساب يمكن التحقق منه بشكل متزايد (IVC). يعود مفهوم IVC إلى Valiant الذي أظهر كيفية دمج دليلين للطول k في دليل واحد للطول k. الفكرة هي أنه يمكننا إثبات أي عملية حسابية طويلة الأمد من خلال الإثبات بشكل متكرر أن التنفيذ من الخطوة i إلى الخطوة I+1+1 صحيح والتحقق من الدليل الذي يوضح أن الانتقال من الخطوة i

−1−1to الخطوة كنت على حق. تتعامل نوفا بشكل جيد مع الحسابات الموحدة؛ تم توسيعه لاحقًا للتعامل مع أنواع مختلفة من الدوائر مع إدخال المستعر الأعظم. تستخدم Nova نسخة مريحة من R1CS وتعمل على منحنيات إهليلجية ودية. يتم استخدام العمل باستخدام دورات منحنيات ودية (على سبيل المثال، منحنيات المعكرونة) لتحقيق IVC أيضًا في Pickles، وهي لبنة البناء الرئيسية في Mina لتحقيق حالة موجزة. ومع ذلك، فإن فكرة الطي تختلف عن التحقق العودي SNARK. ترتبط فكرة المجمع ارتباطًا وثيقًا بمفهوم تجميع البراهين. قدمت هالو فكرة التراكم كبديل لتكوين الدليل العودي. توفر Protostar مخطط IVC غير موحد لـ Plunk الذي يدعم البوابات عالية الدرجة وعمليات البحث عن المتجهات.

استخدام وظائف التجزئة المقاومة للتصادم

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

تاينيرام (2013)

في SNARKs لـ C ، قاموا بتطوير SNARK استنادًا إلى PCP لإثبات صحة تنفيذ برنامج C، والذي تم تجميعه إلى TinyRAM، وهو كمبيوتر ذو مجموعة تعليمات مخفضة. استخدم الكمبيوتر بنية هارفارد مع ذاكرة وصول عشوائي قابلة للعنونة على مستوى البايت. من خلال الاستفادة من عدم الحتمية، يكون حجم الدائرة شبه خطي في حجم الحساب، والتعامل بكفاءة مع الحلقات التعسفية والمعتمدة على البيانات، وتدفق التحكم، والوصول إلى الذاكرة.

ستاركس (2018)

تم تقديم ستاركس بواسطة بن ساسون وآخرون. في عام 2018. لقد حققوا O(log2n)(log2⁡)

لا تتطلب أحجام الإثبات، مع المثبت والمتحقق السريع، إعدادًا موثوقًا به، ويُعتقد أنها آمنة بعد الكم. تم استخدامها لأول مرة بواسطة Starkware/Starknet، جنبًا إلى جنب مع القاهرة vm. ومن بين مقدماته الرئيسية التمثيل الوسيط الجبري (AIR) وبروتوكول FRI (إثبات القرب التفاعلي السريع لـ Reed-Solomon Oracle). يتم استخدامه أيضًا من قبل مشاريع أخرى (Polygon Miden، Risc0، Winterfell، Neptune) أو شهد تعديلات على بعض المكونات (zkSync's Boojum، Plonky2، Starky).

ليجيرو (2017)

يقدم Ligero نظام إثبات يحقق البراهين ذات الحجم

O(√n)، حيث n هو حجم الدائرة. يقوم بترتيب المعاملات متعددة الحدود في شكل مصفوفة ويستخدم الرموز الخطية.
يعتمد برنامج Brakedown على Ligero ويقدم فكرة مخططات الالتزام متعددة الحدود المحايدة للمجال.

بعض التطورات الجديدة

أظهر استخدام أنظمة إثبات مختلفة في الإنتاج مزايا كل نهج، وأدى إلى تطورات جديدة. على سبيل المثال، توفر عملية الحساب بلونكيش طريقة بسيطة لتضمين البوابات المخصصة ووسائط البحث؛ لقد أظهرت FRI أداءً رائعًا مثل PCS، مما أدى إلى Plonky. وبالمثل، أدى استخدام فحص المنتج الكبير في AIR (مما يؤدي إلى AIR العشوائي مع المعالجة المسبقة) إلى تحسين أدائه وتبسيط وسائط الوصول إلى الذاكرة. اكتسبت الالتزامات المستندة إلى وظائف التجزئة شعبية، استنادًا إلى سرعة وظائف التجزئة في الأجهزة أو تقديم وظائف تجزئة جديدة صديقة لـ SNARK.

خطط التزام متعددة الحدود الجديدة (2023)

مع ظهور SNARKs الفعالة القائمة على كثيرات الحدود متعددة المتغيرات، مثل Spartan أو HyperPlonk، كان هناك اهتمام متزايد بخطط الالتزام الجديدة المناسبة لهذا النوع من كثيرات الحدود. يقترح كل من Binius و Zeromorph و Basefold أشكالًا جديدة للالتزام بمتعددات الحدود متعددة الخطوط. يوفر Binius ميزة عدم وجود أي حمل لتمثيل أنواع البيانات (بينما تستخدم العديد من أنظمة الإثبات عناصر حقل 32 بت على الأقل لتمثيل البتات المفردة) ويعمل على الحقول الثنائية. يتكيف الالتزام مع الكبح، والذي تم تصميمه ليكون ملحدًا للميدان. يقوم Basefold بتعميم FRI على رموز أخرى غير Reed-Solomon، مما يؤدي إلى PCS غير محدد المجال.

أنظمة القيود القابلة للتخصيص (2023)

يقوم CCS بتعميم R1CS أثناء التقاط حسابات R1CS وPlonkish وAIR دون أي نفقات عامة. يؤدي استخدام CCS مع Spartan IOP إلى إنتاج SuperSpartan، الذي يدعم القيود عالية الدرجة دون أن يتحمل المُبرهن تكاليف تشفير تتزايد مع درجة القيد. على وجه الخصوص، ينتج SuperSpartan SNARK لـ AIR مع مُثبت زمني خطي.

خاتمة

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

تنصل:

1. تمت إعادة طباعة هذه المقالة من [lambdaclass]، جميع حقوق الطبع والنشر مملوكة للمؤلف الأصلي [LambdaClass]. إذا كانت هناك اعتراضات على إعادة الطبع هذه، فيرجى الاتصال بفريق Gate Learn ، وسوف يتعاملون معها على الفور.
2. إخلاء المسؤولية: الآراء والآراء الواردة في هذه المقالة هي فقط آراء المؤلف ولا تشكل أي نصيحة استثمارية.
3. تتم ترجمة المقالة إلى لغات أخرى بواسطة فريق Gate Learn. ما لم يُذكر ذلك، يُحظر نسخ أو توزيع أو سرقة المقالات المترجمة.