كانون صفر المعرفة

ملاحظة المحرر: يحتوي تشفير a16z على سلسلة طويلة من "البنادق"، منا داو كانون العام الماضي لنا NFT كانون في وقت سابق (وقبل ذلك لدينا الأصلي تشفير كانون) - تأكد من التسجيل في موقعنا النشرة الأسبوعية web3 لمزيد من التحديثات بالإضافة إلى الموارد المنسقة الأخرى.

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

كانت أنظمة إثبات المعرفة الصفرية موجودة منذ عقود: كان لإدخالها من قبل شافي جولدفاسر وسيلفيو ميكالي وتشارلز راكوف في عام 1985 تأثير تحولي في مجال التشفير ، وتم الاعتراف بها من قبل ACM Turing Award الممنوحة لجولدفاسر وميكالي في 2012. نظرًا لأن هذا العمل - بما في ذلك انتقاله من النظرية إلى الممارسة والتطبيقات في crypto / web3 اليوم - قد استغرق عدة عقود ، فإننا نشارك أيضًا للمرة الأولى في سلسلة شرائعنا الجزء الثاني (في الوقت الحالي ، مضمن هنا أدناه): قائمة قراءة مشروحة بـ جاستن ثالر، باتباع الجزء الأول أدناه.

شكر وتقدير: شكرًا أيضًا لمايكل بلاو وسام راجسدال وتيم روغاردن.

أسس ، خلفية ، تطورات

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

اتجاهات جديدة في التشفير (1976)
بواسطة ويتفيلد ديفي ومارتن هيلمان
https://ee.stanford.edu/~hellman/publications/24.pdf

طريقة للحصول على التوقيعات الرقمية وأنظمة تشفير المفتاح العام
بقلم رونالد ريفيست وعدي شامير وليونارد أدلمان
https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=856E21BC2F75800D37FD611032C30B9C?doi=10.1.1.40.5588&rep=rep1&type=pdf

بروتوكولات لأنظمة تشفير المفتاح العام (1980)
بواسطة رالف ميركل
http://www.merkle.com/papers/Protocols.pdf

الاتصالات الآمنة عبر القنوات غير الآمنة (1978)
بواسطة رالف ميركل
https://www.merkle.com/1974/PuzzlesAsPublished.pdf

استخدام المنحنيات الإهليلجية في التشفير (1988)
بواسطة فيكتور ميلر
https://link.springer.com/content/pdf/10.1007%2F3-540-39799-X_31.pdf

التعقيد المعرفي لأنظمة الإثبات التفاعلية (1985)
بقلم شافي جولدفاسر وسيلفيو ميكالي وتشارلز راكوف
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.419.8132&rep=rep1&type=pdf

البراهين السليمة حسابيًا (2000)
بواسطة سيلفيو ميكالي
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf

من مقاومة الاصطدام القابلة للاستخراج إلى الحجج المختصرة غير التفاعلية للمعرفة [SNARKs] والعودة مرة أخرى (2011)
بقلم نير بيتانسكي وران كانيتي وأليساندرو كيزا وعيران ترومر
https://eprint.iacr.org/2011/443.pdf

حجة المعرفة الصفرية الفعالة لصحة المراوغة (2012)
بواسطة ستيفاني باير وجينز جروث
http://www0.cs.ucl.ac.uk/staff/J.Groth/MinimalShuffle.pdf

معرفة صفرية غير تفاعلية موجزة لهندسة معمارية فون نيومان (2013)
بقلم إيلي بن ساسون وأليساندرو كيزا وإيران ترومر ومادارس فيرزا
https://eprint.iacr.org/2013/879.pdf

سلامة حسابية قابلة للتطوير وشفافة وآمنة بعد الكم (2018)
بقلم إيلي بن ساسون وإيدو بنتوف وينون هوريش ومايكل ريابزيف
https://eprint.iacr.org/2018/046.pdf

حجج المعرفة الصفرية للعملات العامة مع (تقريبًا) الحد الأدنى من الوقت والمساحة (2020)
بقلم ألكسندر بلوك وجوستين هولمغرين وألون روزين ورون روثبلوم وبراتيك سوني
https://www.iacr.org/cryptodb/data/paper.php?pubkey=30645

لمحات عامة ومقدمات

البراهين والحجج والمعرفة الصفرية - نظرة عامة على الحوسبة التي يمكن التحقق منها والبراهين والحجج التفاعلية ، وبروتوكولات التشفير التي تمكن المُثبِت من تقديم ضمان للمحقق بأن المُثبِت قد أجرى الحساب المطلوب بشكل صحيح ، بما في ذلك المعرفة الصفرية (حيث لا تكشف البراهين أي معلومات بخلاف صحتها) . تحتوي حجج Zk على عدد لا يحصى من التطبيقات في علم التشفير وقد قفزت من النظرية إلى الممارسة خلال العقد الماضي.
بواسطة جاستن ثالر
https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

تطور نماذج البراهين الصفرية المعرفة - مراجعة لإثباتات المعرفة الصفرية ، حيث يبحث Meiklejohn (كلية لندن الجامعية ، Google) في التطبيقات التي تقود تطورها ، والنماذج المختلفة التي ظهرت لالتقاط هذه التفاعلات الجديدة ، والإنشاءات التي يمكننا تحقيقها ، والعمل غادر الى القيام به.
بواسطة سارة ميكليجون
https://www.youtube.com/watch?v=HO97kVMI3SE

جلسات السبورة ZK - وحدات تمهيدية
مع دان بونيه وآخرون
https://zkhack.dev/whiteboard/

الأمن والخصوصية للتشفير مع zkps - الريادة في إثبات عدم المعرفة في الممارسة ؛ ما هي zkps وكيف تعمل ... بما في ذلك "العرض التوضيحي" للمسرح المباشر
بواسطة زوكو ويلكوكس
https://a16z.com/2019/08/29/security-and-privacy-for-crypto-with-zero-knowledge-proofs/

شرح أهم الموضوعات التقنية - بما في ذلك التعاريف والآثار المترتبة على المعرفة الصفرية بشكل عام
بقلم جو بونو وتيم روجاردن وسكوت كومينرز وعلي يحيى وكريس ديكسون
https://web3-with-a16z.simplecast.com/episodes/hot-research-summer-blockchain-crypto-tech-topics-explainers-overviews-seminar-videos

كيف ستعمل طبقة الخصوصية القادمة على إصلاح الويب المعطل
بواسطة هوارد وو
https://future.com/a-privacy-layer-for-the-web-can-change-everything/

مقدمة إلى zkSNARKs
مع هوارد وو وآنا روز
https://zeroknowledge.fm/38-2/

لماذا وكيف يعمل zk-SNARK: شرح نهائي
بواسطة ماكسيم بيتكوس
https://arxiv.org/pdf/1906.07221.pdf

مقدمة لأدلة المعرفة الصفرية
بواسطة فريدريك هاريسون وآنا روز
https://www.zeroknowledge.fm/21 [+ ملخص الكتابة في مكان آخر هنا]

Zk-SNARKs: تحت الغطاء
بواسطة فيتاليك بوتيرين
https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6
جزء 1, جزء 2, جزء 3

السرعة اللامركزية - على التقدم في براهين المعرفة الصفرية ، والأجهزة اللامركزية
بواسطة إلينا برجر
https://a16z.com/2022/04/15/zero-knowledge-proofs-hardware-decentralization-innovation/

أحدث البحوث zk - مع باحث zk في مؤسسة Ethereum
مع ماري مالر وآنا روز وكوبي جوركان
https://zeroknowledge.fm/232-2/

استكشاف بحث zk - مع مدير الأبحاث في DFINITY ؛ أيضا وراء التطورات مثل Groth16
مع جينس غروث وآنا روز وكوبي غوركان
https://zeroknowledge.fm/237-2/

أبحاث SNARK و أصول التدريس - مع أحد مؤسسي ZCash و Starkware
مع أليساندرو كييزا وآنا روز
https://zeroknowledge.fm/episode-200-snark-research-pedagogy-with-alessandro-chiesa/

الغطس العميق ، أدلة البناء

أسس البراهين الاحتمالية - دورة مكونة من 5 وحدات من البراهين التفاعلية وأكثر
بواسطة أليساندرو كييزا
https://www.youtube.com/playlist?list=PLGkwtcB-DfpzST-medFVvrKhinZisfluC

STARKs - الجزء الأول والثاني والثالث
بواسطة فيتاليك بوتيرين
https://vitalik.ca/general/2017/11/09/starks_part_1.html
https://vitalik.ca/general/2017/11/22/starks_part_2.html
https://vitalik.ca/general/2018/07/21/starks_part_3.html

تشريح ستارك - برنامج تعليمي من ستة أجزاء يشرح آليات نظام مقاومة ستارك
بواسطة آلان زيبينيك
https://aszepieniec.github.io/stark-anatomy/

تصميم SNARK ، الجزء 1 - المسح ، الاستخدام في التراكمية ، المزيد
بواسطة جاستن ثالر
https://www.youtube.com/watch?v=tg6lKPdR_e4

تصميم SNARK ، الجزء 2 - التراكمية والأداء والأمن
بواسطة جاستن ثالر
https://www.youtube.com/watch?v=cMAI7g3UcoI

قياس أداء SNARK - الواجهة الأمامية والخلفية والمزيد
بواسطة جاستن ثالر
https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

فهم PLONK
https://vitalik.ca/general/2019/09/22/plonk.html

نظام إثبات عدم المعرفة PLONK - سلسلة من 12 مقطع فيديو قصيرًا حول كيفية عمل PLONK
بواسطة ديفيد وونغ
https://www.youtube.com/playlist?list=PLBJMt6zV1c7Gh9Utg-Vng2V6EYVidTFCC

من AIRs إلى RAPs - كيف يعمل الحساب بأسلوب PLONK
بواسطة ارييل جابيزون
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

عمليات التحقق المتعددة في PLONK و Plookup
بواسطة ارييل جابيزون
https://hackmd.io/@arielg/ByFgSDA7D

تصميم Halo2 - من ECC
https://zcash.github.io/halo2/design.html

لونكي 2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

التطبيقات والبرامج التعليمية: إثبات المفاهيم والعروض التوضيحية والأدوات والمزيد

تطبيق zk - مصادر التعلم
بواسطة 0xPARC
https://learn.0xparc.org/materials/intro

بيئة تطوير عبر الإنترنت لـ zkSNARKs - zkREPL ، مجموعة جديدة من الأدوات للتفاعل مع حزمة أدوات Circom في المتصفح
بواسطة كيفن كووك
https://zkrepl.dev (+ الخيط التوضيحي هنا)

برامج حسابية من الدرجة الثانية من الصفر إلى البطل
بواسطة فيتاليك بوتيرين
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

على zkEVMs
مع أليكس جلوتشوسكي وآنا روز
https://zeroknowledge.fm/175-2/

أنواع مختلفة من zkEVMs
بواسطة فيتاليك بوتيرين
https://vitalik.ca/general/2022/08/04/zkevm.html

التعلم الآلي ZK - برنامج تعليمي وعرض توضيحي لوضع شبكة عصبية في SNARK
بقلم هوراس بان وفرانسيس هو وهنري بالاتشي
https://0xparc.org/blog/zk-mnist

على لغات ZK
مع أليكس أوزدمير وآنا روز
https://zeroknowledge.fm/172-2/

Dark Forest - تطبيق تشفير zk على الألعاب - لعبة RTS (إستراتيجية الوقت الحقيقي) لا مركزية بالكامل ومستمرة
https://blog.zkga.me/announcing-darkforest

ZKPs للمهندسين - نظرة على Dark Forest ZKPs
https://blog.zkga.me/df-init-circuit

الغوص في المعرفة الصفرية
مع إيلينا نادولينسكي وآنا روز وجيمس بريستويتش
https://zeroknowledge.fm/182-2/

zkDocs: مشاركة المعلومات الصفرية
بواسطة سام راجسدال ودان بونيه
https://a16zcrypto.com/zkdocs-zero-knowledge-information-sharing/

إنزال الهواء المشفر لحماية الخصوصية مع عدم وجود أدلة على المعرفة
بواسطة سام راجسدال
https://a16z.com/2022/03/27/crypto-airdrop-privacy-tool-zero-knowledge-proofs/

احتفالات الإعداد الموثوق بها على السلسلة -
بواسطة فاليريا نيكولاينكو وسام راجسدال
https://a16zcrypto.com/on-chain-trusted-setup-ceremony/

لوائح التشفير والتمويل غير المشروع والخصوصية وغير ذلك - يتضمن قسمًا عن المعرفة الصفرية في السياقات التنظيمية / الامتثال ؛ الفرق بين تقنيات "الحفاظ على الخصوصية" مقابل تقنيات التشويش
مع ميشيل كورفر وجاي راماسوامي وسونال تشوكشي
https://web3-with-a16z.simplecast.com/episodes/crypto-regulations-sanctions-compliance-aml-ofac-news-explained

مصادر أخرى

النشرة الإخبارية zkMesh - نشرة إخبارية شهرية تشارك أحدث التقنيات اللامركزية للحفاظ على الخصوصية ، وتطوير بروتوكول الخصوصية ، وأنظمة المعرفة الصفرية
https://zkmesh.substack.com/

بودكاست المعرفة الصفرية - على أحدث تطبيقات البحث zk و zk وخبراء بناء تقنية خصوصية تدعم التشفير
مع آنا روز
https://zeroknowledge.fm/

... قائمة قراءة مشروحة ، حسب الموضوع والتسلسل الزمني ، بقلم جاستن ثالر:

SNARKs من PCPs الخطية (المعروف أيضًا باسم SNARKs مع إعداد خاص بالدائرة)

الحجج الفعالة بدون PCPs قصيرة (2007)
بقلم يوفال إشاي وإيال كوشيلفيتز ورافيل أوستروفسكي

قبل حوالي عام 2007 ، تم تصميم SNARKs بشكل أساسي عبر كيليان-ميكالي نموذج ، لأخذ برهان احتمالي "قصير" قابل للفحص (PCP) و "تجميعه بشكل مشفر" في حجة موجزة عبر تجزئة Merkle وتحويل Fiat-Shamir. لسوء الحظ ، فإن PCPs القصيرة معقدة وغير عملية ، حتى اليوم. أظهرت هذه الورقة (IKO) كيفية استخدام التشفير متماثل الشكل للحصول على حجج تفاعلية موجزة (غير شفافة) من PCPs "طويلة ولكن منظمة". يمكن أن تكون هذه أبسط بكثير من PCPs القصيرة ، ويكون لـ SNARKs الناتج أدلة أقصر بكثير وتحقق أسرع. تم التعرف على هذه الحجج لأول مرة على أنها تنطوي على إمكانية تحقيق الكفاءة العملية ، وتم صقلها وتنفيذها ، في فلفل اسود. لسوء الحظ ، تحتوي حجج IKO على مُثبِّت تربيعي الوقت وسلسلة مرجعية هيكلية ذات حجم تربيعي ، لذا فهي لا تتناسب مع الحسابات الكبيرة.

برامج من الدرجة الثانية و NIZK موجزة بدون PCPs (2012)
بقلم روزاريو جينارو وكريغ جينتري وبريان بارنو وماريانا رايكوفا

خفضت ورقة الاختراق هذه (GGPR) تكاليف المُثبِت لنهج IKO من تربيعي في حجم الدائرة إلى شبه خطية. بناء على عمل سابق لـ غروث و ليبما، كما أنها أعطت SNARKs عبر التشفير القائم على الاقتران ، بدلاً من الحجج التفاعلية كما هو الحال في IKO. وصفت SNARKs الخاصة بها في سياق ما يشار إليه الآن باسم مشاكل رضاء القيد من المرتبة الأولى (R1CS) ، وهو تعميم لمرضية الدائرة الحسابية.

كانت هذه الورقة أيضًا بمثابة الأساس النظري لأول SNARKs لرؤية الانتشار التجاري (على سبيل المثال ، في ZCash) وأدت مباشرة إلى SNARKs التي لا تزال شائعة اليوم (على سبيل المثال ، Groth16). جاء التنفيذ الأولي لحجج GGPR الزعتر و بينوكيو، وتشمل المتغيرات اللاحقة SNARKs لـ C. و BCTV. BCIOP أعطى إطارًا عامًا يوضح هذه التحولات الخطية من PCPs إلى SNARK (انظر أيضًا الملحق A من الزعتر) ويصف أشكال مختلفة منها.

حول حجم الحجج غير التفاعلية القائمة على الاقتران (2016)
بواسطة Jens Groth

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

SNARKs مع إعداد عالمي موثوق

PlonK: التباديل على قواعد لاغرانج للحجج المسكونية غير التفاعلية للمعرفة (2019)
بقلم أرييل جابيزون وزاكاري ويليامسون وأوانا سيوبوتارو

Marlin: معالجة zkSNARKs مسبقًا باستخدام SRS العالمي والقابل للتحديث (2019)
بقلم أليساندرو كييزا ويونكونغ هو وماري مالر وبراتيوش ميشرا وبسي فيسيلي ونيكولاس وارد

يستبدل كل من PlonK و Marlin الإعداد الموثوق به الخاص بالدائرة في Groth16 بإعداد عالمي. يأتي هذا على حساب البراهين الأكبر حجمًا من 4 × 6 أضعاف. يمكن للمرء أن يفكر في PlonK و Marlin على أنهما يأخذان العمل الخاص بالدائرة أثناء الإعداد الموثوق به في Groth16 وما سبقه وينقله إلى مرحلة ما قبل المعالجة التي تحدث بعد الإعداد الموثوق به ، وكذلك أثناء إنشاء إثبات SNARK.

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

مخططات الالتزام متعدد الحدود ، مفتاح تشفير بدائي في SNARKs

التزامات الحجم الثابت تجاه كثيرات الحدود وتطبيقاتها (2010)
بواسطة Aniket Kate و Gregory Zaverucha و Ian Goldberg

قدمت هذه الورقة فكرة مخططات الالتزام متعدد الحدود. أعطت مخططًا لكثيرات الحدود أحادية المتغير (تسمى عادةً التزامات KZG) مع التزامات ذات حجم ثابت وإثباتات تقييم. يستخدم المخطط إعدادًا موثوقًا به (أي سلسلة مرجعية منظمة) وتشفير قائم على الاقتران. لا تزال تحظى بشعبية كبيرة في الممارسة اليوم ، وتستخدم في SNARKs بما في ذلك PlonK و Marlin التي تمت مناقشتها أعلاه (ويستخدم Groth16 تقنيات تشفير متشابهة للغاية).

برهان Oracle Reed-Solomon التفاعلي على القرب (2017)
بقلم إيلي بن ساسون وإيدو بنتوف وينون هوريش ومايكل ريابزيف

يعطي إثباتًا تفاعليًا أوراكل (IOP) لاختبار Reed-Solomon - أي إثبات أن سلسلة ملتزمة قريبة من جدول تقييم متعدد الحدود وحيد المتغير. بالاقتران مع تجزئة Merkle وتحويل Fiat-Shamir ، ينتج عن ذلك مخطط التزام متعدد الحدود شفاف مع أدلة تقييم بحجم متعدد اللوغاريتمات (انظر VP19 للتفاصيل). اليوم ، لا يزال هذا هو الأقصر بين مخططات الالتزام متعدد الحدود المعقولة بعد الكم.

Ligero: حجج فرعية خفيفة الوزن بدون إعداد موثوق (2017)
بقلم سكوت أميس وكارميت هازاي ويوفال إشاي وموثوراماكريشنان فينكيتاسوبرامانيام

على غرار FRI ، يعطي هذا العمل IOP لاختبار Reed-Solomon ، ولكن بطول دليل الجذر التربيعي بدلاً من polylogarithmic. نظري أعمال أظهر أنه من خلال تبديل كود Reed-Solomon برمز مختلف لتصحيح الأخطاء مع تشفير أسرع ، يمكن للمرء الحصول على مُثبِّت الوقت الخطي الذي يعمل أيضًا بشكل أصلي على أي حقل. تم تحسين هذا النهج وتنفيذه في الفرامل أسفل و أوريون، مما يؤدي إلى أداء مثقف على أحدث طراز.

مضاد للرصاص: أدلة قصيرة للمعاملات السرية والمزيد (2017)
بقلم بينيديكت بونز ، وجوناثان بوتل ، ودان بونيه ، وأندرو بولسترا ، وبيتر ويلي ، وجريج ماكسويل

تكرير العمل السابق من قبل BCCGP، يعطي Bulletproofs مخطط التزام متعدد الحدود شفاف (في الواقع ، تعميم يسمى وسيطة المنتج الداخلي) على أساس صلابة حساب اللوغاريتمات المنفصلة مع حجم إثبات لوغاريتمي ولكن وقت التحقق الخطي. لا يزال المخطط شائعًا اليوم نظرًا لشفافيته وإثباتاته القصيرة (على سبيل المثال ، يتم استخدامه في ZCash Orchard و Monero).

دوري: حجج فعالة وشفافة للمنتجات الداخلية المعممة والالتزامات متعددة الحدود (2020)
بواسطة جوناثان لي

يقلل Dory من وقت المدقق في Bulletproofs من الخطي إلى اللوغاريتمي ، مع الحفاظ على الشفافية والبراهين اللوغاريتمية (وإن كانت أكبر بشكل ملموس من Bulletproofs) والشفافية. يستخدم الاقتران ويستند إلى افتراض SXDH.

البراهين التفاعلية والأدلة التفاعلية متعددة الأمثال وما يرتبط بها من SNARKs

تفويض الحساب: البراهين التفاعلية لل Muggles (2008)
بقلم شافي جولدفاسر ويايل طومان قلعي وجاي روثبلوم

قبل هذه الورقة ، كانت البراهين التفاعلية للأغراض العامة تتطلب أ وقت فائق الحدود مَثَل. تقدم هذه الورقة بروتوكول إثبات تفاعلي ، يُطلق عليه عادةً بروتوكول GKR ، مع مُثبِّت زمني متعدد الحدود ومدقق زمني شبه خطي ، لأي مشكلة تمتلك خوارزمية متوازية فعالة (بالتساوي ، ينطبق الدليل التفاعلي على أي دائرة حسابية ذات عمق صغير).

حساب عملي تم التحقق منه مع تدفق البراهين التفاعلية (2011)
بقلم غراهام كورمود ومايكل ميتزنماخر وجوستين ثالر

هذه الورقة (تسمى أحيانًا CMT) قللت من وقت المثول في بروتوكول GKR من رباعي في حجم الدائرة إلى شبه خطي. أنتج أول تنفيذ لإثبات تفاعلي للأغراض العامة. سطر من الأعمال اللاحقة (فلفل افرنجي, ثالر 13, زرافةو برج الميزان) قلل وقت تشغيل المُثبِّت بدرجة أكبر ، من شبه خطي إلى خطي في حجم الدائرة.

vSQL: التحقق من استعلامات SQL التعسفية عبر قواعد البيانات الديناميكية الخارجية (2017)
بواسطة Yupeng Zhang و Daniel Genkin و Jonathan Katz و Dimitrios Papadopoulos و Charalampos Papamanthou

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

فيما بعد أعمال المقدمة الحجج المعرفة الصفرية وقدمت خطط التزام مختلفة لكثيرات الحدود متعددة الخطوط.

Spartan: zkSNARKs فعالة وعامة الأغراض بدون إعداد موثوق (2019)
بواسطة سريناث سيتي

يحصل على SNARKs لإرضاء الدوائر و R1CS من خلال الجمع بين البراهين التفاعلية متعددة الأمثال (MIPs) مع مخططات الالتزام متعدد الحدود ، بناءً على العمل السابق على MIPs ذات الكفاءة الملموسة والتي تسمى نفل. التأثير هو الحصول على SNARKs مع براهين أقصر من تلك المشتقة من البراهين التفاعلية مثل بروتوكول GKR الذي تمت مناقشته أعلاه. على غرار PlonK و Marlin ، يوضح Spartan أيضًا كيفية معالجة الدوائر التعسفية وأنظمة R1CS عبر المعالجة المسبقة وتوليد إثبات SNARK.

استخدم Spartan مخطط التزام متعدد الحدود من الوبر. دعا الأعمال اللاحقة الفرامل أسفل و أوريون قم بدمج برنامج Spartan MIP مع مخططات الالتزام متعددة الحدود الأخرى لإنتاج SNARKs التي تم تنفيذها لأول مرة مع مثقف الوقت الخطي.

PCPs قصيرة PCPs و IOPs

PCPs قصيرة مع تعقيد استعلام Polylog (2005)
بقلم إيلي بن ساسون ومادو سودان

 أعطى هذا العمل النظري أول برهان احتمالي قابل للفحص (PCP) بطول إثبات شبه خطي في حجم الحساب المراد التحقق منه وتكلفة الاستعلام متعدد اللوغاريتمي (على الرغم من وقت المدقق الخطي). بعد تحويل Kilian-Micali لـ PCPs إلى SNARKs ، كانت هذه خطوة نحو SNARKs مع مدقق زمني شبه خطي ومدقق متعدد اللوغاريتمات.

العمل النظري في وقت لاحق تقليل وقت المدقق إلى متعدد اللوغاريتمات. لاحق صقل العمل المركّز عمليًا هذا النهج ، ولكن لا يزال الأشخاص الذين يستخدمون الرعاية الأولية القصيرة غير عملي اليوم. للحصول على SNARKs العملية ، الى وقت لاحق أعمال تحول إلى دعا التعميم التفاعلي PCPs البراهين التفاعلية من Oracle (IOPs). أدت هذه الجهود والبناء عليها جمعة، وهو مخطط التزام متعدد الحدود شائع تمت مناقشته في قسم الالتزامات متعدد الحدود في هذا التجميع.

تشمل الأعمال الأخرى في هذه الفئة ZKBoo ونسله. هذه لا تحقق براهين مقتضبة ، لكن لها عوامل ثابتة جيدة ، وبالتالي فهي جذابة لإثبات العبارات الصغيرة. لقد أدىوا إلى عائلات من تواقيع ما بعد الكم مثل منقوش التي لديها كان الأمثل in عدة أعمال. يتم تقديم ZKBoo على أنه نموذج تصميم متميز يسمى MPC في الرأس، لكنه ينتج IOP.

العودية SNARKs

حساب يمكن التحقق منه بشكل تدريجي أو إثباتات المعرفة ضمنيًا كفاءة الوقت / المكان (2008)
بواسطة بول فاليانت

قدم هذا العمل المفهوم الأساسي للحساب الذي يمكن التحقق منه تدريجيًا (IVC) ، والذي يقوم فيه المثل بإجراء حساب ويحافظ في جميع الأوقات على دليل على أن الحساب حتى الآن كان صحيحًا. شيدت IVC عن طريق التكوين العودي لـ SNARKs. هنا ، سلامة المعرفة خاصية SNARKs ضرورية لتأسيس سلامة الحجج غير التفاعلية المكونة بشكل متكرر. قدمت هذه الورقة أيضًا مستخرجًا فعالًا للغاية للمعرفة عن SNARKs المشتق من الفينول الخماسي الكلور (وفقًا لنموذج كيليان ميكالي).

معرفة صفرية قابلة للتطوير عبر دورات المنحنيات الإهليلجية (2014)
بقلم إيلي بن ساسون وأليساندرو كيزا وإيران ترومر ومادارس فيرزا

متابَع العمل النظري، استخدم هذا البحث تطبيقًا متكررًا لمتغير SNARK الخاص بـ GGPR ، لتوفير أول تنفيذ لـ IVC لجهاز افتراضي بسيط (TinyRAM ، من SNARKs لـ C. ورقة).

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

تكوين دليل متكرر بدون إعداد موثوق به (2019)
بقلم شون بو ، وجاك جريج ، ودايرا هوبوود

يدرس هذا العمل (المسمى Halo) كيفية تكوين SNARKs الشفافة بشكل متكرر. يعتبر هذا الأمر أكثر صعوبة من تأليف غير شفاف لأن إجراء التحقق في SNARKs الشفافة يمكن أن يكون أكثر تكلفة بكثير.

ثم أثار هذا خط of العمل التي بلغت ذروتها في أنظمة مثل Nova تحقيق أداء IVC المتطور ، متفوقًا حتى على الأداء الذي تم الحصول عليه من خلال تكوين SNARKs غير الشفافة مثل Groth16.

التطبيقات

Zerocash: مدفوعات مجهولة لامركزية من Bitcoin (2014)
بقلم إيلي بن ساسون ، وأليساندرو كيزا ، وكريستينا جارمان ، وماثيو جرين ، وإيان مايرز ، وإيران ترومر ، ومادارس فيرزا

بناء على عمل مسبق بما في ذلك Zerocoin (ومع عملة بينوتشيو كعمل متزامن) ، تستخدم هذه الورقة SNARKs المشتقة من GGPR لتصميم عملة مشفرة خاصة. أدى إلى ZCash.

Geppetto: حساب متعدد الاستخدامات يمكن التحقق منه (2014)
بقلم كريج كوستيلو وسيدريك فورنيت وجون هاول وماركولف كولويس وبنجامين كريوتر ومايكل نيهريج وبريان بارنو وسمي زاهور

يمكن القول إن Geppetto قد سبقت انفجار الاهتمام بتنفيذ العقود الذكية الخاصة ، حيث تمت كتابتها بعد عام تقريبًا من إنشاء Ethereum. ومن ثم ، لا يتم تقديمها في سياق تنفيذ العقود الذكية الخاصة. ومع ذلك ، فإنه يستخدم العودية ذات العمق المحدد لـ SNARKs للسماح لمثب غير موثوق به بتنفيذ أي برنامج كمبيوتر خاص (ملتزم / موقّع) على البيانات الخاصة ، دون الكشف عن معلومات حول البرنامج قيد التشغيل أو البيانات التي يتم تشغيله عليها. وفقًا لذلك ، فهو سابق للعمل على منصات العقود الذكية الخاصة ، مثل زيكس [هو موضح أدناه].

يمكن التحقق من ASICs (2015)
بقلم رياض وهبي ، ماكس هوالد ، سيدهارث جارج ، أبهي شيلات ، مايكل والفيش

تتناول هذه الورقة مشكلة كيفية استخدام ASIC بشكل آمن ومثمر تم تصنيعه في مسبك غير موثوق به (في عام 2015 ، كانت هناك خمس دول فقط لديها مسابك متطورة). تتمثل الطريقة في الحصول على ASIC السريع ولكن غير الموثوق به لإثبات صحة مخرجاته لمدقق يعمل على ASIC أبطأ ولكن موثوق به. الحل مثير للاهتمام طالما أن إجمالي وقت تنفيذ النظام (أي مجموع أوقات تشغيل المُثبِّت والمدقق بالإضافة إلى أي تكاليف لنقل البيانات) أقل من خط الأساس البسيط: الوقت المطلوب لتشغيل الحساب بالكامل على أبطأ - لكن موثوق به ASIC. باستخدام متغير البراهين التفاعلية GKR / CMT / Allspice ، تتفوق الورقة بالفعل على الخط الأساسي الساذج لعدد من المشكلات الأساسية ، بما في ذلك التحويلات النظرية للأرقام ، ومطابقة الأنماط ، وعمليات المنحنى الإهليلجي. يشير هذا العمل إلى أن بعض أنظمة الإثبات أكثر ملاءمة لتنفيذ الأجهزة من غيرها. يتم الآن تلقي تحسين أنظمة الإثبات لتطبيق الأجهزة كبير اهتمام، ولكن لا يزال هناك الكثير لاستكشافه.

يمكن التحقق منها وظائف التأخير (2018)
بقلم دان بونيه وجوزيف بونو وبينيديكت بونز وبن فيش

قدم تدوين وظائف التأخير التي يمكن التحقق منها (VDFs) ، وهي بدائية تشفير مفيدة على نطاق واسع في تطبيقات blockchain ، على سبيل المثال ، في التخفيف من التلاعب المحتمل في بروتوكولات توافق إثبات الحصة. تقدم SNARKs (خاصة للحسابات التي يمكن التحقق منها بشكل متزايد) طريقًا إلى أحدث محركات VDF.

Zexe: تمكين الحساب الخاص اللامركزي (2018)
بقلم شون بو ، وأليساندرو كيزا ، وماثيو جرين ، وإيان مايرز ، وبراتيوش ميشرا ، وهوارد وو

Zexe هو تصميم لمنصة عقد ذكية خاصة. يمكن للمرء أن ينظر إلى Zexe باعتباره امتدادًا لـ Zerocash (الموصوف أعلاه). يتيح Zerocash تشغيل تطبيق واحد على السلسلة (مما يتيح للمستخدمين نقل الرموز) مع حماية خصوصية بيانات المستخدم ، على سبيل المثال ، إلى من يرسلون الرموز إليه ، ويستقبلون الرموز ، وكمية الرموز التي تم نقلها ، وما إلى ذلك. يسمح Zexe بالعديد من تطبيقات مختلفة (عقود ذكية) للتشغيل على نفس blockchain والتفاعل مع بعضها البعض. يتم تنفيذ المعاملات خارج السلسلة ، ويتم نشر البراهين على التنفيذ الصحيح على السلسلة. لا يتم حماية خصوصية البيانات فحسب ، بل أيضًا خصوصية الوظيفة. هذا يعني أن الدليل المرتبط بكل معاملة لا يكشف حتى عن التطبيق (التطبيقات) التي تتعلق بها المعاملة. تتمثل المساهمة الهندسية الأكثر عمومية لـ Zexe في أنها قدمت BLS12-377 ، وهي مجموعة منحنى بيضاوي مفيدة للتكوين الفعال للعمق 1 من SNARKs القائمة على الاقتران.

آلات الحالة المنسوخة بدون تنفيذ متكرر (2020)
بقلم جوناثان لي وكيريل نيكيتين وسريناث سيتي

هذه واحدة من الأوراق الأكاديمية القليلة التي تتناول تراكمًا لقابلية تطوير blockchain. لا يستخدم مصطلح التراكمية ، لأنه يسبق أو يتزامن مع المفهوم الذي يتم تقديمه خارج الأدبيات الأكاديمية.

الأطراف الأمامية (التحولات الفعالة من برامج الكمبيوتر إلى التمثيلات الوسيطة مثل إرضاء الدوائر ، R1CS ، والمزيد)

تخفيضات سريعة من ذاكرة الوصول العشوائي (RAM) إلى مشاكل الرضا عن القيود الموجزة القابلة للتفويض (2012)
بقلم إيلي بن ساسون وأليساندرو كييزا ودانييل جنكين وعيران ترومر

من منظور حديث ، يعد هذا عملًا مبكرًا حول تحويلات عملية من برنامج كمبيوتر إلى دائرة إلى SAT من أجل تجريد آلة افتراضية (VM). البناء على أعمال من أواخر السبعينيات حتى التسعينيات (على سبيل المثال ، عمل روبسون) توضح هذه الورقة اختزالًا حتميًا من تنفيذ خطوات VM لـ T إلى مدى إرضاء دائرة بحجم O (T * polylog (T)).

الأوراق اللاحقة ، على سبيل المثال ، SNARKs لـ C. و BCTV، استمر في تطوير الواجهات الأمامية عبر تجريد VM ، وتشمل عمليات إنشاء التطبيقات الحديثة مشاريع مثل القاهرة, RISC صفرو مضلع ميدن.

أخذ حساب تم التحقق منه على أساس الإثبات على بعد خطوات قليلة من التطبيق العملي (2012)
بقلم سريناث سيتي وفيكتور فو ونيخيل بانباليا وبنجامين براون ومقيت علي وأندرو جيه بلومبرج ومايكل والفيش

هذه الورقة ، المشار إليها باسم Ginger ، هي مساهمة مبكرة أخرى في تقنيات الواجهة الأمامية العملية. قدم Ginger أدوات لأساسيات البرمجة العامة مثل الشرطية والتعبيرات المنطقية والمقارنات والحساب الأحادي عبر تقسيم البتات وحساب النقطة العائمة البدائية وما إلى ذلك. واستخدمت هذه الأدوات لتوفير الواجهة الأمامية الأولى المطبقة من لغة عالية المستوى إلى درجة منخفضة القيود الحسابية (على غرار ما يعرف الآن باسم R1CS) ، تمثيل وسيط (IR) يمكن تطبيق SNARK الخلفية عليه.

في حين أن ورقة "التخفيضات السريعة" وأحفادها تستخدم أسلوب "CPU-emulator" في إنتاج IRs (على سبيل المثال ، يفرض IR أن المثقف قام بتشغيل برنامج معين بشكل صحيح عن طريق تطبيق وظيفة الانتقال الخاصة بوحدة المعالجة المركزية لعدد محدد من الخطوات) ، يتخذ Ginger وأسلافه منهجًا أكثر شبهاً بـ ASIC ، وينتجون IRs المصممة خصيصًا لبرنامج الكمبيوتر الذي يدعي المُثقف أنه ينفذه بشكل صحيح.

على سبيل المثال، بوفيه يوضح أنه من الممكن التعامل مع تدفق التحكم المعقد في نموذج ASIC ، عن طريق تحويل تدفق التحكم هذا إلى آلة ذات حالة محدودة مصممة خصيصًا للبرنامج الجاري تنفيذه ، وأن هذا النهج يمكن أن يكون أكثر كفاءة بشكل ملحوظ من بناء محاكي وحدة المعالجة المركزية للأغراض العامة. xJsnark يعطي بنية فعالة للحسابات متعددة الدقة ، وتحسينات لذاكرة الوصول العشوائي (RAM) وذاكرة القراءة فقط (ROM) ، ويعرض لغة عالية المستوى تشبه Java لمبرمج ، والتي لا تزال شائعة اليوم. سيرك يلاحظ أن تجميع برامج الكمبيوتر إلى R1CS يرتبط ارتباطًا وثيقًا بالتقنيات المعروفة جيدًا من تحليل البرنامج ويبني مجموعة أدوات إنشاء مجمّع تتضمن أفكارًا من كلا المجتمعين ("LLVM للتمثيلات الشبيهة بالدوائر"). تشمل الأعمال السابقة التي تقدم مساهمات في الواجهات الأمامية على غرار ASIC بينوكيو و Geppetto.

استخدمت ورقة "التخفيضات السريعة" بنية معقدة ومكلفة تسمى "شبكات التوجيه" لما يسمى فحص الذاكرة (على سبيل المثال ، التأكد من أن المُثبِّت غير الموثوق به يحافظ بشكل صحيح على ذاكرة الوصول العشوائي لجهاز VM طوال تنفيذ الجهاز الظاهري الذي تم إثبات صحته). تم إجراء هذا الاختيار لأن الأعمال المبكرة مثل هذا العمل كانت تسعى للحصول على PCP ، الأمر الذي يتطلب أن تكون الواجهة الأمامية على حد سواء معلومات غير تفاعلية وآمنة نظريًا. دعا العمل في وقت لاحق حجرة المؤن (سلف من بوفيه العمل المذكور أعلاه) استخدمت أشجار Merkle بدلاً من شبكات التوجيه ، وتحقيق الكفاءة من خلال تجميع دالة تجزئة جبرية (أي "مناسبة لـ SNARK") ، بسبب اجتاي، في القيود. نتج عن ذلك واجهات أمامية "آمنة حسابيًا". يوجد اليوم مؤلفات بحثية كبيرة حول وظائف التجزئة الملائمة لـ SNARK ، مع أمثلة منها بوسيدون, ميمك, خرسانة مسلحة, إنقاذ، وأكثر من ذلك.

تعتمد التقنيات الحديثة لضمان الحفاظ على ذاكرة الوصول العشوائي (RAM) بشكل صحيح على ما يسمى بأساليب "البصمة الثابتة للتبديل" التي يعود تاريخها على الأقل إلى ليبتون (1989) وتستخدم لفحص الذاكرة بواسطة بلوم وآخرون. (1991). تتضمن هذه التقنيات بطبيعتها التفاعل بين المُثبِت والمحقق ، ولكن يمكن جعلها غير تفاعلية مع تحويل فيات شامير. على حد علمنا ، تم تقديمهم إلى الأدبيات المتعلقة بواجهات SNARK الأمامية العملية من خلال نظام يسمى vRAM.

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

إثباتات المعرفة الخطية تقريبًا من أجل التنفيذ الصحيح للبرنامج (2018)
بقلم جوناثان بوتل ، وأندريا سيرولي ، وجينز غروث ، وسوني جاكوبسن ، وماري مالر

Plookup: بروتوكول متعدد الحدود مبسط لجداول البحث (2020)
بقلم أرييل جابيزون وزاكاري ويليامسون

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

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