Эволюция рекурсивных снарков
zkSNARK
zkSNARK — это очень сложный Zero Knowledge Proofs, доказывающий некоторую программу, в которой присутствуют секретные входные данные, которые не разглашаются при доказательстве того, что программа отработала корректно.
The most widely used snarks
Почти все наиболее известные снарки сейчас используются в блокчейне.
Groth 16 — это самый короткий снарк, то есть доказательство занимает три групповых элемента и где-то 280 байт.
STARK — в принципе они могут делать то же самое что и Groth 16, но это нечто совершенно универсальное. Разработчики называют это даже не Universal а Transparent потому, что нет никакой привязки к Circuit, который доказывается, и нет процедуры trusty сетапа. Кроме того, это система квантовая, то есть её невозможно будет взломать, когда появятся квантовые компьютеры, которые поломают абсолютно всю асимметричную криптографию, используемую сейчас. И тогда Groth 16, Plonk и Halo 2 — станут не нужны.
Но проблема в том, что они генерируют очень большие доказательства. Однако, огромный их плюс заключается в том, что это очень быстрая система и в результате некоторые реализации используют рекурсию. То есть, они доказывают какие-то утверждения Circuit с помощью STARK, потом доказывают саму процедуру верификации STARK с помощью какого-нибудь снарка и получают компактное доказательство в районе нескольких килобайт или сотен байт, если использовать Groth 16.
Pairing Friendly Curves
Pairing Friendly Curves — это кривые, у которых есть определённая структура и они удовлетворяют следующему условию: у них параметр — embedding degree. Он имеет отношение не к самой кривой, а к порядку подгруппы Q, который использует это кривая. Таким образом существует кривая и в ней есть число элементов - точек, которые будут использоваться. Это число равно Q. Кривая может состоять из всего Q точек, но обычно порядок наиболее удобных кривых не равен порядку этой подгруппы.
Embedding degree — минимальное K, которое делит количество элементов поля, p в степени d - 1. То есть делит порядок мультипликативный подгруппы поля. Pairing Friendly означает, что вот это значение должно быть очень маленькое. То есть, в принципе у любой кривой такой параметр есть, но он огромный и это значит, что Pairing посчитать на практике практически невозможно.
Pairings
Billiner map — это такое понятие, которое удовлетворяет следующим свойствам: есть 2 точки из 2 разных групп — G1 и G2, обе порядка Q. Если мы считаем отображение от этих точек скалярного умножения aS и bT, то мы сможем посчитать, то же самое отображение, считая Pairing от S и T, возведя Pairing в степень ab.
Non-degeneracy — для любой точки S, если Pairing равен 1, то другая точка обязательно будет равна 0. То есть, это будет точка на бесконечности.
Pairings Friendly Curves security
В Pairings Friendly Curves безопасность зависит от классической проблемы дискретного логарифма. Этот логарифм будет браться в поле, которое является расширением над степенью k, называемая Embedding degree.
Chains of elliptic curves
Если мы хотим с помощью SNARK доказывать какие-то утверждения и они достаточно сложные и длинные, то это можно делать с помощью Chains of elliptic curves.
Chains of elliptic curves — это Circuit, который лежит в каком-то поле, равном скалярному полю этой кривой. То есть, это количество точек — число Q. Сам пруф имеет вид точек этой кривой - поле Fp. Далее, если мы хотим доказать это еще раз, то мы не можем использовать ту же самую кривую потому, что в результате это повысит стоимость в сотни раз.
Если у нас есть какое-то доказательство и мы хотим доказать его, то следующая кривая должна иметь скалярное поле точно такое же как поле первой кривой. В данном случае — это E2.
Cycles of elliptic curves
Если мы имеем дело с циклом кривых, то в таком случае мы можем разбивать вычисления на какие-то куски. Если у нас очень большое вычисление, то можно строить Circuit с доказательством в одном поле и опять же доказывать это уже в следующем поле, а потом обратно переходить к первой кривой.
Было бы замечательно если бы можно было использовать кривую, у которой скалярное поле равно полю самой кривой. Тогда не приходилось скакать с одной кривой на другую. Такие кривые называются аномальными кривыми и их нельзя использовать в криптографии потому что для того, чтобы посчитать дискретный логарифм, то есть найти соотношение между двумя точками, решить это уравнение в виде скаляра, требуется полиномиальное время. Фактически аномальные кривые, которые даже с большими аргументами, взламываются моментально.
Some cyclic pairing-friendly curves
Pairing-friendly curves, к сожалению, имеет очень большие поля. Например, кривые MNT4 и MNT6 прекрасно описаны, на них есть rfс, можно использовать их для рекурсивных доказательств, но в таком случае производительность упадёт в 10 раз. Потому что поле получается больше в 3 раза, чем обычное поле 256 бит, которое используется в SNARK чаще всего.
Recursive proof
У нас есть доказательство Circuit (C) и на вход приходит секретное значение witness — открытый ключ верификации, который называют внутренним доказательством. Есть внешнее доказательство, доказывающее процедуру верификации, которая уже была проведена и в этой процедуре само доказательство уже является секретным. Результат является доказательством того, что первое доказательство — корректно. То есть Circuit отработал абсолютно корректно и значит witness известен.
Use cases of snark recursion
Snark recursion нужен для того, чтобы сжать очень сложные доказательства, а также для zkRollups.
Что должен сделать доказатель, чтобы обработать большое количество транзакций?
Самый простой способ - это проверить, что все балансы были соблюдены, и что не было двойных списаний. Он должен создать криптографические доказательства для всех хэшей и цифровых подписей в этих транзакциях. Фактически это представляет собой последовательность в рамках криптографического контура, которая состоит из огромного Circuit. В Circuit содержится утверждение о том, что все проверки подписи выполнены корректно.
Если говорить о нагрузке и вычислениях, можно сделать это более сложным, интересным и быстрым. Можно взять и параллельно обработать эти доказательства. Например, взять первые 10 транзакций, создать для них пруф, а затем кто-то другой может обработать следующие 10 транзакций. Таким образом, не нужно ждать формирования блока, а можно обрабатывать транзакции по мере их поступления.
Далее, необходимо выполнить рекурсивное доказательство, убедившись, что все доказательства для каждой десятки корректны. Фактически это объединяет все доказательства в один контур, что делает его менее сложным. На практике для этого используются деревья Меркла, что позволяет серьезно распараллеливать процесс.
Verification in Grooth16
Ниже пример того, что надо доказать, если мы хотим доказать доказательство Grooth16. Мы видим пруф, verification key и публичные инпуты. Если мы попытаемся решить эту проблему прямым путем, то у нас получится гигантское количество констрейтов, которые возникнут в системе. Но по-другому у нас не получится это сделать, поскольку эффективных доказательств для pairing-friendly кривых нет. У нас нет эффективных циклов. Процедура доказательства, которая состоит из четырёх пейрингов, занимает около 20 млн констрейтов. Это называется побитовое доказательство. Если бы мы доказывали это всё в поле, то есть нам не надо было доказывать отдельное сложение по модулю P, умножение по модулю P, то это всё было бы гораздо быстрее.
Plonk
KZG commitment использует pairing-friendly кривые. В классическом Plonk, к сожалению, такие же проблемы, как и в Grooth16. То есть если мы хотим делать рекурсию на Plonk, нам придётся менять KZG commitment, что многие и делают. Таким образом возникают системы типа Plonk2. То есть меняется commitment и происходит избавление от тяжёлых pairing-friendly кривых.
Такие commitment называются FRI (Fast Reed-Solomon Interactive oracle proofs) и Inner Product Argument.
Cycle curves
FRI вообще не использует эллиптические кривые, Inner Product Argument может использовать обычные кривые. Поэтому мы можем использовать кривые под названием семейство Pasta. Это две кривые: Pallas и Vesta, что вместе называется Pasta. Они образуют цикл, то есть с помощью них можно доказывать в цикле большое количество доказательств и с помощью этого избавиться от побитового доказательства.
Inner Product Argyment
Полиномиальный комитмент - это когда у нас есть prover и verifier, и есть многочлен p(x), который знает и хочет доказать verifier, не раскрывая сам многочлен.
Prover начинает с вычисления некоего значения, называемого commitment, от этого многочлена, и отправляет его verifier. Затем verifier отправляет prover значение X, которое он хочет, чтобы prover вычислил, и также доказал, что он честно вычислил это значение. Prover вычисляет p(x) и отправляет значение v вместе с доказательством p.
Verifier, с помощью специальной процедуры проверки, определяет, было ли вычисление произведено неправильно или правильно, и в зависимости от этого либо принимает, либо отвергает результат.
Pedersen commitment
Пусть G — вектор из n генераторов группы, и U - это отдельный генератор. Если мы хотим доказать, что у нас есть многочлен из n элементов, и мы хотим сделать такой commitment, то для этого нам необходим вектор из таких элементов, при условии, что невозможно вычислить дискретный логарифм между элементами вектора G и генератором U. В противном случае можно было бы подделать такие доказательства.
Есть вектор коэффициентов p и commitment. Мы умножаем значение C — скалярное умножение элементов вектора на точки группы из вектора G. В результате у нас получится пруф, состоящий из двух векторов L и R, включая точку G0 и элемент p0, и количество элементов будет равно логарифму по основанию 2 от n. Это относительно простое доказательство, и его размер логарифмический.
Inner Product Argyment
Ниже мы выполняем commitment, то есть берем вектор элементов, которые мы желаем вычислить, и находим степени этих элементов. Таким образом, мы практически обозначаем процесс вычисления этого многочлена. Иными словами, V представляет вычисление многочлена. Затем мы выполняем k раундов, где k - это логарифм по основанию 2 от n, и проводим вычисления. Мы разделяем эти векторы пополам: p - это вектор с коэффициентами, b - это вектор значений, который verifier хочет понять, и G - это элементы генератора группы.
Проводя k таких вычислений каждый раз, мы получаем новый челлендж от verifier, приходим к тому, что verifier получает доказательство, и он может проверить, насколько правильно было это всё вычислено.
Единственная проблема в данном случае заключается в том, что у нас возникает линейное время. Несмотря на то, что число элементов логарифмическое, оно оказывает значительное воздействие на оптимизацию. И здесь на помощь приходит рекурсия. Мы используем аккумуляторы и рассчитываем рекурсивные SNARK каждый раз. В результате, если у нас есть значительный объем доказательств, то линейное время для одной верификации компенсируется тем, что все commitment фактически аккумулируются. Таким образом, мы имеем хорошую временную эффективность при проверке доказательств.
