Схемы агрегации доказательств: SNARKPack и aPlonk

Ссылка на оригинал статьи: https://www.entropy1729.com/proof-aggregation-schemes-snarkpack-and-aplonk/ Мой Discord: useless_dorozhkina#1394

Введение

zk-SNARKs — это мощные криптографические примитивы, позволяющие одной стороне, известной как доказывающий, доказать второй стороне, известной как проверяющий, что первая знает определенный секрет, не раскрывая ничего о данном секрете. Это применяется, например, в децентрализованных приватных вычислениях, когда мы можем делегировать дорогие вычисления серверу, которому не доверяем, не раскрывая значимой информации, и получить криптографическое доказательство, подтверждающее верность этих вычислений. Мы также можем использовать zk-SNARKs для решения проблем конфиденциальности и масштабируемости, от которых страдает большинство децентрализованных реестров. В случае с реестром каждая нода должна выполнить вычисление самостоятельно, чтобы проверить его достоверность. Это означает, что менее мощные устройства в реестре могут выступать в качестве слабых мест, что влияет на масштабируемость, особенно когда вычисления являются дорогостоящими. Однако вместо того, чтобы заставлять каждую ноду повторно выполнять каждое вычисление, мы могли бы дать им проверить короткое доказательство, которое показывает, что вычисление правильное, тогда мы сможем уменьшить нагрузку на всю систему.

Одной из главных проблем с zk-SNARKs является время генерации доказательства. Как правило, генерация доказательств включает в себя преобразование вычислений в некоторую NP-полную задачу, в которой мы можем доказать правильность вычисления, например, в выполнимость арифметической схемы или в систему квадратичных ограничений (система ограничений первого ранга, R1CS), включающих выполнение некоторых дорогостоящих вычислений, таких как мультискалярные умножения (MSM) и совмещение эллиптических кривых... Для снижения вычислительных затрат было принято несколько стратегий, таких как составление доказательств, пакетирование, рекурсия, попытка справиться с увеличенным числом доказательств меньшего размера и использование преимуществ схем полиномиальных обязательств.

В предыдущей статье, мы рассмотрели пошагово проверяемые вычисления (IVC) и схемы сворачивания, которые дают нам способы реализовать IVC на практике. Мы рассмотрели основы Nova и то, как работает схема сворачивания. Теперь мы обратим наше внимание на схемы агрегирования доказательств: SNARKPack и aPlonK. Они позволяют нам уменьшить общий размер доказательств и связанное с ними время проверки: для n доказательств размер и время проверки агрегированного доказательства будут O(n), что является значительным сокращением, особенно для большого количества доказательств. SNARKPack создан поверх Groth16 SNARK, в то время как aPlonk работает с системой доказательства Plonk. Оба являются одними из наиболее широко используемых SNARKs и используют trusted setups, которые являются результатом церемоний настройки, включающих многосторонние вычисления.

SNARKPack

В схеме Groth16 доказательство π состоит из трёх элементов групп эллиптических кривых, A, B, C. И A, и B принадлежат к группе G1, а C принадлежит к группе G2. Группы имеют одинаковый порядок (количество элементов), p, и входят в число групп кручения порядка p эллиптической кривой над полем расширения. Можно определить билинейное отображение (или операцию сопряжения), взяв по элементу от каждой группы и выведя элемент в третьей группе Gt : e: G1 × G2 → Gt так, что

где a, b — числа, а g, h — генераторы групп G1 and G2, соответственно (элемент группы g называют генератором, если любой элемент в группе может быть получен путем многократного его добавления). Верификация доказательства в Groth16 производится с помощью операции сопряжения

где D — это элемент G2, а Y — элемент Gt. Основная идея, лежащая в основе агрегирования n доказательств Groth16 заключается в том, что мы можем проверить их все одновременно, используя случайную линейную комбинацию (с точностью до некоторой очень небольшой ошибки). Таким образом, нам нужно выполнить только одну операцию сопряжения вместо n операций

где r — случайно выбранное число, а ∏ означает, что мы берем результаты всех возможных сопряжений.

Чтобы упростить задачу, определены следующие термины:

После проверки того, что это последнее уравнение выполняется, нам остается удостовериться в том, что для некоторых начальных зафиксированных векторов A = (A1, A2, ..., An), B = (B1, B2, ..., Bn) и C = (C1, C2, ..., Cn), ZAC, ZB соответствуют этим спецификациям. Это делается с помощью двух внутренних аргументов сопряжения:

1. Целевой результат внутреннего сопряжения (TIPP) показывает, что

2. Результат внутреннего сопряжения с многократным возведением в степень (MIPP) показывает, что

Чтобы иметь возможность реализовать эти продукты внутреннего сопряжения, нам нужны эффективные схемы обязательств с гомоморфными свойствами и свойствами сворачивания. Можно сказать, что обязательство аддитивно гомоморфно, если с двумя данными элементами, a, b, схема обязательств удовлетворяет cm(a+b) = cm(a) + cm(b). Для примера, обязательства Pedersen и Kate-Zaverucha-Goldberg обладают этим свойством. Чтобы добиться логарифмического размера доказательства, авторы SNARKPack используют ту же стратегию, что и bulletproofs, которая основывается на аргументе внутреннего продукта. Эти обязательства также и гомоморфны в ключевой области: с данными k1, k2 для любого сообщения m мы получаем, что cm(m, k1 + k2) = cm(m, k1) + cm(m, k2).

Данный протокол использует trusted setups с двух значимый церемоний установки: Filecoin и Zcash. В Groth16 структурированная ссылочная строка (SRS), которая является результатом церемонии, состоит из степеней случайного элемента τ, спрятанных внутри групп G1, G2. Учитывая генераторы g, h, SRS задаётся через

Это позволит нам зафиксировать многочлены и проверить утверждения по ним.

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

w1 = (g, g11, h12, ...) и v1 = (h, h11, h12, ...) SRS для церемонии 1.
w2 = (g, g21, h22, ...) и v2 = (h, h21, h22, ...) SRS для церемонии 2.

Существует две версии этих обязательств: одиночная группа и двойная группа. Первая принимает в качестве ключа обязательства ks = (v1, v2), а вторая — kd = (v1, w1, v2, w2).

Обязательство одиночной группы принимает вектор A и ключ ks и получает два элемента группы:

где

Двойное обязательство принимает векторы A и C, сформированные из элементов в G1 и G2 соответственно, а также kd и получает два элемента:

где

Двойное обязательство будет использоваться в сопряжении с TIPP, чтобы показать, что

в то время, как MIPP будет использоваться с одиночным обязательством, чтобы убедиться, что

Имеются две зависимости, которые необходимо проверить:

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

Для того, чтобы узнать точные детали для алгоритмов доказательства и верификации, мы предлагаем читателю ознакомиться с источником.

В показанных примерах схема агрегирования превосходит пакетную проверку как по размеру, так и по времени при чуть более чем 100 доказательствах.

aPlonk

aPlonk основывается на идеях SNARKPack, используя различные системы доказательств (Plonk) и вводя многополиномиальные обязательства для достижения сублинейного размера числа полиномов. Основная идея заключается в том, что мы можем верифицировать несколько доказательств, выполнив случайную линейную комбинацию обязательств и проверив её. Обозначения немного отличаются, поскольку авторы aPlonk используют аддитивную форму при работе с группами, в то время как авторы SNARKPack используют мультипликативную форму. Если cm(pk) — обязательство полинома pk (который является элементом эллиптической кривой, если мы используем обязательства KZG), то мы можем проверить все обязательства, выполнив

и удостовериться, что β в точке z открывается (равняется)

где vk — значение в точке pk(z). Если бы мы использовали мультипликативную форму, предыдущее уравнение имело бы следующий вид

Чтобы добиться сублинейного размера, доказывающий должен зафиксировать обязательства полиномов следующим образом

Поскольку мы вычисляем линейную комбинацию, используя степени r, естественно будет использовать полиномиальную схему обязательств такую, как KZG, или аргументы внутреннего продукта (IPA).

Система ограничений Plonk выражена как

и может быть расширена, чтобы включать условия более высокой степени или пользовательские логические операции. Для каждого qk мы можем определить одномерный полином qL(x), qR(x), qO(x), qM(x), qC(x) путем приравнивания каждого полинома к их соответствующим qki в n примитивный корнях единства ωi. Мы называем ωi примитивным n-ым корнем единства, если

если k < n. Кроме того, доказывающий должен показать, что отношения между индексами ai, bi, ci связаны перестановками; эти перестановки также выражаются в терминах многочленов. Это дает в общей сложности 8 полиномов, которые нужно зафиксировать.

Одним из ключевых строительных блоков является схема многополиномиальных обязательств. Она включает в себя 5 эффективных алгоритмов,
настройка, обязательство — полином, обязательство — вычисление, открыть, проверить; главное отличие заключается в добавлении алгоритма обязательство — вычисление. Многополиномиальные обязательства основаны на двух схемах полиномиальных обязательств: KZG и IPA.

Одна важная оптимизация заключается в том, что все многочлены вычисляются при одном и том же случайном вызове r, заданном эвристикой Фиата-Шамира. Для этого r должен быть получен из частичной расшифровки всех доказательств, требующей, чтобы доказательства каждого утверждения выполнялись согласованно. Даже если это предотвращает построение вычислений, поддающихся пошаговой проверке (IVC), поскольку в этом случае доказательства генерируются одно за другим, конструкция хорошо работает для свёркти верификации.

Заключение

Схемы агрегирования доказательств являются альтернативой для уменьшения размера и времени проверки многих zk-SNARKs. Ключевым фактом является то, что можно получить доказательства размеров и времени проверки порядка O(log(n)) для n доказательств, что превосходит методы пакетной обработки чуть более чем для 100 доказательств и имеет существенную разницу, когда мы складываем вместе более 1000 доказательств. Основными строительными блоками для достижения этих свойств являются гомоморфные полиномиальные обязательства (такие как KZG), два trusted setups и тот факт, что мы можем проверить многие доказательства, взяв случайную линейную комбинацию, используя в качестве коэффициентов степени некоторого числа r.