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

Ariel Gabizon | Apr 11, 2017

<< Часть III

В этой части, мы основываемся на Части II и III чтобы разработать протокол для слепой оценки поддающихся проверке многочленов, которые мы вскоре определим. В части V мы начнём видеть, как этот протокол может использоваться для строительства SNARK, поэтому потерпите меня немного больше для связи со SNARK :).

Предположим, как в Части II, что у Алисы есть многочлен \(P\) степени \(d\) и у Боба есть точка \(s\in\mathbb{F}_p\) которую он выбрал случайно. Мы хотим построить протокол, который позволит Бобу изучить \(E(P(s))\), то есть скрыть \(P\) определённый в \(s\), с двумя дополнительными свойствами:

  1. Слепота: Алиса не будет знать \(s\) (и Боб не будет знать \(P\)).
  2. Проверяемость: Вероятность, что Алиса пересылает значение, не имеющее вида \(E(P(s))\) для \(P\) степени \(d\) которое ей известно, но Боб по-прежнему его принимает - ничтожно мала.

Это мы называем проверяемостью слепой оценки многочлена. Протокол в Части II дал нам первый пункт, но не дал второй. Чтобы получить проверяемость, нам нужна расширенная версия Знания Коэффициента Предположения (KCA) которую мы презентовали в Части III.

Свойства проверяемости и слепоты полезны вместе, так как они позволяют Алисе решить, какой многочленl \(P\) она будет использовать без того, чтобы видеть \(s\). [1] В некотором смысле это передаёт Алисе "ответный многочлен" не видя "точки проблемы" \(s\). Такая интуиция станет более ясной в следующих статьях серии.

Расширенный KCA

KCA, как мы его определили в Части III, по сути говорит что-то вроде этого: Если Боба даёт Алисе некоторую \(\alpha\)-pair \((a,b = \alpha\cdot a)\) и затем Алиса создаёт другую \(\alpha\)-pair \((a',b')\), то она знает \(c\) так как \(a'=c\cdot a\). Другими словами Алиса знает \(a'\) и \(a\).

Теперь предположите, что вместо одной Боб пересылает Алисе несколько \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (для того же самого \(\alpha\)); и затем снова, после получение этих пар, Алиса генерирует несколько других \(\alpha\)-pair \((a',b')\). Вспомните, основной момент в том, что Алиса должна делать так, хотя она не знает \(\alpha\).

Как мы говорили в Части III, естественный способ для Алисы произвести такой \(\alpha\)-pair, будет в том, чтобы взять одну из пар, \((a_i,b_i)\) которую она получила от Боба, и умножить оба элемента на некоторый \(c\in\mathbb{F}^*_p\); если \((a_i,b_i)\) будет \(\alpha\)-pair, то \((c\cdot a_i,c\cdot b_i)\) будет также. Но может Алиса произвести \(\alpha\)-pairs большим количеством способов сейчас, когда она получила множественные \(\alpha\)-pairs? Возможно, используя несколько из полученных \(\alpha\)-pairs одновременно для получения новой?

Ответ да: Например, Алиса может выбрать два values \(c_1,c_2\in \mathbb{F}_p\) и вычислить пару \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\). Лёгкое вычисление показывает, что, пока \(a'\) отличается от нуля, это также \(\alpha\)-pair:

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

Более широко, Алиса может взять любую линейную комбинацию данных \(d\) пар - затем выбрать любые \(c_1,\ldots,c_d\in\mathbb{F}_p\) и определить \((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\).

Заметим, что если Алиса использует эту стратегию для того, чтобы произвести её \(\alpha\)-pair она будет знать некоторое линейное отношение между \(a'\) и \(a_1,\ldots,a_d\); то есть, она знает \(c_1,\ldots,c_d\) таким образом \(a'=\sum_{i=1}^d c_i\cdot a_i\).

Расширенный KCA это по сути заявление, что есть единственный способ для Алисы, которым она может создать \(\alpha\)-pair; то есть каждый раз достигая успеха она будет знать линейное соотношение между \(a'\) и \(a_1,\ldots,a_d\). Более формально, предположим, что \(G\) это группа размера \(p\) с генератором \(g\) описанная дополнительно как в Части III. d-сила Знания Коэффициента Приближения (d-KCA) [2] в \(G\) следующая:

d-KCA: Предположим, что Боб выбирает случайную * |alphainFpstar| *и \(s\in\mathbb{F}_p\), и пересылает Алисе \(\alpha\)-pairs \((g,\alpha\cdot g), (s\cdot g,\alpha s\cdot g),\ldots,(s^d\cdot g,\alpha s^d\cdot g)\). Предположим, что Алиса тогда выдаёт другую \(\alpha\)-pair \((a',b')\). Затем, за исключением пренебрежимо малой вероятности, Алиса знает \(c_1,\ldots,c_d\in\mathbb{F}_p\) таким образом \(\sum_{i=0}^d c_i s^i\cdot g = a'\).

Обратите внимание, что в d-KCA Боб посылает не произвольный набор \(\alpha\)-pairs, а с определённой "многочленной структурой". Это будет полезно для протокола ниже.

Проверяемый протокол слепой оценки

Предположим, что наше HH является отображением \(E(x)=x\cdot g\) для генератора \(g\) или \(G\) как показано выше.

Чтобы упростить, мы представим протокол для этого особого \(E\):

  1. Боб выбирает случайные \(\alpha\in\mathbb{F}_p^*\), и пересылает Алисе, скрывая \(g,s\cdot g,\ldots,s^d\cdot g\) (от \(1,s,\ldots,s^d\)) а также скрывая \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) (от \(\alpha,\alpha s,\ldots,\alpha s^d\)).
  2. Алиса вычисляет \(a=P(s)\cdot g\) и \(b=\alpha P(s)\cdot g\) используя элементы, пересланные на первом шаге, и пересылает их Бобу.
  3. Боб проверяет, что \(b=\alpha \cdot a\), и принимает их только если равенство соблюдается.

Во-первых, заметим, что данные коэффициенты \(P\), \(P(s)\cdot g\) являются линейной комбинацией \(g,s\cdot g,\ldots,s^d\cdot g\); и \(\alpha P(s)\cdot g\) это линейная комбинация \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\). Таким образом, подобно Протоколу в Части II, Алиса может действительно вычислить эти значения из посланий Боба для многочлена \(P\) который она знает.

Во-вторых, by the d-KCA если Алиса пересылает \(a\), \(b\) таким образом, что \(b=\alpha \cdot a\) то она почти наверняка знает \(c_1,\ldots,c_d\in\mathbb{F}_p\) следовательно \(a=\sum_{i=0}^d c_is^i\cdot g\). В этом случае, \(a=P(s)\cdot g\) для многочлена \(P(X)=\sum_{i=0}^d c_i\cdot X^i\) известного Алисе. Другими словами, вероятность того, что Боб принимает на шаге 3 в то время, как Алиса не знает такой \(P\) пренебрежимо мала.

Подытожим, используя d-KCA мы разработали протокол для слепой оценке поддающихся проверке многочленов. В следующих статьях вы узнаете, как эти строительные блоки будут использоваться для создания SNARK.

[1]В полностью формальном доказательстве вещи немного более тонкие, как Алиса видит некоторую информацию о \(s\) перед выбором её \(P\) - например, ⇥скрытые \(s,\ldots,s^d\).
[2]d-KCA представлена в документе Йенса Грота.

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