Merkle Patricia Trie (MPT) в Ethereum — как устроено текущее дерево состояния

Зачем Ethereum нужен Merkle Patricia Trie

Блокчейн блокчейн должен решать три задачи:

• однозначно зафиксировать текущее состояние (балансы, storage контрактов);
• позволить любому узлу проверить корректность состояния, не доверяя другим;
• давать компактные доказательства (proof), что определённый ключ/значение действительно присутствует в состоянии.

Merkle Patricia Trie обеспечивает:

• корневой хеш (root), который включается в заголовок блока;
• возможность построить доказательство включения (Merkle-proof) для любого ключа;
• относительно компактное хранение ключей за счёт префиксного дерева.

Если корень MPT, записанный в заголовке блока, совпадает с результатом локального пересчёта узла, значит:

• все переходы состояний внутри блока были выполнены по правилам;
• состояние, к которому пришёл узел, согласовано с сетью.

Базовая идея: Patricia-trie + Merkle-хеши

Ключи состояния в Ethereum (адреса аккаунтов, слоты storage и т.п.) представляют в виде последовательности полубайтов (nibble) и размещают в префиксном дереве (trie):

• каждый путь от корня до листа соответствует ключу;
• общие префиксы ключей разделяют общие ветки;
• это экономит место по сравнению с «плоским» массивом.

Чтобы получить криптографическую привязку, на вершинах дерева считают Merkle-хеши:

• каждый узел кодируется в RLP-структуру;
• хеш узла (keccak256(RLP(node))) зависит от его детей;
• корень дерева — это хеш верхнего узла, включённый в заголовок блока.

Любое изменение значения по ключу:

• обновляет лист;
• меняет хеши на пути от листа к корню;
• приводит к новому корневому хешу.

Где в Ethereum используется MPT

В каждом блоке Ethereum есть три важных корня MPT:

• stateRoot

Хеш корня дерева состояния:

• аккаунты (EOA и контракты);
• балансы, nonce;
• хеши деревьев storage для контрактов.

• transactionsRoot

Корень дерева транзакций в блоке:

• порядок и состав транзакций;
• используется для доказательств включения конкретной транзакции.

• receiptsRoot

Корень дерева квитанций:

• статусы исполнения (успех/ошибка);
• события (лог-записи);
• потреблённый gas.

Все три корня хранятся в заголовке блока и позволяют узлу:

• проверять, что полученное состояние соответствует описанному в блоке;
• строить и проверять отдельные proofs для транзакций и логов.

Типы узлов в Merkle Patricia Trie

Ethereum использует вариацию Patricia-trie с несколькими типами узлов:

• Branch node (ветвь)

Узел имеет:

• до 16 дочерних указателей (по возможным nibble 0–f);
• опциональное «значение по пути» (value), если ключ заканчивается тут.

• Extension node (расширение пути)

Сжимает последовательность одиночных ветвей:

• хранит префикс пути (несколько nibble подряд);
• содержит ссылку на следующий узел.

• Leaf node (лист)

Представляет окончание пути ключа:

• хранит оставшуюся часть ключа;
• хранит значение (например, RLP-структуру аккаунта или слота storage).

Для кодирования типов узлов и префиксов используется hex-prefix encoding: в отдельном байте помечают, является ли узел листом или extension, а также чётность длины пути.

Подробнее о раскладке ключей состояния см. Размётка ключей состояния в Ethereum.

Как выглядит Merkle-proof в MPT

Доказательство включения ключа в Merkle Patricia Trie — это набор узлов, который позволяет:

• восстановить путь от корня до целевого ключа;
• пересчитать хеши всех узлов по пути;
• убедиться, что конечное значение действительно привязано к объявленному корню.

Процесс верификации:

• узел получает:
  • корень дерева (из заголовка блока);
  • целевой ключ;
  • список RLP-кодированных узлов (witness).
• проходя по trie в соответствии с nibble-ключом:
  • узел декодирует каждый узел;
  • проверяет, что переход по префиксу/индексу корректен;
  • пересчитывает хеш и сверяет с хешем в родителе.
• если итоговый хеш совпадает с корнем, а лист содержит ожидаемое значение — proof принят.

Такие доказательства используются, например, когда:

• light-клиенту нужно подтвердить, что транзакция была в блоке (через transactionsRoot);
• off-chain-сервис доказывает баланс или событие, не загружая всё состояние.

Ограничения и проблемы MPT

Несмотря на надёжность, у Merkle Patricia Trie есть ряд недостатков:

• Крупные пруфы.

При большом state и глубоком дереве количество узлов в доказательстве заметно растёт, особенно если ключи разбросаны по разным веткам.

• Высокая нагрузка на узлы.

Полные узлы должны:

• хранить всё состояние и обслуживать множество запросов;
• поддерживать дисковую БД с большим количеством мелких узлов (RocksDB/LevelDB).

• Сложность stateless-валидации.

Попытка сделать узлы, которые не хранят state и полагаются только на witness:

• упирается в большие объёмы данных по каждому блоку;
• делает p2p-распространение блоков с witness тяжёлым.

Эти ограничения — одна из причин, по которой в roadmap Ethereum появился переход к Verkle tree и stateless-клиентам.

Связь MPT с будущими обновлениями Ethereum

Переход к Verkle tree и сопутствующим механизмам (в том числе KZG-коммитменты) должен:

• уменьшить размер пруфов состояния на порядок;
• сделать stateless-валидацию реалистичной;
• позволить смелее повышать лимит газа и развивать функциональность L1, не «ломая» узлы.

Тем не менее знание Merkle Patricia Trie остаётся важным:

• для понимания текущего формата заголовков и RPC;
• для интеграции с историческими данными и архивными узлами;
• для анализа старых блоков и отладочных инструментов.

Что важно знать разработчику смарт-контрактов

Для обычного разработчика Solidity детали MPT не видны напрямую, но:

• раскладка ключей и pattern’ы доступа к storage влияют:
  • на объём данных, которые придётся включать в пруфы;
  • на нагрузку на узлы и потенциальную стоимость операций в будущих gas-моделях.
• чем «локальнее» данные (группируются по связанным префиксам), тем проще строить компактные proofs и меньше удар по инфраструктуре.

По мере внедрения Verkle часть этих нюансов будет меняться, но общая идея остаётся: структура state-ключей — это не только про удобство контракта, но и про нагрузку на базовый слой.

См. также

• Ethereum (ETH)
• Архитектура Ethereum
• Verkle tree — компактные доказательства состояния
• KZG-коммитменты
• Stateless-клиенты в Ethereum
• Размётка ключей состояния в Ethereum
• Блокчейн
• Хеш-функция