Verkle tree — компактные доказательства состояния для «stateless» Ethereum

Интуиция: почему Merkle-ветка «распухает», а Verkle — нет

• В Merkle/MPT для доказательства включения ключа нужно перечислять соседние хеши на каждом уровне дерева — получается логарифмический по глубине и довольно «толстый» набор данных. Чем глубже дерево (чем меньше ветвление и больше состояние), тем длиннее «ветка».

• В Verkle каждый внутренний узел хранит коммитмент к массиву дочерних значений. Доказательство «вытягивает» не все соседние хеши, а пруф корректности конкретной позиции в векторе, на который «ссылается» коммитмент. Поскольку векторные коммитменты допускают компактные пруфы (в Ethereum выбран KZG), размер пруфа почти не зависит от числа детей. Поэтому можно делать широкие узлы (например, с ветвлением 256), резко уменьшая глубину дерева и суммарный объём свидетеля.

Базовые понятия

• Коммитмент. Криптографическая «связка» на набор данных: вы публикуете компактный «отпечаток» (commitment) и позже можете доказать, что конкретное значение было частью зафиксированного набора.

• Векторный коммитмент. Коммитмент на упорядоченный список значений с возможностью доказать корректность элемента по индексу. Важные свойства — компактность пруфа и проверяемость относительно опубликованного коммитмента.

• KZG-коммитменты. Полиномиальные коммитменты (Kate–Zaverucha–Goldberg), позволяющие делать постоянного размера пруфы корректности значения многочлена в точке. В контексте Verkle список дочерних значений «вкладывается» в полином, который коммитится, — а доказательство корректности «позиции» сводится к проверке значения полинома. См. Kzg Commitments.

• Witness (свидетель). Набор данных, который поставляется вместе с блоком/транзакцией и позволяет узлу проверить корректность чтений состояния без локального доступа к полному состоянию.

Структура Verkle-дерева

По смыслу Verkle — это trie (префиксное дерево) с широкими узлами и особой схемой коммитмента/доказательств.

Ключи состояния. В Ethereum-спеке ключ представляют в виде 32-байтного ключа особой формы:

31-байтовый stem — «ствол» пути (основная часть ключа),

1-байтовый suffix — «хвост», который различает тип/ячейку значения в этом «стволе» (например, слоты стореджа, код аккаунта, поля заголовка аккаунта и т. п.).

Такое разбиение упрощает батчинг чтений и уменьшает повторяемость пруф-частей: много обращений к разным suffix одного и того же stem «делят» часть сведений в общем свидетеле.

Типы узлов (обобщённо):

• Внутренние (inner) узлы — содержат векторный коммитмент (набор «детей» по индексам 0..255). Значения детей — это либо следующие узлы (их коммитменты/ссылки), либо листовые значения.

• Extension/leaf-узлы — «развилки» на концах путей, привязанные к stem и хранящие до 256 «ячеек» по всем возможным suffix (0..255) для данного ствола. Отсутствующие ячейки трактуются как пустые.

• Ветвление и глубина. Типичный выбор для Ethereum — ветвление 256 (ширина по одному байту пути за уровень). Это даёт малую глубину (обычно 2–3 уровня до extension-узла) и высокую «совместимость» с байтовыми ключами.

См. также: Размётка state-ключей в Ethereum (создать), Патриция-tries (создать).

Как строится корень состояния

Как и в Merkle/MPT, над всем деревом считается корневой коммитмент (root), который включается в заголовок блока. Разница в том, что:

• на каждом внутреннем узле фиксируется KZG-коммитмент к массиву «детей» (256 позиций);

• листовые/extension-узлы фиксируют коммитмент к ячейкам для данного stem;

• верификация чтений/записей состояния сводится к проверке KZG-пруфов от листа к корню.

Доказательства (witness): принцип работы

Чтобы проверить доступ к значению V = state[key], валидатору, который не хранит состояние, нужно получить от построителя блока witness:

Путь ключа (stem + suffix) и указание, в какой «ячейке» хранится V;

Пруф корректности для соответствующего extension-узла: «массив 256 ячеек действительно коммитится в опубликованный коммитмент листа, и в позиции suffix лежит V»;

Пруфы для внутренних уровней, что «коммитмент листа является элементом массива детей у родителя в позиции i», и так — пока не дойдём до корня.

Благодаря KZG-пруфам и широким узлам количество передаваемых данных компактно: в среднем оценка порядка сотен байт на аккаунт/ключ, а общий witness для блока с батчингом чтений остаётся приемлемым для p2p-распространения. Это ключ к stateless-клиентам: они не держат state, но «видят» достаточно, чтобы проверить корректность доступа.

См. Stateless Clients.

Сравнение: Merkle Patricia Trie vs Verkle

См. Merkle Patricia Trie, Kzg Commitments, Stateless Clients.

Почему KZG (и какие есть альтернативы)

KZG даёт постоянного размера пруфы и быструю проверку, опирается на pairing-кривые и доверительную установку (toxic waste) — это архитектурный компромисс, принятый экосистемой Ethereum ранее (см. EIP-4844 для блобов данных) и повторно используемый для Verkle.

Альтернативные конструкции (векторные коммитменты на основе Pedersen/IPA, SNARK-доказательства поверх бинарных Merkle и др.) обсуждаются в исследовательских ветках: они могут убирать доверительную установку, но часто проигрывают по скорости/размеру пруфа или усложняют внедрение. В продакшен-цепочке Ethereum ставка сделана на KZG как на уже «обкатанную» технологию.

См. Kzg Commitments, системы доказательств (создать).

«Стебли» и «суффиксы»: как ключи экономят witness

Разделение ключа на 31-байтовый stem + 1-байтовый suffix даёт два эффекта:

• Плотная укладка «ячейек» в одном листе по всем суффиксам 0..255 — меньше уникальных листов в пруфе;

• Шаринг пруф-частей между разными доступами в рамках одного stem (типично для чтений одного аккаунта/его стореджа): повторно используемые куски не дублируются в общем witness блока.

Это — один из главных источников выигрыша над MPT, где ветка для каждого слота часто уникальна на многих уровнях.

См. State Layout.

Stateless-клиенты: что меняется в узлах

В режиме stateless у узла нет локальной БД состояния (или есть неполная/кэш).

Вместо этого:

• блок (или набор транзакций) приходит вместе с witness по всем чтениям/записям состояния;

• узел проверяет корректность каждого доступа (чтение/предыдущее значение, корректность изменения) относительно корня состояния и транзакционной логики;

• после валидации узел может выбросить witness (если не кэширует), продолжая оставаться «тонким» валидатором.

Варианты: weak-statelessness (узлы кэшируют часто используемые узлы дерева/ветви) и full-statelessness (минимальный/нулевой кэш). На практике в Ethereum курс в сторону weak-statelessness как «рабочего» компромисса на первом этапе.

См. Stateless Clients, Portal Network (создать).

Газовая модель и доступ к состоянию

Когда чтения состояния «упакованы» в компактный witness, возникает желание привязать газ-стоимость не только к операциям EVM, но и к реальной цене доступа к состоянию (размеру/сложности свидетеля):

• дороже обходится доступ к «раскиданным» по префиксам ключам;

• дешевле — батчированные/локализованные доступы (много суффиксов у одного stem).

Внедрение Verkle в Ethereum предполагает коррекцию газовых констант и правил доступа к state, чтобы нагрузка отражала реальную цену сети. Это поощряет разработчиков хранить данные компактно и «локально» по ключам.

См. Газовая модель в Ethereum (создать).

Миграция с MPT на Verkle: общая логика

Полная замена «коммитмента состояния» в публичном блокчейне — деликатная операция. Для Ethereum дорожная карта включает:

• Фазу подготовки: тестовые реализации, соответствие спецификации, генерация двух параллельных корней (MPT и Verkle) на стенде;

• Инструменты миграции: преобразование ключей/данных в новую раскладку (stems/suffixes), построение начального Verkle-дерева;

• Проверки и инварианты: совпадение «смыслового» состояния (балансы, сторедж) при переходе;

• Активацию хардфорка: блок, в котором узлы начинают проверять только Verkle-корень в заголовке.

После перехода узлы, не обновившиеся на Verkle, выпадут из консенсуса (несовместимый корень/правила). Поэтому релиз сопровождается долгим тестированием и коммуникацией для операторов узлов.

См. Merkle Patricia Trie, Апгрейды сети Ethereum (создать), Portal Network.

Взаимосвязь с другими направлениями (L2, DA, zk)

• L2/роллапы. Меньшие witness и лучшая модель доступа к состоянию улучшают данные для доказательств и встроенные вызовы L2→L1, особенно в zk-сценариях.

• DA (доступность данных). Verkle не заменяет data availability (см. EIP-4844 и блобы), но «подтягивает» слой состояния к более компактным доказательствам.

• zk-EVM. Более «дружелюбный» к zk формат prуфов снижает накладные расходы на L1-верификацию (меньше публичных входов, меньше Merkle-веток), упрощая zk-путь.

См. Роллапсы — оптимистические и zk: как это работает, Danksharding/блобы (создать), Zk Evm (создать).

Примерный порядок выигрышей (интуитивно)

• На один ключ: вместо длинной Merkle-ветки — постоянного порядка пруф для листа и каждого уровня (обычно 2–3).

• На блок: за счёт батчинга обращений к одним и тем же stems многие части свидетеля не дублируются; итоговый объём укладывается в рамки безопасной p2p-передачи в слоте.

Численные оценки зависят от параметров сети, числа уникальных stems, шаблонов доступа контрактов, но именно снижение witness на порядки и делает stateless-валидацию практичной.

См. Stateless Clients.

Инженерные аспекты и имплементация

Ключевые задачи для клиентов/валидаторов:

• Реализовать KZG-операции (коммитменты/пруфы/верификация) одинаково в основных клиентах (geth, Nethermind, Erigon и др.).

• Встроить кодеки для ключей (stem/suffix), согласовать форматы сериализации узлов Verkle.

• Реализовать хранилище (on-disk) и кэширование горячих узлов, чтобы узлы-производители блоков и полноузловые операторы могли работать эффективно.

• Обновить RPC/трейсеры/инструменты (отладка, архивные узлы, снапшоты).

• Подобрать параметры ширины узлов (256 — де-факто стандарт), конфигурацию «пустых» ячеек и правила pruning.

Безопасность:

• Проверка корректности библиотек эллиптической криптографии (pairings).

• Поддержание/проверка trusted setup (как и в EIP-4844): артефакты церемонии, верификация и общественный аудит.

• Инварианты корректности (например, «нет несогласованности между старым MPT-состоянием и Verkle» в фазе подготовки).

См. Kzg Commitments, Клиенты Ethereum (создать).

Типичные вопросы (FAQ)

Это «ещё один вид Merkle»? Нет. Идея похожа (дерево → корневой коммитмент), но криптографический механизм другой: векторные коммитменты вместо хеш-цепочек. Это даёт более короткие доказательства и позволяет делать широкие узлы.

Что с доверительной установкой? Для KZG нужен trusted setup. Альтернативы без него существуют, но хуже по параметрам/сложности. В Ethereum уже есть опыт безопасной церемонии (для блобов), поэтому экосистема склоняется к reuse этого подхода.

Verkle решит все проблемы масштабирования? Нет. Это «кирпич» в стене масштабирования: уменьшает state-witness, открывает дорогу stateless-валидации, но вопросы доступности данных, MEV, L2-архитектуры и экономики газа остаются отдельными направлениями.

Как это повлияет на разработчиков смарт-контрактов? Косвенно. Изменится базовая стоимость доступа к состоянию (в газовой модели), будут предпочтительны локальные по ключам схемы хранения и батчированные операции. Код на Solidity не «ломается», но паттерны хранения стоит пересмотреть.

Практические рекомендации разработчикам

• Проектируйте ключи «локально». Храните связанные слоты так, чтобы они попадали в один stem и разные suffix — это удешевит witness при батчинге.

• Минимизируйте «разброс» чтений. Старайтесь, чтобы транзакция (или батч) обращались к меньшему числу stems.

• Журналируйте доступы. Профилируйте, какие ключи и в каком паттерне опрашивает ваш контракт, — это поможет оптимизировать газ после перехода.

• Готовьте миграцию. Если вы храните сложные структуры в MPT-ключах, спланируйте «мэппинг» на (stem, suffix) и протестируйте миграционные процедуры.

См. Gas Model, State Layout.

Термины и определения

• Vector commitment (векторный коммитмент): коммитмент к массиву значений с короткими пруфами по индексу. См. Vector Commitment.

• KZG: полиномиальный коммитмент с постоянного размера пруфом; основа для Verkle в Ethereum. См. Kzg Commitments.

• Witness: данные для проверки чтений состояния без локального state. См. Stateless Clients.

• Stem/Suffix: схема разбиения ключа состояния (31+1 байт), уменьшающая дублирование данных в witness. См. State Layout.

Хронология и статус (обобщённо)

См. Network Upgrades.

Связанные и рекомендуемые страницы в нашей Wiki

Базовые: Блокчейн — как устроен распределённый реестр, Merkle Patricia Trie, Kzg Commitments, Stateless Clients, Роллапсы — оптимистические и zk: как это работает, Gas Model, Portal Network

Криптовалюты: Биткоин (BTC) — что это такое и как работает, Ethereum

Персоны/идеи: Виталик Бутерин, Ник Сабо

Перспективные (создать): Векторные коммитменты: практика и свойства, Ключи состояния и layout в Ethereum, Системы доказательств для L1/L2