ستقوم هذه المقالة بفك تشفير هذه التقنية باستخدام الرياضيات، موضحة كيف يمكنها إثبات حقيقة المعرفة دون الكشف عن أي معلومات.

تم تجميعه بواسطة: أبحاث دودو

المؤلف: 0xAlpha المؤسس المشارك @DeriProtocol

مقدمة العملة

ZK-snark، أو حجة المعرفة المختصرة غير التفاعلية للمعرفة، تمكن المدقق من تأكيد أن المُثبت يمتلك معرفة معينة (تسمى الشهود) ترضي علاقات محددة دون الكشف عن أي معلومات حول المعرفة نفسها.

يتضمن إنشاء ZK-SNARK لمشكلة معينة المراحل الأربع التالية:

• قم بتحويل مشكلة (أو وظيفة) إلى دائرة حسابية.
• ثم تُترجم هذه الدائرة إلى معادلة مصفوفة.
• يتم تحويل معادلة المصفوفة هذه أيضًا إلى متعدد الحدود يجب أن يكون قابلاً للقسمة على حد أدنى محدد متعدد الحدود.
• أخيرًا، يتم التعبير عن قابلية القسمة هذه بنقاط منحنى بيضاوي فوق حقل محدود، حيث يتم الإثبات.

تقوم الخطوات الثلاث الأولى فقط بتحويل تمثيل العبارة الأصلية. تعرض الخطوة الأخيرة العبارة من الخطوة الثالثة إلى مساحة مشفرة باستخدام التشفير المتماثل، مما يسمح للمُثبت بالتحقق من العبارات المنعكسة الموجودة فيها. وبالنظر إلى أن هذا الإسقاط يستخدم التشفير غير المتماثل، فليس من الممكن التراجع عن العبارة الواردة في الخطوة 3 إلى البيان الأصلي، مما يضمن عدم التعرض للمعرفة.

الخلفية الرياضية المطلوبة لقراءة هذه المقالة قابلة للمقارنة بمستوى الجبر المتوقع لطلاب كلية STEM في السنة الأولى. قد يكون المفهوم الوحيد الذي قد يمثل تحديًا هو تشفير المنحنى البيضاوي. بالنسبة لأولئك الذين ليسوا على دراية بهذا، يمكنك التفكير فيه كدالة أسية ذات قاعدة خاصة، مع الأخذ في الاعتبار أن معكوسها يظل بدون حل.

ستتبع هذه المقالة قواعد الترميز التالية:

المصفوفات: أحرف كبيرة غامقة، على سبيل المثال A؛ مكتوب بأشكال صريحة\
المتجهات: حرف صغير مع أسهم، مكتوب بأشكال صريحة []؛ جميع المتجهات هي متجهات أعمدة افتراضيًا\
المقاييس: يتم تمثيلها بأحرف عادية

لنأخذ السؤال التالي كمثال:

f (x) =x^3+x^2+5 (1)

لنفترض أن أليس تريد إثبات أنها تعرف الحقيقة. سنستعرض الإجراء بأكمله الذي تحتاج أليس إلى اتخاذه لإنشاء ZK-snark لإثباتها.
قد يبدو هذا السؤال بسيطًا جدًا لأنه لا يتضمن تدفق التحكم (على سبيل المثال، if-then-else). ومع ذلك، ليس من الصعب تحويل الوظائف مع تدفق التحكم إلى تعبيرات حسابية. على سبيل المثال، ضع في اعتبارك المشكلة التالية (أو «الوظيفة» في لغات البرمجة):

f (x، z):
إذا (z==1):
إرجاع xxx+xx+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) إلى العمليات الحسابية الأساسية التالية:

هذا يتوافق مع الدائرة الحسابية التالية:

نشير أيضًا إلى المعادلة (2) كمجموعة من 4 «قيود أولية»، كل قيد يصف علاقة البوابة الحسابية في الدائرة. بشكل عام، يمكن تلخيص مجموعة من القيود الأساسية n كبرنامج حسابي تربيعي (QAP)، والذي سيتم شرحه بعد ذلك.

الخطوة 2: المصفوفة

أولاً، دعنا نحدد متجه «الشاهد» على النحو التالي:

حيث يتم تعريف y و s1 و s2 و s3 كما في المعادلة (2).
عادةً ما تكون هناك مشكلة تتعلق بمدخلات m وبوابات حسابية n (بمعنى آخر. n-1 (الخطوات المتوسطة والإخراج النهائي)، سيكون متجه الشاهد هذا ذو أبعاد (m+n+1). في حالات العالم الحقيقي، يمكن أن يكون الرقم n كبيرًا للغاية. على سبيل المثال، بالنسبة لوظائف التجزئة، عادة ما تكون n بالآلاف.

بعد ذلك، دعونا نبني ثلاث مصفوفات n(m+n+1) A، B، C حتى نتمكن من إعادة كتابة المعادلة (2) على النحو التالي:

المعادلة (3) هي مجرد تمثيل آخر للمعادلة (2): كل مجموعة (ai، bi، ci) تتوافق مع بوابة في الدائرة. يمكننا رؤية ذلك من خلال توسيع معادلة المصفوفة بشكل صريح:

لذا فإن LHS=RHS هي بالضبط نفس المعادلة (2)، وكل صف من معادلة المصفوفة يتوافق مع قيد أساسي (أي بوابة حسابية في الدائرة).

لقد تخطينا خطوات البناء (A، B، C)، والتي هي في الواقع بسيطة نسبيًا. نحتاج فقط إلى تحويلها إلى مصفوفة وفقًا للقيود الأولية المقابلة لتحديد محتوى كل صف من (A، B، C)، أي (ai، bi، ci). بأخذ الصف الأول كمثال: يمكننا أن نرى بسهولة أنه لجعل القيد الأساسي الأول x مضروبًا في x يساوي s1، نحتاج إلى ضرب [0,1,0,0,0] و [0, 1,0,0,0] و [0,0,0,1,0,0] بالمتجه s.

وهكذا نجحنا في تحويل الدائرة الحسابية إلى معادلة مصفوفة، وهي المعادلة (3). في الوقت نفسه، قمنا أيضًا بتغيير الكائن الذي يجب إثبات إتقانه إلى متجه الشهود.

الخطوة 3: كثيرات الحدود

الآن، دعونا نبني مصفوفة n(n+m+*1) PA، والتي تحدد مجموعة من متعددات الحدود فيما يتعلق بـ z:

التأكد من أن الدالةتأخذ القيم التالية في {1, 2, 3, 4} يفي بالشروط:

ثم يمكننا إعادة كتابة A على النحو التالي:

هذه أربع مجموعات من المعادلات الخطية تتضمن ستة متغيرات يمكن حلها باستخدام الطرق التقليدية. ومع ذلك، فإن الطريقة الأكثر فعالية لحل PA في هذه الحالة هي الاستكمال اللاغراني، الذي يستغل خصوصيات المشكلة. هنا نتخطى عملية حل PA، وهي عملية شاقة بعض الشيء ولكنها مباشرة.

وبالمثل، نقوم ببناء PB و PC بشكل منفصل لـ B و C. ثم يمكننا إعادة كتابة معادلة المصفوفة علىالنحو التالي:

من خلال مراقبة كل صف على حدة، يتضح أن هذه الصفوف الأربعة تتوافق مع نفس التعبير الذي تم تقييمه في أربع نقاط مختلفة. لذلك، معادلة المصفوفة أعلاه تعادل:

الخطوة 3: نقطة المنحنى البيضاوي

أعد كتابة المعادلة (4) على النحو التالي:

حيث i (z) =1 هو مجرد متعدد الحدود بدرجة الصفر في z يستخدم لتوحيد المعادلات - جميع المصطلحات تربيعية. ستتضح ضرورة ذلك قريبًا. لاحظ أن هذه المعادلة تحتوي فقط على جمع وضرب كثيرات الحدود في z.

يرجى ملاحظة أن العمليات الحسابية والجمع (+) والضرب (X) يتم تعيينها أيضًا للعمليات المقابلة في المجال المحدود لنقاط المنحنى الإهليلجي. يتم استخدام الرموز لتجنب الارتباك والإشارة إلى إعادة تعريف هذه العمليات الميدانية.

بعد ذلك، سنشرح الخطوات العملية بمزيد من التفصيل.

تشفير المنحنى الإهليلجي

تتجاوز النظرية العامة للمنحنيات الإهليلجية نطاق هذه المقالة. للأغراض الواردة هنا، يُعرَّف المنحنى البيضاوي على أنه تعيينات من الحقل الرئيسي Fp إلى الوظيفة E، حيث يتضمن E نقاطًا مثل y^2=x^3+ax+b (تسمى نقاط المنحنى الإهليلجي، أو ECPs للاختصار).

يرجى ملاحظة أنه بينما كنا نناقش الحساب العادي حتى الآن، عند الانتقال إلى حقل أولي، يتم تنفيذ العمليات الحسابية على الأرقام باستخدام الحساب المعياري. على سبيل المثال، a+b=a+b (mod p)، حيث p هو ترتيب Fp.

من ناحية أخرى، يتم تحديد إضافة نقطتي منحنى بيضاوي كما هو موضح أدناه:

على وجه التحديد، إضافة P و Q لاثنين من ECPs:

ابحث عن تقاطع الخط PQ والمنحنى R وقم بتعريفه على أنه - (P+Q) انتقل
إلى نقطة «المرآة» R' لـ R على المنحنى.
لذلك نحدد إضافة نقاط المنحنى البيضاوي P+Q = R':

لاحظ أن هذه القاعدة تنطبق أيضًا على الحالة الخاصة حيث يتم استخدام إضافة ECP واحد، وفي هذه الحالة سيتم استخدام المماس لتلك النقطة.

لنفترض الآن أننا اخترنا عشوائيًا النقطة G ونرسم الرقم 1 لها. (يبدو هذا «التعيين الأولي» تعسفيًا بعض الشيء. سنناقشها لاحقًا). وبالنسبة للعديد من الأشخاص الذين ينتمون إلى Fp، نحدد:

E (N) =G+G+G+... +G=G مضروبًا في n

هناك تعبير عملية. حدد العملية +G على أنها «مولد»، ويُشار إليها بـ g. ثم التعريف أعلاه يعادل:

بعد تعريف الإضافة، تصبح العلاقة الخطية التالية واضحة:

لذلك، سيتم الاحتفاظ بأي علاقة خطية (أو قيد) في Fp في الفضاء المشفر B من خلال هذا التعيين. على سبيل المثال، ستؤدي المعادلة l + m = n في Fp إلى

ومع ذلك، بما أن المعادلة (5) التي تريد أليس إثباتها في الصورة التربيعية، فهي ليست خطية بدرجة كافية. من أجل التعامل مع المصطلحات التربيعية، نحتاج إلى تعريف الضرب في الفضاء المشفر. وهذا ما يسمى بالخريطة المزدوجة أو ثنائية الخطوط، والتي سأشرحها في القسم التالي.

خريطة ثنائية الخطوط

لنفترض أن G1 و G2 و GT هي مجموعات من الدرجة الأولى g. يتم تعريف وظيفة الاقتران، أو الخريطة ثنائية الخطوط، على النحو التالي:

سلسلة مرجعية مشتركة

هذا كله يسمى «مفتاح الإثبات» (PK). لاحظ أن تمثيل المتجهات داخل E () يجب أن يُفهم على أنه متجهات لنقاط المنحنى الإهليلجي، حيث يتم تعيين كل نقطة من عنصر المتجه المقابل. وبالتالي، فإن هذه المتجهات الـ 11 تشتمل فعليًا على 62 (= 42+6 3+63+63) نقطة منحنى بيضاوي. سيتم توفير برامج ECP الـ 62 هذه إلى أليس، المُثبت. في السيناريو العام، بالنسبة لمشكلة المدخلات m والقيود الأساسية n، سيحتوي PK على 2n + 3 (m+n+1) *3 = 11n + 9m + 9 ECPs.

في نفس الوقت، سيتم تنفيذ الحسابات التالية:

تسمى العملية بأكملها «مفتاح التحقق» (VK). يتم تضمين 7 نقاط منحنى بيضاوي (ECPs) فقط هنا، والتي يجب تقديمها إلى المدقق. وتجدر الإشارة إلى أنه بغض النظر عن عدد المدخلات والقيود الأولية التي تنطوي عليها المشكلة، فإن VK يتكون دائمًا من 7 ECPs.

بالإضافة إلى ذلك، تجدر الإشارة إلى أن «الإعداد الموثوق» وعملية إنشاء PK و VK يجب أن تتم مرة واحدة فقط لمشكلة معينة.

الإثبات والتحقق

تمتلك أليس الآن المفتاح العام (PK)، وستحسب نقاط المنحنى الإهليلجي التالية (ECPs):

تعتبر نقاط المنحنى الإهليلجية التسع هذه ضرورية لحجة المعرفة الموجزة وغير التفاعلية للمعرفة (ZK-SNARK)!

لاحظ أن أليس تقوم أساسًا بإجراء مجموعات خطية على نقاط المنحنى الإهليلجي في المفتاح العام. هذا أمر بالغ الأهمية وسيتم فحصه بدقة أثناء التحقق.

الآن، تقدم أليس دليل ZK-SNARK، مما يقودنا أخيرًا إلى عملية التحقق، والتي تحدث في ثلاث خطوات.

أولاً، من الضروري التأكد من أن نقاط المنحنى الإهليلجية الثمانية الأولى هي بالفعل مجموعات خطية لتلك النقاط في السلسلة المرجعية المشتركة.

إخلاء المسؤولية：

1. تمت إعادة طباعة هذه المقالة من [chaincatcher]. جميع حقوق الطبع والنشر تنتمي إلى المؤلف الأصلي [0xAlpha المؤسس المشارك @ DERiProtocol]. إذا كانت هناك اعتراضات على إعادة الطبع هذه، فيرجى الاتصال بفريق Gate Learn ، وسيتعاملون معها على الفور.
2. إخلاء المسؤولية: الآراء ووجهات النظر الواردة في هذه المقالة هي فقط آراء المؤلف ولا تشكل أي نصيحة استثمارية.
3. يقوم فريق Gate Learn بترجمة المقالة إلى لغات أخرى. ما لم يُذكر، يُحظر نسخ المقالات المترجمة أو توزيعها أو سرقتها.