Автор: 0xAlpha Соучредитель @DeriProtocol; Составитель: DODO Research
Введение
zk-SNARK, или «краткие неинтерактивные аргументы знания с нулевым разглашением», позволяют верификатору подтвердить, что доказывающий обладает определенными специфическими знаниями, известными как свидетели, которые удовлетворяют определенным отношениям, не раскрывая ничего о самом свидетеле.
Генерация zk-SNARK для конкретной задачи состоит из следующих четырех этапов:
- Преобразование задачи (или функции) в схему арифметического вентиля.
- Затем эта схема преобразуется в матричную формулу.
- Эта матричная формула далее преобразуется в полином, который должен делиться на определенный минимальный многочлен.
- Наконец, эта делимость представлена в точках эллиптической кривой в конечных полях, где и происходит доказательство.
Первые три шага просто преобразуют представление исходного оператора. На последнем шаге используется гомоморфное шифрование для проецирования оператора шага 3 в криптографическое пространство, что позволяет проверяющему проверить зеркальное выражение в нем. Учитывая, что в этой проекции используется асимметричная криптография, невозможно проследить исходное утверждение с третьего шага, что обеспечивает раскрытие с нулевым разглашением.
Математический бэкграунд, необходимый для прочтения этой статьи, эквивалентен уровню алгебры первокурсника для специальностей STEM. Единственная концепция, которая может быть сложной, — это, вероятно, шифрование на основе эллиптических кривых. Для тех, кто не знаком с этим, ее можно рассматривать как экспоненциальную функцию с особой мощностью, имея в виду, что ее обратная остается нерешенной.
В этой статье будут следовать следующим правилам обозначения:
- Матрица: полужирные прописные буквы, например, A; Явное написание в форме
- Вектор: строчные буквы со стрелками, написанные в явной форме [ ] ; По умолчанию все векторы являются столбчатыми
- Скалярный: Обычное буквенное представление
Возьмем в качестве примера этот вопрос:
f(x)=x^3+x^2+5 (1)
Допустим, Алиса хочет доказать, что она его знает. Мы рассмотрим всю процедуру, которую Алиса должна пройти, чтобы сгенерировать zk-SNARK для своих доказательств.
Этот вопрос может показаться слишком простым, поскольку он не включает в себя поток управления (например, if-then-else). Однако преобразовать функцию с потоком управления в арифметическое выражение несложно. Для примера рассмотрим следующий вопрос (или «функцию» в языке программирования):
f(x, z):
if(z==1):
возвращает x*x*x+x*x+5
еще:
return x*x+5
Эту задачу легко переписать в следующее арифметическое выражение (предполагая, что z принадлежит (0,1)), которое не намного сложнее уравнения (1).
f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)
В этой статье мы продолжим использовать уравнение (1) в качестве основы для обсуждения.
Шаг 1: Схема арифметического вентиля
Уравнение (1) можно разбить на следующие основные арифметические операции:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-122a4a0e88-dd1a6f-cd5cc0.webp)
Это соответствует следующей схеме арифметического вентиля:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-9001e3d244-dd1a6f-cd5cc0.webp)
Мы также называем уравнение (2) набором из 4 «ограничений первого порядка», каждое из которых описывает соотношение арифметического вентиля в цепи. В общем случае набор из n ограничений первого порядка может быть обобщен в виде квадратичной арифметической процедуры (QAP), которая будет объяснена далее.
Шаг 2: Матрица
Во-первых, давайте определим вектор-свидетель следующим образом:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-1157f4c74a-dd1a6f-cd5cc0.webp)
где y, s1, s2, s3 совпадают с теми, что определены в уравнении (2).
В общем случае для задачи с m входами и n арифметическими вентилями (т.е. n-1 промежуточными шагами и конечным выходом) этот вектор-свидетель будет (m+n+1) размерным. В практической задаче число n может быть очень большим. Например, для хеш-функции n обычно равно нескольким тысячам.
Далее построим три n*(m+n+*1) матрицы A,B,C, чтобы можно было переписать уравнение (2) следующим образом:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a9e2164b2f-dd1a6f-cd5cc0.webp)
Уравнение (3) является просто еще одним представлением уравнения (2): каждой группе (ai, bi, ci) соответствует вентиль в цепи. Нам нужно только однозначно развернуть формулу матрицы, чтобы увидеть это:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-630e507588-dd1a6f-cd5cc0.webp)
Таким образом, LHS=RHS в точности совпадает с уравнением (2), и каждая строка матричного уравнения соответствует ограничению первого порядка (т.е. арифметическому вентилю в схеме).
Мы пропустили этапы сборки (A, B, C), которые относительно просты. Нам нужно только преобразовать их в матричный вид в соответствии с соответствующими ограничениями первого уровня, чтобы определить содержимое каждой строки (A, B, C), Т.Е. (AI, BI, CI). Возьмем в качестве примера первую строку: легко увидеть, что для того, чтобы ограничение первого порядка x было умножено на x, равное s1, нам нужно умножить [0,1,0,0,0,0], [0,1,0,0,0] и [0,0,0,0,1,0,0] на вектор s.
Таким образом, нам удалось преобразовать арифметическую вентильную схему в матричную формулу, т.е. уравнение (3). В то же время мы также изменили объект, который необходимо доказать для освоения, с вектора-свидетеля s.
Шаг 3: Полиномы
Теперь построим n*(*n+m+*1) матрицу PA, определяющую множество полиномов о z:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-94169f2b1d-dd1a6f-cd5cc0.webp)
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-2c37ea96a6-dd1a6f-cd5cc0.webp)
Это четыре набора линейных уравнений для шести переменных, которые могут быть решены традиционными методами. Однако более эффективным способом решения ПА в этом случае является интерполяция Лагранжа, которая использует специфику задачи. Здесь мы пропускаем процесс решения для PA, который немного утомителен, но прост.
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-fcac15b335-dd1a6f-cd5cc0.webp)
При этом:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a7d3309d02-dd1a6f-cd5cc0.webp)
Шаг 4: Точки кривой эллипса
Перепишите уравнение (4) следующим образом:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-f974fc7c93-dd1a6f-cd5cc0.webp)
где i(z)=1 - это просто тривиальный многочлен нулевого порядка для z, который используется для унификации уравнения - все члены квадратичны. Необходимость в этом скоро станет очевидной. Заметим, что это уравнение содержит только сложение и умножение полинома z.
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-8fdea08104-dd1a6f-cd5cc0.webp)
Далее мы объясним фактические шаги более подробно.
Шифрование эллиптических кривых
Общая теория эллиптических кривых выходит далеко за рамки данной статьи. Для целей данной статьи эллиптические кривые определяются как отображение из простой области Fp в функцию E, где E включает точки, удовлетворяющие y^2=x^3+ax+b (называемые точками эллиптической кривой, или сокращенно ECP).
Заметьте, что до сих пор мы говорили об обычной арифметике, теперь, когда мы преобразуем в простые поля, арифметические операции над числами выполняются модульным способом. Например, a+b=a+b(mod p), где p — порядок Fp.
С другой стороны, определение сложения двух точек эллиптической кривой показано на следующем рисунке:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-baf3cc3cbe-dd1a6f-cd5cc0.webp)
В частности, добавление двух ВТП, P и Q:
Найдите пересечение прямой PQ и кривой R, определяемой как -(P+Q)
Перевернитесь в «зеркальную» точку R’ на кривой для R.
Итак, определим сложение точек эллиптической кривой P+Q=R’:
Обратите внимание, что это правило также применимо к особым случаям, т.е. когда используется самоаддитив ВТП, где будет использоваться касательная точки.
Теперь предположим, что мы выбираем случайную точку G и сопоставляем с ней число 1. (Это «начальное сопоставление» звучит несколько произвольно.) Подробнее об этом позже). Тогда для того, чтобы любое n принадлежало Fp, определим:
E(N)=G+G+G+…+G=G
У него есть выражение действия. Действия, определяющие +G, являются «генераторами» и обозначаются как g. Тогда приведенное выше определение эквивалентно следующему:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-bb825d6ba2-dd1a6f-cd5cc0.webp)
Для тех, кто не знаком с эллиптическими кривыми, вы можете провести аналогию с обычной экспоненциальной функцией, где кардинальное g заменяет действительные числа. Арифметические операции ведут себя аналогично. Однако ключевое отличие заключается в том, что обратная функция g^n не является вычислительно осуществимой. То есть, нет никакой возможности вычислить версию эллиптической кривой! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c989bcd81c-dd1a6f-cd5cc0.webp)。 Это, конечно, основа криптографии на эллиптических кривых. Такое сопоставление известно как одностороннее шифрование.
Обратите внимание, что для данной эллиптической кривой, поскольку выбор G (и, следовательно, Generator g) является произвольным (за исключением точек на оси x), существует бесконечное количество способов ее отображения. Выбор (G или g) может быть аналогичен выбору мощности экспоненциальной функции (2^x, 10^x, e^x и т.д.) в рамках здравого смысла.
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-ce9f261ecc-dd1a6f-cd5cc0.webp)
Однако уравнение (5), которое хочет доказать Алиса, является квадратичным и, следовательно, недостаточно линейным. Для того, чтобы иметь дело с квадратичными членами, нам нужно определить умножение в криптографическом пространстве. Это называется парной функцией, или билинейным отображением, и будет объяснено далее.
Билинейное отображение
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-146a4881e5-dd1a6f-cd5cc0)
Общая ссылочная строка
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-17e9a49fa0-dd1a6f-cd5cc0.webp)
Весь процесс называется «ключом верификации», или сокращенно ВКонтакте. Здесь задействовано всего 7 точек эллиптической кривой (ECP), которые необходимо предоставить верификатору. Важно отметить, что независимо от того, сколько входов и ограничений первого уровня задействовано в задаче, ВКонтакте всегда состоит из 7 ECP.
Кроме того, стоит упомянуть, что «доверенная настройка» и процесс генерации PK и VK можно сделать один раз для конкретной задачи.
Доказательство и проверка
Теперь с помощью открытого ключа (PK) Алиса будет вычислять следующие точки эллиптической кривой (ECP):
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c7eacd57e6-dd1a6f-cd5cc0.webp)
Эти 9 точек эллиптической кривой являются ключом к кратким неинтерактивным доказательствам с нулевым разглашением (zk-SNARKs)!
Заметьте, что Алиса на самом деле просто выполняет некоторые линейные комбинаторные операции над точками эллиптической кривой в открытом ключе. Это особенно важно и будет проверено во время проверки.
Теперь, когда Алиса передала доказательство zk-SNARK, давайте наконец перейдем к процессу проверки, который состоит из трех этапов.
Прежде всего, важно убедиться, что первые 8 точек эллиптической кривой действительно являются линейной комбинацией этих точек в общей ссылочной строке.
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-4cf599e8c2-dd1a6f-cd5cc0.webp)
Если все три проверки верны, то уравнение (5) проверяется, поэтому мы считаем, что Алиса знает свидетеля.
Давайте объясним логику уравнения. Возьмем в качестве примера первое уравнение из первой части, которое справедливо из-за билинейной природы:
! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-0032ace846-dd1a6f-cd5cc0.webp)
Однако, поскольку Алиса не знает значения символа альфа, она не может вычислить это сложение явно. Единственный способ, которым она могла придумать пару, удовлетворяющую уравнению (EA, EA’), состоял в том, чтобы использовать один и тот же набор векторов s каждый, вычислить! [Сила доказательств с нулевым разглашением: математическое декодирование zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-933d054c72-dd1a6f-cd5cc0.webp).
Список литературы
«ЗК-СНАРКи: Под капотом» (Виталик Бутерин)
«Обзор доказательств с нулевым разглашением» (Томас Чен, Эбби Лу, Джерн Кунпиттайя и Алан Луо)
«Почему и как работает zk-SNARK: окончательное объяснение» (Максим Петкус)
Веб-сайт: Доказательства с нулевым разглашением
Википедия: Эллиптическая кривая
Википедия: Конечное поле
Википедия: Криптография на основе пар
