Наш дуже суб'єктивний погляд на історію доведень з нульовим знанням

Короткі, стислі, неінтерактивні аргументи знання (zk-SNARK) - це потужні криптографічні примітиви, які дозволяють одній стороні, що доводить, переконати іншу сторону, що перевіряє, що дане твердження є істинним, не розкриваючи нічого іншого, окрім достовірності твердження. Вони отримали широку популярність завдяки застосуванню у верифікованих приватних обчисленнях, що забезпечують доказ правильності виконання комп'ютерних програм і допомагають масштабувати блокчейн. Ми вважаємо, що СНАРК матимуть значний вплив на формування нашого світу, як ми описали в нашому дописі. SNARKs діє як парасолька для різних типів систем доведення, що використовують різні схеми поліноміальних зобов'язань (PCS), схеми арифметизації, інтерактивні оракулові доведення (IOP) або доведення з імовірнісною перевіркою (PCP). Однак основні ідеї та концепції виникли ще в середині 1980-х років. Розвиток значно прискорився після впровадження Bitcoin і Ethereum, які виявилися захоплюючим і потужним варіантом використання, оскільки їх можна масштабувати за допомогою доказів нульового знання (зазвичай для цього конкретного випадку вони називаються доказами дійсності). SNARK - це важливий інструмент для масштабування блокчейну. Як описує Бен-Сассон, останні роки стали свідками кембрійського вибуху криптографічних доказів. Кожна система доказування має свої переваги та недоліки і була розроблена з урахуванням певних компромісів. Удосконалення апаратного забезпечення, кращі алгоритми, нові аргументи та гаджети призводять до підвищення продуктивності та народження нових систем. Багато з них використовуються у виробництві, і ми продовжуємо розширювати межі. Чи матимемо ми загальну систему доведення для всіх застосувань або кілька систем, пристосованих для різних потреб? Ми вважаємо, що навряд чи одна система доказів буде керувати ними всіма, тому що:

1. Різноманітність застосувань.
2. Типи обмежень, які ми маємо (щодо пам'яті, часу перевірки, часу доведення).
3. Потреба в надійності (якщо одна система доказів зламається, у нас є інші).

Навіть якщо системи доказів сильно змінюються, всі вони мають важливу властивість: докази можна швидко перевірити. Наявність шару, який перевіряє докази і може бути легко адаптований для роботи з новими системами доказів, вирішує труднощі, пов'язані зі зміною базового шару, як, наприклад, в Ethereum. Дати огляд різних характеристик СНАРК:

• Криптографічні припущення: стійкі до зіткнень хеш-функції, дискретна логічна задача над еліптичними кривими, знання експоненти.
• Прозоре та надійне налаштування.
• Час доказу: лінійна vs суперлінійна.
• Час верифікатора: постійний час, логарифмічний, сублінійний, лінійний.
• Пробний розмір.
• Простота рекурсії.
• Схема арифметичних дій.
• Одновимірні та багатовимірні поліноми.

У цій публікації ми розглянемо походження СНАРК, деякі фундаментальні будівельні блоки та розвиток (і занепад) різних систем доведення. Ця публікація не претендує на вичерпний аналіз систем доведення. Натомість ми зосереджуємося на тих, які мали на нас вплив. Звичайно, ці розробки стали можливими лише завдяки великій праці та ідеям піонерів цієї галузі.

Основи

Як ми вже згадували, доведення з нульовим знанням не є новим. Визначення, основи, важливі теореми і навіть важливі протоколи були створені з середини 1980-х років. Деякі з ключових ідей і протоколів, які ми використовуємо для побудови сучасних SNARK, були запропоновані в 1990-х роках (протокол sumcheck) або навіть до появи Біткоїна (GKR в 2007 році). Основні проблеми з її впровадженням були пов'язані з відсутністю потужного користувацького середовища (Інтернет не був настільки розвиненим у 1990-х роках), а також з обсягом необхідних обчислювальних потужностей.

Докази з нульовим знанням: витоки (1985/1989)

Теорія доказів з нульовим знанням з'явилася в науковій літературі завдяки роботі Гольдвассера, Мікалі та Ракоффа. Для обговорення походження, ви можете переглянути наступне відео. У статті введено поняття повноти, обґрунтованості та нульового знання, наведено конструкції для квадратичної залишковості та квадратичної ненульової залишковості.

Протокол Сумчека (1992)

Протокол сумарної перевірки був запропонований Лундом, Фортноу, Карлоффом і Нісаном у 1992 році. Це один з найважливіших будівельних блоків для лаконічних інтерактивних пробних версій. Це допомагає нам звести вимогу щодо суми оцінок багатовимірного полінома до однієї оцінки у випадково вибраній точці.

Goldwasser-Kalai-Rothblum (GKR) (2007)

Протокол GKR - це інтерактивний протокол, який має верифікатор, що працює лінійно за кількістю воріт схеми, в той час як верифікатор працює сублінійно за розміром схеми. У протоколі верифікатор і верифікатор домовляються про арифметичну схему віяла над скінченним полем глибиною d, де шар d відповідає вхідному шару, а шар 0 - вихідному шару. Протокол починається з твердження про вихід схеми, яке зводиться до твердження про значення попереднього рівня. Використовуючи рекурсію, ми можемо перетворити це на твердження про входи схеми, яке можна легко перевірити. Ці скорочення досягаються за допомогою протоколу sumcheck.

Поліноміальна схема зобов'язань KZG (2010)

Кейт, Заверуха та Голдберг представили у 2010 році схему зобов'язань для поліномів з використанням білінійної групи сполучень. Зобов'язання складається з одного групового елемента, і учасник може ефективно відкрити зобов'язання для будь-якої правильної оцінки полінома. Більше того, завдяки методам пакетної обробки, відкриття може бути зроблено для декількох оцінок. Зобов'язання тенге стали одним з основних будівельних блоків для кількох ефективних SNARK, таких як Pinocchio, Groth16 і Plonk. Він також лежить в основі EIP-4844. Щоб отримати уявлення про техніку пакетування, ви можете переглянути наш пост про міст Міна-Ефіріум.

Практичні СНАРК з використанням еліптичних кривих

Перші практичні конструкції для СНАРК з'явилися у 2013 році. Вони вимагали попередньої обробки для генерації підтверджуючих та верифікуючих ключів і були специфічними для конкретних програм/схем. Ці ключі могли бути досить великими і залежали від секретних параметрів, які повинні залишатися невідомими сторонам, інакше вони могли б підробляти докази. Перетворення коду на щось, що можна довести, вимагало компіляції коду до системи поліноміальних обмежень. Спочатку це доводилося робити вручну, що забирало багато часу і могло призвести до помилок. Досягнення в цій галузі намагалися усунути деякі з основних проблем:

1. Мати більш ефективні докази.
2. Зменшити кількість попередньої обробки.
3. Мати універсальні, а не специфічні для конкретної схеми налаштування.
4. Уникайте довірених налаштувань.
5. Розробка способів опису схем за допомогою мови високого рівня, замість того, щоб писати поліноміальні обмеження вручну.

Піноккіо (2013)

Pinocchio - це перший практичний, придатний для використання zk-SNARK. СНАРК базується на програмах квадратичної арифметики (QAP). Спочатку розмір перевірки становив 288 байт. Інструментарій Піноккіо забезпечував компілятор з коду C в арифметичні схеми, який далі трансформувався в QAP. Протокол вимагав, щоб верифікатор генерував ключі, які є специфічними для конкретної схеми. Для перевірки рівнянь він використовував пари еліптичних кривих. Асимптотика генерації доказів та налаштування ключів була лінійною від розміру обчислень, а час перевірки був лінійним від розміру відкритих входів та виходів.

Groth 16 (2016)

Грот представив новий аргумент знання з підвищеною продуктивністю для проблем, описаних R1CS. Він має найменший розмір доказу (лише три елементи групи) і швидку перевірку за допомогою трьох пар. Він також включає в себе етап попередньої обробки для отримання структурованого рядка посилань. Основний недолік полягає в тому, що для кожної програми, яку ми хочемо довести, потрібне різне довірене налаштування, що незручно. Groth16 використовувався в ZCash.

Куленепробивні & ПНД (2016)

Однією зі слабких сторін РКС КЗГ є те, що вона потребує надійного налаштування. Бутл та ін. ввели ефективну систему аргументів з нульовим рівнем знань для відкриттів зобов'язань Педерсена, які задовольняють внутрішньому відношенню продуктів. Аргумент внутрішнього продукту має лінійне доведення, з логарифмічним зв'язком і взаємодією, але з лінійною перевіркою часу. Вони також розробили поліноміальну схему зобов'язань, яка не вимагає довіреної установки. PCS, що використовує ці ідеї, використовується в Halo 2 та Kimchi.

Сонік, Марлін і Плонк (2019)

Sonic, Plonk та Marlin вирішують проблему довіреного налаштування для кожної програми, яку ми мали у Groth16, шляхом введення універсальних та оновлюваних структурованих рядків посилань. Marlin надає систему перевірки на основі R1CS і є ядром Aleo.

Плонк запровадив нову схему арифметики (пізніше названу Плонкіш) і використання перевірки великого добутку для обмежень на копіювання. Плонкіш також дозволив запровадити спеціалізовані ворота для певних операцій, так звані спеціальні ворота. Кілька проектів мають кастомізовані версії Plonk, зокрема Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2, Scroll та інші.

Пошуки (2018/2020)

Габізон і Вільямсон представили plookup у 2020 році, використовуючи велику перевірку продукту, щоб довести, що значення включено в попередньо обчислену таблицю значень. Хоча аргументи пошуку раніше були представлені в Arya, конструкція вимагала визначення кратності для пошуку, що робить конструкцію менш ефективною. У статті PlonkUp було показано, як ввести аргумент plookup у Plonk. Проблема з цими аргументами пошуку полягала в тому, що вони змушували доказувача платити ціну за всю таблицю, незалежно від того, скільки разів він її шукав. Це означає значні витрати для великих таблиць, і багато зусиль було докладено для того, щоб зменшити витрати на перевірку лише до кількості переборів, які він використовує.
Хабьок представив LogUp, який використовує логарифмічну похідну, щоб перетворити перевірку великого добутку на суму зворотних чисел. LogUp має вирішальне значення для продуктивності в Polygon ZKEVM, де потрібно розбити всю таблицю на кілька модулів STARK. Ці модулі мають бути правильно пов'язані між собою, і перехресний пошук забезпечує це. Впровадження LogUp-GKR використовує протокол GKR для підвищення продуктивності LogUp. Caulk була першою схемою з часом перевірки, сублінійним до розміру таблиці, за рахунок використання часу попередньої обробки O(NlogN) та зберігання O(N), де N - розмір таблиці. Згодом з'явилося ще кілька схем, таких як Baloo, flookup, cq та caulk+. Lasso пропонує кілька покращень, уникаючи прив'язки до таблиці, якщо вона має задану структуру. Крім того, перевірка Лассо оплачує лише ті записи таблиці, до яких здійснюється доступ за допомогою операцій пошуку. Jolt використовує Lasso, щоб довести виконання віртуальної машини за допомогою пошуку.

Спартанець (2019)

Spartan забезпечує IOP для схем, описаних за допомогою R1CS, використовуючи властивості багатовимірних поліномів і протоколу перевірки суми. Використовуючи відповідну поліноміальну схему зобов'язань, він призводить до прозорого SNARK з лінійною перевіркою часу.

HyperPlonk (2022)

HyperPlonk спирається на ідеї Plonk, використовуючи багатовимірні поліноми. Замість коефіцієнтів для перевірки виконання обмежень він покладається на протокол перевірки суми. Він також підтримує обмеження високого ступеня без шкоди для часу роботи перевірника. Оскільки він спирається на багатовимірні поліноми, немає необхідності виконувати ШПФ, а час роботи перевірювача лінійно залежить від розміру схеми. HyperPlonk представляє новий перестановочний IOP, придатний для менших полів, і протокол відкриття пакетів на основі перевірки суми, який зменшує роботу верифікатора, розмір доказу і час верифікатора.

Схеми складання (2008/2021)

Nova представляє ідею схеми згортання, яка є новим підходом для досягнення інкрементно верифікованих обчислень (IVC). Концепція IVC бере свій початок від Валіанта, який показав, як об'єднати два доведення довжини k в одне доведення довжини k. Ідея полягає в тому, що ми можемо довести будь-яке довготривале обчислення, рекурсивно довівши, що виконання від кроку i до кроку I+1+1 є правильним, і перевіривши доведення, яке показує, що перехід від кроку i

-1-1 до кроку i був правильним. Nova добре справляється з однорідними обчисленнями; пізніше її було розширено для роботи з різними типами схем з появою Supernova. Nova використовує полегшену версію R1CS і працює над дружніми еліптичними кривими. Робота з дружніми циклами кривих (наприклад, криві Паста) для досягнення IVC також використовується в Pickles, головному будівельному блоці Міни для досягнення лаконічного стану. Однак ідея згортання відрізняється від рекурсивної SNARK-перевірки. Ідея акумулятора глибше пов'язана з концепцією пакетних доказів. Гало ввів поняття накопичення як альтернативу рекурсивній композиції доведення. Protostar надає неоднорідну схему IVC для Plonk, яка підтримує вентилі високого ступеня та векторний пошук.

Використання хеш-функцій, стійких до колізій

Приблизно в той самий час, коли був розроблений Pinocchio, з'явилися ідеї генерувати схеми/схеми арифметичних дій, які могли б довести правильність виконання віртуальної машини. Хоча розробка арифметики віртуальної машини може бути складнішою або менш ефективною, ніж написання спеціальних схем для деяких програм, вона має ту перевагу, що будь-яку програму, незалежно від того, наскільки вона складна, можна довести, показавши, що вона правильно виконується у віртуальній машині. Ідеї, закладені в TinyRAM, згодом були вдосконалені при розробці Cairo vm та наступних віртуальних машин (таких як zk-evms або zkvms загального призначення). Використання хеш-функцій, стійких до зіткнень, усунуло необхідність у надійних налаштуваннях або використанні еліптичних кривих, але за рахунок довших перевірок.

TinyRAM (2013)

В SNARKs for C вони розробили SNARK на основі PCP для доведення правильності виконання програми на C, яка компілюється в TinyRAM, комп'ютер зі скороченим набором інструкцій. Комп'ютер використовував гарвардську архітектуру з байтовою адресованою пам'яттю довільного доступу. Використовуючи недетермінованість, розмір схеми квазілінійно залежить від розміру обчислень, ефективно обробляючи довільні та залежні від даних цикли, потік керування та доступ до пам'яті.

СТАРКИ (2018)

STARKs були введені Беном Сассоном та ін. у 2018 році. Вони досягають O(log2n)(log2)

з швидким доведенням і верифікатором не потребують надійного налаштування і, як припускають, є пост-квантово безпечними. Вперше вони були використані Starkware/Starknet разом з Cairo vm. Серед ключових нововведень - алгебраїчне проміжне представлення (AIR) та протокол FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Він також використовується іншими проектами (Polygon Miden, Risc0, Winterfell, Neptune) або є адаптацією деяких компонентів (Boojum від zkSync, Plonky2, Starky).

Лігеро (2017)

Ligero представляє систему доказу, яка дозволяє отримувати докази, розмір яких становить

O(√n), де n - розмір схеми. Він впорядковує коефіцієнти полінома у матричній формі та використовує лінійні коди.
Brakedown спирається на Ligero і вводить ідею поле-агностичних поліноміальних схем зобов'язань.

Деякі нові розробки

Використання різних систем доказу на виробництві показало переваги кожного з підходів і призвело до нових розробок. Наприклад, plonkish арифметика пропонує простий спосіб включення користувацьких воріт і аргументів пошуку; FRI показав чудову продуктивність як PCS, що призвело до появи Plonky. Аналогічно, використання перевірки великого добутку в AIR (що призвело до рандомізованого AIR з попередньою обробкою) покращило його продуктивність і спростило аргументи доступу до пам'яті. Зобов'язання, засновані на хеш-функціях, набули популярності завдяки швидкості роботи хеш-функцій в апаратному забезпеченні або впровадженню нових SNARK-дружніх хеш-функцій.

Нові поліноміальні схеми зобов'язань (2023)

З появою ефективних СНАРК на основі багатовимірних поліномів, таких як Spartan або HyperPlonk, зросла зацікавленість у нових схемах зобов'язань, придатних для такого типу поліномів. Binius, Zeromorph та Basefold пропонують нові форми для мультилінійних поліномів. Перевагою Binius є відсутність накладних витрат на представлення типів даних (тоді як багато систем доказу використовують щонайменше 32-розрядні елементи полів для представлення одиночних бітів) і робота з двійковими полями. Зобов'язання адаптує систему гальмування, яка була розроблена як агностична до поля. Basefold узагальнює FRI на коди, відмінні від коду Ріда-Соломона, що призводить до польової діагностики PCS.

Налаштовувані системи обмежень (2023)

CCS узагальнює R1CS, захоплюючи арифметику R1CS, Plonkish та AIR без накладних витрат. Використання CCS зі Spartan IOP дає SuperSpartan, який підтримує обмеження високого ступеня, не вимагаючи від перевіряючого нести криптографічні витрати, які масштабуються зі ступенем обмеження. Зокрема, SuperSpartan дає SNARK для AIR з лінійною перевіркою часу.

Висновок

Ця публікація описує досягнення СНАРК з моменту їх впровадження в середині 1980-х років. Досягнення в галузі комп'ютерних наук, математики та апаратного забезпечення разом із впровадженням блокчейну призвели до появи нових і більш ефективних SNARK, відкриваючи двері для багатьох застосувань, які можуть трансформувати наше суспільство. Дослідники та інженери запропонували вдосконалення та адаптацію SNARK відповідно до своїх потреб, зосередившись на розмірі доказу, використанні пам'яті, прозорому налаштуванні, пост-квантовій безпеці, часі доведення та часі верифікатора. Хоча спочатку було дві основні лінії (SNARKs vs STARKs), межа між ними почала стиратися, намагаючись об'єднати переваги різних систем доведення. Наприклад, поєднання різних схем арифметики з новими схемами поліноміальних зобов'язань. Ми можемо очікувати, що нові системи доказування продовжуватимуть розвиватися, підвищуючи свою продуктивність, і деяким системам, які потребують певного часу на адаптацію, буде важко йти в ногу з цими розробками, якщо ми не зможемо легко використовувати ці інструменти без необхідності змінювати якусь основну інфраструктуру.

Відмова від відповідальності:.

1. Ця стаття передрукована з[lambdaclass], всі авторські права належать оригінальному автору[LambdaClass]. Якщо у вас є заперечення щодо цього передруку, будь ласка, зв'яжіться з командою Gate Learn, і вони оперативно його опрацюють.
2. Відмова від відповідальності: Погляди та думки, висловлені в цій статті, належать виключно автору і не є інвестиційною порадою.
3. Переклади статті іншими мовами виконані командою Gate Learn. Якщо не зазначено інше, копіювання, розповсюдження або плагіат перекладених статей заборонені.