Zk-SNARKs: под капотом

Автор: Vitalik Buterin

Оригинальное название: 《Zk-SNARKs: Under the Hood》

Дата публикации: 1 февраля 2017 года

Это третья часть серии статей, объясняющих, как работает технология, стоящая за zk-SNARKs; предыдущие статьи о квадратичных арифметических программах и парных эллиптических кривых являются обязательными для чтения, и в этой статье предполагается знание этих двух концепций. Также предполагается базовое понимание того, что такое zk-SNARK и что они делают. Также см. статью Кристиана Рейтвисснера для еще одного технического введения.

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

В этой статье мы сосредоточимся на протоколе Pinocchio (обычно называемом PGHR13), разработанном Парно, Джентри, Хауэллом и Райковой, начиная с 2013 года; основные механизмы претерпели некоторые изменения, поэтому zk-SNARK схемы, реализуемые на практике, могут немного отличаться, но основные принципы обычно остаются неизменными.

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

По сути, если у вас есть пара точек P и Q, где P * k = Q, и у вас есть точка C, то невозможно вывести C * k, если C не "происходит" от P каким-либо образом. Это может показаться интуитивным, но это предположение на самом деле не может быть выведено из любых других предположений, которые мы обычно используем для доказательства безопасности протоколов на основе эллиптических кривых (например, сложности дискретного логарифма), поэтому zk-SNARK на самом деле зависит от более общего и менее стабильного фундамента, чем эллиптическая криптография — хотя он все еще достаточно прочен, чтобы большинство криптографов могли его принять.

Теперь давайте посмотрим, как это использовать. Предположим, есть пара точек (P, Q), которая упала с неба, где P * k = Q, но никто не знает, каково значение k. Теперь предположим, что я предоставляю пару точек (R, S), где R * k = S. Тогда предположение KoE означает, что я могу вывести эту пару точек единственным способом, взяв P и Q и умножив оба на некоторый коэффициент r, который я знаю. Также обратите внимание, что благодаря магии парных эллиптических кривых проверка R = k * S на самом деле не требует знания k — наоборот, вы можете просто проверить e(R, Q) = e(P, S).

Давайте сделаем что-то более интересное. Предположим, у нас есть десять пар точек, упавших с неба: (P1, Q1), (P2, Q2)… (P10, Q10). Во всех случаях Pi * k = Qi. Предположим, я затем предоставляю вам пару точек (R, S), где R * k = S. Что вы теперь знаете? Вы знаете, что R является некоторой линейной комбинацией P1 * i1 + P2 * i2 + … + P10 * i10, где я знаю коэффициенты i1, i2 … i10. То есть, чтобы получить такую пару точек (R, S), единственный способ — это взять некоторые кратные P1, P2…P10 и сложить их, а затем провести аналогичные вычисления с Q1, Q2…Q_10.

Обратите внимание, что для любого конкретного набора точек P1…P10, который вы можете захотеть проверить на линейную комбинацию, вы на самом деле не можете создать соответствующие точки Q1…Q10, не зная, что такое k; если вы действительно знаете, что такое k, то вы можете создать пару (R, S), где R * k = S для любого R, который вы хотите, без создания линейной комбинации. Поэтому, чтобы это работало, абсолютно необходимо убедиться, что человек, создающий эти точки, заслуживает доверия, и что после создания десяти точек k фактически удаляется. Вот откуда возникает концепция "доверенной настройки".

Помните, что решение QAP — это набор полиномов (A, B, C), таких что A(x) * B(x) - C(x) = H(x) * Z(x), где:

• A — это линейная комбинация набора полиномов {A1…Am}
• B — это линейная комбинация с теми же коэффициентами {B1…Bm}
• C — это линейная комбинация с теми же коэффициентами {C1…Cm}

Наборы {A1…Am}, {B1…Bm} и {C1…Cm} и полином Z являются частью формулировки задачи.

Однако в большинстве практических случаев A, B и C очень велики; для таких вещей, как хеш-функции, имеющие тысячи логических ворот, полиномы (и факторы линейных комбинаций) могут содержать тысячи членов. Поэтому мы не заставляем доказателя напрямую предоставлять линейные комбинации, а используем приемы, которые мы представили выше, чтобы позволить доказателю доказать, что то, что они предоставляют, является линейной комбинацией, но не раскрывать ничего другого.

Вы, возможно, заметили, что вышеупомянутые приемы применимы к точкам эллиптической кривой, а не к полиномам. Поэтому на самом деле происходит следующее: мы добавляем следующие значения в доверенную настройку:

G * A1(t), G * A1(t) * ka G * A2(t), G * A2(t) * ka
…
G * B1(t), G * B1(t) * kb G * B2(t), G * B2(t) * kb
…
G * C1(t), G * C1(t) * kc G * C2(t), G * C2(t) * kc
…
Вы можете рассматривать t как "секретную точку" для вычисления полиномов. G — это "генератор" (некоторые случайные точки эллиптической кривой, назначенные частью протокола), t, ka, kb и kc — это "токсичные отходы", которые абсолютно необходимо удалить любой ценой, иначе у кого-то, кто их имеет, будет возможность создать ложные доказательства. Теперь, если кто-то дает вам пару точек P, Q, так что P * ka = Q (напоминаем: нам не нужно ka для проверки этого, потому что мы можем сделать проверку пар), то вы знаете, что они предоставили вам линейную комбинацию полиномов Ai, которые вы оцениваете в t.

Таким образом, до сих пор доказатель должен предоставить:

πa = G * A(t), π'a = G * A(t) * ka πb = G * B(t), π'b = G * B(t) * kb
πc = G * C(t), π'c = G * C(t) * k_c

Обратите внимание, что доказателю на самом деле не нужно знать (и не следует знать!) t, ka, kb или k_c для вычисления этих значений; наоборот, доказатель должен быть в состоянии вычислить эти значения только на основе точек, которые мы добавили в доверенную настройку.

Следующий шаг — убедиться, что все три линейные комбинации имеют одинаковые коэффициенты. Мы можем сделать это, добавив в доверенную настройку еще одну группу значений: G * (Ai(t) + Bi(t) + C_i(t)) * b, где b — это еще одно число, которое следует рассматривать как "токсичные отходы", и которое должно быть немедленно выброшено после завершения доверенной настройки. Затем мы можем позволить доказателю создать линейную комбинацию с этими значениями, имеющими одинаковые коэффициенты, и использовать тот же прием пар, чтобы проверить, соответствует ли это значение предоставленным A + B + C.

Наконец, нам нужно доказать, что A * B - C = H * Z. Мы снова выполняем это с помощью проверки пар:

e( πa, πb) / e( πc, G) ?= e( πh, G * Z(t))

где π_h = G * H(t). Если эта связь между уравнением и A * B - C = H * Z не имеет смысла для вас, вернитесь и прочитайте статью о парных.

Мы увидели выше, как преобразовать A, B и C в точки эллиптической кривой; G просто является генератором (то есть точка эллиптической кривой, эквивалентная числу один). Мы можем добавить G * Z(t) в доверенную настройку. H более сложен; H просто полином, и мы редко заранее предсказываем коэффициенты каждого отдельного решения QAP. Поэтому нам нужно добавить больше данных в доверенную настройку; конкретный порядок:

G, G * t, G * t², G * t³, G * t⁴ …。

В доверенной настройке Zcash эта последовательность достигает около 2 миллионов; это количество степеней, необходимое для того, чтобы гарантировать возможность вычисления H(t) в любой момент времени, по крайней мере, для конкретного QAP, который их интересует. Таким образом, доказатель может предоставить проверяющему всю информацию для окончательной проверки.

Есть еще один момент, который нам нужно обсудить. Чаще всего мы не просто хотим абстрактно доказать существование решения для определенной задачи; наоборот, мы хотим доказать правильность конкретного решения (например, доказать, что если вы используете слово "cow" и хешируете его с помощью SHA3 миллион раз, конечный результат начинается с 0x73064fe5), или если вы ограничиваете существование решения некоторыми параметрами. Например, в примерах криптовалют, где сумма транзакции и баланс счета зашифрованы, вы хотите доказать, что знаете некоторый ключ расшифровки k, так что:

Зашифрованные oldbalance, txvalue и new_balance должны быть открыто указаны, так как это те конкретные значения, которые мы хотим проверить в определенный момент времени; только ключ расшифровки должен оставаться скрытым. Необходимо внести некоторые тонкие изменения в протокол, чтобы создать "настраиваемый ключ проверки", соответствующий определенным ограничениям входных данных.

Теперь давайте сделаем шаг назад. Сначала вот полный алгоритм проверки, предоставленный Беном Сассоном, Тромером, Вирзой и Чизой:

Первая строка обрабатывает параметризацию; по сути, вы можете рассматривать его функцию как создание "настраиваемого ключа проверки" для конкретного экземпляра задачи, в которой указаны определенные параметры. Вторая строка — это проверка линейной комбинации A, B, C; третья строка — это проверка того, имеют ли линейные комбинации одинаковые коэффициенты, четвертая строка — это проверка произведения A * B - C = H * Z.

В общем, процесс проверки состоит из нескольких умножений эллиптической кривой (по одному для каждой "публичной" переменной ввода) и пяти проверок пар, одна из которых включает дополнительное умножение пар. Доказательство содержит восемь точек эллиптической кривой: A(t), B(t) и C(t) по одной паре точек, b * (A(t) + B(t) + C(t)) имеет одну точку πk, а также точка πh для H(t). Из этих семи точек на кривой Fp (по 32 байта, так как вы можете сжать y-координату до одного бита), в реализации Zcash одна точка (πb) находится на искаженной кривой F_p² (64 байта), так что общий размер доказательства составляет около 288 байт.

Две наиболее вычислительно сложные части создания доказательства:

Разделить (A * B - C) / Z, чтобы получить H (алгоритм на основе быстрого быстрого преобразования Фурье может выполнить это за время, близкое к квадратичному, но вычислительная нагрузка все равно велика)
Выполнить операции умножения и сложения эллиптической кривой для создания значений A(t), B(t), C(t) и H(t) и их соответствующих пар
Основная причина, по которой создание доказательства так сложно, заключается в том, что если мы хотим создать нулевое знание из этого, отдельные логические ворота в исходных вычислениях превращаются в операции, которые должны быть зашифрованы с помощью операций эллиптической кривой. Этот факт, наряду с суперлинейностью быстрого преобразования Фурье, означает, что создание доказательства для транзакций Zcash занимает около 20-40 секунд.

Еще один очень важный вопрос: можем ли мы попытаться сделать доверенную настройку немного… менее требующей доверия? К сожалению, мы не можем сделать ее полностью недоверенной; само предположение KoE исключает возможность создания независимых пар (Pi, Pi * k), не зная, что такое k. Однако мы можем значительно повысить безопасность, используя многопартийные вычисления N-of-N — то есть строя доверенную настройку между N сторонами, при условии, что хотя бы один участник удаляет свои токсичные отходы, тогда вы в порядке.

Чтобы немного понять, как это сделать, вот простой алгоритм для получения существующего набора (G, G * t, G * t², G * t³…), и "добавления" вашего собственного секрета, чтобы вам понадобились ваши секреты и предыдущие секреты (или предыдущий набор секретов), чтобы обмануть.

Выходной набор очень прост:

G, (G * t) * s, (G * t²) * s², (G * t³) * s³…

Обратите внимание, что вы можете знать только исходный набор и s, чтобы сгенерировать этот набор, и функция нового набора такая же, как у старого набора, просто теперь используется t*s в качестве "токсичных отходов", а не t. Пока вы и создатель предыдущего набора (или нескольких людей) не удалили свои токсичные отходы и затем не сговорились, эта группа "безопасна".

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

Еще одна активная область исследований — это использование других методов, не использующих пары, и того же примера доверенной настройки для достижения той же цели. См. недавнюю презентацию Эли Бен Сассона для другого варианта (хотя имейте в виду, что он по крайней мере математически так же сложен, как SNARK!).

Особая благодарность Ариэлю Габизону и Кристиану Рейтвисснеру за рецензирование.