1. Введение
ZK-SNARK — это система криптографических доказательств, которая позволяет организации доказать, что что-то верно, без раскрытия другой информации.
ZK-SNARK полезны во многих приложениях и областях, таких как блокчейн и проверяемые вычисления. Одно известное приложение блокчейна используется в ZK-Rollups.
ZK-Rollup — это блокчейны второго уровня, построенные поверх других блокчейнов (таких как Ethereum), которые используют ZK-SNARK (или другие системы криптографического доказательства) для доказательства достоверности переходов состояний. То есть каждый раз, когда производится новое обновление сети (добавляется новый пакет транзакций), вычисляется новое состояние сети и генерируется доказательство достоверности этого состояния. Дело в том, что для создания этого доказательства требуется только одна организация, и тогда любой может доверять его достоверности.
Желаемые свойства, предоставляемые ZK-Rollups, обычно включают (i) масштабируемость и/или (ii) защиту конфиденциальности. ZK-накопительные пакеты иногда называют накопительными пакетами эффективности, когда требуется только масштабируемость.
Для вычисления доказательств в ZK-Rollups, предназначенных для расширения EVM Ethereum, можно использовать ZK-EVM. Строго говоря, ZK-EVM — это набор криптографических программ (схем), отвечающих за генерацию доказательств с нулевым разглашением (ZKP), хотя иногда в разговорной речи он также относится к универсальному ZK-Rollup с поддержкой EVM в целом.
2. Определение ЗК-СНАРК
SNARK — это краткое доказательство того, что определенное утверждение верно. Формально он демонстрирует знание трассировки выполнения алгоритма, который дает правильное решение определенной проблемы. Скорее, он демонстрирует знание непубличных и непостоянных значений, которые выполняют отслеживание. Эти ценности в целом часто называют свидетелями. Элементы-свидетели, то есть части входных данных алгоритма, представляют собой независимые свидетели, поскольку они существуют до выполнения алгоритма и не определяются другими элементами трассировки выполнения. Открытое непостоянное значение трассировки выполнения, которое указывает экземпляр проблемы, которую решает алгоритм, называется общедоступным оператором.
ZK-SNARK означает краткий неинтерактивный аргумент с нулевым разглашением.
С – Простота
Простота — доказательство «короткое», а время проверки «быстрое»:
«Короткое» доказательство означает, что размер доказательства сублинейен по отношению к размеру свидетеля.
«Быстрое» время проверки означает, что время работы верификатора должно (i) быть сублинейным по размеру свидетеля и (ii) быть линейным по публичному заявлению.
Но на самом деле мы хотим, чтобы он был не только «кратким», но и «логарифмическим полиномиальным уровнем».
Это означает, что размер доказательства и время проверки практически не зависят от размера свидетеля.
Докажите, что размер π не должен расти быстрее, чем в несколько раз больше квадрата логарифма размера свидетеля w (при достаточно большом w):
Размер доказательства зависит от конкретного протокола ZK-SNARK. Для Plonky2 это O(log^2(|w|)), но это «худший» случай. Например, для классических PLONK и Groth16 размер доказательства равен O(1), что является константой.
Время проверки t_v должно быть не более чем на некоторое постоянное произведение квадрата логарифма свидетеля w и линейно зависеть от размера публичного объявления x (x и w достаточно велики, когда только один из них меняет свой размер).
N - Неинтерактивный - Генерация доказательства происходит без получения каких-либо данных от верификатора.
ARK — Доказательство знаний — аналогично обычным доказательствам, но достоверность справедлива только для полиномиально ограниченных доказывающих, тогда как в доказательствах достоверность справедлива для вычислительно неограниченных доказывающих. Мы обсудим концепцию звука в следующем разделе.
ЗК – Нулевое разглашение – Не раскрытие свидетелей.
3. Свойства ЗК-СНАРКов.
ZK-SNARK имеют три основных свойства, описанных ниже:
Полнота: если доказывающему известна правильная траектория выполнения алгоритма, то проверяющий должен полагать, что доказывающее обладает этими знаниями.
Надежность знаний: если доказывающий действительно не знает правильную траекторию выполнения, он не может убедить проверяющего, что он ее знает, но существует очень небольшая вероятность.
Нулевое разглашение: верификатор ничего не знает о траектории выполнения, кроме того, что она правильна.
4. Система доказательств PLONKish ZK-SNARK
4.1 Знакомство с PLONKish ZK-SNARK и их функциями
Чтобы быть примененной к определенному алгоритму, система доказательства ZK-SNARK должна знать систему уравнений на конечном поле. Эти уравнения описывают взаимосвязь между значениями в таблице траекторий выполнения алгоритма (таблица траекторий выполнения алгоритма). структура данных, в которой хранится траектория выполнения), чтобы гарантировать целостность вычислений. Язык, используемый для выражения этой системы уравнений (также называемой системой ограничений), называется арифметикой.
Система доказательства PLONKish ZK-SNARK использует арифметику с более высокой выразительной силой, чем старые системы доказательства. Первый позволяет использовать уравнения системы ограничений произвольной полиномиальной формы над переменными ограничения, тогда как для более старых систем доказательства (т.е. систем на основе R1CS) эти уравнения имели форму линейных и квадратичных полиномов. Эта функция позволяет системе доказательств PLONKish ZK-SNARK положительно влиять на вычислительную эффективность доказывающего устройства и упрощает ее применение к различным алгоритмам. Поэтому в последние годы появилось множество систем доказательств PLONKish ZK-SNARK, таких как классические PLONK, Halo2, Kimchi, Plonky2, HyperPlonk и др.
В Taiko мы используем вариант системы доказательств Halo2, основанный на схеме полиномиального обязательства KZG.
Система доказательств PLONKish ZK-SNARK состоит из трех компонентов:
4.2 План обязательств
Схема обещания позволяет коммиттеру публиковать значение, называемое обещанием, которое привязывает коммиттера к сообщению, не раскрывая само сообщение. Затем коммиттер может открыть обязательство и предоставить зафиксированное сообщение или некоторую его часть верификатору, который может проверить, соответствует ли предоставленная информация обязательству.
Разные авторы описывают разное количество алгоритмов, составляющих схему обязательства. Однако следует упомянуть как минимум четыре таких алгоритма:
Настройка: принимает некоторые исходные параметры в качестве входных данных и генерирует параметры настройки. Настройки определяют (i) что мы фиксируем (например, для схемы фиксации унарного полинома мы указываем область коэффициентов и максимальную степень полинома, который мы фиксируем) и (ii) уровень безопасности в битах. Мы можем просто определить уровень безопасности следующим образом: если для взлома системы шифрования требуется время O(2^n), то уровень безопасности системы шифрования составляет n бит.
Обещание: обещание, которое генерирует сообщения на основе заданных параметров.
Частичное открытие: генерирует доказательство частичного открытия, специфичное для выбранной части сообщения (например, значение зафиксированного унарного полинома для некоторого параметра), а также устанавливает параметры.
Проверка: используйте частично открытую аттестацию и задайте параметры, чтобы проверить, является ли информация, предоставляемая проверяющим, указанной частью сообщения, соответствующей указанному обязательству.
*Для некоторых схем фиксации алгоритмы «настройки» и «открытия» могут отсутствовать (например, при использовании хэш-функции для фиксации больших значений).
План обязательств должен иметь следующие характеристики:
Привязка: как только доказывающее устройство фиксирует конкретное сообщение, оно будет привязано к сообщению, которое оно передало;
Сокрытие: обещание не раскрывать никакой информации о сообщении. Сокрытие может быть идеальным, т. е. частично открытое доказательство не раскрывает никакой информации о незапрашиваемой части сообщения (например, обязательство KZG), или несовершенным, т. е. частично открытое доказательство раскрывает некоторую часть вышеупомянутой информации (например, сообщение на основе FRI). полиномиальное обязательство).
Схемы обязательств можно разделить на несколько типов в зависимости от целевого объекта: одноэлементное обязательство; полиномиальное обязательство;
Схемы полиномиальных обязательств — единственный тип, непосредственно используемый в системе доказательств PLONKish ZK-SNARK. Для вышеупомянутых систем доказательства (таких как классические PLONK, Halo2, Kimchi, Plonky2 и т. д.) очень важна схема одномерного полиномиального обязательства. Однако сейчас существует несколько новых методов PLONKish ZK-SNARK, основанных на схемах многолинейных полиномиальных обязательств (например, HyperPlonk).
4.3 Интерактивное доказательство Oracle
Интерактивное доказательство оракула — это интерактивное доказательство, в котором проверяющий имеет «доступ к оракулу» для получения сообщений доказывающего, может запрашивать их вероятностным образом и ему не нужно читать все сообщения доказывающего.
4.4 Эвристика Фиата-Шамира
Эвристика Фиата-Шамира обеспечивает способ преобразования интерактивных аргументов (публичных монет) в неинтерактивные аргументы. Интуитивно идея состоит в том, чтобы заменить случайный запрос валидатора хэшем предыдущего сообщения, но подробности обычно не уточняются.
*Протокол Public Coin — это протокол, в котором валидаторы отправляют только случайные элементы.
4.5 Принцип работы системы доказательств ZK-SNARK типа PLONK
В системе доказательств ZK-SNARK для доказательства знаний свидетеля используется модифицированный интерактивный метод доказательства Oracle, который использует полиномиальные обязательства для предоставления Oracle доступа к сообщению доказывающего и делает его неинтерактивным с помощью эвристики Фиата-Шамира. В этом разделе мы подробно объясним данный конструктор.
Напомним, что применение системы доказательств ZK-SNARK к алгоритму требует построения соответствующей системы ограничений. Чтобы иметь возможность его построить, определим структуру таблицы трассировки выполнения алгоритма и значения констант в ней. Мы используем термин «схема» для обозначения сложной структуры таблицы трассировки выполнения, заполненной только константами и соответствующей системой ограничений. Чтобы сгенерировать доказательство ZK-SNARK для экземпляра выполнения алгоритма, нам необходимо синтезировать для него экземпляр схемы, который является соответствующим экземпляром схемы алгоритма и таблицы трассировки выполнения (т. е. таблицы, в которой указаны константы, свидетели, и значения публичной декларации).
Давайте рассмотрим структуру таблицы отслеживания, используемой системой доказательств ZK-SNARK в стиле PLONK. Все столбцы в такой таблице относятся к одному из трех типов, которые мы называем согласно терминологии, используемой в Halo2, и описываем следующим образом:
Фиксированные столбцы – их ячейки содержат константы из таблицы трассировки выполнения;
Столбец экземпляра — используется для хранения значений публичного объявления;
Столбец предложения — где хранятся все данные-свидетели (включая значения независимых свидетелей и рассчитанные секретные результаты).
Подводя итог, отметим следующее:
Таблица трассировки выполнения (тип PLONKish) = фиксированные столбцы + столбцы экземпляров + столбцы предложений; схема = таблица трассировки выполнения, содержащая только константы + система ограничений; экземпляр схемы = схема + свидетели в своей таблице + общедоступные объявления в своей таблице; публичное заявление, значение независимого свидетеля) → Экземпляр схемы. Применить систему доказательств ZK-SNARK к определенному алгоритму = описать схему + определить процесс синтеза.
Почему термин «схема» широко используется в этом контексте? Изначально, когда были доступны только системы доказательств ZK-SNARK на базе R1CS, было удобно представлять систему ограничений в виде арифметической схемы, выходной сигнал которой должен быть равен нулю. Мы считаем, что в контексте PLONKish SNARKs термин «схема» используется по историческим причинам. В любом случае, давайте кратко рассмотрим арифметическую схему, используемую в старых версиях ЗК-СНАРК.
Арифметическая схема для SNARK на основе R1CS определяет полином с n-переменной над конечным полем и имеет схему оценки. Изначально он представляется в виде ориентированного ациклического графа (DAG):
Оно включает:
Открытый ввод x, используемый для указания значения публичного объявления;
Секретный вход w, используемый для указания значения независимого свидетеля;
Арифметические элементы, используемые для задания сложения и умножения в конечных полях.
Давайте рассмотрим пример арифметической схемы над полем рациональных чисел.
Начинаем снизу и работаем с самыми нижними воротами на схеме, т.е. (2 х 4 = 8) и (4 + 11 = 15), сохраняя эти значения как промежуточные;
Затем перемещаемся на одну строку вверх (на вторую строку) и вычисляем сумму двух промежуточных значений (полученных нами на предыдущем этапе), которая равна (8+15=23);
Поскольку у нас есть только три врата, и мы прошли через них все, наш окончательный результат — 23.
После того, как система доказательств PLONKish ZK-SNARK синтезирует экземпляр схемы, столбцы таблицы трассировки выполнения каждого экземпляра кодируются как полиномы по конечным полям следующим образом. Предположим, что C_j(x) — многочлен, описывающий столбец j, а ω — примитивный корень 2^k-го уровня, где k выбирается так, что 2^k немного больше начальной высоты экземпляра таблицы. Экземпляр таблицы заполняется случайными строками (только с ненулевыми ячейками в предложенных столбцах), которые содержат 2^k строк, а C_j(ω^i) устанавливается в значение i-й строки j-го числа. столбец данного экземпляра таблицы. Роль заполнения свойств с нулевым разглашением будет объяснена позже.
Утверждение «ω является примитивным корнем 2^k-го» означает, что ω^(2^k) = 1, и мы имеем ω^t ≠ 1 для любого положительного целого числа t меньше 2^k.
Система ограничений преобразуется в форму полиномиального уравнения путем замены переменных в ней соответствующими полиномами, полученными из полиномов столбца, путем замены x на «x, умноженное на ω, возведенное в некоторую степень».
Например, рассмотрим уравнение системы ограничений s(i) * (a(i) * b(i) - c(i+1)) = 0. Это означает, что если s(i) не равно нулю, то a(i) * b(i) должно равняться c(i+1). Здесь a, b и c — предлагаемые столбцы, s — фиксированный столбец, а i — текущий номер строки.
Это ограничение можно применить ко всем строкам длиной 2^k следующим образом. Пусть S(x), A(x), B(x) и C(x) — многочлены в столбцах a, b, c и s соответственно. Поэтому мы надеемся:
Это означает, что все элементы этого множества должны быть корнями S(x) * (A(x) * B(x) - C(x * ω)). Следовательно, этот многочлен должен делиться на:
Потому что ω — примитивный корень порядка 2^k.
Z(x) = x^(2^k) - 1 называется «исчезающим многочленом», поскольку он равен 0 для всех x, которые являются элементами циклической мультипликативной группы, порожденной ω. Следовательно, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 означает, что вышеуказанные ограничения выполняются для всех 2^k строк.
Предположим, P_0(x), P_1(x),..., P_m(x) — ограничения, применяемые ко всем 2^k строкам и соответствующие рассматриваемому многочлену S(x) * (A(x) * B(x) выше) - C(x * ω)) имеет аналогичный вид. Если α случайно выбран проверяющим из конечного поля, то
Это означает, что с чрезвычайно высокой вероятностью все эти ограничения выполняются для всех 2^k строк. Это уравнение означает, что мы можем найти фактор-многочлен T(x) такой, что
Следовательно, чтобы верификатор поверил, что доказывающему известно содержимое таблицы трассировки выполнения, удовлетворяющей всем m ограничениям с очень высокой вероятностью, нужно лишь доказать, что для случайно выбранного α доказывающая имеет вхождения P_0 (x), P_1(x),..., предлагаемые полиномы столбцов и фактор-полиномы T(x) в P_m(x) удовлетворяют этому полиномиальному уравнению. Верификатор может сделать это, попросив доказывающего найти значение данного многочлена в случайной точке, выбранной проверяющим из числа некорневых точек ζ из Z(x), и вычислить обе части этого уравнения в этой точке. ζ Я считаю, что доказывающий, вероятно, знает эти многочлены. Этот метод можно доказать с помощью леммы Шварца-Циппеля.
Чтобы сделать генерацию доказательства неинтерактивной, все случайные значения, генерируемые верификатором в интерактивной версии, должны быть получены с помощью эвристики Фиата-Шамира.
Чтобы связать доказывающее устройство с его полиномом предложения и фактор-полиномом T(x), используется схема полиномиального обязательства. Доказывающий берет на себя обязательства по этим полиномам, открывает эти обязательства на ζ (или на ζ * ω^q, если какое-то ограничение влияет на строки i и i + q) и создает доказательство, которое включает (I) эти обязательства, (II) Значение многочлена в точке ζ (или над ζ * ω^q, если необходимо) и (III) соответствующее открытое доказательство. Собственно, чтобы сделать доказательство короче, используйте множественное открытие, т.е. сгенерируйте небольшое доказательство для значений всех полиномиальных точек. Поэтому доказательство является кратким.
Чтобы удовлетворить свойству нулевого разглашения, случайно выбранные доказывающим строки добавляются к экземпляру таблицы трассировки выполнения, делая ее высоту равной 2^k строк. В этих строках есть только ненулевые ячейки в столбце предложений, поскольку только столбец предложений содержит данные, которые мы хотим скрыть. Сделайте это перед созданием полиномов столбца предложения, чтобы количество пар «значение параметра», обнаруженных в течение периода открытия обязательства, было меньше, чем количество случайно добавленных пар для каждого полинома. Следовательно, для каждого полинома столбца предложения объем информации, необходимый для его восстановления после открытия обязательства, больше, чем объем информации-свидетеля. Такая ситуация приводит к нулевому знанию.
На этапе предварительной обработки все экземпляры исполняющей схемы выполняют одни и те же вычисления, включая настройку и вычисление полиномов с фиксированным столбцом и их обязательств для схемы полиномиальных обязательств. Часть данных, полученных в результате этих вычислений, используется верификатором и часто называется ключом проверки. Аналогичным образом можно определить концепцию ключа доказательства. Базовая схема полиномиального обязательства определяет, выполняются ли настройки доверия на этапе предварительной обработки.