TL;DR
- ** Каков процесс создания SNARK? **
Проблемы, которые необходимо доказать-Арифметические схемы-R1CS-Полиномы
- **Зачем в конце концов конвертировать в многочлен? **
Благодаря характеристикам многочленов время проверки эффективно сокращается, и достигается простота.
- **Как добиться нулевого знания? **
Проще говоря, в процессе вывода многочлена выбираются еще два случайных числа, чтобы полученный многочлен мог помешать проверяющему получить коэффициенты исходного многочлена, то есть секретный ввод доказывающего, так что реализовать ЗК.
- **Как добиться невзаимодействия? **
Перед началом доказательства вводится третья сторона, то есть доверительная установка, которая назначает первоначальному верификатору задачу выбора случайных чисел доверенной настройке, тем самым реализуя невзаимодействие между верификатором и доказывающим.
За последние два года технология ZK привлекла большое внимание в сфере Web3. Начиная с Rollup, все больше и больше проектов на разных треках пытаются использовать технологию ZK. Среди них SNARK и STARK являются двумя наиболее часто встречающимися терминами.Чтобы лучше понять применение технологии ZK на более позднем этапе, **эта статья упростит логику доказательства SNARK с нетехнической точки зрения, а затем использовать * * Zk Rollup компании Scroll ** используется в качестве примера для иллюстрации работы системы проверки zk. **
Цель статьи состоит в том, чтобы объяснить основную логику, которая легко читается, она постарается избежать использования терминологии и не будет вдаваться в подробности, такие как математические преобразования, и, пожалуйста, простите меня за любые упущения.
В январе 2012 года Алессандро Кьеза, профессор Калифорнийского университета в Беркли, стал соавтором статьи о SNARK и предложил термин zk-SNARK.
zk-SNARK, полное название Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, представляет собой систему доказательств, использующую технологию ZK. **Следует отметить, что SNARK — это название класса схем, и существует множество различных методов комбинирования, которые могут реализовать SNARK. **
- Нулевое знание (Zero-Knowledge): Контент, который знает только доказывающий, будет скрыт, и никто, кроме доказывающего, не сможет его увидеть.
- Короткий (краткий): сгенерированное доказательство небольшое, а время проверки быстрое.
- Неинтерактивный (неинтерактивный): взаимодействие между доказывающим и проверяющим практически отсутствует.
- Аргумент: Проверка верификатора действительна только для доказывающего с ограниченной вычислительной мощностью, потому что доказывающий с супер-вычислительной мощностью может подделать доказательство, то есть система обладает вычислительной надежностью.
- Знание: доказывающий может вычислить доказательство только в том случае, если он знает некоторую информацию, которой не знает проверяющий.
Что zk-SNARK должен решить, так это «проблему проверки вычислений», то есть может ли верификатор эффективно проверить результаты вычислений, не зная конфиденциальности доказывающего.
Далее будет использоваться упрощенный процесс построения zk-SNARK, чтобы проиллюстрировать, как система объединяет нулевое знание для достижения эффективной проверки. **
Зк-СНАРК Строительство
Превратите проблему, которую нужно доказать, в полином
Проще говоря, идея SNARK состоит в том, чтобы преобразовать доказательство того, верно утверждение или нет, в доказательство того, верно или нет полиномиальное равенство.
Весь процесс преобразования: задачи для проверки ➡ арифметическая схема ➡ R1CS ➡ многочлен ➡ преобразование между многочленами
Вопрос на проверку➡Арифметическая схема
Чтобы доказать истинность вопроса с помощью вычислений, вопрос, который необходимо доказать, должен быть сначала преобразован в задачу вычисления, а любое вычисление может быть описано как арифметическая схема.
Арифметические схемы обычно состоят из констант, «элементов сложения» и «элементов умножения». Путем суперпозиции элементов мы можем построить сложные многочлены.
Полином, построенный арифметической схемой на рисунке выше, имеет вид: (Inp1+Inp2)*(-1) = Output
Задача на самом деле чрезвычайно сложна, чтобы превратить ее в арифметическую схему, мы можем просто понять это как: вводите некоторый контент, контент преобразуется схемой и, наконец, выводит результат. Прямо сейчас:
На основе концепции арифметических схем построим арифметическую схему для генерации доказательств, а именно:
Схема содержит два набора входов: общедоступный вход x и секретный вход w. Публичный ввод x означает, что содержание представляет собой фиксированное значение задачи, которое нужно доказать, которое известно как верификатору, так и доказывающему, а секретный ввод w означает, что содержание известно только доказывающему.
Арифметическая схема, которую мы построили, имеет вид C( x, w ) = 0, то есть ввод x и w через схему, а окончательный результат на выходе равен 0. Когда доказывающий и проверяющий знают, что выход схемы равен 0, а общедоступный вход равен x, доказывающему необходимо доказать, что он знает секретный вход w.
Арифметическая схема ➡R1CS
Наконец, нам нужен полином, но арифметическая схема не может быть напрямую преобразована в полином, а R1CS необходим в качестве посредника между ними, поэтому арифметическая схема сначала преобразуется в R1CS.
R1CS, полное название Rank-1 Constraints (система ограничений первого порядка), представляет собой язык описания схем, который по сути является матрично-векторным уравнением. В частности, R1CS — это последовательность трех векторов (a, b, c), а решением R1CS является вектор s, где s должен удовлетворять уравнению:
Среди них представляет операцию внутреннего продукта.
Конкретное математическое преобразование здесь можно найти в Vatalik: Quadratic Arithmetic Programs: from Zero to Hero
Нам нужно только знать, что роль **R1CS состоит в том, чтобы ограничить описание каждого элемента в арифметической схеме, чтобы векторы между каждым элементом удовлетворяли приведенному выше соотношению. **
R1CS➡Полиномиальный
Получив среду R1CS, мы можем преобразовать ее в полиномиальный эквивалент.
Эквивалентные преобразования между матрицами и полиномами могут быть выполнены, как показано на следующем рисунке:
многочлен
преобразовать в матрицу
В соответствии с характером приведенного выше эквивалентного преобразования для матрицы, удовлетворяющей R1CS, мы можем использовать метод интерполяции Лагранжа для восстановления каждого коэффициента полинома.На основе этого отношения мы можем вывести матрицу R1CS как полиномиальное соотношение, а именно:
Примечание: A, B, C представляют полином соответственно
Полином соответствует ограничению матрицы R1CS, соответствующему проблеме, которую мы хотим доказать.Благодаря приведенному выше преобразованию мы можем узнать, что если полиномы удовлетворяют приведенному выше соотношению, это означает, что наша матрица R1CS верна, что указывает на то, что доказывающая находится в арифметической схеме.Секретный ввод для также правильный.
До этого момента наша задача упрощалась: проверяющий случайным образом выбирает число x и просит удостоверяющего доказать, что A(x) * B(x)=C(x) истинно. Если это верно, то означает, что секретный ввод сертификатора верен.
Преобразование между полиномами
В сложных арифметических схемах есть десятки тысяч вентилей, и нам нужно проверить, удовлетворяет ли каждый вентиль ограничению R1CS. Иными словами, нам нужно несколько раз проверить равенство А(х) * В(х)=С(х), но эффективность раздельной проверки слишком мала Как проверить правильность всех вентильных ограничений при один раз секс?
Для удобства понимания введем P(x), пусть P(x) = A(x) * B(x) – C(x)
Мы знаем, что любой многочлен можно разложить на линейные многочлены, если он имеет решение. Итак, мы разделяем P(x) на F(x) и H(x), а именно:
Тогда F(x) является общедоступным, что означает, что существует H(x) = P(x)/F(x), поэтому полином, который мы хотим проверить, в конечном итоге превращается в:
A(x) * B(x) – C(x): Содержит коэффициенты полинома, известные только доказывающему, то есть секретный ввод.
F(x): общедоступный многочлен, известный как верификатору, так и доказывающему, т. е. общедоступный ввод.
H(x): доказывающий знает это посредством вычислений, но верификатор неизвестен.
**Последняя проблема, которую необходимо доказать, заключается в следующем: полиномиальное уравнение A(x) * B(x) – C(x) = F(x) * H(x) верно для всех x. **
Теперь достаточно один раз проверить полином, чтобы убедиться, что все ограничения удовлетворяют матричным соотношениям.
** Здесь мы завершили преобразование доказываемой задачи в многочлен, который нужно проверить только один раз, осознавая простоту системы. **
Но простота этой реализации заключается в сокращении времени проверки верификатора, так что насчет размера доказательства?
**Проще говоря, в протоколе доказательства используется древовидная структура Меркла, которая эффективно уменьшает размер доказательства. **
После завершения всего процесса конвертации естественно возникнут две проблемы:
- Зачем конвертировать в многочлен?
Потому что многочлены обеспечивают простоту доказательства. Проблема доказательства с нулевым разглашением заключается в проверке того, что вычисления удовлетворяют нескольким ограничениям, а полиномы могут проверять несколько ограничений в одной точке. Другими словами, верификатор должен проверить n раз, чтобы подтвердить проблему, но теперь ему нужно проверить только один раз, чтобы подтвердить правильность доказательства с высокой вероятностью.
- Почему два многочлена A(x) * B(x) – C(x )= F(x) * H(x) можно установить, проверив точку на многочлене?
Это определяется характеристиками многочленов, то есть результат вычисления многочлена в любой точке можно рассматривать как представление его однозначного тождества. Для двух полиномов они будут пересекаться только в конечном числе точек.
Для двух приведенных выше многочленов степени d: A(x) * B(x) – C(x) и F(x) * H(x), если они не равны, они будут не более чем d точек Пересекаются, то есть решения в d точках совпадают.
После завершения полиномиального преобразования мы перейдем к этапу полиномиального доказательства.
Докажите, что полином верен
Для иллюстрации воспользуемся многочленом Р(х) = F(x)*H(x).
Теперь проблема, которую хочет доказать доказывающая, заключается в следующем: для всех x P(x) = F(x) * H(x).
Процесс проверки вышеуказанного многочлена доказывающим и проверяющим выглядит следующим образом:
- Проверяющий выбирает случайную контрольную точку x, предполагая, что x = s;
- После того, как доказывающий получит s, вычислите P(s) и H(s) и передайте эти два значения проверяющему;
- Проверяющий сначала вычисляет F(s), затем вычисляет F(s) * H(s) и оценивает, верно ли F(s) * H(s) = P(s), и если оно истинно, проверка пройдена.
Но если мы хорошенько подумаем, то обнаружим, что в описанном выше процессе есть некоторые проблемы:
- Доказывающий может знать информацию обо всем уравнении.Если он получает случайную точку s, он может вычислить F(s), а затем построить пару ложных P(x) и H(x), так что P(s ) = F(s) * H(s), чтобы обмануть верификатора.
- Доказывающий не использует s, данные верификатором, для вычисления F(s) и H(s), а вычисляет с другими значениями, чтобы обмануть верификатора.
- Значение, полученное верификатором, рассчитывается на основе общедоступного ввода и частного ввода доказывающего.Если верификатор обладает большой вычислительной мощностью, он может взломать приватный ввод доказывающего.
Для решения вышеперечисленных проблем проведем следующие оптимизации:
- После того, как верификатор выбирает случайную точку s, он выполняет гомоморфное шифрование на s. Гомоморфное шифрование означает решение, вычисленное после шифрования, = решение, зашифрованное после вычисления; в этой форме шифрования доказывающий может вычислить решение, но не может построить ложные P(x) и H(x).
- Когда верификатор выбирает контрольную точку s, выбирается другой случайный параметр λ для создания дополнительной линейной зависимости между s и λ. Верификатор отправляет s и λ после гомоморфного шифрования доказывающему. Доказывающая сторона отправляет доказательство обратно, а верифицирующая сторона должна проверить взаимосвязь между случайным параметром λ и s в дополнение к проверке истинности доказательства.
- ** Чтобы решить проблему, связанную с тем, что верификатор может взломать секретный ввод, мы можем ввести ZK. ** Глядя на все доказательство, мы можем обнаружить, что в процессе проверки доказывающая сторона только отправляет вычисленное значение полинома проверяющей стороне, а верифицирующая сторона может вывести коэффициент полинома через значение, которое является секретным входом проверяющей стороны. прувер Чтобы предотвратить отталкивание верификатора, мы можем выбрать еще два случайных числа и добавить набор значений при выводе полиномов A, B и C из R1CS, чтобы восстановленный полином был на один порядок больше, чем исходный полином. , так что проверка Читатель не может получить информацию об исходном многочлене из зашифрованного многочлена для реализации ZK.
После оптимизации мы обнаружили, что система доказательств по-прежнему требует взаимодействия между верификатором и доказывающим, как добиться невзаимодействия?
Реализовать неинтерактивный формат
** Чтобы добиться невзаимодействия, SNARK вводит доверенные настройки (Setup). **
Другими словами, перед началом доказательства право верификатора на выбор случайных контрольных точек передается доверенной третьей стороне, которая после выбора случайного параметра λ помещает зашифрованную λ в цепь R1CS. Таким образом, создается CRS (Common Reference String, общедоступная справочная строка). Верификатор может получить свой собственный Sv от CRS, а доказывающий может получить свой собственный Sp от CRS.
Следует отметить, что λ необходимо уничтожить после создания Sv и Sp.Если λ просочился, он может быть использован для подделки транзакций путем ложной проверки.
Рабочий процесс zk-SNARK
После понимания процесса построения SNARK на основе построенной нами арифметической схемы, которая может генерировать доказательства, процесс доказательства zk-SNARK выглядит следующим образом:
- Настройка: (контур C, λ)= (Sv, Sp)
С помощью схемы C и случайного параметра λ генерируются случайные параметры Sv и Sp, используемые последующими доказывающими и проверяющими.
Доказывающая сторона вычисляет доказательство Π через случайный параметр Sp, общедоступные входные данные x и секретные входные данные w.
- Проверить(Sv,x,Π) == (∃ w st C(x,w))
Верификатор проверяет, существует ли C(x,w)=0 с помощью случайного параметра Sv, общедоступных входных данных x и доказательства Π. В то же время проверьте, вычисляется ли доказательство по схеме C или нет.
На этом мы закончили объяснение всего zk-SNARK, давайте взглянем на реальный случай применения.
Кейс: в качестве примера возьмем zk Rollup от Scroll
Роль системы доказательств состоит в том, чтобы позволить доказывающему убедить проверяющего поверить в одну вещь;
Для системы zk-доказательства нужно заставить проверяющего поверить в то, что доказательство с нулевым разглашением (доказательство с нулевым разглашением), рассчитанное с помощью алгоритма zk, верно.
В качестве примера мы используем zk Rollup от Scroll, чтобы проиллюстрировать работу системы проверки zk.
Сведение относится к расчету вне сети и проверке в сети. Для zk Rollup после выполнения транзакции вне цепочки доказывающая сторона должна сгенерировать сертификат zk для нового корня состояния, сгенерированного после выполнения транзакции, а затем передать сертификат контракту L1 Rollup для проверки в цепочке.
Следует отметить, что в zk Rollup есть два типа блоков:
- Блок L1 Rollup: блок, отправленный в Ethereum.
- Блок L2: блок, состоящий из транзакций, отправленных пользователями на L2.
Ниже приведен рабочий процесс Scroll’s zk Rollup:
- Пользователь инициирует транзакцию в L2, Sequencer извлекает транзакцию, выполняет транзакцию вне сети и генерирует блок L2 и новый корень состояния; в то же время отправляет данные транзакции и новый корень состояния в контракт Rollup на Ethereum (предоставление данных о транзакциях для доступности данных);
- Когда блок L2 сгенерирован, Координатор получит трек исполнения блока от Секвенсора, а затем случайным образом назначит трек любому Роллеру;
- Роллер преобразует полученный трек исполнения в схемы и генерирует сертификат действительности для каждой схемы, а затем отправляет сертификат обратно Координатору;
- Каждый раз, когда генерируется k блоков L2, координатор отправляет задачу агрегации другому ролику для объединения доказательств k блоков в одно агрегированное доказательство;
- Координатор отправляет одно доказательство агрегации в контракт агрегации, а контракт агрегации проверяет доказательство агрегации в сочетании с ранее отправленным корнем состояния и данными транзакции.Если проверка проходит успешно, соответствующий блок считается завершенным при прокрутке.
Как видно из приведенного выше процесса, Roller является проверяющим в системе, а контракт Rollup — верификатором. Roller генерирует доказательство zk для транзакций, выполненных вне сети; контракт Rollup проверяет доказательство, и если проверка проходит успешно, контракт Rollup напрямую примет отправленный корень состояния в качестве своего нового корня состояния.
