Merkle Patricia Trie

Merkle Patricia Trie — это структура данных, объединяющая свойства криптографического дерева Меркла и префиксного дерева (Patricia trie), используемая для эффективного хранения и верификации пар «ключ-значение» в распределённых системах. Она обеспечивает детерминированное построение корневого хеша (корня Меркла), который однозначно представляет всё состояние хранилища, и позволяет проверять наличие и целостность отдельных записей без загрузки полного набора данных. Наиболее широкое применение получила в реализации Ethereum (включая его ответвления, такие как Polygon и BNB Smart Chain) для хранения состояния аккаунтов, хранилищ смарт-контрактов и транзакционных данных.

История и предпосылки

Идея Patricia trie была предложена Дональдом Моррисоном в 1968 году как оптимизация обычного префиксного дерева (trie) для сжатия длинных путей. В 1979 году Ральф Меркл разработал концепцию криптографического дерева (дерево Меркла), позволяющего доказывать принадлежность элемента набору данных с помощью логарифмического числа хешей.

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

• Позволяла бы быстро обновлять состояние (добавлять, изменять, удалять записи).
• Гарантировала бы криптографическую целостность всего состояния через один корневой хеш.
• Обеспечивала бы эффективную верификацию отдельных записей (доказательства Меркла).

В 2013–2014 годах команда Ethereum под руководством Виталика Бутерина адаптировала Patricia trie, добавив к нему криптографическое хеширование каждого узла, и назвала результат Merkle Patricia Trie. Этот выбор был обусловлен необходимостью хранить произвольные бинарные ключи (адреса аккаунтов, хеши транзакций) и обеспечивать детерминизм — одинаковый порядок вставки всегда даёт одинаковый корневой хеш.

Устройство

Merkle Patricia Trie представляет собой дерево, в котором каждый узел имеет уникальный идентификатор — хеш своего содержимого. Ключи кодируются в шестнадцатеричной системе (hex-кодирование), что позволяет разбивать их на нибблы (полубайты). В зависимости от структуры ключа и количества ветвлений, узел может быть одного из четырёх типов.

Типы узлов

1. Пустой узел (NULL) — обозначает отсутствие данных. Хеш пустого узла — это хеш пустой строки (в Ethereum — keccak256("")).
2. Листовой узел (Leaf node) — содержит:

• Флаг окончания пути (обычно кодируется добавлением специального префикса или бита).
• Оставшуюся часть ключа (оставшиеся нибблы).
• Значение (value), которое хранится по данному ключу.

1. Расширяющий узел (Extension node) — содержит:

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

1. Ветвящий узел (Branch node) — содержит:

• Массив из 16 ссылок (по одной на каждый возможный ниббл: 0–F).
• Опциональное значение (если ключ заканчивается точно на этом узле).

Принцип работы

1. Кодирование ключа: Ключ (например, адрес аккаунта) преобразуется в последовательность нибблов. Например, ключ 0xABCD даёт нибблы [A, B, C, D].
2. Вставка: Для вставки пары (ключ, значение) алгоритм проходит по дереву, сравнивая нибблы ключа с путями в узлах:

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

1. Обновление хешей: После каждого изменения (вставка, удаление, изменение значения) рекурсивно пересчитываются хеши всех затронутых узлов вплоть до корня. Это гарантирует, что новый корневой хеш отражает все внесённые изменения.
2. Доказательство Меркла: Чтобы доказать, что определённый ключ существует в дереве и имеет конкретное значение, достаточно предоставить путь от корня до листового узла, включая хеши всех «родственных» узлов на каждом уровне. Размер такого доказательства растёт логарифмически от общего числа записей.

Применение в Ethereum

В Ethereum используется три отдельных Merkle Patricia Trie:

State Trie (Дерево состояния)

Хранит глобальное состояние всех аккаунтов. Ключом является 20-байтовый адрес аккаунта, а значением — RLP-кодированная структура, содержащая nonce, баланс, корень storage trie и хеш кода контракта. Корень state trie (stateRoot) включается в заголовок каждого блока, обеспечивая криптографическую фиксацию всего состояния сети на момент блока.

Storage Trie (Дерево хранилища)

Каждый смарт-контракт имеет своё собственное дерево для хранения своих переменных состояния. Ключом является 256-битный слот хранения (определённый в коде контракта), а значением — 256-битное значение. Корень storage trie хранится в структуре аккаунта внутри state trie.

Transaction Trie (Дерево транзакций)

Хранит все транзакции, включённые в блок. Ключом является индекс транзакции в блоке (кодированный как RLP), а значением — сама транзакция. Корень этого дерева (transactionsRoot) включается в заголовок блока. Это позволяет быстро проверять, была ли конкретная транзакция включена в блок.

Преимущества и недостатки

Преимущества

• Детерминизм: Одинаковый набор данных всегда даёт одинаковый корневой хеш, что критично для консенсуса в блокчейне.
• Эффективность обновления: Вставка, удаление и изменение выполняются за O(log N) операций, где N — количество записей.
• Компактность: Расширяющие узлы сжимают длинные цепочки, что снижает размер дерева по сравнению с обычным trie.
• Криптографическая верификация: Позволяет строить доказательства Меркла для отдельных записей.

Недостатки

• Сложность реализации: Алгоритмы вставки и удаления требуют тщательной обработки граничных случаев (расщепление узлов, преобразование типов).
• Высокое потребление памяти: Каждый узел хранит хеши и ссылки, что может приводить к значительному объёму данных в оперативной памяти при работе с большими деревьями.
• Чувствительность к порядку: Хотя дерево детерминировано, разные порядки вставки могут приводить к разной внутренней структуре (но к одинаковому корневому хешу). В Ethereum порядок вставки строго определён протоколом.

Альтернативы и развитие

В более современных блокчейн-проектах (например, Solana, Diem) для хранения состояния часто используются другие структуры данных, такие как:

• Verkle Trie — использует векторные обязательства (vector commitments), позволяющие строить доказательства меньшего размера.
• Sparse Merkle Trie — оптимизирована для разреженных наборов данных и часто применяется в системах с нулевым разглашением (zero-knowledge proofs).
• Хеш-таблицы с деревьями Меркла — используют хеш-таблицы для быстрого доступа и отдельное дерево Меркла для верификации.

Тем не менее, Merkle Patricia Trie остаётся стандартом де-факто для платформ, совместимых с Ethereum (EVM-совместимые сети), и продолжает использоваться в Ethereum 2.0 (после перехода на Proof-of-Stake) для хранения состояния.

Интересные факты

• Размер state trie в Ethereum по состоянию на 2024 год составляет несколько сотен гигабайт, а количество узлов превышает 1 миллиард.
• В ранних версиях Ethereum использовалось простое Patricia trie (без хеширования), но оно было заменено на Merkle Patricia Trie для обеспечения криптографической верификации.
• Алгоритм кодирования пути (hex-prefix encoding) используется для различения листовых и расширяющих узлов, а также для обозначения чётности длины пути.

Источники

• Wood, G. (2014). Ethereum: A Secure Decentralised Generalised Transaction Ledger (Yellow Paper).
• Buterin, V. (2013). Ethereum Whitepaper.
• Morrison, D. R. (1968). PATRICIA — Practical Algorithm To Retrieve Information Coded in Alphanumeric.
• Merkle, R. C. (1980). Protocols for Public Key Cryptosystems.
• Документация Ethereum Foundation: «Ethereum Patricia Tree».