Merkle-Patricia Trees. Часть 5

Новая неделя и новые душные посты про Патрицию!

Понимаю, многим интересны будут, скорее, посты про что-то базовое из Solidity, но я хотел бы на канале порой дальше двигаться с "мясными" темами, которые сложно найти где-либо еще. Поэтому недели на две мы еще продолжим говорить про деревья Меркл-Патриция, захватывая темы верификации и уязвимостей. Итак, продолжим.

На прошлой неделе мы поняли, что Patricia tree (также известное как «Радиксное дерево» или «Trie») - это особый тип структуры данных, которая используется для хранения набора строк. Строки разбиваются на отдельные символы, и дерево строится путем создания пути для каждой строки, где каждый символ образует узел на пути. Patricia tree особенно полезны для наборов данных, в которых префиксы строк значительно пересекаются.

В дереве Меркла-Патриция Ethereum каждый счет с сопутствующей информацией (такой как баланс счета, nonce, код контракта, если это контрактный счет, и хранилище) образует строку, которую необходимо сохранить.

Основными компонентами дерева Патриция являются:

1. Узел: Каждый узел в дереве представляет собой символ строки. В контексте Ethereum узел может быть частью адреса счета или другой информации о счете.

2. Грани: это связь между узлами. Ребро соединяет узел с последующим узлом.

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

4. Путь/префикс: Это последовательность символов (ключей) от корня дерева до определенного узла.

5. Корневой узел: Это начальная точка дерева. Все пути в дереве начинаются от корневого узла.

6. Листовой узел: Это конечные точки каждого пути. В Ethereum узел листьев обычно содержит состояние счета.

Как работает древо?

В Patricia tree каждый путь от корня до листового узла представляет собой строку из набора строк, которые хранит дерево. Символы строки являются ключами узлов, расположенных вдоль пути.

Для того, чтобы найти определенную строку в дереве, вы начинаете с корня и следуете по пути, который соответствует символам строки.

В Ethereum для хранения состояния используется модифицированная версия дерева Патриция, называемая «деревом Меркл-Патриция». В этом случае каждый путь от корня до узла листа представляет собой адрес аккаунта, а узел листа содержит состояние этого аккаунта.

А дальше переходим к совсем сложным объяснениям...

#merkle #patricia