Понимание баз данных Trie в Ethereum

Поверьте, это будет весело и познавательно :)

Прелюдия:

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

Здравствуйте, заядлые ученики и энтузиасты блокчейна!

Основные структуры данных, существующие в Ethereum, состоят из оптимизированной реализации попыток Меркла Патрисии. Эта статья призвана предоставить читателям более полное представление о том, как работает уровень хранения данных Ethereum, и о различных тонкостях, составляющих «мировое состояние». В частности, я буду обсуждать различные структуры дерева, их полезные свойства, модифицированное дерево Меркла Патрисии Эфириума, различные попытки внутри Эфириума и их соответствующие цели. Кроме того, внизу этой статьи есть полезные упражнения и ресурсы, которые помогут читателю лучше понять.

Поверьте, это будет весело и познавательно. :)

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

Структуры данных Trie | Radix Trees

Термин «trie» происходит от слова re trie ve; для ясности в статье термины «дерево» и «дерево» будут использоваться как синонимы. По словам Пола Блэка [1], термин «дерево» использовался просто для того, чтобы отличить его от слова «дерево», но в этой статье такого различия не будет… извините, Пол. (Разве я не говорил вам, что это будет весело?) Хорошо, давайте серьезно.

Рисунок A. Источник: https://en.wikipedia.org/wiki/Trie

Trie - это древовидная структура данных, также называемая цифровым деревом, деревом счисления или деревом префиксов, которое используется для получения строковое значение путем обхода ветви узлов, хранящих связанные ссылки (ключи), которые вместе ведут к конечному значению, которое может быть возвращено [2]. В частности, если мы начнем с вершины дерева в корневом узле, каждый символ в ключе указывает, по какому дочернему узлу следовать, что приводит к пути к соответствующему значению. Ключи могут содержать N символов, таким образом, каждый узел может содержать N потомков, а максимальная глубина дерева - это максимальная длина ключа [2]. Например, если бы мы использовали английский алфавит для составления ключей, каждый узел в дереве мог бы иметь до 26 дочерних элементов, поскольку в алфавите 26 букв. Чтобы сократить время, необходимое для перехода по ветви до конечного значения, ключи, начинающиеся в одной и той же последовательности, группируются в непосредственной близости друг от друга. При этом наш поиск конечной ценности оптимизируется и становится более эффективным. Чтобы подчеркнуть этот момент, я покажу дерево счисления, которое НЕ группирует одни и те же ключи последовательности вместе, а другой, который это делает.

Для иллюстрации на рисунке ниже изображены набор данных (рисунок B) и неэффективное дерево счисления счисления (рисунок C). Чтобы получить значение 5 с помощью нашего ключа BLOCK, нам нужно спуститься по пяти внутренним узлам с нулевыми значениями до достижения желаемого значения. Эта неэффективная реализация потребляет много бесполезного пространства.

Рисунок Б. Набор данных для неэффективного дерева счисления счисления

Рисунок C. Неэффективная реализация основанного на корне дерева

Улучшенное использование одного и того же основания счисления с одним и тем же набором данных может быть достигнуто путем объединения одинаковых ключей последовательности. Вместо односимвольных ключей, представляющих путь к значению, мы создаем строку. См. Рисунок D.

Рисунок D. Эффективная реализация дерева системы счисления

Вместо того, чтобы идти по пути пяти узлов с нулевым значением, нам просто нужно спуститься на один, чтобы получить желаемое значение 5, и только два узла, чтобы добраться до значения 6, где ключ - BLOCK (S).

Итак, мы рассмотрели основы попыток, в частности структуры данных в виде дерева счисления. Давайте обсудим деревья Меркла.

Структуры данных Trie | Деревья Меркла

Основная цель деревьев Меркла - доказать непротиворечивость данных, и, по сути, они представляют собой дерево хешей. Название Merkle Tree происходит от Ральфа Меркла, который запатентовал эту концепцию в 1979 году [3]. Википедия определяет деревья Меркла более точно следующим образом:

Дерево Меркла - это« дерево , в котором каждый листовой узел помечен хешем блока данных, а каждый нелистовой узел помечен криптографическим хешем меток его дочерние узлы ».

Рисунок E. Источник: http://en.wikipedia.org/wiki/hash_tree

Давайте рассмотрим рисунок E выше, чтобы получить более конкретное представление о деревьях Меркла. Нижние листья (C, D, E, F) представляют собой хеши следующих блоков данных, и эти блоки данных являются значениями, в которых мы сохраняем. Родители листьев ([C, D], [E, F]) будут равны Hash (valueOfChild1, valueOfChild2). Например, узел A представляет собой конкатенированные хэши двух своих дочерних узлов C и D. Этот процесс повторного хеширования конкатенации дочерних узлов для создания родительского узла выполняется до тех пор, пока не будет достигнута вершина дерева, называемая корневым хешем. '[3]. Вышеописанный процесс / структура хеширования «родитель-потомок» приводит к ключевому свойству деревьев Меркла: они предоставляют средства для подтверждения целостности и достоверности ваших данных.

Например, если бы мы изменили значение блока данных, весь путь, ведущий к «корневому хешу», также был бы изменен. Следовательно, если мы сохраняем значение корневого хеша, мы можем проверить согласованность данных, перестроив дерево, чтобы получить корневой хеш, а затем сравнить его с корневым хеш-значением, в котором мы храним [4]. Подделать данные без изменения значения корня невозможно.

Давайте рассмотрим больше преимуществ Merkle Trees, так как это будет способствовать нашему пониманию причин использования попыток для «мирового состояния» Ethereum.

Деревья Меркла | Полезные свойства

Ключевые преимущества деревьев Меркла заключаются в следующих свойствах [3]:

Согласованность данных / проверка
Доказательства Дерева Меркла вычисляются просто и быстро
Доказательства Merkle Tree требуют, чтобы только небольшие фрагменты данных транслировались по сети.

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

В этих распределенных системах данные существуют в нескольких местах; если некоторые данные изменяются в одном месте, эти изменения необходимо отразить везде. Деревья Меркла используются для проверки данных и обеспечения их совпадения - везде. Опять же, как мы описали ранее, мы можем сделать это, отправив хэш для сравнения. Рассмотрим следующую последовательность действий между двумя компьютерами [5]:

Компьютер A отправляет хэш файла на компьютер B.
Компьютер B сравнивает этот хэш с корнем дерева Меркла.
Если нет разницы, готово! В противном случае переходите к шагу 4.
Если в одном хэше есть разница, компьютер B запросит корни двух поддеревьев этого хеша.
Компьютер A создает необходимые хэши и отправляет их обратно на компьютер B.
Повторяйте шаги 4 и 5, пока не обнаружите несогласованные блоки данных. Можно найти более одного ошибочного блока данных, потому что в данных может быть более одной ошибки.

Приведенная выше последовательность показывает, как деревья Меркла упрощают проверку данных в сети. Чтобы уточнить, мы отправляем только хэш листа, который был идентифицирован как измененный по сети. Важность этого состоит в том, что это позволяет узлам в распределенной системе быстро и эффективно идентифицировать данные, которые изменились, без необходимости пересылать все данные для сравнения. Можно добиться проверки и согласованности данных без использования деревьев Меркла, но это потребует много времени и вычислительных ресурсов, требуя от сети проверки полноты каждой части данных всякий раз, когда узлы в сети запрашивают проверку данных.

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

Милая! Итак, это было наше введение в trie-структуры данных и их преимущества, в частности, основание системы счисления и деревья Меркла. Это довольно крутые структуры данных, и Ethereum удалось сделать их еще лучше.

Модифицированный Ethereum Меркл Патрисия Трие | Различия

Реализация структуры данных trie в Ethereum отличается от традиционных реализаций trie, поскольку были внесены изменения для повышения производительности и эффективности, отсюда Modified Merkle Patricia Trie. Мы рассмотрим эти улучшения, включая системы кодирования, используемые сетью Ethereum, а также рассмотрим особые типы узлов. Однако давайте начнем с собственного определения Ethereum его модифицированной Меркла Патрисии Трие из их статьи в вики:

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

Подводя итог, попытки криптографически безопасны, и на каждый узел ссылается его хэш, который используется для поиска в базе данных Leveldb (Go-Ethereum, CPP-Ethereum, Py-Ethereum) или RocksDB (Parity) [2]. В этой структуре корневые узлы становятся криптографическим отпечатком всей структуры данных, достигая оптимальной эффективности для вставки, поиска и удаления. Эти попытки хранятся в экземпляре Leveldb для клиентов Ethereum Go, C ++ и Python. Ниже приводится краткое описание Leveldb и некоторых его функций. (RocksDB выходит за рамки этой статьи, так как в основном относится к реализации Ethereum с паритетом.)

Leveldb - это библиотека для хранения ключей и значений от Google с открытым исходным кодом, которая предоставляет множество интересных функций, которые включают, но не ограничиваются [6]:

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

Так как же получить значения структур данных trie? Почему вы исследуете закодированный путь с шестнадцатеричным префиксом (HP) из их уважаемых корневых хэшей, конечно ...

Кодирование HP - это система кодирования Ethereum, используемая исключительно на путях, которые соединяют узлы каждой структуры данных trie. Эта система кодирования служит двойной цели: устранять неоднозначность между типами узлов (в частности, между листовыми узлами и узлами расширения - подробнее об этом позже) и преобразовывать путь в четную длину [7]. При этом дерево Меркла всегда будет состоять из целого числа байтов, что важно для машин.

Давайте углубимся в наше понимание того, как используется кодирование HP. Начнем с того, что Leaf и Extension - это два разных типа узлов. Листовые узлы содержат терминатор; думайте об этом как о флаге. Терминатор - это последний байт пути, который имеет значение 16 в десятичном формате или 0x10 в шестнадцатеричном формате [8]. Полубайт, который представляет собой всего лишь один шестнадцатеричный символ, добавляется к началу ключа, чтобы определить четность (четную или нечетную по длине) и наличие ограничителя. Точнее, младший значащий бит кодирует четную и нечетную длину, а следующий младший бит кодирует терминатор. Когда функция кодирования HP встречает терминатор, она удаляет его, а затем продолжает создавать префикс в пути. Если префикс равен 0x0 или 0x2, функция добавит полубайт 0, за которым следует префикс, таким образом, полный префикс будет 0x0 0 или 0x2 0 . Опять же, причина состоит в том, чтобы поддерживать одинаковую длину любого заданного пути.

Рассмотрим таблицу на рисунке F: строка B - это узел расширения нечетной длины, начинающийся с шестнадцатеричного числа 1, поэтому мы префикс пути с 1, и теперь путь четный. Строка C - листовой узел четной длины; он имеет терминатор в конце (шестнадцатеричный 10), а путь начинается с шестнадцатеричного числа 0. Терминатор удаляется, и шестнадцатеричный знак 2 ставится впереди (20), за которым следует шестнадцатеричный символ 0 перед шестнадцатеричным числом f, создавая четную длину дорожка.

Рисунок F. Пример шестнадцатеричного префикса

В то время как HP кодирует путь к заданному значению, собственная система кодирования Ethereum, известная как рекурсивный префикс длины (RLP), кодирует фактическое значение. Обратите внимание, что на момент написания этой статьи, хотя Ethereum все еще использует эту методологию для сериализации объектов, RLP будет заменен более оптимальной формой сериализации в будущем, как упоминалось здесь. Мы обсудим его роль в текущей реализации.

Для правильного хранения данных требуется форма сериализации данных, то есть перевод структур данных или состояния объекта в формат, который может быть сохранен или передан по сети для последующего восстановления. Ethereum использует RLP для сериализации данных. Целью RLP является кодирование вложенных массивов двоичных данных или кодирование структуры. Функция кодирования RLP принимает элемент и соответственно кодирует переданный элемент.

Вики-страница Ethereum определяет элемент следующим образом:

Строка (т.е. байтовый массив) - это элемент
Список предметов - это предмет

Вики-страница Ethereum также предоставляет подробное определение кодировки RLP на основе длины байтов среди других факторов и предоставляет убедительные примеры.

Оптимизация Modified Merkle Patricia Trie является результатом дополнительной сложности, а именно введения различных типов узлов. Он содержит четыре различных типа узлов [9]:

NULL Nodes (представленные как пустая строка)
Узлы ФИЛИАЛА (узел из 17 элементов, [v0… ..v15, vt])
Узлы LEAF (узел из 2 элементов, [encodedPath, значение])
Узлы РАСШИРЕНИЯ (узел из 2 элементов, [encodedPath, ключ])

Мы кратко обсудили листовые узлы и узлы расширения выше, но не указали их важность. Без каждого отдельного типа узла, если бы мы прошли 64-символьный путь (в случае дерева состояний), мы могли бы встретить узел без различных доступных путей, и этот узел мог бы иметь пустые значения в каждом индексе (одно для каждый из 16 шестнадцатеричных символов) помимо целевого индекса [9]. Чтобы предотвратить эти случаи и уменьшить расстояние, которое проходит по такому пути, Ethereum использует узлы расширения [encodedPath, key], где encodedPath (вспомните кодировку HP выше) состоит из «частичного пути», который позволяет нам пропустить вперед, а ключ затем используется для следующего поиска в базе данных в Leveldb [9].

Конечные узлы [encodedPath, value], если вы помните, когда мы обсуждали шестнадцатеричные префиксы, могут быть идентифицированы по их флагу-терминатору в первом полубайте encodedPath. Возникает та же ситуация, описанная выше, encodedPath содержит «частичный путь», который быстро пересылает нас к полному концу пути, где значением является само целевое значение [9]. Чтобы лучше понять эти типы узлов, давайте посмотрим на пример на рисунке G.

Рисунок G. Источник: Ли Томас, https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

В правом верхнем углу у нас есть упрощенное состояние мира. Ключи представляют адреса, а значения - остатки. В этом примере корневой узел является узлом расширения [encodedPath, key], и мы знаем, что это основано на шестнадцатеричном префиксе. Также обратите внимание, что в этом примере все ключи имеют один и тот же полубайт a7, поэтому они сгруппированы соответствующим образом, как это пытается сделать атрибут radix. Поскольку корень является узлом расширения [encodedPath, key], сегмент «следующий узел» будет хешем, указывающим на следующий узел, который в данном случае является узлом ветвления [v0… ..v15, vt]. Если мы будем следовать за первым ключом в нашем упрощенном состоянии (a711355), мы будем использовать 1 после a7, чтобы посмотреть в первый индекс узла ветвления. Это приводит нас к созданию листового узла, где, если мы сравниваем ключ и путь, они совпадают, что позволяет нам пропустить вперед и приводит нас к значению или балансу счета в 45,0 ETH.

Trie структуры данных Ethereum | Подробности

Ethereum использует свою «модифицированную Merkle Patricia Trie» для каждой из четырех структур данных trie:

Дерево квитанции
Государственное дерево
Дерево хранения
Дерево транзакций

Корнем для каждой из попыток является 256-битный хэш Keccak, и три из четырех попыток, перечисленных выше, существуют в заголовке блока, дереве получения, дереве состояний и дереве транзакций. Корень дерева хранения находится в значении данных, закодированных по протоколу RLP, в дереве состояний. См. Рисунок H ниже.

Рисунок H. Источник: https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

Время транзакции

Как упоминалось выше, корень транзакции существует в заголовке блока, и, как вы можете догадаться, его цель - записывать транзакции. Поскольку порядок данных в основном определяется майнером, мы не знаем, как они выглядят, пока они не будут добыты. Мы действительно знаем, какие параметры используются для создания дерева транзакции, и они следующие:

Одноразовый номер аккаунта
Цена на газ
Лимит газа
Получатель
Стоимость перевода
Значения подписи транзакции
Инициализация учетной записи (если транзакция относится к типу создания контракта) или данные транзакции (если транзакция представляет собой вызов сообщения)

После добычи блока дерево транзакции никогда не обновляется [9].

Номер квитанции

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

Состояние после транзакции
Общее количество использованного газа
Журналы
Фильтр Блума, созданный на основе информации из вышеуказанных журналов

Это дерево никогда не обновляется.

State Trie

Одно и только одно глобальное дерево состояний. Он содержит пару ключ-значение для каждой учетной записи Ethereum в сети, где ключ представляет собой адрес Ethereum, а значение - учетную запись Ethereum с кодировкой RLP. Учетная запись Ethereum и дерево состояний состоят из следующих полей:

Nonce
Остаток средств
Корень хранилища
Codehash

В отличие от попыток транзакции и получения, дерево состояний обновляется с течением времени… постоянно.

Storage Trie

Дерево хранилища - это место, где находятся все данные контракта, и для каждой учетной записи существует отдельное дерево хранилища [9].

Теперь мы рассмотрели каждое дерево, его назначение и содержание. На рисунке I ниже четко показано то, что мы рассмотрели выше. Как вы можете видеть, справа у нас есть заголовок блока, который содержит корень для «Мирового состояния Trie», «Transaction Trie» и «Transaction Receipt Trie». Он также отображает содержимое в каждом из этих деревьев, включая корень хранилища для «Учетной записи хранилища данных».

Рисунок I. Источник: Ли Томас, https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

Заключение

Цель этой статьи заключалась в том, чтобы предоставить читателям более полное представление о trie-структурах данных в Ethereum. Я надеюсь, что цель этой статьи была достигнута, но если нет, то я включил ряд ресурсов и упражнений ниже. Спасибо, что нашли время прочитать.

Глоссарий

Ветвь: структура из 17 элементов, первые шестнадцать элементов которой соответствуют каждому из шестнадцати возможных значений полубайта для ключей на данном этапе их обхода. 17-й элемент используется в том случае, если он является узлом-терминатором и, следовательно, ключом, заканчивающимся в этой точке его обхода [7].

Расширение: структура из двух элементов, первый элемент которой соответствует серии полубайтов размером больше одного, которые используются как минимум двумя разными ключами после накопления полубайтов ключей и ветвей, проходящих от корня. . Используется метод кодирования с шестнадцатеричным префиксом, и второй параметр функции должен иметь значение false [7].

Leaf: структура из двух элементов, первый элемент которой соответствует полубайтам в ключе, еще не учтенным накоплением ключей и ветвей, пройденных от корня. Используется метод кодирования с шестнадцатеричным префиксом, и второй параметр функции должен быть истинным [7].

Полубайт: шестнадцатеричная форма из 4 бит (0x1, 0x4, 0xf).