Введение

В нашем предыдущем посте мы представили концепцию SNARK и необходимые основные свойства. Имея в виду основную цель этой серии постов, а именно: как построить zk-SNARK для любых вычислений, мы представляем в этом посте создание SNARK для доказательства знания полинома. Мы будем делать это шаг за шагом, отходя от одной конструкции, которая не будет отвечать всем требованиям, и заканчивая протоколом, который будет «полным» SNARK с нулевым разглашением.

ZK-SNARK для многочленов

Мы будем строить zk-SNARK шаг за шагом, начиная с более простой конструкции, которая не является SNARK, а затем улучшая ее с помощью новых методов, пока не достигнем наших целей.

Первый шаг: лемма Шварца — Циппеля

Мы хотим создать протокол, позволяющий доказывающему P убедить проверяющего V в знании определенного многочлена степени n с коэффициентами в конечном поле F. Другими словами, P хочет убедить V, что он знает многочлен вида

Предположим, что a_1, a_2,..., a_n ∈ F являются n корнями этого многочлена, поэтому p(x) можно записать в виде

Предположим, что V знает d < n корней многочлена p(x).

Тогда мы можем переформулировать нашу задачу: теперь P хочет доказать V, что он знает полином h(x) такой, что

Полином t(x) будем называть целевым полиномом. Заметим, что он имеет вид

Первая версия нашего zk-SNARK основана на лемме Шварца — Циппеля: пусть F — поле и f: F^m → F — многочлен степени n от многих переменных. Тогда для любого конечного множества S ⊆ F:

Лемма показывает, что если мы возьмем u ∈ Sm случайным образом, вероятность того, что u будет набором корней для f, не превосходит n / |S|. Заметьте, что эта вероятность мала, если мы считаем S конечным полем F. Размер поля был бы очень большим по сравнению с n.

Это может показаться противоречивым, но эта лемма позволяет нам доказать знание многочлена f. Нам не нужно доказывать, что мы знаем все коэффициенты p, а только то, что мы знаем, как вычислить пару (s, f(s)) для любого s ∈ Fm. Лемма Шварца — Циппеля обеспечивает эффективность, требуемую в нашем zk-SNARK.

Первый протокол

Напомним, что P знает многочлен p(x), а V знает d < n корней p(x) или, что то же самое, V знает целевой многочлен t(x). P также знает t(x).

Наш первый подход заключается в следующем:

1. V принимает случайное значение s и вычисляет t = t(s). V посылает s в P.
2. P вычисляет полином

4. V проверяет, выполняется ли равенство p = t · h.

Этот протокол верен, поскольку, если P знает многочлен p(x), он может вычислить h(x) и, следовательно, P может также вычислить значения h и p, такие что p = h · t. С другой стороны, этот протокол также эффективен благодаря лемме Шварца — Циппеля.

Тем не менее, этот протокол ненадежен, так как доказывающая сторона может вычислить t = t(s) с помощью целевого полинома, даже если P не знает p(x). Он может взять случайное h, вычислить p = h · t и послать пару (h, p) V, который примет эту пару как верную.

Мы видим, что критическая точка, позволяющая P обмануть V, состоит в том, что P знает точку оценки s. Этот трюк был бы невозможен, если бы P мог оценить p, не зная точки оценки s. Это приводит нас ко второму шагу: гомоморфному запутыванию или гомоморфному сокрытию.

Второй шаг: гомоморфная обфускация

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

Мы сделаем это, полагаясь на сложность задачи дискретного логарифмирования. Для классического компьютера задача дискретного логарифмирования вычислительно невыполнима: в циклической группе G порядка p, порожденной элементом g, определение элемента a такого, что = ga (mod p) для известного .

Таким образом, предполагая сложность полинома дискретного логарифма, мы можем запутать значение a, вычислив = ga (mod p). Получатель сам по себе не может узнать значение a. Интересным моментом этой техники является то, что возведение в степень имеет некоторые гомоморфные свойства:

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

Если мы хотим вычислить многочлен

в точке x = s, не сообщая оценщику точную точку, нам нужно запутать весь многочлен:

Нам также нужно вычислить степени от 1 до степени полинома всех запутанных значений для x = r, то есть:

Заметьте, что со всеми этими элементами мы теперь можем вычислить запутанную оценку многочлена p в точке x = r. Действительно:

Пример гомоморфного скрытия

Рассмотрим конечное поле F = ℤ127 и g = 3 генератор. Предположим, что P знает полином p(x) = 4x2 + 3x + 1 и что V хочет, чтобы P вычислил полином в точке x = 2, не сообщая P эту точку. Мы можем сделать это с помощью следующих шагов:

1. V вычисляет все степени x = 2 от 0 до степени многочлена, n = 2:

1.б. 32 (мод 127) = 9

1.в. 34 (мод 127) = 81

и отправляет пару (9, 81) в P.

2. P может вычислить оценку p(x) при x = 2, не зная значения x, действительно, используя информацию, полученную от V, он может вычислить:

Второй протокол

Теперь, когда мы знаем, как запутать точки, чтобы доказывающий мог вычислить полином в этой запутанной точке, мы улучшим первый протокол. Напомним, что P знает многочлен p(x), а V знает d < n корней p(x) или, что то же самое, V знает целевой многочлен t(x). P также знает t(x).

Наш второй протокол выглядит следующим образом:

1. V принимает случайное значение s и вычисляет t = t(s).
2. V вычисляет и отправляет P следующие мощности:

4. Используя значения , P вычисляет g^p = g^{p(s)} и g^h = g*{h(s)}, используя инструкции предыдущего примера.

5. P отправляет g^p и g^h V.

6. V проверяет, выполняется ли следующее тождество: g^p = (g^h)^t

Обратите внимание, что ошибка, обнаруженная в первом протоколе, была исправлена, но этот второй протокол еще не является надежным. Действительно, P все еще может использовать значения zp и zh так, что z_p = (z_h)^t, и отправлять их в V, как если бы они были g^p и g^h. P мог бы сделать это, взяв случайное r, вычислив z_h = g^r и установив z_p = (g^t)^r. Значение z_p можно вычислить, используя запутанные мощности, отправленные V.

Чтобы избежать этой ситуации, нам нужно убедиться, что g^p и g^h вычисляются с использованием только запутанных степеней, отправленных V.

Третий шаг: предположение о знании экспоненты

Существует одно общее предположение при определении SNARK: давайте рассмотрим простое число q такое, что 2q + 1 также является простым числом. Рассмотрим ga генератор ℤ_{2q + 1}. Имея q, g и g' = g^, мы хотим найти пару (x, y) такую, что x ≠ g, y ≠ g' и y = x^. Предположение о знании экспоненты (KEA) гласит, что единственный способ найти пару (x, y) — это взять значение c ∈ ℤ_q, сначала вычислив x = g^c, а затем взяв y = (g')^ в.

KEA означает, что если кто-то хочет получить пару (x, y), единственный способ сделать это — знать показатель степени c, такой что x = g^c. Другими словами, мы можем получить пару (x, y) со свойством KEA, только используя степени g.

Используя KEA, приведенный ниже протокол гарантирует, что P возвращает определенную степень g, генератор мультипликативной подгруппы, доставленный V:

1. V принимает случайное значение и вычисляет g' = g^ (mod 2q + 1).
2. V посылает пару (g, g') P и запрашивает пару (b, b') такую, что (b, b') = (g, g').
3. P принимает значение c и вычисляет b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1) и отправляет пару (b, b') в V.
4. V проверяет, является ли b' = b^ (mod 2q + 1).

P использовал одну и ту же мощность c как для g, так и для g', и он мог использовать только значения, предоставленные V.

Третий протокол

Мы готовы построить надлежащий протокол, который гарантирует, что доказывающий P будет выводить мощности значения s в запутанной области.

1. V принимает случайное значение s и вычисляет t = t(s).
2. V принимает случайное значение и вычисляет t( · s).
3. V вычисляет следующую серию запутанных значений и отправляет их P.
4. V вычисляет следующую серию запутанных значений

5. P вычисляет полином h(x).

6. Используя , P вычисляет p(s) и h(s) вместе с g^p = g^{p(s)} и g^h = g^{h(s)}.

7. Используя , P вычисляет p(s) и h(s) вместе с g^{p'} = g^{p( · s)}.

8. P отправляет g^p, g^h и g^{p'} в V.

9. V проверяет, что P произвел вычисления запутанных значений, используя только ту информацию, которую он ему отправил. Для этого V проверяет, является ли g^p = g^{p'}.

10. V проверяет, выполняется ли следующее тождество: g^p = (g^h)^{t(s)}.

Этот протокол теперь удовлетворяет свойствам, требуемым SNARK: он корректен, надежен и эффективен. Следующие разделы будут посвящены неинтерактивности и нулевому разглашению.

Примечание: шаги 6 и 7 в приведенном выше протоколе выполняются в соответствии с примером гомоморфного скрытия.

с нулевым разглашением

В протоколе, который мы представили до сих пор, коэффициенты ci многочлена, известные P, очень специфичны, и V мог бы попытаться узнать некоторую информацию о них, используя gp, gh и gp', поступающие от P. Следовательно, чтобы убедиться, что P что V ничего не узнает, P нужно скрыть эти значения.

Стратегия скрытия значений, отправленных P, следует шагам, использованным ранее: P берет случайный и использует его, чтобы скрыть значения, отправленные в сообщении с V. Точнее, вместо отправки g ^ p, g ^ h и g ^{p'}, P вычисляет и отправляет (g^p)^, (g^h)^ и (g^{p'})^. Затем V выполняет проверку значений, скрытых под .

Процедура проверки, которую должен выполнить V, все еще действительна с этим сокрытием:

Таким образом, чтобы сделать третий протокол нулевым разглашением, шаг 8 заменяется, чтобы P мог отправлять запутанные значения.

Не интерактивность

Различные протоколы, которые мы представили, требуют взаимодействия между доказывающим и верификатором, потому что правильность протоколов зависит от секретных значений s и , выбранных верификатором.

Если мы хотим повторить любой из вышеперечисленных протоколов с другим верификатором V', V' нужно будет выбрать новые значения s' и '. Использование значений, сгенерированных V, может позволить P обмануть, если он вступит в сговор с V, а V раскроет P значения s и .

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

Мы введем пары для решения этой задачи. Напомним, что спаривание обладает следующим свойством:

Это свойство включает проверку на равенство продуктов в запутанном домене.

Итак, чтобы сделать наши протоколы неинтерактивными, первым шагом будет взять секретные случайные значения s и и запутать их: g^, и .

Как только мы вычислим эти степени, мы сможем избавиться от секретных значений s и и транслировать их запутанные значения, известные как Common Reference String (CRS). Значения CRS обычно хранятся как:

1. Ключ оценки: (, ).
2. Ключ подтверждения: (g^, g^{t(s)}).

Окончательный протокол: zk-SNARK для знания многочлена

Теперь мы определим zk-SNARK для доказательства знаний о многочлене p(x) степени n при заданном целевом многочлене t(x).

Установка параметра

1. Каждая сторона случайным образом берет два секретных значения s и .
2. Каждая сторона вычисляет g, и .
3. Значения s и уничтожаются.
4. Один передает ключ оценки ( и ).
5. Один передает ключ проверки g^, g^{t(s)}.

1. Предполагая, что P знает p(x), P вычисляет полином h(x).
2. P оценивает p(x) и h(x) и вычисляет gp(s) и gh(s), используя значения, содержащиеся в ключе оценки.
3. P вычисляет значение g^{p( · s)}, используя ключ оценки.
4. P принимает случайное значение .
5. P транслирует доказательство π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

Предполагая, что V имеет доступ к π = (g^{ · p}, g^{ · h}, g^{ · p'}), он проверяет,

Нам удалось установить протокол, удовлетворяющий всем свойствам, требуемым в определении zk-SNARK: краткости (поскольку доказательство просто проверяет полином в точке), нулевому разглашению и неинтерактивности (поскольку он использует CRS). ).

Генерация CRS

Zk-SNARK можно сделать неинтерактивными, используя набор скрытых значений, известный как Common Reference String (CRS). Эти скрытые значения, которые в нашем случае имеют форму и , происходят из секретных значений s и , которые должны быть уничтожены после получения скрытых значений. Обратите внимание, что создание CRS имеет решающее значение, поскольку, если кто-то делегирует его создание третьему участнику, каждый должен быть уверен, что участник уничтожит значения s и . Третья сторона представляет собой единую точку отказа.

Если мы хотим избежать единой точки отказа, нам нужен распределенный способ генерации CRS, в котором достаточно одного честного участника, чтобы гарантировать невозможность восстановления значений s и .

Давайте используем CRS для SNARK, который мы создали в нашем предыдущем примере. Напомним, что используя s и в качестве секретов, нам нужно вычислить скрытые значения и степени g^, и .

В нашем новом протоколе мы заменим значения s и , сгенерированные одной третьей стороной, на значения s_{ABC} и _{ABC}, сгенерированные тремя пользователями A, B и C. Распространение механизма на n пользователей не представляет сложности. .

Протокол следующий:

1. Пользователь A генерирует пару (sA, A), вычисляет и передает:

3. Б вещает:

4. C берет случайную пару (sC, C), вычисляет и передает:

Этот протокол генерирует скрытые значения для s_{ABC} = s_A · s_B · s_C и _{ABC} = _A · _B · _C, при этом ни один участник не знает эту пару значений.

Тем не менее, нам нужен протокол, который позволит участникам проверить правильность вычисления этих скрытых значений. Нам нужно убедиться, что значения, сгенерированные каждым пользователем, удовлетворяют требованиям, то есть набор значений является степенью gs для s-значения каждого пользователя, и что набор был вычислен правильно. Для этого мы проверяем, что каждый (g^s)^i фактически является i-й степенью gs. Это можно сделать, проверив выполнение следующих равенств. Эта проверка выполняется каждым участником для всех значений sU и U, связанных с каждым участником U:

Это не единственная необходимая проверка. Нам также нужно проверить, что каждый участник использует правильные значения от предыдущего участника. Для этого каждый участник будет использовать скрытые публичные параметры одного пользователя в сочетании с выводами другого участника. Например, C может проверить промежуточные значения CRS, сгенерированные B, используя информацию CRS от A, проверив следующее:

Заключение

До сих пор мы научились создавать SNARK с нуля и со всеми подробностями, чтобы доказать знание полинома. В нашем следующем посте, последнем, мы расширим приведенную выше конструкцию на любые вычисления. Для этого мы введем два ключевых понятия: квадратичные арифметические программы, QAP, и системы ограничений ранга 1, R1CS, хотя последняя не будет представлена ​​конкретно (она появится как подсознательное сообщение).

Рекомендации

Хорди Эррера Хоанкомарти, Кристина Перес Сола, Cryptografia avançada. Конспект лекций. Открытый университет Каталонии, 2022 г.