How to become an author
Search
Profile
Pull to refresh

Объяснение SNARKs. Гомоморфное скрытие и слепое вычисление полиномов (перевод)

Decentralized networks *Information Security *Cryptography *Mathematics *
Translation
Original author: Ariel Gabizon
Привет, Хабр! Представляю вашему вниманию перевод статей блога ZCash, в которых рассказывается о механизме работы системы доказательств с нулевым разглашением SNARKs, применяемых в криптовалюте ZCash (и не только).

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


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

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


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

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

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

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

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

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

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

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

Пусть n является некоторым целым числом. Когда пишется $A\ mod\ n$ для целого числа A, то имеется ввиду взятие остатка от деления A на n. Например, $9\ mod\ 7 = 2$ и $13\ mod\ 12 = 1$. Также можно использовать $mod\ n$ для определения операции сложения на множестве { 0,…, n — 1 }. Сначала производится обычное сложение, но затем применяется $(mod\ n)$ к результату, чтобы получить число входящее во множество { 0,…, n — 1 }. Иногда $(mod\ n)$ пишется справа от выражения, уточняя, что используется этот тип сложения. Например, $2 + 3 = 1\ (mod\ 4)$. Будем называть множество элементов { 0,…, n — 1 } вместе с операцией сложения группой $Z_n$.

Для простого числа p, можно использовать $mod\ n$, чтобы определить операцию умножения на множестве { 1,…, p — 1 }, таким образом, чтобы результат умножения также всегда входил во множество { 1,…, p — 1 }. Это достигается путем обычного умножения целых чисел, а затем применив к результату $mod\ p$. Например, $2 ⋅ 4 = 1\ ( mod\ 7 )$.
Когда p не является простым, проблематично определить умножение таким образом. Одна из проблем заключается в том, что результат умножения может быть равен нулю, даже если оба аргумента не равны нулю. Например, когда p = 4, мы можем получить $2 * 2 = 0\ (mod\ 4)$.

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

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

Используя эти свойства, построим теперь гомоморфное скрытие, которое «поддерживает сложение», что означает возможность вычисления $E( x + y)$ зная $E( x )$ и $E(y)$. Предположим, что аргумент x для $E$ принадлежит группе $Z_{p-1}$, поэтому он находится в диапазоне { 0,…, p — 2 }. Определим $E( x ) = g^x$ для каждого такого х, и докажем, что $E$ является ГС: из первого свойства следует, что разным $x'$ из $Z_{p-1}$ будут соответствовать разные значения функции. Из второго свойства следует, что для $E( x ) = g^x$ трудно найти x, Наконец, используя третье свойство, для заданных $E( x )$ и $E( y)$, мы можем вычислить $E( x + y)$ как $E( x + y) = g^{x + y\ mod\ p-1} = E( x ) ⋅ E( y)$.

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


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

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

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


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

$P(X) = a_0+ a_1 * X+ a_2⋅ X^2+ ... + a_d⋅ X^d$

, для некоторого $a_0, ... , a_d ∈ F_p$,

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

$P( s ) = a_0+ a_1⋅ s + a_2⋅ s^2+ ... + a_d⋅ s^d$

Для того, кто знает что такое $P$, значение $P(s)$ является линейной комбинацией значений $1 , s , ... , s^d$ где под линейной комбинацией понимается «взвешенная сумма», в случае $P(s)$ «весами» являются $a_0, ... , a_d$

Выше мы определили ГС от $E$ как $E( x ) = g^x$, где g является генератором группы с тяжело выполнимой дискретной задачей логарифмирования. Мы упоминали, что это ГС «поддерживает сложение» в том смысле, что $E( x + y)$ может быть вычислено, зная $E( x )$ и $E(y)$. Отметим также, что оно «поддерживает линейные комбинации». Это означает, что для заданных $a , b , E( x ) , E( y)$, мы можем вычислить $E( a x + b y)$, Это легко можно показать:
$E( ax + by) = g^{ax + by} = g^{ax} * g^{by} = (g^x)^a *(g^y)^b = E(x)^a * E(y)^b$

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


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

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

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

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

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

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

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

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


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

Часть 2. Объяснение SNARKs. Знание о принятом коэффициенте и достоверное слепое вычисление полиномов
Tags:
Hubs:
Total votes 7: ↑6 and ↓1 +5
Views 4.1K
Comments 1
0
Karma
0.1
Rating
Андрей @AgentRX

CTO

Comments Comments 1

Your account

Sections

Information

Services

Support Return to old version
© 2006–2022, Habr