Canon دانش صفر

یادداشت سردبیر: کریپتو a16z دارای یک سری طولانی از "اسلحه"، از ما DAO Canon سال گذشته به ما NFT Canon قبل از آن (و قبل از آن اصلی ما Crypto Canon) - حتما برای ما ثبت نام کنید خبرنامه هفتگی web3 برای به روز رسانی های بیشتر و همچنین سایر منابع انتخاب شده.

بنابراین بایلو، ما مجموعه ای از منابع را برای کسانی که به دنبال درک، عمیق تر شدن و ساختن با همه چیز هستند جمع آوری کرده ایم. دانش صفر: فناوری‌های قدرتمند و پایه‌ای که کلیدهای مقیاس‌پذیری بلاک چین را نگه می‌دارند و آینده برنامه‌های حفظ حریم خصوصی و نوآوری‌های بی‌شماری دیگر را نشان می‌دهند. اگر پیشنهادی برای اضافه کردن قطعات با کیفیت بالا دارید، به ما اطلاع دهید @a16zcrypto.

سیستم‌های اثبات دانش صفر دهه‌ها است که وجود داشته‌اند: معرفی آن‌ها توسط شفی گلدواسر، سیلویو میکالی و چارلز راکف در سال 1985 تأثیری دگرگون‌کننده بر حوزه رمزنگاری داشت و توسط جایزه ACM Turing که به گلدواسر و میکالی در سال XNUMX اهدا شد، شناخته شد. 2012. از آنجایی که این کار - از جمله حرکت آن از تئوری به عمل و کاربردهای آن در کریپتو/وب 3 امروزی - ده ها سال در حال ساخت است، ما همچنین برای اولین بار در سری Canon خود قسمت دوم را به اشتراک می گذاریم (در حال حاضر، در اینجا در زیر آمده است): یک لیست خواندنی که توسط جاستین تالر، در ادامه قسمت اول زیر.

تشکر و قدردانی: همچنین از مایکل بلاو، سم راگزدیل و تیم راگگاردن تشکر می کنم.

مبانی، پیشینه، تحولات

برخی از این مقالات همچنین بیشتر در مورد رمزنگاری به طور کلی هستند (نه همه دانش صفر فی نفسه)، از جمله تشریح مشکلات یا پیشرفت‌های کلیدی که امروزه با مدرک‌های دانش صفر مورد بررسی قرار می‌گیرند: چگونگی اطمینان از حفظ حریم خصوصی و احراز هویت در شبکه‌های باز.

مسیرهای جدید در رمزنگاری (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 (کالج دانشگاهی لندن، گوگل) به برنامه‌هایی که توسعه آن‌ها را هدایت می‌کنند، مدل‌های مختلفی که برای به تصویر کشیدن این تعاملات جدید پدید آمده‌اند، ساختارهایی که می‌توانیم به آن دست پیدا کنیم و کار نگاه می‌کند. باقی مانده برای انجام.
توسط سارا میکلجون
https://www.youtube.com/watch?v=HO97kVMI3SE

جلسات تخته سفید ZK - ماژول های مقدماتی
با Dan Boneh و همکاران
https://zkhack.dev/whiteboard/

امنیت و حریم خصوصی برای رمزارز با zkps - پیشگام اثبات دانش صفر در عمل؛ zkps چیست و چگونه کار می کند ... از جمله "دمو" استیج زنده
توسط Zooko Wilcox
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 در بنیاد اتریوم
با مری مالر، آنا رز، کوبی گورکان
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 - بخش I، II، III
توسط ویتالیک بوترین
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

آناتومی یک استارک - یک آموزش شش قسمتی که مکانیک سیستم اثبات STARK را توضیح می دهد
توسط Alan Szepieniec
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

از AIR تا RAP - نحوه عملکرد محاسبات به سبک PLONK
توسط آریل گابیزون
https://hackmd.io/@aztec-network/plonk-arithmetiization-air

Multiset را در 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/

انواع مختلف zkEVM
توسط ویتالیک بوترین
https://vitalik.ca/general/2022/08/04/zkevm.html

یادگیری ماشینی ZK - آموزش و دمو برای قرار دادن شبکه عصبی در SNARK
توسط هوراس پان، فرانسیس هو و هنری پالاکی
https://0xparc.org/blog/zk-mnist

در زبان های ZK
با الکس اوزدمیر و آنا رز
https://zeroknowledge.fm/172-2/

جنگل تاریک - استفاده از رمزنگاری zk در بازی ها - یک بازی کاملاً غیر متمرکز و پایدار RTS (استراتژی زمان واقعی).
https://blog.zkga.me/announcing-darkforest

ZKP برای مهندسان - نگاهی به ZKP های جنگل تاریک
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/

پادکست Zero Knowledge - در مورد جدیدترین تحقیقات zk و برنامه‌های کاربردی zk و متخصصان در ساخت فناوری حفظ حریم خصوصی با قابلیت رمزنگاری
با آنا رز
https://zeroknowledge.fm/

... فهرست خواندن مشروح، بر اساس موضوع و زمان بندی، توسط جاستین تالر:

SNARK از PCP های خطی (معروف به SNARK با تنظیمات مدار خاص)

آرگومان های کارآمد بدون PCP های کوتاه (2007)
توسط یووال ایشای، ایال کوشیلویتز، و رافائل اوستروفسکی

قبل از حدود سال 2007، SNARK ها عمدتاً از طریق طراحی شده بودند کیلیان-میکالی پارادایم، گرفتن یک اثبات احتمالی «کوتاه» (PCP) و «کامپایل رمزنگاری» آن به یک استدلال موجز از طریق هش کردن مرکل و تبدیل فیات-شمیر. متأسفانه PCP های کوتاه حتی امروزه نیز پیچیده و غیرعملی هستند. این مقاله (IKO) نشان داد که چگونه می توان از رمزگذاری همومورفیک برای به دست آوردن آرگومان های تعاملی مختصر (غیر شفاف) از PCP های "طولانی اما ساختاریافته" استفاده کرد. اینها می توانند بسیار ساده تر از PCP های کوتاه باشند، و SNARK های به دست آمده دارای اثبات بسیار کوتاه تر و تأیید سریعتر هستند. این استدلال ها ابتدا به عنوان دارای پتانسیل برای کارایی عملی شناخته شدند و در آن پالایش و اجرا شدند فلفل. متأسفانه، آرگومان های IKO دارای یک اثبات کننده زمان درجه دوم و رشته مرجع ساختار یافته با اندازه درجه دوم هستند، بنابراین آنها به محاسبات بزرگ مقیاس نمی شوند.

برنامه های درجه دوم و NIZK های مختصر بدون PCP (2012)
توسط روزاریو جنارو، کریگ جنتری، برایان پارنو و ماریانا رایکوا

این مقاله پیشرفت (GGPR) هزینه های اثباتی رویکرد IKO را از درجه دوم در اندازه مدار به شبه خطی کاهش داد. بر اساس کارهای قبلی از گروت و لیپما، همچنین SNARK ها را از طریق رمزنگاری مبتنی بر جفت، به جای آرگومان های تعاملی مانند IKO ارائه می دهد. SNARK های خود را در زمینه آنچه که اکنون به عنوان مسائل رضایت از محدودیت رتبه-1 (R1CS) نامیده می شود، که تعمیم رضایت پذیری مدار حسابی است، توصیف کرد.

این مقاله همچنین به عنوان شالوده نظری اولین SNARK هایی بود که شاهد استقرار تجاری (مثلاً در ZCash) بودند و مستقیماً به SNARK هایی منجر شد که امروزه محبوب هستند (مثلاً Groth16). پیاده سازی های اولیه آرگومان های GGPR وارد شدند زاتار و پینوکیو، و انواع بعدی شامل SNARK برای C و BCTV. BCIOP یک چارچوب کلی ارائه می دهد که این تبدیل های خطی PCPs به SNARK را توضیح می دهد (همچنین به پیوست A مراجعه کنید زاتار) و نمونه های مختلفی از آن را شرح می دهد.

در مورد اندازه آرگومان های غیر تعاملی مبتنی بر جفت شدن (2016)
توسط ینس گروت

این مقاله که به صورت محاوره ای به عنوان Groth16 نامیده می شود، اصلاحاتی از SNARK های GGPR را ارائه می دهد که حتی امروزه نیز هزینه های تأیید بتن پیشرفته را به دست می آورد (اثبات سه عنصر گروهی هستند، و تأیید با سه عملیات جفت سازی، حداقل با فرض عمومی، غالب است. ورودی کوتاه است). امنیت در مدل گروه عمومی ثابت شده است.

SNARK با راه‌اندازی قابل اعتماد جهانی

PlonK: جایگشت بر مبنای لاگرانژ برای استدلال‌های غیرتعاملی دانش (2019)
توسط آریل گابیزون، زکاری ویلیامسون و اوانا چیوبوتارو

مارلین: پیش پردازش zkSNARK با SRS جهانی و قابل به روز رسانی (2019)
توسط الساندرو کیزا، یونکونگ هو، مری مالر، پراتیوش میشا، پسی وزلی و نیکلاس وارد

هم PlonK و هم Marlin، راه‌اندازی مطمئن مدار خاص را در Groth16 با یک راه‌اندازی جهانی جایگزین می‌کنند. این به قیمت 4 تا 6 برابر اثبات بزرگتر تمام می شود. می توان PlonK و Marlin را در حین راه اندازی قابل اعتماد در Groth16 و پیشینیان و انتقال آن به مرحله پیش پردازش که اتفاق می افتد در نظر گرفت. بعد از راه اندازی قابل اعتماد، و همچنین در طول تولید اثبات SNARK.

توانایی پردازش مدارهای دلخواه و سیستم های R1CS به این روش گاهی اوقات هولوگرافی یا تعهدات محاسباتی نامیده می شود و همچنین در اسپارتی (که بعداً در این مجموعه بحث می شود). از آنجایی که کار بیشتری در طول تولید اثبات اتفاق می‌افتد، پروورهای PlonK و Marlin برای یک مدار معین یا نمونه R16CS کندتر از Groth1 هستند. با این حال، بر خلاف Groth16، PlonK و Marlin می‌توانند با نمایش‌های متوسط ​​عمومی‌تری نسبت به R1CS کار کنند.

طرح‌های تعهد چندجمله‌ای، یک رمزگذاری اولیه کلیدی در SNARK‌ها

تعهدات با اندازه ثابت به چند جمله ای ها و کاربردهای آنها (2010)
توسط آنیکت کیت، گریگوری زاوروچا و ایان گلدبرگ

این مقاله مفهوم طرح های تعهد چند جمله ای را معرفی می کند. این طرحی برای چند جمله ای های تک متغیره (که معمولاً تعهدات KZG نامیده می شود) با تعهدات با اندازه ثابت و اثبات ارزیابی ارائه داد. این طرح از یک راه اندازی قابل اعتماد (به عنوان مثال، رشته مرجع ساختاریافته) و رمزنگاری مبتنی بر جفت استفاده می کند. امروزه در عمل بسیار محبوب است و در SNARK ها از جمله PlonK و Marlin مورد استفاده قرار می گیرد (و Groth16 از تکنیک های رمزنگاری بسیار مشابه استفاده می کند).

Fast Reed-Solomon Interactive Oracle Proofs of Proximity (2017)
توسط الی بن ساسون، آیدو بنتوف، ینون هورش، مایکل ریابزف

یک اثبات اوراکل تعاملی (IOP) را برای آزمایش رید-سولومون ارائه می‌کند - یعنی ثابت می‌کند که یک رشته متعهد به جدول ارزیابی یک چند جمله‌ای تک متغیره نزدیک است. همراه با Merkle-Hashing و تبدیل Fiat-Shamir، این یک طرح تعهد چند جمله ای شفاف با اثبات های ارزیابی اندازه چند لگاریتمی به دست می دهد (نگاه کنید به VP19 برای جزئیات). امروزه، این کوتاه‌ترین در میان طرح‌های تعهد چند جمله‌ای پس کوانتومی است.

Ligero: آرگومان های زیرخطی سبک وزن بدون تنظیم قابل اعتماد (2017)
توسط اسکات ایمز، کارمیت هازی، یووال ایشای و موتوراماکریشنان ونکیتاسوبرامانیام

مشابه FRI، این کار یک IOP برای آزمایش Reed-Solomon می دهد، اما با طول اثبات ریشه مربع به جای چند لگاریتمی. نظری با این نسخهها کار نشان داد که با تعویض کد Reed-Solomon با کد تصحیح خطای متفاوت با رمزگذاری سریع‌تر، می‌توان یک اثبات‌کننده زمان خطی به دست آورد که به‌علاوه به‌طور بومی در هر زمینه‌ای کار می‌کند. این رویکرد اصلاح و اجرا شده است ترمز کردن و شکارچی ماهر، عملکرد پیشرفته ای را ارائه می دهد.

ضد گلوله: شواهد کوتاه برای معاملات محرمانه و موارد دیگر (2017)
توسط بندیکت بونز، جاناتان بوتل، دن بونه، اندرو پولسترا، پیتر ویل و گرگ ماکسول

پالایش کار قبلی توسط BCGP، Bulletproofs یک طرح تعهد چند جمله ای شفاف (در واقع یک تعمیم به نام آرگومان محصول درونی) بر اساس سختی محاسبه لگاریتم های گسسته با اندازه اثبات لگاریتمی اما زمان تایید کننده خطی ارائه می دهد. این طرح به دلیل شفافیت و اثبات کوتاه آن امروزه محبوب باقی مانده است (مثلاً در ZCash Orchard و Monero استفاده می شود).

Dory: استدلال های کارآمد و شفاف برای محصولات درونی تعمیم یافته و تعهدات چند جمله ای (2020)
توسط جاناتان لی

Dory زمان تأییدکننده در ضدگلوله‌ها را از خطی به لگاریتمی کاهش می‌دهد، در حالی که شفافیت و اثبات‌های اندازه لگاریتمی (البته بزرگ‌تر از ضدگلوله‌ها) و شفافیت را حفظ می‌کند. از جفت ها استفاده می کند و بر اساس فرض SXDH است.

اثبات های تعاملی، اثبات های تعاملی چند اثبات کننده، و SNARK های مرتبط

تفویض محاسبات: اثبات های تعاملی برای ماگل ها (2008)
توسط شفی گلدواسر، یائل تاومن کالای و گای راثبلوم

قبل از این مقاله، اثبات های تعاملی همه منظوره مورد نیاز است زمان ابرچند جمله ای اثبات کننده این مقاله یک پروتکل اثبات تعاملی، که معمولاً پروتکل GKR نامیده می‌شود، با یک اثبات‌کننده زمان چند جمله‌ای و تأییدکننده زمان شبه خطی، برای هر مشکلی که دارای یک الگوریتم موازی کارآمد است ارائه می‌دهد (به طور معادل، اثبات تعاملی برای هر مدار حسابی با عمق کم اعمال می‌شود).

محاسبات تأیید شده عملی با اثبات های تعاملی جریانی (2011)
توسط گراهام کورمود، مایکل میزنماخر، جاستین تالر

این مقاله (گاهی اوقات CMT نامیده می شود) زمان اثبات را در پروتکل GKR از کوارتیک در اندازه مدار به شبه خطی کاهش داد. اولین اجرای یک اثبات تعاملی همه منظوره را تولید کرد. خطی از کارهای بعدی (آردپس, تالر13, زرافهو برج میزان) زمان اجرای پروور را بیشتر کاهش داد، از شبه خطی به خطی در اندازه مدار.

vSQL: تأیید پرس و جوهای SQL دلخواه از طریق پایگاه های داده برون سپاری پویا (2017)
توسط Yupeng Zhang، Daniel Genkin، Jonathan Katz، Dimitrios Papadopoulos و Charalampos Papamanthou

اگرچه عنوان به یک حوزه کاربردی خاص (پایگاه های داده) اشاره دارد، مشارکت های این مقاله کلی تر است. به طور خاص، مشاهده شد که می‌توان با ترکیب اثبات‌های تعاملی با طرح‌های تعهد چند جمله‌ای (برای چند جمله‌ای چند خطی) استدلال‌های موجز برای ارضای مدار به دست آورد.

پس از آن با این نسخهها کار ارائه شده آرگومان‌های دانش صفر و طرح‌های تعهد متفاوتی را برای چندجمله‌ای‌های چند خطی معرفی کردند.

Spartan: zkSNARK های کارآمد و همه منظوره بدون راه اندازی قابل اعتماد (2019)
توسط Srinath Setty

SNARK ها را برای رضایت مداری و R1CS با ترکیب اثبات های تعاملی چند اثبات کننده (MIPs) با طرح های تعهد چند جمله ای، بر اساس کار قبلی بر روی MIP های کارآمد مشخص به دست می آورد. شبدر. اثر این است که SNARK هایی با اثبات های کوتاه تر به دست می آیند که از اثبات های تعاملی مانند پروتکل GKR که در بالا بحث شد، به دست می آیند. مشابه PlonK و Marlin، Spartan همچنین نحوه پردازش مدارهای دلخواه و سیستم های R1CS را از طریق پیش پردازش و تولید اثبات SNARK نشان می دهد.

اسپارتان از طرح تعهد چند جمله ای استفاده کرد هیراکس. آثار بعدی به نام ترمز کردن و شکارچی ماهر MIP اسپارتان را با سایر طرح‌های تعهد چند جمله‌ای ترکیب کنید تا اولین SNARK‌های پیاده‌سازی شده را با یک اثبات‌کننده زمان خطی به دست آورید.

PCP و IOP کوتاه

PCP های کوتاه با پیچیدگی پرس و جو Polylog (2005)
توسط الی بن ساسون و مادو سودان

 این کار نظری اولین اثبات احتمالی قابل بررسی (PCP) را با طول اثبات شبه خطی در اندازه محاسبات و هزینه پرس و جو چند لگاریتمی (هرچند زمان تأییدکننده خطی) ارائه داد. پس از تبدیل کیلیان-میکالی PCP ها به SNARK، این گامی به سوی SNARK ها با اثبات کننده زمان شبه خطی و تأیید کننده زمان چند لگاریتمی بود.

کارهای نظری بعد زمان تایید کننده را به چند لگاریتمی کاهش داد. متعاقب کار متمرکز بر عملی این رویکرد را اصلاح کرد، اما PCP های کوتاه امروزه غیرعملی باقی مانده اند. برای به دست آوردن SNARK های عملی، بعد با این نسخهها کار تبدیل به تعمیم تعاملی PCP ها نامیده می شود مدارک تعاملی اوراکل (IOPs). این تلاش ها منجر شد و بر آن افزوده شد رایگان، یک طرح تعهد چند جمله ای محبوب که در بخش تعهدات چند جمله ای این مجموعه بحث شده است.

از دیگر آثار این دسته می توان به ZKBoo و فرزندان آن اینها به دلایل موجز دست نمی یابند، اما عوامل ثابت خوبی دارند و از این رو برای اثبات گزاره های کوچک جذاب هستند. آنها به خانواده هایی از امضاهای پس کوانتومی مانند پیک نیک که بوده بهینه in چند با این نسخهها کار. ZKBoo به عنوان یک الگوی طراحی متمایز به نام ارائه شده است MPC-in-the-head، اما یک IOP ایجاد می کند.

SNARK های بازگشتی

محاسبات با قابلیت تأیید افزایشی یا اثبات دانش دلالت بر کارایی زمان/مکان دارد (2008)
توسط پل والیانت

این کار مفهوم بنیادی محاسبات قابل تأیید افزایشی (IVC) را معرفی کرد، که در آن Prover یک محاسبات را اجرا می‌کند و همیشه ثابت می‌کند که محاسبات تاکنون درست بوده است. IVC را از طریق ترکیب بازگشتی SNARK ها ساخت. اینجا دانش - سلامت ویژگی SNARK ها برای ایجاد درستی آرگومان های غیر تعاملی با ترکیب بازگشتی ضروری است. این مقاله همچنین یک استخراج کننده دانش بسیار کارآمد برای SNARK های مشتق شده از PCP (طبق پارادایم Kilian-Micali) ارائه کرد.

دانش صفر مقیاس پذیر از طریق چرخه منحنی های بیضوی (2014)
توسط الی بن ساسون، الساندرو کیزا، اران ترومر و مدرس ویرزا

ذیل کار نظری، این مقاله از کاربرد بازگشتی یک نوع SNARK GGPR برای ارائه اولین پیاده سازی IVC برای یک ماشین مجازی ساده (TinyRAM، از SNARK برای C کاغذ).

همچنین مفهوم چرخه‌های منحنی‌های بیضوی را معرفی کرد که برای ترکیب SNARK‌های بازگشتی که از رمزنگاری منحنی بیضوی استفاده می‌کنند، مفید هستند.

ترکیب اثبات بازگشتی بدون تنظیم قابل اعتماد (2019)
توسط شان بوو، جک گریگ و دایرا هاپوود

این اثر (به نام Halo) چگونگی ترکیب SNARK های شفاف را به صورت بازگشتی مطالعه می کند. این چالش‌برانگیزتر از نوشتن موارد غیرشفاف است، زیرا روش تأیید در SNARK‌های شفاف می‌تواند بسیار گران‌تر باشد.

این سپس جرقه ای زد خط of کار که در سیستم هایی مانند نو اختر دستیابی به عملکرد پیشرفته IVC، حتی از عملکردی که با ترکیب SNARK های غیر شفاف مانند Groth16 به دست می آید، برتر است.

اپلیکیشن‌ها

Zerocash: پرداخت های غیرمتمرکز ناشناس از بیت کوین (2014)
توسط الی بن ساسون، الساندرو کیزا، کریستینا گارمن، متیو گرین، ایان میرز، اران ترومر، مادارس ویرزا

بر اساس کارهای قبلی از جمله زیروکین (و با سکه پینوکیو به عنوان کار همزمان)، این مقاله از SNARK های مشتق شده از GGPR برای طراحی یک ارز دیجیتال خصوصی استفاده می کند. منجر به ZCash شد.

Geppetto: محاسبات قابل تأیید همه کاره (2014)
توسط کریگ کاستلو، سدریک فورن، جان هاول، مارکولف کوهلویس، بنجامین کروتر، مایکل ناهریگ، برایان پارنو و سامی زاهور

Geppetto احتمالاً قبل از انفجار علاقه به اجرای قراردادهای هوشمند خصوصی است که تقریباً یک سال پس از ایجاد اتریوم نوشته شده است. از این رو، در زمینه اجرای قراردادهای هوشمند خصوصی ارائه نشده است. با این حال، از بازگشت با عمق محدود SNARK ها استفاده می کند تا به یک پروور غیرقابل اعتماد اجازه دهد تا هر برنامه کامپیوتری خصوصی (متعهد/امضا شده) را روی داده های خصوصی اجرا کند، بدون اینکه اطلاعاتی در مورد برنامه در حال اجرا یا داده هایی که روی آن اجرا می شود را فاش کند. بر این اساس، این یک سلف کار بر روی پلتفرم های قرارداد هوشمند خصوصی است، مانند Zexe [توضیح داده شده در زیر].

ASIC های قابل تأیید (2015)
توسط ریاد وهبی، مکس هاوالد، سیدارت گارگ، آبی شلات، مایکل والفیش

این مقاله مشکل چگونگی استفاده ایمن و مثمر ثمر از ASIC تولید شده در یک ریخته گری غیرقابل اعتماد را در نظر می گیرد (در سال 2015، تنها پنج کشور با ریخته گری های سطح بالا وجود داشتند). رویکرد این است که ASIC سریع اما نامطمئن صحت خروجی خود را به تأیید کننده ای که روی یک ASIC کندتر اما قابل اعتماد اجرا می شود ثابت کند. راه حل جالب است تا زمانی که کل زمان اجرای سیستم (یعنی مجموع زمان اجراهای اثبات کننده و تأیید کننده به اضافه هر گونه هزینه انتقال داده) کمتر از خط پایه ساده باشد: زمان مورد نیاز برای اجرای کامل محاسبات با سرعت کمتر. ASIC -اما قابل اعتماد. این مقاله با استفاده از گونه‌ای از اثبات‌های تعاملی GKR/CMT/Allspice، در واقع خط پایه ساده‌ای را برای تعدادی از مشکلات اساسی، از جمله تبدیل‌های نظری اعداد، تطبیق الگو، و عملیات منحنی بیضوی شکست می‌دهد. این کار نشان می‌دهد که برخی از سیستم‌های اثبات برای اجرای سخت‌افزار مناسب‌تر از سایرین هستند. بهینه سازی سیستم های اثبات برای پیاده سازی سخت افزار در حال حاضر دریافت می شود قابل توجه توجه، اما هنوز چیزهای زیادی برای بررسی باقی مانده است.

قابل تایید توابع تاخیر (2018)
توسط Dan Boneh، Joseph Bonneau، Benedikt Bünz و Ben Fisch

نماد توابع تأخیر قابل تأیید (VDF) را معرفی کرد، یک رمزنگاری اولیه که به طور گسترده در برنامه های بلاک چین مفید است، به عنوان مثال، در کاهش دستکاری احتمالی پروتکل های اجماع اثبات سهام. SNARK ها (مخصوصاً برای محاسبات با تأیید افزایشی) مسیری را به VDF های پیشرفته ارائه می دهند.

Zexe: فعال کردن محاسبات خصوصی غیرمتمرکز (2018)
توسط شان بوو، الساندرو کیزا، متیو گرین، ایان میرز، پراتیوش میشا و هوارد وو

Zexe یک طراحی برای یک پلت فرم قرارداد هوشمند خصوصی است. می‌توان Zexe را به‌عنوان پسوند Zerocash (که در بالا توضیح داده شد) مشاهده کرد. Zerocash همزمان با محافظت از حریم خصوصی داده‌های کاربر، یک برنامه واحد را قادر می‌سازد تا روی زنجیره اجرا شود (به کاربران امکان می‌دهد تا توکن‌ها را منتقل کنند) به عنوان مثال، به چه کسی توکن‌ها را ارسال می‌کنند، توکن‌ها را از آنها دریافت می‌کنند، میزان توکن‌های منتقل شده، و غیره. برنامه های مختلف (قراردادهای هوشمند) برای اجرا در یک بلاک چین و تعامل با یکدیگر. تراکنش‌ها خارج از زنجیره انجام می‌شوند و شواهد اجرای صحیح در زنجیره ارسال می‌شوند. نه تنها حریم خصوصی داده ها محافظت می شود، بلکه از حریم خصوصی عملکرد نیز محافظت می شود. این بدان معناست که اثبات مرتبط با هر تراکنش حتی نشان نمی‌دهد که تراکنش مربوط به کدام برنامه (ها) است. مشارکت مهندسی کلی‌تر Zexe این است که BLS12-377 را معرفی کرد، یک گروه منحنی بیضوی که برای ترکیب عمقی کارآمد SNARK‌های مبتنی بر جفت‌سازی مفید است.

ماشین های حالت تکراری بدون اجرای تکراری (2020)
توسط جاناتان لی، کریل نیکیتین و سرینات ستی

این یکی از معدود مقالات آکادمیک در مورد جمع‌بندی برای مقیاس‌پذیری بلاک چین است. از اصطلاح rollups استفاده نمی کند، زیرا این مفهوم پیش از تاریخ یا همزمان با این مفهوم است که خارج از ادبیات دانشگاهی معرفی شده است.

فرانت‌اندها (تبدیل‌های کارآمد از برنامه‌های کامپیوتری به نمایش‌های میانی مانند رضایت مدار، R1CS و موارد دیگر)

کاهش سریع از RAM به مشکلات رضایت مختصر مختصر قابل واگذاری (2012)
توسط الی بن ساسون، الساندرو کیزا، دنیل جنکین و اران ترومر

از دیدگاه مدرن، این یک کار اولیه در مورد تبدیل‌های عملی کامپیوتر-برنامه-به-مدار-SAT برای انتزاع ماشین مجازی (VM) است. با تکیه بر آثار اواخر دهه 1970 تا 1990 (به عنوان مثال، کارهای رابسون) این مقاله کاهش قطعی از اجرای یک VM برای مراحل T تا رضایت مداری با اندازه O(T*polylog(T)) را بیان می کند.

مقالات بعدی، به عنوان مثال، SNARK برای C و BCTV، به توسعه فرانت‌اندها از طریق انتزاع VM ادامه داد و نمونه‌های مدرن شامل پروژه‌هایی مانند قاهره, RISC صفرو چند ضلعی میدن.

انجام محاسبات تایید شده مبتنی بر اثبات چند قدم به عملی بودن نزدیکتر است (2012)
توسط Srinath Setty، Victor Vu، Nikhil Panpalia، Benjamin Braun، Muqeet Ali، Andrew J. Blumberg و Michael Walfish

این مقاله، که به عنوان زنجبیل شناخته می شود، یکی دیگر از کمک های اولیه به تکنیک های کاربردی جلویی است. جینجر ابزارهایی را برای برنامه نویسی اولیه اولیه مانند شرطی ها و عبارات منطقی، مقایسه ها و محاسبات بیتی از طریق تقسیم بیت، محاسبات ممیز شناور اولیه و غیره معرفی کرد. از این گجت ها برای ارائه اولین front-end پیاده سازی شده از زبان سطح بالا به درجه پایین استفاده کرد. محدودیت‌های حسابی (شبیه به آنچه که اکنون به عنوان R1CS شناخته می‌شود)، یک نمایش میانی (IR) که می‌توان یک بک‌اند SNARK برای آن اعمال کرد.

در حالی که مقاله «کاهش سریع» و نسل‌های آن از رویکرد «شبیه‌ساز CPU» در تولید IR استفاده می‌کنند (یعنی IR با اعمال تابع انتقال CPU برای تعداد معینی از مراحل، اجرای صحیح برنامه خاصی را توسط پروور اجرا می‌کند). جینجر و نوادگانش رویکردی شبیه به ASIC دارند و IRهایی را تولید می‌کنند که برای برنامه رایانه‌ای که پروور مدعی اجرای صحیح آن است، طراحی شده است.

به عنوان مثال، بوفه نشان می‌دهد که می‌توان جریان کنترل پیچیده را در مدل ASIC، با تبدیل چنین جریان کنترلی به یک ماشین حالت محدود متناسب با برنامه در حال اجرا، مدیریت کرد و این رویکرد می‌تواند به طور قابل‌توجهی کارآمدتر از ساخت یک شبیه‌ساز CPU همه منظوره باشد. xJsnark ساختاری کارآمد برای محاسبات با دقت چندگانه، بهینه سازی برای رم ها و رام ها، و یک زبان سطح بالا شبیه جاوا را در معرض دید یک برنامه نویس قرار می دهد، که امروزه نیز محبوب است. CirC مشاهده می کند که کامپایل برنامه های کامپیوتری به R1CS ارتباط نزدیکی با تکنیک های شناخته شده از تجزیه و تحلیل برنامه دارد و یک جعبه ابزار ساخت کامپایلر را ایجاد می کند که ایده های هر دو جامعه را در بر می گیرد ("LLVM برای نمایش های مدار مانند"). کارهای قبلی که به سبک ASIC کمک می‌کردند عبارتند از پینوکیو و ژپتو.

مقاله "کاهش سریع" از ساختار پیچیده و گران قیمتی به نام "شبکه های مسیریابی" برای به اصطلاح استفاده کرد. بررسی حافظه (یعنی اطمینان از اینکه اثبات کننده نامعتبر حافظه دسترسی تصادفی ماشین مجازی را در طول اجرای VM که درستی آن در حال اثبات است به درستی حفظ می کند). این انتخاب به این دلیل انجام شد که کارهای اولیه مانند این مورد به دنبال به دست آوردن PCP بودند، که نیاز به جلویی داشت. هر دو غیر تعاملی و از لحاظ نظری اطلاعات امن است. بعداً کار نامیده شد آبدارخانه (یک سلف از بوفه کار ذکر شده در بالا) از درختان Merkle به جای شبکه های مسیریابی استفاده کرد که با کامپایل یک تابع هش جبری (به عنوان مثال، "SNARK-friendly") کارایی را به دست آورد. آجتایی، به محدودیت ها. این منجر به صفحه‌های جلویی «ایمن محاسباتی» شد. امروزه، ادبیات تحقیقاتی زیادی در مورد توابع هش پسند SNARK وجود دارد که شامل مثال‌هایی نیز می‌شود خدای دریا, MiMC, بتن آرمه, نجات، و بیشتر.

تکنیک‌های پیشرفته برای حصول اطمینان از اینکه پروور رم را به‌درستی حفظ می‌کند، بر روش‌های به اصطلاح «اثر انگشت جایگشت ثابت» تکیه می‌کنند که قدمت آن حداقل به لیپتون (1989) و برای بررسی حافظه توسط بلوم و همکاران (1991). این تکنیک‌ها ذاتاً شامل تعامل بین اثبات‌کننده و تأییدکننده هستند، اما می‌توانند با تبدیل فیات-شمیر غیرتعاملی شوند. تا آنجا که ما اطلاع داریم، آنها توسط سیستمی به نام SNARK با ادبیات ظاهری کاربردی SNARK آشنا شدند vRAM.

تکنیک‌های انگشت نگاری تغییرناپذیر در حال حاضر در بسیاری از بخش‌های جلویی و SNARK برای انتزاع‌های ماشین مجازی، از جمله برای مثال، استفاده می‌شوند. قاهره. ایده های نزدیک به هم در زمینه های مرتبط دوباره در دو اثر زیر ظاهر شدند که امروزه به طور گسترده در عمل مورد استفاده قرار می گیرند.

شواهد دانش زمان تقریبا خطی برای اجرای صحیح برنامه (2018)
توسط جاناتان بوتل، آندریا سرولی، ینس گروت، سونه یاکوبسن و مری مالر

Plookup: یک پروتکل چند جمله ای ساده شده برای جداول جستجو (2020)
توسط آریل گابیزون و زکری ویلیامسون

کارهای اولیه روی قسمت‌های جلویی، عملیات‌های «غیر حسابی» (مانند بررسی محدوده، عملیات بیتی و مقایسه اعداد صحیح) را در داخل مدارها و IRهای مرتبط با شکستن عناصر میدان به بیت‌ها، انجام عملیات روی این بیت‌ها و سپس «بسته‌بندی» نشان می‌دادند. نتیجه به یک عنصر فیلد برمی گردد. از نظر اندازه مدار حاصل، این منجر به سربار لگاریتمی در هر عملیات می شود.

دو کار فوق (BCGJM و Plookup) تکنیک‌های تأثیرگذاری (بر اساس به اصطلاح «جدول جستجو») را برای نمایش کارآمدتر این عملیات در داخل مدارها، به معنای مستهلک شده ارائه می‌دهند. به طور کلی، برای برخی از پارامترهای B که توسط طراح جلویی انتخاب شده است، این پارامترها تعداد گیت های مورد نیاز برای نمایش هر عملیات غیر حسابی در مدار را با یک ضریب لگاریتمی در B کاهش می دهند و این به قیمت متعهد شدن رمزنگاری توسط پروور به یک عامل اضافی است. بردار "مشاوره" با طول تقریبا B.