المؤلف: 0xAlpha المؤسس المشارك @DeriProtocol ؛ مترجم: دودو للأبحاث
مقدمة
zk-SNARKs ، أو “حجج المعرفة الموجزة غير التفاعلية للمعرفة” ، تمكن المدقق من تأكيد أن البروفير لديه معرفة محددة معينة ، تعرف باسم الشهود ، والتي تلبي علاقات محددة دون الكشف عن أي شيء عن الشاهد نفسه.
يتكون إنشاء zk-SNARKs لمشكلة معينة من المراحل الأربع التالية:
- تحويل مشكلة (أو وظيفة) إلى دائرة بوابة حسابية.
- ثم تترجم هذه الدائرة إلى صيغة مصفوفة.
- يتم تحويل صيغة المصفوفة هذه إلى كثير حدود ، والتي يجب أن تكون قابلة للقسمة على حد أدنى محدد لكثير الحدود.
- أخيرا ، يتم تمثيل قابلية القسمة هذه في نقاط منحنى إهليلجي في الحقول المحدودة ، حيث يحدث الإثبات.
الخطوات الثلاث الأولى ببساطة تحويل تمثيل البيان الأصلي. تستخدم الخطوة الأخيرة التشفير المتجانس لعرض بيان الخطوة 3 في مساحة التشفير ، مما يمكن البروفير من التحقق من عبارة المرآة فيه. بالنظر إلى أن هذا الإسقاط يستخدم التشفير غير المتماثل ، فمن غير الممكن تتبع البيان الأصلي من الخطوة الثالثة ، مما يضمن التعرض للمعرفة الصفرية.
خلفية الرياضيات المطلوبة لقراءة هذه المقالة تعادل مستوى الجبر الجديد لتخصصات العلوم والتكنولوجيا والهندسة والرياضيات. ربما يكون المفهوم الوحيد الذي يمكن أن يكون صعبا هو تشفير المنحنى الإهليلجي. بالنسبة لأولئك الذين ليسوا على دراية بهذا ، يمكن اعتباره دالة أسية ذات كاردينالية خاصة ، مع الأخذ في الاعتبار أن عكسها لا يزال دون حل.
ستتبع هذه المقالة قواعد التدوين التالية:
- المصفوفة: أحرف كبيرة غامقة ، على سبيل المثال A ؛ الكتابة بشكل صريح في النموذج
- المتجه: أحرف صغيرة مع الأسهم ، مكتوبة في شكل صريح [ ] ؛ بشكل افتراضي ، تكون جميع المتجهات متجهات عمودية
- عددي: تمثيل الحروف العادية
دعنا نستخدم هذا السؤال كمثال:
f(x)=x^3+x^2+5 (1)
لنفترض أن أليس تريد أن تثبت أنها تعرف واحدة. سنتعرف على الإجراء بأكمله الذي تحتاج أليس إلى اتخاذه لإنشاء zk-SNARKs لبراهينها.
قد يبدو هذا السؤال بسيطا للغاية لأنه لا يتضمن تدفق التحكم (على سبيل المثال ، if-then-else). ومع ذلك ، ليس من الصعب تحويل دالة ذات تدفق تحكم إلى تعبير حسابي. على سبيل المثال ، دعنا نفكر في السؤال التالي (أو “الوظيفة” في لغة برمجة):
F (X، Z):
إذا(z==1):
إرجاع x*x*x+x*x+5
اخر:
إرجاع x*x+5
من السهل إعادة كتابة هذه المشكلة في التعبير الحسابي التالي (بافتراض أن z ينتمي إلى (0,1)) ، وهو ليس أكثر تعقيدا من المعادلة (1).
F(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)
في هذه المقالة ، سنستمر في استخدام المعادلة (1) كأساس للمناقشة.
الخطوة 1: دائرة البوابة الحسابية
يمكن تقسيم المعادلة (1) إلى العمليات الحسابية الأساسية التالية:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-122a4a0e88-dd1a6f-cd5cc0.webp)
هذا يتوافق مع دائرة البوابة الحسابية التالية:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-9001e3d244-dd1a6f-cd5cc0.webp)
نشير أيضا إلى المعادلة (2) على أنها مجموعة من 4 “قيود من الدرجة الأولى” ، يصف كل منها علاقة بوابة حسابية في الدائرة. بشكل عام ، يمكن تعميم مجموعة من قيود n من الدرجة الأولى كإجراء حسابي تربيعي (QAP) ، والذي سيتم شرحه بعد ذلك.
الخطوة 2: ماتريكس
أولا ، دعنا نعرف متجه “الشاهد” على النحو التالي:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-1157f4c74a-dd1a6f-cd5cc0.webp)
حيث y ، s1 ، s2 ، s3 هي نفسها كما هو محدد في المعادلة (2).
بشكل عام ، بالنسبة لمشكلة في مدخلات m والبوابات الحسابية n (أي الخطوات الوسيطة n-1 والإخراج النهائي) ، سيكون هذا المتجه الشاهد (m + n + 1) بعدا. في مسألة عملية ، يمكن أن يكون الرقم n كبيرا جدا. على سبيل المثال ، بالنسبة لدالة التجزئة ، عادة ما تكون n بضعة آلاف.
بعد ذلك ، دعونا نبني ثلاث مصفوفات n \ * (m + n + \ * 1) A و B و C حتى نتمكن من إعادة كتابة المعادلة (2) على النحو التالي:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a9e2164b2f-dd1a6f-cd5cc0.webp)
المعادلة (3) هي مجرد تمثيل آخر للمعادلة (2): كل مجموعة (ai ، bi ، ci) تتوافق مع بوابة في الدائرة. نحتاج فقط إلى توسيع صيغة المصفوفة بشكل لا لبس فيه لرؤية هذا:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-630e507588-dd1a6f-cd5cc0.webp)
لذا فإن LHS = RHS هي بالضبط نفس المعادلة (2) ، وكل صف من معادلة المصفوفة يتوافق مع قيد من الدرجة الأولى (أي بوابة حسابية في الدائرة).
لقد تخطينا خطوات البناء (A ، B ، C) ، والتي تكون واضحة نسبيا. نحتاج فقط إلى تحويلها إلى شكل مصفوفة وفقا لقيود المستوى الأول المقابلة ، وذلك لتحديد محتوى كل صف من (A ، B ، C) ، أي (الذكاء الاصطناعي ، BI ، CI). خذ السطر الأول كمثال: من السهل أن نرى أنه لكي يتم ضرب قيد الرتبة الأولى x في x يساوي s1 للاحتفاظ به ، نحتاج إلى ضرب [0،1،0،0،0،0،0] و [0،1،0،0،0،0] و [0،0،0،1،0،0] مع المتجه s.
وهكذا نجحنا في تحويل دائرة البوابة الحسابية إلى صيغة مصفوفة ، أي المعادلة (3). في الوقت نفسه ، قمنا أيضا بتغيير الكائن الذي يجب إثبات إتقانه من إلى متجه شاهد.
الخطوة 3: كثيرات الحدود
الآن ، دعنا نبني مصفوفة n \ * (\ * n + m + \ * 1) PA التي تحدد مجموعة من كثيرات الحدود حول z:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-94169f2b1d-dd1a6f-cd5cc0.webp)
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-2c37ea96a6-dd1a6f-cd5cc0.webp)
هذه أربع مجموعات من المعادلات الخطية لستة متغيرات يمكن حلها بالطرق التقليدية. ومع ذلك ، فإن الطريقة الأكثر فعالية لحل PA في هذه الحالة هي استيفاء Lagrangian ، والذي يستفيد من خصوصية المشكلة. هنا نتخطى عملية الحل للسلطة الفلسطينية ، وهي مملة بعض الشيء ولكنها مباشرة.
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-fcac15b335-dd1a6f-cd5cc0.webp)
وفيها:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a7d3309d02-dd1a6f-cd5cc0.webp)
الخطوة 4: نقاط منحنى القطع الناقص
أعد كتابة المعادلة (4) إلى:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-f974fc7c93-dd1a6f-cd5cc0.webp)
حيث i (z) = 1 هو مجرد كثير حدود صفري تافه ل z ، والذي يستخدم لتوحيد المعادلة - جميع المصطلحات تربيعية. وسرعان ما ستتضح الحاجة إلى القيام بذلك. لاحظ أن هذه المعادلة تحتوي فقط على جمع وضرب كثير حدود z.
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-8fdea08104-dd1a6f-cd5cc0.webp)
بعد ذلك ، سنشرح الخطوات الفعلية بمزيد من التفصيل.
تشفير المنحنى الإهليلجي
النظرية العامة للمنحنيات الإهليلجية تتجاوز نطاق هذه المقالة. لأغراض هذا البحث ، يتم تعريف المنحنيات الإهليلجية على أنها تعيين من المجال الأولي Fp إلى الدالة E ، حيث تتضمن E نقاطا تحقق y ^ 2 = x ^ 3 + ax + b (تسمى نقاط المنحنى الإهليلجي ، أو ECPs للاختصار).
لاحظ أنه بينما كنا نتحدث عن العمليات الحسابية العادية حتى الآن ، الآن عندما نحول إلى حقول أولية ، تتم العمليات الحسابية على الأرقام بطريقة معيارية. على سبيل المثال ، a + b = a + b (mod p) ، حيث p هو ترتيب Fp.
من ناحية أخرى ، يظهر تعريف الجمع لنقطتي منحنى إهليلجي في الشكل التالي:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-baf3cc3cbe-dd1a6f-cd5cc0.webp)
على وجه التحديد ، إضافة اثنين من ECPs ، P و Q:
أوجد تقاطع الخط PQ والمنحنى R ، المعرف ك - (P + Q)
اقلب إلى نقطة “المرآة” R "على منحنى R.
لذلك نحدد إضافة نقاط المنحنى الإهليلجي P + Q = R ':
لاحظ أن هذه القاعدة تنطبق أيضا على حالات خاصة ، أي عندما تكون الإضافة الذاتية ECP ، حيث سيتم استخدام ظل النقطة.
لنفترض الآن أننا اخترنا نقطة عشوائية G وقمنا بتعيين الرقم 1 إليها. (يبدو هذا “التعيين الأولي” تعسفيا بعض الشيء.) المزيد عن ذلك لاحقا). ثم لكي ينتمي أي n إلى Fp ، نحدد:
E (N) = G + G + G + …+ G = G
هذا له تعبير فعل. الإجراءات التي تحدد +G هي “مولدات” ويشار إليها ب g. ثم التعريف أعلاه يعادل:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-bb825d6ba2-dd1a6f-cd5cc0.webp)
بالنسبة لأولئك الذين ليسوا على دراية بالمنحنيات الإهليلجية ، يمكنك تشبيه هذا التعيين بدالة أسية منتظمة حيث يحل الكاردينال g محل الأرقام الحقيقية. العمليات الحسابية تتصرف بالمثل. ومع ذلك ، فإن الاختلاف الرئيسي هو أن الدالة العكسية ل g ^ n غير ممكنة حسابيا. أي أنه لا توجد طريقة لحساب إصدار المنحنى الإهليلجي! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c989bcd81c-dd1a6f-cd5cc0.webp)。 هذا ، بالطبع ، أساس تشفير المنحنى الإهليلجي. يعرف هذا التعيين بالتشفير أحادي الاتجاه.
لاحظ أنه بالنظر إلى منحنى بيضاوي الشكل ، نظرا لأن اختيار G (وبالتالي Generator g) أمر تعسفي (باستثناء النقاط الموجودة على المحور x) ، فهناك عدد لا حصر له من الطرق لتعيينه. يمكن أن يكون اختيار (G أو g) مشابها لاختيار العلاقة الأساسية لدالة أسية (2 ^ x ، 10 ^ x ، e ^ x ، إلخ) كجزء من الفطرة السليمة.
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-ce9f261ecc-dd1a6f-cd5cc0.webp)
ومع ذلك ، فإن المعادلة (5) التي تريد أليس إثباتها هي معادلة تربيعية وبالتالي ليست خطية بدرجة كافية. للتعامل مع الحدود التربيعية ، نحتاج إلى تعريف الضرب في فضاء التشفير. يعرف هذا باسم وظيفة الاقتران ، أو الخريطة ثنائية الخط ، وسيتم شرحه بعد ذلك.
رسم الخرائط ثنائية الخطوط
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-146a4881e5-dd1a6f-cd5cc0)
سلسلة مرجعية مشتركة
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-17e9a49fa0-dd1a6f-cd5cc0.webp)
تسمى العملية برمتها “مفتاح التحقق” ، أو VK للاختصار. لا يوجد سوى 7 نقاط منحنى إهليلجي (ECPs) متضمنة هنا ، والتي يجب تقديمها إلى المدقق. من المهم ملاحظة أنه بغض النظر عن عدد المدخلات وقيود المستوى الأول التي تنطوي عليها المشكلة ، فإن VK يتكون دائما من 7 ECPs.
بالإضافة إلى ذلك ، تجدر الإشارة إلى أنه يمكن إجراء “الإعداد الموثوق” وعملية إنشاء PK و VK مرة واحدة لمشكلة معينة.
الإثبات والتحقق
الآن باستخدام المفتاح العام (PK) ، ستحسب أليس نقاط المنحنى الإهليلجي التالية (ECPs):
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c7eacd57e6-dd1a6f-cd5cc0.webp)
هذه 9 نقاط منحنى إهليلجي هي مفتاح البراهين غير التفاعلية الموجزة للمعرفة الصفرية (zk-SNARKs)!
لاحظ أن أليس تقوم في الواقع ببعض العمليات التوافقية الخطية على نقاط المنحنى الإهليلجي في المفتاح العام. هذا أمر بالغ الأهمية بشكل خاص وسيتم التحقق منه أثناء التحقق من الصحة.
الآن بعد أن سلمت أليس دليل zk-SNARK ، دعنا ندخل أخيرا في عملية التحقق ، وهي عملية من ثلاث خطوات.
بادئ ذي بدء ، من المهم التأكد من أن أول 8 نقاط منحنى إهليلجي هي في الواقع مزيج خطي من تلك النقاط في السلسلة المرجعية العامة.
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-4cf599e8c2-dd1a6f-cd5cc0.webp)
إذا كانت جميع الشيكات الثلاثة صحيحة ، التحقق من المعادلة (5) ، لذلك نعتقد أن أليس تعرف الشاهد.
دعونا نشرح الأساس المنطقي وراء المعادلة. خذ المعادلة الأولى في الجزء الأول كمثال ، والتي تنطبق بسبب الطبيعة ثنائية الخط:
! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-0032ace846-dd1a6f-cd5cc0.webp)
ومع ذلك ، نظرا لأن أليس لا تعرف قيمة الرمز ألفا ، فهي غير قادرة على حساب هذه الإضافة صراحة. كانت الطريقة الوحيدة التي يمكنها من خلالها التوصل إلى زوج يفي بالمعادلة (EA ، EA ') هي استخدام نفس مجموعة المتجهات s لكل منهما ، احسب! [قوة براهين المعرفة الصفرية: فك تشفير zk-SNARKs رياضيا] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-933d054c72-dd1a6f-cd5cc0.webp).
المراجع
“Zk-SNARKs: تحت الغطاء” (فيتاليك بوتيرين)
“مراجعة لبراهين المعرفة الصفرية” (توماس تشين ، آبي لو ، جيرن كونبيتايا ، وآلان لو)
“لماذا وكيف يعمل zk-SNARK: تفسير نهائي” (ماكسيم بيتكوس)
الموقع الإلكتروني: براهين المعرفة الصفرية
ويكيبيديا: منحنى إهليلجي
ويكيبيديا: حقل محدود
ويكيبيديا: التشفير القائم على الاقتران
