** TL ؛ DR **
- ** ما هي عملية بناء SNARK؟ **
المشكلات التي يجب إثباتها - الدوائر الحسابية - R1CS - كثيرات الحدود
- ** لماذا التحويل إلى كثير الحدود في النهاية؟ **
نظرًا لخصائص كثيرات الحدود ، يتم تقصير وقت التحقق بشكل فعال ، ويتم تحقيق البساطة.
- ** كيف نحقق صفر معرفة؟ **
لوضعها ببساطة ، في عملية اشتقاق كثير الحدود ، يتم اختيار رقمين عشوائيين آخرين ، بحيث يمكن لكثير الحدود المشتق أن يمنع المدقق من الحصول على معاملات كثير الحدود الأصلي ، أي المدخلات السرية للمثقف ، وذلك لتحقيق ZK.
- ** كيف نحقق عدم التفاعل؟ **
قبل أن يبدأ الإثبات ، يتم تقديم طرف ثالث ، أي إعداد موثوق به ، يقوم بتعيين المهمة الأصلية للمدقق لتحديد أرقام عشوائية للإعداد الموثوق به ، وذلك لإدراك عدم التفاعل بين المدقق والمثقف.
جذبت تقنية ZK الكثير من الاهتمام في مجال Web3 في العامين الماضيين. بدءًا من Rollup ، تحاول المزيد والمزيد من المشاريع على مسارات مختلفة استخدام تقنية ZK. من بينها ، SNARK و STARK هما المصطلحان الأكثر شيوعًا. من أجل فهم أفضل لتطبيق تقنية ZK في مرحلة لاحقة ، ** ستعمل هذه المقالة على تبسيط منطق إثبات SNARK من منظور غير تقني ، ثم استخدام * * ** Scroll’s zk Rollup ** ** تستخدم كمثال لتوضيح تشغيل نظام zk proof. **
الغرض من المقال هو شرح المنطق الأساسي الذي يسهل قراءته ، وسيحاول تجنب استخدام المصطلحات ، ولن يدخل في التفاصيل مثل التحولات الرياضية ، أرجو أن يغفر لي أي سهو.
في يناير 2012 ، شارك Alessandro Chiesa ، الأستاذ في جامعة كاليفورنيا ، بيركلي ، في تأليف ورقة بحثية عن SNARK واقترح مصطلح zk-SNARK.
zk-SNARK ، الاسم الكامل حجة المعرفة غير التفاعلية المختصرة الصفرية ، هو نظام إثبات باستخدام تقنية ZK. ** تجدر الإشارة إلى أن SNARK هو اسم فئة المخططات ، وهناك العديد من طرق التجميع المختلفة التي يمكنها تنفيذ SNARK. **
- المعرفة الصفرية (المعرفة الصفرية): سيتم إخفاء المحتوى الذي لا يعرفه إلا المُثبِّت ، ولا يمكن لأي شخص آخر رؤيته باستثناء المُثِّل.
- قصير (موجز): الدليل الذي تم إنشاؤه صغير ووقت التحقق سريع.
- غير تفاعلي (غير تفاعلي): يوجد تفاعل ضئيل أو معدوم بين المُثبِت والمُحقق.
- الحجة: لا يكون التحقق من المدقق صالحًا إلا للمثب ذي القدرة الحوسبية المحدودة ، لأن المُثبِت الذي يتمتع بقوة حوسبة فائقة يمكن أن يبرهن ، أي أن النظام لديه موثوقية حسابية.
- المعرفة: لا يستطيع المُثبَّت حساب الإثبات إلا إذا كان يعرف بعض المعلومات التي لا يعرفها المدقق.
ما يحتاج zk-SNARK إلى حله هو “مشكلة التحقق من الحساب” ، أي ما إذا كان المدقق يمكنه التحقق بكفاءة من نتائج الحساب دون معرفة خصوصية المُثبِّت.
سيستخدم ما يلي عملية البناء المبسطة لـ zk-SNARK لتوضيح كيف يجمع النظام بين المعرفة الصفرية لتحقيق التحقق الفعال. **
** بناء Zk-SNARK **
** حول المشكلة ليتم إثباتها إلى كثير الحدود **
لتوضيح الأمر ببساطة ، فإن فكرة SNARK هي تحويل إثبات ما إذا كانت العبارة صحيحة أم لا إلى دليل على ما إذا كانت المساواة متعددة الحدود صحيحة أم لا.
عملية التحويل بأكملها: مشاكل يجب التحقق منها ➡ دائرة حسابية R1CS ➡ متعدد الحدود ➡ التحويل بين كثيرات الحدود
** السؤال المراد التحقق منه➡ دائرة حسابية **
لإثبات ما إذا كان السؤال صحيحًا من خلال الحساب ، يجب أولاً تحويل السؤال المراد إثباته إلى مشكلة حسابية ، ويمكن وصف أي عملية حسابية بأنها دائرة حسابية.
تتكون الدوائر الحسابية عادة من الثوابت و “بوابات الإضافة” و “بوابات الضرب” ، ومن خلال تراكب البوابات يمكننا بناء كثيرات حدود معقدة.
كثير الحدود التي أنشأتها الدائرة الحسابية في الشكل أعلاه هي: (Inp1 + Inp2) \ * (- 1) = الإخراج
المشكلة في الواقع معقدة للغاية لتتحول إلى دائرة حسابية ، يمكننا ببساطة فهمها على النحو التالي: إدخال بعض المحتوى ، يتم تحويل المحتوى بواسطة الدائرة ، وأخيراً إخراج نتيجة. الآن:
بناءً على مفهوم الدوائر الحسابية ، نقوم ببناء دائرة حسابية لتوليد البراهين ، وهي:
تحتوي الدائرة على مجموعتين من المدخلات ، المدخلات العامة x والمدخلات السرية w. تعني المدخلات العامة x أن المحتوى هو قيمة ثابتة للمشكلة المراد إثباتها ، وهو أمر معروف لكل من المدقق والمُثبِت ، ويعني الإدخال السري w أن المحتوى معروف فقط للمثقف.
الدائرة الحسابية التي أنشأناها هي C (x ، w) = 0 ، أي المدخلات x و w من خلال الدائرة ، والنتيجة النهائية هي 0. عندما يعلم المُثبِت والمحقق أن ناتج الدائرة يساوي 0 وأن المُدخل العام هو x ، يحتاج المُثبِّت إلى إثبات أنه يعرف المُدخلات السرية w.
** الدائرة الحسابية ➡R1CS **
نحتاج أخيرًا إلى كثير الحدود ، لكن الدائرة الحسابية لا يمكن تحويلها مباشرة إلى كثير حدود ، وهناك حاجة إلى R1CS كوسيط بين الاثنين ، لذلك يتم تحويل الدائرة الحسابية إلى R1CS أولاً.
R1CS ، الاسم الكامل قيود الرتبة 1 (نظام القيد من الدرجة الأولى) ، هي لغة لوصف الدوائر ، والتي هي أساسًا معادلة متجه المصفوفة. على وجه التحديد ، R1CS عبارة عن سلسلة من ثلاثة نواقل (أ ، ب ، ج) ، وحل R1CS هو متجه s ، حيث يجب أن تفي s بالمعادلة:
فيما بينها ، يمثل عملية المنتج الداخلي.
- يمكن العثور على التحويل الرياضي المحدد هنا في Vatalik: البرامج الحسابية التربيعية: من الصفر إلى البطل *
نحتاج فقط إلى معرفة أن دور ** R1CS هو تحديد وصف كل بوابة في الدائرة الحسابية ، بحيث تفي المتجهات بين كل بوابة بالعلاقة المذكورة أعلاه. **
** R1CS➡ متعدد الحدود **
بعد الحصول على وسيط R1CS ، يمكننا تحويله إلى مكافئ متعدد الحدود.
يمكن إجراء التحويلات المتكافئة بين المصفوفات ومتعددة الحدود كما هو موضح في الشكل التالي:
متعدد الحدود
تحويل إلى مصفوفة
وفقًا لطبيعة التحويل المكافئ أعلاه ، بالنسبة للمصفوفة التي ترضي R1CS ، يمكننا استخدام طريقة الاستيفاء لاغرانج لاستعادة كل معامل من كثير الحدود. وبناءً على هذه العلاقة ، يمكننا اشتقاق مصفوفة R1CS كعلاقة متعددة الحدود ، وهي:
** ملاحظة: تمثل A ، B ، C كثير الحدود على التوالي **
يتوافق كثير الحدود مع قيد مصفوفة R1CS يتوافق مع المشكلة التي نريد إثباتها. ومن خلال التحويل أعلاه ، يمكننا أن نعرف أنه إذا كانت كثيرات الحدود تفي بالعلاقة أعلاه ، فهذا يعني أن مصفوفة R1CS الخاصة بنا صحيحة ، مما يشير إلى أن المثل في الدائرة الحسابية ، كما أن الإدخال السري لـ صحيح.
حتى هذه النقطة ، تم تبسيط مشكلتنا إلى: يقوم المدقق باختيار رقم x عشوائيًا ، ويطلب من المصدق إثبات أن A (x) \ * B (x) = C (x) صحيح. إذا كان هذا صحيحًا ، فهو يعني أن الإدخال السري الخاص بالمصدق صحيح.
** التحويل بين كثيرات الحدود **
في الدوائر الحسابية المعقدة ، توجد عشرات الآلاف من البوابات ، وعلينا التحقق مما إذا كانت كل بوابة تفي بقيد R1CS. بمعنى آخر ، نحتاج إلى التحقق من المساواة بين A (x) \ * B (x) = C (x) عدة مرات ، لكن كفاءة التحقق المنفصل واحدًا تلو الآخر منخفضة جدًا. كيف يمكننا التحقق من صحة جميع قيود البوابة في وقت واحد؟ الجنس؟
لتسهيل الفهم ، نقدم P (x) ، دعنا P (x) = A (x) \ * B (x) - C (x)
نحن نعلم أن أي كثير حدود يمكن أن تتحلل إلى كثيرات حدود خطية طالما أنها تحتوي على حل. لذلك قمنا بتقسيم P (x) إلى F (x) و H (x) ، وهي:
ثم F (x) عامة ، مما يعني أن هناك H (x) = P (x) / F (x) ، وبالتالي فإن كثير الحدود الذي نريد التحقق منه يتحول أخيرًا إلى:
A (x) \ * B (x) - C (x): يحتوي على معاملات كثير الحدود ، المعروفة فقط للمثقف ، أي المدخلات السرية.
F (x): كثير حدود عام معروف لكل من المدقق والمثقف ، أي المدخلات العامة.
ح (خ): المُثبِت يعرفها من خلال الحساب ، لكن المدقق غير معروف.
** المشكلة الأخيرة التي يجب إثباتها هي: المعادلة متعددة الحدود A (x) \ * B (x) - C (x) = F (x) \ * H (x) ، صحيحة على كل x. **
الآن من الضروري فقط التحقق من كثير الحدود مرة واحدة للتحقق من أن جميع القيود تفي بعلاقات المصفوفة.
** لقد أكملنا هنا تحويل المشكلة ليتم إثباتها إلى كثير حدود لا تحتاج إلا إلى التحقق منها مرة واحدة ، مع إدراك بساطة النظام. **
لكن بساطة هذا التطبيق هو تقصير وقت التحقق من المدقق ، فماذا عن حجم الإثبات؟
** بكل بساطة ، في بروتوكول الإثبات ، يتم استخدام هيكل شجرة Merkle ، مما يقلل بشكل فعال من حجم الإثبات. **
بعد اكتمال عملية التحويل بأكملها ، ستظهر مشكلتان بشكل طبيعي:
- لماذا التحويل إلى كثير الحدود؟
لأن كثيرات الحدود تتيح بساطة الإثبات. تكمن مشكلة برهان المعرفة الصفرية في التحقق من أن الحسابات تلبي قيودًا متعددة ، ويمكن للعديد من الحدود التحقق من قيود متعددة عند نقطة واحدة. بمعنى آخر ، يجب على المدقق التحقق من n مرة لتأكيد المشكلة ، ولكنه يحتاج الآن فقط إلى التحقق مرة واحدة لتأكيد صحة الدليل باحتمالية عالية.
- لماذا يمكن إنشاء اثنين من كثيرات الحدود A (x) \ * B (x) - C (x) = F (x) \ * H (x) بالتحقق من نقطة على كثير الحدود؟
يتم تحديد ذلك من خلال خصائص كثيرات الحدود ، أي أن نتيجة حساب كثير الحدود في أي نقطة يمكن اعتبارها تمثيلاً لهويتها الفريدة. بالنسبة لاثنين من كثيرات الحدود ، سوف يتقاطعان فقط عند عدد محدود من النقاط.
بالنسبة إلى كثيرات الحدود أعلاه من الدرجة d: A (x) \ * B (x) - C (x) و F (x) \ * H (x) ، إذا لم تكن متساوية ، فستكون فقط نقطة d على الأكثر تقاطع ، أي أن الحلول عند نقاط d هي نفسها.
بعد إتمام التحويل متعدد الحدود ، سندخل مرحلة إثبات كثير الحدود.
** برهن على أن كثير الحدود يحمل **
من أجل التوضيح ، نستخدم كثير الحدود P (x) = F (x) \ * H (x).
الآن ، المشكلة التي يريد المُثقف إثباتها هي: على كل x ، P (x) = F (x) \ * H (x).
تكون عملية التحقق من كثير الحدود أعلاه بواسطة المُثبِّت والمدقق كما يلي:
- يختار المدقق نقطة تحدي عشوائية x ، بافتراض x = s ؛
- بعد أن يتلقى المُثبُت s ، احسب P (s) و H (s) ، وأعط هاتين القيمتين للمدقق ؛
- يقوم المدقق أولاً بحساب F (s) ، ثم يحسب F (s) \ * H (s) ، ويحكم ما إذا كان F (s) \ * H (s) = P (s) صحيحًا ، وإذا كان صحيحًا ، تم تمرير التحقق.
لكن إذا فكرنا جيدًا ، سنجد أن هناك بعض المشكلات في العملية المذكورة أعلاه:
- يمكن للمثل معرفة معلومات المعادلة بأكملها. إذا تلقى نقطة عشوائية s ، فيمكنه حساب F (s) ، ثم إنشاء زوج مزيف P (x) و H (x) ، بحيث يكون P (s) ) = F (s) \ * H (s) لخداع المدقق.
- لا يستخدم المُثبِّت القيم التي قدمها المدقق لحساب F (s) و H (s) ، ولكنه يحسب مع القيم الأخرى لخداع المدقق.
- يتم احتساب القيمة التي يتلقاها المدقق من خلال المدخلات العامة والمدخلات الخاصة للمثقف.إذا كان المدقق لديه قوة حوسبة كبيرة ، فيمكنه كسر المدخلات الخاصة للمثقف.
لحل المشكلات المذكورة أعلاه ، نقوم بإجراء التحسينات التالية:
- بعد أن يحدد المدقق نقطة عشوائية ، فإنه ينفذ تشفيرًا متماثل الشكل على s. يعني التشفير المتجانس ** الحل المحسوب بعد التشفير = الحل المشفر بعد الحساب ** ؛ في نموذج التشفير هذا ، يمكن للمثقف حساب الحل ، ولكن لا يمكنه إنشاء خطأ P (x) و H (x).
- عندما يختار المدقق نقاط التحدي ، يتم تحديد معلمة عشوائية أخرى لتوليد علاقة خطية إضافية بين s و. يرسل المدقق كلاً من s و بعد التشفير متماثل الشكل إلى المُثبِّت. يرسل المُثبَّت الإثبات مرة أخرى ، ويحتاج المدقق إلى التحقق من العلاقة بين المعلمة العشوائية λ و s بالإضافة إلى التحقق مما إذا كان الدليل صحيحًا.
- ** بهدف حل مشكلة قدرة المدقق على كسر الإدخال السري ، يمكننا تقديم ZK. ** بالنظر إلى الدليل بأكمله ، يمكننا أن نجد أنه أثناء عملية التحقق ، يرسل المُثبِت فقط قيمة متعددة الحدود المحسوبة إلى المدقق ، ويمكن للمدقق استنتاج معامل كثير الحدود من خلال القيمة ، وهي الإدخال السري لـ مَثَل. من أجل منع المدقق من التراجع ، يمكننا تحديد رقمين عشوائيين آخرين وإضافة مجموعة من القيم عند اشتقاق كثيرات الحدود A و B و C من R1CS ، بحيث يكون كثير الحدود المستعاد أمرًا واحدًا أكثر من كثير الحدود الأصلي ، بحيث لا يمكن للقارئ الحصول على معلومات كثير الحدود الأصلي من كثير الحدود المشفر لتحقيق ZK.
بعد التحسين وجدنا أن نظام الإثبات لا يزال يتطلب التفاعل بين المدقق والمثب كيف يمكننا تحقيق عدم التفاعل؟
** تنفيذ غير تفاعلي **
** لتحقيق عدم التفاعل ، تقدم SNARK إعدادات موثوقة (إعداد). **
بعبارة أخرى ، قبل بدء الإثبات ، يتم تسليم حق المدقق في اختيار نقاط التحدي العشوائية إلى طرف ثالث موثوق به. بعد أن يختار الطرف الثالث المعلمة العشوائية λ ، فإنه يضع λ المشفر في دائرة R1CS. في هذا الطريقة ، يتم إنشاء CRS (سلسلة مرجعية عامة ، سلسلة مرجعية عامة). يمكن للمدقق الحصول على Sv الخاص به من CRS ، ويمكن للمثقف الحصول على Sp الخاص به من CRS.
وتجدر الإشارة إلى أن يجب تدميره بعد إنشاء Sv و Sp. إذا تم تسريب λ ، فيمكن استخدامه لتزوير المعاملات من خلال التحقق الخاطئ.
** سير عمل zk-SNARK **
بعد فهم عملية بناء SNARK ، استنادًا إلى الدائرة الحسابية التي أنشأناها والتي يمكن أن تولد البراهين ، فإن عملية إثبات zk-SNARK هي كما يلي:
- الإعداد: (دائرة C ، λ) = (Sv ، Sp)
من خلال الدائرة C والمعلمة العشوائية λ ، يتم إنشاء المعلمات العشوائية Sv و Sp المستخدمة بواسطة المُثبِت والمدقق اللاحقين.
يحسب المُثبُت الإثبات Π من خلال المعلمة العشوائية Sp والمدخلات العامة x والمدخلات السرية w.
- تحقق من (Sv، x، Π) == (∃ w st C (x، w))
يتحقق المدقق مما إذا كانت C (x، w) = 0 موجودة من خلال المعلمة العشوائية Sv والمدخلات العامة x والإثبات Π. في نفس الوقت ، تحقق مما إذا كان الدليل محسوبًا بالدائرة C أم لا.
في هذه المرحلة ، أكملنا شرح zk-SNARK بالكامل. دعنا نلقي نظرة على حالة التطبيق الفعلية.
** الحالة: خذ zk Rollup في Scroll كمثال **
دور نظام الإثبات هو السماح للمُثبِّت بإقناع المحقق بأن يؤمن بشيء واحد ؛
بالنسبة لنظام إثبات ZK ، من الضروري أن يعتقد المدقق أن إثبات المعرفة الصفرية (إثبات المعرفة الصفرية) المحسوب بواسطة خوارزمية zk صحيح.
نحن نأخذ Scroll’s zk Rollup كمثال لتوضيح تشغيل نظام zk proof.
يشير التراكمي إلى الحساب خارج السلسلة والتحقق على السلسلة. بالنسبة إلى zk Rollup ، بعد تنفيذ المعاملة خارج السلسلة ، يحتاج المُثبِت إلى إنشاء شهادة zk لجذر الحالة الجديد الذي تم إنشاؤه بعد تنفيذ المعاملة ، ثم تمرير الشهادة إلى عقد L1 Rollup للتحقق على السلسلة.
وتجدر الإشارة إلى أن هناك نوعين من الكتل في zk Rollup:
- كتلة L1 Rollup: الكتلة المقدمة إلى Ethereum
- كتلة L2: كتلة تتكون من المعاملات التي يرسلها المستخدمون على L2
فيما يلي سير عمل Scroll’s zk Rollup:
- يبدأ المستخدم معاملة في L2 ، ويسترد Sequencer المعاملة ، وينفذ المعاملة خارج السلسلة وينشئ كتلة L2 وجذر حالة جديد ؛ وفي الوقت نفسه ، يرسل بيانات المعاملة وجذر الحالة الجديد إلى عقد التجميع على Ethereum (إرسال بيانات المعاملة لتوفر البيانات) ؛
- عندما يتم إنشاء كتلة L2 ، سيتلقى المنسق مسار تنفيذ الكتلة من جهاز التسلسل ، ثم يقوم بتعيين المسار عشوائيًا لأي أسطوانة ؛
- يقوم Roller بتحويل مسار التنفيذ المستلم إلى دوائر ، ويقوم بإنشاء شهادة صلاحية لكل دائرة ، ثم يرسل الشهادة مرة أخرى إلى المنسق ؛
- في كل مرة يتم فيها إنشاء كتل k L2 ، سيرسل المنسق مهمة تجميع إلى بكرة أخرى لتجميع أدلة k في برهان مجمع واحد ؛
- يقدم المنسق دليلًا واحدًا للتجميع إلى عقد التجميع ، ويتحقق عقد التجميع من إثبات التجميع جنبًا إلى جنب مع جذر الحالة التي تم إرسالها مسبقًا وبيانات المعاملة. إذا نجح التحقق ، فسيتم اعتبار الكتلة المقابلة قد اكتملت في التمرير.
كما يتضح من العملية المذكورة أعلاه ، فإن Roller هو المُثبِّت في النظام ، وعقد التجميع هو المُحقِّق. تقوم Roller بإنشاء دليل zk للمعاملات المنفذة خارج السلسلة ؛ يتحقق عقد التجميع من الإثبات ، وإذا نجح التحقق ، سيعتمد عقد التجميع مباشرة جذر الحالة المقدم باعتباره جذر الحالة الجديد.
