Префиксное дерево Меркла-Патриции

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

Структура данных Эфириума представляет собой «модифицированное префиксное дерево Меркла-Патриции» (Merkle-Patricia Trie). Оно названо так, потому что заимствует некоторые особенности PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric — практический алгоритм для извлечения информации, закодированной в буквенно-цифровом виде), а также потому, что оно предназначено для эффективного извлечения (retrieval) данных, составляющих состояние Эфириума.

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

В ближайшем будущем Эфириум планирует перейти на структуру дерева Веркла (Verkle Tree), что откроет множество новых возможностей для будущих улучшений протокола.

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

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

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

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

[i_0, i_1 ... i_n, value]

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

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

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

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

    def update(node_hash, path, value):
        curnode = db.get(node_hash) if node_hash else [NULL] * 17
        newnode = curnode.copy()
        if path == "":
            newnode[-1] = value
        else:
            newindex = update(curnode[path[0]], path[1:], value)
            newnode[path[0]] = newindex
        db.put(hash(newnode), newnode)
        return hash(newnode)

    def delete(node_hash, path):
        if node_hash is NULL:
            return NULL
        else:
            curnode = db.get(node_hash)
            newnode = curnode.copy()
            if path == "":
                newnode[-1] = NULL
            else:
                newindex = delete(curnode[path[0]], path[1:])
                newnode[path[0]] = newindex

            if all(x is NULL for x in newnode):
                return NULL
            else:
                db.put(hash(newnode), newnode)
                return hash(newnode)

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

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

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

Префиксное дерево Меркла-Патриции

У radix-деревьев есть одно серьезное ограничение: они неэффективны. Если вы хотите сохранить одну привязку (path, value), где путь, как в Эфириуме, имеет длину 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 предназначен для следующего поиска в БД.

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

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

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

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

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

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

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

    def compact_encode(hexarray):
        term = 1 if hexarray[-1] == 16 else 0
        if term:
            hexarray = hexarray[:-1]
        oddlen = len(hexarray) % 2
        flags = 2 * term + oddlen
        if oddlen:
            hexarray = [flags] + hexarray
        else:
            hexarray = [flags] + [0] + hexarray
        # Теперь hexarray имеет четную длину, а его первый полубайт — это флаги.
        o = ""
        for i in range(0, len(hexarray), 2):
            o += chr(16 * hexarray[i] + hexarray[i + 1])
        return o

Примеры:

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

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

    def get_helper(node_hash, path):
        if path == []:
            return node_hash
        if node_hash == "":
            return ""
        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
        if len(curnode) == 2:
            (k2, v2) = curnode
            k2 = compact_decode(k2)
            if k2 == path[: len(k2)]:
                return get(v2, path[len(k2) :])
            else:
                return ""
        elif len(curnode) == 17:
            return get_helper(curnode[path[0]], path[1:])

    def get(node_hash, path):
        path2 = []
        for i in range(len(path)):
            path2.push(int(ord(path[i]) / 16))
            path2.push(ord(path[i]) % 16)
        path2.push(16)
        return get_helper(node_hash, path2)

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

Предположим, нам нужно дерево, содержащее четыре пары путь/значение: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

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

<64 6f> : 'verb'
    <64 6f 67> : 'puppy'
    <64 6f 67 65> : 'coins'
    <68 6f 72 73 65> : 'stallion'

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

rootHash: [ <16>, hashA ]
    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
    hashB:    [ <00 6f>, hashC ]
    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

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

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

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

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

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

stateRoot
transactionsRoot
receiptsRoot

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

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

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

Дерево хранилища — это место, где находятся все данные контракта. Для каждого аккаунта существует отдельное дерево хранилища. Чтобы извлечь значения в определенных позициях хранилища по заданному адресу, требуются адрес хранилища, целочисленная позиция хранимых данных в хранилище и идентификатор блока. Затем их можно передать в качестве аргументов в eth_getStorageAt, определенный в API JSON-RPC, например, чтобы извлечь данные в слоте хранилища 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 равна:

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

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

> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
undefined
> web3.sha3(key, {"encoding": "hex"})
"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 для аккаунта Эфириума по умолчанию пуст, если это не контрактный аккаунт.

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

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

if legacyTx:
  value = rlp(tx)
else:
  value = TxType | encode(tx)

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

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

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

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

Префиксное дерево Меркла-Патриции

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

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

Префиксное дерево Меркла-Патриции

Оптимизация

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

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

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

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

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

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

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

Дополнительная литература