Рекурсивные ZK-доказательства

Mina Protocol хранит всю историю блокчейна в одном proof размером 22 КБ. Не 500 ГБ как Ethereum, не 600 ГБ как Bitcoin - двадцать два килобайта, и неважно, прошёл миллион блоков или миллиард. Каждый новый блок «поглощается» предыдущим доказательством, как матрёшка: proof внутри proof внутри proof. А Polygon AggLayer идёт ещё дальше - агрегирует proofs десятков rollup'ов в один, экономя 60x на gas. Как доказать доказательство? Как сложить два вычисления в одно без потерь? И почему folding на порядки дешевле рекурсии?

• **Mina Protocol** - блокчейн с постоянным размером state proof (~22 КБ), использующий рекурсивную SNARK-композицию через Pickles (Pasta curves). Полная нода синхронизируется за секунды, а не часы
• **Polygon AggLayer** - shared proving layer, агрегирующий proofs от множества zkRollup'ов в один on-chain proof. Cross-rollup atomic transactions и экономия gas в десятки раз
• **zkSync Boojum** - proving pipeline, где тысячи мелких proofs (по одному на EVM-инструкцию) рекурсивно агрегируются до одного L1 proof через STARK→SNARK wrapping

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

• zk-SNARK: From Theory to Practice

Proof Composition: доказательство внутри доказательства

В уроке по zk-SNARK мы узнали, что Groth16 proof занимает 128 байт и верифицируется за 5 мс. Но что если нужно верифицировать **тысячи** таких proofs? Например, zkRollup генерирует proof для каждого batch транзакций, и за сутки их накапливаются сотни. Публикация каждого по отдельности - это сотни on-chain транзакций. А что если можно взять **N доказательств** и сжать их в **одно**? Именно это делает **proof composition** - верификация доказательства **внутри** другого доказательства.

Идея на первый взгляд простая: верификация zk-SNARK - это алгоритм, а любой алгоритм можно выразить как арифметическую схему (R1CS). Значит, можно написать **verifier как circuit** и доказать, что «я знаю proof π, который верификатор принимает». Prover создаёт новый proof π', доказывающий: «я успешно выполнил верификацию proof π». Verifier проверяет только π' и знает, что оригинальное утверждение верно.

Но есть ключевая проблема: Groth16 verifier использует **bilinear pairing** - операцию на эллиптических кривых. Выразить pairing как R1CS circuit **крайне дорого**: сотни тысяч constraints только для одной pairing-операции. Verifier Groth16 требует 3 pairings - это миллионы constraints. Prover, генерирующий proof для такого circuit, работает минуты или часы.

**Mina Protocol** - самый яркий пример рекурсивных proofs в production. Вместо хранения всей истории блокчейна (сотни ГБ у Ethereum), Mina поддерживает **один рекурсивный proof** (~22 КБ), доказывающий корректность всей цепочки с генезиса. Каждый новый блок - это новый шаг рекурсии: proof нового блока включает верификацию proof предыдущего. Используется система **Pickles** на Pasta curves (Pallas + Vesta), где две кривые образуют цикл, позволяющий эффективно чередовать рекурсивные шаги.

**Историческая справка:** Первые рекурсивные SNARK были описаны в работе Bitansky et al. (2013), но считались непрактичными из-за огромных circuit'ов для verifier'а. Прорыв произошёл в 2019 году, когда Bowe, Grigg и Hopwood предложили использовать cycle of curves (Pasta: Pallas + Vesta), что легло в основу Mina Protocol. С тех пор рекурсия стала стандартным инструментом: zkSync, Polygon zkEVM и Scroll используют различные формы рекурсивной композиции для агрегации batch proofs.

IVC: инкрементально верифицируемые вычисления

Proof composition позволяет сжать N proofs в один. Но что если вычисление происходит **пошагово**, и нужно доказать корректность всей цепочки шагов? Например, блокчейн - это последовательность state transitions: `State₀ → State₁ → ... → Stateₙ`. Наивный подход - создать proof для каждого перехода, а потом рекурсивно сжать все proofs. Но это требует хранить все промежуточные proofs. **IVC** (Incrementally Verifiable Computation) решает это компактнее: каждый шаг **одновременно** выполняет вычисление и проверяет proof предыдущего шага.

Ключевое отличие IVC от простой рекурсии: proof на шаге `i` доказывает корректность **всех предыдущих шагов**, а не только текущего. Это как снежный ком: каждый новый proof «поглощает» предыдущий, но размер остаётся постоянным. Verifier на любом шаге проверяет один proof и получает гарантию корректности всей цепочки от `z₀` до `zᵢ`.

Проблема классического IVC на базе рекурсивных SNARK: **augmented step function** F' содержит полный SNARK verifier как subcircuit. Для Groth16 это миллионы constraints (из-за pairing). Даже с cycle of curves verifier занимает ~100K constraints. Если сама функция F - простая (например, хеш), то verifier доминирует: 90%+ circuit'а - это проверка предыдущего proof, а не полезное вычисление. Это мотивирует поиск более дешёвых способов «поглощения» предыдущего proof - и именно здесь появляется **Nova**.

**IVC vs обычная рекурсия в цифрах:** Рекурсивный SNARK (Groth16 + cycle of curves) - verifier circuit ~500K–1M constraints, prover time ~30–60 секунд на шаг. Nova (folding) - нет SNARK verifier'а в circuit, overhead ~10K constraints, prover time ~1 секунда на шаг. Разница в 30–60x - вот почему folding schemes произвели революцию в IVC.

Nova: folding вместо рекурсии

Мы видели, что главный bottleneck IVC - **SNARK verifier внутри circuit**. Каждый шаг тратит сотни тысяч constraints на верификацию предыдущего proof. В 2022 году Abhiram Kothapalli и Srinath Setty из Microsoft Research предложили радикально иной подход: **Nova**. Вместо того чтобы **доказывать** корректность предыдущего шага (создавая полный SNARK proof), Nova **складывает** (folds) два instance'а R1CS в один. Folding - не доказательство, а **алгебраическое объединение** - и оно на порядки дешевле.

Чтобы понять folding, нужно расширить формат R1CS. Обычный R1CS: для witness `w` и constraints `(A, B, C)` выполняется `Az ∘ Bz = Cz` (поэлементное произведение). Nova вводит **Relaxed R1CS**: `Az ∘ Bz = u·Cz + E`, где `u` - скалярный множитель, а `E` - вектор ошибки. Обычный R1CS - частный случай при `u = 1`, `E = 0`. Фокус в том, что два relaxed R1CS instance'а можно **линейно скомбинировать** в один, и результат тоже будет relaxed R1CS.

Критически важно: folding **не создаёт proof**. Оно накапливает вычисления в **аккумуляторе** (relaxed R1CS instance). После N шагов folding аккумулятор содержит «сжатое представление» всех N вычислений, но это ещё не proof - verifier не может проверить relaxed R1CS без знания witness. Финальный SNARK proof создаётся **один раз** в самом конце: prover берёт аккумулятор и генерирует обычный SNARK, доказывающий, что он знает witness для накопленного relaxed R1CS.

**SuperNova** (Kothapalli & Setty, 2022) расширяет Nova для **нескольких различных circuit'ов**. В оригинальном Nova функция шага F - одна и та же на каждом шаге. SuperNova позволяет чередовать разные функции F₁, F₂, ..., Fₖ, выбирая нужную на каждом шаге. Это критично для zkVM (виртуальных машин), где каждая инструкция - свой circuit. **HyperNova** (2023) - дальнейшее обобщение, работающее с CCS (Customizable Constraint System) вместо R1CS, поддерживающее higher-degree constraints и совместимое с PLONK-style arithmetization.

**Folding vs рекурсия - в чём разница?** Рекурсивный SNARK на каждом шаге генерирует полный cryptographic proof (pairing, commitments, Fiat-Shamir). Nova на каждом шаге выполняет **алгебраическую операцию** - линейную комбинацию witness'ов с одним commitment. SNARK вызывается только один раз в самом конце. Это как разница между «перестроить весь дом после каждого этажа» и «складывать кирпичи, а крышу поставить один раз».

Proof Aggregation: масштабирование L2 в реальном мире

Мы изучили рекурсию (proof внутри proof), IVC (пошаговое накопление) и Nova (folding вместо рекурсии). Теперь соберём всё вместе в контексте реального применения - **proof aggregation** для Layer 2. Сегодня на Ethereum работает десяток zkRollup'ов, каждый из которых периодически публикует proof на L1. Каждая on-chain верификация стоит ~300K–500K gas. А что если можно взять proofs от **нескольких rollup'ов** и объединить их в **один proof**, проверяемый L1 за одну транзакцию?

**Polygon AggLayer** - самый амбициозный проект в этом направлении. Идея: создать **shared proving layer** для всех Polygon-compatible rollup'ов (Polygon zkEVM, Polygon CDK chains, Miden и другие). Каждый rollup генерирует proof по своему протоколу (Groth16, PLONK, STARK), AggLayer принимает их все, конвертирует в единый формат через proof composition, и публикует один aggregated proof на Ethereum. Это позволяет не только экономить gas, но и обеспечивать **cross-chain atomic transactions** между rollup'ами через shared state root.

**zkSync Boojum** - proving система zkSync Era, использующая proof aggregation на практике. Boojum генерирует proofs для отдельных circuit'ов (каждая EVM-инструкция - свой circuit), затем агрегирует их в batch proof через рекурсивную композицию, и наконец сжимает batch proofs в один final proof через SNARK wrapping (STARK → SNARK конвертация для дешёвой L1 верификации). Весь pipeline: тысячи мелких proofs → десятки batch proofs → один L1 proof.

Будущее proof aggregation - **shared security** через shared proving. Представьте: вместо десятков изолированных rollup'ов, каждый со своим prover'ом, - единый proving layer, где rollup'ы делят затраты на proving пропорционально использованию. AggLayer от Polygon, shared sequencing от Espresso, universal proving от Succinct - все эти проекты движутся к одной цели: сделать ZK-proving **commodity** (общедоступным ресурсом), как AWS сделал commodity из серверов.

**Три поколения ZK масштабирования:** Первое поколение (2019–2021): отдельный rollup, отдельный proof, отдельная верификация на L1. Второе поколение (2022–2024): рекурсивная агрегация внутри rollup'а - сотни batch proofs сжимаются в один. Третье поколение (2024+): shared proving между rollup'ами - AggLayer, proof marketplace, cross-chain composability. Мы переходим от «один rollup = один proof» к «вся экосистема = один proof».

Итоги

• **Proof Composition** - верификация SNARK внутри SNARK circuit. Главный вызов - pairing в non-native поле (миллионы constraints). Cycle of curves (Pallas + Vesta) решает проблему чередованием native полей. Mina Protocol использует это для constant-size блокчейна
• **IVC** (Incrementally Verifiable Computation) - каждый шаг одновременно выполняет вычисление и верифицирует proof предыдущего шага. Proof на шаге N доказывает корректность ВСЕХ N шагов, сохраняя постоянный размер
• **Nova** - folding scheme, заменяющая SNARK-рекурсию алгебраическим объединением через Relaxed R1CS. На порядки дешевле: ~10K constraints overhead на шаг вместо ~500K. SNARK создаётся один раз в конце. SuperNova и HyperNova расширяют подход для множественных circuit'ов
• **Proof Aggregation** - объединение proofs нескольких rollup'ов (AggLayer) или батчей (Boojum) в один on-chain proof. Помните 22 КБ proof Mina, с которого мы начали? Та же идея рекурсии, масштабированная до целой экосистемы L2: от «один rollup = один proof» к «вся экосистема = один proof»

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

Рекурсивные ZK-доказательства - связующее звено между базовыми SNARK/STARK протоколами и практическими системами масштабирования:

• zk-SNARK: от теории к практике — R1CS, QAP, Groth16 и trusted setup - фундамент, на котором строится рекурсивная композиция. Verifier Groth16 как circuit - основа proof recursion
• PLONK: universal SNARK — Universal setup и custom gates PLONK делают его основным выбором для recursive proof systems. Nova/SuperNova часто используют PLONK для финального proof
• zkEVM: виртуальная машина с доказательствами — zkEVM генерирует тысячи circuit-proofs (по одному на инструкцию), которые агрегируются через рекурсивную композицию в один batch proof
• zk-Rollups: масштабирование через validity proofs — zkRollup'ы - главный потребитель proof aggregation. AggLayer и shared proving - следующий эволюционный шаг от изолированных rollup'ов к shared security

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

• Nova делает SNARK proof только один раз в конце, после всех шагов folding. Что произойдёт, если на шаге 5000 из 10000 prover допустит ошибку (некорректный witness)? Обнаружится ли это при folding или только при создании финального SNARK?
• Proof marketplace создаёт экономические стимулы для specialized proving hardware (GPU, FPGA, ASIC). Как это соотносится с идеей децентрализации - не приведёт ли это к централизации proving в руках нескольких крупных операторов?
• AggLayer агрегирует proofs от rollup'ов с разными proving systems (Groth16, PLONK, STARK). Какие ограничения это накладывает на формат aggregation - можно ли складывать Groth16 и STARK напрямую, или нужна промежуточная конвертация?

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

• crypto-34-zkp-basics