Приветствуем! Впервые на сайте Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Язык

Разбираем SNARK, часть 2: Слепая оценка полиномов

Ariel Gabizon | Mar 13, 2017

<< Часть 1

В этой статье мы снова поговорим о полиномах: дадим объяснение термину "слепая оценка" полинома и расскажем, как она применяется при гомоморфном шифровании (Homomorphic Hiding или HH). (Подробнее об HH читайте в части 1 ) Из последующих постов вы узнаете, что слепая оценка является основным инструментом в конструкциях SNARK.

Через \(\mathbb{F}_p\) мы обозначаем поле, размером которого является \(p\); иными словами, элементы \(\mathbb{F}_p\) принадлежат множеству \(\{0,\ldots,p-1\}\), а операции сочетания и умножения происходят с \(\mathrm{mod}\;p\), о чем говорилось в 1-й части.

Полиномы и линейные комбинации

Вспомним, что полином \(P\) в степени \(d\) над полем \(\mathbb{F}_p\) выражается как

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\), for some \(a_0,\ldots,a_d\in\mathbb{F}_p.\)

Мы можем вычислить \(P\) в точке \(s\in {\mathbb{F}_p}\) заменив \(X\) на \(s\) и посчитав конечную сумму

\(P(s) = a_0 + a_1\cdot s + a_2\cdot s^2 + \ldots + a_d\cdot s^d\)

Для кого-то, кому известно \(P,\) значение \(P(s)\) является линейной комбинацией значений \(1,s,\ldots,s^d\), где линейная комбинация означает просто "взвешенную сумму"; в случае с \(P(s)\) "весом" является \(a_0,\ldots,a_d.\)

В прошлом посте мы рассмотрели гомоморфный шифр \(E\), определенный формулой \(E(x)=g^x\), где \(g\) является порождающим элементом группы со сложной задачей дискретного логарифма. Мы также упомянули о том, что эта схема гомоморфного шифрования "поддерживает сложение", в том смысле, что \(E(x+y)\) можно вычислить из \(E(x)\) and \(E(y)\). А теперь мы обращаем ваше внимание на то, что эта схема также "поддерживает линейные комбинации: это значит, что через известные \(a,b,E(x),E(y),\) мы можем вычислить \(E(ax+by)\). Это просто, потому как

\(E(ax+by)=g^{ax+by}=g^{ax}\cdot g^{by} = (g^x)^a\cdot (g^y)^b = E(x)^a\cdot E(y)^b.\)

Слепая оценка полинома

Предположим, что у Алисы есть полином \(P\) степени \(d\), а у Боба есть точка \(s\in\mathbb{F}_p\), которую он выбрал случайно. Боб хочет узнать \(E(P(s))\), т.е. HH вычисления \(P\) от \(s.\) Для этого существует два простых способа:

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

Как бы то ни было, задача слепой идентификации дать Бобу узнать \(E(P(s))\) не раскрывая ему значения \(P\), что делает невозможным первый вариант; и что более важно, мы не хотим, чтобы Алиса узнала \(s\), что исключает второй [1].

Используя гомоморфное шифрование мы можем провести слепую оценку следующим образом.

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

Отметим, что т.к. были отправлены только скрытые данные, Алиса не узнала значения \(s\) [2], как и Боб не узнал \(P\).

Почему это так эффективно?

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

[1]Главная причина, по которой мы не хотим отправлять Бобу \(P\) заключается большом значении - например, в настоящем протоколе Zcash могут быть элементы (d+1) где, d~2000000; это имеет отношение к сегментам SNARKов "Succinct". Последовательность шифров, которые Боб посылает Алисе в примере выше получается такой же длинной, но кроме того эта последовательность может быть "жестко заданной" в параметрах системы, и следует принять во внимание, что сообщения Алисы будут разными для каждого доказательства SNARK.
[2]На самом деле, способность скрывать гарантирует только то, что \(s\) не будет известно из \(E(s)\), но нам также необходимо, чтобы его нельзя было узнать из последовательности \(E(s),\ldots,E(s^d)\), которая потенциально содержит в себе больше информации об \(s\). Это опирается на утверждение Диффи-Хеллмана о сложность вычисления, которое по итогу оказывается необходимым для безопасности SNARK.