Привет, Хабр! Представляю вашему вниманию перевод статей блога ZCash, в которых рассказывается о механизме работы системы доказательств с нулевым разглашением SNARKs, применяемых в криптовалюте ZCash (и не только).

Предыдущие мои переводы из этой области. Советую сначала ознакомиться с ними, чтобы лучше понимать, о чем пойдет речь:

• Введение в zk-SNARKs с примерами (перевод)
• Квадратичные арифметические программы: из грязи в князи (перевод)

В этой части мы рассмотрим гомоморфное скрытие и слепое вычисление полиномов. Поехали…

Гомоморфное скрытие

Конструкции zk-SNARKs включают в себя гармоничное сочетание нескольких компонентов. Чтобы понять полностью, как эти компоненты работают вместе, понадобится достаточно времени.

Если бы мне пришлось выбрать только одну составляющую, роль которой наиболее заметна, то я бы выделил Гомоморфное Cкрытие (Homomorphic Hiding — HH). В этой части статьи мы объясним, что такое ГС, а затем приведем пример того, почему оно полезно и разберем как оно устроено.

Гомоморфное скрытие не является термином, формально используемым в криптографии, и вводится здесь для дидактических целей. По свойствам оно похоже, но слабее, чем известное понятие "схема обязательства". Разница заключается в том, что ГС является функцией, определяющей аргумент, тогда как обязательство использует дополнительную случайность. Как следствие, гомоморфные скрытия по существу «скрывают большинство x», тогда как обязательства «скрывают каждый x».

ГС $$ числа x — это функция, удовлетворяющей следующим свойствам:

• Для большинства x, при известном значении $$ нахождение x является трудной задачей.
• Различные значения аргументов приводят к разным значениям функции. Поэтому, если $$, то $$
• Если кому-то известно $$ и $$, то он может генерировать ГС от арифметических операций для x и y. Например, он может вычислять $$, зная $$ и $$.

Простой пример, почему ГС полезно для доказательств с нулевым разглашением: предположим, что Алиса хочет доказать Бобу, что знает числа x, y такие, что $$ (Конечно, это не особо интересно, знать такие х и у, но это хороший пример для объяснения концепции).

1. Алиса отправляет $$ и $$ Бобу.
2. Боб вычисляет $$ из этих значений (он может это сделать, т.к. $$ является ГС).
3. Боб также вычисляет $$ и теперь проверяет, является ли $$. Он принимает доказательство Алисы только в случае выполнения равенства.

Поскольку разные значения аргументов $$ соответствуют разным скрытиям (значения функции $$. Прим. переводчика), Боб действительно принимает доказательство только в том случае, если Алиса отправила скрытия для $$, такие что $$. С другой стороны, Боб не получает значения $$, так как у него доступ только к их скрытиям.

Все же Боб получил некоторую информацию об $$ и $$. Например, он может выбрать случайное $$ и проверить, выполняется ли равенство $$ вычислением $$. По этой причине вышеприведенный протокол на самом деле не является протоколом Zero-Knowledge, и используется здесь только для пояснения схемы. Фактически, как мы увидим далее, ГС в конечном итоге используется в SNARKs, чтобы маскировать запросы проверяющего, а не секреты доказывающего.

Теперь давайте разберем пример того, как устроены такие скрытия. На самом деле мы не можем их построить для регулярных целых чисел с регулярным сложениями, вместо этого нужно рассмотреть конечные группы:

Пусть n является некоторым целым числом. Когда пишется $$ для целого числа A, то имеется ввиду взятие остатка от деления A на n. Например, $$ и $$. Также можно использовать $$ для определения операции сложения на множестве { 0,…, n — 1 }. Сначала производится обычное сложение, но затем применяется $$ к результату, чтобы получить число входящее во множество { 0,…, n — 1 }. Иногда $$ пишется справа от выражения, уточняя, что используется этот тип сложения. Например, $$. Будем называть множество элементов { 0,…, n — 1 } вместе с операцией сложения группой $$.

Для простого числа p, можно использовать $$, чтобы определить операцию умножения на множестве { 1,…, p — 1 }, таким образом, чтобы результат умножения также всегда входил во множество { 1,…, p — 1 }. Это достигается путем обычного умножения целых чисел, а затем применив к результату $$. Например, $$.

Когда p не является простым, проблематично определить умножение таким образом. Одна из проблем заключается в том, что результат умножения может быть равен нулю, даже если оба аргумента не равны нулю. Например, когда p = 4, мы можем получить $$.

Набор элементов вместе с этой операцией называется группой $$. Эта группа обладает следующими полезными свойствами:

1. Это циклическая группа. Это означает, что существует некоторый элемент g в $$, называемый генератором такой, что все элементы $$ могут быть записаны как $$ для некоторого а из множества { 0,…, p — 2 }, где $$
2. Дискретное логарифмирование должно быть тяжело выполнимым для $$. Это означает, что когда p достаточно большое, и задан элемент h из $$, то трудно найти целое число a из множества { 0,…, p — 2 }, такое что $$
3. Поскольку степени складываются при умножении элементов с одинаковым основанием, мы получим для a, b из множества { 0,…, p — 2 }: $$

Используя эти свойства, построим теперь гомоморфное скрытие, которое «поддерживает сложение», что означает возможность вычисления $$ зная $$ и $$. Предположим, что аргумент x для $$ принадлежит группе $$, поэтому он находится в диапазоне { 0,…, p — 2 }. Определим $$ для каждого такого х, и докажем, что $$ является ГС: из первого свойства следует, что разным $$ из $$ будут соответствовать разные значения функции. Из второго свойства следует, что для $$ трудно найти x, Наконец, используя третье свойство, для заданных $$ и $$, мы можем вычислить $$ как $$.

Слепое вычисление полиномов

Теперь давайте вспомним что такое понятие полинома, введем понятие «слепого вычисления» многочлена и как оно реализуется с помощью гомоморфного скрытия (ГС). В дальнейшем мы увидим, что «слепое вычисление» является центральным инструментом в конструкциях SNARK.

Обозначим через $$ поле размером p, т. е. элементы $$ принадлежат множеству { 0,…, p — 1 }, где операции сложения и умножения выполняются с $$ как объяснено выше.

Многочлены и линейные комбинации

Напомним, что многочлен P порядка d на поле $$ является выражение вида:

$$

, для некоторого $$,

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

$$

Для того, кто знает что такое $$, значение $$ является линейной комбинацией значений $$ где под линейной комбинацией понимается «взвешенная сумма», в случае $$ «весами» являются $$

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

Слепое вычисление полиномов

Предположим, что у Алисы есть многочлен P порядка d, а у Боба есть значение $$, которое он выбрал случайным образом. Боб хочет узнать $$, т.е. значение ГС P в точке s. Существует два простых способа сделать это:

• Алиса отправляет P Бобу, и он вычисляет $$ сам.
• Боб посылает s Алисе и она вычисляет $$ и отправляет его Бобу.

Однако в случае слепого вычисления мы хотим, чтобы Боб узнал $$ без получения $$ — что исключает первый вариант. А самое главное — мы не хотим, чтобы Алиса узнала s, что исключает второй вариант.

Основная причина, по которой мы не хотим отправлять $$ Бобу, просто состоит в том, что он является большим — он содержит $$ элементов, где d ~ 2000000 в текущем протоколе Zcash. По сути это связано с «ограниченной» частью SNARK.

Используя ГС, мы можем выполнить слепое вычисление следующим образом:

1. Боб посылает Алисе скрытия $$
2. Алиса вычисляет $$ из элементов, отправленных на первом этапе, и отправляет $$ Бобу. (Алиса может это сделать, так как $$ поддерживает линейные комбинации, а $$ является линейной комбинацией $$)
   

Конечно верно то, что последовательность скрытий, которую Боб посылает Алисе, так же длинна как и сам полином, но оказывается, эта последовательность может быть «жестко закодирована» в параметрах системы, при этом сообщения Алисы будут отличаться для каждого доказательства SNARK

Обратите внимание, что только скрытия были отправлены, при этом Алиса не узнала s, а Боб не узнал P.

На самом деле, свойство скрытия гарантирует только то что s не может быть получен, при знании $$. При этом нам также необходимо, чтобы s нельзя было получить, зная последовательность $$, которая потенциально содержит намного больше информации об s. Решение этой проблемы следует из решения d-порядка Диффи — Хеллмана, которое применяется в нескольких доказательствах безопасности SNARK. (сложность дискретного логарифмирования. Прим. переводчика)

Почему это полезно?

В следующих частях будет более подробно рассмотрено, как слепые вычисления используются в SNARK. Если говорить примерно, то проверяющий обладает представлением о «правильном» многочлене и хочет проверить то, что доказывающий знает его. Когда доказывающий проводит слепые вычисления в случайной точке, не известной им обоим, это гарантирует, что доказывающий даст неверный ответ с большой вероятностью, если их многочлен неверен. Это, в свою очередь, опирается на лемму Шварца-Зиппеля о том, что «разные многочлены различны в большинстве точек».

Продолжение следует…