zk-STARK: прозрачность без trusted setup

Чтобы доверять Groth16 SNARK, 140,000 человек провели церемонию и поклялись уничтожить свои секреты. Если хотя бы один солгал - вся система под угрозой. А что если построить zero-knowledge proof, который вообще не требует доверия ни к кому? Где единственное допущение - что SHA-256 работает как положено? Именно это делает STARK: вместо эллиптических кривых и секретных церемоний - таблица вычислений, полиномы и хеш-функция. Proof в 1000 раз больше, но за это вы получаете нечто, чего не может дать ни один SNARK: полную прозрачность и устойчивость к квантовому компьютеру, который однажды уничтожит всю криптографию на эллиптических кривых.

• **StarkNet** - L2 на Ethereum, где Cairo-программы компилируются в STARK proof, агрегирующий тысячи транзакций без trusted setup. Обрабатывает до 500 TPS при стоимости ~0.01 за транзакцию
• **dYdX v4** - крупнейшая децентрализованная биржа деривативов, использующая STARK proof'ы StarkWare для settlement'а ордеров. Обработала более 1 трлн совокупного объёма торгов
• **Polygon Miden** - ZK-rollup, полностью построенный на STARK, с client-side proving: proof генерируется на устройстве пользователя, обеспечивая приватность без доверия к секверсеру

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

• zk-SNARK: From Theory to Practice

AIR: вычисление как алгебраическая таблица

В уроке по zk-SNARK мы превращали программу в **R1CS** - систему constraints вида `a * b = c`. STARK использует другой формат: **AIR** - Algebraic Intermediate Representation. Вместо системы умножений мы записываем вычисление как **таблицу** (execution trace), а затем формулируем **полиномиальные ограничения** на переходы между строками. Это даёт STARK ключевое преимущество: constraint'ы описывают не отдельные операции, а **паттерн**, повторяющийся на каждом шаге вычисления.

Execution trace - это матрица, где каждая строка представляет состояние вычисления на конкретном шаге, а столбцы - регистры (переменные). Для доказательства корректности нужны два типа ограничений: **transition constraints** (связь между соседними строками) и **boundary constraints** (значения в начальной/конечной строке).

Ключевое отличие AIR от R1CS: в R1CS каждый constraint уникален (разные коэффициенты в матрицах A, B, C), а в AIR **один и тот же полином** описывает constraint для **всех строк**. Это значит, что размер описания AIR не зависит от длины вычисления - только от его **ширины** (количество регистров) и **степени** перехода. Вычисление из миллиона шагов описывается тем же constraint'ом, что и из десяти.

**AIR vs R1CS - сравнение подходов.** R1CS (SNARK): каждая операция - отдельный constraint, размер описания растёт линейно с количеством операций. Перевод ETH - ~5,000 constraints. AIR (STARK): один transition constraint описывает паттерн для всех строк, размер описания фиксирован. Тот же перевод ETH - 2-3 transition constraints на **миллион строк** trace. Цена этой компактности: prover должен интерполировать огромный trace в полиномы, что требует FFT за O(n log n). Но для verifier'а это прозрачно - он работает только с composition polynomial.

FRI: проверка полиномов без trusted setup

После AIR мы свели корректность вычисления к вопросу: «является ли composition polynomial действительно полиномом низкой степени?» В SNARK эту проверку делал pairing на эллиптических кривых - но он требовал trusted setup. **FRI** (Fast Reed-Solomon Interactive Oracle Proof) решает ту же задачу, используя только **хеш-функции и Merkle-деревья**. Это протокол «proximity testing»: он проверяет, что функция, заданная набором значений, **близка** к полиному степени не выше d.

Интуиция за FRI: если у вас полином степени d, заданный значениями в 2d точках, можно «сложить» его пополам - разделить на чётную и нечётную части - и получить полином степени d/2 на d точках. Повторяя этот процесс log(d) раз, мы дойдём до константы. Если на каком-то шаге «складывание» не сработает, значит исходная функция не была полиномом нужной степени.

Почему FRI даёт **transparency**? Единственный «секретный» элемент - случайные challenge'ы α₁, α₂, ... Но verifier генерирует их **после** получения Merkle root, поэтому prover не может подстроиться. А для перехода от interactive к non-interactive протоколу применяется **трансформация Фиата-Шамира**: challenge'ы вычисляются как хеш от предыдущих commitment'ов. Никаких секретных параметров, никакой церемонии - только хеш-функция.

**Размер FRI proof** зависит от количества query-точек и глубины folding. Для security level 128 бит нужно ~30 query-точек, каждая требует Merkle-путь на каждом уровне. Итого: proof ≈ 30 × log(d) × (размер хеша) ≈ **40-200 KB** - в 200-1000 раз больше, чем Groth16 (128 байт). Но эта «плата» за размер покупает полную прозрачность и квантовую устойчивость.

Transparency: только хеши, ничего больше

Теперь мы можем точно определить, что делает STARK **transparent**: вся система построена на двух примитивах - **collision-resistant hash function** (SHA-256, Blake3, Poseidon) и **FRI** для proximity testing полиномов. Нет эллиптических кривых, нет pairings, нет toxic waste. Любой может проверить proof, имея только публичный код и хеш-функцию. Это фундаментальное отличие от SNARK, где security опирается на алгебраическую структуру elliptic curve groups.

В криптографии различают три типа setup: **per-circuit** (Groth16 - новая церемония для каждой схемы), **universal/updatable** (PLONK, Marlin - одна церемония для всех схем, можно «достраивать» участников) и **transparent** (STARK, Bulletproofs - setup не требуется вовсе). Transparent - сильнейшая гарантия: доверительные допущения сведены к стандартной криптографической модели (random oracle для хеш-функций).

**Cairo** - язык программирования, разработанный StarkWare специально для STARK. Программа на Cairo компилируется в execution trace, совместимый с AIR. Это как Solidity для EVM, но оптимизированный для генерации zk-proof'ов. StarkNet - L2-решение на Ethereum, где все транзакции исполняются в Cairo VM, а на L1 отправляется только STARK proof, сжимающий тысячи транзакций в один commitment.

**Proof size - это не приговор.** 100 KB кажется огромным рядом с 128 байтами Groth16, но в контексте L2-rollup'ов proof публикуется один раз на тысячи транзакций. При batch из 10,000 транзакций стоимость proof'а - ~10 байт на транзакцию. StarkWare обрабатывает сотни тысяч транзакций в сутки на dYdX (деривативы) и StarkNet (general-purpose L2), и размер proof компенсируется масштабом. рекурсивные STARK позволяют «сжимать» несколько proof'ов в один, ещё больше снижая amortized cost.

Квантовая устойчивость: почему STARKs переживут квантовый компьютер

Квантовая устойчивость STARK - не маркетинговое преимущество, а прямое следствие архитектуры. Вся безопасность STARK опирается на **collision resistance хеш-функций**. Алгоритм Шора, который на квантовом компьютере ломает RSA, ECC и pairings за полиномиальное время, **бесполезен** против хеш-функций - он работает только с задачами, имеющими алгебраическую структуру (факторизация, дискретный логарифм). Алгоритм Гровера ускоряет поиск коллизий, но лишь **квадратично**: для SHA-256 security снижается с 2¹²⁸ до 2⁶⁴ - достаточно увеличить длину хеша до 384 или 512 бит.

Реалистичный timeline квантовой угрозы: криптографически значимые квантовые компьютеры (способные запустить алгоритм Шора для 256-битных кривых) ожидаются между 2030 и 2040 годами. Но готовиться нужно **уже сейчас**: данные, зашифрованные сегодня, могут быть записаны и расшифрованы позже (атака «harvest now, decrypt later»). NIST уже стандартизировал post-quantum алгоритмы в 2024 году: **ML-KEM** (Kyber) для шифрования и **ML-DSA** (Dilithium) для подписей - оба основаны на lattice-задачах.

Lattice-based ZKP - перспективное направление, которое может совместить **компактный proof** (как SNARK) с **квантовой устойчивостью** (как STARK). Задача Module-LWE (Learning With Errors), лежащая в основе Kyber и Dilithium, считается квантово-устойчивой и допускает построение polynomial commitment schemes. Но пока эти системы остаются в стадии исследований - для production-ready ZKP в 2025 году STARK является единственным квантово-устойчивым вариантом с подтверждённой безопасностью.

**Практический взгляд на квантовую миграцию.** StarkWare (StarkNet, dYdX) и Polygon Miden уже работают на STARK - им не нужна миграция. zkSync и Scroll используют PLONK + KZG и планируют переход на FRI-based commitment. Zcash исследует Halo 2 (рекурсивный PLONK без trusted setup), но с ECC-based commitments - квантовая уязвимость остаётся. Полная миграция экосистемы ZKP на post-quantum примитивы займёт 5-10 лет, и STARK-based системы имеют в этой гонке стратегическое преимущество: им достаточно увеличить длину хеша.

Итоги

• **AIR** (Algebraic Intermediate Representation) - вычисление записывается как execution trace (матрица), а transition constraints описывают паттерн перехода между строками. В отличие от R1CS, один constraint покрывает все шаги - размер описания не зависит от длины вычисления
• **FRI** (Fast Reed-Solomon IOP) - протокол proximity testing, проверяющий, что функция является полиномом низкой степени. Работает через последовательное «складывание» полинома пополам с Merkle commitment'ами на каждом уровне. Fiat-Shamir превращает интерактивный протокол в non-interactive proof
• **Transparency** - STARK не требует trusted setup, полагаясь только на collision-resistant hash functions. Proof больше (~100 KB vs 128 байт Groth16), но при batch-верификации в rollup'ах amortized cost сопоставим. Cairo - язык для написания STARK-совместимых программ (StarkNet)
• **Квантовая устойчивость** - алгоритм Шора ломает ECC-based SNARK'и, но бесполезен против хеш-функций. Помните церемонию 140,000 человек из начала урока? STARK делает её ненужной - и при этом переживёт появление квантового компьютера, который обнулит безопасность всех ECC-based систем

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

zk-STARK связывает hash-based криптографию с практическим масштабированием блокчейнов и post-quantum безопасностью:

• zk-SNARK: от теории к практике — SNARK использует R1CS + QAP + pairings, STARK заменяет их на AIR + FRI + хеши. Понимание обоих подходов позволяет осознанно выбирать tradeoff между proof size и trust assumptions
• PLONK: universal SNARK — PLONK - гибрид: universal setup (одна церемония для всех схем) и возможность замены KZG на FRI для получения transparency без потери universality
• zkEVM: EVM-эквивалентные доказательства — zkEVM использует ZKP (STARK или SNARK) для доказательства корректности исполнения EVM-транзакций. Выбор proof system определяет tradeoff'ы L2-решения
• ZK-Rollups: масштабирование через доказательства — ZK-Rollup'ы - главное применение STARK: тысячи транзакций сжимаются в один proof, а transparency устраняет необходимость доверия к оператору rollup'а

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

• STARK proof в 1000 раз больше SNARK, но STARK prover работает быстрее (нет дорогих EC-операций). Для L2-rollup'а, обрабатывающего 10,000 TPS, что важнее: скорость prover'а (задержка finality) или размер proof (стоимость on-chain публикации)?
• Если квантовый компьютер появится в 2035 году, а миграция ZKP-системы с ECC на hash-based примитивы займёт 3 года, когда нужно начинать переход? Учитывайте атаку «harvest now, decrypt later» для данных, публикуемых on-chain.
• Cairo (StarkWare) - это domain-specific language для STARK. Альтернативный подход - zkEVM, который доказывает исполнение обычного EVM-кода. Какие преимущества и ограничения у каждого подхода с точки зрения разработчика и пользователя?

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

• crypto-44-zk-snarks