zk-SNARKs: براهين موجزة غير تفاعلية

‏zk-SNARK ‏(Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) هو برهان: (1) يحقق المعرفة الصفرية، (2) موجز (برهان صغير جدًا وتحقق سريع بغض النظر عن حجم الحساب)، (3) غير تفاعلي (سلسلة برهان واحدة).

تعمل بروتوكولات سيغما مع العبارات البسيطة، مثل معرفة اللوغاريتم المتقطع. أما الحسابات المعقدة — «لقد نفذت هذه الدالة بصورة صحيحة على مدخلات خاصة» — فتحتاج إلى نظام براهين عام الغرض. تثبت SNARKs حسابات عامة في زمن تحقق O(1).

يُعبَّر عن الحساب أولًا بوصفه دائرة حسابية: رسم بياني موجّه لا دوري من بوابات الجمع والضرب فوق حقل منتهٍ. مثال: إثبات معرفة x بحيث x^3 + x + 5 = 35 دون كشف أن x=3. تتكون الدائرة من نحو 5 بوابات.

تُحوَّل الدائرة الحسابية إلى R1CS: مجموعة من القيود (A*z)*(B*z) = C*z حيث إن z متجه يضم قيم جميع الأسلاك. تصبح كل بوابة ضرب قيدًا واحدًا. يجب على المُثبِت إيجاد z يحقق جميع القيود دون كشف الأسلاك الخاصة.

تُحوَّل R1CS إلى QAP: كثيرات الحدود A(x) وB(x) وC(x) بحيث يكون A(x)*B(x)-C(x) قابلًا للقسمة على كثير الحدود المستهدف t(x) إذا وفقط إذا تحققت القيود. يثبت المُثبِت أنه يعرف حاصل القسمة كثير الحدودي H(x) دون كشف الشاهد.

يُعد Groth16 ‏(2016) أكثر أنظمة SNARK العامة كفاءة. بعد إعداد موثوق (توليد CRS)، ينتج المُثبِت برهانًا من 3 عناصر من المجموعة (نحو 192 بايتًا لـ BLS12-381). التحقق: 3 عمليات اقتران. ويظل حجم البرهان ثابتًا بغض النظر عن حجم الدائرة.

يتطلب Groth16 إعدادًا موثوقًا لكل دائرة على حدة: تُولَّد مخلفات سامة (سر عشوائي)، ثم تُحسب سلسلة المرجع المشترك، وبعد ذلك تُدمَّر المخلفات السامة. إذا بقيت هذه المخلفات، يستطيع مهاجم تزوير البراهين. وتوزّع المراسم متعددة الأطراف، مثل Powers of Tau، الثقة بين المشاركين.

يستخدم PLONK ‏(2019) إعدادًا موثوقًا عامًا: تكفي مراسم واحدة لجميع الدوائر حتى حد حجمي معين. ولا حاجة إلى إعداد خاص بكل دائرة. والمقابل هو براهين أكبر قليلًا من براهين Groth16. ويُستخدم في تطبيقات ZK-EVM، مثل Polygon Hermez وzkSync Era.

لا تتطلب STARKs ‏(Scalable Transparent ARguments of Knowledge) إعدادًا موثوقًا، وتستخدم دوال التجزئة (الآمنة بعديًا). والمقابل هو براهين أكبر حجمًا (عشرات KB مقابل 200 بايت). وتُستخدم في StarkWare وStarkNet ولغة Cairo. أما SNARKs فأصغر حجمًا، بينما STARKs آمنة في مواجهة الحوسبة الكمومية.

يستخدم Groth16 الاقترانات الثنائية الخطية: e: G1 × G2 → GT حيث e(a*P, b*Q) = e(P,Q)^{ab}. ويتيح ذلك التحقق من هويات كثيرات الحدود في الأس دون كشف القيم. وقد حُسِّن منحنى BLS12-381 لتنفيذ اقترانات Groth16 بكفاءة.

يستغرق توليد برهان Groth16 لدائرة تضم 10^6 بوابة نحو 10 ثوانٍ على وحدة معالجة مركزية حديثة. أما التحقق فيستغرق نحو 1 ms. وهذا التفاوت مقصود: فالمُثبِت، الذي أجرى الحسابات الثقيلة، ينفذ العمل؛ بينما لا ينفذ المدقق، أي عقدة سلسلة الكتل، إلا عملًا شبه معدوم.

ما العيب الرئيسي في Groth16 مقارنةً بـ PLONK؟

تثبت zk-SNARKs حسابات عامة باستخدام براهين ثابتة الحجم. المسار: الحساب → الدائرة الحسابية → R1CS → QAP → برهان SNARK. يُعد Groth16 الأكثر كفاءة (إعداد موثوق لكل دائرة)، بينما يستخدم PLONK إعدادًا عامًا. التالي: تطبيقات براهين المعرفة الصفرية في سلسلة الكتل.