Хеш-структуры: Patricia, Verkle trees

Ethereum хранит балансы 250 миллионов аккаунтов в одном дереве. Полная нода загружает 150 ГБ данных только чтобы начать работу. А что если можно проверить любой баланс, получив от сети всего 150 байт доказательства? Разница между 4 килобайтами и 150 байтами proof - это разница между тем, может ли проверку запустить только дата-центр или любой смартфон. За этим стоят две структуры данных: одна работает в Ethereum прямо сейчас, другая скоро её заменит.

• **Ethereum State Trie** - Modified Merkle Patricia Trie хранит баланс, nonce и storage каждого из 250+ млн аккаунтов. Три stateRoot в заголовке блока гарантируют целостность всего состояния сети
• **Verkle Trees в Ethereum (EIP-6800)** - переход на новую структуру данных уменьшит witness с 600 КБ до ~150 КБ на блок, открывая путь к stateless клиентам на обычных устройствах
• **DNS и IP-маршрутизация** - Patricia Trie используется в ядре Linux (routing table), BIND (DNS lookup) и практически любой системе, которой нужен быстрый поиск по префиксу

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

• Merkle Trees: the tree of trust
• Elliptic Curves (ECC)

Patricia Trie: radix-дерево со сжатием путей

В уроке о Merkle Trees мы строили бинарное дерево хешей для **списка** транзакций. Но что если нужно хранить не список, а **словарь** - ключ-значение, вроде `адрес → баланс`? Обычное Merkle Tree для этого не подходит: оно не умеет искать по ключу.

**Patricia Trie** (Practical Algorithm to Retrieve Information Coded in Alphanumeric) - это radix trie, оптимизированный для ключ-значение хранения. Его главная идея: **сжатие путей**. Если несколько узлов подряд имеют только одного потомка, они сворачиваются в один узел с общим префиксом.

В контексте блокчейна ключи - это **hex-encoded** строки (адреса, хеши). Patricia Trie работает с **nibble** (полубайт, 4 бита, символ 0-f). 20-байтный Ethereum-адрес превращается в путь из 40 nibble.

**Происхождение названия:** Patricia придумал Дональд Моррисон в 1968 году. Эта структура данных старше интернета на 20 лет. Её используют IP-маршрутизаторы для поиска по таблице маршрутов - та же задача «найти значение по ключу с общими префиксами».

Modified Merkle Patricia Trie: сердце Ethereum

Ethereum объединил две идеи: **Patricia Trie** (поиск по ключу) и **Merkle Tree** (криптографическая верификация). Результат - **Modified Merkle Patricia Trie (MPT)** - структура данных, которая хранит **всё состояние сети**: балансы, nonce, код и storage каждого аккаунта.

MPT имеет **4 типа узлов**: - **Branch Node** - массив из 17 элементов: 16 слотов для каждого nibble (0-f) + слот значения - **Extension Node** - сжатый путь (shared nibbles) + ссылка на следующий узел - **Leaf Node** - оставшийся путь + значение (данные аккаунта) - **Empty Node** - пустая ветка (null)

В **заголовке каждого блока** Ethereum записывает 3 корня MPT: - **stateRoot** - корень дерева состояний всех аккаунтов - **transactionsRoot** - корень дерева транзакций блока - **receiptsRoot** - корень дерева результатов выполнения транзакций

**Проблема MPT:** каждый proof для одного значения включает **все узлы на пути от корня до листа**. Для дерева из 250 млн аккаунтов - это ~40 уровней, каждый branch node весит ~532 байт (17 хешей по 32 байта). Итого proof: **~4 КБ** на одно значение. Для полной верификации блока нужны proof для всех затронутых аккаунтов - **сотни килобайт**.

Verkle Tree: вектор вместо хеша

MPT справляется со своей задачей, но его proof слишком большие: **~4 КБ на одно значение**. Для stateless клиентов, которые должны верифицировать блок без хранения всего state, это означает скачивание **сотен килобайт** дополнительных данных на каждый блок.

**Verkle Tree** (Vector commitment + Merkle = Verkle) - новая структура данных, которая решает эту проблему. Ключевое отличие: вместо хешей для связи узлов используются **vector commitments** - криптографические обязательства на основе полиномов (IPA или KZG).

Два фундаментальных изменения по сравнению с MPT: 1. **Wider branching factor:** 256 детей вместо 16. Дерево «толстое и низкое» вместо «тонкого и высокого» 2. **Vector commitments:** proof для одного ребёнка **не включает** данные о всех 255 остальных. В MPT branch node содержит 16 хешей - и все 16 попадают в proof

Свойство vector commitments: чтобы доказать, что определённый ребёнок принадлежит узлу с 256 детьми, **не нужно** раскрывать данные о 255 остальных. Polynomial commitment позволяет доказать значение в одной точке полинома, не раскрывая весь полином. Это как доказать, что f(5) = 42, не рассказывая, чему равно f(1), f(2) и т.д.

**EIP-6800** описывает переход Ethereum на Verkle Trees. Это часть «The Verge» - третьей фазы дорожной карты Ethereum после The Merge (PoS) и The Surge (sharding). Переход планируется через overlay method: новые данные пишутся в Verkle Tree, старые MPT данные мигрируют постепенно.

State Proofs: путь к stateless клиентам

Зачем вообще нужны маленькие proof? Ответ: **stateless clients** - ноды, которые **не хранят** полное состояние сети, но при этом способны **полностью верифицировать** каждый блок. Для этого каждый блок должен содержать **witness** - все proof для всех значений, к которым обращаются транзакции блока.

Сегодня полная нода Ethereum хранит **~150 ГБ** state (дерево аккаунтов). Это «входной билет» для запуска ноды. Stateless клиент снижает барьер до нуля: ему нужен только текущий блок + witness.

Проблема с текущей MPT: witness для одного блока Ethereum занимает **~600 КБ - 1.5 МБ**. С Verkle Trees этот размер сокращается до **~150 КБ** - на порядок меньше. Это делает stateless верификацию практически возможной даже на мобильных устройствах.

**Portal Network** - проект для распространения state данных и witness через P2P. Он разбивает state на мелкие фрагменты и раздаёт их по DHT (Distributed Hash Table). Лёгкий клиент запрашивает у Portal Network только нужные фрагменты с proof и верифицирует их самостоятельно. Комбинация Verkle Trees + Portal Network - это путь к тысячам лёгких нод на обычных ноутбуках и смартфонах.

**Зачем столько нод?** Чем больше нод верифицируют блоки, тем выше **censorship resistance** сети. Если запуск ноды требует терабайтов хранилища, только дата-центры могут его позволить. Stateless клиенты позволяют **любому** проверять сеть - это фундамент децентрализации.

Ключевые идеи

• **Patricia Trie** - radix-дерево со сжатием путей, обеспечивающее O(log N) lookup по ключу. Основа для key-value хранения в блокчейне
• **Modified Merkle Patricia Trie** - гибрид Patricia Trie и Merkle Tree, используемый в Ethereum для хранения state. 4 типа узлов (branch, extension, leaf, empty), stateRoot в каждом блоке
• **Verkle Tree** - замена MPT с vector commitments вместо хешей. Branching factor 256 вместо 16, proof ~150 байт вместо ~4 КБ - это та самая разница, которая позволит смартфону верифицировать Ethereum
• **State proofs и witness** - данные для stateless верификации блока. Переход MPT→Verkle сокращает witness с ~600 КБ до ~150 КБ, делая реальностью тысячи лёгких нод через Portal Network

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

Хеш-структуры связывают криптографию, структуры данных и архитектуру Ethereum:

• Merkle Trees — Фундамент - бинарное дерево хешей. MPT расширяет идею Merkle Tree для key-value хранения, добавляя поиск по ключу
• Эллиптические кривые (ECC) — Verkle Trees используют polynomial commitments на эллиптических кривых - ту же математику, что лежит в основе цифровых подписей
• KZG Commitments — KZG - один из кандидатов для vector commitments в Verkle Trees (альтернатива - IPA/Pedersen). Та же математика используется в Proto-Danksharding
• EVM — EVM читает и пишет state через MPT. Переход на Verkle Trees изменит газовую модель доступа к storage (EIP-6800 переопределяет стоимость SLOAD/SSTORE)

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

• Если Verkle Trees настолько лучше MPT по размеру proof, почему Ethereum не использовал их с самого начала в 2015 году?
• Stateless клиенты не хранят state - значит ли это, что кто-то всё равно должен его хранить? Как это влияет на децентрализацию?
• Patricia Trie используется в IP-маршрутизации, DNS, блокчейне. Какие ещё задачи с иерархическими ключами (URL, файловые пути, геолокация) можно решить с её помощью?

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

• bc-02-hashing — Hash-based structures are built from cryptographic hash functions; hashing fundamentals are required
• bc-03-merkle — Merkle trees are the foundational hash-based structure; this lesson extends them
• bc-08-commitment — Accumulator and Merkle structures are commitment schemes for sets
• bc-13-kzg — Hash-based structures vs KZG polynomial commitments: hash-based is simple and quantum-safe; KZG has constant proof size
• alg-25-rabin-karp