ZKP و zk-SNARKs
الخلاصة
- zk-SNARKs = حجج معرفة موجزة وغير تفاعلية قائمة على انعدام المعرفة
- تتيح لطرفٍ ما إثبات أنه يعرف شيئًا دون الكشف عن المعلومة نفسها
- يستخدم Zcash تقنيات zk-SNARKs لإثبات أن المعاملة صالحة (المبالغ صحيحة، والمدخلات غير منفقة) من دون الكشف عن المُرسِل أو المُستقبِل أو المبلغ
- تعني كلمة "موجزة" أن الإثبات صغير جدًا وسريع التحقق حتى بالنسبة إلى العبارات المعقدة
- تستخدم مجموعة Orchard نظام Halo 2، وهو نظام zk-SNARK لا يتطلب إعدادًا موثوقًا
ما هو الإثبات؟
تُعدّ الإثباتات أساس كل الرياضيات. والإثبات هو ادعاء أو مبرهنة تحاول إثباتها، مع تسلسل من الاشتقاقات يُستخدم لإعلان أن المبرهنة قد تم إثباتها. على سبيل المثال، يمكن لأي شخص (المدقّق) التحقق بشكل مستقل من أن مجموع زوايا المثلث يساوي 180°.
الإثباتات
المُثبِت ---> يقدّم ادعاءً ---> يختار المُدقّق ---> قبول/رفض
(كلٌّ من المُثبِت والمُدقّق عبارة عن خوارزمية)
في علوم الحاسوب، يُطلق على الإثباتات التي يمكن التحقق منها بكفاءة اسم إثباتات NP. يمكن التحقق من هذه الإثباتات القصيرة في زمن كثير الحدود. والفكرة العامة هي: "يوجد حل لمبرهنة ما ويتم تمريره إلى المُدقّق ليتحقق منه"
في لغة NP = يجب أن يتحقق شرطان:
الاكتمال: ستُقبَل الادعاءات الصحيحة من قبل المُدقّق (مما يسمح للمُثبِتين الصادقين بالوصول إلى التحقق)
السلامة: لن تكون هناك إثباتات للادعاءات الخاطئة (وبالنسبة إلى أي استراتيجية يتبعها مُثبِت غشّاش، فلن يتمكن من إثبات صحة ادعاء غير صحيح).
الإثباتات التفاعلية والاحتمالية
التفاعل: بدلًا من مجرد قراءة الإثبات، ينخرط المُدقّق مع المُثبِت ذهابًا وإيابًا عبر عدة جولات من الرسائل.
العشوائية: تكون طلبات المُدقّق إلى المُثبِت عشوائية، ويجب على المُثبِت أن يكون قادرًا على الإجابة عنها جميعًا بشكل صحيح.
وباستخدام التفاعل والعشوائية معًا، يصبح من الممكن إثبات ادعاء لمُدقّق أعمى ضمن زمن احتمالي كثير الحدود (PPT).
هل يمكن للإثباتات التفاعلية التحقق بكفاءة من أكثر من مجرد إثباتات NP؟
إثباتات NP مقابل إثباتات IP:
| العبارة | NP | IP |
|---|
| NP | نعم | نعم |
| CO-NP | لا | نعم |
| #P | لا | نعم |
| PSPACE | لا | نعم |
NP - يوجد حل لعبارة ما
CO-NP - إثبات عدم وجود حلول لعبارة ما
#P - إحصاء عدد الحلول الموجودة لعبارة ما
PSPACE - إثبات تعاقبٍ من عبارات مختلفة
ما هو انعدام المعرفة؟
ما يستطيع المُدقّق حسابه بعد التفاعل مطابق لما كان يمكنه إثباته مسبقًا. فالتفاعل عبر جولات متعددة بين المُثبِت والمُدقّق لم يزد القدرة الحاسوبية للمُدقّق.
نموذج المحاكاة (Simulation Paradigm)
توجد هذه التجربة في مختلف مجالات علم التشفير. وهي تعرض "رؤية حقيقية" و"رؤية مُحاكاة".
الرؤية الحقيقية: جميع التواريخ الممكنة للتفاعلات بين المُثبِت والمُدقّق (P,V)
الرؤية المُحاكاة: يُحاكي المُدقّق جميع التفاعلات الممكنة بين المُثبِت والمُدقّق
يحاول مميّز يعمل في زمن كثير الحدود تحديد ما إذا كان ينظر إلى الرؤية الحقيقية أو الرؤية المُحاكاة، ويطلب عيّنة من كلتيهما بشكل متكرر.
ويُقال إن الرؤيتين "غير قابلتين للتمييز حسابيًا" إذا كان احتمال النجاح، بالنسبة إلى جميع خوارزميات/استراتيجيات التمييز، حتى بعد تلقي عدد كثير الحدود من العينات من الرؤية الحقيقية أو المُحاكاة، أكبر من 1/2.
حجج المعرفة القائمة على انعدام المعرفة
يكون البروتوكول التفاعلي (P,V) قائمًا على انعدام المعرفة إذا وُجد مُحاكي (خوارزمية) بحيث تكون توزيعات الاحتمال التي تميّز بين الرؤية الحقيقية والرؤية المُحاكاة غير قابلة للتمييز حسابيًا، وذلك بالنسبة إلى كل مُدقّق احتمالي يعمل في زمن كثير الحدود (عندما تكون المبرهنة صحيحة).
تكون البروتوكولات التفاعلية مفيدة عندما يوجد مُدقّق واحد فقط. ومن الأمثلة على ذلك مدقّق ضرائب في تطبيق "إثبات الضرائب" القائم على انعدام المعرفة.
ما هو SNARK؟
حجة معرفة موجزة وغير تفاعلية
التعريف العام - إثبات موجز على أن عبارةً ما صحيحة. يجب أن يكون الإثبات قصيرًا وسريع التحقق. في SNARKS، تُرسَل رسالة واحدة من المُثبِت إلى المُدقّق. وبعد ذلك يمكن للمُدقّق أن يختار القبول أو الرفض.
مثال على عبارة: "أنا أعرف رسالة (m) بحيث إن SHA256(m)=0"
في zk-SNARK، لا يكشف الإثبات أي شيء عن الرسالة (m).
كثيرات الحدود: مجموع حدود تحتوي على ثابت (مثل 1,2,3)، ومتغيرات (مثل x,y,z)، وأسّ للمتغيرات (مثل x², y³).
مثال: "3x² + 8x + 17"
الدائرة الحسابية: نموذج لحساب كثيرات الحدود. وبصورة أعمّ، يمكن تعريفها على أنها رسم بياني موجّه لا دوري تُنفَّذ عند كل عقدة فيه عملية حسابية. تتكون الدائرة من بوابات جمع، وبوابات ضرب، وبعض البوابات الثابتة. وبالطريقة نفسها التي تنقل بها الدوائر المنطقية البِتّات عبر الأسلاك، تنقل الدوائر الحسابية الأعداد الصحيحة.
في هذا المثال، يريد المُثبِت إقناع المُدقّق بأنه يعرف حلًا للدائرة الحسابية.
الالتزامات: للقيام بذلك، يضع المُثبِت جميع القيم (الخاصة والعامة) المرتبطة بالدائرة داخل التزام. وتُخفي الالتزامات مدخلاتها باستخدام دالة يكون ناتجها غير قابل للعكس.
يُعد Sha256 مثالًا على دالة تجزئة يمكن استخدامها في مخطط التزام.
بعد أن يلتزم المُثبِت بالقيم، تُرسَل الالتزامات إلى المُدقّق (مع الثقة بأنه غير قادر على كشف أي من القيم الأصلية). وبعد ذلك يستطيع المُثبِت أن يُظهر للمُدقّق معرفته بكل قيمة من القيم الموجودة على عقد الرسم البياني.
Fiat-Shamir Transform
لجعل البروتوكول غير تفاعلي، يُنشئ المُثبِت العشوائية (المستخدمة في التحدي المخفي) نيابةً عن المُدقّق باستخدام دالة تجزئة تشفيرية. ويُعرف هذا باسم المِعْمَار العشوائي (random oracle). ويمكن للمُثبِت بعد ذلك إرسال رسالة واحدة إلى المُدقّق الذي يستطيع التحقق من صحتها.
ولتكوين SNARK يمكن استخدامه مع الدوائر العامة، يلزم عنصران:
مخطط التزام وظيفي: يتيح للملتزِم أن يلتزم بكثير حدود عبر سلسلة قصيرة يمكن للمُدقّق استخدامها لتأكيد التقييمات المُدَّعاة لكثير الحدود المُلتزَم به.
Oracle تفاعلي لكثيرات الحدود: يطلب المُدقّق من المُثبِت (الخوارزمية) فتح جميع الالتزامات عند نقاط مختلفة يختارها هو باستخدام مخطط التزام كثيرات الحدود، ثم يتحقق من أن الهوية بينها صحيحة.
الإعداد
تساعد إجراءات الإعداد المُدقّق من خلال تلخيص دائرة ما وإخراج معاملات عامة.
أنواع إعداد المعالجة المسبقة:
Trusted Setup لكل دائرة - يُجرى مرة واحدة لكل دائرة. وهو خاص بدائرة بعينها، ويجب الحفاظ على العشوائية السرية (Common Reference String) في سرية تامة ثم إتلافها.
إن تعرّض الإعداد للاختراق في هذه الطريقة يعني أن المُثبِت غير النزيه يمكنه إثبات عبارات كاذبة.
Trusted but Universal Setup - لا يلزم تشغيل trusted setup إلا مرة واحدة، ثم يصبح من الممكن بعد ذلك إجراء المعالجة المسبقة لدوائر متعددة بصورة حتمية.
Transparent Setup (No Trusted Setup)- لا تستخدم خوارزمية المعالجة المسبقة أي عشوائية سرية على الإطلاق.
أنواع بُنى إثبات SNARK:
Groth16: يتطلب Trusted Setup، لكنه يوفّر إثباتات قصيرة جدًا يمكن التحقق منها بسرعة.
Sonic/Marlin/PLONK: Trusted Setup عام.
DARK/Halo/STARK: لا تتطلب إعدادًا موثوقًا، لكنها تنتج إثباتات أطول قليلًا أو قد تستغرق وقتًا أطول لتشغيل المُثبِت.
تكون SNARKS مفيدة عندما تكون هناك حاجة إلى عدة مُدقّقين، كما في blockchain مثل Zcash أو zk-Rollup مثل Aztec، بحيث لا تضطر عقد التحقق المتعددة إلى التفاعل عبر عدة جولات مع كل إثبات.
كيف تُطبَّق zk-SNARK's في Zcash؟
بشكل عام، تُعدّ الإثباتات القائمة على انعدام المعرفة أداة لفرض السلوك النزيه داخل البروتوكولات من دون الكشف عن أي معلومات.
Zcash هو blockchain عام يسهّل المعاملات الخاصة. وتُستخدم zk-SNARK's لإثبات أن المعاملة الخاصة صالحة ضمن قواعد إجماع الشبكة من دون الكشف عن أي تفاصيل أخرى حول المعاملة.
فيديو توضيحي - في هذه المحاضرة، يقدّم Ariel Gabizon أوصافًا لشجرة التزامات الملاحظات في Zcash، والتقييم الأعمى لكثيرات الحدود، والتحديات المخفية تماثليًا، وكيفية تطبيقها على الشبكة.
اقرأ كتاب Halo2 لمزيد من المعلومات.
تطبيقات أخرى لانعدام المعرفة
توفر zk-SNARKs عدة مزايا في مجموعة متنوعة من التطبيقات المختلفة. لنلقِ نظرة على بعض الأمثلة.
قابلية التوسع: يتحقق ذلك من خلال "الاستعانة بالحوسبة الخارجية". ليست هناك حاجة صارمة إلى انعدام المعرفة لكي تتمكن سلسلة L1 من التحقق من عمل خدمة خارج السلسلة. كما أن المعاملات ليست بالضرورة خاصة على zk-EVM.
تتمثل ميزة خدمة Rollup القائمة على الإثبات (zk-Rollup) في معالجة دفعة من مئات/آلاف المعاملات، بينما تكون L1 قادرة على التحقق من إثبات موجز يفيد بأن جميع المعاملات قد تمت معالجتها بشكل صحيح، مما يزيد من إنتاجية معاملات الشبكة بمقدار 100 أو 1000 مرة.
التشغيل البيني: يتحقق ذلك على zk-Bridge من خلال "قفل" الأصول على سلسلة المصدر وإثبات للسلسلة الهدف أن الأصول قد تم قفلها (إثبات الإجماع).
الامتثال: تستطيع مشاريع مثل Espresso إثبات أن معاملة خاصة متوافقة مع القوانين المصرفية المحلية من دون الكشف عن تفاصيل المعاملة.
مكافحة التضليل: من بين عدة أمثلة خارج blockchain والعملات المشفرة، هناك استخدام توليد الإثباتات على الصور التي عالجتها مؤسسات الأخبار ووسائل الإعلام، بحيث يتمكن المشاهدون من التحقق بشكل مستقل من مصدر الصورة وجميع العمليات التي أُجريت عليها. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
للمزيد من التعلّم:
ببليوغرافيا انعدام المعرفة - a16z Crypto
zkSNARK's مع Hanh Huynh Huu
Zcash: Halo 2 و SNARKs من دون Trusted Setups - Sean Bowe في Dystopia labs
إثباتات انعدام المعرفة مع Avi Wigderson - Numberphile
إثباتات انعدام المعرفة التفاعلية - مقال Chainlink
المحاضرة 1: مقدمة وتاريخ ZKP - zklearning.org
شرح مبسّط للدوائر الحسابية - Medium
قابلية التوسع مملة، والخصوصية ميتة: إثباتات ZK، ما فائدتها؟
صفحات ذات صلة
