Сила доказательств с нулевым знанием: Глубокое погружение в zk-SNARKs

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

Составлено: DODO Research

Автор: 0xAlpha Сооснователь @DeriProtocol

Введение

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):
returnxxx+xx+5
else:
return xx+5

Переписать эту задачу в следующее арифметическое выражение (при условии, что z принадлежит (0,1)) не сложнее, чем уравнение (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

В этой статье мы продолжим использовать уравнение (1) в качестве основы для нашего обсуждения.

Шаг 1: Арифметическая схема

Уравнение (1) можно разбить на следующие основные арифметические действия:

Это соответствует следующей арифметической схеме:

Мы также называем уравнение (2) набором из 4 "первичных ограничений", каждое из которых описывает взаимосвязь арифметических ворот в схеме. В общем случае, набор из n первичных ограничений можно обобщить в виде квадратичной арифметической программы (QAP), о которой мы расскажем далее.

Шаг 2: Матрица

Во-первых, давайте определим вектор "свидетеля" следующим образом:

где y, s1, s2 и s3 определены как в уравнении (2).
Как правило, для задачи с m входами и n арифметическими воротами (т.е. n-1 промежуточных шагов и конечный выход), этот вектор свидетелей будет иметь размерность (m+n+1). В реальных условиях число n может быть очень большим. Например, для хэш-функций n обычно исчисляется тысячами.

Далее давайте построим три n(m+n+1) матрицы A,B,C так, чтобы мы могли переписать уравнение (2) следующим образом:

Уравнение (3) - это просто другое представление уравнения (2): каждый набор (ai, bi, ci) соответствует воротам в схеме. Мы можем убедиться в этом, явно расширив матричное уравнение:

Таким образом, LHS=RHS в точности совпадает с уравнением (2), а каждая строка матричного уравнения соответствует первичному ограничению (т.е. арифметическим воротам в схеме).

Мы пропустили шаги построения (A, B, C), которые на самом деле относительно просты. Нам нужно только преобразовать их в матрицу согласно соответствующим первичным ограничениям, чтобы определить содержание каждой строки (A, B, C), то есть (ai, bi, ci). Возьмем в качестве примера первый ряд: мы можем легко увидеть, что для того, чтобы первое первичное ограничение x, умноженное на x, было равно s1, нам нужно умножить [0,1,0,0,0], [0, 1,0,0,0] и [0,0,0,1,0,0] на вектор s.

Таким образом, мы успешно преобразовали арифметическую схему в матричное уравнение, а именно в уравнение (3). В то же время мы также изменили объект, который необходимо доказать, что он освоен, на вектор свидетеля s.

Шаг 3: Полиномы

Теперь давайте построим n(n+m+*1) матрицу PA, которая определяет набор полиномов относительно z:

Убедитесь, что функцияпринимает следующие значения в точке {1, 2, 3, 4}, удовлетворяя условиям:

Тогда мы можем переписать A как:

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

Аналогично, мы строим PB и PC отдельно для B и C. Затем мы можем переписать матричное уравнениеследующим образом:

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

Шаг 3: Точка эллиптической кривой

Перепишите уравнение (4) в виде:

где i(z)=1 - это тривиальный многочлен нулевой степени от z, используемый для унификации уравнений - все члены квадратичны. Необходимость этого станет понятна в ближайшее время. Обратите внимание, что это уравнение содержит только сложение и умножение многочленов в z.

Обратите внимание, что арифметические операции, сложение (+) и умножение (X), также отображаются на соответствующие операции в конечном поле точек эллиптической кривой. Символы и используются для того, чтобы избежать путаницы и указать, что это переопределенные полевые операции.

Далее мы расскажем о практических шагах более подробно.

Криптография эллиптических кривых

Общая теория эллиптических кривых выходит далеко за рамки этой статьи. В настоящем документе эллиптическая кривая определяется как отображение простого поля Fp на функцию E, где E включает точки, такие что y^2=x^3+ax+b (называемые точками эллиптической кривой, или сокращенно ECP).

Обратите внимание, что хотя до сих пор мы обсуждали обычную арифметику, при переходе к простому полю арифметические операции над числами выполняются с помощью модульной арифметики. Например, a+b=a+b(mod p), где p - порядок Fp.

С другой стороны, сложение двух точек эллиптической кривой определяется, как показано ниже:

В частности, сложение P и Q двух ECP:

Найдите точку пересечения прямой PQ и кривой R и определите ее как -(P+Q).
Перевернитесь в "зеркальную" точку R' относительно R на кривой.
Поэтому мы определяем дополнение точек эллиптической кривой P+Q=R':

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

Теперь предположим, что мы случайным образом выбираем точку G и обозначаем ее числом 1. (Это "начальное отображение" звучит несколько условно. Мы обсудим это позже). И для любого n, принадлежащего Fp, мы определяем:

E(N)=G+G+G+.....+G=G, умноженное на n

Существует операционное выражение. Определите операцию +G как "генератор", обозначаемый как g. Тогда приведенное выше определение эквивалентно:

После определения сложения становится очевидной следующая линейная зависимость:

Поэтому любое линейное отношение (или ограничение) в Fp будет сохранено в зашифрованном пространстве B благодаря этому отображению. Например, уравнение l + m = n в Fp приведет к тому, что

Однако, поскольку уравнение (5), которое Алиса хочет доказать, имеет квадратичную форму, оно не является достаточно линейным. Чтобы работать с квадратичными членами, нам нужно определить умножение в зашифрованном пространстве. Это называется сопряжением, или билинейной картой, которую я объясню в следующем разделе.

Билинейная карта

Предположим, что G1, G2 и GT - это группы простого порядка g. Функция сопряжения, или билинейная карта, определяется следующим образом:

Общая справочная строка

Это целое называется "подтверждающий ключ" (PK). Обратите внимание, что представление векторов в E() следует понимать как векторы точек эллиптической кривой, где каждая точка отображается из соответствующего элемента вектора. Таким образом, эти 11 векторов фактически составляют 62 ( =42+63+63+63+63 ) точки эллиптическойкривой. Эти 62 ECP будут предоставлены Алисе, проверяющему. В общем случае, для задачи с m входами и n первичными ограничениями, PK будет содержать 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECP.

Одновременно будут выполняться следующие вычисления:

Весь этот процесс называется "ключ верификации" (VK). Здесь задействованы только 7 точек эллиптической кривой (ECP), которые необходимо предоставить верификатору. Следует отметить, что независимо от того, сколько входов и первичных ограничений задействовано в задаче, VK всегда состоит из 7 ECP.

Кроме того, стоит отметить, что "доверенную настройку" и процесс генерации PK и VK нужно выполнить только один раз для конкретной задачи.

Доказательство и проверка

Теперь, обладая открытым ключом (PK), Алиса вычислит следующие точки эллиптической кривой (ECP):

Эти 9 точек эллиптической кривой имеют решающее значение для краткого неинтерактивного аргумента знания с нулевым знанием (zk-SNARK)!

Обратите внимание, что Алиса, по сути, просто выполняет линейные комбинации на точках эллиптической кривой в открытом ключе. Это особенно важно и будет тщательно проверяться во время верификации.

Теперь Алиса представляет доказательство zk-SNARK, что, наконец, приводит нас к процессу проверки, который происходит в три этапа.

Во-первых, необходимо подтвердить, что первые 8 точек эллиптической кривой действительно являются линейными комбинациями точек в общей эталонной строке.

Отказ от ответственности：

1. Эта статья перепечатана с сайта[chaincatcher]. Все авторские права принадлежат оригинальному автору[0xAlpha Co-founder @ DeriProtocol]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Предупреждение об ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.