Merkle-Patricia Trees. Часть 13

Проверка содержимого Merkle-Patricia Tree

Наиболее привлекательной особенностью Merkle-Patricia Tree (MPT) является его способность быстро и эффективно проверять содержимое блока данных благодаря свойствам криптографической хэш-функции, лежащей в его основе. Фундаментальным принципом, лежащим в основе этого процесса проверки, является концепция «доказательств Меркла», которые могут подтвердить существование определенной точки данных в дереве.

Давайте подробнее рассмотрим, как можно проверить содержимое Merkle-Patricia Tree.

Понимание основ: Узлы и маски ветвей

Прежде чем приступить к процессу проверки, необходимо четко понимать, что такое узлы и как они устроены в MPT. Помните, что каждый узел в MPT связан с уникальным хэшем.

В MPT существует три типа узлов:

1. Листовые узлы: Эти узлы содержат фактические данные (например, состояние счета). Каждый узел листа состоит из ключа (путь от корневого узла к листу) и значения (состояние счета).

2. Узлы расширения: Эти узлы по сути являются узлами «быстрого доступа», которые позволяют нам пропустить те части дерева, где есть длинный ряд узлов, каждый из которых имеет только одного ребенка. Они состоят из общей последовательности нибблов и ссылки на другой узел.

3. Узлы ветвей: Эти узлы - настоящая сила, когда речь идет о ветвлении и связывании внутри дерева. Узел ветвления состоит из 17 элементов; 16 из них представляют все возможные значения nibble (от 0 до 15), а последний 17-й элемент хранит значение, если этот узел является концом ключа.

Каждый узел ветвления в MPT также имеет «битовую маску ветвления» - 16-битное двоичное число, отражающее наличие дочерних узлов. Если у узла ветвления есть дочерний узел, соответствующий определенному значению полубайта, то в битовой маске в соответствующей позиции будет стоять '1'.

В MPT у узла ветвления может быть до 16 дочерних узлов, поскольку он основан на 16-битной (4-битной) системе из-за использования шестнадцатеричных ключей.

Таким образом, в данном контексте «битовая маска ветви» - это 16-битное двоичное число, каждый бит которого соответствует существованию (или несуществованию) дочернего узла. Если для данного значения полубайта существует дочерний узел, соответствующий бит в битовой маске ветвления будет равен '1'; если для данного полубайта дочерний узел не существует, бит будет равен '0'.

Процесс верификации: Прохождение через доказательство Меркла

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

Для того, чтобы проверить содержимое дерева, нужно:

1. Начните с корневого узла и хэша всего дерева, которые должны быть известны.

2. Изучите узел, указанный в доказательстве Меркла. Для узлов с ветвями вы будете смотреть на битовую маску ветви и следовать по пути, указанному ключом, который вы пытаетесь доказать. Если битовая маска указывает на дочерний узел, следуйте по этому пути и переходите к следующему узлу в доказательстве. Если дочернего узла нет, это означает, что ключ не существует в дереве.

3. Для узлов листьев и расширений вы будете проверять, соответствует ли пара ключ/значение тому, что вы пытаетесь доказать. Узлы листьев должны содержать точный ключ, который вы ищете. Продлевающие узлы должны соответствовать текущему сегменту ключа, а следующий узел в доказательстве должен быть следующим.

4. Продолжайте двигаться вниз по дереву, повторяя процесс для каждого узла в доказательстве.

5. Процесс завершится, когда вы достигнете узла листа с точным ключом, который вы ищете. Значение в этом узле листа - это данные, которые вы пытались доказать. Если процесс завершается, не найдя соответствия, значит, ключа в дереве нет.

6. Важно отметить, что по мере прохождения доказательства вы также должны вычислять хэш каждого узла и проверять, совпадает ли он с хэшем родительского узла. Это очень важно для гарантии того, что данные не были подделаны.