04.12.2017 15:48
AgentRX 3 950 Источник
Привет, Хабр! Представляю вашему вниманию перевод статей блога 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.

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

Комментарии (3)


  1. sheknitrtch
    05.12.2017 00:41
    #10551790

    Классная статья. Когда меня спросят «Зачем ты эту теорию чисел учил в универе?», Я отвечу — для того, чтобы уметь читать вот такие выкладки.

    Я понимаю, что статья носит вводный характер и допускает некоторые упрощения, но всё равно интересно следить, как из простых конструкций получается протокол для достоверного слепого вычисления полиномов при почти-нулевом раскрытии секрета.

    С нетерпением жду продолжения.


  1. vibornoff
    05.12.2017 12:21
    #10552474

    И, как водится в популярных статьях, за фразой «очевидно что» спрятали приличный кусок математических выкладок.

    Я никак не возьму в толк, зачем на шаге 2 Алиса будет вычислять ?-пару через линейное комбинирование, если она может просто взять одну произвольную пару Боба из шага 1 и домножить её на случайное ?, при том, что ответ будет таки валидной альфа-парой и Боб на шаге 3 его примет?


    1. AgentRX Автор
      05.12.2017 16:42
      #10552962

      Одна пара — это полином с коэффициентом, отличным от нуля для одного из порядков X.
      Дальше уже будет рассказано как Бобу проверить именно сам полином в «нужных» точках за счет получения остатка от деления полиномов.