Дерево Меркла-Патрисии

Состояние Ethereum (совокупность всех аккаунтов, балансов и смарт-контрактов) кодируется в специальную версию структуры данных, известной в информатике как дерево Меркла. Эта структура полезна для многих приложений в криптографии, поскольку она создает проверяемую связь между всеми отдельными фрагментами данных, объединенными в дереве, в результате чего получается одно корневое значение, которое можно использовать для доказательства утверждений о данных.

Структура данных Ethereum — это «модифицированное дерево Меркла-Патрисии», названное так потому, что оно заимствует некоторые функции PATRICIA (практического алгоритма для извлечения информации, закодированной в буквенно-цифровом виде), а также потому, что оно предназначено для эффективного извлечения (retrieval) элементов, составляющих состояние Ethereum.

Дерево Меркла-Патрисии является детерминированным и криптографически верифицируемым: единственный способ сгенерировать корень состояния — это вычислить его из каждой отдельной части состояния, а идентичность двух состояний можно легко доказать, сравнив корневой хэш и хэши, которые к нему привели (доказательство Меркла). И наоборот, невозможно создать два разных состояния с одним и тем же корневым хэшем, и любая попытка изменить состояние с другими значениями приведет к другому корневому хэшу. Теоретически, эта структура обеспечивает «святой Грааль» эффективности O(log(n)) для вставок, поиска и удалений.

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

Предварительные условия

Чтобы лучше понять эту страницу, было бы полезно иметь базовые знания о хэшах (opens in a new tab), деревьях Меркла (opens in a new tab), префиксных деревьях (tries) (opens in a new tab) и сериализации (opens in a new tab). Эта статья начинается с описания базового radix-дерева (opens in a new tab), а затем постепенно вводит модификации, необходимые для более оптимизированной структуры данных Ethereum.

Базовые radix-деревья

В базовом radix-дереве каждый узел выглядит следующим образом:

1    [i_0, i_1 ... i_n, value]

Где i_0 ... i_n представляют собой символы алфавита (часто двоичные или шестнадцатеричные), value — это конечное значение в узле, а значения в i_0, i_1 ... ячейках i_n — это либо NULL, либо указатели на (в нашем случае, хэши) другие узлы. Это формирует базовое хранилище (ключ, значение).

Допустим, вы хотите использовать структуру данных radix-дерева для сохранения порядка в наборе пар «ключ-значение». Чтобы найти значение, сопоставленное в данный момент с ключом dog в дереве, сначала нужно преобразовать dog в буквы алфавита (получив 64 6f 67), а затем спускаться по дереву по этому пути, пока не найдете значение. То есть вы начинаете с поиска корневого хэша в плоской базе данных «ключ/значение», чтобы найти корневой узел дерева. Он представлен в виде массива ключей, указывающих на другие узлы. Вы бы использовали значение по индексу 6 в качестве ключа и искали бы его в плоской базе данных «ключ/значение», чтобы получить узел на один уровень ниже. Затем выберите индекс 4 для поиска следующего значения, затем выберите индекс 6 и так далее, пока, пройдя по пути: корень -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, вы не найдете значение узла и не вернете результат.

Существует разница между поиском чего-либо в «дереве» (trie) и в базовой плоской «БД» (DB) «ключ/значение». Оба они определяют сопоставления «ключ/значение», но базовая БД может выполнять традиционный одношаговый поиск ключа. Поиск ключа в дереве требует нескольких обращений к базовой БД для получения конечного значения, как описано выше. Чтобы устранить двусмысленность, будем называть последнее путем (path).

Операции обновления и удаления для radix-деревьев можно определить следующим образом:

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                return hash(newnode)
Показать все

Radix-дерево Меркла строится путем связывания узлов с помощью детерминированно сгенерированных криптографических хэш-дайджестов. Эта адресация по содержимому (в БД «ключ/значение» key == keccak256(rlp(value))) обеспечивает криптографическую гарантию целостности хранимых данных. Если корневой хэш данного дерева общеизвестен, то любой, у кого есть доступ к базовым листовым данным, может построить доказательство того, что дерево включает данное значение по определенному пути, предоставив хэши каждого узла, соединяющего конкретное значение с корнем дерева.

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

Атомарную единицу radix-дерева (например, один шестнадцатеричный символ или 4-битное двоичное число) мы будем называть «ниббл» (полубайт). При обходе пути по одному нибблу за раз, как описано выше, узлы могут ссылаться максимум на 16 дочерних элементов, но при этом включают элемент value. Следовательно, мы представляем их в виде массива длиной 17. Мы называем эти 17-элементные массивы «ветвящимися узлами».

Дерево Меркла-Патрисии

У radix-деревьев есть одно серьезное ограничение: они неэффективны. Если вы хотите сохранить одну привязку (путь, значение), где путь, как в Ethereum, имеет длину 64 символа (количество нибблов в bytes32), нам потребуется более килобайта дополнительного пространства для хранения одного уровня на символ, и каждый поиск или удаление займет все 64 шага. Дерево Патрисии, представленное далее, решает эту проблему.

Оптимизация

Узел в дереве Меркла-Патрисии является одним из следующих:

NULL (представленный в виде пустой строки)
branch (ветвь) — узел из 17 элементов [ v0 ... v15, vt ]`
leaf (лист) — узел из 2 элементов [ encodedPath, value ]
extension (расширение) — узел из 2 элементов [ encodedPath, key ]

При 64-символьных путях неизбежно, что после прохождения первых нескольких уровней дерева вы достигнете узла, в котором не существует расходящегося пути, по крайней мере, на части оставшегося спуска. Чтобы избежать необходимости создавать до 15 разреженных NULL узлов на пути, мы сокращаем спуск, устанавливая узел extension (расширение) вида [ encodedPath, key ], где encodedPath содержит «частичный путь» для пропуска вперед (с использованием компактного кодирования, описанного ниже), а key — для следующего поиска в БД.

Для листового узла, который может быть помечен флагом в первом ниббле encodedPath, путь кодирует все фрагменты пути предыдущих узлов, и мы можем напрямую найти значение.

Однако описанная выше оптимизация вносит неоднозначность.

При обходе путей по нибблам мы можем получить нечетное количество нибблов для обхода, но поскольку все данные хранятся в формате байтов (bytes). Невозможно различить, например, ниббл 1 и нибблы 01 (оба должны храниться как <01>). Чтобы указать нечетную длину, частичный путь снабжается префиксом-флагом.

Спецификация: компактное кодирование шестнадцатеричной последовательности с необязательным терминатором

Маркировка как нечетной/четной длины оставшегося частичного пути, так и листового/расширяющего узла, как описано выше, находится в первом ниббле частичного пути любого узла из 2 элементов. Это приводит к следующему:

шестн. символ	биты	тип узла/частичный	длина пути
0	0000	расширение	четная
1	0001	расширение	нечетная
2	0010	конечный (лист)	четная
3	0011	конечный (лист)	нечетная

Для четной оставшейся длины пути (0 или 2) всегда будет следовать еще один «заполняющий» ниббл 0.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarray now has an even length whose first nibble is the flags.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
Показать все

Примеры:

1    > [1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [f, 1, c, b, 8, 10]
8    '3f 1c b8'

Вот расширенный код для получения узла в дереве Меркла-Патрисии:

1    def get_helper(node_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
Показать все

Пример дерева

Предположим, мы хотим создать дерево, содержащее четыре пары «путь/значение»: ('do', 'глагол'), ('dog', 'щенок'), ('doge', 'монеты'), ('horse', 'жеребец').

Сначала мы преобразуем и пути, и значения в байты. Ниже фактические байтовые представления для путей обозначаются через \<>, хотя значения все еще показаны как строки, обозначаемые '', для облегчения понимания (они тоже на самом деле были бы байтами):

1    <64 6f> : 'глагол'
2    <64 6f 67> : 'щенок'
3    <64 6f 67 65> : 'монеты'
4    <68 6f 72 73 65> : 'жеребец'

Теперь мы строим такое дерево со следующими парами «ключ/значение» в базовой БД:

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'жеребец' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashC ]
4    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'глагол' ]
5    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'монеты' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'щенок' ] ]

Когда один узел ссылается на другой, включается keccak256(rlp.encode(node)), если len(rlp.encode(node)) >= 32, иначе node, где rlp.encode — это функция кодирования RLP.

Обратите внимание, что при обновлении дерева необходимо сохранять пару «ключ/значение» (keccak256(x), x) в постоянной таблице поиска, если вновь созданный узел имеет длину >= 32. Однако, если узел короче, ничего хранить не нужно, так как функция f(x) = x обратима.

Деревья в Ethereum

Все деревья Меркла на уровне исполнения Ethereum используют дерево Меркла-Патрисии.

В заголовке блока есть 3 корня от 3 из этих деревьев.

stateRoot
transactionsRoot
receiptsRoot

Дерево состояний

Существует одно глобальное дерево состояний, и оно обновляется каждый раз, когда клиент обрабатывает блок. В нем path всегда равен keccak256(ethereumAddress), а value всегда равен rlp(ethereumAccount). Более конкретно, аккаунт Ethereum — это массив из 4 элементов: [nonce, balance, storageRoot, codeHash]. Здесь стоит отметить, что этот storageRoot является корнем другого дерева Патрисии:

Дерево хранилища

В дереве хранилища находятся все данные контракта. Для каждого аккаунта существует отдельное дерево хранилища. Для извлечения значений в определенных позициях хранилища по заданному адресу требуются адрес хранилища, целочисленная позиция хранимых данных в хранилище и ID блока. Затем они могут быть переданы в качестве аргументов в eth_getStorageAt, определенный в JSON-RPC API, например, для извлечения данных в слоте хранилища 0 для адреса 0x295a70b2de5e3953354a6a8344e616ed314d7251:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

Извлечение других элементов в хранилище немного сложнее, потому что сначала необходимо вычислить позицию в дереве хранилища. Позиция вычисляется как хэш keccak256 от адреса и позиции в хранилище, причем оба значения дополняются нулями слева до длины 32 байта. Например, позиция для данных в слоте хранилища 1 для адреса 0x391694e7e0b0cce554cb130d723a9d27458f9298 такова:

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

В консоли Geth это можно рассчитать следующим образом:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

path (путь) поэтому равен keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Теперь это можно использовать для извлечения данных из дерева хранилища, как и раньше:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Примечание: storageRoot для аккаунта Ethereum по умолчанию пуст, если это не аккаунт контракта.

Дерево транзакций

Для каждого блока существует отдельное дерево транзакций, снова хранящее пары (ключ, значение). Здесь путь — это rlp(transactionIndex), который представляет ключ, соответствующий значению, определяемому следующим образом:

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

Более подробную информацию об этом можно найти в документации EIP 2718 (opens in a new tab).

Дерево квитанций

У каждого блока есть свое дерево квитанций. Здесь path (путь) — это rlp(transactionIndex). transactionIndex — это его индекс в блоке, в который он был включен. Дерево квитанций никогда не обновляется. Подобно дереву транзакций, существуют текущие и устаревшие квитанции. Для запроса конкретной квитанции в дереве квитанций требуются индекс транзакции в ее блоке, полезная нагрузка квитанции и тип транзакции. Возвращенная квитанция может быть типа Receipt, который определяется как конкатенация TransactionType и ReceiptPayload, или типа LegacyReceipt, который определяется как rlp([status, cumulativeGasUsed, logsBloom, logs]).

Более подробную информацию об этом можно найти в документации EIP 2718 (opens in a new tab).

Дерево Меркла-Патрисии

Предварительные условия

Базовые radix-деревья

Дерево Меркла-Патрисии

Оптимизация

Спецификация: компактное кодирование шестнадцатеричной последовательности с необязательным терминатором

Пример дерева

Деревья в Ethereum

Дерево состояний

Дерево хранилища

Дерево транзакций

Дерево квитанций

Дополнительные материалы

Была ли эта статья полезной?