zk-SNARK: от теории к практике

Представьте: вы переводите криптовалюту, и весь мир может проверить, что транзакция корректна, но никто не узнает ни сумму, ни отправителя, ни получателя. Proof занимает 128 байт и проверяется за 5 миллисекунд. Это не фантастика - именно так работает Zcash с 2016 года, используя zk-SNARK на базе Groth16. За этими 128 байтами стоит цепочка превращений: программа становится арифметической схемой, схема - системой полиномов, полиномы - тремя точками на эллиптической кривой. И всё начинается с простого правила: a умножить на b равно c.

• **Zcash** - первая криптовалюта с полной приватностью транзакций через Groth16 zk-SNARK (с 2016 года), where proof в 128 байт скрывает отправителя, получателя и сумму
• **Tornado Cash** - mixer на Ethereum, использовавший Groth16 для доказательства принадлежности к множеству депозитов без раскрытия, какой именно депозит выводится
• **Filecoin** - сеть хранения данных, где Groth16 доказывает, что майнер действительно хранит заявленные данные (Proof of Storage) без передачи самих данных

Предварительные знания

• Zero-Knowledge Proofs: The Fundamentals
• Elliptic Curves (ECC)

R1CS: вычисление как система ограничений

В предыдущем уроке мы узнали, что zero-knowledge proof позволяет доказать знание секрета, не раскрывая его. Но как именно формализовать **произвольное вычисление** так, чтобы его можно было «доказать»? Первый шаг - перевести программу в **арифметическую схему** (arithmetic circuit), а затем в систему ограничений формата **R1CS** - Rank-1 Constraint System.

Идея R1CS проста: любое вычисление можно разложить на элементарные операции вида **a * b = c**, где `a`, `b`, `c` - линейные комбинации переменных. Это как разложить сложную программу на цепочку простейших инструкций, где каждая - одно умножение. Сложение «бесплатно» - оно просто складывает коэффициенты в линейной комбинации.

**Witness** (свидетель) - это вектор всех переменных, включая секретный вход `x` и все промежуточные значения. Prover знает witness целиком, а verifier видит только публичные входы/выходы (в нашем случае `out = 35`). Задача prover'а - доказать, что существует witness, удовлетворяющий **всем** constraints, не раскрывая сам witness.

**Размер R1CS масштабируется линейно** с количеством умножений в программе. Простой перевод ETH - около 5,000 constraints. Проверка ECDSA подписи - ~300,000 constraints. Полный EVM-эквивалентный zkRollup (zkSync, Polygon zkEVM) генерирует миллионы constraints на блок. Оптимизация количества constraints - ключевая задача для производительности zk-систем.

QAP: от матриц к полиномам

R1CS даёт нам набор constraints: `<Aᵢ, w> * <Bᵢ, w> = <Cᵢ, w>` для `i = 1..m`. Verifier мог бы проверить каждый constraint по отдельности, но это **линейно** по числу constraints. Для миллионов constraints это неприемлемо. **QAP** (Quadratic Arithmetic Program) - удачный трюк: превратить все constraints в **один полиномиальный тест**, который проверяется за O(1).

Ключевая идея: каждый столбец матриц A, B, C превращается в **полином** через интерполяцию Лагранжа. Если в R1CS было `m` constraints, мы выбираем `m` точек (например, `r₁, r₂, ..., rₘ`) и строим полином, проходящий через значения столбца в этих точках. Теперь все `m` constraints превращаются в **одно тождество между полиномами**.

Если `A(t) * B(t) - C(t)` равен нулю во всех точках `r₁..rₘ`, значит этот полином **делится** на `T(t) = (t - r₁)(t - r₂)...(t - rₘ)` - так называемый target polynomial. Это центральная проверка QAP: существует полином `H(t)` такой, что `A(t) * B(t) - C(t) = H(t) * T(t)`.

Здесь вступает **лемма Шварца-Циппеля**: два разных полинома степени `d` могут совпасть **не более чем в `d` точках**. Если поле содержит `p` элементов (для BN254 это ~2²⁵⁴), а степень полинома `d` - несколько тысяч, то вероятность случайного совпадения примерно `d/p ≈ 10⁻⁷⁰` - исчезающе мала. Достаточно проверить тождество **в одной случайной точке** `τ`, и если `A(τ) * B(τ) - C(τ) = H(τ) * T(τ)`, мы с подавляющей вероятностью уверены в корректности.

**Зачем полиномы?** Они дают нам «сжатие» проверки: вместо `m` отдельных constraint-проверок - **одна** проверка в случайной точке. Но verifier не должен знать witness, чтобы вычислить `A(τ)`, `B(τ)`, `C(τ)`! Решение: verifier выбирает `τ` **до** того, как prover создаёт proof. А чтобы prover не мог подогнать ответ под `τ`, точка скрывается за эллиптическими кривыми - это называется **homomorphic hiding**. Именно здесь QAP встречается с криптографией.

Groth16: самый компактный SNARK

QAP свёл задачу к проверке полиномиального тождества в одной точке `τ`. Но как проверить `A(τ) * B(τ) - C(τ) = H(τ) * T(τ)`, если verifier **не знает `τ`**, а prover **не должен его знать** (иначе сможет подделать proof)? Ответ - **Groth16**, самая широко используемая SNARK-система, опубликованная Йенсом Гротом в 2016 году.

Groth16 работает в три фазы: **Setup** генерирует «зашифрованные» степени секретной точки `τ` на эллиптических кривых. **Prove** вычисляет proof - три элемента групп эллиптических кривых. **Verify** проверяет proof через **bilinear pairing** - единственную операцию, связывающую две группы кривой.

Магия Groth16 - в **bilinear pairing** `e(P, Q)`. Это функция, которая берёт точку из группы G₁ и точку из группы G₂ и возвращает элемент целевой группы G_T. Её ключевое свойство: `e(a·G₁, b·G₂) = e(G₁, G₂)^(ab)`. Благодаря этому verifier может проверить **произведение зашифрованных значений**, не зная самих значений. Pairing «раскрывает» одно умножение - ровно то, что нужно для проверки QAP-тождества.

**Почему Groth16 до сих пор популярен?** Несмотря на необходимость trusted setup, proof в 128 байт и верификация за 5 мс делают его идеальным для on-chain проверки, где каждый байт стоит gas. PLONK и STARKs генерируют proofs в сотни байт или килобайты. Для L1-верификации в смарт-контракте Groth16 остаётся золотым стандартом по соотношению размер/стоимость.

Trusted Setup: церемония доверия

Groth16 требует секретную точку `τ` (toxic waste) для генерации proving и verification keys. Если **кто-то** узнает `τ`, он сможет создавать **поддельные proofs** - доказывать ложные утверждения. Как сгенерировать `τ` так, чтобы **никто** его не знал? Ответ - **MPC ceremony** (Multi-Party Computation), где множество участников совместно создают параметры.

В истории было несколько знаковых церемоний. **Zcash Sprout** (2016) - первый trusted setup в production. Всего **6 участников**, каждый на изолированном компьютере. Один из них (Питер Ван Валькенбург) физически уничтожил свой компьютер. **Zcash Sapling** (2018) - улучшенная церемония с **90+ участниками**. Процесс стал более открытым: любой мог участвовать, подключаясь через бинарник.

Самая масштабная - **Perpetual Powers of Tau** и церемония **Hermez/Polygon**: тысячи участников, непрерывный процесс. А Ethereum для KZG commitments в EIP-4844 провёл церемонию с **140,000+ участниками** из 177 стран - участники использовали лавовые лампы, радиоактивный распад, атмосферный шум и другие источники энтропии для генерации своей доли секрета.

**Эволюция индустрии:** Groth16 с per-circuit trusted setup → PLONK/Marlin с universal setup (одна церемония для всех схем) → STARKs/FRI с transparent setup (без церемонии вообще). Современные zkRollup'ы (zkSync Era, Scroll) предпочитают PLONK-подобные системы именно из-за universal setup. Но для фиксированных схем (Zcash shielded transfers, Tornado Cash mixer) Groth16 остаётся оптимальным выбором благодаря минимальному размеру proof.

Существует активное исследование полностью **transparent** систем, не требующих доверенных церемоний: **STARKs** (используют FRI вместо pairings), **Bulletproofs** (используют дискретный логарифм), **PLONK с FRI** (гибрид). Каждый подход имеет свои трейдоффы по размеру proof, скорости prover'а и скорости verifier'а. Идеальной системы пока не существует - выбор зависит от конкретного применения.

Итоги

• **R1CS** (Rank-1 Constraint System) - любое вычисление раскладывается на constraints вида `a * b = c`, где a, b, c - линейные комбинации переменных. Witness - вектор всех переменных (включая секретные), удовлетворяющий всем constraints
• **QAP** (Quadratic Arithmetic Program) - столбцы R1CS-матриц превращаются в полиномы через интерполяцию Лагранжа. Все constraints сводятся к одной проверке `A(τ)·B(τ) - C(τ) = H(τ)·T(τ)`, а лемма Шварца-Циппеля гарантирует, что одной случайной точки достаточно
• **Groth16** - proof из 3 элементов эллиптических кривых (~128 байт), верификация через bilinear pairing за ~5 мс. Самый компактный SNARK, используемый в Zcash, Tornado Cash, Filecoin
• **Trusted setup** - MPC ceremony генерирует параметры, а «1-of-N honest assumption» означает: достаточно одного честного участника из всех, чтобы система была безопасна. Помните 128 байт proof, с которых мы начали? Их компактность - прямое следствие pairing-based криптографии, а её цена - необходимость этой церемонии доверия

Связанные темы

zk-SNARK связывает криптографию эллиптических кривых с практическими системами приватности и масштабирования:

• Zero-Knowledge Proofs: введение — Базовые концепции ZKP (completeness, soundness, zero-knowledge), на которых строится вся архитектура SNARK
• zk-STARK: transparent proofs — Альтернатива SNARK без trusted setup - использует FRI вместо pairings, hash-based security вместо эллиптических кривых
• PLONK: universal SNARK — Следующее поколение SNARK: universal trusted setup (одна церемония для всех схем) вместо per-circuit setup Groth16
• KZG Commitments и полиномы — Polynomial commitment scheme, используемая в PLONK и EIP-4844. KZG - прямое развитие идеи polynomial evaluation proof из QAP

Вопросы для размышления

• Groth16 требует per-circuit trusted setup: если схема меняется, Phase 2 ceremony нужно проводить заново. Как это влияет на возможность обновления zk-систем (например, добавления новых фич в zkRollup)?
• STARKs не требуют trusted setup и устойчивы к квантовым компьютерам, но их proofs в 100-1000 раз больше. В каких сценариях размер proof критичен, а в каких - нет?
• MPC ceremony с 140,000 участниками даёт практическую уверенность в безопасности. Но можно ли математически доказать, что хотя бы один участник был честен? Где граница между математической и практической безопасностью?

Связанные уроки

• crypto-34-zkp-basics