Охота на (zk-) SNARK
Ссылка на оригинал статьи: https://www.entropy1729.com/the-hunting-of-the-zk-snark/
Мой Дискорд: useless_dorozhkina#1394
Введение
Краткие не интерактивные аргументы знания (SNARK) — это мощные криптографические примитивы, которые находят свое применение в децентрализованных финансах, управлении и вычислениях. Существует множество различных SNARK таких, как Marlin (на котором основан Aleo), Plonk, STARK, Groth16 и т.д., построенных на различных инструментах и с различными производительностью, размером доказательств, временем проверки и т.д. Однако все они основываются на общих принципах и свойствах. Среди SNARK самыми важными для приватных приложений являются SNARK с нулевым разглашением (сокращенно zk-SNARK). Они позволяют доказывать, что мы знаем некие переменные, называемые свидетелем, w, такие, что выходное значение функции F, вычисленное в свидетеле и экземпляре (публичных переменных), x, равно F(x, w) = y, не раскрывая при этом ничего о w.
Компьютерные программы могут быть преобразованы в функции, которые принимают входные данные (некоторые из них мы, возможно, захотим скрыть), и правильное выполнение которых мы доказываем с помощью SNARK. Например, мы можем преобразовать программу в арифметическую схему, C, и, учитывая публичные входные и выходные данные, x, и засекреченные данные, w, мы можем доказать, что программа была выполнена корректно, продемонстрировав выполнимость схемы, C(x, w)=0. Поскольку выполнимость арифметических схем — это NP-полная задача, мы можем свести любую NP-задачу к арифметической схеме (однако, это не единственная альтернатива, и несколько конструкций опираются на другие техники).
Перед тем, как перейти к деталям, позвольте объяснить главные свойства SNARK и дать точные определения каждого слова в его названии. В zk-SNARK участвуют две стороны, доказывающий и проверяющий, где первый пытается убедить последнего в данном утверждении, например, в том, что доказывающий знает такой w, что C(x, w)=0. SNARK должен удовлетворять свойствам:
- Завершенности: если доказывающий знает w, он всегда должен быть способен убедить честного проверяющего в достоверности утверждения.
- Надежности: если утверждение ложно, то ни один обманывающий доказывающий не сможет убедить проверяющего принять его, за исключением случаев с очень низкой вероятностью.
- Нулевого разглашения: доказательство не раскрывает никакой информации о свидетеле.
- Краткость: доказательства должны быть короткими и быстро проверяемыми. Это позволило бы нам делегировать дорогостоящие вычисления ненадежным сторонам и проверять их достоверность без необходимости запускать программу самостоятельно.
- Не интерактивность: ни для генерации, ни для проверки доказательства не требуется взаимодействия между доказывающим и проверяющим. Мы увидим, что изначально конструкция полагалась на интерактивные доказательства, но мы сможем превратить их в не интерактивные, используя трансформацию Фиата-Шамира.
- Аргумент знания: мы с высокой вероятностью можем доказать, что мы знаем свидетеля.
Настройка
SNARK требуют доверенную настройку. Среди её видов мы можем выделить:
— Единую справочную строку, или прозрачные настройки (URS).
— Структурированную ссылочную строку, или частную настройку (SRS).
В случае SRS мы можем наткнуться на два случая:
— Универсальная (например, MARLIN)
На практике частная настройка выполняется как многостороннее вычисление; конструкция будет безопасной до тех пор, пока существует одна честная сторона. Проблема с конкретными SRS заключается в том, что строка зависит от программы, и для каждой из них необходимо выполнить новую настройку (это нежелательное свойство).
Вероятностные доказательства и возможности проверяющего
Краткость аргумента опирается на вероятностные доказательства. Чтобы это было возможно, мы сначала должны установить то, что соответствует "полномочиям", или возможностям проверяющего. Имеется:
— Интерактивность: проверяющему разрешается взаимодействовать с доказывающим, отправляя вызовы и получая ответы.
— Множество доказывающих: существует несколько доказывающих, но все они изолированы.
— Случайность: проверяющий может выбирать случайные элементы или запросы.
— Возможность отправления запросов в оракул: проверяющий может отправлять запросы на сообщения доказывающего.
Когда у проверяющего имеется доступ к более, чем одному из этих полномочий, мы получаем разные виды доказательств:
— Интерактивность + Случайность: Интерактивные доказательства (IP).
— Случайность + Оракул: Вероятностно проверяемые доказательства (PCP).
— Интерактивность + Случайность + Оракул: Интерактивные доказательства с оракулом (IOP).
Имеются и другие возможные варианты, например, MIOP, но мы сосредоточимся на предыдущих трёх. На данный момент IOP предоставляет наиболее эффективную конструкцию для SNARK: квазилинейное время проверки, линейная длина размера доказательств, линейное время доказывающего и эффективные реализации. PCP интересны с теоретической точки зрения, но на практике не эффективны (они не приводят к кратким доказательствам, за исключением линейных запросов). Наконец, IP предоставляют интересные строительные блоки в виде подпрограмм.
В IOP доказывающий и проверяющий обмениваются сообщениями. Доказывающий отправляет произвольные сообщения (в полиномиальном IOP доказывающий отправляет обязательства — см. следующий раздел — полиномам), и проверяющий отправляет случайные вызовы. После нескольких раундов проверяющий составляет запрос из нескольких переменных и решает, принять доказательство или же нет.
Схема обязательств
Производительность SNARK зависит от типа использованных обязательств; за последние годы было сделано много шагов по их улучшению.
Мы можем представлять обязательство как сейф. Мы делаем какой-либо выбор для ставки, кладем его в сейф и передаем другому. Когда результат объявлен, мы можем раскрыть нашу ставку, открыв сейф.
Обязательство должно удовлетворять двум свойствам:
— Связывающее: мы не можем произвести два верных открытия для одного и того же обязательства. Иными словами, если обязательство имеет некое значение a, должно быть невозможно найти такой b, что cm(a) = cm(b).
— Скрывающее: обязательство не раскрывает ничего о зафиксированных данных.
Один из способов зафиксировать сообщение — использовать устойчивую к коллизиям хеш-функцию. Если нам даны сообщение m и случайное значение r,
cm(m, r) = hash(m ∣ r)
Учитывая, что она устойчива к коллизиям, мы получаем свойство связывания.
Затем мы можем открыть обязательство и проверить:
Verify(m, r, cm) → принять или отклонить
Одним из преимуществ обязательств является то, что они склонны быть короткими. Например, если мы будем использовать SHA-256, длина доказательства будет равна 32 байтам.
Одна важная группа обязательств — это полиномиальные схемы. Ниже представлены несколько конструкций и математика, на которой они основываются:
— Базовые эллиптические кривые: bulletproofs
— Билинейные группы: полиномиальные обязательства Kate-Zaverucha-Goldberg (KZG) (спаривания, доверенная настройка), DORY (без доверительной настройки)
— Группы неопределенного порядка: DARK
Анатомия SNARK
SNARK может быть сконструирован путем выбора следующих двух элементов:
- Тип вероятностного доказательства: например, вероятностно проверяемое доказательство (PCP) или интерактивное доказательство с оракулом (IOP). Особый вид IOP — это полиномиальный IOP (PIOP).
- Схемы обязательств (криптография). Например, полиномиальные/функциональные обязательства, векторные обязательства и линейное кодирование.
Вероятностное доказательство определяет тип вычисления. Возможны варианты машинного вычисления (например, vmTinyRam) или схемы.
Криптографический элемент определяет стоимость генерации доказательства, будет ли оно постквантово безопасным и тип настройки (прозрачная или структурированная). Математические инструменты, с которыми нам придется работать для каждого из них:
— Линейное кодирование: Спаривание эллиптических кривых (ECP) + Решётки
— Векторное обязательство: устойчивый к коллизиям хеш-функции (CRH) + ECP
— Полиномиальные обязательства: CRH, ECP, PO группы, UO группы
- Линейное PCP + Линейное кодирование: Groth16, Groth-Maller 17
- PCP/IOP + Векторное обязательство: STARK
- Полиномиальные PCP/IOP + Полиномиальное обязательство: MARLIN, SONIC, Plonk, Spartan.
Bulletproofs используют несколько различных комбинаций вышеперечисленных элементов и основаны на криптографических проверках суммы.
Размер доказательства сильно зависит от типа конструкции. Например, для PIOP с полиномиальными обязательствами KZG доказательство занимает менее, чем 1 КиБ (два элемента эллиптических кривых), тогда как IOP с FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) — около 100 КиБ, более чем на два порядка больше! Это так, потому что FRI использует деревья Меркла; для проверки требуется путь аутентификации, требующий нескольких хешей.
Одна из проблем, с которой мы сталкиваемся в схемах, заключается в том, что проверяющий должен прочитать её, в результате чего время проверки линейно зависит от размера (что сделало бы доказательство не кратким). Чтобы избежать этого, мы можем предварительно обработать схему и достичь сублинейного времени проверки.
Теперь мы сосредоточимся на полиномиальных обязательствах KZG, которые являются основой Marlin и Plonk.
Схема полиномиальных обязательств KZG
Схема полиномиальных обязательств имеет следующие алгоритмы:
Чтобы зафиксировать полином, мы оценим его в заданной, но неизвестной точке α.
Настройка принимает максимальную степень полинома (которая зависит от количества вентилей арифметической схемы) и выводит общедоступные параметры: доказывающий ключ и проверяющий ключ. Чтобы иметь возможность вычислять многочлены, мы будем использовать эллиптическую кривую (нам нужно, чтобы она была удобной для спаривания, например, BLS 12-377), чтобы скрыть α и его мощности (α выбирается во время церемонии настройки и выбрасывается как токсичный мусор!). Чтобы сделать это, мы выбираем генератор из группы большого простого порядка d+1, g, и вычисляем
Это даст нам очень большую коллекцию точек эллиптической кривой (мы сохраним их в виде строки), которая будет работать как доказывающий ключ. В случае универсальной настройки количество элементов будет совпадать с максимальным размером схемы. Поскольку точки эллиптической кривой занимают порядка 100 B, если мы хотим иметь дело с 10^8 вентилей, нам потребуется более 1 Гбайт лишь для того, чтобы хранить их. Для заданной схемы, которая может быть намного меньше максимальной, MARLIN обрезает ключ, так что работать с ним намного проще и быстрее. Настройка также зависит от параметра безопасности λ, но в нашем анализе мы будем считать его постоянным.
Следовательно, мы имеем setup(λ, N) → pp(pk, vk).
Доказывающий генерирует полином
и фиксирует его, вычисляя в точке α. Мы не знаем α, только скалярные кратные элементы группы степеней α
Это проблема мульти-скалярного умножения (MSM). Мы видим, что полиномиальные обязательства соответствует одному групповому элементу эллиптической кривой.
Мы также могли бы использовать дерево Меркла, чтобы зафиксировать многочлен. Проблема дерева Меркла заключается в том, что размер дерева зависит от степени полинома. В случае KZG обязательство - это всего лишь один элемент группы, который не зависит от размера. Кроме того, когда мы хотим вычислить многочлен в доказательстве, нам нужно отправить все коэффициенты в открытом виде (который показывает многочлен), при этом проверяющему приходится выполнять линейную работу над размером многочлена. С другой стороны, мы увидим, что KZG в основном скрывает многочлен (если только запросов не много), и проверка не зависит от степени многочлена.
Кроме того, KZG допускает пакетные доказательства: если у нас есть несколько обязательств cm1, cm2, ..., cmk, мы можем сгенерировать лишь одно доказательство, показывающее, что все обязательства действительны.
Как только многочлен зафиксирован, проверяющий (в интерактивной схеме) может отправлять случайные точки rk доказывающему, и последний выдает многочлен, вычисленный в rk, P(rk). Чтобы сделать его неинтерактивным, мы используем преобразование Фиата-Шамира, где случайные вызовы будут генерироваться из криптографической хеш-функции.
Предположим, что доказывающий хочет убедить проверяющего в том, что P(u) = v. Он может превратить это равенство в полином, g(x) = P(x) − v, который имеет решение в x = u. Это означает, что g(x) делится на x − u, что мы можем записать как g(x) = P(x)−v = Q(x)(x−u), где Q — частный многочлен. Доказывающий может зафиксировать Q(x), выполнив то же, что и раньше
— еще один MSM. Доказательство π содержит этот элемент группы, который имеет постоянный размер! Доказательство продемонстрирует, что P(u) = v, и P — это действительно многочлен степени не больше, чем d, и фиксация P — это cm(P).
Проверяющий принимает доказательство, если (α−u)cm(Q) = cm(P) − vg. Но проблема в том, что мы не знаем α. Вот где спаривание приходит на помощь, и нам понадобятся только элементы h0 и h1, чтобы иметь возможность провести вычисление. Грубо говоря, спаривание эллиптических кривых — это функция
которая принимает два элемента, P из G1 and Q из G2, и производит элемент R из Gt. Все группы имеют одинаковый порядок r и соответствуют группам в удобных для спаривания эллиптических кривых. В случае MARLIN используется кривая BLS 12-377. Спаривание удовлетворяет:
где g and g2 — генераторы из групп G1 и G2 (и P = pg и Q = qg2).
Форма уравнения проверки с точки зрения спаривания:
Проверка проводится в Gt. Нам нужно лишь узнать αg2 из доверенной настройки.
Теперь, как мы можем быть уверены в том, что если мы оценили многочлены в одной точке и они совпадают, то очень вероятно, что аргумент верен? Ответ лежит в лемме Шварца-Зиппеля (мы сформулируем её для конечных полей): для полинома P степени d в конечном поле порядка p вероятность, что полином равен нулю в точке r, выбранной случайным образом, равна
Учитывая, что максимальный размер схемы (который определяет максимальный порядок полинома) равен примерно 2^26 ≈ 10^8, а размер поля больше, чем 2^256, эта вероятность равна примерно 2^(-230) ≈ 10^(-70). Если P1 и P2 совпадают в одной точке r, мы можем составить полином P(x) = P1(x )− P2(x) (поскольку сложение полиномов замкнуто) и P(r) = 0. Учитывая, насколько маловероятно случайное попадание в нуль, мы можем быть вполне уверены, что P(x) — нулевой полином.
Вывод
zk-SNARK начали привлекать внимание благодаря их использованию при разработке полностью частных приложений. Они предоставляют краткие доказательства того, что определенное вычисление было выполнено правильно, не раскрывая конфиденциальной информации. Существует множество возможных конструкций, основанных на вероятностных доказательствах и схеме обязательств. В зависимости от различных вариантов возможны более эффективные версии, которые определяют тип вычислений (машинные или схемные вычисления). Мы изучили схему обязательств KZG, которая демонстрирует идею, лежащую в основе таких систем, как MARLIN и Plonk, и вычисления, которые нам необходимо выполнить для генерации и проверки доказательств.