Канон нульового знання

Примітка редактора: a16z crypto мала довгу серію “пістолети», від нашого DAO Canon минулого року до нашого NFT Canon раніше (і до цього наш оригінал Crypto Canon) — обов’язково підписуйтесь на наш web3 щотижневий бюлетень для отримання додаткових оновлень, а також інші підібрані ресурси.

Отже, бдовше, ми підібрали набір ресурсів для тих, хто хоче зрозуміти, заглибитися та створити з усіма речами нульові знання: потужні основоположні технології, які тримають ключ до масштабованості блокчейну та представляють майбутнє програм для збереження конфіденційності та незліченну кількість інших інновацій. Якщо у вас є пропозиції щодо високоякісних речей, які можна додати, дайте нам знати @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

Від стійкості до зіткнень, яку можна витягти, до стислих неінтерактивних аргументів знань [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

Заняття на дошці ЗК — вступні модулі
з Деном Боне та ін
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 у 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 — від ECC
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

Онлайн-середовище розробки для zkSNARKs — zkREPL, новий набір інструментів для взаємодії з Circom toolstack у браузері
Кевін Квок
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

ЗК машинне навчання — підручник і демонстрація для розміщення нейронної мережі в 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/

Подкаст Zero Knowledge — про останні дослідження zk і програми zk, а також про експертів, які розробляють технології конфіденційності з підтримкою криптографії
з Анною Роуз
https://zeroknowledge.fm/

…анотований список літератури за темами та хронологією, автор Джастін Талер:

SNARK від лінійних PCP (також відомі як SNARK із налаштуванням для конкретної схеми)

Ефективні аргументи без коротких PCP (2007)
Юваль Ішаї, Еял Кушилевітц і Рафаїл Островський

Приблизно до 2007 року SNARK в основному розроблялися за допомогою Kilian-Мікалі Парадигма полягає в тому, щоб взяти «короткий» імовірнісно перевірений доказ (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, представлено удосконалення GGPR SNARK, яке забезпечує найсучасніші конкретні витрати на верифікацію навіть сьогодні (докази складаються з 3 групових елементів, а верифікація складається з трьох парних операцій, принаймні за умови, що громадськість вхід короткий). Безпека доведена в загальній груповій моделі.

SNARK з універсальним надійним налаштуванням

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

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

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

Здатність обробляти довільні схеми та системи R1CS у такий спосіб іноді називають голографією або зобов’язаннями обчислень, і також описано в спартанський (обговорюється далі в цій добірці). Оскільки під час генерації доказів виконується більше роботи, првери PlonK і Marlin працюють повільніше, ніж Groth16, для певної схеми або примірника R1CS. Однак, на відміну від Groth16, PlonK і Marlin можна змусити працювати з більш загальними проміжними представленнями, ніж R1CS.

Поліноміальні схеми зобов’язань, ключовий криптографічний примітив у SNARK

Обов'язки постійного розміру для поліномів та їх застосування (2010)
Анікет Кейт, Грегорі Заверуча та Ієн Голдберг

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

Інтерактивні докази близькості Oracle Reed-Solomon Proofs of Proximity (2017)
Елі Бен-Сассон, Іддо Бентов, Інон Хореш, Майкл Рябзєв

Надає інтерактивне доказ оракула (IOP) для перевірки Ріда-Соломона — тобто доведення того, що зафіксований рядок близький до таблиці оцінки одновимірного полінома. У поєднанні з хешуванням Меркла та перетворенням Фіата-Шаміра це дає прозору поліноміальну схему зобов’язань із доказами оцінки полілогарифмічного розміру (див. VP19 для деталей). Сьогодні це залишається найкоротшим серед правдоподібно постквантових поліноміальних схем зобов’язань.

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

Подібно до FRI, ця робота дає ВОТ для тестування Ріда-Соломона, але з довжиною доказу квадратного кореня, а не полілогарифмічною. Теоретичні працює показав, що, замінивши код Ріда-Соломона на інший код з виправленням помилок із швидшим кодуванням, можна отримати систему перевірки лінійного часу, яка, крім того, працює над будь-яким полем. Цей підхід було вдосконалено та реалізовано в Гальмування та Orion, що забезпечує найсучаснішу продуктивність прувера.

Bulletproofs: Короткі докази для конфіденційних транзакцій тощо (2017)
Бенедикт Бунц, Джонатан Бутл, Ден Боне, Ендрю Поелстра, Пітер Уілле та Грег Максвелл

Доопрацювання попередньої роботи BCCGP, Bulletproofs надає прозору поліноміальну схему зобов’язань (фактично, узагальнення, яке називається аргументом внутрішнього добутку), засноване на складності обчислення дискретних логарифмів із логарифмічним розміром доказу, але лінійним часом перевірки. Схема залишається популярною сьогодні завдяки своїй прозорості та коротким доказам (наприклад, вона використовується в ZCash Orchard і Monero).

Дорі: Ефективні, прозорі аргументи для узагальнених внутрішніх добутків і поліноміальних зобов’язань (2020)
Джонатан Лі

Dory скорочує час верифікації в Bulletproofs з лінійного до логарифмічного, зберігаючи при цьому прозорість і логарифмічні розміри доказів (хоча конкретно більші, ніж Bulletproofs) і прозорість. Використовує пари та базується на припущенні SXDH.

Інтерактивні докази, інтерактивні докази з кількома перевірками та пов’язані SNARK

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

До цієї статті інтерактивні докази загального призначення вимагали a суперполіноміальний час перевірка. У цьому документі наводиться протокол інтерактивного підтвердження, який зазвичай називають протоколом GKR, із поліноміальним перевірячем часу та квазілінійним перевірячем часу для будь-якої задачі, що має ефективний паралельний алгоритм (еквівалентно, інтерактивне підтвердження застосовується до будь-якої арифметичної схеми з малою глибиною).

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

Цей документ (іноді званий CMT) зменшив час перевірки в протоколі GKR з квартичного розміру схеми до квазілінійного. Створено першу реалізацію інтерактивного доказу загального призначення. Низка наступних робіт (Запашний перець, Талер13, Жираф та ваги) ще більше зменшив час роботи прувера, від квазілінійного до лінійного за розміром схеми.

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

Незважаючи на те, що назва стосується конкретної області застосування (бази даних), внески цієї статті є більш загальними. Зокрема, було зазначено, що можна отримати стислі аргументи для задовільності схеми, поєднуючи інтерактивні докази з поліноміальними схемами зобов’язань (для багатолінійних поліномів).

Пізніше працює винесено аргументи з нульовим знанням і ввели різні схеми зобов'язань для багатолінійних поліномів.

Spartan: ефективні zkSNARK загального призначення без надійного налаштування (2019)
від Srinath Setty

Отримує 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 (ВГД). Ці зусилля призвели до розвитку та розвитку БЕЗКОШТОВНО, популярна схема поліноміальних зобов’язань, яка обговорюється в розділі поліноміальних зобов’язань цієї збірки.

Інші роботи в цій категорії включають ZKBoo і його нащадків. Вони не забезпечують стислих доказів, але вони мають хороші постійні коефіцієнти і, отже, є привабливими для доведення невеликих тверджень. Вони призвели до сімейств постквантових сигнатур, таких як Пікнік що є було оптимізований in кілька працює. ZKBoo представлено як дотримання окремої парадигми дизайну під назвою MPC-в-голові, але це дає IOP.

Рекурсивні SNARK

Обчислення з можливістю інкрементальної перевірки або докази знань передбачають ефективність часу/простору (2008)
від Paul Valiant

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

Масштабований нульовий рівень знань за допомогою циклів еліптичних кривих (2014)
Елі Бен-Сассон, Алессандро К'єза, Еран Тромер і Мадарс Вірза

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

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

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

Ця робота (називається Halo) вивчає, як рекурсивно створювати прозорі SNARK. Це складніше, ніж створення непрозорих, оскільки процедура перевірки в прозорих SNARK може бути набагато дорожчою.

Потім це викликало а лінія of робота що досягло кульмінації в таких системах, як Нова зірка досягнення найсучаснішої продуктивності IVC, що перевершує навіть ті, що досягаються шляхом композиції непрозорих SNARK, таких як Groth16.

додатків

Zerocash: децентралізовані анонімні платежі з Bitcoin (2014)
Елі Бен Сассон, Алессандро К'єза, Крістіна Гарман, Метью Грін, Ян Міерс, Еран Тромер, Мадарс Вірза

Спираючись на попередню роботу в тому числі Зерокоин (і с Монета Пінокіо як одночасну роботу), у цьому документі використовуються SNARK, отримані від GGPR, для розробки приватної криптовалюти. Привів до ZCash.

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

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

Верифіковані ASIC (2015)
Ріад Вахбі, Макс Ховальд, Сіддхарт Гарг, абхі шелат, Майкл Волфіш

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

Перевіряється Функції затримки (2018)
Ден Боне, Джозеф Бонно, Бенедикт Бюнц і Бен Фіш

Представлено нотацію верифікованих функцій затримки (VDF), криптографічного примітиву, який широко корисний у додатках блокчейну, наприклад, для пом’якшення можливого маніпулювання консенсусними протоколами підтвердження частки. SNARK (особливо для інкрементально перевірених обчислень) пропонують шлях до найсучасніших VDF.

Zexe: увімкнення децентралізованих приватних обчислень (2018)
Шон Боу, Алессандро К'єза, Меттью Грін, Ян Мієрс, Пратюш Мішра та Говард Ву

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

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

Це одна з небагатьох наукових робіт про зведення для масштабованості блокчейну. У ньому не використовується термін згортання, оскільки він з’явився раніше або з’явився одночасно з цим поняттям, яке вводиться за межами академічної літератури.

Інтерфейси (ефективні перетворення від комп’ютерних програм до проміжних представлень, таких як схема-задовільність, R1CS тощо)

Швидке скорочення від оперативної пам’яті до делегованих стислих проблем із задоволенням обмежень (2012)
Елі Бен-Сассон, Алессандро К'єза, Даніель Генкін і Еран Тромер

З сучасної точки зору, це рання робота з практичних перетворень комп’ютерної програми в схему SAT для абстракції віртуальної машини (VM). Спираючись на роботи з кінця 1970-х до 1990-х років (наприклад, робота Робсон) у цій статті описується детермінована редукція від виконання VM для T кроків до виконуваності схеми розміром O(T*polylog(T)).

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

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

Ця стаття, яка називається Ginger, є ще одним раннім внеском у практичні методи інтерфейсу. Джинджер представив гаджети для загальних примітивів програмування, таких як умовні вирази та логічні вирази, порівняння та порозрядну арифметику через розбиття бітів, примітивну арифметику з плаваючою комою тощо. Він використовував ці гаджети, щоб забезпечити перший реалізований інтерфейс від мови високого рівня до мови низького ступеня. арифметичні обмеження (подібні до того, що зараз відомо як R1CS), проміжне представлення (IR), до якого може бути застосований сервер SNARK.

У той час як стаття «Швидкі скорочення» та її нащадки використовують підхід «емулятора процесора» для створення IR (тобто IR гарантує, що првер правильно запустив певну програму, застосовуючи функцію переходу ЦП для визначеної кількості кроків) , Ginger та його нащадки використовують підхід, більш схожий на ASIC, виробляючи IR, адаптовані до комп’ютерної програми, яку, як стверджує, перевірка виконує правильно.

Наприклад, Буфет показує, що можливо обробляти складний потік керування в моделі ASIC, перетворюючи такий потік керування на кінцевий автомат, адаптований до програми, що виконується, і що цей підхід може бути значно ефективнішим, ніж побудова емулятора центрального процесора загального призначення. xJsnark дає ефективну конструкцію для арифметики з різною точністю, оптимізує RAM та ROM та надає програмісту Java-подібну мову високого рівня, яка залишається популярною сьогодні. CirC зауважує, що компіляція комп’ютерних програм до R1CS тісно пов’язана з добре відомими техніками аналізу програм, і створює набір інструментів для створення компілятора, що включає ідеї обох спільнот («LLVM для схемоподібних представлень»). Більш ранні роботи, що внесли внесок у інтерфейси в стилі ASIC, включають Піноккіо та Geppetto.

У документі «Швидкі скорочення» використовувалася складна і дорога конструкція під назвою «мережі маршрутизації» для т.зв. перевірка пам'яті (тобто забезпечення того, що ненадійний перевірник правильно підтримує оперативну пам’ять віртуальної машини протягом усього часу виконання віртуальної машини, правильність якої перевіряється). Цей вибір був зроблений тому, що перші роботи, такі як ця, прагнули отримати PCP, для чого вимагалося, щоб інтерфейс був обидва неінтерактивний та інформаційно-теоретично захищений. Пізніше робота дзвонила Комора (попередник Буфет робота, згадана вище) використовувала Merkle-дерева замість мереж маршрутизації, досягаючи ефективності шляхом компіляції алгебраїчної (тобто «дружньої до SNARK») хеш-функції, завдяки Айтай, в обмеження. Це призвело до «обчислювально безпечних» інтерфейсів. Сьогодні існує велика дослідницька література про дружні до SNARK хеш-функції, включаючи приклади Посейдон, MiMC, Залізобетон, РятуватиІ багато іншого.

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

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

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

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

Ранні роботи над інтерфейсами представляли «неарифметичні» операції (такі як перевірки діапазону, порозрядні операції та цілочисельні порівняння) всередині ланцюгів і пов’язаних ІР шляхом розбиття елементів поля на біти, виконання операцій над цими бітами, а потім «упакування» результат повертається в один елемент поля. З точки зору розміру результуючої схеми, це призводить до логарифмічних накладних витрат на операцію.

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