zk-SNARKs: краткие неинтерактивные аргументы

zk-SNARK (краткое неинтерактивное доказательство знания с нулевым разглашением) — это доказательство, которое: (1) обеспечивает нулевое разглашение, (2) является кратким (крошечное доказательство и быстрая проверка независимо от размера вычисления), (3) является неинтерактивным (одна строка доказательства).

Сигма-протоколы подходят для простых утверждений (знание дискретного логарифма). Для сложных вычислений — например, «я правильно выполнил эту функцию над закрытыми входными данными» — нужна универсальная система доказательств. SNARK доказывают произвольные вычисления за время проверки O(1).

Сначала вычисление представляют в виде арифметической схемы: ориентированного ациклического графа из вентилей сложения и умножения над конечным полем. Например, можно доказать знание x, для которого x^3 + x + 5 = 35, не раскрывая x=3. Схема содержит около 5 вентилей.

Арифметическую схему преобразуют в систему ограничений: (A*z)*(B*z) = C*z, где z — вектор значений всех проводов. Каждому вентилю умножения соответствует одно ограничение. Доказывающий должен найти z, удовлетворяющий всем ограничениям, не раскрывая закрытые провода.

Эту систему преобразуют в QAP: полиномы A(x), B(x), C(x), для которых A(x)*B(x)-C(x) делится на целевой полином t(x) тогда и только тогда, когда ограничения выполнены. Доказывающий показывает, что знает полиномиальное частное H(x), не раскрывая свидетельство.

Groth16 (2016) — самая эффективная универсальная система SNARK. После доверенной настройки (генерации CRS) доказывающий выдаёт доказательство из 3 элементов группы (около 192 байт для BLS12-381). Проверка: 3 операции спаривания. Размер доказательства постоянен независимо от размера схемы.

Groth16 требует доверенной настройки для каждой схемы: нужно сгенерировать токсичный секрет (случайный секрет), вычислить общую эталонную строку, а затем уничтожить токсичный секрет. Если он сохранится, злоумышленник сможет подделывать доказательства. Многосторонние церемонии (Powers of Tau) распределяют доверие.

PLONK (2019) использует универсальную доверенную настройку: одна церемония подходит для всех схем до заданного размера. Отдельная настройка для каждой схемы не нужна. Компромисс: доказательства немного больше, чем у Groth16. Используется в реализациях ZK-EVM (Polygon Hermez, zkSync Era).

STARK (масштабируемые прозрачные аргументы знания) не требуют доверенной настройки и используют хеш-функции (защищены от атак квантовых компьютеров). Компромисс: более крупные доказательства (десятки KB против 200 байт). Используются в StarkWare/StarkNet и языке Cairo. SNARK меньше; STARK устойчивы к квантовым атакам.

Groth16 использует билинейные спаривания: e: G1 × G2 → GT, где e(a*P, b*Q) = e(P,Q)^{ab}. Это позволяет проверять тождества полиномов в показателе степени, не раскрывая значения. Кривая BLS12-381 оптимизирована для эффективных спариваний Groth16.

Время генерации доказательства Groth16 для схемы из 10^6 вентилей: около 10 секунд на современном CPU. Проверка: около 1 мс. Эта асимметрия намеренна: доказывающий, выполнивший основную вычислительную работу, делает всё сложное; проверяющий (узел блокчейна) выполняет почти нулевой объём работы.

Каков главный недостаток Groth16 по сравнению с PLONK?

zk-SNARK доказывают произвольные вычисления с доказательствами постоянного размера. Конвейер: вычисление → арифметическая схема → система ограничений ранга 1 → QAP → доказательство SNARK. Groth16 наиболее эффективен (требует доверенной настройки для каждой схемы); PLONK использует универсальную настройку. Далее: применения ZKP в блокчейне.