The Present Must Prove the Past

Перенести валидность вперёд

Пусть $S_h$ обозначает состояние после блока $h$, а $\pi_h$ обозначает доказательство, связанное с этим состоянием.

Для каждого нового блока proof должен установить два факта:

Результатом становится новое доказательство $\pi_h$:

Каждое доказательство проверяет предыдущее и добавляет ещё один переход. На высоте десять миллионов proof не содержит десять миллионов отдельных proofs. Его форма не растёт вместе с высотой цепочки. Валидность переходов переносится вперёд рекурсивно.

Теперь возникает важный вопрос для консенсуса:

когда доказательство становится основанием для принятия состояния?

Если именно $\pi_h$ является причиной принять $S_h$ как валидное состояние, proof не может быть дополнительным сертификатом, который появится когда-нибудь после блока. Причина принять состояние должна существовать уже в тот момент, когда оно входит в консенсус.

Иначе у протокола появляются две независимые точки прогресса:

Тогда пришлось бы отдельно определять, что означает ещё не доказанная вершина, какая из двух точек является главной, что сохраняется после сбоя и откуда должно продолжиться proving.

Гораздо чище определить атомарную единицу принятия:

Новое состояние входит в консенсус вместе с доказательством перехода, который его создал. State и proof движутся вместе, поэтому у консенсуса остаётся одна точка прогресса.

Рекурсивный proof теперь не является отдельным сертификатом об истории.

Он переносит саму причину валидности из одного состояния в следующее.

И если историческое исполнение больше не выполняет эту роль, меняется и роль самой истории.

Что тогда остаётся от истории?

Если текущее состояние уже несёт рекурсивное доказательство своего валидного происхождения, старые тела блоков больше не нужны новому узлу для того, чтобы установить валидность настоящего.

Но прошлое не перестаёт быть важным. Иногда нас интересует не сегодняшний State, а конкретное событие в прошлом.

Представим, что я кому-то заплатил и спустя время должен доказать, что сеть действительно приняла эту транзакцию. Я могу сохранить саму транзакцию и её Merkle path. По ним можно восстановить transaction root блока и доказать, что транзакция действительно входила в этот блок.

Но одного факта всё ещё не хватает.

Блок мог быть полностью валидным, распространяться по сети и всё же проиграть конкурирующей ветви. Включение в блок ещё не означает включение в каноническую цепочку.

Поэтому доказательство платежа должно отвечать на два вопроса:

На первый вопрос отвечают транзакция и её Merkle path.

Можно было бы заставить рекурсивный proof фиксировать аутентифицированную историю блоков с возможностью открыть любую высоту. Но нет причины возлагать на него ещё и эту задачу.

Заголовки блоков достаточно компактны, чтобы хранить их постоянно. Цепочка заголовков сохраняет канонический spine и позволяет узлу определить, входит ли в него конкретный блок.

Теперь у двух частей разные роли.

Транзакция и Merkle path доказывают:

Проверенная цепочка заголовков доказывает:

Вместе они образуют небольшое переносимое доказательство платежа, payment receipt.

Полное тело блока для проверки такого платежа больше не требуется.

Каждому узлу не нужно вечно хранить все транзакции только ради того, чтобы когда-нибудь доказать одну из них. Тот, кому важен конкретный платёж, сохраняет receipt этого платежа.

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

Теперь разные данные выполняют разные задачи:

История не исчезла. Её задачи разделились. Узлу больше не нужно обращаться со всей историей исполнения сети как с одним огромным объектом, который необходимо вечно хранить и воспроизводить целиком.

Текущее состояние тоже не обязано быть историей

Та же логика меняет представление активного состояния.

В UTXO-системе для проверки нового перехода не нужны все outputs, которые когда-либо существовали. Нужны только те, которые существуют и могут быть потрачены сейчас.

Поэтому активное состояние может содержать именно live UTXOs. Потраченные outputs покидают его. Освободившуюся capacity можно использовать снова, а пустые области не обязаны занимать физическое место.

Размер состояния, которое обязан хранить узел, определяется текущим использованием сети, а не накопленной историей.

Он зависит от live set и той capacity, которая нужна сети сейчас, а не от общего числа транзакций за всё время её существования.

Возраст цепочки больше не означает, что придётся воспроизводить всё больше исторического исполнения или продолжать хранить всё больше мёртвого состояния.

Но остаётся ещё одна фундаментальная задача блокчейна.

Если валидность уже установлена, кто выбирает порядок?

Рекурсивный proof может установить, что переход состояния валиден.

Но он не может выбрать между двумя валидными переходами.

Представим, что два producer построили разные дочерние состояния от одного parent. Оба перехода корректны. Оба блока несут валидные proofs.

Какой из них становится каноническим?

Это задача порядка, а не валидности.

Именно для этого нужен proof of work.

Proof уже установил валидность. PoW даёт конкурирующим валидным ветвям объективно сравнимую накопленную работу и позволяет сети сойтись на одной канонической цепочке.

Разделение получается простым:

Из этого разделения меняется и порядок производства блока.

Сначала строится transition. Затем доказывается его корректность. Когда всё значимое для консенсуса, кроме nonce, зафиксировано, начинается поиск nonce.

Nonce намеренно исключён из утверждения, которое покрывает рекурсивный proof. Майнинг может менять nonce, не затрагивая ничего из уже доказанного.

Победивший nonce завершает тот же block template, валидность перехода которого уже установлена.

Hashpower не способен превратить неправильный state transition в правильный. Он не исправляет невалидную транзакцию. Он не делает сломанный proof валидным.

Hashpower определяет канонический порядок между уже корректными переходами.

Этот канонический выбор записывается в постоянную цепочку заголовков, которая также даёт payment receipts их канонический anchor.

Так block production отделяется от raw hashing, но proving остаётся частью производства блока.

Block producer и есть prover. Он должен хранить текущее состояние, построить следующий transition и создать рекурсивный proof до того, как начнётся поиск nonce. Отдельного prover, который сертифицирует блок позже, не существует.

В production path только механический поиск nonce можно вынести в отдельную делегируемую роль. Внешние workers, pools и специализированное оборудование могут получить неизменяемый уже доказанный block template и искать для него nonce. Они не могут изменить transition, исправить невалидный блок или создать другое состояние.

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

Теперь всё упирается в proving

До сих пор задача была в основном архитектурной.

Когда рекурсивный proof становится обязательным для каждого блока, задача становится вычислительной. Это не редкий checkpoint и не сертификат, который строится постфактум. Без proof следующее состояние вообще не может войти в консенсус.

Практический вопрос уже не в том, можно ли построить такой proof теоретически.

Для proof-native block production узким местом становится proving, а не verification.

Если каждый блок требует рекурсивного proof, независимый майнер должен успевать построить его в пределах block interval на обычном оборудовании. Если для производства блока нужен дорогой proving cluster, мы просто перенесли централизацию в другое место.

Дешёвой проверки недостаточно. Producer строит proof на критическом пути каждого блока, а требования к памяти не должны превращать независимое производство в задачу только для дата-центра.

Это ограничение определяет, как приходится строить proof system. Но прежде чем оптимизировать prover, нужно сделать более фундаментальный выбор: на каких криптографических предпосылках будет держаться валидность цепочки от genesis?

На какой криптографии будет держаться настоящее?

Архитектура уже сильно сузила пространство выбора. Proof system должна поддерживать recursion. Форма proof не должна расти вместе с высотой цепочки. Proving должен быть достаточно быстрым и экономным по памяти для независимого производства блоков на обычном оборудовании. Проверка рекурсивного proof должна оставаться практичной независимо от возраста сети.

Здесь я хочу явно зафиксировать ещё два требования.

Первое требование: transparency.

No trusted setup.

Второе требование строже:

сквозная постквантовая корректность от genesis.

Именно рекурсивный proof позволяет узлу принять текущее состояние как результат валидной цепочки переходов от genesis. Поэтому важное для нас свойство гораздо шире, чем постквантовая безопасность отдельных компонентов.

Квантовый противник может попытаться подделать авторизацию, переход, proof одного из предков или сам terminal. Утверждение о корректности должно охватывать весь путь и итоговое событие принятия: может ли любая из этих подделок заставить узел принять недопустимый текущий State как имеющий валидный путь от genesis?

Именно это является требованием.

Эти ограничения и определили криптографический стек.

Committed arithmetic работает над бинарными полями, прежде всего над GF(2^128). Security-critical challenges и recursive authentication используют GF(2^256). Общей permutation для consensus proof system стала Poseidon2b.

Минимальный размер proof не является целью.

Рекурсивные системы, основанные на группах эллиптических кривых и предположении о сложности дискретного логарифмирования, могут давать гораздо меньшие proofs. Это разумный инженерный выбор, когда сквозная постквантовая корректность от genesis не требуется.

Но они не могут обеспечить сквозную постквантовую корректность рекурсивного пути валидности от genesis. Если какая-либо часть этого пути опирается на криптографию на эллиптических кривых, то отказаться от неё позже можно будет, только заменив сами основы recursion вместе с commitments и consensus relations, построенными на этой основе.

Такой криптографический долг был неприемлем для нас с самого первого блока.

Новая архитектура стала Parano1d

Parano1d представляет собой proof-native Layer 1, построенный вокруг этой архитектуры. Текущее состояние консенсуса в протоколе называется State и представляет собой точный разреженный вектор live UTXOs вместе с consensus counters. Рекурсивный proof каждого блока называется HistoryStep. Каждый HistoryStep доказывает точный переход своего блока и проверяет предыдущий HistoryStep внутри той же relation.

Блок принимается только вместе с соответствующим terminal:

Узел хранит текущий State, постоянную компактную цепочку заголовков и ограниченный суффикс последних полных блоков. Рекурсивный proof устанавливает валидность переходов, а порядок PoW и накопленную работу узел проверяет по цепочке заголовков. Старые тела блоков не участвуют в активной проверке.

Платёж можно сохранить как переносимый receipt. Потраченная capacity возвращается в использование, а пустые области не требуют постоянного физического хранения.

Поиск nonce начинается только после завершения nonce-independent block proof.

Production path выглядит так:

Как я довёл recursive proving до 10.7 секунды на обычном ноутбуке

Средний block target Parano1d составляет 15 секунд. Поэтому proving time становится ограничением уровня консенсуса: независимый producer должен успевать построить рекурсивный proof и оставаться конкурентоспособным без отдельного proving cluster.

Одним из главных источников стоимости в prover оказался Poseidon2b.

Одна и та же permutation используется в State commitments, Merkle relations, transaction commitments, proof transcripts и recursive verification. Если доказывать каждый вызов отдельной цепочкой constraints, prover тысячи раз повторяет почти одну и ту же алгебраическую работу.

Inputs меняются. Связи между вызовами меняются. Сама permutation остаётся прежней.

Поэтому я изменил представление.

Вместо множества отдельных копий я поместил все исполнения Poseidon2b в одну глобальную трассу с тремя координатами:

Proof устанавливает корректность permutation сразу для всего набора. Отдельные relations связывают каждый вызов с теми местами, где нужны его входы и выходы.

Я назвал эту конструкцию FROST-GKR, Frobenius Reduction over Shifted Tables.

На контрольной нагрузке из 59 исполнений Poseidon2b:

Это результаты уровня reduction, а не утверждение об ускорении HistoryStep целиком в 10.69 раза. Полные границы benchmark и журнал измерений опубликованы в статье FROST-GKR и reference artifact.

В production используются два класса proof. B25 является стандартным профилем производства блоков. B255 использует более крупную аутентифицированную матрицу и другую геометрию блока. Оба класса допустимы для консенсуса и обрабатываются одним production verifier.

С этой конструкцией production prover показывает следующие результаты HistoryStep:

Для стандартного production path важен результат B25 на ноутбуке: 10.734 секунды p50 на обычном оборудовании при среднем block target 15 секунд.

Benchmark измеряет построение HistoryStep, а не полную задержку майнинга. Точная граница измерения и методика воспроизведения опубликованы в performance record.

Что означает сквозная постквантовая корректность от genesis?

Назвать несколько primitives постквантовыми ещё не означает доказать сквозную корректность всей системы.

Вопрос безопасности здесь конкретен:

может ли квантовый противник подделать валидность в любой точке истории, представленной рекурсивным proof, и заставить узел принять недопустимый текущий State как имеющий валидный путь от genesis?

Это и есть failure event.

Атака не обязана быть направлена на последний HistoryStep. Она может начаться глубже в истории, представленной рекурсивным proof, и попытаться перенести ложное утверждение вперёд через следующие proofs. Поэтому теорема должна охватывать каждый компонент, от которого зависит окончательное принятие:

Утверждение не ограничено одной подписью, одним hash, одним компонентом proof или одной высотой цепочки.

Оно относится к текущему State, который сеть принимает как валидный от genesis.

Для production profile опубликованы два отдельных анализа, и они отвечают на разные вопросы.

Классический анализ FS-FRI по Block и Tiwari даёт:

при target 128 bits.

Отдельная исполняемая теорема в quantum random-oracle model рассматривает всю invalid-State game от genesis против одного stateful quantum adversary. Все представленные предки учитываются в рамках единого бюджета ресурсов противника.

Вывод о достижении Category 1 для production profile имеет две явные предпосылки. Для фиксированного production compiler Poseidon2b должно выполняться:

Также должна выполняться заявленная нижняя граница стоимости coherent oracle responses по числу логических вентилей и глубине.

В идеальной модели доминирующая граница произведения числа вентилей на глубину для успеха с вероятностью 1/2 составляет:

Ресурсный ориентир NIST для AES-128 Category 1 в той же модели с учётом глубины составляет:

Полная граница вероятности успеха в идеальной модели внутри Category 1 envelope:

При выполнении двух предпосылок запас для фиксированного Poseidon2b сохраняет полную вероятность успешной атаки на production profile ниже 1/2 во всей ресурсной области Category 1. Полная теорема, предпосылки, production parameters и исполняемая арифметика опубликованы в soundness certificate.

Важны не только числа, но и область утверждения.

Не отдельная подпись.

Не отдельный hash.

Не один компонент proof.

Не одна точка цепочки.

А всё текущее состояние, которое сеть принимает как валидное от genesis блока.

Это здесь и означает end-to-end.