Префиксные деревья в Эфириуме

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

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

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

Радиксные деревья хороши тем, что ключи, которые начинаются одинаково, располагаются в них ближе друг к другу. Кроме того, в отличие от хеш-таблиц, в таком дереве невозможны коллизии ключей. Однако радиксные деревья могут быть довольно неэффективными — например, если вы имеете дело с длинным ключом, не имеющим общего префикса с другими ключами. В этом случае для того, чтобы добраться до значения, вам нужно пройти (и сохранить!) в дереве большое количество узлов, несмотря на то, что никаких других значений по пути к нужному листу нет.

В Эфириуме радиксные деревья улучшены. Чтобы они были криптографически безопасны, ссылка на каждый узел осуществляется по хешу, который в текущих реализациях используется для получения нужных данных из БД leveldb. В такой схеме корневой узел становится криптографическим отпечатком (fingerprint) всей структуры данных (т. е. дерева Меркла). Кроме того, в Эфириуме для повышения эффективности введены разные «типы» узлов. Есть пустой узел (blank node), который просто пуст, и стандартный узел-лист (leaf node), который представляет собой простой список из ключа и значения: [key, value]. Есть также узлы-расширения (extension node). Они тоже являются списками [key, value], но в их случае значение  value является хешем некоторого другого узла. Этот хеш можно использовать для просмотра узла в базе данных. Наконец, есть узлы-ветви (branch node) — списки длиной 17. Первые 16 элементов списка соответствуют 16 возможным шестнадцатеричным знакам в ключе, а последний элемент показывает, существует ли пара [key, value], ключ которой заканчивается узлом-ветвью. Если пока это непонятно, не беспокойтесь — никому сразу не понятно 😀. Чтобы все прояснить, мы рассмотрим несколько примеров.

Еще один важный момент — это специальное шестнадцатеричное кодирование префиксов ключей (hex-prefix, HP). Как уже было сказано, алфавит содержит 16 знаков, так что у каждого узла может быть 16 дочерних узлов. Поскольку есть два типа узлов формата [key, value] (узел-лист и узел-расширение), в Эфириуме используется специальный флаг-терминатор, указывающий, к узлу какого типа относится ключ. Если этот флаг установлен, ключ относится к узлу-листу, а соответствующее значение является значением этого ключа. Если флаг не установлен, то значение является хешем, который используется для просмотра соответствующего узла в базе данных. В HP также кодируются сведения о том, имеет ли ключ четную или нечетную длину. Наконец, запомните, что один шестнадцатеричный знак, или 4-разрядное двоичное число, занимает полбайта и называется «ниббл».

Спецификация HP довольно проста. К ключу присоединяется ниббл, который кодирует состояние флага-терминатора и четность длины ключа: наименьший значимый бит ниббла кодирует четность длины, а следующий за ним — состояние флага. Если ключ имеет четную длину, мы добавляем еще один ниббл со значением 0 для сохранения четности длины (чтобы можно было правильно представлять данные в байтах).

Пока что все мило и красиво, и вы, вероятно, уже читали об этом здесь, здесь, или, если вы достаточно смелы, здесь, но давайте вернемся в реальность и рассмотрим несколько примеров на Python. Я создал на github небольшой репозиторий — можете клонировать его и следовать за мной.

git clone git@github.com:ebuchman/understanding_ethereum_trie

По сути, я просто взял необходимые файлы из репозитория pyethereum (trie.py, utils.py, rlp.py, db.py) и написал на python несколько небольших сценариев-упражнений. Я также добавил в файл trie.py несколько инструкций print, чтобы вам было проще понять, что происходит. Из-за рекурсии вывод может быть немного неряшливым, так что в начале файла trie.py есть флаг, с помощью которого печать можно отключить. Запускайте сценарии с помощью команд вида python exercises/exA.py, где A — номер упражнения. Давайте начнем с упражнения ex1.py.

В файле ex1.py мы инициализируем дерево пустым корнем и добавляем в него один элемент:

state = trie.Trie('triedb', trie.BLANK_ROOT)
state.update('\x01\x01\x02', rlp.encode(['hello']))
print state.root_hash.encode('hex')</code></pre>

Здесь мы используем ключ '\x01\x01\x02' и значение 'hello'. Ключ должен быть строкой (максимум 32 байта, обычно целое число с обратным порядком байтов (big-endian) или адрес), а значение — RLP-кодом произвольных данных. Мы могли бы использовать в качестве ключа что-нибудь проще, например 'dog', но давайте будем реалистичны и используем «сырые» данные. Чтобы увидеть, что происходит «под капотом», можно рассмотреть код в файле trie.py. Поскольку в этом случае мы начали с пустого узла, сценарий trie.py создает новый узел-лист (добавляя к ключу флаг-терминатор), кодирует его в формате RLP и сохраняет в БД пару из хеша и кода [hash, rlp(node)]. Инструкция print должна отобразить хеш, который мы с этого момента можем использовать как корневой хеш префиксного дерева. Взглянем ради полноты описания на HP-кодировку ключа:

k, v = state.root_node
print 'корневой узел:', [k, v]
print 'ключ в кодировке hp:', k.encode('hex')


Вывод сценария ex1.py таков:

root hash 15da97c42b7ed2e1c0c8dab6a6d7e3d9dc0a75580bbc4f1f29c33996d1415dcc
корневой узел: [' \x01\x01\x02', '\xc6\x85hello']
ключ в кодировке hp: 20010102

Обратите внимание, что последние 6 нибблов представляют ключ, который мы использовали, 010102, а первые два описывают кодировку HP. Первый ниббл указывает, что это узел-терминатор (в двоичном формате ниббл равен 10, т. е. установлен второй наименее значимый бит), и, поскольку ключ имеет четную длину (наименьший значимый бит равен 0), мы добавляем второй, нулевой ниббл.

Давайте перейдем к упражнению ex2.py и инициализируем дерево указанным выше хешем:

state = trie.Trie('triedb', '15da97c42b7ed2e1c0c8dab6a6d7e3d9dc0a75580bbc4f1f29c33996d1415dcc'.decode('hex'))
print state.root_node

Инструкция print должна вывести пару [key, value], которую мы сохранили ранее. Отлично. Давайте добавим больше элементов. Попробуем сделать это несколькими разными способами, чтобы получить представление о возможностях. Мы будем использовать несколько файлов ex2, каждый раз инициализируя дерево оригинальным хешем. Давайте сначала создадим элемент с тем же ключом, который мы уже использовали, но другим значением. Поскольку у нового значения будет новый хеш, мы получим два дерева, на которые будут ссылаться два разных хеша, оба начинающиеся одним ключом.

state.update('\x01\x01\x02', rlp.encode(['hellothere']))
print state.root_hash.encode('hex')
print state.root_node

Вывод сценария ex2.py таков:

05e13d8be09601998499c89846ec5f3101a1ca09373a5f0b74021261af85d396
[‘ \x01\x01\x02’, ‘\xcb\x8ahellothere’]

Это не так уж и интересно, но здорово то, что мы не перезаписали исходный элемент и можем получать доступ к обоим элементам, используя их хеши. Давайте теперь добавим элемент с тем же ключом, но другим конечным нибблом (ex2b.py):

state.update('\x01\x01\x03', rlp.encode(['hellothere']))
print 'корневой хеш:', state.root_hash.encode('hex')
k, v = state.root_node
print 'корневой узел:', [k, v]
print 'ключ в кодировке hp:', k.encode('hex')

Инструкция print 'корневой узел' должна возвратить что-то невразумительное, потому что она возвращает нам узел [key, value], где key — это общий префикс наших двух ключей ([0,1,0,1,0]), закодированный с в HP с добавлением флага и сведений о нечетной длине ключа, а value — хеш RLP-кода узла, который нас интересует. Иначе говоря, мы имеем дело с узлом-расширением. Мы можем использовать хеш для просмотра узла в базе данных:

print state._get_node_type(state.root_node) == trie.NODE_TYPE_EXTENSION
common_prefix_key, node_hash = state.root_node
print state._decode_to_node(node_hash)
print state._get_node_type(state._decode_to_node(node_hash)) == trie.NODE_TYPE_BRANCH

А вот вывод сценария ex2b.py:

корневой хеш: b5e187f15f1a250e51a78561e29ccfc0a7f48e06d19ce02f98dd61159e81f71d
корневой узел: ['\x10\x10\x10', '"\x01\xab\x83u\x15o\'\xf7T-h\xde\x94K/\xba\xa3[\x83l\x94\xe7\xb3\x8a\xcf\n\nt\xbb\xef\xd9']
ключ в кодировке hp: 101010
True
['', '', [' ', '\xc6\x85hello'], [' ', '\xcb\x8ahellothere'], '', '', '', '', '', '', '', '', '', '', '', '', '']
True

Этот результат довольно интересен. Мы видим узел-ветвь, список с 17 записями. Обратите внимание на различие в оригинальных ключах: оба они начинаются как [0,1,0,1,0], но один заканчивается на 2, тогда как другой — на 3. Таким образом, когда мы добавляем новый элемент (ключ, заканчивающийся на 3), узел, который ранее содержал ключ, заканчивающийся на 2, заменяется узлом-ветвью, ключом которого является общий префикс двух ключей в кодировке HP. Узел-ветвь хранится как узел-расширение [key, value], где key — общий префикс в кодировке HP, а value — хеш узла, который можно использовать для просмотра узла-ветви, на который он указывает. Элементом по индексу 2 этого узла-ветви является оригинальный узел с ключом, заканчивающимся на 2 (‘hello’), а элементом с индексом 3 — новый узел (‘hellothere’). Поскольку оба ключа лишь на один ниббл больше, чем ключ самого узла-ветви, конечный ниббл кодируется неявно по позиции узлов в узле-ветви. А поскольку это исчерпывает все знаки в ключах, эти узлы хранятся с пустыми ключами в узле-ветви.

Как видите, я добавил пару инструкций print, чтобы показать, что эти узлы на самом деле являются узлом-расширением и узлом-ветвью. Имейте также в виду, что есть общее правило сохранения узлов в узлах-ветвях: если RLP-код узла меньше 32 байтов, узел сохраняется непосредственно в элементе узла-ветви. Если RLP-код больше 32, в узле-ветви сохраняется хеш узла, который можно использовать для просмотра узла в базе данных.

Думаю, вам понравилось. Давайте проделаем это еще раз с ключом, равным первым нескольким нибблам нашего оригинального ключа (ex2c.py):

state.update('\x01\x01', rlp.encode(['hellothere']))

Это снова приводит к созданию узла-ветви, но в данном случае происходит кое-что другое. Узел-ветвь соответствует ключу ‘\x01\x01’, но у нас также есть значение с этим ключом (‘hellothere’). Следовательно, значение помещается в последнюю (17-ю) позицию узла-ветви. Другой элемент, с ключом ‘\x01\x01\x02’, помещается в позицию, соответствующую следующему нибблу в его ключе, в данном случае 0. Поскольку его ключ не был полностью исчерпан, мы сохраняем оставшиеся нибблы (в данном случае просто ‘2’) в позиции ключа узла. Вывод сценария таков:

[['2', '\xc6\x85hello'], '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '\xcb\x8ahellothere']

Давайте разберем последний вариант упражнения 2 (ex2d.py). В нем мы добавляем новый элемент с ключом, который идентичен оригинальному ключу, но имеет два дополнительных ниббла:

state.update('\x01\x01\x02\x57', rlp.encode(['hellothere']))

Случилось противоположное тому, что мы только что видели! Значение оригинального элемента сохранилось в конечной позиции узла-ветви, где ключом узла-ветви является ключ этого значения (‘\x01\x01\x02’). Второй элемент сохранился в позиции следующего ниббла (5) с ключом, равным количеству оставшихся нибблов (всего 7):

['', '', '', '', '', ['7', '\xcb\x8ahellothere'], '', '', '', '', '', '', '', '', '', '', '\xc6\x85hello']

Та-да! Попробуйте поэкспериментировать с кодом немного, чтобы полностью понять, что происходит. Узлы хранятся в БД согласно хешам их RLP-кодов. При извлечении узла ключи используются для прохода пути через последующие узлы (что может включать дополнительные просмотры хешей) для достижения последнего значения. Ради простоты мы использовали в каждом из этих примеров лишь два элемента, но и этого оказалось достаточно, чтобы обнажить базовые механизмы работы дерева. Мы могли бы добавить больше элементов для заполнения узла-ветви, но, поскольку мы уже понимаем, как все работает, давайте перейдем к более сложным примерам. В упражнении 3 мы добавим третий элемент, имеющий общий префикс со вторым. Этот пример чуть больше, но его результат впечатляет (ex3.py):

state = trie.Trie('triedb', '15da97c42b7ed2e1c0c8dab6a6d7e3d9dc0a75580bbc4f1f29c33996d1415dcc'.decode('hex'))
print state.root_hash.encode('hex')
print state.root_node
print ''
state.update('\x01\x01\x02\x55', rlp.encode(['hellothere']))
print 'корневой хеш:', state.root_hash.encode('hex')
print 'корневой узел:', state.root_node
print 'узел-ветвь, на который он указывает:', state._decode_to_node(state.root_node[1])
print ''

Пока что ничего нового: мы инициализируем дерево из исходного хеша, добавляем новый узел с ключом '\x01\x01\x02\x55'. Код создает узел-ветвь и указывает на него с помощью хеша. Все это мы знаем, а теперь самое веселое:

state.update('\x01\x01\x02\x57', rlp.encode(['jimbojones']))
print 'корневой хеш:', state.root_hash.encode('hex')
print 'корневой узел:', state.root_node
branch_node = state._decode_to_node(state.root_node[1])
print 'узел-ветвь, на который он указывает:', branch_node

Мы делаем то же самое: добавляем новый узел, в этот раз с ключом '\x01\x01\x02\x57' и значением 'jimbojones'. Но теперь в узле-ветви там, где был узел со значением 'hellothere' (т. е. по индексу 5), находится старый хеш! Ну а что мы делаем с хешами в радиксных деревьях? Разумеется, мы используем их, чтобы просмотреть больше узлов!

next_hash = branch_node[5]
print 'хеш, сохраненный в узле-ветви:', next_hash.encode('hex')
print 'узел-ветвь, на который он указывает:', state._decode_to_node(next_hash)

И вывод:

корневой хеш: 17fe8af9c6e73de00ed5fd45d07e88b0c852da5dd4ee43870a26c39fc0ec6fb3
корневой узел: ['\x00\x01\x01\x02', '\r\xca6X\xe5T\xd0\xbd\xf6\xd7\x19@\xd1E\t\x8ehW\x03\x8a\xbd\xa3\xb2\x92!\xae{2\x1bp\x06\xbb']
узел-ветвь, на который он указывает: ['', '', '', '', '', ['5', '\xcb\x8ahellothere'], '', '', '', '', '', '', '', '', '', '', '\xc6\x85hello']

корневой хеш: fcb2e3098029e816b04d99d7e1bba22d7b77336f9fe8604f2adfb04bcf04a727
корневой узел: ['\x00\x01\x01\x02', '\xd5/\xaf\x1f\xdeO!u>&3h_+\xac?\xf1\xf3*\xb7)3\xec\xe9\xd5\x9f2\xcaoc\x95m']
узел-ветвь, на который он указывает: ['', '', '', '', '', '\x00&\x15\xb7\xc4\x05\xf6\xf3F2\x9a(N\x8f\xb2H\xe75\xcf\xfa\x89C-\xab\xa2\x9eV\xe4\x14\xdfl0', '', '', '', '', '', '', '', '', '', '', '\xc6\x85hello']
хеш, сохраненный в узле-ветви: 002615b7c405f6f346329a284e8fb248e735cffa89432daba29e56e414df6c30
узел-ветвь, на который он указывает: ['', '', '', '', '', [' ', '\xcb\x8ahellothere'], '', [' ', '\xcb\x8ajimbojones'], '', '', '', '', '', '', '', '', '']

Та-да! Таким образом, этот хеш, который соответствует ключу [0,1,0,1,0,2,5], указывает на другой узел-ветвь, содержащий в соответствующих позициях наши значения 'hellothere' и 'jimbojones'. Попробуйте подобавлять новые записи, а имено попытайтесь заполнить финальный узел-ветвь, включая его последнюю позицию.

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

state = trie.Trie('triedb', 'b5e187f15f1a250e51a78561e29ccfc0a7f48e06d19ce02f98dd61159e81f71d'.decode('hex'))
print 'использование корневого хеша из ex2b'
print rlp.decode(state.get('\x01\x01\x03'))
print ''
state = trie.Trie('triedb', 'fcb2e3098029e816b04d99d7e1bba22d7b77336f9fe8604f2adfb04bcf04a727'.decode('hex'))
print 'использование корневого хеша из ex3'
print rlp.decode(state.get('\x01\x01\x02'))
print rlp.decode(state.get('\x01\x01\x02\x55'))
print rlp.decode(state.get('\x01\x01\x02\x57'))

Вы должны увидеть значения, которые мы сохранили в предыдущих упражнениях.

Это все! Думаю, теперь вас интересует, как все это на самом деле используется в Эфириуме. В моем репозитории нет ответов, но если вы клонируете официальный репозиторий pyethereum и выполните команду grep -r 'Trie' . , вы получите некоторые намеки. Мы обнаружили, что радиксное дерево используется в двух ключевых местах: для кодирования списков транзакций в блоке и для кодирования состояния блока. В случае транзакций ключами являются целые числа с обратным порядком байтов (big-endian), которые представляют количество транзакций в текущем блоке. В случае дерева состояния ключами являются эфириум-адреса. Для любого полного узла важно поддерживать дерево состояния, поскольку его необходимо использовать для проверки новых транзакций (потому что необходимо ссылаться на данные контракта). Однако, в отличие от Биткойна, хранить старые траназкции ради проверки не требуется, поскольку имеется БД состояний. В общем, с технической точки зрения хранить префиксные деревья транзакций не требуется. Конечно, если никто не будет хранить их, то никто никогда не сможет проверить состояния, начиная с генезис-блока до текущего момента, так что все же имеет смысл хранить их.

Вот так. Теперь вы знаете, что такое радиксное дерево в Эфириуме. Now go forth, and trie it!

4 июня 2014 г.

Understanding the ethereum trie