Приветствуем! Впервые на сайте 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 Часть VII: Попарное соединение эллиптических кривых

Ariel Gabizon | Jun 07, 2017

<< Часть VI

В Части VI, мы увидели схему Пиноккио zk-SNARK. Мы пропустили две вещи - HH, который поддерживает как сложение так и умножение, и необходим для проверки свидетельства, и переход от интерактивного протокола к не интерактивной системе доказательства.

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

Мы начинаем введение в эллиптические кривые и объясняем, как они дают нам необходимый HH.

Эллиптические кривые и их попарное соединение

Предположим, что \(p\) iэто простое число большее чем \(3\), и возьмем некоторые \(u,v\in\mathbb{F}_p\) таким образом что \(4u^3+27v^2\neq 0\). Мы смотрим на уравнение

\(Y^2=X^3 +u\cdot X +v\)

Эллиптическая кривая \({\mathcal C}\) это набор точек \((x,y)\) [1] которые удовлетворяют этому уравнению. Такие кривые дают нам интересный способ построения групп. Элементы группы будут точками \((x,y)\in \mathbb{F}^2_p\) которые находятся на кривой, то есть теми, которые удовлетворяют уравнению, вместе со специальной точкой \({\mathcal O}\), которая по техническим причинам иногда называется "точкой бесконечности", и служит элементом идентичности, то есть нулём для группы.

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

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

Тест |P+Q=O --> P=-Q|

Таким образом мы должны получить \(P+Q={\mathcal O}\) что значит \(P=-Q\); то есть, \(Q\) это инверсия \(P\) в группе

Теперь давайте посмотрим на точки \(P\) и \(Q\) у которых есть различная первая координата - то есть, \(x_1\neq x_2\), и посмотрим, как добавить их. Мы проведем линию через \(P\) и \(Q\).

Тест |P+Q+R=0|

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

Таким образом у нас должно быть \(P+Q+R={\mathcal O}\), что означает \(P+Q=-R\); и к настоящему времени мы знаем, что \(-R\) получен из \(R\) переключением по второй координате от \(y\) до \(-y\).

Таким образом мы получили дополнительное правило для нашей группы: Возьмем точки \(P\) и \(Q\), проведем линию через них, и затем возьмем "зеркальную" точку третьего пересечения линии как дополнительный пункт. [2]

Эту группу обычно называют \({\mathcal C}(\mathbb{F}_p)\) - поскольку она состоит из точке на кривой \({\mathcal C}\) с координатами в \(\mathbb{F}_p\); но давайте обозначим его как \(G_1\) с этого времени. Предположите для простоты, что ряд элементов в \(G_1\) является простым числом \(r\), и отличается от \(p\). Это много раз имеет место, например, в кривой, которую Zcash в настоящий момент использует. В этом случае, любой элемент \(g\in G_1\) отличающийся от \({\mathcal O}\) производит \(G_1\).

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

Мультипликативная группа \(\mathbb{F}_{p^k}\) содержит подгруппу порядка \(r\) которую мы обозначаем как \(G_T\). Мы можем посмотреть на точки кривой с координатами \(\mathbb{F}_{p^k}\) and not just in \(\mathbb{F}_p\). По тому же самому дополнительному правилу, эти точки также формируют группу вместе с \({\mathcal O}\) которая называется \({\mathcal C}(\mathbb{F}_{p^k})\). Заметим, что \({\mathcal C}(\mathbb{F}_{p^k})\) ясно содержит \(G_1\). Помимо \(G_1\), \({\mathcal C}(\mathbb{F}_{p^k})\) будет содержать дополнительную подгруппу \(G_2\) порядка \(r\) (фактически, \(r-1\) это дополнительные подгруппы порядка \(r\)).

Исправим генераторы \(g\in G_1,h\in G_2\). Оказывается, что есть эффективная карта, которая называется уменьшенное соединение Тейта, которое берет пару элементов \(G_1\) и \(G_2\) в элемент \(G_T\),

следовательно

  1. \(\mathrm{Tate}(g,h)=\mathbf{g}\) для генератора \(\mathbf{g}\) от \(G_T\), и
  2. учитывая пару элементов \(a,b \in \mathbb{F}_r\), мы получим \(\mathrm{Tate}(a\cdot g,b\cdot h)=\mathbf{g}^{ab}\).

Определение \(\mathrm{Tate}\) немного выходит за пределы этой серии описаний, и полагается на понятия алгебраической геометрии, наиболее заметные в делителях. Вот набросок определения \(\mathrm{Tate}\): [4]

Для \(a\in\mathbb{F}_p\) многочлен \((X-a)^r\) имеет нулевое множество \(r\) в точке \(a\), и никаких других нулей. Для точки \(P\in G_1\), делители позволяют нам доказать что существует функция \(f_P\) от кривой \(\mathbb{F}_p\) и это также имеет, в некотором точном смысле, нулевое множество \(r\) в \(P\) и никаких других нулей. \(\mathrm{Tate}(P,Q)\) тогда определен как \(f_P(Q)^{(p^k-1)/r}\).

Может вообще не казаться ясным, что это определение имеет отношение к заданным свойствам, и действительно доказать, что у \(\mathrm{Tate}\) есть эти свойства, довольно сложно.

Определяя \(E_1(x) := x\cdot g, E_2(x):=x\cdot h, E(x):=x\cdot \mathbf{g}\), мы получаем ослабленную версию HH которая поддерживает и сложение и умножение: \(E_1,E_2,E\) это HH которые поддерживают сложение, и взяв скрытые \(E_1(x)\), \(E_2(y)\) мы можем вычислить \(E(xy)\). Другими словами, если у нас есть ''правильное'' скрытие \(x\) и \(y\) мы можем получить (различное) скрытие \(xy\). Но например, если у нас было скрытие \(x,y,z\) мы не могли бы получить скрытие \(xyz\).

Мы движемся к обсуждению не интерактивных систем доказательства. Мы начнём с точного объяснения того, что подразумеваем под словами 'не интерактивная'.

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

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

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

Мы объясним, каким образом в модели CRS мы можем преобразовать слепой протокол проверки, см. ЧастьIV в не интерактивную систему доказательства. Поскольку протокол Части VI состоял из нескольких таких подпротоколов он может быть превращен в не интерактивную систему доказательства схожим образом.

Не интерактивный протокол оценки

Не интерактивная версия протокола оценки в основном базируется на публикации первого сообщения Боба как CRS. Вспомните, что цель протокола состоит в том, чтобы получить скрытие \(E(P(s))\) многочлена Алисы \(P\) случайно выбранным \(s\in\mathbb{F}_r\).

Установка: случайные \(\alpha\in \mathbb{F}_r^*,s\in\mathbb{F}_r\) выбраны и CRS:
\((E_1(1),E_1(s),\ldots,E_1(s^d),\) \(E_2(\alpha),E_2(\alpha s),\ldots,E_2(\alpha s^d))\)
опубликованы.

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

Verification: Fix the \(x,y\in \mathbb{F}_r\) следовательно \(a=E_1(x)\) and \(b=E_2(y)\). Bob computes \(E(\alpha x)=\mathrm{Tate}(E_1(x),E_2(\alpha))\) and \(E(y)=\mathrm{Tate}(E_1(1),E_2(y))\), and checks that they are equal. (If they are equal it implies \(\alpha x =y\).)

Как объясняется в Части IV, Алиса может только построить \(a,b\) которые пройдут проверку верификации если \(a\) iбудет скрывать \(P(s)\) для многочлена \(P\) степени \(d\) известной ей. Основное отличие здесь в том, что Боб не должен знать \(\alpha\) для проверки верификации, поскольку он может использовать функцию соединения для вычисления \(E(\alpha x)\) только из \(E_1(x)\) и \(E_2(\alpha)\). Таким образом он не должен построить и переслать первое сообщение, и это сообщение может быть просто зафиксировано в CRS.

[1]Вы можете спросить 'Множество точек начиная откуда?'. Мы имеем в виду набор точек с координатами в алгебраическом замыкании \(\mathbb{F}_p\). Также у кривой есть родственная и проективная версия. Когда описываем проективную версию, мы также включаем "точку бесконечности" \({\mathcal O}\) как элемент кривой.
[2]Мы не рассматривали случай добавления \(P\) к самому себе. Это делается при помощи использования линии, которая является тангенсом кривой в \(P\), и берет \(R\) чтобы быть второй точкой пересечения этой линии и кривой.
[3]https://eprint.iacr.org/2005/133.pdf
[4]Соединение Zcash на самом деле использует оптимальное соединение Ate, которое основано на сокращенных соединениях Тейта, и может быть вычислено более эффективно чем \(\mathrm{Tate}\).
[5]В вычислительных условиях теории сложности, можно показать, что только у языков в BPP есть не интерактивные доказательства с нулевым разглашением в строгом смысле этих слов. Тип претензий, которые мы должны доказать в транзакциях Zcash, например, 'Я знаю прообраз хэша этой строки', связан с классом сложности NP который, как полагают, намного выше, чем BPP.
[6]Использованные изображения были взяты из следующей статьи и используются в соответствии с лицензией creative commons.

cryptography, zkSNARKs, explainers | Просмотреть все тэги