Объяснение SNARKs. Сопряжения эллиптических кривых (перевод)27.12.2017 10:33

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

Источник

Предыдущие статьи:

Часть 1: Объяснение SNARKs. Гомоморфное скрытие и слепое вычисление полиномов (перевод)
Часть 2: Объяснение SNARKs. Знание о принятом коэффициенте и достоверное слепое вычисление полиномов (перевод)
Часть 3: Объяснение SNARKs. От вычислений к многочленам, протокол Пиноккио и сопряжение эллиптических кривых (перевод)

В предыдущей статье был рассмотрен протокол Пиноккио для zk-SNARK. Осталось разобрать две вещи: Гомоморфное скрытие (ГС), которое поддерживает как добавление, так и умножение, необходимые для верификации, и переход от интерактивного протокола к неинтерактивной системе доказательств.

В этой статье будет показано, как с помощью эллиптических кривых можно получить ограниченную, но достаточную для наших целей форму ГС, которая поддерживает умножение. Далее будет показано, что этой ограниченной формы ГС также достаточно, чтобы преобразовать протокол в необходимую неинтерактивную систему.

Начнем с введения в эллиптические кривые и объяснения того, как они позволяют получить необходимую нам форму ГС.

Эллиптические кривые и их сопряжения

Предположим, что p является простым числом больше 3, и возьмем некоторые $u, v ∈ F_p$ такие, что $4u^3+ 27v^2≠ 0$ . Рассмотрим уравнение:

$Y^2= X^3+ u ⋅ X+ v$

Эллиптическая кривая C является множеством точек $( x , y)$ , которые удовлетворяют данному уравнению. Эти кривые дают нам интересный способ построения групп. Элементами группы будут точки $( x , y) ∈ F^2_p$ которые находятся на кривой, т. е. удовлетворяют уравнению вместе со специальной точкой O, нужная по техническим причинам иногда упоминается как «точка в бесконечности» и служит элементом идентичности, то есть нулем группы.

Вы можете спросить «Набор точек на чем?». Мы имеем в виду множество точек с координатами в алгебраическом замыкании . Кроме того, кривая имеет аффинную и проективную версию. Когда ссылаемся на проективную версию, мы также включаем «точку на бесконечности» O как элемент кривой.

Теперь вопрос заключается в том, как сложить две точки $P= ( x_1, y_1) , Q = ( x_2, y_2)$ чтобы получить третью? Правило сложения получается из некоторого абстрактного объекта, называемого группой классов дивизоров кривой. Для наших целей все, что вам нужно знать об этой группе классов дивизоров, состоит в том, что она накладывает следующее ограничение на определение операции сложения: сумма точек на любой линии должна быть равна нулю, т.е. O.

Давайте рассмотрим, какое правило сложения вытекает из данного ограничения. Посмотрите на вертикальную линию, определяемую уравнением вида $X= c$ . Предположим, что эта линия пересекает кривую в точке $P= ( x_1, y_1)$ . Поскольку уравнение кривой имеет вид $Y^2= f(X)$ , если $( x1, y1)$ находится на кривой, то существует точка $Q : = ( x_1, - y_1)$ . Более того, поскольку это вертикальная линия, и уравнение кривой второго порядка Y, мы можем быть уверены, что это единственные точки, где пересекаются линия и кривая.

Таким образом, мы имеем уравнение $P+ Q = O$ , что означает $P= - Q$ Таким образом $Q$ является обратным к $P$ в группе.

Теперь давайте разберем точки $inlineP$inline и $inlineQ$inline, у которых не совпадают первые координаты, т.е. $x_1≠ x_2$ , и посмотрим, как их сложить. Проводим линию через P и Q.

Так как кривая определяется полиномом третьей степени X и уже пересекает эту (не вертикальную) линию в двух точках, она гарантированно пересечет линию в третьей точке, которую мы обозначим $R = ( x , y)$ , и не пересекает линию в других точках.

Поэтому получаем $P+ Q + R = O$ , что означает $P+ Q = - R$ . Мы уже знаем, что $-R$ получается из $R$ с помощью разворота второй координаты из $y$ в $-y$ .

Таким образом, правило сложения для нашей группы выглядит следующим образом: Для выбранных точек P и Q, необходимо провести через них линию, а затем взять «зеркальную» точку для третьей точки пересечения линии. Это и будет результатом сложения.

Мы не рассматривали случай сложения P с самим собой. Это делается с использованием линии, являющейся касательной к кривой в точке P, и получением R, как второй точки пересечения этой линии с кривой.

Эта группа обычно называется $C( F_p)$ , поскольку она состоит из точек на кривой $inlineC$inline с координатами в $F_p$ . Но будем обозначать ее далее как $G_1$ . Для удобства будем считать, что число элементов в $G_1$ — простое число r, отличное от p. Это применяется во многих решениях, например, на кривой, которую использует Zcash. В этом случае любой элемент $g∈ G_1$ , отличающийся от O, генерирует $G_1$ .

Наименьшее целое число k такое, что r делит $p^k-1$ называется степенью вложенности кривой. Считается, что если k достаточно большое, например, не менее 6, то задача дискретного логарифмирования в $G_1$ , т.е. нахождение $α$ и $g$ из $α⋅g$ , является достаточно сложной. (В кривых BN, используемых в настоящее время в Zcash, $k = 12$ ).

Мультипликативная группа $F_{p^k}$ содержит подгруппу порядка r которая обозначается $G_T$ . Мы можем посмотреть точки кривой с координатами в $F_{p^k}$ и не только в $F_p$ . В соответствии с тем же правилом сложения, эти точки также образуют группу вместе с O, которая называется $C( F_{p^k})$ . Заметим, что $C(F_{p^k})$ явно содержит $G_1$ . Помимо $G_1, C(F_{p^k})$ будет содержать дополнительную подгруппу $G_2$ порядка r(в действительности, $r - 1$ дополнительных подгрупп порядка r).

Зафиксируем генераторы $g∈ G_1, h ∈ G_2$ . Оказывается, существует эффективная карта, называемая упрощенным сопряжением Тейта (Tate reduced pairing), переводящая пару элементов из $G_1$ и $G_2$ в элемент из $G_T$ такой, что

для генератора ξ из
Для заданной пары элементов выполняется $Tate( a ⋅ g, b ⋅ h ) = ξ^{ab}$

Определение Tate немного выходит за рамки серии этих статей и опирается на концепции из алгебраической геометрии, в большей степени на дивизоры.

Фактически, сопряжение Zcash использует оптимальное сопряжение Ate, которое основано на упрощенном сопряжении Тейта и может быть вычислено более эффективно, чем Tate.

Для $a ∈ F_p$ многочлен $( X- а )^r$ принимает значение ноль в степени $r$ в точке a, и нигде больше. Для точки $P∈ G_1$ , дивизоры позволяют доказать, что существует функция $f_P$ от кривой на $F_p$ , которая также принимает в некотором точном смысле ноль в степени r для P и нигде больше. $Tate ( P, Q )$ тогда определяется как $f_P( Q )^{( p^k- 1 ) / r}$ .

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

Определив $inline$E_1(x) : = x ⋅ g, E_2(x) : = x ⋅ h, E (x) : = x ⋅ ξ$inline$ мы получаем слабую версию ГС, которая поддерживает как сложение, так и умножение: $E_1, E_2, E$ являются ГС, которые поддерживают сложение, и зная скрытия $E_1( x ), E_2( y)$ мы можем вычислить $E( xy)$ . Другими словами, если у нас есть «правильные» скрытия x и y, мы можем получить (другое) скрытие xy. Но, например, если у нас есть скрытия для $x , y, z$ , мы не сможем получить скрытие $xyz$ .

Давайте перейдем к обсуждению неинтерактивных систем доказательств. Начнем с объяснения того, что мы подразумеваем под «неинтерактивным».

Неинтерактивные доказательства в модели общей ссылающейся строки

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

В терминах теории сложности вычислений можно показать, что только языки классов сложности BPP реализуют неинтерактивные доказательства с нулевым разглашением в полной мере. Тип утверждений, которые нам нужно доказать в транзакциях Zcash, например «Я знаю оригинал для хэша этой строки», соответствует классу сложности NP, который, как известно, намного больше, чем BPP.

Ослабим определение неинтерактивного доказательства, чтобы внести понятие общей ссылающейся строки — ОСС (от англ. CRS). В модели ОСС, прежде чем будут построены какие-либо доказательства, существует фаза установки, в которой строка создается в соответствии с определенным случайным процессом и передается всем сторонам. Эта строка называется ОСС, а затем используется для создания и проверки доказательств. Предполагается, что случайные данные, используемые при создании ОСС, неизвестны ни одной из сторон, поскольку знание этих данных позволит построить ложные доказательства.

Давайте рассмотрим, как в модели ОСС можно преобразовать протокол достоверного слепого вычисления в неинтерактивную систему доказательств. Поскольку данный протокол состоит из нескольких похожих под-протоколов, он может быть превращен в неинтерактивную систему доказательств аналогичным образом.

Неинтерактивный протокол вычисления

Неинтерактивная версия протокола вычисления изначально состоит в публикации первого сообщения Боба как ОСС. Напомним, что целью протокола является получение гомоморфного скрытия $E(P(s))$ для многочлена Алисы $P$ для случайно выбранного $s ∈ F_р$ .

Установка: Выбираются случайные $α ∈ F^*_r, s ∈ F_r$ и публикуется ОСС: $( E_1( 1 ) , E_1(s) , ... , E_1(s^d), E_2( α ) , E_2( αs ) , ... , E_2( αs^d))$ .

Доказательство. Алиса вычисляет $a = E_1( P(s))$ и $b=E_2(αP(s))$ используя элементы ОСС, и тот факт, что $E_1$ и $E_2$ поддерживают линейные комбинации.

Проверка: Приняв $x , y∈ F_р$ для $a = E_1( x )$ и $b = E_2( y)$ , Боб вычисляет $E( α x ) = Tate ( E_1( x ) , E_2( α ) )$ и $E( y) = Tate ( E_1( 1 ) , E_2( y) )$ , и проверяет их равенство. (Если они равны, то это значит, что $αx = y$ .)

Как было показано в предыдущих частях, Алиса может создать только такие $a,b$ , которые будут проходить проверки, если $a$ является скрытием $P(s)$ для многочлена $P$ порядка d, известного ей. Основное различие здесь в том, что Бобу не нужно знать $α$ для проверки, поскольку он может использовать функцию сопряжения для вычисления $E(αx)$ только от $E_1(x)$ и $E_2(α)$ . Следовательно, ему не нужно самостоятельно создавать и отправлять первое сообщение, и это сообщение может быть просто исправлено в ОСС.

Используемые изображения были взяты из данной статьи и используются по лицензии Creative Commons .