فيتاليك بوتيرين عبر مدونة فيتاليك بوتيرين
هذه مرآة لهذا المنصب في https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
هذا هو الجزء الثالث من سلسلة مقالات تشرح كيفية عمل التكنولوجيا التي تكمن وراء zk-SNARKs؛ المقالات السابقة عن برامج حسابية من الدرجة الثانية و أزواج منحنى بيضاوي مطلوبة القراءة، وهذه المادة سوف تفترض معرفة كلا المفهومين. يُفترض أيضًا أن تكون هناك معرفة أساسية بماهية zk-SNARKs وما تفعله. أنظر أيضا مقالة كريستيان رييتويسنر هنا لمقدمة فنية أخرى.
في المقالات السابقة، قدمنا برنامج الحساب التربيعي، وهو طريقة لتمثيل أي مشكلة حسابية بمعادلة متعددة الحدود أكثر قابلية لأشكال مختلفة من الخداع الرياضي. لقد قدمنا أيضًا أزواج المنحنيات الإهليلجية، والتي تسمح بنموذج محدود جدًا من التشفير المتماثل أحادي الاتجاه الذي يتيح لك التحقق من المساواة. الآن، سنبدأ من حيث توقفنا، ونستخدم أزواج المنحنيات الناقصية، جنبًا إلى جنب مع بعض الحيل الرياضية الأخرى، من أجل السماح للمبرهن بإثبات أنه يعرف حلًا لـ QAP معين دون الكشف عن أي شيء آخر حول الحل الفعلي.
هذه المقالة سوف تركز على بروتوكول بينوكيو بواسطة Parno وGentry وHowell وRaykova من عام 2013 (يُطلق عليها غالبًا PGHR13)؛ هناك بعض الاختلافات في الآلية الأساسية، لذا فإن مخطط zk-SNARK المطبق عمليًا قد يعمل بشكل مختلف قليلاً، لكن المبادئ الأساسية بشكل عام ستظل كما هي.
للبدء، دعونا ننتقل إلى افتراض التشفير الرئيسي الكامن وراء أمان الآلية التي سنستخدمها: * معرفة الأس* افتراض.
في الأساس، إذا حصلت على زوج من النقاط � و �، حيث � ⋅ �= �، وحصلت على نقطة �، فمن غير الممكن التوصل إلى � ⋅ � إلا إذا كانت � «مشتقة» من � بطريقة ما الذي تعرفه. قد يبدو هذا بديهيًا، ولكن هذا الافتراض لا يمكن استخلاصه في الواقع من أي افتراض آخر (على سبيل المثال، صلابة السجل المنفصلة) التي نستخدمها عادةً عند إثبات أمان البروتوكولات القائمة على المنحنى الإهليلجي، وبالتالي فإن zk-SNARKs تعتمد في الواقع على نوع ما أساس أكثر اهتزازًا من التشفير ذي المنحنى الإهليلجي بشكل عام - على الرغم من أنه لا يزال قويًا بدرجة كافية بحيث يقبله معظم مصممي التشفير.
الآن، دعونا نذهب إلى كيف يمكن استخدام هذا. لنفترض أن زوجًا من النقاط (�،�) يسقط من السماء، حيث ��، لكن لا أحد يعرف قيمة �. الآن، لنفترض أنني توصلت إلى زوج من النقاط (�،�) حيث ⋅�= �. بعد ذلك، يشير افتراض KoE إلى أن الطريقة الوحيدة التي أمكنني بها الحصول على هذا الزوج من النقاط كانت عن طريق أخذ - و - وضرب كليهما في عامل ما r الذي أعرفه شخصيا. لاحظ أيضًا أنه بفضل سحر أزواج المنحنى الإهليلجي، تم التحقق من ذلك لا يتطلب في الواقع المعرفة � - بدلاً من ذلك، يمكنك ببساطة التحقق مما إذا كان �( �، �) = � (�، �) أم لا.
دعونا نفعل شيئا أكثر إثارة للاهتمام. لنفترض أن لدينا عشرة أزواج من النقاط تسقط من السماء: ( �١، �١)، ( �٢، �٢) … ( �١٠، �١٠). وفي جميع الأحوال ��. لنفترض أنني قمت بعد ذلك بتزويدك بزوج من النقاط ( � ، � ) حيث � � � = �. ماذا تعرف الآن؟ أنت تعلم أن � عبارة عن تركيبة خطية �1⋅ �1+ �2⋅ �2+…+ �10⋅ �10، حيث أعرف المعاملات �1، �2… �10. وهذا يعني أن الطريقة الوحيدة للوصول إلى مثل هذا الزوج من النقاط (�،�) هي أخذ بعض مضاعفات ��1، 2… 10 وجمعها معًا، وإجراء نفس العملية الحسابية باستخدام �� 1، 2… 10.
لاحظ أنه، في ضوء أي مجموعة محددة من 1... 10 نقاط قد ترغب في التحقق من التركيبات الخطية لها، لا يمكنك فعليًا إنشاء نقاط 1... 10 المصاحبة دون معرفة ما هي، وإذا كنت تعرف ما هي � بعد ذلك يمكنك إنشاء زوج ( �، �) حيث � � � = � لأي شيء تريده، دون الحاجة إلى إنشاء مجموعة خطية. ومن ثم، لكي ينجح هذا، فمن الضروري تمامًا أن يكون من أنشأ تلك النقاط جديرًا بالثقة ويقوم بالفعل بحذفها - بمجرد إنشاء النقاط العشر. ومن هنا يأتي مفهوم "الإعداد الموثوق به"..
تذكر أن حل QAP هو مجموعة من متعددات الحدود (�,�,�) مثل �(�)⋅�( �)− �( �)= �(�)⋅ �( �) ،حيث:
- � هو مزيج خطي من مجموعة كثيرات الحدود { �1… ��}
- � هي المجموعة الخطية من { �1… ��} بنفس المعاملات
- � عبارة عن مزيج خطي من { �1… ��} بنفس المعاملات
المجموعات {�1…��}،{�1…��} و{�1…��} ومتعددة الحدود � هي جزء من بيان المشكلة.
ومع ذلك، في معظم حالات العالم الحقيقي، تكون "" و"" كبيرة للغاية؛ بالنسبة لشيء يحتوي على عدة آلاف من بوابات الدائرة مثل دالة التجزئة، فإن كثيرات الحدود (وعوامل المجموعات الخطية) قد تحتوي على عدة آلاف من المصطلحات. وبالتالي، بدلًا من جعل المُثبِّت يقدم المجموعات الخطية مباشرةً، سنستخدم الحيلة التي قدمناها أعلاه لجعل المُثبِّت يُثبت أنه يقدم شيئًا ما عبارة عن مجموعة خطية، ولكن دون الكشف عن أي شيء آخر.
ربما لاحظت أن الخدعة أعلاه تعمل على نقاط المنحنى الإهليلجي، وليس على متعددات الحدود. وبالتالي، ما يحدث فعليًا هو أننا نضيف القيم التالية إلى الإعداد الموثوق:
- �⋅�1(�)، �⋅ �1(�)⋅��
- �⋅�2(�)، �⋅ �2(�)⋅��
- ...
- �⋅�1(�)، �⋅ �1(�)⋅��
- �⋅�2(�)، �⋅ �2(�)⋅��
- ...
- �⋅�1(�)، �⋅ �1(�)⋅��
- �⋅�2(�)، �⋅ �2(�)⋅��
- ...
يمكنك التفكير في t باعتبارها "نقطة سرية" يتم عندها تقييم كثير الحدود. � هي "مولد" (نقطة منحنى إهليلجية عشوائية تم تحديدها كجزء من البروتوكول) و،،،، و، هي "نفايات سامة"، وهي أرقام يجب حذفها مطلقًا بأي ثمن، وإلا من يمتلكها سيكون قادرًا على تقديم أدلة مزيفة. الآن، إذا أعطاك شخص ما زوجًا من النقاط ��، � بحيث �� ��= � (تذكير: لسنا بحاجة �� للتحقق من ذلك، حيث يمكننا إجراء فحص الاقتران)، فأنت تعلم أن ما ما نقدمه لك عبارة عن مجموعة خطية من �� كثيرات الحدود التي تم تقييمها بـ .
وبالتالي، حتى الآن يجب على المثل أن يعطي:
- ���������������
- ���������������
- ���������������
لاحظ أن المُثبِّت لا يحتاج في الواقع إلى معرفة (ولا ينبغي له أن يعرف!) �� أو �� أو �� لحساب هذه القيم؛ بدلاً من ذلك، يجب أن يكون المُثبِّت قادرًا على حساب هذه القيم فقط من النقاط التي نضيفها إلى الإعداد الموثوق.
والخطوة التالية هي التأكد من أن المجموعات الخطية الثلاثة لها نفس المعاملات. يمكننا القيام بذلك عن طريق إضافة مجموعة أخرى من القيم إلى الإعداد الموثوق به: �⋅(��( �)+��(�)+��( �))⋅ �، حيث � هو رقم آخر يجب اعتباره «سامًا» النفايات" ويتم التخلص منها بمجرد اكتمال الإعداد الموثوق به. يمكننا بعد ذلك أن نطلب من المُثبِّت إنشاء مجموعة خطية من هذه القيم بنفس المعاملات، واستخدام نفس خدعة الاقتران المذكورة أعلاه للتحقق من تطابق هذه القيمة مع "+" + المقدمة.
وأخيرًا، علينا أن نثبت أن ⋅−⋅⋅. نقوم بذلك مرة أخرى من خلال فحص الاقتران:
��(��,��)/��(��,�)?=�( �ℎ, �⋅�( �))
حيث �ℎ=�⋅�(�). إذا كان الارتباط بين هذه المعادلة و ⋅�−�=�⋅� غير منطقي بالنسبة لك، فارجع واقرأ مقال عن الاقتران.
لقد رأينا أعلاه كيفية تحويل "" و"" و"" إلى نقاط منحنى إهليلجي؛ � هو مجرد المولد (أي نقطة المنحنى الإهليلجي المكافئة للرقم واحد). يمكننا إضافة ⋅�( �) إلى الإعداد الموثوق به. � أصعب؛ � هي مجرد كثيرة الحدود، ولا نتوقع سوى القليل جدًا مسبقًا حول معاملاتها لكل حل QAP فردي. وبالتالي، نحن بحاجة إلى إضافة المزيد من البيانات إلى الإعداد الموثوق به؛ على وجه التحديد التسلسل:
, ⋅ , ⋅ 2, ⋅ 3, ⋅ 4….
في إعداد Zcash الموثوق، يصل التسلسل هنا إلى حوالي 2 مليون؛ هذا هو عدد صلاحيات - التي تحتاجها للتأكد من أنك ستتمكن دائمًا من حساب -( �)، على الأقل بالنسبة لمثيل QAP المحدد الذي يهتمون به. وبهذا، يمكن للمثبت توفير جميع المعلومات للمدقق لإجراء الفحص النهائي.
هناك تفصيل آخر نحتاج إلى مناقشته. في أغلب الأحيان، لا نريد فقط أن نثبت نظريًا وجود حل ما لمشكلة معينة؛ بل نريد أن نثبت إما صحة بعض الحلول المحددة (على سبيل المثال إثبات أنه إذا أخذت كلمة "بقرة" وقمت بتجزئة SHA3 مليون مرة، فإن النتيجة النهائية تبدأ بـ 0x73064fe5)، أو أن الحل موجود إذا قمت بتقييد بعض المعلمات. على سبيل المثال، في إنشاء مثيل للعملة المشفرة حيث يتم تشفير مبالغ المعاملات وأرصدة الحسابات، فأنت تريد إثبات أنك تعرف بعض مفاتيح فك التشفير k بحيث:
decrypt(old_balance, k) >= decrypt(tx_value, k)
decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)
المشفرة old_balance
, tx_value
و new_balance
يجب تحديدها علنًا، لأن هذه هي القيم المحددة التي نتطلع إلى التحقق منها في ذلك الوقت المحدد؛ يجب إخفاء مفتاح فك التشفير فقط. هناك حاجة إلى بعض التعديلات الطفيفة على البروتوكول لإنشاء "مفتاح تحقق مخصص" يتوافق مع بعض القيود المحددة على المدخلات.
الآن، دعونا نتراجع قليلا. أولاً، إليك خوارزمية التحقق بأكملها، مقدمة من ben ساسون وترومر وفيرزا وكييزا:
السطر الأول يتناول البارامترات؛ بشكل أساسي، يمكنك التفكير في وظيفتها على أنها إنشاء "مفتاح تحقق مخصص" للمثيل المحدد للمشكلة حيث يتم تحديد بعض الحجج. السطر الثاني هو التحقق من التركيبة الخطية لـ , , و ; السطر الثالث هو التحقق من أن المجموعات الخطية لها نفس المعاملات، والسطر الرابع هو التحقق من المنتج ⋅ �− �= �⋅ �.
إجمالاً، تتكون عملية التحقق من عدد قليل من مضاعفات المنحنى الإهليلجي (واحدة لكل متغير إدخال "عام")، وخمس عمليات تحقق من الاقتران، تتضمن إحداها مضاعفة اقتران إضافية. يحتوي الدليل على ثماني نقاط منحنى إهليلجي: زوج من النقاط لكل من �(�) و�(�) و �(�)، ونقطة �� لـ �⋅(�( �)+ �( �)+ �( �) )))، ونقطة ℎ لـ ��( �). سبع من هذه النقاط موجودة على المنحنى �� (32 بايت لكل منها، حيث يمكنك ضغط الإحداثي �� إلى بت واحد)، وفي تطبيق Zcash توجد نقطة واحدة (��) على المنحنى الملتوي في ��2 (64 بايت)، وبالتالي فإن الحجم الإجمالي للدليل هو ~ 288 بايت.
الجزءان الأصعب حسابيًا في إنشاء الدليل هما:
- قسمة (⋅��−��)/ � للحصول على (الخوارزميات المستندة إلى تحويل فورييه السريع يمكن القيام بذلك في زمن شبه تربيعي، لكنه لا يزال يتطلب الكثير من العمليات الحسابية)
- إجراء الضرب والجمع على المنحنى الإهليلجي لتكوين قيم �( �) و � (�) و � (�) و �(�) وأزواجها المقابلة
السبب الأساسي وراء صعوبة إنشاء الدليل هو حقيقة أن ما كان عبارة عن بوابة منطقية ثنائية واحدة في الحساب الأصلي يتحول إلى عملية يجب معالجتها تشفيريًا من خلال عمليات المنحنى الإهليلجي إذا كنا نصنع منها دليلًا للمعرفة الصفرية . هذه الحقيقة، جنبًا إلى جنب مع الخطية الفائقة لتحويلات فورييه السريعة، تعني أن إنشاء الإثبات يستغرق ما يقرب من 20 إلى 40 ثانية لمعاملة Zcash.
سؤال آخر مهم جدًا هو: هل يمكننا أن نحاول جعل الإعداد الموثوق به قليلًا... أقل تطلبًا للثقة؟ ولسوء الحظ، لا يمكننا أن نجعل الأمر غير جدير بالثقة تمامًا؛ إن افتراض KoE نفسه يمنع إنشاء أزواج مستقلة (������) دون معرفة ما هو. ومع ذلك، يمكننا زيادة الأمان بشكل كبير عن طريق استخدام حساب متعدد الأطراف - أي إنشاء الإعداد الموثوق به بين - الأطراف بطريقة بحيث طالما قام أحد المشاركين على الأقل بحذف نفاياته السامة، فأنت بخير .
للحصول على فكرة بسيطة عن كيفية القيام بذلك، إليك خوارزمية بسيطة لأخذ مجموعة موجودة ( �، ⋅ �، ⋅ � 2، � ⋅ � 3 …)، و “إضافة” سرك الخاص بحيث تحتاج إلى كل من سرك والسر السابق (أو مجموعة الأسرار السابقة) للغش.
مجموعة الإخراج هي ببساطة:
� ،(⋅ �)⋅ � ،(⋅ �2)⋅ �2 ،( �⋅ �3)⋅ �3…
لاحظ أنه يمكنك إنتاج هذه المجموعة بمعرفة المجموعة الأصلية فقط، وتعمل المجموعة الجديدة بنفس طريقة المجموعة القديمة، باستثناء استخدام ⋅" باعتبارها "النفايات السامة" بدلاً من . طالما أنك والشخص (أو الأشخاص) الذين أنشأوا المجموعة السابقة لم يفشلوا في حذف نفاياتك السامة ثم تواطأوا لاحقًا، فإن المجموعة "آمنة".
يعد القيام بذلك للإعداد الموثوق الكامل أصعب بعض الشيء، نظرًا لوجود العديد من القيم المعنية، ويجب تنفيذ الخوارزمية بين الأطراف في عدة جولات. إنه مجال بحث نشط لمعرفة ما إذا كان من الممكن تبسيط خوارزمية الحساب متعدد الأطراف بشكل أكبر وجعلها تتطلب جولات أقل أو جعلها أكثر قابلية للتوازي، حيث أنه كلما تمكنت من القيام بذلك، أصبح من الممكن تضمين المزيد من الأطراف في إجراء الإعداد الموثوق به . من المعقول أن نرى لماذا قد يجعل الإعداد الموثوق به بين ستة مشاركين يعرفون جميعًا ويعملون مع بعضهم بعضًا بعض الأشخاص غير مرتاحين، لكن الإعداد الموثوق به مع آلاف المشاركين لا يمكن تمييزه تقريبًا عن انعدام الثقة على الإطلاق - وإذا كنت مصابًا بجنون العظمة حقًا ، يمكنك الدخول والمشاركة في إجراء الإعداد بنفسك، والتأكد من أنك قمت بحذف القيمة الخاصة بك شخصيًا.
هناك مجال آخر للبحث النشط وهو استخدام الأساليب الأخرى التي لا تستخدم عمليات الاقتران ونفس نموذج الإعداد الموثوق به لتحقيق نفس الهدف؛ يرى العرض الأخير لإيلي بن ساسون لبديل واحد (على الرغم من تحذيرك، فهو على الأقل معقد رياضيًا مثل SNARKs!)
شكر خاص لأرييل غابيزون وكريستيان رييتويسنر للمراجعة.
- محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
- PlatoData.Network Vertical Generative Ai. تمكين نفسك. الوصول هنا.
- أفلاطونايستريم. ذكاء Web3. تضخيم المعرفة. الوصول هنا.
- أفلاطون كربون، كلينتك ، الطاقة، بيئة، شمسي، إدارة المخلفات. الوصول هنا.
- أفلاطون هيلث. التكنولوجيا الحيوية وذكاء التجارب السريرية. الوصول هنا.
- BlockOffsets. تحديث ملكية الأوفست البيئية. الوصول هنا.
- المصدر ذكاء بيانات أفلاطون.