Архив

Monthly Archives: Декабрь 2015

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

Блок в блокчейне Эфириума состоит из заголовка, списка транзакций и списка анкл-блоков. Заголовок включает хеш корневой транзакции, который используется для проверки списка транзакций. По мере распространения транзакций между пирами в виде простого списка их нужно собирать в специальную структуру данных — префиксное дерево (trie) — для вычисления корневого хеша. Имейте в виду, что эта структура данных нужна лишь для проверки блоков (и, следовательно, для их майнинга), и с технической точки зрения после проверки блока ее можно отбросить. Предполагается, однако, что списки транзакций хранятся локально в префиксном дереве и для отправки клиентам, которые запрашивают блокчейн, сериализуются в списки. После этого клиент реконструирует для каждого блока его префиксное дерево со списком транзакций, чтобы проверить корневой хеш. Для кодирования всех элементов в дереве в Эфириуме используется система RLP собственной разработки.

Префиксное дерево также известно как радиксное дерево (?) (radix tree). В Эфириуме в его реализацию ради повышения эффективности была внесена пара изменений. В обычном радиксном дереве ключом является фактический путь через дерево к соответствующему значению. Иначе говоря, начиная с корневого узла дерева каждый знак ключа говорит вам, какой дочерний узел выбирать, чтобы добраться до нужного значения, а сами значения хранятся в «листовых узлах», которыми завершается каждая «ветвь» дерева. Если алфавит, из которого создаются ключи, содержит N знаков, то каждый узел в дереве может иметь до N дочерних узлов, а максимальная длина ключа равна максимальной длине ветви дерева.

Read More