Объяснение SNARKs. От вычислений к многочленам, протокол Пиноккио и сопряжение эллиптических кривых (перевод)

в 17:04, , рубрики: zk-snarks, децентрализованные сети, защита информации, информационная безопасность, криптовалюта, криптография, математика, перевод

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

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

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

Вступление от переводчика

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

Ну что же, не буду задерживать далее вашего внимания, давайте перейдем к самому интересному…

От вычислений к многочленам

В предыдущих статьях мы разработали определенный механизм для работы с многочленами. В этой части мы узнаем, как преобразовать те утверждения, которые мы хотим доказать и проверить, на языке многочленов. Идея использования многочленов таким образом начинается с новаторской работы 1991 года Лунда, Фортвона, Карлоффа и Нисана (Carsten Lund, Lance Fortnow, Howard Karloff — University of Chicago AND Noam Nisan — Hebrew University).

В 2013 году выходит еще одна еще одна прорывная работа Дженнаро, Джентри, Парно и Райковой (Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova). Эта работа определила чрезвычайно удобные преобразования вычислений в полиномы, называемые Квадратичной Арифметической Программой (КАП — Quadratic Arithmetic Program (QAP)). КАП стали основой в современных конструкциях zk-SNARK, в частности тех, которые используются в криптовалюте ZCash.

В первой части статьи будут объяснены преобразования вычислений в КАП на примере. Даже если сосредоточиться на небольшом примере, а не на общем определении, вам придется потратить достаточно времени, чтобы понять его для начала. Поэтому будьте готовы к определенным умственным усилиям :)

Предположим, что Алиса хочет доказать Бобу, что знает, $c_1, c_2, c_3∈ F_p$ такие, что $( c_1⋅ c_2) ⋅ ( c_1+ c_3)=7$. Первый шаг — представление вычисления с $c_1, c_2, c_3$ в виде арифметической схемы.

Арифметические схемы

Арифметическая схема состоит из вычисляемых арифметических операций, называемых переходами, таких как сложение и умножение, с соединениями между ними. В нашем случае схема выглядит так:
image

Соединители снизу — это входные параметры, а верхнее выходное соединение — это результат вычисления всей схемы для данных входных параметров.

Как видно на рисунке, соединители и переходы схемы обозначены определенным образом. Эти правила будут необходимы для следующего шага, а именно перевода схемы в КАП:

  • Когда один и тот же исходящий соединитель переходит в более чем один переход, считается, что он один и тот же соединитель — например, $w_1$ в примере.
  • Принимается, что у блоков умножения есть ровно два входа, которые называются левым и правым соединителями.
  • Соединители, идущие от сложения к умножения или сложению не помечаются. Считается, что входные параметры переходов сложения идут напрямую в переход умножения. В примере считается, что $w_1$ и $w_3$ являются входами $g_2$

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

Итак, для нашей схемы допустимый набор присваивания имеет вид: $( c_1, ... , c_5)$ где $c_4=c_1⋅ c_2$ и $c_5=c_4⋅ ( c_1+ c_3)$

Следуя данной терминологии, Алиса хочет доказать, что она знает допустимый набор присваивания $( c_1, ... , c_5)$ такой, что $c_5=7$. Следующим шагом будет перевод этого утверждение в полином с использованием КАП.

Приведение в КАП

Каждый переход умножения нужно соотнести с элементом поля: $g_1$ будет соотнесен с $1 ∈ F_p$ и $g_2$ с $2 ∈ F_p$. Назовем точки {1, 2} нашими целевыми точками. Теперь нам нужно определить набор «левых соединительных многочленов» $L_1, ... , L_5$, «правых соединительных многочленов» $R_1, ... , R_5$ и «выходные соединительные многочлены» $O_1, ... , O_5$.

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

Говоря конкретно, поскольку $w_1, w_2, w_4$ соответственно, левый, правый и выходной соединители $g_1$, можно определить $L_1=R_2=O_4=2 - X$, так как многочлен $2 - X$ равен одному в точке 1 соответствующий $g_1$и равен нулю в точке 2 соответствующий $g_2$.

Заметим, что $w_1$ и $w_3$ оба являются правыми входами $g_2$. Поэтому аналогично определяем $L_4=R_1=R_3=O_5=X- 1$, так как $X- 1$ равен одному в целевой точке 2 соответствующей $g_2$ и ноль в другой целевой точке.

Обозначим все остальные полиномы как нулевые многочлены.

При фиксированных значениях $( c_1, ... , c_5)$ они используются в качестве коэффициентов для определения левых, правых и выходных «суммарных» многочленов. То есть, можно определить:

$inline$L : = Σ^5_{i = 1}c_i⋅L_i, R : = Σ^5_{i = 1}c_i⋅R_i, O : = Σ^5_{i = 1}c_i⋅O_i$inline$

Затем определяем многочлен $P :=L ⋅ R - O$

Теперь, после всех этих определений, можно сформировать центральное определение: $( c_1, ... , c_5)$ является допустимым набором присваивания схемы тогда и только тогда, когда P принимает нулевое значение во всех целевых точках.

Давайте убедимся в этом, используя наш пример. Предположим, что были определены $L , R , O , P$ как указано выше, с некоторым $c_1, ... , c_5$. Давайте вычислим все эти многочлены в целевой точке 1:

Из всех $L_i$ только $L_1$ отлична от нуля в точке 1. Итак, $L ( 1 )=c_1⋅ L_1( 1 )=c_1$. Аналогично получаем $R ( 1 )=c_2$ и $O ( 1 )=c_4$.

Следовательно, $P( 1 )=c_1⋅ c_2- c_4$. Аналогичный можно получить $P( 2 )=c_4⋅ ( c_1+ c_3) - c_5$.

Другими словами, P обращается в нуль в целевых точках тогда и только тогда, когда $( с_1, ... , c_5)$ является допустимым набором присваивания.

Теперь будем использовать следующий алгебраический факт: для многочлена P и точки $a ∈ F_p$, имеем $P( a )=0$ тогда и только тогда, когда многочлен $X-a$ делит P без остатка, т.е. $P=( X- a ) ⋅ H$ для некоторого многочлена H.

Определив целевой многочлен таким образом: $T(X) :=( X- 1 ) ⋅ ( X- 2 )$, получаем, что T делит P тогда и только тогда, когда $( с_1, ... , c_5)$ является допустимым набором присваивания.

Исходя из вышесказанного, определим КАП следующим образом:

Квадратичная арифметическая программа Q порядка d и размером m состоит из многочленов $L_1, ... , L_m, R_1, ... , R_m, O_1, ... , O_m$ и целевого многочлена T порядка d.

Набор присваивания $( c_1, ... , c_m)$ удовлетворяет Q если, определяя $inline$L : = Σ^m_{i = 1}c_i ⋅ L_i, R : = Σ^m_{i = 1}c_i⋅ R_i, O : = Σ^m_{i = 1}c_i⋅ O_i$inline$ и $P:=L ⋅ R - O$, существует T, который делит без остатка P.

Следуя этой терминологии, Алиса хочет доказать, что знает набор присваивания $( c_1, ... , c_5)$, удовлетворяющий КАП, определенной выше, где $c_5=7$,

Подведем итог данной части. Мы увидели, как утверждение типа «Я знаю, $c_1, c_2, c_3$ такие, что $( с_1⋅ c_2) ⋅ ( c_1+ c_3)=7$» можно перевести в эквивалентное утверждение о многочленах, использующих КАП. Далее мы рассмотрим эффективный протокол для подтверждения знания о допустимом наборе присваивания КАП.

Выше мы попытались дать достаточно короткий пример приведения в КАП. Также рекомендуем отличный пост Виталика Бутерина для более подробной информации о преобразовании программы в КАП.

Протокол Пиноккио

Ранее мы показали, что утверждение, которое Алиса хочет доказать Бобу, может быть преобразовано в эквивалентную форму на «языке полиномов», называемом Квадратичной Арифметической Программой (КАП).

В этой части мы расскажем, как Алиса может отправить достаточно короткое доказательство Бобу, показав, что у нее есть допустимый набор присваивания для КАП. Мы будем использовать Протокол Пиноккио, разработанный Парно, Хауэлл, Джентри и Райковой (Bryan Parno, Jon Howell, Craig Gentry, Mariana Raykova).

Как было дано выше, Алиса хочет доказать, что у нее есть допустимый набор присваивания, который обладает некоторыми дополнительными ограничениями, например $c_m=7$. Но мы не будем учитывать это здесь и для простоты покажем, как просто доказать знание некоторого допустимого набора присваивания.

Если у Алисы есть допустимый набор присваивания, это означает, что если определить $L,R,O,P$ как описано выше, то существует некий многочлен H такой, что $P=H⋅T$. В частности, для любого $s∈F_p$ мы имеем $P(s)=H(s)⋅T(s)$.

Предположим теперь, что у Алисы нет допустимого набора присваивания, но она также определяет $L,R,O,P$ из некоторого недопустимого набора $(c_1,…,c_m)$. Тогда можно быть уверенными, что T не делит P. Это означает, что для любого полинома H порядком не выше d, P и $H⋅T$ будут разными многочленами. Заметим, что P и $H⋅T$ здесь имеют порядок не выше $2d$.

Для доказательства мы воспользуемся известной леммой Шварца-Зиппеля, которая утверждает, что два различных многочлена степени не выше $2d$ могут пересекаться не более в $2d$ точек $s∈F_p$. Таким образом, если p намного больше $2d$ вероятность того, что $P(s)=H(s)⋅T(s)$ для случайного выбора $s∈F_p$ ничтожна.

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

  1. Алиса выбирает полиномы $L,R,O,H$ порядка не выше d.
  2. Боб выбирает случайную точку $s∈F_p$ и вычисляет скрытие $E(T(s))$.
  3. Алиса посылает Бобу скрытие для этих полиномов в точке s, а именно $E(L(s)),E(R(s)),E(O(s)),E(H(s))$.
  4. Боб проверяет, выполняется ли требуемое равенство в точке s. То есть он проверяет $E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s))$

Повторяясь снова, если у Алисы нет допустимого набора присваивания, она в итоге будет использовать полиномы, с которыми не будет выполняться требуемое равенство для большинства случайно выбранных s. Поэтому Боб с большой вероятностью отклонит ответ Алисы, независимо от выбранного s.

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

Учитывая это, осталось еще четыре основных момента, которые необходимо решить, чтобы превратить этот эскиз в zk-SNARK. Два первых мы рассмотрим в рамках данной статье, а два остальных в заключительной статье.

Достоверность того, что Алиса выбирает свои полиномы, согласно набору присваивания

Важный момент: если у Алисы нет допустимого набора присваивания, это не означает, что она не может найти любые многочлены $L , R , O , H$ порядком не выше d, для которых $L ⋅ R - O=T⋅ H$. Это просто означает, что она не может найти такие многочлены, где $L , R$ и $O$ были «получены из набора присваивания»; а именно, что $inline$L : = Σ^m_{i = 1}c_i⋅ L_i, R : = Σ^m_{i = 1}c_i⋅ R_i, O : = Σ^m_{i = 1}c_i⋅ O_i$inline$ для набора $( c_1, ... , c_m)$.

Протокол выше только гарантирует, что она использует некоторые многочлены $L , R , O$ нужного порядка, но не гарантирует, что они были созданы из допустимого набора присваивания. Формальное доказательство несколько заковыристое, поэтому мы приведем примерное решение.

Давайте совместим многочлены $L , R , O$ в один многочлен F следующим образом:

$F=L + X^{d+ 1}⋅ R + X^{2 ( d+ 1 )}⋅ O$

Смысл умножения R на $X^{d+ 1}$ и O на $X^{2 ( d+ 1 )}$ в том, чтобы «не смешивать» коэффициенты $L , R , O$ в F. Коэффициенты $1 , X, ... , X^d$ в F соответствуют L, следующие $d+ 1$ коэффициентов $X^{d+ 1}, ... , X^{2 (d+ 1)}$ соответствуют R, а последние $d+ 1$ коэффициентов соответствуют O.

Объединим полиномы в определении КАП аналогичным образом, определяя для каждого $i ∈ { 1 , ... , m }$ многочлен $F_i$ чьи первые $d+ 1$ коэффициенты являются коэффициентами $L_i$, а затем коэффициенты $R_i$ и затем $O_i$. То есть для каждого $i ∈ { 1 , ... , m }$ мы определяем многочлен:

$F_i=L_i+ X^{d+ 1}⋅ R_i+ X^{2 ( d+ 1 )}⋅ O_i$

Заметим, что когда мы суммируем два $F_i$, то $L_i, R_i$ и $O_i$ «суммируются отдельно». Например, $F_1+ F_2=( L_1+ L_2) + X^{d+ 1}⋅ ( R_1+ R_2) + X^{2 ( d+ 1 )}⋅ ( O_1+ O_2)$.

В более общем случае предположим, что у нас есть $F=Σ^m_{i=1}c_i⋅ F_i$ для некоторого набора $( c_1, ... , c_m)$. Тогда мы также получаем $inline$L = Σ^m_{i=1}c_i⋅ L_i, R = Σ^m_{i=1}c_i⋅ R_i, O = Σ^m_{i=1}c_i⋅ O_i$inline$ для тех же самых коэффициентов $( c_1, ... , c_m)$. Другими словами, если F является линейной комбинацией $F_i$ это означает, что $L , R , O$ были действительно созданы из набора.

Поэтому Боб попросит Алису доказать ему, что F является линейной комбинацией от $F_i$. Это делается аналогично протоколу для достоверного вычисления:

Боб выбирает случайный $β∈ F^*_p$, и отправляет Алисе скрытия $inline$E( β⋅ F_1(s )) , ... , E( β⋅ F_m(s) )$inline$. Затем он просит Алису отправить ему скрытие $E( β⋅ F( s ) )$. Если ей это удается, расширенная версия Знания о Принятом Коэффициенте предполагает, что она знает, как создать F, являющуюся линейной комбинацией от $F_i$.

Добавление части «нулевого разглашения» — скрытие набора присваивания

В zk-SNARK Алиса хочет скрыть всю информацию о своем наборе присваивании. Однако скрытия $E( L ( s ) ) , E( R ( s ) ) , E( O ( s ) ) , E( H(s)$ предоставляют некоторую информацию о наборе.

Например, с учетом некоторого другого удовлетворяющего набора присваивания $( c'_1, ... , c'_m)$ Боб может вычислить соответствующие $L', R', O', H'$ и скрытия $E( L'( s ) ) , E( R'( s ) ) , E( O'( s ) ) , E( H'( s ) )$. Если они отличаются от ответа Алисы, он может понять, что $( c'_1, ... , c'_m)$ не набор присваивания Алисы.

Чтобы избежать такой утечки информации о ее наборе, Алиса скрывает свой набор, добавив «случайное Т-смещение» для каждого многочлена, т.е. выбирает случайные $inline$δ_1, δ_2, δ_3∈ F^*_p$inline$, и определяет $inline$L_z: = L + δ_1⋅ T, R_z: = R + δ_2⋅ T, O_z: = O + δ3⋅ T$inline$.

Предположим, что $L , R , O$ были получены из удовлетворяющего набора присваивания. Следовательно $L ⋅ R - O=T⋅ H$ для некоторого многочлена H. Поскольку мы только что добавили кратное T везде, T также делит $L_z⋅ R_z- O_z$. Давайте убедимся в этом:

$inline$L_z⋅ R_z- O_z= ( L + δ_1⋅ T) ( R + δ_2⋅ T) - (O + δ_3⋅ T)$inline$ $inline$= ( L ⋅ R - O ) + L ⋅ δ_2⋅ T+ δ_1⋅ T⋅ R + δ_1δ_2⋅ T^2- δ_3$inline$ $inline$= T⋅ ( H+ L ⋅ δ_2+ δ_1⋅ R + δ_1δ_2⋅ T- δ_3)$inline$

Таким образом, определяя $inline$H_z= H+ L ⋅ δ_2+ δ_1⋅ R + δ_1δ_2⋅ T- δ_3$inline$, получим $L_z⋅ R_z- O_z=T⋅ H_z$. Поэтому, если Алиса использует многочлены $L_z, R_z, O_z, H_z$ вместо $L , R , O , H$, Боб всегда будет принимать ее ответ.

С другой стороны, эти полиномы, вычисленные в точке $s ∈ F_p$ при условии, что $T(s) ≠ 0$ (что практически всегда для всех d и s), не содержат никакой информации о допустимом наборе присваивания. Например, $T(s)$ отлична от нуля и $δ_1$ является случайной. Тогда $δ_1⋅T(s)$ является случайным значением, поэтому $L_z( s )=L ( s ) + δ_1⋅ T( s )$ не будет содержать никакой информации о $L ( s )$ поскольку он «замаскирован» этим случайным значением.

Что осталось рассмотреть в финальной части?

Мы примерно показали схему протокола Пиноккио, в котором Алиса может убедить Боба в том, что она обладает допустимым набором присваивания для КАП, не раскрывая информацию об этом наборе. Но осталось еще два важных вопроса, которые необходимо решить, чтобы получить zk-SNARK:

  • В схеме Бобу нужен полином H, который «поддерживает умножение». Например, ему нужно вычислить скрытие $E( H( s ) ⋅ T( s ) )$ из $E( H( s ) )$ и $E( T( s ) )$. Тем не менее, мы пока не рассматривали примеры H, который позволяет это сделать. Мы рассматривали только H, который поддерживает сложение и линейные комбинации.
  • Также мы обсудили интерактивные протоколы между Алисой и Бобом. Однако, наша конечная цель, состоит в том, чтобы позволить Алисе отправлять неинтерактивные доказательства в одно сообщение. Эти сообщения при этом являются общедоступными. Это означает, что любой, кто увидит это «сообщение — доказательство», также может убедиться в его достоверности, а не только Боб (который предварительно взаимодействовал с Алисой).

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

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

Автор: AgentRX

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js