حدس ZKP: كهف علي بابا

يتيح إثبات المعرفة الصفرية (ZKP) للمُثبِت إقناع المتحقّق بأنه يعرف سرًا (أو بأن عبارة ما صحيحة) دون الكشف عن السر نفسه. وله ثلاث خصائص: الاكتمال، والسلامة، والمعرفة الصفرية.

إذا كان المُثبِت يعرف السر، فبإمكانه دائمًا إقناع المتحقّق. وسينجح المُثبِت الصادق الذي يتبع البروتوكول باحتمال يساوي 1 (أو باحتمال ساحق). ولن يرفض المتحقّق برهانًا صحيحًا.

لا يستطيع مُثبِت غشاش (لا يعرف السر) إقناع المتحقّق إلا باحتمال مهمل. ويؤدي كل دور من أدوار التفاعل إلى خفض احتمال الغش؛ فبعد k من الأدوار، لا يتجاوز احتمال نجاح الغشاش 2^{-k}.

لا يتعلم المتحقّق شيئًا يتجاوز حقيقة صحة العبارة. وبصورة رسمية، يوجد محاكٍ يستطيع، من دون معرفة السر، إنتاج سجل لا يمكن تمييزه عن سجل تفاعل حقيقي بين المُثبِت والمتحقّق. ولا يكتسب المتحقّق أي معرفة إضافية.

يحتوي كهف على ممر دائري يتوسطه باب سحري. تدّعي المُثبِتة (Alice) أنها تعرف كلمة المرور. ينتظر المتحقّق (Bob) في الخارج. تدخل Alice وتختار الاتجاه الأيسر أو الأيمن. ثم ينادي Bob طالبًا منها الخروج من أحد الجانبين. إذا كانت Alice تعرف كلمة المرور، فستخرج دائمًا من الجانب المطلوب. احتمال الغش في كل دور: 1/2.

بعد 20 دورًا، ينجح الغشاش باحتمال 2^{-20}، أي نحو مرة واحدة من كل مليون. أما Alice، التي تعرف كلمة المرور، فتنجح في كل مرة. ولا يتعلم Bob كلمة المرور مطلقًا؛ فهو لا يرى سوى خروج Alice من الجانب الذي طلبه. وهذا هو مفهوم المعرفة الصفرية.

تتطلب براهين المعرفة الصفرية التفاعلية تبادلًا ذهابًا وإيابًا بين المُثبِت والمتحقّق. أما براهين المعرفة الصفرية غير التفاعلية (NIZKs) فتستخدم تحويل Fiat-Shamir، إذ تستبدل التحدي العشوائي من المتحقّق بتجزئة للالتزام (تجزئة = أوراكل عشوائي). وينتج عن ذلك نص برهان واحد يمكن لأي شخص التحقق منه.

يكون ZKP إثباتَ معرفة (PoK) إذا كانت استراتيجية المُثبِت تعني إمكانية استخراج السر منه. وهذا أقوى من مجرد إثبات صحة عبارة ما. وتُعد توقيعات ECDSA وSchnorr براهين معرفة غير تفاعلية للمفتاح الخاص.

مصادقة كلمات المرور دون إرسال كلمة المرور. التحقق من العمر دون الكشف عن تاريخ الميلاد. براهين النطاق (راتبك ضمن نطاق معين) دون الكشف عن الراتب. في Blockchain: إثبات معرفة معاملة صحيحة دون الكشف عن المعاملة.

المعرفة الصفرية المثالية: مخرجات المُحاكي مطابقة لسجل الحوار الحقيقي. المعرفة الصفرية الإحصائية: لا يمكن تمييزها إلا باحتمال مهمل. المعرفة الصفرية الحسابية: لا يستطيع المدققون ذوو الزمن متعدد الحدود تمييزها. الضمانات الأضعف = براهين أكثر كفاءة.

الكهف هو بروتوكول من ثلاث حركات: التزام → تحدٍّ → استجابة. ويُسمّى رسميًا بروتوكول سيغما. معظم براهين المعرفة الصفرية العملية، مثل Schnorr وPedersen وFiat-Shamir، هي بروتوكولات سيغما أو تراكيب منها. جاءت التسمية من شكل Σ لمخطط تدفق الرسائل.

تثبت براهين المعرفة الصفرية معرفة سر دون كشفه. ولها ثلاث خصائص: الاكتمال، والمتانة، والمعرفة الصفرية. يوضح كهف علي بابا برهان معرفة صفرية تفاعليًا. التالي: بروتوكولات سيغما وتحديد الهوية باستخدام Schnorr.