Особая благодарность Ben Wan, Matthew Finestone, и Brecht Devos за отзывы и рецензии.
Введение
Определение ZK-SNARK
Свойства ZK-SNARKs
Системы доказательств ZK-SNARK PLONKish
3.1 ZK-SNARK ПЛОНКИША вкратце и их роль
3.2 Схемы обязательств
3.3 Interactive Oracle Proof
3.4 Эвристика Фиата-Шамира
3.5. Как работают системы доказательств PLONKish ZK-SNARK
3.6 Немного о расширенных аспектах PLONKish ZK-SNARK
Ссылки
ZK-SNARK - это криптографическая система доказательства. Она позволяет доказать правдивость какого-либо утверждения без раскрытия другой информации.
ZK-SNARKs полезны в нескольких областях и приложениях, таких как блокчейн и проверяемая вычислительная техника. Одним из ярких примеров применения блокчейна является ZK-Rollups.
ZK-Rollups - это layer-2 блокчейны, построенные на основе других блокчейнов (например, Ethereum), которые используют ZK-SNARKs (или другие криптографические системы доказательств) для подтверждения правильности переходов состояния. То есть, при каждом новом обновлении сети (когда добавляется новый пакет транзакций), вычисляется новое состояние сети и генерируется доказательство его правильности. Важно отметить, что только одно существо должно сгенерировать это доказательство, после чего кто угодно может убедиться в его правильности.
Желаемые свойства, которые обеспечивают ZK-Rollups, обычно связи с (i) масштабируемостью и/или (ii) сохранением конфиденциальности. Когда масштабируемость - единственное желаемое свойство, ZK-Rollups иногда называются validity rollups.
Для вычисления доказательства в ZK-Rollups, предназначенных для масштабирования Ethereum EVM, используется ZK-EVM. По строгому определению, ZK-EVM - это набор криптографических программ (цепей), которые отвечают за генерацию доказательства Zero-Knowledge Proof (ZKP), хотя иногда в переносном смысле относится ко всему универсальному ZK-Rollup, поддерживающему EVM.
В этой статье мы подробно рассмотрим, что такое ZK-SNARK и как он работает.
SNARK - это краткое доказательство правдивости утверждения. Формально оно доказывает знание следов выполнения алгоритма, который дает правильное решение определенной проблемы. Более точно, оно подтверждает знание неоткрытых и неизменных значений следа выполнения. Эти значения в целом обычно называются свидетельством. Элементы свидетельства, которые являются частями входа алгоритма, составляют независимые свидетельства, поскольку они существуют до выполнения алгоритма и не определяются другими элементами следа выполнения. Публичные неизменные значения следа выполнения, которые определяют экземпляр проблемы, решенный алгоритмом, мы называем открытыми утверждениями.
ZK-SNARK означает Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.
S - краткое
Краткое означает, что доказательство должно быть «коротким», а время проверки - «быстрым»:
«Коротким» доказательством означает, что размер доказательства является сублинейным относительно размера свидетельства.
"Быстрое" время проверки означает, что время работы верификатора должно быть (i) сублинейным по отношению к размеру свидетеля и (ii) линейным по отношению к публичному заявлению.
Но на самом деле мы хотим, чтобы он был не просто "кратким", а "полилогарифмическим".
Это означает, что размер доказательства и время проверки практически не зависят от размера свидетеля.
1. Размер доказательства π не рсти быстрее, чем некоторая константа, умноженная на квадрат логарифма размера свидетельства w (для достаточно большого w):
Размер доказательства зависит от конкретного протокола ZK-SNARK. Для Plonky2 он составляет O(log^2(|w|), но это "худший" случай. Например, для классических протоколов PLONK и Groth16 размер доказательства составляет O(1), т.е. константу.
2. Время проверки t_v должно расти не быстрее, чем некоторая константа, умноженная на квадрат логарифма размера свидетеля w, и линейно зависеть от размера открытого высказывания x (для достаточно больших x и w, когда только один из них меняет свой размер):
N - Non-Interactive - генерация доказательства выполняется без получения каких-либо данных от проверяющего.
ARK - Argument of Knowledge - аналогично обычному доказательству, но обоснованность сохраняется только для полиномиально ограниченного проверяющего, в то время как в доказательстве обоснованность сохраняется для вычислительно неограниченного проверяющего. Понятие состоятельности мы обсудим в следующем разделе.
ZK - Zero-Knowledge - неразглашение информации о свидетеле.
Существует три основных свойства ZK-SNARK, которые рассматриваются ниже.
Полнота: Если проверяющий знает правильный след выполнения алгоритма, то проверяющий должен быть убежден, что проверяющий обладает этим знанием.
Достоверность знаний: Доказатель может убедить верификатора в том, что знает правильный след выполнения, только если он действительно знает его, за исключением некоторой очень малой вероятности.
Нулевое знание: Проверяющий не знает о трассе выполнения ничего, кроме того, что она верна.
Чтобы быть примененной к некоторому алгоритму, система доказательства ZK-SNARK должна знать систему уравнений над конечным полем, которые описывают отношения между значениями в таблице трассы выполнения этого алгоритма (структура данных для хранения трассы выполнения) способом, достаточным для гарантии целостности вычислений. Язык, используемый для выражения этой системы уравнений (также называемой системой ограничений), называется арифметизацией.
Системы доказательств PLONKish ZK-SNARK используют арифметизации с большей выразительной силой по сравнению со старыми системами доказательств. Первые позволяют использовать уравнения системы ограничений в виде произвольных полиномов от ограниченных переменных, в то время как в старых системах доказательств (т.е. основанных на R1CS) эти уравнения имеют вид линейных и квадратичных полиномов. Эта особенность систем доказательства PLONKish ZK-SNARK благотворно влияет на эффективность вычислений проверяющего и облегчает применение ZK-SNARK к различным алгоритмам. В результате, в последнее время появилось множество PLONKish ZK-SNARK доказательных систем: классический PLONK, Halo2, Kimchi, Plonky2, HyperPlonk и др.
В Taiko мы используем вариант системы доказательств Halo2, основанный на полиномиальной схеме обязательств KZG.
Система доказательств PLONKish ZK-SNARK состоит из трех компонентов:
Ниже мы подробно рассмотрим каждый компонент.
Схема обязательств позволяет пользователю опубликовать значение, называемое обязательством, которое связывает пользователю с сообщением, не раскрывая его. Позже человек может открыть обязательство и раскрыть обязательство или некоторую его часть верификатору, который может проверить, что раскрытая информация соответствует обязательству.
Разные авторы описывают разное количество алгоритмов, составляющих схему обязательств. Однако мы должны упомянуть, по крайней мере, четыре из них:
Установка: принимает некоторые начальные параметры в качестве входных и генерирует параметры установки. Установка определяет (i) какие объекты мы берем на себя обязательства (например, для схем обязательств с одномерными полиномами мы указываем поле коэффициентов и максимальную степень для полиномов, которые мы берем на себя обязательства) и (ii) уровень безопасности в битах. Мы можем кратко определить уровень безопасности следующим образом: криптосистема имеет n-битный уровень безопасности, если ее взлом требует O(2^n) времени.
Commit: производит обязательство сообщения в соответствии с параметрами установки.
Частичное открытие: производит частичное доказательство вскрытия, специфичное для выбранной части сообщения (например, значение фиксированного одномерного многочлена для некоторого аргумента) и установочных параметров.
Проверка: использует доказательство частичного вскрытия и параметры установки для проверки того, является ли информация, раскрытая проверяющим, указанной частью сообщения, которая соответствует указанному обязательству.
*Для некоторых схем обязательств алгоритм "установки" и "открытия" может отсутствовать (например, в случае использования хэш-функции для фиксации больших чисел).
Схема обязательств должна обладать следующими свойствами:
Связывание: как только проверяющий принял на себя обязательство по конкретному сообщению, он привязывается к сообщению, по которому принял обязательство;
Скрытие: обязательство не раскрывает ничего о сообщении. Скрытие может быть совершенным, когда доказательство частичного открытия не раскрывает никакой информации о невопрошаемой части сообщения (например, обязательства KZG), или несовершенным, когда доказательство частичного открытия раскрывает некоторую часть вышеупомянутой информации (например, полиномиальные обязательства на основе FRI).
Схемы обязательств можно разделить на несколько типов в соответствии с целевыми объектами:
Одноэлементные обязательства;
Множественные обязательства;
Векторные обязательства;
Полиномиальные обязательства.
Полиномиальные схемы обязательств - единственный тип, который непосредственно используется в системах доказательства PLONKish ZK-SNARK. Одномерные полиномиальные схемы обязательств имеют большое значение для вышеупомянутых систем доказательства (например, классический PLONK, Halo2, Kimchi, Plonky2 и т.д.). Однако в настоящее время появляются некоторые новые подходы к ZK-SNARK PLONKish, основанные на многолинейных полиномиальных обязательствах (например, HyperPlonk).
Для формального и подробного объяснения схемы обязательств вы можете прочитать эту статью Аникета Кейта, Грегори М. Заверуча и Яна Голдберга. Также в ней представлена полиномиальная схема обязательств KZG, используемая как в классическом PLONK, так и в варианте Halo2, используемом Taiko.
Для формального и подробного объяснения полиномиальной схемы обязательств вы можете ознакомиться с этой статьей Александра Власова и Константина Панарина.
Интерактивное Oracle Proof - это интерактивное доказательство, в котором проверяющий имеет "oracle access" к сообщениям проверяющего, может вероятностно запрашивать их и не обязан читать все сообщение проверяющего.
Формальное и подробное объяснение Interactive Oracle Proof (IOP) можно найти в этой статье Эли Бен-Сассона, Алессандро Кьеза и Николаса Спунера.
Fiat-Shamir heuristic предоставляет способ преобразования интерактивного аргумента (публичных монет) в non-interactive аргумент. Интуитивно понятно, что идея состоит в том, чтобы заменить случайные вызовы проверяющего хэшем предыдущих сообщений проверяющего, но точные детали обычно не уточняются.
Протокол *Public-coin - это протокол, в котором верификатор посылает только случайные элементы.
В системах доказательства ZK-SNARK знание свидетеля доказывается с помощью модифицированного подхода Interactive Oracle Proof, который использует полиномиальные обязательства для обеспечения доступа оракула к сообщению проверяющего и делается неинтерактивным с помощью Fiat-Shamir Heuristic. В этом разделе мы подробно объясним данную конструкцию.
Напомним, что применение системы доказательств ZK-SNARK к некоторому алгоритму требует построения соответствующей системы ограничений. Чтобы иметь возможность ее построить, мы определяем структуру таблицы трассировки выполнения для данного алгоритма и значения констант в ней. Мы используем термин "circuit" для обозначения совокупности таблицы трассировки выполнения, заполненной только константами и соответствующей системой ограничений. Чтобы сгенерировать ZK-SNARK доказательство для экземпляра выполнения некоторого алгоритма, необходимо синтезировать для него экземпляр схемы, который представляет собой схему алгоритма с соответствующим экземпляром таблицы трассировки выполнения (т.е. таблицы, в которой заданы значения констант, свидетелей и публичных утверждений).
Рассмотрим структуру таблиц трассировки, используемых в системах доказательства PLONKish ZK-SNARK. Все столбцы в такой таблице принадлежат к одному из трех типов, которые мы называем в соответствии с терминологией, используемой в Halo2, и описываем следующим образом:
Фиксированные столбцы - их ячейки содержат константы таблицы трассировки выполнения;
Колонки экземпляров - они используются для хранения значений публичных утверждений;
Колонки Advice - в них хранятся все свидетельские данные (включая независимые свидетельские значения и секретные результаты вычислений).
Подводя итог, отметим следующее:
Таблица трассировки выполнения (PLONKish) = фиксированные колонки + колонки экземпляров + колонки советов;
Контур = таблица трассировки исполнения, заполненная только константами + система ограничений;
Экземпляр схемы = схема + свидетель в ее таблице + публичное утверждение в ее таблице;
Синтез: (схема, публичное утверждение, независимые значения свидетелей) → экземпляр схемы;
Применение системы доказательства ZK-SNARK к некоторому алгоритму = описание схемы + определение процедуры синтеза.
Почему термин "схема" широко используется в данном контексте? Первоначально, когда были доступны только системы доказательств ZK-SNARK на основе R1CS, было удобно представлять систему ограничений в виде арифметической схемы над конечным полем, выход которой должен быть равен нулю. Мы утверждаем, что термин "схема" в контексте ПЛОНКИШ СНАРК используется скорее по историческим причинам. В любом случае, давайте кратко рассмотрим арифметические схемы, используемые для старых ZK-SNARK.
Арифметическая схема, используемая для ЗК-СНАРК на базе R1CS, определяет n-переменный многочлен над конечным полем с рецептом оценки. Первоначально он представлен в виде направленного ациклического графа (DAG):
Это включает в себя
Открытые входы x, которые используются для указания значений публичных показаний;
секретные входы w, которые используются для указания значений независимых свидетелей;
Арифметические ворота, которые обозначают сложение и умножение над конечным полем.
Рассмотрим пример арифметической схемы над полем рациональных чисел.
Мы начинаем снизу графа с самых низких ворот, то есть (2 x 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, которое меньше 2^k, имеем ω^t ≠ 1.
Система ограничений преобразуется в форму полиномиального уравнения путем замены переменных в ней на соответствующие полиномы, полученные из полиномов столбца путем замены "x умножить на ω до определенной степени" на x.
Например, рассмотрим уравнение системы ограничений s(i) * (a(i) * b(i) - c(i+1)) = 0. Это означает, что a(i) * b(i) должно быть равно c(i+1), если s(i) ненулевое. Здесь 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), ... , P_m(x)) и полином котировки T(x), которые удовлетворяют этому полиномиальному уравнению. Верификатор может убедиться в том, что проверяющий с большой вероятностью знает эти многочлены, спросив у проверяющего значения данных многочленов в случайной точке ζ, которая выбирается верификатором среди некорней Z(x), и оценив обе стороны этого уравнения в точке ζ. Этот подход может быть обоснован с помощью леммы Шварца-Циппеля.
Чтобы сделать генерацию доказательства non-interactive, все случайные значения, которые будут генерироваться верификатором в интерактивной версии, должны быть получены с помощью эвристики Fiat-Shamir heuristic.
Для привязки проверяющего к его рекомендательным полиномам и полиномам коэффициента T(x) используется схема полиномиальных обязательств. The prover принимает на себя обязательства по этим полиномам, открывает эти обязательства на ζ (и ζ * ω^q, если некоторые ограничения затрагивают строки i и i + q) и создает proof, которое состоит из (I) этих обязательств, (II) значений полиномов на ζ (и ζ * ω^q, если это требуется) и (III) соответствующих открывающих proofs. На самом деле, чтобы сделать доказательство короче, используется мультиоткрытие, т.е. мы генерируем один маленький proof для значений всех точек многочленов. Таким образом, доказательство получается лаконичным.
Чтобы удовлетворить свойству нулевого знания, строки, случайно выбранные проверяющим, добавляются к экземпляру таблицы трассировки выполнения, чтобы сделать ее высотой в 2^k строк. Эти строки имеют ненулевые ячейки только в столбцах рекомендаций, поскольку только столбцы рекомендаций содержат данные, которые мы скрываем. Это делается перед построением полиномов столбцов советов, чтобы количество пар "аргумент-значение", которые раскрываются во время открытия обязательств, было меньше количества случайно добавленных пар для каждого из этих полиномов. Таким образом, для каждого полинома столбца советов количество информации, необходимой для его восстановления, больше, чем количество информации свидетелей даже после вскрытия обязательств. Это обстоятельство приводит к нулевому знанию.
Некоторые вычисления, одинаковые для всех экземпляров схемы, выполняются на этапе предварительной обработки. Они включают в себя настройку схем полиномиальных обязательств и вычисление полиномов фиксированного столбца, а также обязательств для них. Часть данных, полученных в результате этих вычислений, которая используется верификатором, часто называется ключом верификации. Аналогичным образом можно определить понятие ключа доказательства. Лежащая в основе схемы полиномиальных обязательств схема определяет, выполняется ли доверенная установка на этапе предварительной обработки.
Некоторые более продвинутые аспекты PLONKish SNARKs здесь не рассматриваются, а именно:
Ограничения копирования: т.е. чтобы i-я ячейка столбца a была равна j-й ячейке столбца b;
Ворота поиска: гарантия того, что значения определенных ячеек строки принадлежат некоторому множеству. Представление об этих темах требует понимания материала, описанного выше. Более подробную информацию можно найти здесь и здесь.
ZK-EVM on Rollup-glossary.vercel.app
Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg, Constant-Size Commitments to Polynomials and Their Applications
Dan Boneh, Building a SNARK
Alexander Vlasov, Konstantin Panarin, TRANSPARENT POLYNOMIAL COMMITMENT SCHEME WITH POLYLOGARITHMIC COMMUNICATION COMPLEXITY
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner, Interactive Oracle Proofs
TokenInsight Team, How to transform interactive proofs into non-interactive proofs? Fiat-Shamir Heuristic!
Manish Kumar Giri, Deep dive into Zero-knowledge-proof & ZK-SNARK
Fiat-Shamir Problems on Merlin.cool
Zcash Team, Lookup Argument
Metastate Team, On PLONK and plookup
Zcash Team, Proof Systems
Paul Garrett, Roots of Unity
Изучите открытые вакансии на нашей доске объявлений.
Чтобы быть в курсе последних новостей от Taiko:
Website: https://taiko.xyz
Discord: https://discord.gg/taikoxyz
GitHub: https://github.com/taikoxyz
Twitter: https://twitter.com/taikoxyz
Внесите свой вклад в Taiko и получите GitPOAP! Вы также будете упомянуты в качестве участника в нашем README. Начните с руководства по внесению вклада.
Translated by: perfeect & igorizuchaetcrypty