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

Habrahabr

Привет, Хабр! Представляю вашему вниманию перевод статей блога 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.

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