Подробно объясните два новых инструмента SNARK, запущенных криптовалютой a16z.

Эта статья взята из 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 решают все три ключевые проблемы: производительность, удобство для разработчиков и возможность аудита, и вместе они реализуют концепцию поиска сингулярности. Лассо и Джолт также заставляют переосмыслить большую часть принятой мудрости в дизайне SNARK.

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

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

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

Я имею в виду работу по доказыванию полиномиальной схемы обязательств как стоимость обязательства. ** SNARK требует дополнительных затрат на доказательство полиномиальных схем обязательств. Но затраты на обязательства часто являются узким местом. ** Лассо и Толчок также. Если SNARK разработан таким образом, что стоимость обязательства не является основной стоимостью доказывания, это не означает, что схема полиномиального обязательства дешева. Скорее, это означает, что другие затраты выше, чем они должны быть.

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

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

Вычисление обязательств включает в себя многократное возведение в степень (также известное как множественное скалярное умножение или MSM) или БПФ и хэши Меркла, в зависимости от используемой полиномиальной схемы обязательства. Lasso и Jolt могут использовать любую полиномиальную схему обязательств, но имеют особенно привлекательную стоимость при реализации с использованием схем на основе MSM, таких как IPA/Bulletproofs, KZG/PST, Hyrax, Dory или Zeromorph.

Почему Lasso и Jolt важны

Лассо — это новый параметр поиска, где доказывающий обещает все меньше и меньше значений, чем предыдущая работа. Это может быть ускорение в 20 раз или более, где ускорение от 2 до 4 раз связано с меньшим количеством зафиксированных значений, а еще одно ускорение в 10 раз связано с тем, что все зафиксированные значения в Lasso малы. В отличие от многих предыдущих параметров поиска, Lasso (и Jolt) также избегают БПФ, которые занимают много места и могут быть узким местом для больших экземпляров.

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

Лассо использует две разные структурные концепции: разложимость и структуры LDE. (LDE — это аббревиатура технической концепции, называемой расширенным полиномом низкой степени.) Разложимость примерно означает, что ответ на один поиск в таблице можно получить, выполнив меньшее количество поисков в меньшей таблице. Это более строгое требование, чем структура LDE, но Lasso особенно эффективен при применении к разложимым таблицам.

Толчок

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

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

Пересмотр общепринятой мудрости в дизайне SNARK

Лассо и Джолт также ниспровергают некоторые общепринятые принципы дизайна SNARK.

** № 1. SNARK большой площади — пустая трата времени. Все должны использовать FRI, Ligero, Brakedown или их варианты, поскольку они избегают методов эллиптических кривых, которые обычно применимы к большим масштабам. **

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

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

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

Напротив, Lasso и Jolt требуют от доказывающего только небольшого значения (доказательство Lasso также отправляет меньше значений, чем предыдущий параметр поиска). Это значительно повышает производительность схем на основе MSM. Как минимум, Лассо и Джолт должны разрушить представление о том, что сообщество должно отказаться от обязательств, основанных на МСМ, в тех случаях, когда эффективность прувера имеет значение.

** # 2 Более простой набор инструкций приводит к более быстрой работе zkVM. **

Сложность Jolt (для каждой инструкции) зависит только от размера входных данных инструкции, если таблица оценки для каждой инструкции является разложимой. Джолт продемонстрировал, что удивительно сложные инструкции можно разложить, особенно все RISC-V.

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

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

**#3 Разбиение больших вычислений на маленькие фрагменты не приводит к снижению производительности. **

Основываясь на этом представлении, сегодняшние проекты разбивают любую большую схему на небольшие блоки, проверяют каждый блок отдельно и рекурсивно агрегируют результаты с помощью SNARK. Эти развертывания используют этот подход для устранения узких мест производительности в популярных SNARK. Например, для SNARK на основе FRI требуется около 100 ГБ пространства для проверки даже для небольших цепей. Они также требуют БПФ, ультралинейной операции, которая может стать узким местом, если SNARK применяются «одновременно» к большим схемам.

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

Ускорение Пиппенджера для MSM размера n: улучшение в логарифмическом ( n ) раз по сравнению с наивным алгоритмом. Чем больше n, тем больше улучшение.

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

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

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

**#4 Ограничения по высоте необходимы для эффективных SNARK. **

Jolt использует R 1 CS в качестве своего промежуточного представления. Нет никакой пользы от использования ограничений высоты или пользовательских ограничений в Jolt. Большая часть стоимости доказывающего в Jolt заключается в поиске параметра Lasso, а не в доказательстве выполнимости полученной системы ограничений, которая принимает поиск как должное.

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

Конечно, некоторые контексты могут по-прежнему выигрывать от высоты или пользовательских ограничений. Важным примером является Minroot VDF, чье 5-градусное ограничение может снизить стоимость обязательств примерно в 3 раза.

**#5 Схемы разреженных полиномиальных обязательств являются дорогостоящими, и их следует избегать, когда это возможно. **

Это основная критика в адрес недавно введенной удерживающей системы под названием CCS и поддерживающих ее СНАРКов - Spartan и Marlin, CCS является явным обобщением всех распространенных сегодня на практике удерживающих систем.

Эта критика необоснованна. Фактически, техническим ядром Lasso и Jolt является разреженная полиномиальная схема фиксации в Spartan — Spark. Сама Spark представляет собой универсальное преобразование любой (не разреженной) схемы фиксации полиномов в схему, поддерживающую разреженные полиномы.

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

Подход Spartan имеет дополнительные преимущества в производительности, особенно для схем с повторяющимися структурами. Для этих схем дополнительные вентили не увеличивают криптографическую работу спартанского доказывающего. Эта работа растет только с увеличением количества переменных в данной системе ограничений, а не с количеством ограничений. В отличие от Plonk, спартанским пруверам не нужно отправлять несколько разных «копий» одной и той же переменной.

Мы с оптимизмом смотрим на то, что Lasso и Jolt кардинально изменят способ разработки SNARK, улучшив производительность и проверяемость. Это ключевой инструмент со сверхъестественной способностью свести к минимуму затраты на выполнение обязательств испытателя.