Преамбула
В предыдущей части мы в общих чертах узнали о математической и криптографической основе zk-SNARK. Теперь я продолжу углубляться в новые и довольно сложные концепции, чтобы вы могли глубже понять технологию, лежащую в основе zk-SNARK !
Арифметическая схема (Арифметическая схема)
Понятие арифметической схемы
Арифметическая схема — это ориентированный ациклический граф (DAG) или, проще говоря, ориентированный ациклический граф, состоящий из:
Узлы действуют как вентили сложения и умножения.
Края представляют собой проводники, установленные на конечном поле Fp. Провод соединяет выход одного порта со входом другого порта. Каждый порт имеет два входа и один выход.
Арифметическая схема завершается окончательным выводом. На рисунке выше показан пример арифметической схемы, где мы можем видеть, как данные обрабатываются и проходят через каждый элемент для получения конечного результата.
Арифметическая схема рассказывает нам о том, как zk-SNARK обрабатывает и подтверждает вычисления, не раскрывая никакой информации. Арифметическую схему можно описать как диаграмму, содержащую систематически расположенные арифметические операции.
Работа арифметических схем
Учитывая рисунок выше, арифметическая схема позволяет вычислить
Глядя на изображение выше, мы видим, что процесс начинается с первого шлюза ядра, который получает s1 и s2 в качестве входных данных и производит s4 в качестве выходных данных. Затем s4 и s3 подаются во второй вентиль ядра для получения окончательного выходного s5.
Для схемы m-порта и n-проводов мы сможем определить
свидетель s = (s1, s2, s3,…, sn)
назначить n проводам схемы так, чтобы вход и выход каждого вентиля удовлетворяли ограничению, определяемому работой вентиля.
Арифметическая схема m-gate, n-wire определяет отношения между свидетелями.
s = (s1, s2, …, sn)
такой, что для постоянного
затем
Вышеупомянутые ограничения относятся к набору ограничений m ранга-1, целью которых является моделирование взаимосвязи между входом и выходом вентиля умножителя в арифметической схеме.
Примером конкретного ограничения ранга 1 является уравнение
с1 . с2 – с3 = 0.
Это уравнение описывает вентиль умножителя в схеме, который принимает два входных сигнала, s1 и s2, а затем выдает выходной сигнал s3. Таким образом, чтобы уравнение выполнялось, произведение s1 и s2 должно равняться s3.
Набор из m ограничений ранга 1, подобных этому, можно обобщить в программу квадратичной арифметики.
QAP — это инструменты для преобразования и приведения арифметических схем к форме, которая упрощает проверку операций без повторной визуализации всей схемы.
Программа квадратичной арифметики
Ядро zk-SNARK лежит в программах квадратичной арифметики (QAP). QAP может представлять собой любую арифметическую схему, включая элементы сложения и умножения. На основе QAP проверяющий может предоставить доказательство того, что он знает входные значения, не раскрывая ничего об этом значении или внутреннем поведении программы.
Исследователь zk-SNARK Эран Тромер вывел процесс построения zk-SNARK на основе основных математических принципов следующим образом:
Описанные выше шаги можно разделить на две половины. В этой статье будет подробно объяснена «первая половина» процесса. «Первую половину» процесса можно рассматривать как этапы от «Вычисления» к «QAP», это та часть, где первоначальные вычисления преобразуются в математическую форму, которую можно использовать для создания zk-SNARK.
Я объясню наиболее простым для понимания способом:
Прежде чем мы сможем использовать zk-SNARK для какой-либо вычислительной задачи, мы должны преобразовать задачу в подходящую «форму». Эта форма называется QAP, или «программа квадратичной арифметики».
Как только мы преобразуем нашу проблему в QAP, мы приступим к ее решению с некоторыми конкретными входными данными. Найденное решение называется «свидетелем». Это похоже на то, когда мы решаем головоломку и знаем ответ.
Теперь, когда у нас есть ответ, нам нужно найти способ доказать, что мы знаем ответ, не раскрывая его. Этот процесс создает «нераскрытое доказательство», то есть позволяет нам доказать, что мы знаем ответ, не произнося его.
Наконец, кто-то другой может использовать отдельный процесс для проверки созданных нами доказательств и подтверждения того, что мы действительно знаем ответ, не зная, каков он на самом деле!
Например: У нас есть следующее уравнение:
x**3 + x + 5 == 37 (рекомендуемый ответ — 3)
Мы докажем, что знаем решение приведенного выше математического уравнения, не раскрывая его, написав простую компьютерную программу следующим образом:
Функция qevel вычислит значение уравнения x**3 + x + 5. Когда мы подставим число 3 в x, функция вернет 35, и это и есть желаемый результат.
Однако в этом случае мы увидим ограничения языков программирования. Этот язык поддерживает только основные арифметические операции (+, -, *, /) и степени с фиксированными показателями (x**7, а не x**y). Он не поддерживает деление с остатком (%) или сравнение (>, <, ≤, ≥), поскольку не существует эффективного способа выполнения по модулю или сравнения непосредственно в арифметике конечных циклических групп.
Решение здесь в том, что мы можем расширить этот язык для поддержки дополнительных операций, таких как деление с остатком и сравнение.
Например:
если х<5:у=7; иначе: у = 9
преобразуя их в арифметику:
у = 7 * (х < 5) + 9 * (х >= 5)
Вы можете обратиться к компилятору, который можно использовать для преобразования кода в удобную форму для zk-SNARK, реализованного vbuterin (только в образовательных целях; пока не готов создать QAP для zk-SNARK на практике).
Сглаживание
Первым шагом преобразования в эту форму QAP является шаг «сглаживания», проще говоря, это шаг преобразования программного кода, чтобы сделать его более простым, каждая строка выполняет только одно базовое действие.
В приведенном выше примере исходная компьютерная программа имеет сложное математическое выражение. Процесс «сглаживания» разбивает это выражение на небольшие части, каждая из которых выполняет лишь одно простое вычисление:
sym_1 = х * х
Умножьте x на себя, чтобы создать промежуточное значение, называемое sym_1.
y = sym_1 * x
Затем снова умножьте промежуточное значение sym_1 на x, чтобы получить y, следуя точному вычислению x^3.
sym_2 = у + х
Добавьте y, только что вычисленный с помощью x
~выход = sym_2 + 5
Наконец, добавьте 5 к sym_2, чтобы получить конечный результат, и поставьте ~ перед out, чтобы указать, что это конечный результат программы.
Очень легко понять! Этот процесс «сглаживания» помогает подготовить код для обработки zk-SNARK, поскольку zk-SNARK требует, чтобы программный код имел простую форму, которую можно было бы легко преобразовать в математические формы, с которыми он может работать. Хорошо.
Ворота в R1CS
Далее мы выполним серию вычислений, чтобы преобразовать их в немного более сложную форму, называемую (система ограничений ранга 1), сокращенно R1CS.
R1CS — это последовательность групп из трех векторов (a, b, c), а решением R1CS является вектор s, где s должен удовлетворять уравнению:
с. как . б-с. с = 0
При этом проверяется, является ли выходное значение правильным произведением двух входных значений. Если все эти условия выполнены, мы имеем точный вектор решения системы.
Мы можем увидеть изображение ниже, чтобы лучше понять R1CS:
Прежде всего, мы определим переменные, используемые в системе, я предоставлю шаг для сопоставления переменных следующим образом:
«~one» (первый индекс обозначает цифру 1)
«x» (входная переменная)
«~out» (выходная переменная)
«sym_1», «y», «sym_2» (промежуточные переменные)
Вектор «s» будет содержать значения для всех этих переменных в указанном порядке.
#Мы дадим (a, b, c) тройку для первых ворот (для умножения x * x):
Векторы a и b содержат значение [0, 1, 0, 0, 0, 0] . Число 1 на второй позиции в каждом из этих векторов означает, что значение переменной x будет использоваться в расчетах. В частности, это значение умножается само на себя, поскольку и a, и b помещают веса в позицию x.
Вектор c имеет значение [0, 0, 0, 1, 0, 0] с числом 1 в четвертой позиции, что указывает на то, что значение, вычисленное из a и b, будет сравниваться с переменной sym_1 в векторе s.
a = [0, 1, 0, 0, 0, 0]: указывает, что переменная «x» будет участвовать в расчете.
b = [0, 1, 0, 0, 0, 0]: снова указывает, что «x» будет умножаться само на себя.
c = [0, 0, 0, 1, 0, 0]: результат будет сохранен в переменной «sym_1»
Когда «x = 3», расчет будет «3 * 3 = 9», что удовлетворяет ограничению «sym_1 = x * x»
#Далее идут Вторые ворота (для умножения sym_1 * x):
Аналогично, a = [0, 0, 0, 1, 0, 0]: укажите «sym_1» (9, если «x = 3»)
b = [0, 1, 0, 0, 0, 0]: укажите «x» (3, если «x = 3»)
c = [0, 0, 0, 0, 1, 0]: результат будет сохранен в «y»
Расчет: «9 * 3 = 27», что удовлетворяет ограничению
#Далее идут Третьи ворота (для сложения x + y)
Похожий,
a = [0, 1, 0, 0, 1, 0]: укажите «x» и «y»
b = [1, 0, 0, 0, 0, 0]: используйте значение «1» (представляющее «~один»), чтобы сложение выполнялось правильно.
c = [0, 0, 0, 0, 0, 1]: результат сохраняется в «sym_2».
Расчет: «3 + 27 = 30», что удовлетворяет ограничению «sym_2 = x + y».
#Наконец Четвертые ворота (для сложения sym_2 + 5):
Похожий,
a = [5, 0, 0, 0, 0, 1]: используйте значение «5» из «~one» и значение «1» из «sym_2».
b = [1, 0, 0, 0, 0, 0] : снова «~один», чтобы сложение выполнялось правильно.
c = [0, 0, 1, 0, 0, 0]: результат сохраняется в «~out»
Расчет: «30 + (5*1) = 35», что удовлетворяет ограничению «~out = sym_2 + 5».
Три столбца A, B и C соответствуют векторам «a», «b» и «c». Число «35» внизу столбца C — окончательный результат («~выход»).
Сравните (s.a)*(s.b) и (s.c), они должны быть равны (их разница должна быть 0)
На этом этапе вектор «s» будет содержать следующие значения:
1: это значение фиктивной переменной ~one, которая всегда равна 1, обозначая константу 1.
3: Это значение входной переменной x.
35: Это желаемое значение, конечный результат программы (переменная ~out).
9: Результат x * x, сохраненный в sym_1.
27: Результат sym_1 * x, сохраненный в y.
30: Результат y + x, сохраненный в sym_2.
Наконец, полный R1CS собирается, как показано ниже:
R1CS в GAP
Следующий шаг — взять этот R1CS и преобразовать его в форму QAP, но вместо использования векторов и скалярных произведений, как в R1CS.
QAP использует «полиномы», поскольку они обладают особыми математическими свойствами, которые упрощают процесс тестирования.
Интерполяция Лагранжа — это метод рисования кривой (полинома), проходящей через ряд известных точек. Если у вас есть определенное количество точек и вам нужна кривая (полином), касающаяся всех этих точек, интерполяция Лагранжа поможет вам найти эту кривую.
Например: предположим, что нам нужен полином, который проходит через (1, 3), (2, 2) и (3, 4). Начнем с создания полинома, проходящего через (1, 3), (2, 0) и (3, 0).
Простой способ сделать это — взять произведение (x-2) и (x-3). Эта функция будет иметь изогнутую форму, поднимающуюся в точке x=1 и пересекающую горизонтальную ось в точках x=2 и x=3.
как показано ниже:
Теперь нам просто нужно «подкорректировать» его так, чтобы высота в точке x=1 была правильной:
В результате получается полином, и график будет выглядеть так, как показано ниже:
Затем делаем то же самое с оставшимися двумя точками и получаем еще два многочлена, складываем все три и получаем:
Исходный алгоритм требует времени O(n^3) для расчета, поскольку каждая из n точек требует O(n^2) для умножения полиномов. Однако, подумав умнее, мы можем сократить это время до O(n^2).
Применяя такие алгоритмы, как преобразование БПФ, мы можем еще быстрее сократить время вычислений, что важно в таких приложениях, как zk-SNARK с тысячами вентилей.
Мы применим интерполяцию Лагранжа для преобразования R1CS, взяв первое значение каждого вектора a, а затем используя эту интерполяцию для создания полинома для каждого вектора, чтобы при оценке полинома с определенным номером индекса мы получали первое значение соответствующий вектор.
Сделайте то же самое для первых значений векторов b и c, затем поочередно примените этот метод к следующим элементам каждого вектора.
Мы получим результат, как показано ниже:
Алгоритм использует ряд возрастающих коэффициентов для создания полинома:
Этот полином является частью параметров рассматриваемой версии QAP (программа квадратичной арифметики).
Следует отметить, что настройку этих параметров необходимо выполнить только один раз для каждой функции, проверенной с помощью zk-SNARK; После настройки их можно использовать повторно.
При оценке всех полиномов при x=1 процесс очень прост, потому что вы просто суммируете все коэффициенты (поскольку 1^k всегда равно 1 для всех значений k. Мы получим следующий результат:
Полином А при оценке при x = 1 дает все результаты 0, кроме второго результата, который равен 1.
Полином B при оценке при x = 1 также дает все результаты 0, кроме второго результата, который равен 1.
Полином C при оценке при x = 1 дает все результаты 0, кроме четвертого результата, который равен 1.
Мы видим, что здесь мы имеем точно такую же тройку векторов (a, b, c) для первого логического элемента, который мы создали выше.
Источник статьи: Team Tech/Research AlphaTrue.
Справочный источник:
Чен Т., Лу Х., Кунпиттая Т. и Луо А. (2022). Обзор zk-snarks. Препринт arXiv arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
https://eprint.iacr.org/2012/215.pd
