Детально поясніть два нових інструменти SNARK, запущені a16z crypto

Ця стаття взята з 16 z, оригінальний автор: Джастін Талер, зібрано перекладачем Odaily Planet Daily Джесікою.

10 серпня крипто 16 z запустило нові інструменти на основі SNARK Lasso та Jolt, які разом представляють новий підхід до дизайну SNARK, який може покращити продуктивність широко розгорнутих інструментальних ланцюжків на порядок чи більше; надаючи кращий, зручніший досвід розробника та спрощення аудиту.

SNARK (Succinct Non-Interactive Argument of Knowledge) — це криптографічний протокол, за допомогою якого будь-хто може довести ненадійному верифікатору, що він знає «свідка», який задовольняє певні властивості.

• Основний варіант використання в Web 3 полягає в тому, щоб L2 доводив L1, що вони знають цифровий підпис, який авторизує низку транзакцій, тому сам підпис не потрібно зберігати та перевіряти в мережі L1, покращуючи масштабованість.
• Програми за межами блокчейну включають: швидке підтвердження дійсності всіх виходів, створених ненадійними апаратними пристроями, гарантуючи, що користувачі можуть їм довіряти. Особи можуть довести без інформування, що довірений орган видав їм облікові дані, які підтверджують, що вони достатньо дорослі для доступу до вмісту з віковими обмеженнями, не повідомляючи дати свого народження. Кожен, хто надсилає зашифровані дані через мережу, може довести адміністраторам, що ці дані відповідають політиці мережі, не розкриваючи додаткових деталей.

Незважаючи на те, що багато SNARK залишаються привабливими витратами для верифікатора, SNARK зазвичай все ще спричиняють приблизно шість порядків величини накладних витрат у обчислення прувера. Додаткова робота, яку виконує прувер, дуже розпаралелена, але накладні витрати в мільйони разів серйозно обмежують сферу застосування SNARK.

**SNARK з більшою продуктивністю пришвидшить L 2, а також дозволить розробникам розблокувати програми, які ще не передбачені. **Ось чому ми представляємо дві нові пов’язані технології: Lasso, новий параметр пошуку, який може значно збільшити вартість прувера; Jolt, яка використовує Lasso, щоб створити нову структуру для так званої zkVM, і ширший зовнішній дизайн проектувати SNARK. Разом вони покращують продуктивність, досвід розробників і можливість перевірки проектів SNARK, що, у свою чергу, покращує збірки в web 3.

Наша початкова реалізація Lasso продемонструвала прискорення більш ніж у 10 разів порівняно з параметрами пошуку в популярному інструментальному ланцюжку SNARK halo 2. Коли кодову базу Lasso буде повністю оптимізовано, ми очікуємо ~40-кратного прискорення. Jolt включає інші інновації на додаток до Lasso, і ми очікуємо, що він досягне подібного або кращого прискорення, ніж існуюча zkVM.

Знайти параметри, ласо та поштовх

Інтерфейс SNARK — це компілятор, який перетворює комп’ютерну програму на схему, яку може отримати сервер SNARK. (Примітка: Схема є надзвичайно обмеженою моделлю обчислень, де єдиними доступними «примітивними операціями» є додавання та множення.)

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

Однак, як сказав минулого року Баррі Уайтхат з Ethereum Foundation, «якщо ми зможемо ефективно визначити схеми, використовуючи лише параметри пошуку, це призведе до простіших інструментів і схем». Розроблена нами схема виконує лише пошуки. З часом параметри пошуку «стануть більш ефективними, ніж поліноміальні обмеження майже для всього».

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

Lasso та Jolt вирішують усі три ключові питання: продуктивність, досвід розробника та можливість аудиту, і разом вони реалізують бачення пошуку унікальності. Lasso та Jolt також змушують переглянути багато загальноприйнятих ідей у дизайні SNARK.

Після того, як надано необхідну основну інформацію, нижче розглядаються деякі загальні ідеї щодо продуктивності SNARK і пояснюється, як їх можна оптимізувати у світлі інновацій, таких як Lasso та Jolt.

Фон дизайну SNARK: чому так повільно?

Більшість серверних модулів SNARK мають систему перевірки, яка криптографічно фіксує значення кожного вентиля в схемі за допомогою поліноміальної схеми фіксації. Потім перевірка доводить, що подане значення справді відповідає правильному виконанню перевірки свідка.

Я називаю роботу перевірки за схемою поліноміальних зобов’язань вартістю зобов’язань. **SNARK мають додаткові витрати на підтвердження через поліноміальні схеми зобов’язань. Але витрати на зобов'язання часто є вузьким місцем. **Лассо та Джолт також. Якщо SNARK розроблено так, що вартість зобов’язань не є основною вартістю перевірки, це не означає, що поліноміальна схема зобов’язань є дешевою. Скоріше це означає, що інші витрати вищі, ніж вони повинні бути.

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

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

Обчислювальні зобов’язання включають багаторазове піднесення до степеня (також відоме як багаторазове скалярне множення, або MSM) або ШПФ і хеші Merkle, залежно від використовуваної поліноміальної схеми зобов’язання. Lasso та Jolt можуть використовувати будь-яку поліноміальну схему зобов’язань, але мають особливо привабливу вартість, коли створюють екземпляри за допомогою схем на основі MSM, таких як IPA/Bulletproofs, KZG/PST, Hyrax, Dory або Zeromorph.

Чому Lasso та Jolt важливі

Ласо — це новий параметр пошуку, де перевірка обіцяє менше та менших значень, ніж у попередній роботі. Це може бути прискорення у 20 або більше разів, де прискорення від 2 до 4 разів походить від меншої кількості прийнятих значень, а ще одне прискорення в 10 разів – через те, що всі прийняті значення в Lasso малі. На відміну від багатьох попередніх параметрів пошуку, Lasso (і Jolt) також уникають ШПФ, які займають багато місця та можуть бути вузьким місцем для великих екземплярів.

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

Lasso використовує дві різні структурні концепції: розкладність і структуру LDE. (LDE — це абревіатура технічної концепції під назвою розширений поліном низького ступеня.) Розкладність приблизно означає, що на один пошук таблиці можна відповісти, виконавши меншу кількість пошуків у меншій таблиці. Це суворіша вимога, ніж структура LDE, але Lasso особливо ефективний у застосуванні до розкладних таблиць.

Поштовх

Jolt (Just One Lookup Table) — це новий інтерфейс, який розблоковано завдяки можливості Lasso використовувати величезні таблиці пошуку. Jolt націлений на абстракцію віртуальної машини/ЦП, також відому як архітектура набору інструкцій (ISA). SNARK, які підтримують цю абстракцію, називаються zkVM. Наприклад, розглянемо набір інструкцій RISC-V (включаючи розширення множення), на який також спрямований проект RISC-Zero. Це популярна ISA з відкритим кодом, розроблена спільнотою комп’ютерних архітектур без урахування SNARK.

Для кожної інструкції RISC-V fi основна ідея Jolt полягає в тому, щоб створити таблицю пошуку, яка містить всю таблицю оцінки fi. Практично для кожної інструкції RISC-V результуюча таблиця пошуку є розкладною та застосовується ласо.

Перегляд загальноприйнятої мудрості в дизайні SNARK

Лассо та Джолт також руйнують деякі загальноприйняті думки про дизайн SNARK.

**№ 1. SNARK великої площі – марна трата. Кожен повинен використовувати FRI, Ligero, Brakedown або інші варіанти, оскільки вони уникають методів еліптичних кривих, які зазвичай застосовуються до великих масштабів. **

Розмір поля тут приблизно відповідає розміру чисел у доказі SNARK. Оскільки додавання та множення дуже великих чисел є дорогим, ідея про те, що SNARK для великих полів є марнотратним, означає, що ми повинні прагнути до розробки протоколів, які ніколи не мають великих чисел. Зобов’язання на основі MSM використовують еліптичні криві, які зазвичай визначаються для великих полів (розміром ~2 256), тому ці обіцянки мають репутацію неефективних.

Те, чи є сенс використовувати малі поля (навіть якщо вони є опцією), значною мірою залежить від програми. Lasso і Jolt йдуть ще далі. Вони показують, що навіть із схемою зобов’язань на основі MSM робота прувера може бути майже незалежною від розміру поля. Це пояснюється тим, що для зобов’язань на основі MSM розмір прийнятих значень важливіший, ніж розмір полів, у яких ці значення знаходяться.

Існуючі SNARK змушують прувер виконувати багато випадкових елементів поля. Наприклад, засіб перевірки в популярному сервері SNARK під назвою Plonk фіксує близько 7 елементів випадкового поля (та інших невипадкових елементів поля) на вентиль схеми. Ці випадкові елементи поля можуть бути великими, навіть якщо всі значення, які з’являються в перевірених розрахунках, малі.

На відміну від цього, Lasso та Jolt вимагають від перевірки лише невелике значення (прівер Lasso також надсилає менше значень, ніж попередній параметр пошуку). Це значно покращує ефективність схем на основі ЧСЧ. Як мінімум Лассо та Джолт повинні розвіяти думку про те, що спільнота повинна відмовитися від зобов’язань, заснованих на ЧСЧ, у випадках, коли ефективність перевірки має значення.

**#2 Простіший набір інструкцій веде до швидшої zkVM. **

Складність Jolt (для кожної інструкції) залежить лише від вхідного розміру інструкції, доки таблиця оцінки для кожної інструкції розкладається. Jolt продемонстрував, що напрочуд складні інструкції розкладаються, особливо всі RISC-V.

Це суперечить поширеній думці про те, що простіші віртуальні машини (zkVM) обов’язково призводять до менших схем і пов’язаних із ними швидших перевірок (кожен крок віртуальної машини). Це керівна мотивація особливо простих zkVM, таких як Cairo VM, які спеціально розроблені для підтримки SNARK.

Фактично, для простіших віртуальних машин Jolt досягає нижчої вартості зобов’язань для перевірки, ніж попередні SNARK. Наприклад, для виконання Cairo VM засіб перевірки SNARK надсилає 51 елемент поля на кожному кроці VM. SNARK, розгорнуті Cairo, наразі працюють з 251-бітними полями (63 біти — жорстка нижня межа розміру поля, який може використовувати SNARK). Прувер Jolt працює з ~60 елементами полів на крок (визначаючи понад 64-бітні типи даних) для процесорів RISC-V. Після врахування того факту, що подані елементи поля малі, вартість перевірки Jolt приблизно еквівалентна вартості подання 6 випадкових 256-бітових елементів поля.

**#3 Розбиття великих обчислень на маленькі фрагменти не знижує продуктивність. **

Виходячи з цього погляду, сучасні проекти розкладають будь-яку велику схему на маленькі блоки, перевіряють кожен блок окремо та рекурсивно агрегують результати через SNARK. Ці розгортання використовують цей підхід для усунення вузьких місць у продуктивності популярних SNARK. Наприклад, SNARK на основі FRI потребують близько 100 ГБ простору для перевірки навіть для невеликих схем. Вони також потребують ШПФ, надлінійної операції, яка може стати вузьким місцем, якщо SNARK застосовуються «одночасно» до великих схем.

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

Прискорення Pippenger для ЧСЧ розміру n: покращення коефіцієнта log(n) порівняно з простим алгоритмом. Чим більше n, тим більше покращення.

У параметрах пошуку, таких як Lasso, перевірка сплачує «одноразову» вартість, яка залежить від розміру таблиці пошуку, але не має нічого спільного з кількістю значень, які шукаються. Одноразова вартість перевірки амортизується за всі пошуки в таблиці. Більші блоки означають більше пошуків, що означає кращу амортизацію.

Сьогодні популярний спосіб роботи з великими ланцюгами – розбивати речі на найменші частини. Основне обмеження розміру кожної частини полягає в тому, що вони не можуть бути настільки малими, щоб доказ рекурсивного агрегування став вузьким місцем для перевірки.

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

**#4 Обмеження висоти необхідні для ефективних SNARK. **

Jolt використовує R 1 CS як проміжне представлення. Немає ніякої користі від використання Height або Custom constraints у Jolt. Більша частина витрат на перевірку в Jolt полягає в пошуку параметра Lasso, а не в доведенні задовільності результуючої системи обмежень, яка сприймає пошук як належне.

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

Звичайно, деякі контексти все ще можуть виграти від висоти або спеціальних обмежень. Важливим прикладом є Minroot VDF, чиє 5-ступеневе обмеження може зменшити вартість зобов’язань приблизно в 3 рази.

**#5 Схеми зобов’язань із розрідженим поліномом є дорогими, і їх слід уникати, коли це можливо. **

Це основна критика щодо нещодавно представленої системи обмежень під назвою CCS та SNARK, які її підтримують - Spartan і Marlin, CCS є чітким узагальненням усіх систем обмежень, які поширені на практиці сьогодні.

Ця критика безпідставна. Насправді технічною основою Lasso and Jolt є розріджена поліноміальна схема зобов’язань у Spartan – Spark. Сам Spark є загальним перетворенням будь-якої (нерозрідженої) поліноміальної схеми зобов’язань у таку, яка підтримує розріджені поліноми.

Lasso оптимізує та розширює Spark, щоб гарантувати, що прувер використовує лише «малі» значення, але навіть без цих оптимізацій критика невиправдана. Фактично, прувер Spartan використовує менше (випадкових) елементів поля, ніж SNARK (наприклад, Plonk, який уникає розріджених поліноміальних зобов’язань).

Підхід Spartan має додаткові переваги продуктивності, особливо для схем із повторюваними структурами. Для цих схем додаткові ворота не додають до криптографічної роботи спартанського прувера. Ця робота зростає лише з кількістю змінних у даній системі обмежень, а не з кількістю обмежень. На відміну від Плонка, спартанським перевірникам не потрібно подавати кілька різних «копій» однієї змінної.

Ми оптимістично налаштовані, що Lasso та Jolt кардинально змінять спосіб розробки SNARK, покращивши продуктивність і можливість перевірки. Це ключовий інструмент із неймовірною здатністю мінімізувати витрати на перевірку.