Состояние и trie: один хеш для всего мира
EVM вычисляет над хранилищем — но где это хранилище на самом деле живёт, и как сеть незнакомцев соглашается, что оно побайтово идентично, не пересылая друг другу гигабайты? Эта глава выводит дерево Меркла-Патриции: структуру, которая сжимает всё мировое состояние в один 32-байтовый корень, который можно дёшево обновлять и против которого можно доказывать.
- EVM и хранилище
- хеширование (keccak256)
Глава 2 оставила нить незавершённой. storage в EVM — единственное место, где переживают данные контракта — было, как мы сказали, «зафиксировано в дереве состояния и хранится на диске каждого узла». Но что такое это trie и почему именно такая форма? Настоящая проблема под этим — суровая: сотни тысяч машин, которыми управляют незнакомцы, каждая хранит всё состояние Ethereum — каждый баланс аккаунта, nonce, контракт и слот хранилища — и они должны соглашаться, что оно в точности одинаково, блок за блоком. Этого нельзя добиться, пересылая друг другу гигабайты по почте и сравнивая их. Эта глава выводит структуру, которая делает это возможным — так же, как мы выводим всё остальное: начинаем с самой тупой вещи, которая могла бы сработать, и чиним то, что ломается.
Проблема: дёшево доказать, что два мира идентичны
мировое состояние Полное отображение от каждого адреса аккаунта к его состоянию — баланс, nonce, а для контрактов ещё хеш кода и хранилище. Именно это преобразует исполнение блока; каждый полный узел хранит всё это. огромно и постоянно меняется. Двум узлам нужен способ убедиться, что они хранят идентичное состояние, не пересылая его целиком — и, отдельно, способ доказать один факт («аккаунт 0xa7… держит 12 ETH») тому, у кого состояния нет вовсе. Обе потребности указывают на один и тот же инструмент: криптографический отпечаток. Хешируем всё состояние в одно 32-байтовое число, и если числа двух узлов совпадают, совпадают и их состояния; измените хоть один вей где угодно — и число перевернётся.
→ Шаг 2: заработаем структуру, исправляя по одному недостатку за раз.
От простой карты к дереву Меркла-Патриции
Смотрите, как структура строит сама себя. Каждый этап ниже чинит недостаток предыдущего — у простой карты нет вообще никакого обязательства; хеширование её в одно число фиксирует, но не позволяет ни доказывать, ни дёшево обновлять; хеширование в дереве означает, что изменение перехеширует лишь один путь и любой лист можно доказать его веткой; превращение самого ключа в маршрут вниз по дереву делает форму канонической (все строят идентичное дерево); а схлопывание длинных неветвящихся участков убирает лишние узлы. В итоге получается дерево Меркла-Патриции Структура состояния Ethereum: радиксное дерево, ключом которого служит путь через данные, где каждый узел также фиксирует хеш своих потомков (Меркл), а неветвящиеся пути сжаты (Патриция). Даёт единый корневой хеш, обновления за O(log n) и компактные доказательства включения. (Merkle-Patricia trie).
Выводим дерево Меркла-Патриции
Стоит назвать два свойства, потому что на них опирается всё дальнейшее. корень Меркла Хеш на вершине дерева хешей, где каждый узел хеширует своих потомков. Поскольку хеш распространяется вверх, единственный корень фиксирует каждый лист под собой — а короткий список хешей-соседей (ветка) доказывает любой один лист. фиксирует каждый лист через цепочку хешей потомков, так что один корень закрепляет весь набор данных. И поскольку ключ определяет путь, дерево каноническое: имея одни и те же аккаунты, каждый клиент независимо строит побайтово одинаковый trie и, значит, одинаковый корень. Никакого выбора порядка, никакой неоднозначности.
→ Шаг 3: три типа узлов.
Leaf, extension, branch — и почему их ровно три
Ключ сначала хешируется, а затем читается по 4 бита за раз. Каждый 4-битный кусок — это ниббл Половина байта — одна шестнадцатеричная цифра, 0–f. Ключи trie обходятся по одному ниббл за раз, так что в каждой точке ветвления есть шестнадцать возможных направлений — по одному на значение ниббла. (nibble), так что в любой точке ветвления есть шестнадцать возможных направлений. Это и задаёт нужные типы узлов: ветвящийся узел Узел с 17 слотами — по одному указателю на потомка на каждый ниббл (0–f) плюс слот значения. Используется там, где пути действительно расходятся. (branch node) для мест, где пути реально расходятся, узел-расширение Узел, хранящий общую последовательность ниббл и один указатель на потомка — сжатие по Патриции, схлопывающее длинный неветвящийся участок в один узел. (extension node), чтобы схлопнуть общий участок ниббл в один узел, и листовой узел Узел, хранящий оставшиеся ниббл ключа и его значение — конец пути. (leaf node), чтобы хранить хвост ключа и его значение.
Тот факт, что «каждый узел также хранит хеши своих потомков» — это тихая, но несущая деталь: именно она сплавляет обычное маршрутизирующее дерево (Патриция) с деревом хешей (Меркл). Маршрут делает поиск детерминированным; хеши делают всю конструкцию заметно защищённой от подделки вплоть до корня.
- 1 делим на 4-битные куски; каждый ниббл выбирает одно из 16 направлений ветвления
- 2 сначала хешируем ключ — это равномерно распределяет ключи, так что trie остаётся неглубоким и сбалансированным
→ Шаг 4: меняем один баланс и смотрим, как это распространяется.
Один баланс меняется; перехешируется только его путь
Вот и вознаграждение за всю эту структуру. Измените баланс одного аккаунта — и вы не трогаете остальную часть trie. Вы переписываете лист, а затем идёте вверх по его пути, перехешируя каждого родителя — потому что хеш узла зависит от его потомков, изменившийся потомок вынуждает новый хеш вплоть до самого корня. Каждый узел, не лежащий на этом пути, сохраняет свой старый хеш нетронутым и просто переиспользуется. Пролистайте это:
0xa7c1→- 01 / 06
An account is a path
Alice's key 0xa7c1 isn't stored in a row somewhere — it's a route. Read it one nibble at a time, a → 7 → c → 1, and each nibble picks the next turn down the tree until you reach her leaf.
- 02 / 06
Three kinds of node
The route is built from just three parts. A branch is a 16-way fork. An extension is a shortcut that swallows a run of shared nibbles. A leaf is the end of the road, holding the value.
- 03 / 06
Change one balance
Alice spends some ETH: 12.0 → 99.0. Only her leaf is touched — its bytes change, so its hash must change. Nothing else in the tree has moved yet.
- 04 / 06
Re-hash, bottom-up
A node's hash is built from its children's hashes. So the new leaf hash forces its parent to re-hash, which forces its parent… a wave of recomputation travels straight up Alice's path — and only her path.
- 05 / 06
A brand-new state root
The wave reaches the top. The root node emits a fresh 32-byte hash: the new state root. Every node on Earth, fed the same edit, computes this exact same number.
- 06 / 06
It lands in the header
That root drops into the block header's stateRoot slot. One changed balance has changed the block's identity — this is where state and consensus are welded together.
Так что обновление имеет сложность O(глубины), а не O(размера состояния): горстка хешей, а не миллионы. Тот же самый путь — лист плюс хеши-соседи по дороге — это в точности доказательство Меркла Лист плюс хеши-соседи на пути к корню. Любой, у кого есть только корень, может пересчитать всё вверх и подтвердить, что лист включён — доказывая один аккаунт без остального состояния. (Merkle proof): передайте его тому, у кого есть только корень, и он сможет проверить этот один аккаунт, без остального состояния. Дешёвые обновления и компактные доказательства — это одно и то же свойство, прочитанное в двух направлениях.
→ Шаг 5: куда на самом деле уходит корень.
Корень состояния в заголовке блока
Весь смысл сжатия состояния в один хеш — в том, что теперь с этим можно сделать. корень состояния Хеш корневого узла дерева состояния — единое 32-байтовое обязательство по всему мировому состоянию после исполнения блока. Хранится в заголовке блока рядом с корнями транзакций и квитанций. (state root) становится одним полем в заголовке блока, рядом с корнем транзакций и корнем квитанций. Исполните блок, вычислите новый корень состояния и вложите его туда. Теперь согласие по заголовку идентично согласию по всему мировому состоянию — несколько сотен байт замещают собой память всей цепочки. И поскольку каждый заголовок также называет хеш своего родителя, изменение любого прошлого состояния изменило бы корень того блока, его хеш и каждый хеш после него.