Наш весьма субъективный взгляд на историю доказательств с нулевым знанием

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

1. Разнообразие вариантов применения.
2. Типы ограничений, которые мы имеем (относительно памяти, времени проверки, времени доказательства).
3. Необходимость в надежности (если одна система доказательств сломается, у нас останутся другие).

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

• Криптографические предположения: хэш-функции, устойчивые к столкновениям, проблема дискретного журнала над эллиптическими кривыми, знание экспонент.
• Прозрачная и доверенная настройка.
• Время работы провера: линейное и суперлинейное.
• Время работы верификатора: постоянное время, логарифмическое, сублинейное, линейное.
• Размер доказательства.
• Простота рекурсии.
• Схема арифметизации.
• Одномерные и многомерные полиномы.

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

Основы

Как мы уже говорили, доказательства с нулевым знанием не являются чем-то новым. Определения, основы, важные теоремы и даже важные протоколы были созданы в середине 1980-х годов. Некоторые из ключевых идей и протоколов, которые мы используем для создания современных SNARK, были предложены в 1990-х годах (протокол sumcheck) или даже до появления Биткойна (GKR в 2007 году). Основные проблемы с его внедрением были связаны с отсутствием мощного usecase (в 1990-х годах Интернет был не так развит), а также с количеством необходимой вычислительной мощности.

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

Область доказательств с нулевым знанием появилась в академической литературе благодаря статье Голдвассера, Микали и Рэкоффа. Чтобы узнать о происхождении, Вы можете посмотреть следующее видео. В статье вводятся понятия полноты, состоятельности и нулевого знания, даются конструкции для квадратичной остаточности и квадратичной неостаточности.

Протокол Sumcheck (1992)

Протокол sumcheck был предложен Лундом, Фортноу, Карлоффом и Нисаном в 1992 году. Это один из самых важных строительных блоков для лаконичных интерактивных доказательств. Это помогает нам свести требование о сумме оценок многомерного полинома к единственной оценке в случайно выбранной точке.

Гольдвассер-Калаи-Ротблюм (ГКР) (2007)

Протокол GKR - это интерактивный протокол, в котором проверяющий работает линейно по числу ворот схемы, а верификатор работает сублинейно по размеру схемы. В протоколе проверяющий и проверяемый договариваются об арифметической схеме fan-in-two над конечным полем глубины d, причем слой d соответствует входному слою, а слой 0 - выходному. Протокол начинается с утверждения относительно выхода схемы, которое сводится к утверждению относительно значений предыдущего уровня. Используя рекурсию, мы можем превратить это в утверждение над входами схемы, которое можно легко проверить. Эти сокращения достигаются с помощью протокола sumcheck.

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

Кейт, Заверуча и Голдберг представили в 2010 году схему обязательств для многочленов с использованием билинейной группы сопряжения. Обязательство состоит из единственного элемента группы, и коммиттер может эффективно открыть обязательство для любой правильной оценки многочлена. Более того, благодаря технике пакетной обработки, открытие может быть выполнено для нескольких оценок. Обязательства KZG стали одним из основных строительных блоков для нескольких эффективных SNARK, таких как Pinocchio, Groth16 и Plonk. Он также лежит в основе EIP-4844. Чтобы получить представление о технике пакетной обработки, Вы можете посмотреть наш пост о мосте Mina-Ethereum.

Практические SNARK с использованием эллиптических кривых

Первые практические конструкции для SNARK появились в 2013 году. Они требуют предварительной обработки для генерации доказывающего и проверяющего ключей и являются специфическими для программы/схемы. Эти ключи могут быть довольно большими и зависеть от секретных параметров, которые должны оставаться неизвестными сторонам; в противном случае они могли бы подделать доказательства. Преобразование кода в нечто, что можно доказать, требует компиляции кода в систему полиномиальных ограничений. Сначала это приходилось делать вручную, что отнимает много времени и чревато ошибками. Достижения в этой области позволили устранить некоторые из основных проблем:

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

Пиноккио (2013)

Пиноккио - первый практичный, пригодный для использования зк-СНАРК. SNARK основан на квадратичных арифметических программах (QAP). Изначально размер доказательства составлял 288 байт. Инструментарий Пиноккио предоставляет компилятор из кода на языке C в арифметические схемы, которые далее преобразуются в QAP. Протокол требует, чтобы верификатор генерировал ключи, которые зависят от схемы. Для проверки уравнений он использовал сопряжения эллиптических кривых. Асимптотика для генерации доказательства и установки ключа была линейной по объему вычислений, а время проверки было линейным по размеру открытых входов и выходов.

Грот 16 (2016)

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

Bulletproofs & IPA (2016)

Одним из слабых мест KZG PCS является то, что он требует доверенной настройки. Бутл и др. представили эффективную систему аргументов с нулевым знанием для открытий обязательств Педерсена, которые удовлетворяют отношению внутреннего продукта. Аргумент внутреннего продукта имеет линейный провор, с логарифмическими коммуникациями и взаимодействием, но с линейным временем проверки. Они также разработали полиномиальную схему обязательств, которая не требует доверенной установки. PCS, использующие эти идеи, применяются в Halo 2 и Kimchi.

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

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

Плонк представил новую схему арифметизации (позже названную Plonkish) и использование проверки большого произведения для ограничений на копирование. Plonkish также позволил внедрить специализированные ворота для определенных операций, так называемые пользовательские ворота. Несколько проектов имеют адаптированные версии 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 предлагает несколько улучшений, позволяющих избежать фиксации таблицы, если она имеет заданную структуру. Кроме того, провор Lasso платит только за записи в таблице, к которым обращаются при выполнении операций поиска. Jolt использует Lasso для подтверждения выполнения виртуальной машины с помощью поисковых запросов.

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

Spartan обеспечивает IOP для схем, описанных с помощью R1CS, используя свойства многомерных полиномов и протокол sumcheck. Используя подходящую полиномиальную схему обязательств, вы получаете прозрачный SNARK с проверкой за линейное время.

HyperPlonk (2022)

HyperPlonk развивает идеи Plonk, используя многомерные полиномы. Вместо котировок для проверки выполнения ограничений он использует протокол sumcheck. Он также поддерживает ограничения высокой степени без ущерба для времени работы провера. Так как он опирается на многомерные полиномы, нет необходимости выполнять БПФ, а время работы провера линейно по отношению к размеру схемы. 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, которая поддерживает ворота высокой степени и векторный поиск.

Использование хэш-функций, устойчивых к столкновениям

Примерно в то же время, когда был разработан Пиноккио, возникли идеи создания схем/арифметических схем, которые могли бы доказать правильность выполнения виртуальной машины. Несмотря на то, что разработка арифметизации виртуальной машины может быть более сложной или менее эффективной, чем написание специальных схем для некоторых программ, это давало то преимущество, что любую программу, независимо от ее сложности, можно было доказать, продемонстрировав, что она правильно выполняется в виртуальной машине. Идеи, заложенные в TinyRAM, были позже усовершенствованы при создании Cairo vm, а также последующих виртуальных машин (таких как zk-evms или zkvms общего назначения). Использование хэш-функций, устойчивых к столкновениям, устранило необходимость в доверенных установках или использовании операций с эллиптическими кривыми, но за счет более длинных доказательств.

TinyRAM (2013)

В SNARKs for C они разработали SNARK, основанный на PCP, чтобы доказать правильность выполнения программы на языке C, которая компилируется в TinyRAM, компьютер с сокращенным набором инструкций. В компьютере использовалась гарвардская архитектура с памятью с произвольным доступом на уровне байтов. Используя недетерминизм, размер схемы квазилинейно зависит от размера вычислений, эффективно обрабатывая произвольные и зависящие от данных циклы, поток управления и доступ к памяти.

STARKs (2018)

STARK были представлены Беном Сассоном и др. в 2018 году. Они достигают O(log2n)(log2)

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

Ligero (2017)

Лигеро представляет систему доказательств, которая позволяет получить доказательства, размер которых

O(√n), где n - размер схемы. Он представляет коэффициенты полинома в виде матрицы и использует линейные коды.
Brakedown основывается на Ligero и представляет идею полиномиальных схем обязательств, не зависящих от поля.

Некоторые новые разработки

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

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

С появлением эффективных SNARK, основанных на многомерных полиномах, таких как Spartan или HyperPlonk, возрос интерес к новым схемам обязательств, подходящим для этого типа полиномов. Binius, Zeromorph и Basefold предлагают новые формы для фиксации многолинейных полиномов. Преимущество Binius заключается в отсутствии накладных расходов на представление типов данных (в то время как многие системы доказательств используют как минимум 32-битные элементы поля для представления отдельных битов) и работе с двоичными полями. Это обязательство адаптирует систему brakedown, которая была разработана для того, чтобы не зависеть от условий эксплуатации. Basefold обобщает FRI на коды, отличные от кодов Рида-Соломона, что приводит к PCS, не зависящему от поля.

Настраиваемые системы ограничений (2023)

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

Заключение

В этом посте описываются достижения SNARK с момента их появления в середине 1980-х годов. Достижения в области компьютерных наук, математики и аппаратного обеспечения, а также внедрение блокчейна привели к появлению новых и более эффективных SNARK, открыв двери для множества приложений, которые могут изменить наше общество. Исследователи и инженеры предложили усовершенствования и адаптации SNARK в соответствии с их потребностями, уделяя особое внимание размеру доказательства, использованию памяти, прозрачной настройке, пост-квантовой безопасности, времени на проверку и времени на верификатор. Хотя изначально существовали две основные линии (SNARK и STARK), граница между ними начала стираться, пытаясь объединить преимущества различных систем доказательств. Например, комбинирование различных схем арифметизации с новыми схемами полиномиальных обязательств. Мы можем ожидать, что новые системы доказательств будут продолжать появляться, увеличивая производительность, и некоторым системам, которым требуется некоторое время на адаптацию, будет трудно идти в ногу с этими разработками, если мы не сможем легко использовать эти инструменты без необходимости изменения основной инфраструктуры.

Отказ от ответственности：

1. Эта статья перепечатана с сайта[lambdaclass], Все авторские права принадлежат автору оригинала[LambdaClass]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Отказ от ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.