Привет, Хабр! Представляю вашему вниманию перевод статей блога ZCash, в которых рассказывается о механизме работы системы доказательств с нулевым разглашением SNARKs, применяемых в криптовалюте ZCash (и не только).
Предыдущие мои переводы из этой области. Советую сначала ознакомиться с ними, чтобы лучше понимать, о чем пойдет речь:
В этой части мы рассмотрим гомоморфное скрытие и слепое вычисление полиномов. Поехали…
Конструкции zk-SNARKs включают в себя гармоничное сочетание нескольких компонентов. Чтобы понять полностью, как эти компоненты работают вместе, понадобится достаточно времени.
Если бы мне пришлось выбрать только одну составляющую, роль которой наиболее заметна, то я бы выделил Гомоморфное Cкрытие (Homomorphic Hiding — HH). В этой части статьи мы объясним, что такое ГС, а затем приведем пример того, почему оно полезно и разберем как оно устроено.
ГС
числа x — это функция, удовлетворяющей следующим свойствам:
Простой пример, почему ГС полезно для доказательств с нулевым разглашением: предположим, что Алиса хочет доказать Бобу, что знает числа x, y такие, что
(Конечно, это не особо интересно, знать такие х и у, но это хороший пример для объяснения концепции).
Поскольку разные значения аргументов
соответствуют разным скрытиям (значения функции
. Прим. переводчика), Боб действительно принимает доказательство только в том случае, если Алиса отправила скрытия для
, такие что
. С другой стороны, Боб не получает значения
, так как у него доступ только к их скрытиям.
Теперь давайте разберем пример того, как устроены такие скрытия. На самом деле мы не можем их построить для регулярных целых чисел с регулярным сложениями, вместо этого нужно рассмотреть конечные группы:
Пусть n является некоторым целым числом. Когда пишется
для целого числа A, то имеется ввиду взятие остатка от деления A на n. Например,
и
. Также можно использовать
для определения операции сложения на множестве { 0,…, n — 1 }. Сначала производится обычное сложение, но затем применяется
к результату, чтобы получить число входящее во множество { 0,…, n — 1 }. Иногда
пишется справа от выражения, уточняя, что используется этот тип сложения. Например,
. Будем называть множество элементов { 0,…, n — 1 } вместе с операцией сложения группой
.
Для простого числа p, можно использовать
, чтобы определить операцию умножения на множестве { 1,…, p — 1 }, таким образом, чтобы результат умножения также всегда входил во множество { 1,…, p — 1 }. Это достигается путем обычного умножения целых чисел, а затем применив к результату
. Например,
.
Набор элементов вместе с этой операцией называется группой
. Эта группа обладает следующими полезными свойствами:
Используя эти свойства, построим теперь гомоморфное скрытие, которое «поддерживает сложение», что означает возможность вычисления
зная
и
. Предположим, что аргумент x для
принадлежит группе
, поэтому он находится в диапазоне { 0,…, p — 2 }. Определим
для каждого такого х, и докажем, что
является ГС: из первого свойства следует, что разным
из
будут соответствовать разные значения функции. Из второго свойства следует, что для
трудно найти x, Наконец, используя третье свойство, для заданных
и
, мы можем вычислить
как
.
Теперь давайте вспомним что такое понятие полинома, введем понятие «слепого вычисления» многочлена и как оно реализуется с помощью гомоморфного скрытия (ГС). В дальнейшем мы увидим, что «слепое вычисление» является центральным инструментом в конструкциях SNARK.
Обозначим через
поле размером p, т. е. элементы
принадлежат множеству { 0,…, p — 1 }, где операции сложения и умножения выполняются с
как объяснено выше.
Напомним, что многочлен P порядка d на поле
является выражение вида:

, для некоторого
,
Мы можем вычислить значение P точке
подставляя s в качестве X, и вычисляя полученную сумму:

Для того, кто знает что такое
, значение
является линейной комбинацией значений
где под линейной комбинацией понимается «взвешенная сумма», в случае
«весами» являются 
Выше мы определили ГС от
как
, где g является генератором группы с тяжело выполнимой дискретной задачей логарифмирования. Мы упоминали, что это ГС «поддерживает сложение» в том смысле, что
может быть вычислено, зная
и
. Отметим также, что оно «поддерживает линейные комбинации». Это означает, что для заданных
, мы можем вычислить
, Это легко можно показать:

Предположим, что у Алисы есть многочлен P порядка d, а у Боба есть значение
, которое он выбрал случайным образом. Боб хочет узнать
, т.е. значение ГС P в точке s. Существует два простых способа сделать это:
Однако в случае слепого вычисления мы хотим, чтобы Боб узнал
без получения
— что исключает первый вариант. А самое главное — мы не хотим, чтобы Алиса узнала s, что исключает второй вариант.
Используя ГС, мы можем выполнить слепое вычисление следующим образом:
Обратите внимание, что только скрытия были отправлены, при этом Алиса не узнала s, а Боб не узнал P.
В следующих частях будет более подробно рассмотрено, как слепые вычисления используются в SNARK. Если говорить примерно, то проверяющий обладает представлением о «правильном» многочлене и хочет проверить то, что доказывающий знает его. Когда доказывающий проводит слепые вычисления в случайной точке, не известной им обоим, это гарантирует, что доказывающий даст неверный ответ с большой вероятностью, если их многочлен неверен. Это, в свою очередь, опирается на лемму Шварца-Зиппеля о том, что «разные многочлены различны в большинстве точек».
Часть 2. Объяснение SNARKs. Знание о принятом коэффициенте и достоверное слепое вычисление полиномов
Предыдущие мои переводы из этой области. Советую сначала ознакомиться с ними, чтобы лучше понимать, о чем пойдет речь:
- Введение в zk-SNARKs с примерами (перевод)
- Квадратичные арифметические программы: из грязи в князи (перевод)
В этой части мы рассмотрим гомоморфное скрытие и слепое вычисление полиномов. Поехали…
Гомоморфное скрытие
Конструкции zk-SNARKs включают в себя гармоничное сочетание нескольких компонентов. Чтобы понять полностью, как эти компоненты работают вместе, понадобится достаточно времени.
Если бы мне пришлось выбрать только одну составляющую, роль которой наиболее заметна, то я бы выделил Гомоморфное Cкрытие (Homomorphic Hiding — HH). В этой части статьи мы объясним, что такое ГС, а затем приведем пример того, почему оно полезно и разберем как оно устроено.
Гомоморфное скрытие не является термином, формально используемым в криптографии, и вводится здесь для дидактических целей. По свойствам оно похоже, но слабее, чем известное понятие "схема обязательства". Разница заключается в том, что ГС является функцией, определяющей аргумент, тогда как обязательство использует дополнительную случайность. Как следствие, гомоморфные скрытия по существу «скрывают большинство x», тогда как обязательства «скрывают каждый x».
ГС
- Для большинства x, при известном значении
нахождение x является трудной задачей.
- Различные значения аргументов приводят к разным значениям функции. Поэтому, если
, то
- Если кому-то известно
и
, то он может генерировать ГС от арифметических операций для x и y. Например, он может вычислять
, зная
и
.
Простой пример, почему ГС полезно для доказательств с нулевым разглашением: предположим, что Алиса хочет доказать Бобу, что знает числа x, y такие, что
- Алиса отправляет
и
Бобу.
- Боб вычисляет
из этих значений (он может это сделать, т.к.
является ГС).
- Боб также вычисляет
и теперь проверяет, является ли
. Он принимает доказательство Алисы только в случае выполнения равенства.
Поскольку разные значения аргументов
Все же Боб получил некоторую информацию оби
. Например, он может выбрать случайное
и проверить, выполняется ли равенство
вычислением
. По этой причине вышеприведенный протокол на самом деле не является протоколом Zero-Knowledge, и используется здесь только для пояснения схемы. Фактически, как мы увидим далее, ГС в конечном итоге используется в SNARKs, чтобы маскировать запросы проверяющего, а не секреты доказывающего.
Теперь давайте разберем пример того, как устроены такие скрытия. На самом деле мы не можем их построить для регулярных целых чисел с регулярным сложениями, вместо этого нужно рассмотреть конечные группы:
Пусть n является некоторым целым числом. Когда пишется
Для простого числа p, можно использовать
Когда p не является простым, проблематично определить умножение таким образом. Одна из проблем заключается в том, что результат умножения может быть равен нулю, даже если оба аргумента не равны нулю. Например, когда p = 4, мы можем получить.
Набор элементов вместе с этой операцией называется группой
- Это циклическая группа. Это означает, что существует некоторый элемент g в
, называемый генератором такой, что все элементы
могут быть записаны как
для некоторого а из множества { 0,…, p — 2 }, где
- Дискретное логарифмирование должно быть тяжело выполнимым для
. Это означает, что когда p достаточно большое, и задан элемент h из
, то трудно найти целое число a из множества { 0,…, p — 2 }, такое что
- Поскольку степени складываются при умножении элементов с одинаковым основанием, мы получим для a, b из множества { 0,…, p — 2 }:
Используя эти свойства, построим теперь гомоморфное скрытие, которое «поддерживает сложение», что означает возможность вычисления
Слепое вычисление полиномов
Теперь давайте вспомним что такое понятие полинома, введем понятие «слепого вычисления» многочлена и как оно реализуется с помощью гомоморфного скрытия (ГС). В дальнейшем мы увидим, что «слепое вычисление» является центральным инструментом в конструкциях SNARK.
Обозначим через
Многочлены и линейные комбинации
Напомним, что многочлен P порядка d на поле
, для некоторого
Мы можем вычислить значение P точке
Для того, кто знает что такое
Выше мы определили ГС от
Слепое вычисление полиномов
Предположим, что у Алисы есть многочлен P порядка d, а у Боба есть значение
- Алиса отправляет P Бобу, и он вычисляет
сам.
- Боб посылает s Алисе и она вычисляет
и отправляет его Бобу.
Однако в случае слепого вычисления мы хотим, чтобы Боб узнал
Основная причина, по которой мы не хотим отправлятьБобу, просто состоит в том, что он является большим — он содержит
элементов, где d ~ 2000000 в текущем протоколе Zcash. По сути это связано с «ограниченной» частью SNARK.
Используя ГС, мы можем выполнить слепое вычисление следующим образом:
- Боб посылает Алисе скрытия
- Алиса вычисляет
из элементов, отправленных на первом этапе, и отправляет
Бобу. (Алиса может это сделать, так как
поддерживает линейные комбинации, а
является линейной комбинацией
)
Конечно верно то, что последовательность скрытий, которую Боб посылает Алисе, так же длинна как и сам полином, но оказывается, эта последовательность может быть «жестко задана» в параметрах системы, при этом сообщения Алисы будут отличаться для каждого доказательства SNARK
Обратите внимание, что только скрытия были отправлены, при этом Алиса не узнала s, а Боб не узнал P.
На самом деле, свойство скрытия гарантирует только то что s не может быть получен, при знании. При этом нам также необходимо, чтобы s нельзя было получить, зная последовательность
, которая потенциально содержит намного больше информации об s. Решение этой проблемы следует из решения d-порядка Диффи — Хеллмана, которое применяется в нескольких доказательствах безопасности SNARK. (сложность дискретного логарифмирования. Прим. переводчика)
Почему это полезно?
В следующих частях будет более подробно рассмотрено, как слепые вычисления используются в SNARK. Если говорить примерно, то проверяющий обладает представлением о «правильном» многочлене и хочет проверить то, что доказывающий знает его. Когда доказывающий проводит слепые вычисления в случайной точке, не известной им обоим, это гарантирует, что доказывающий даст неверный ответ с большой вероятностью, если их многочлен неверен. Это, в свою очередь, опирается на лемму Шварца-Зиппеля о том, что «разные многочлены различны в большинстве точек».
Часть 2. Объяснение SNARKs. Знание о принятом коэффициенте и достоверное слепое вычисление полиномов