Приветствуем! Впервые на сайте Zcash?
Сеть Zcash пока еще молода, но быстро растет! Регистрируйтесь на сайте, чтобы получить больше информацией о том, как начать пользоваться Zcash!

Язык

Объяснение SNARKs часть III: тестовый коэффициент и представление

Ariel Gabizon | Mar 28, 2017

<< Часть II

В Части II мы увидели, как Алиса вслепую может оценить скрытие \(E(P(s))\) её полиномиала \(P\) степени \(d,\) в пункте \(s\) принадлежащем Бобу. Мы назвали это оценкой "вслепую", потому что Алиса не узнала \(s\) в процессе.

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

Таким образом нам нужен способ "заставить" Алису следовать протоколу корректно. Мы будем объяснять в части IV, как точно мы хотим достигнуть этого. В этой статье мы сосредоточимся на объяснении основных инструментов, необходимых для этого - которые мы называем здесь тест Знания Коэффициента (KC).

Как и прежде, мы обозначаем как \(g\) генератор группы \(G\) в порядке \(|G|=p\) где дискретная регистрация трудна. Будет удобно в этой статье далее описывать нашу группу совокупно, а не мультипликативно. Таким образом, для \(\alpha\in\mathbb{F}_p,\) \(\alpha\cdot g\) означает результат суммирования \(\alpha\) копий \(g.\)

KC Тест

Для \(\alpha\in\mathbb{F}_p^*\) [1], давайте назовём пару элементов \((a,b)\) в|G| как \(\alpha\)-pair если \(a,b \neq 0\) и \(b=\alpha\cdot a.\)

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

  1. Боб выбирает случайные \(\alpha\in\mathbb{F}_p^*\) и \(a\in G.\) Он вычисляет \(b=\alpha\cdot a.\)
  2. Он пересылает Алисе "бросающую вызов" пару \((a,b).\) Заметим, что \((a,b)\) это \(\alpha\)-pair.
  3. Алиса теперь должна ответить другой парой \((a',b')\) которая также будет \(\alpha\)-pair.
  4. Боб принимает ответ Алисы только если \((a',b')\) действительно \(\alpha\)-pair. (Поскольку он знает \(\alpha\) он может проверить, действительно ли \(b'=\alpha\cdot a'.)\)

Теперь давайте подумаем, как Алиса успешно может ответить на этот вызов. Давайте предположим на секунду, что она знала \(\alpha\). В этом случае, она могла просто выбрать любую \(a'\) in \(G,\) и вычислить \(b'=\alpha\cdot a';\) и вернуть \((a',b')\) как её новую \(\alpha\)-pair.

Однако поскольку единственной информацией о \(\alpha\) является то, что \(\alpha\cdot a\) и \(G\) имеют трудную дискретную проблему регистрации, мы ожидаем, что Алиса не может найти \(\alpha.\)

Таким образом, как она может успешно ответить на вызов, не зная \(\alpha?\)

Вот естественный способ сделать это: Алиса просто выбирает некоторые \(\gamma\in\mathbb{F}_p^*,\) и отвечает с \((a',b')=(\gamma\cdot a,\gamma\cdot b).\)

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

\(b'=\gamma \cdot b = \gamma \alpha \cdot a = \alpha (\gamma\cdot a) =\alpha \cdot a',\)

Так что действительно \((a',b')\) is an \(\alpha\)-pair как и требуется.

Обратите внимание на то, что Алиса отвечает, используя эту стратегию, она знает соотношение между \(a\) и \(a'\). Таким образом она знает коэффициент \(\gamma\) таким образом, что \(a'=\gamma\cdot a.\)

Знание коэффициента предположения [2] (KCA) заключает, что это всегда имеет место, а именно:

KCA: Если Алиса возвращает действительный ответ \((a',b')\) на вызов Боба \((a,b)\) с незначительной вероятностью выбора Бобом \(a,\alpha\), тогда она знает \(\gamma\) таким образом \(a'=\gamma\cdot a.\)

KC тест и Предположение будут важными инструментами в части IV.

Что именно означают слова "Алиса знает"?

Вы можете задаться вопросом, как выразить KCA в точных математических терминах; а именно, как мы можем формализовать понятие, что "Алиса знает \(\gamma\)" математическими определениями?

Примерно это делается следующим образом: Мы скажем, что кроме Алисы, есть ещё один участник, которого мы назовём Экстрактор Алисы. Экстрактор Алисы имеет доступ к внутреннему состоянию Алисы.

Мы затем сформулируем KCA сказав, что: каждый раз, когда Алиса успешно отвечает с \(\alpha\)-pair \((a',b'),\) Экстрактор Алисы даёт результат \(\gamma\) таким образом, что \(a'=\gamma\cdot a.\) [3]

[1]\(\mathbb{F}_p^*\) обозначает отличные от нуля элементы \(\mathbb{F}_p\). Это совпадает с \(\mathbb{Z}_p^*\), которые описаны в Части I.
[2]В литературе это как правило называют Знанием Предположения Представления, поскольку традиционно это использовалось для групп, написанных мультипликативно.
[3]Полностью формальное определение должен дать Экстрактор "немного ослабив условия" и заявив вместо этого, что вероятность успешного ответа Алисы, если Экстрактор не имеет на выходе такой \(\gamma\) является незначительной.

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