Канон с нулевым разглашением

Примечание редактора: У криптовалюты a16z была длинная серия «пистолеты", от нашего ДАО Канон в прошлом году к нам NFT-канон ранее (и до этого наш оригинальный Крипто Канон) — обязательно подписывайтесь на нашу еженедельный информационный бюллетень web3 для получения дополнительных обновлений, а также других кураторских ресурсов.

Так что бниже, мы отобрали набор ресурсов для тех, кто хочет понять, углубиться и построить все, что угодно. нулевые знания: мощные, основополагающие технологии, которые содержат ключи к масштабируемости блокчейна и представляют собой будущее приложений, сохраняющих конфиденциальность, и бесчисленных других будущих инноваций. Если у вас есть предложения по добавлению высококачественных материалов, сообщите нам об этом @a16zcrypto.

Системы доказательства с нулевым разглашением существуют уже несколько десятилетий: их внедрение Шафи Голдвассером, Сильвио Микали и Чарльзом Ракоффом в 1985 году оказало преобразующее воздействие на область криптографии и было признано премией Тьюринга ACM, присужденной Голдвассеру и Микали в 2012. Поскольку эта работа, в том числе ее переход от теории к практике и приложениям в крипто/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

От извлекаемой устойчивости к коллизиям до кратких неинтерактивных аргументов знаний [SNARK] и обратно (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

Эволюция моделей доказательств с нулевым разглашением — Обзор доказательств с нулевым разглашением, в котором Мейкледжон (Университетский колледж Лондона, 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/

Введение в zkSNARK
с Ховардом Ву, Анной Роуз
https://zeroknowledge.fm/38-2/

Почему и как работает zk-SNARK: исчерпывающее объяснение
Максим Петкус
https://arxiv.org/pdf/1906.07221.pdf

Введение в доказательства с нулевым разглашением
Фредрик Харриссон и Анна Роуз
https://www.zeroknowledge.fm/21 [+ сводная запись в другом месте здесь]

Zk-SNARK: под капотом
Виталик Бутерин
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 Foundation
с Мэри Маллер, Анной Роуз, Коби Гуркан
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

СТАРКи — части 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.
Алан Шепенец
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

Мультисетовые проверки в PLONK и Plookup
Ариэль Габизон
https://hackmd.io/@arielg/ByFgSDA7D

Halo2 дизайн - из ЭКЦ
https://zcash.github.io/halo2/design.html

Плонки2
https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Приложения и учебные пособия: проверка концепций, демонстрации, инструменты и многое другое

Прикладной зк - образовательные ресурсы
по 0xPARC
https://learn.0xparc.org/materials/intro

Онлайн-среда разработки для zkSNARK - zkREPL, новый набор инструментов для взаимодействия со стеком инструментов Circom в браузере.
Кевин Квок
https://zkrepl.dev (+ пояснительная ветка здесь)

Квадратичные арифметические программы от нуля до героя
Виталик Бутерин
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

На zkEVM
с Алексом Глуховски и Анной Роуз
https://zeroknowledge.fm/175-2/

Различные типы zkEVM
Виталик Бутерин
https://vitalik.ca/general/2022/08/04/zkevm.html

ЗК машинное обучение - учебник и демонстрация для помещения нейронной сети в SNARK
Гораций Пэн, Фрэнсис Хо и Анри Палаччи
https://0xparc.org/blog/zk-mnist

На ЗК языках
с Алексом Оздемиром и Анной Роуз
https://zeroknowledge.fm/172-2/

Dark Forest — применение криптографии zk к играм — полностью децентрализованная и постоянная игра RTS (стратегия в реальном времени)
https://blog.zkga.me/announcing-darkforest

ЗКП для инженеров — взгляд на ЗКП Темного Леса
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/

… аннотированный список для чтения по темам и в хронологическом порядке, составленный Джастином Талером:

SNARK от Linear PCP (также известные как SNARK с настройкой для конкретной схемы)

Эффективные аргументы без коротких PCP (2007)
Юваль Ишай, Эяль Кушилевич, Рафаил Островский

Примерно до 2007 года SNARK в основном разрабатывались с помощью Kilian–Микали Парадигма, состоящая в том, чтобы взять «короткое» вероятностно проверяемое доказательство (PCP) и «криптографически скомпилировать» его в краткий аргумент с помощью хеширования Меркла и преобразования Фиата-Шамира. К сожалению, короткие PCP сложны и непрактичны даже сегодня. В этой статье (IKO) показано, как использовать гомоморфное шифрование для получения кратких (непрозрачных) интерактивных аргументов из «длинных, но структурированных» PCP. Они могут быть намного проще, чем короткие PCP, а полученные SNARK имеют гораздо более короткие доказательства и более быструю проверку. Эти аргументы были впервые признаны имеющими потенциал практической эффективности, а затем усовершенствованы и реализованы в перец. К сожалению, аргументы IKO имеют доказательство квадратичного времени и структурированную опорную строку квадратичного размера, поэтому они не масштабируются для больших вычислений.

Квадратичные пролетные программы и краткие НИЗК без ПКП (2012)
Розарио Дженнаро, Крейг Джентри, Брайан Парно и Мариана Райкова

Эта прорывная статья (GGPR) снизила затраты на проверку подхода IKO с квадратичных по размеру схемы до квазилинейных. Опираясь на более раннюю работу Грот и Липмаа, он также выдавал SNARK с помощью криптографии на основе пар, а не интерактивных аргументов, как в IKO. Он описал свои SNARK в контексте того, что теперь называется проблемами удовлетворения ограничений ранга 1 (R1CS), обобщением арифметической выполнимости схемы.

Этот документ также послужил теоретической основой для первых SNARK, которые увидели коммерческое развертывание (например, в ZCash), и непосредственно привел к SNARK, которые остаются популярными сегодня (например, Groth16). Первоначальные реализации аргументов GGPR появились Zaatar и Пиноккио, а более поздние варианты включают SNARK для C и BCTV. БКИОП дал общую основу, объясняющую эти преобразования линейных PCP в SNARK (см. также Приложение A к Zaatar) и описывает различные их воплощения.

О размере неинтерактивных аргументов, основанных на пейринге (2016)
Йенс Грот

В этой статье, в просторечии именуемой Groth16, представлена ​​усовершенствованная версия SNARK GGPR, которая даже сегодня обеспечивает самые современные конкретные затраты на проверку (доказательства представляют собой 3 групповых элемента, а в проверке преобладают три операции сопряжения, по крайней мере, при условии, что общедоступные ввод короткий). Безопасность доказана в общей групповой модели.

SNARK с универсальной надежной настройкой

PlonK: Перестановки над базисами Лагранжа для экуменических неинтерактивных аргументов Знания (2019)
Ариэль Габизон, Закари Уильямсон и Оана Чоботару

Marlin: предварительная обработка zkSNARK с помощью универсального и обновляемого SRS (2019)
Алессандро Кьеза, Юнконг Ху, Мэри Маллер, Пратюш Мишра, Пси Весели и Николас Уорд

И PlonK, и Marlin заменяют доверенную настройку для конкретной схемы в Groth16 универсальной настройкой. Это достигается за счет увеличенных в 4-6 раз доказательств. Можно представить, что PlonK и Marlin берут на себя работу, связанную с схемой, во время доверенной настройки в Groth16 и предшественниках и перемещают ее в фазу предварительной обработки, которая происходит после доверенной установки, а также во время генерации доказательства SNARK.

Способность таким образом обрабатывать произвольные схемы и системы R1CS иногда называют голографией или обязательствами по вычислениям, и она также была описана в спартанский (обсуждается далее в этом сборнике). Поскольку во время генерации доказательства выполняется больше работы, тестеры PlonK и Marlin работают медленнее, чем Groth16, для данной схемы или экземпляра R1CS. Однако, в отличие от Groth16, PlonK и Marlin можно заставить работать с более общими промежуточными представлениями, чем R1CS.

Полиномиальные схемы фиксации, ключевой криптографический примитив в SNARK.

Обязательства постоянного размера для полиномов и их приложений (2010)
Аникет Кейт, Грегори Заверуча и Ян Голдберг

В этой статье введено понятие полиномиальных схем фиксации. Он дал схему для одномерных полиномов (обычно называемых обязательствами KZG) с обязательствами постоянного размера и доказательствами оценки. Схема использует доверенную настройку (т. е. структурированную ссылочную строку) и криптографию на основе спаривания. Сегодня он остается чрезвычайно популярным на практике и используется в SNARK, включая PlonK и Marlin, о которых говорилось выше (и Groth16 использует очень похожие криптографические методы).

Быстрое интерактивное доказательство близости Oracle Reed-Solomon (2017)
Эли Бен-Сассон, Иддо Бентов, Инон Хореш, Михаил Рябзев

Предоставляет интерактивное доказательство оракула (IOP) для тестирования Рида-Соломона, то есть доказывает, что зафиксированная строка близка к таблице оценки одномерного многочлена. В сочетании с хешированием Меркла и преобразованием Фиата-Шамира это дает прозрачную полиномиальную схему обязательств с полилогарифмическими оценочными доказательствами (см. VP19 для подробностей). Сегодня это остается самой короткой среди правдоподобно постквантовых полиномиальных схем обязательства.

Ligero: легкие сублинейные аргументы без надежной установки (2017)
Скотт Эймс, Кармит Хазай, Юваль Ишай и Мутурамакришнан Венкитасубраманиам

Подобно FRI, эта работа дает IOP для тестирования Рида-Соломона, но с длиной доказательства квадратного корня, а не с полилогарифмической. теоретический работает показали, что, заменив код Рида-Соломона на другой код с исправлением ошибок с более быстрым кодированием, можно получить доказательство с линейным временем, которое, кроме того, изначально работает в любом поле. Этот подход был доработан и реализован в Торможение и Orion, что обеспечивает современную производительность прувера.

Bulletproofs: краткие доказательства конфиденциальных транзакций и многое другое (2017)
Бенедикт Банц, Джонатан Бутл, Дэн Боне, Эндрю Поэлстра, Питер Вуилле и Грег Максвелл

Уточнение предыдущей работы БЦГП, Bulletproofs предлагает прозрачную полиномиальную схему обязательств (на самом деле, обобщение, называемое аргументом внутреннего произведения), основанное на сложности вычисления дискретных логарифмов с логарифмическим размером доказательства, но линейным временем проверки. Схема остается популярной и сегодня благодаря своей прозрачности и коротким доказательствам (например, она используется в ZCash Orchard и Monero).

Дори: эффективные, прозрачные аргументы для обобщенных внутренних продуктов и полиномиальных обязательств (2020)
Джонатан Ли

Дори сокращает время проверки в Bulletproofs с линейного до логарифмического, сохраняя при этом прозрачность и доказательства логарифмического размера (хотя и больше, чем Bulletproofs) и прозрачность. Использует пары и основан на предположении SXDH.

Интерактивные доказательства, интерактивные доказательства с несколькими доказательствами и связанные с ними SNARK.

Делегирование вычислений: интерактивные доказательства для магглов (2008)
Шафи Голдвассер, Яэль Тауман Калай и Гай Ротблюм

До этой статьи интерактивные доказательства общего назначения требовали суперполиномиальное время прувер В этой статье приводится протокол интерактивного доказательства, обычно называемый протоколом GKR, с полиномиальным и квазилинейным временными верификаторами для любой задачи, имеющей эффективный параллельный алгоритм (эквивалентно, интерактивное доказательство применимо к любой арифметической схеме с небольшой глубиной).

Практические проверенные вычисления с потоковыми интерактивными доказательствами (2011)
Грэм Кормоуд, Майкл Митценмахер, Джастин Талер

В этой статье (иногда называемой CMT) время доказательства в протоколе GKR сократилось с четвертого по размеру схемы до квазилинейного. Произведена первая реализация универсального интерактивного доказательства. Ряд последующих работ (гвоздичное дерево, Талер13, Жирафаи Libra) еще больше сократил время работы прувера, от квазилинейного до линейного по размеру схемы.

vSQL: проверка произвольных SQL-запросов в динамических сторонних базах данных (2017)
Юпэн Чжан, Даниэль Генкин, Джонатан Кац, Димитриос Пападопулос и Харалампос Папаманту

Хотя название относится к конкретной прикладной области (базам данных), вклад этой статьи носит более общий характер. В частности, было замечено, что можно получить краткие аргументы в пользу выполнимости схемы, комбинируя интерактивные доказательства с полиномиальными схемами фиксации (для полилинейных полиномов).

Позже работает оказываемых аргументы с нулевым разглашением и введены различные схемы фиксации для полилинейных полиномов.

Spartan: эффективные и универсальные zkSNARK без надежной настройки (2019)
Шринат Сетти

Получает SNARK для выполнимости схемы и R1CS, комбинируя интерактивные доказательства с несколькими доказательствами (MIP) с полиномиальными схемами фиксации, опираясь на более раннюю работу над конкретно-эффективными MIP, называемыми Клевер. Результатом является получение SNARK с более короткими доказательствами, чем те, которые получены из интерактивных доказательств, таких как протокол GKR, рассмотренный выше. По аналогии с PlonK и Marlin, Spartan также показывает, как обрабатывать произвольные схемы и системы R1CS с помощью предварительной обработки и генерации доказательств SNARK.

Spartan использовал полиномиальную схему обязательств из Дайракс. Последующие работы назывались Торможение и Orion объедините MIP Spartan с другими полиномиальными схемами фиксации, чтобы получить первые реализованные SNARK с доказательством линейного времени.

Короткие PCP и IOP

Короткие PCP со сложностью запросов Polylog (2005)
Эли Бен-Сассон и Мадху Судан

 Эта теоретическая работа дала первое вероятностно проверяемое доказательство (PCP) с квазилинейной длиной доказательства по размеру проверяемого вычисления и полилогарифмической стоимости запроса (хотя линейное время проверки). После преобразования Килиана-Микали PCP в SNARK это был шаг к SNARK с квазилинейным доказательством времени и верификатором полилогарифмического времени.

Позже теоретическая работа сократил время проверки до полилогарифмического. Последующий Практическая работа усовершенствовала этот подход, но короткие PCP сегодня остаются непрактичными. Чтобы получить практические SNARK, новее работает Оказалось в интерактивное обобщение PCP, называемое Интерактивные доказательства Oracle (ИОП). Эти усилия привели к ПТ, популярная схема полиномиальных обязательств, обсуждаемая в разделе полиномиальных обязательств этого сборника.

Другие работы в этой категории включают ЗКБо и его потомки. Они не дают кратких доказательств, но имеют хорошие постоянные множители и, следовательно, привлекательны для доказательства небольших утверждений. Они привели к появлению семейств постквантовых сигнатур, таких как Пикник , которые имеют было оптимизированный in несколько работает. ZKBoo представлен как следующий отдельной парадигме дизайна, называемой ПДК в голове, но это дает IOP.

Рекурсивные SNARK

Инкрементно проверяемые вычисления или доказательства знаний подразумевают эффективность использования времени/пространства (2008)
Пол Валиант

В этой работе введено фундаментальное понятие вычислений с инкрементальной проверкой (IVC), в которых доказывающая сторона выполняет вычисление и все время поддерживает доказательство того, что вычисление до сих пор было правильным. Он построил IVC с помощью рекурсивной композиции SNARK. Здесь знание-основательность Свойство SNARK необходимо для установления правильности рекурсивно составленных неинтерактивных аргументов. В этой статье также представлен чрезвычайно эффективный экстрактор знаний для SNARK, полученных из PCP (согласно парадигме Килиана-Микали).

Масштабируемое нулевое знание с помощью циклов эллиптических кривых (2014)
Эли Бен-Сассон, Алессандро Кьеза, Эран Тромер и Мадарс Вирза

Следующий теоретическая работа, в этой статье использовалось рекурсивное применение варианта SNARK GGPR, чтобы обеспечить первую реализацию IVC для простой виртуальной машины (TinyRAM, от SNARK для C бумага).

Также введено понятие циклов эллиптических кривых, которые полезны для рекурсивного составления SNARK, использующих криптографию эллиптических кривых.

Рекурсивная композиция доказательства без доверенной установки (2019)
Шон Боу, Джек Григг и Дайра Хопвуд

В этой работе (называемой Halo) изучается, как рекурсивно составлять прозрачные SNARK. Это сложнее, чем составлять непрозрачные, потому что процедура проверки в прозрачных SNARK может быть намного дороже.

Затем это вызвало линия of работает кульминацией которого стали такие системы, как Новая звезда достижение современной производительности IVC, превосходящей даже ту, которая достигается при составлении непрозрачных SNARK, таких как Groth16.

Приложения

Zerocash: децентрализованные анонимные платежи в биткойнах (2014)
Эли Бен Сассон, Алессандро Кьеза, Кристина Гарман, Мэтью Грин, Ян Майерс, Эран Тромер, Мадарс Вирза

Опираясь на предыдущую работу, включая Zerocoin (и с Монета Пиноккио в качестве параллельной работы), в этой статье используются SNARK, производные от GGPR, для разработки частной криптовалюты. Привел к ZCash.

Geppetto: универсальные проверяемые вычисления (2014)
Крейг Костелло, Седрик Фурнет, Джон Хауэлл, Маркульф Кольвейс, Бенджамин Кройтер, Майкл Нэриг, Брайан Парно и Сами Захур

Возможно, Geppetto предшествовал взрыву интереса к исполнению частных смарт-контрактов, поскольку он был написан примерно через год после создания Ethereum. Следовательно, он не представлен в контексте выполнения частного смарт-контракта. Однако он использует рекурсию SNARK с ограниченной глубиной, чтобы позволить ненадежному доказывающему лицу выполнять любую частную (зафиксированную/подписанную) компьютерную программу на частных данных, не раскрывая информацию о выполняемой программе или данных, на которых она выполняется. Соответственно, это предшественник работы на частных платформах смарт-контрактов, таких как Зексе [описано ниже].

Поддающиеся проверке ASIC (2015)
Риад Вахби, Макс Хоуальд, Сиддхарт Гарг, Абхи Шелат, Майкл Уолфиш

В этой статье рассматривается проблема безопасного и плодотворного использования ASIC, изготовленного на ненадежном заводе (в 2015 году было всего пять стран с топовыми заводами). Подход заключается в том, чтобы быстрая, но ненадежная ASIC доказывала правильность своего вывода верификатору, работающему на более медленной, но надежной ASIC. Решение интересно до тех пор, пока общее время выполнения системы (т. е. сумма времени выполнения доказывающего и верифицирующего устройств плюс любые затраты на передачу данных) меньше наивного базового уровня: времени, необходимого для полного выполнения вычислений на более медленном -но-надежный ASIC. Используя вариант интерактивных доказательств GKR/CMT/Allspice, статья действительно превосходит наивную основу для ряда фундаментальных проблем, включая теоретико-числовые преобразования, сопоставление с образцом и операции с эллиптическими кривыми. Эта работа предполагает, что некоторые системы доказательств больше подходят для аппаратной реализации, чем другие. Оптимизация систем подтверждения для аппаратной реализации в настоящее время получает значительный внимание, но многое еще предстоит изучить.

проверяемый Функции задержки (2018)
Дэн Боне, Джозеф Бонно, Бенедикт Бюнц и Бен Фиш

Введена нотация проверяемых функций задержки (VDF), криптографический примитив, который широко используется в блокчейн-приложениях, например, для смягчения возможных манипуляций протоколами консенсуса Proof-of-Stake. SNARK (особенно для вычислений с инкрементальной проверкой) предлагают путь к современным VDF.

Zexe: включение децентрализованных частных вычислений (2018)
Шон Боу, Алессандро Кьеза, Мэтью Грин, Ян Майерс, Пратюш Мишра и Ховард Ву

Zexe — это разработка для частной платформы смарт-контрактов. Zexe можно рассматривать как расширение Zerocash (описано выше). Zerocash позволяет запускать одно приложение в сети (позволяя пользователям передавать токены), защищая при этом конфиденциальность пользовательских данных, например, кому они отправляют токены, от кого получают токены, количество переданных токенов и т. д. различные приложения (смарт-контракты) для работы на одном блокчейне и взаимодействия друг с другом. Транзакции выполняются вне сети, а доказательства правильного выполнения публикуются в сети. Защищена не только конфиденциальность данных, но и конфиденциальность функций. Это означает, что доказательство, связанное с каждой транзакцией, даже не показывает, к какому приложению (приложениям) относится транзакция. Более общий технический вклад Zexe заключается в том, что он представил BLS12-377, группу эллиптических кривых, которая полезна для эффективной композиции SNARK на основе спаривания с глубиной 1.

Реплицированные конечные автоматы без реплицированного выполнения (2020)
Джонатан Ли, Кирилл Никитин и Шринат Сетти

Это одна из немногих академических статей о свертывании для масштабируемости блокчейна. В нем не используется термин «свертки», потому что он предшествует или одновременен с концепцией, введенной за пределами академической литературы.

Внешние интерфейсы (эффективные преобразования компьютерных программ в промежуточные представления, такие как выполнимость схем, R1CS и т. д.)

Быстрый переход от оперативной памяти к делегируемым кратким задачам удовлетворения ограничений (2012)
Эли Бен-Сассон, Алессандро Кьеза, Даниэль Генкин и Эран Тромер

С современной точки зрения, это ранняя работа по практическому преобразованию компьютерной программы в схему SAT для абстракции виртуальной машины (ВМ). Опираясь на работы с конца 1970-х по 1990-е годы (например, работы Робсон) в этой статье описывается детерминированное сокращение от выполнения виртуальной машины за T шагов до выполнимости схемы размером O(T*polylog(T)).

Последующие документы, например, SNARK для C и BCTV, продолжал разрабатывать внешние интерфейсы с помощью абстракции виртуальной машины, а современные реализации включают такие проекты, как Каир, RISC-нольи Многоугольник Miden.

Делая проверенные вычисления на основе доказательств на несколько шагов ближе к практичности (2012)
Шринат Сетти, Виктор Ву, Нихил Панпалия, Бенджамин Браун, Мукит Али, Эндрю Дж. Блумберг и Майкл Уолфиш

Эта статья, известная как Ginger, является еще одним ранним вкладом в разработку практических интерфейсных технологий. Ginger представил гаджеты для общих примитивов программирования, таких как условные и логические выражения, сравнения и побитовая арифметика с помощью разделения битов, примитивная арифметика с плавающей запятой и т. д. Он использовал эти гаджеты, чтобы предоставить первый реализованный внешний интерфейс от языка высокого уровня до языка низкого уровня. арифметические ограничения (аналогичные тому, что сейчас известно как R1CS), промежуточное представление (IR), к которому может применяться серверная часть SNARK.

Принимая во внимание, что статья «Fast Reductions» и ее потомки используют подход «CPU-emulator» для создания IR (т. е. IR обеспечивает правильность выполнения прувером конкретной программы, применяя функцию перехода ЦП для заданного количества шагов). , Ginger и его потомки используют подход, более похожий на ASIC, создавая IR, адаптированные к компьютерной программе, которую, как утверждает прувер, правильно выполняет.

Например, буфет показывает, что можно обрабатывать сложный поток управления в модели ASIC, превращая такой поток управления в конечный автомат, адаптированный к выполняемой программе, и что этот подход может быть значительно более эффективным, чем создание эмулятора ЦП общего назначения. хджснарк дает эффективную конструкцию для арифметики с множественной точностью, оптимизации для ОЗУ и ПЗУ и предоставляет программисту язык высокого уровня, подобный Java, который остается популярным и сегодня. Цирк отмечает, что компиляция компьютерных программ в R1CS тесно связана с хорошо известными методами анализа программ, и создает инструментарий построения компилятора, включающий идеи обоих сообществ («LLVM для схемоподобных представлений»). Более ранние работы, вносящие вклад в интерфейсы в стиле ASIC, включают: Пиноккио и Geppetto.

В статье «Fast-Reductions» использовалась сложная и дорогая конструкция под названием «маршрутизирующие сети» для так называемых проверка памяти (т. е. обеспечение того, чтобы ненадежный доказывающий корректно поддерживал оперативную память ВМ на протяжении выполнения ВМ, корректность которой проверяется). Этот выбор был сделан потому, что ранние работы, такие как эта, стремились получить PCP, который требовал, чтобы внешний интерфейс был изоферменты печени неинтерактивный и информационно-теоретически безопасный. Более поздняя работа называлась Кладовая (предшественник буфет работа, упомянутая выше) использовали деревья Меркла вместо сетей маршрутизации, достигая эффективности за счет компиляции алгебраической (то есть «дружественной к SNARK») хеш-функции из-за Айтай, в ограничения. В результате появились «вычислительно безопасные» внешние интерфейсы. Сегодня существует большая исследовательская литература по хеш-функциям, удобным для SNARK, с примерами, включая Посейдон, МиМС, Железобетон, спасаниеИ многое другое.

Современные технологии, гарантирующие, что прувер правильно поддерживает оперативную память, основаны на так называемых методах «отпечатков пальцев, инвариантных к перестановкам», которые относятся как минимум к Lipton (1989) и использовался для проверки памяти Блюм и др. (1991). Эти методы по своей сути включают взаимодействие между доказывающим и проверяющим, но могут быть переведены в неинтерактивный режим с помощью преобразования Фиата-Шамира. Насколько нам известно, они познакомились с литературой по практическим интерфейсам SNARK через систему под названием VRAM.

Методы пермутационно-инвариантного снятия отпечатков теперь используются во многих интерфейсах и SNARK для абстракций виртуальных машин, включая, например, Каир. Тесно связанные идеи снова появились в связанных контекстах в двух работах ниже, которые широко используются на практике сегодня.

Почти линейное доказательство с нулевым разглашением для правильного выполнения программы (2018)
Джонатан Бутл, Андреа Черулли, Йенс Грот, Суне Якобсен и Мэри Маллер

Plookup: упрощенный полиномиальный протокол для таблиц поиска. (2020)
Ариэль Габизон и Закари Уильямсон

Ранние работы по внешним интерфейсам представляли «неарифметические» операции (такие как проверка диапазона, побитовые операции и целочисленные сравнения) внутри схем и связанных с ними IR путем разбиения элементов поля на биты, выполнения операций над этими битами, а затем «упаковки». результат обратно в один элемент поля. С точки зрения размера результирующей схемы это приводит к логарифмическим издержкам на операцию.

В двух вышеупомянутых работах (BCGJM и Plookup) представлены важные методы (основанные на так называемых «таблицах поиска») для более эффективного представления этих операций внутри схем в амортизированном смысле. Грубо говоря, для некоторого параметра B, выбранного разработчиком внешнего интерфейса, это уменьшает количество вентилей, необходимых для представления каждой неарифметической операции в схеме, на коэффициент, логарифмический по B, за счет того, что доказывающая сторона криптографически фиксирует дополнительную Вектор «совета» длиной примерно B.