[Перевод] Объяснение SNARKs. Знание о принятом коэффициенте и достоверное слепое вычисление полиномов (перевод)04.12.2017 21:03

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

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

В этой статье мы рассмотрим тест на принятый коэффициент и слепое вычисление полиномов, поддающихся проверке. Поехали…

В предыдущей статье мы увидели, как Алиса может слепо вычислить скрытие $E(P(s))$ ее многочлена P порядка d, в точке s принадлежащей Бобу. Мы назвали это «слепым» вычислением, так как Алиса не получает значение s в процессе вычисления.

Однако в этом протоколе что-то отсутствует. Тот факт, что Алиса может вычислить $E(P(s) )$ не гарантирует, что она действительно отправит $E(P(s))$ Бобу, а не какое нибудь другое значение.

Таким образом, нам нужен способ «заставить» Алису правильно следовать протоколу. В статье мы подробно объясним, как достигнуть этого. Давайте сначала рассмотрим и объясним принцип действия основного инструмента, необходимого для этого. Мы называем его «Тест знания о коэффициенте» (Knowledge of Coefficient (KC) Test).

Как и раньше, обозначим через g генератор группы G порядка $|G| = p$, где дискретное логарифмирование является тяжелой задачей. Для удобства, начиная с данного места будем работать с нашей группой аддитивно, а не мультипликативно. То есть, для $inline$α ∈ F_p, α⋅g$inline$ обозначает сложение α раз копии g.

Тест знания о коэффициенте


Для $α ∈ F^*_p$, будем называть пару элементов $( a , b)$ в $G$ »$α$-парой», если $a , b ≠ 0$ и $b = α ⋅ a$.

$F^*_p$ обозначает ненулевые элементы $F_p$. Это то же самое, что и $Z^*_p$ описанные в предыдущей статье.


Тестирование происходит следующим образом.

  1. Боб выбирает случайное число $α ∈ F^*_p$ и число $a ∈ G$. Он вычисляет $b = α ⋅ a$
  2. Он посылает Алисе «запрос» в виде пары $( a , b )$. Заметим, что $( a , b )$ является α-парой.
  3. Теперь Алиса должна ответить на запрос другой парой $(a', b')$. Это также α-пара.
  4. Боб принимает ответ Алисы, только если $( a', b')$ действительно является α-парой (поскольку он знает α, он может проверить, что $b'= α ⋅ a'$).


Теперь давайте подумаем, когда Алиса может успешно ответить на вызов? Предположим, что она знает α. В этом случае она может просто выбрать любой a' из G и вычислить $b'= α ⋅ a'$, а затем вернуть новую α-пару $( a', b')$.

Однако, поскольку единственная информация об α содержится в выражении $α⋅a$ и группа G имеет сложную дискретную задачу логарифмирования, мы полагаем, что Алиса не сможет найти $α$.

Итак, как же она может успешно ответить на запрос, не зная α?

Простой способ сделать это заключается в следующем: Алиса просто выбирает некое $γ∈ F^*_p$ и отвечает парой $inline$(a', b') = (γ⋅ a, γ⋅ b)$inline$

В этом случае мы имеем:

$inline$b'= γ⋅ b = γα ⋅ a = α (γ⋅ a) = α ⋅ a'$inline$

Таким образом пара $(a', b')$ является α-парой, как и требовалось.

Обратите внимание, что если Алиса ответила, используя этот вариант, она знает, чему равно отношение a к a', То есть, она знает такой коэффициент $γ$, чтобы $a'= γ⋅ a$.

Знание о принятом коэффициенте (ЗПК — The Knowledge of Coefficient Assumption (KCA)) утверждает, что это всегда так:

ЗПК: Если Алиса возвращает верный ответ $( a', b')$ на запрос Боба $( a , b )$ то с большой вероятностью, независимо от выбора Бобом $a,\ α$, она знает такой коэффициент $γ$, чтобы $a'= γ⋅ a$.

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


Тест Знания и Принятый Коэффициент будут важными инструментами в следующей части статьи.

Что означает «Алиса знает»?


Вы можете задаться вопросом, как мы можем сформулировать ЗПК в конкретном математическом выражении? В частности, как мы сформулируем представление о том, что «Алиса знает» $γ$ в математическом определении?

Это делается примерно так: мы говорим, что помимо Алисы у нас есть другая сторона, которую мы называем Экстрактором Алисы. Экстрактор Алисы имеет доступ к внутреннему состоянию Алисы.

Теперь мы можем сформулировать ЗПК следующим образом: каждый раз, когда Алиса успешно отвечает $α$-парой $( a', b')$, Экстрактор Алисы возвращает $γ$, такой что $a'= γ⋅ a$.

Полное формальное определение ЗПК определяет Экстрактор «несколько слабее» и вместо этого он сигнализирует о вероятности успешного ответа Алисы, а не выводит $γ$, который является малозначительным в данном случае


Как сделать слепое вычисление полиномов поддающихся проверке


Далее, опираясь на предыдущий материал, мы разработаем протокол для достоверного слепого вычисления полиномов, определения которым будет дано ниже. В последующих частях (и статьях) будет показано, как этот протокол можно использовать для построения SNARKs, поэтому наберитесь еще немного терпения для изучения SNARKs:).

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

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


Это называется проверкой слепого вычисления полинома. Протокол в предыдущей статье дал нам только первый пункт, но не второй. Чтобы получить достоверность, нам понадобится расширенная версия знания о принятом коэффициенте (ЗПК).

Свойства достоверности и конфиденциальности полезны вместе, потому что они заставляют Алису решить, какой полином P она будет использовать, не видя значения s. Это в некотором смысле обязывает Алису к «ответу полиномом», не видя «точечный запрос» s. Эта логика станет более понятной далее.

В полном формальном доказательстве некоторые вещи описаны более тонко. Например то, что Алиса все же получает некую информацию об s, прежде чем принять решение о ее полиноме P. Например она получает скрытия $s , ... , s_d$


Расширенный ЗПК


ЗПК, в том виде, который мы определили выше, звучит примерно так: если Боб дает Алисе некоторую $α$-пару $( a , b = α ⋅ a )$, а затем Алиса генерирует еще одну $α$-пару $( a', b')$, то она знает такое значение c, чтобы $a'= c ⋅ a$. Говоря иначе, Алиса знает соотношение между a' и a.

Теперь предположим, что вместо одной Боб посылает Алисе несколько $α$-пар $( a_1, b_1) , ... , ( a_d, b_d)$ (для одной и той же $α$). И теперь снова Алиса, получив эти пары, должна сгенерировать другие другие $α$-пары $( a', b')$. Важно, что Алиса должна это сделать, при этом она не знает значение $α$.

Как было описано выше, Алисы может создать $α$-пару простым способом. Для этого нужно взять одну из пар $(a_i, b_i)$, полученную от Боба и умножить оба элемента на некоторый $c ∈ F^*_p$. Если $(a_i, b_i)$ была $α$-парой, то $( c ⋅ a_i, c ⋅ b_i)$ тоже будет $α$-парой. Но может ли Алиса сгенерировать $α$-пары для большего количества полученных $α$-пар? И возможно ли получить новую $α$-пару, используя сразу несколько полученных $α$-пар?

Ответ: Да. Например, Алиса может выбрать два значения $c_1, c_2∈ F_p$ и вычислить пару $inline$(a', b') = (c_1⋅ a_1+ c_2⋅ a_2, c_1⋅ b_1+ c_2⋅ b_2)$inline$. Простые преобразования показывают, что для любой $a'$, отличной от нуля, это тоже является $α$-парой:

$inline$b'= c_1⋅ b_1+ c_2⋅ b_2= c_1α ⋅ a_1+ c_2α ⋅ a_2= α (c_1⋅ a_1+ c_2⋅ a_2) = α ⋅ a'$inline$

В более общем случае Алиса может взять любую линейную комбинацию полученных d пар. Для этого нужно выбрать любые $c_1, ... , c_d∈ F_p$ и определить $( a', b') = ( Σ^d_{i = 1}c_ia_i,Σ^d_{i = 1}c_ib_i)$.

Обратите внимание, что если Алиса использует эту стратегию для генерации ее $α$-пар, то она будет знать некоторую линейную зависимость между $a'$ и $a_1, ... , a_d$. То есть она знает $c_1, ... , c_d$ такие, что $a'= Σ^d_{i = 1}c_i⋅a_i$.

Расширенное ЗПК утверждает, по сути, что это единственный способ, которым Алиса может генерировать $α$-пару. Таким образом, когда она успешна сгенерирована, Алиса будет знать линейную зависимость между $a'$ и $a_1, ... , a_d$. Более формально предположим, что G представляет собой группу размера p с генератором g, описанные аддитивно в начале статьи. Знание о принятом коэффициенте порядка d (d-ЗПК) в G можно записать следующим образом:

d-ЗПК: Предположим, что Боб выбирает случайные $α ∈ F^*_p$ и $s ∈ F_p$, и отправляет Алисе $α$-пары $inline$(g, α ⋅ g), (s ⋅ g, α s ⋅ g) , … , (s^d⋅ g, αs^d⋅ g)$inline$. Предположим, что затем Алиса отвечает другой $α$-парой $( a', b')$. Тогда, с большой вероятностью, Алиса знает $c_0, ... , c_d∈ F_p$ такие, что $Σ^d_{i = 0}c_is^i⋅ g= a'$.

D-KCA (d-ЗПК) была представлена ​​в журнале Йенса Грота.


Заметим, что в $d-ЗПК$ Боб не посылает случайный набор $α$-пар, а посылает набора с определенной «полиномиальной структурой». Пользу этого мы увидим в приведенном ниже протоколе.

Протокол достоверного слепого вычисления


Предположим, что наше ГС (гомоморфное скрытие) является отображением $E( x ) = x ⋅ g$ для генератора g из G, описанного выше.

Для простоты мы представляем протокол для этого конкретного E:

  1. Боб выбирает случайную $α ∈ F^*_p$, и отправляет Алисе скрытия $g, s ⋅ g, ... , s^d⋅ g$ (для $1 , s , ... , s^d$), а также скрытия $inline$α ⋅ g, αs ⋅ g, … , α s^d⋅ g$inline$ (для $α , αs , ... , αs^d$).
  2. Алиса вычисляет $a = P( s ) ⋅ g$ и $b = α P(s) ⋅ g$, используя элементы, отправленные на первом этапе, и отправляет их Бобу.
  3. Боб проверяет, что $b = α ⋅ a$, и принимает ответ тогда и только тогда, когда это равенство выполняется.


Во-первых, заметим, что полученные коэффициенты $P$, $P(s) ⋅ g$ являются линейной комбинацией $g, s ⋅ g, ... , s^d⋅g$ и $α P(s) ⋅ g$, а $αP(s) ⋅ g$ является линейной комбинацией $inline$α ⋅ g, α s ⋅ g, … , α s^d⋅ g$inline$. Таким образом, аналогично протоколу в предыдущей статье, Алиса действительно может вычислить эти значения из сообщений Боба для полинома P, который она знает.

Во-вторых, согласно d-ЗПК, если Алиса посылает $a, b$ такие, что $b = α ⋅ a$, то почти наверняка она знает такие $c_0, ... , c_d∈ F_p$, что $a = Σ^d_{i = 0}с_is^i⋅ g$. В этом случае $a = P(s) ⋅ g$ для многочлена $P( X) = Σ^d_{i = 0}с_i⋅ X^i$ известного Алисе. Другими словами, вероятность того, что Боб примет ответ на шаге 3 и при этом Алиса не знает такого многочлена P является ничтожной.

Резюмируя все это, используя d-ЗПК, мы разработали протокол для достоверного слепого вычисления полиномов. В следующих статьях мы увидим, как этот механизм используется в конструкциях SNARK.

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

© Habrahabr.ru