Что такое дерево меркла
Merkle Tree: ржавое и быстрое
Всем привет! Недавно открыл для себя язык Rust. О своих первых впечатлениях поделился в предыдущей статье. Теперь решил копнуть немного глубже, для этого необходимо что-то посерьёзнее списка. Выбор мой пал на дерево Меркла. В этой статье я хочу:
Дерево Меркла
Это относительно простая структура данных, и про неё уже есть много информации в интернете, но думаю, моя статья будет неполной без описания дерева.
В чём проблема
Дерево Меркла было изобретено ещё в 1979 году, но приобрело свою популярность благодаря blockchain. Цепочка блоков в сети имеет очень большой размер (для bitcoin это более 200 ГБ), и далеко не все узлы могут её выкачать. Например, телефоны или кассовые аппараты. Тем не менее им нужно знать о факте включения той или иной транзакции в блок. Для этого был придуман протокол SPV — Simplified Payment Verification.
Как устроено дерево
Это бинарное дерево, листьями которого являются хеши любых объектов. Для построения следующего уровня попарно берутся хеши соседних листьев, конкатенируются и вычисляется хеш от результата конкатенации, что проиллюстрировано на картинке в заголовке. Таким образом, корень дерева представляет собой хеш всех листьев. Если убрать или добавить элемент, то корень изменится.
Как работает дерево
Имея дерево Меркла можно построить доказательство включения транзакции в блок как путь от хеша транзакции до корня. Например, нас интересует транзакция Tx2, для неё доказательством будет (Hash3, Hash01). Этот механизм и используется в SPV. Клиент выкачивает только заголовок блока с его хешем. Имея интересующую транзакцию, он запрашивает доказательство у узла содержащего всю цепочку. Затем делает проверку, для Tx2 это будет:
Полученный результат сравнивается с корнем из заголовка блока. Этот подход делает невозможным подделку доказательства, т. к. в этом случае не сойдётся результат проверки с содержимым заголовка.
Какие уже есть реализации
Rust молодой язык, но на нём уже написано много реализаций дерева Меркла. Судя по Github, на данный момент 56, это больше чем на С и С++ вместе взятых. Хотя Go делает их как стоячих с 80 реализациями.
SpinResearch/merkle.rs
Для своего сравнения я выбрал эту имплементацию по количеству звёзд у репозитория.
Это дерево построено самым очевидным способом, т. е. представляет собой граф объектов. Как я уже заметил, такой подход не вполне Rust-friendly. Например, невозможно сделать двунаправленную связь от детей к родителям.
Построение доказательства происходит через поиск в глубину. Если лист с нужным хешем найден, то путь до него и будет результатом.
Что можно улучшить
Делать просто (n+1)-ю реализацию мне было неинтересно, поэтому я подумал об оптимизации. Код моего vector-merkle-tree находится на Github.
Хранение данных
Первое что приходит в голову, это переложить дерево на массив. Это решение будет намного лучше с точки зрения локальности данных: больше попаданий в кеш и лучше предзагрузка. Обход объектов, разбросанных по памяти, занимает больше времени. Удобным фактом является то, что все хеши имеют одинаковую длину, т.к. вычисляются одним алгоритмом. Дерево Меркла в массиве будет выглядеть так:
Доказательство
При инициализации дерева можно создать HashMap с индексами всех листьев. Таким образом, когда листа нет, не нужно обходить всё дерево, а если есть, то можно сразу перейти к нему и подняться до корня, строя доказательство. В своей имплементации я сделал HashMap опциональным.
Конкатенация и хеширование
Казалось бы, что тут можно улучшить? Всё ведь и так понятно — берём два хеша, склеиваем их и вычисляем новый хеш. Но дело в том, что эта функция некоммутативная, т.е. hash(H0, H1) ≠ hash(H1, H0). Из-за этого при построении доказательства нужно запоминать с какой стороны находится соседний узел. Это делает алгоритм сложнее для реализации, и добавляет необходимость хранить лишние данные. Всё очень легко исправить, достаточно просто отсортировать два узла перед хешированием. Для примера я приводил Tx2, c учётом коммутативности проверка будет выглядеть так:
Когда не надо заботиться о порядке, алгоритм проверки выглядит как простая свёртка массива:
Нулевой элемент это хеш искомого объекта, первый — его сосед.
Погнали!
Рассказ был бы неполным без сравнения производительности, которое заняло у меня в несколько раз больше времени, чем реализация самого дерева. Для этих целей я использовал фреймворк criterion. Исходники самих тестов находятся тут. Всё тестирование происходит через интерфейс TreeWrapper, который был реализован для обоих подопытных:
Оба дерева работают с одной криптографией ring. Тут я не собираюсь сравнивать разные библиотеки. Взял самую распространённую.
В качестве объектов хеширования используются случайно сгенерированные строки. Деревья сравниваются на массивах различной длины: (500, 1000, 1500, 2000, 2500 3000). 2500 — 3000 это примерное число транзакций в блоке биткоина на данный момент.
На всех графиках по оси X — число элементов массива (или количество транзакций в блоке), по Y — среднее время на выполнение операции в микросекундах. Т. е. чем больше, тем хуже.
Создание дерева
Хранение всех данных дерева в одном массиве сильно превосходит по производительности граф объектов. Для массива с 500 элементами в 1,5 раза, а для 3000 элементов уже в 3,6 раза. Чётко виден нелинейный характер зависимости сложности от объёма входных данных в стандартной реализации.
Так же в сравнение я добавил два варианта векторного дерева: с HashMap и без него. Заполнение дополнительной структуры данных добавляет где-то 20%, но зато позволяет намного быстрее искать объекты при построении доказательства.
Построение доказательства
Тут видна явная неэффективность поиска в глубину. С увеличением входных данных, она только усугубляется. Важно понимать, что искомыми объектам являются листы, поэтому сложности log(n) быть не может. Если данные предварительно захешированы, то время операции практически не зависит от числа элементов. Без хеширования, сложность растет линейно и заключается в поиске перебором.
Валидация доказательства
Это последняя операция. Она не зависит от структуры дерева, т.к. работает с результатом построения доказательства. Я полагаю, что основную сложность тут составляет вычисление хеша.
Что такое дерево Меркла и как оно связано с криптовалютами?
Чтобы понимать блокчейн, нужно разбираться в базовых принципах, на которых основана технология. Пожалуй, главной особенностью является дерево Меркла или так называемое хеш-дерево. Именно благодаря ему блокчейн может быть эффективным и прозрачным одновременно. Концепция дерева была запатентована профессором Ральфом Мерклом ещё в 1979 году. Сейчас же оно помогает решить проблемы в больших децентрализованных сетях.
Дерево Меркла — полная структура данных в виде дерева, в листовые вершинах которого находятся хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Это связывает все элементы с информацией между собой. В итоге всё выглядит так.
Дерево Меркла. Источник: Gocoding
Хеш — результат преобразования хеш-функции, то есть функции, которая преобразовывает массив входных данных произвольной длины в выходную строку установленной длины в соответствии с определённым алгоритмом.
Зачем нужно хеш-дерево?
В централизованной системе правдивость информации не является проблемой, так как все её составляющие полагаются на один централизованный узел. Вам не нужно беспокоиться о подлинности денег, когда вы получаете перевод на свой банковский счёт.
Ральф Меркл. Источник: Alchetron
А вот в децентрализованной сети всё не так просто. Каждый её узел сам отвечает за правдивость передаваемой информации, поэтому подтвердить подлинность её полного объёма очень проблематично — как минимум из-за количества всех транзакций в сети. По крайней мере, без дерева Меркла. Последнее позволяет оптимизировать процесс представления данных с помощью хеширования.
Как организовано дерево Меркла в Биткоине?
Хеш-функция — это процесс преобразования входных данных в битовую строку установленной длинны. Полученная строка, хеш, очень сильно зависит от массива входящих данных. Если даже один символ из всего массива будет изменён, полученный хеш примет совсем другое значение.
Все транзакции в блоке Биткоина — это строки в шестнадцатеричном формате, они хешируются и представляются в виде идентификаторов транзакций (txid). Все txid в блоке хешируются, пока не будет получено единое хеш-значение блока. В процессе происходит построение дерева Меркла:
Дерево Меркла в Биткоине. Источник: Github
Визуально процесс составления единого хеша напоминает дерево, от вершины которого расходятся «ветки» с хешами. Собственно, отсюда и название.
Принцип работы дерева Меркла
Процесс составления дерева Меркла похож на «свёртывание данных». Благодаря ему огромный список транзакций или любой другой массив информации можно представить всего одной строкой. Вся прелесть в том, что если где-нибудь в списке этих самых транзакций мы поменяем всего один символ, следующий «уровень» дерева будет уже совсем другим и конечный хеш — то есть «верхушка» дерева — тоже поменяется.
Иными словами, в блок нельзя подставить другую транзакцию или поменять данные уже существующих. Вот почему дерево Меркла считается эффективным способом записи транзакций в блокчейн. Существует также понятие Merkle Proof — это принцип проверки правдивости информации с помощью хешей. Вместо изучения всего массива данных достаточно изучить отдельные хеши в дереве, что сильно снижает затраты вычислительной мощности на весь процесс.
Аналоги дерева Меркла
В статье рассмотрен самый простой бинарный вариант концепции, изобретённой Ральфом Мерклом. В нём каждый «родительский» хеш имеет два «наследника». В Биткоине хеш-дерево строится с использованием двойного хеширования SHA-256.
Вы могли слышать «SHA-256» при выборе ASIC-майнеров Биткоина, которые работают именно на этом алгоритме.
Antminer S9. Источник: Bitcoinist
Существуют более сложные интерпретации концепции. К примеру, в Эфириуме используется префиксное дерево Меркла. В каждом заголовке блока Эфириума содержится сразу три таких дерева: для транзакций, информации об их выполнении и состоянии. В отличие от бинарного дерева, значение узла префиксного зависит ещё и от соединений с другими узлами. Таким образом, значение является динамическим, а не фиксированным, то есть оно может изменяться без необходимости пересчитывать все хеши дерева.
Дерево Меркла в Эфириуме. Источник: Ethereum Stack Exchange
Ещё больше интересной информации о блокчейне можно найти в нашем крипточате. Также не забудьте подписаться на Два Биткоина в Яндекс Дзене.
Как это работает: Деревья Меркла в биткойн сети
Узлы в блокчейн-сети анонимны и работают в условиях отсутствия доверия. В этой ситуации встает проблема верификации данных: как проверить, что в блоке записаны корректные транзакции? Для оценки каждого блока понадобится большое количество времени и вычислительных ресурсов. Решить проблему и упростить процесс помогают деревья Меркла.
Что это такое, как используется, какие существуют альтернативы — расскажем далее.
Дерево Меркла — как оно «выглядит»
Блоки в биткойн-блокчейне — это перманентно записываемые файлы, которые содержат информацию о проведенных пользователями транзакциях. Дополнительно каждый блок содержит Generation Transaction (или Coinbase Transaction) — это транзакция с информацией об адресе с наградой за решение блока, которая всегда стоит первой в списке.
Все транзакции в блоке представлены как строки в шестнадцатеричном формате (raw transaction format), которые хешируются для получения идентификаторов транзакций (txid). На их основе строится хеш блока, который учитывается последующим блоком, обеспечивая неизменяемость и связность реестра. Единое хеш-значение блока собирается при помощи дерева Меркла, концепция которого была запатентована Ральфом Мерклом (Ralph Charles Merkle) в 1979 году.
Дерево Меркла, или хеш-дерево, — это двоичное дерево, конечные узлы которого — это хеши транзакций, а внутренние вершины — результаты сложения значений связанных вершин. Вот пример хеш-дерева с тремя транзакциями-листьями:
/ изображение MrTsepa CC
Построение дерева происходит следующим образом:
Первый раунд SHA-256:
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
Второй раунд:
9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50
А вот пример реализации деревьев Меркла, используемой биткойном, на Python (результаты работы функции вы можете найти в репозитории на GitHub по ссылке):
Для чего нужны хеш-деревья
Файловые системы используют деревья Меркла для проверки информации на наличие ошибок, а распределенные базы данных — для синхронизации записей. В блокчейнах же хеш-деревья позволяют проводить упрощенную верификацию платежей (SPV).
SPV-клиенты, называемые легкими (потому что хранят только заголовки блоков, а не их содержимое), для проверки информации о транзакции не пересчитывают все хеши, а запрашивают доказательство Меркла. Оно состоит из корня и ветви, включающей хеши от запрашиваемой транзакции до корня, поскольку клиенту не нужна информация о других операциях. Сложив запрошенные хеши и сравнив их с корнем, клиент убеждается, что транзакция находится на своем месте.
Такой подход позволяет работать со сколь угодно большими объемами данных, поскольку значительно снижает нагрузку на сеть, так как скачиваются только необходимые хеши. Например, вес блока с пятью транзакциями максимального размера составляет более 500 килобайт. Вес доказательства Меркла в этом же случае не превысит 140 байт.
Аналоги деревьев Меркла
Двоичные деревья Меркла хорошо подходят для верификации последовательности элементов, поэтому справляются с задачей хранения структуры транзакций. Однако они ограничивают возможности легких клиентов, которые не получают информации о состоянии системы. Например, узнать, какое количество монет есть по указанному адресу, не представляется возможным.
Для обхода ограничения исследователи и разработчики модернизируют уже существующие алгоритмы и разрабатывают новые. Например, в блокчейн-платформе Ethereum используется так называемое префиксное дерево Меркла (Trie). Это структура данных, хранящая ассоциативный массив с ключами.
В отличие от бинарных деревьев Меркла, ключ, идентифицирующий конкретный узел дерева, является «динамическим». Его значение определяется местоположением на дереве и формируется путем соединения символов, присвоенных ребрам графа, проходящим от корня до заданного узла.
В Ethereum заголовок блока содержит сразу три префиксных дерева Меркла: для транзакций, информации об их выполнении и состоянии. Такой подход позволил легким клиентам получать от системы ответы на вопросы: «Есть ли транзакция в указанном блоке?», «Сколько монет на счету?» и «Каким будет состояние системы после выполнения этой транзакции?».
В качестве еще одной альтернативы классическим деревьям Меркла выступает метод комбинирования хеш-значений HashFusion, предложенный Hewlett Packard Labs. Как отмечают в компании, новый подход позволяет рассчитывать значения хешей поэтапно. Компоненты хеша вычисляются сразу, как только данные становятся доступны, а потом объединяются друг с другом при необходимости.
HashFusion подразумевает построение частей хеша с помощью бинарной функции объединения. Она является ассоциативной и некоммутативной, поэтому её можно использовать для объединения хешей в момент формирования. Это позволяет уменьшить объемы памяти, необходимые для их хранения.
Работа бинарной функции строится следующим образом: она принимает на вход значения хешей (генерируемых классическими хеширующими функциями) и конвертирует их в матрицы целых чисел. После чего матрицы перемножаются, а результат обратно превращается в байтовый массив фиксированной длины.
Представители компании HPE заявляют, что HashFusion реализует более гибкие структуры, по сравнению с деревьями Меркла, которые позволяют обновлять существующие хеши и выборочно удалять/вставлять новые значения. Авторы надеются, что в будущем технология найдет применение в файловых системах, облачных решениях и распределенных реестрах.
Есть и другие алгоритмы, которые ИТ-сообщество разрабатывает с целью оптимизации процессов обработки метаданных и построения деревьев Меркла. Среди них можно выделить решение iSHAKE, автор которого предлагает заменить процесс построения хеш-деревьев внедрением обратимой операции. Она позволит восстанавливать/добавлять и удалять новые значения из структуры. Также можно отметить модифицированный алгоритм организации цифровых подписей eXtended Merkle Signature Scheme (XMSS) и алгоритм SPHINCS.
Большая часть этих предложений находится на стадии тестирования и пока не нашла широкого применения — однако некоторым из них пророчат большое будущее в мире постквантовой криптографии.
P.S. 25 января в Киеве Bitfury проведет бесплатный воркшоп, во время которого будут разобраны практические особенности разработки с помощью Exonum.
Наши специалисты расскажут и покажут, как развернуть собственный блокчейн и как написать сервис. Встреча будет полезна разработчикам на Rust, C++ и JavaScript, делающим первые шаги в блокчейн-разработке, а также тем, кто уже пробовал создавать блокчейн-решения.
Узнать дополнительную информацию о мероприятии и спикерах, а также зарегистрироваться на событие можно по ссылке.
Экзотические структуры данных: Modified Merkle Patricia Trie
«Какого дьявола я должен помнить наизусть все эти чёртовы алгоритмы и структуры данных?».
Примерно к этому сводятся комментарии большинства статей про прохождение технических интервью. Основной тезис, как правило, заключается в том, что всё так или иначе используемое уже реализовано по десять раз и с наибольшей долей вероятности заниматься этим рядовому программисту вряд ли придётся. Что ж, в какой-то мере это верно. Но, как оказалось, реализовано не всё, и мне, к сожалению (или к счастью?) создавать Структуру Данных всё-таки пришлось.
Загадочное Modified Merkle Patricia Trie.
Так как на хабре информации об этом дереве нет вообще, а на медиуме — немногим больше, хочу поведать о том, что же это за зверь, и с чем его едят.
Что это?
Disclaimer: основным источником информации при реализации для меня являлись Yellow paper, а также исходные коды parity-ethereum и go-ethereum. Теоретической информации по поводу обоснования тех или иных решений было минимум, поэтому все выводы по поводу причин принятия тех или иных решений — мои личные. В случае, если я в чем-то заблуждаюсь — буду рад исправлениям в комментариях.
Дерево — структура данных, представляющая собой связный ациклический граф. Тут всё просто, все с этим знакомы.
Префиксное дерево — корневое дерево, в котором можно хранить пары ключ-значение за счёт того, что узлы делятся на два типа: те, что содержат часть пути (префикс), и конечные узлы, которые содержат хранимое значение. Значение присутствует в дереве тогда и только тогда, когда мы, используя ключ, можем пройти от корня дерева весь путь и в конце найти узел со значением.
PATRICIA-дерево — это префиксное дерево, в котором префиксы бинарны — то есть, каждый узел-ключ хранит информацию об одном бите.
Дерево Мёркла — это дерево хешей, построенное над какой-то цепочкой данных, агрегирующее эти самые хеши в один (корневой), хранящий информацию о состоянии всех блоков данных. То есть, корневой хеш — это эдакая «цифровая подпись» состояния цепи блоков. Используется эта штука активно в блокчейне, и подробнее про неё можно почитать тут.
Итого: Modified Merkle Patricia Trie (далее MPT для краткости) — это дерево хешей, хранящее пары ключ-значение, при этом ключи представлены в бинарном виде. А в чем именно заключается «Modified» мы узнаем чуть позже, когда будем обсуждать реализацию.
Зачем это?
MPT используется в проекте Ethereum для хранения данных об аккаунтах, транзакциях, результатах их выполнения и прочих данных, необходимых для функционирования системы.
В отличие от Bitcoin, в котором состояние неявно и вычисляется каждым узлом самостоятельно, в эфире баланс каждого аккаунта (а также ассоциированные с ним данные) хранятся непосредственно в блокчейне. Более того, нахождение и неизменность данных должны быть обеспечены криптографически — мало кто станет пользоваться криптовалютой, в которой баланс случайного аккаунта может измениться без объективных на то причин.
Основной проблемой, с которой столкнулись разработчики Ethereum — это создание структуры данных, которая позволяет эффективно хранить пары ключ-значение и при этом обеспечивать верификацию хранимых данных. Так и появилось MPT.
Как это?
MPT является префиксным PATRICIA-деревом, в котором ключами являются последовательности байтов.
Ребрами в данном дереве являются последовательности нибблов (половинок байтов). Соответственно, у одного узла может быть до шестнадцати потомков (соответствующих веткам от 0x0 до 0xF).
Узлы делятся на 3 вида:
Очевидно, что во втором случае сохранять узел в базу данных не нужно, т.к. он целиком будет сохранен внутри родительского узла.
Комбинация трёх видов узлов позволяет эффективно хранить данные и в случае, когда ключей мало (тогда большая часть путей будет храниться в extension и leaf нодах, а branch-узлов будет мало), и в случае, когда узлов много (пути не будут храниться явно, а будут «собираться» во время прохода по branch нодам).
Полный пример дерева, использущего все виды узлов:
Как вы могли заметить, хранимые части путей имеют префиксы. Префиксы нужны для нескольких целей:
Правила создания префиксов очень просты:
На битиках, думаю, будет понятнее:
Удаление, которое не удаление
Несмотря на то, что дерево имеет операцию удаления узлов, на самом деле всё, что однажды было добавлено, остается в дереве навсегда.
Нужно это для того, чтобы не создавать полное дерево для каждого блока, а хранить только разницу между старой и новой версией дерева.
Соответственно, используя разные root-хеши в качестве точки входа, мы сможем получить любое из состояний, в котором когда-либо пребывало дерево.
Это не все оптимизации. Там есть ещё, но об этом не будем — и так статья большая. Впрочем, можете почитать сами.
Реализация
Так как кода будет много, и для формата статьи многое придется сокращать и разделять, сразу же оставлю ссылку на github.
В случае необходимости, там можно посмотреть на картину целиком.
Для начала определим интерфейс дерева, который мы хотим получить в итоге:
Интерфейс предельно прост. Доступные операции — получение, удаление, вставка и измененение (объединенные в update), а также получение корневого хеша.
Однако, прежде чем мы приступим к реализации самого дерева, необходимо сделать две важных вещи:
NibblePath
Всё довольно просто, не так ли?
Осталось написать только функции для кодирования и декодирования последовательности нибблов.
Реализация, тем не менее, элементарна:
Перерыв
Фух! Информации получается много. Думаю, самое время отдохнуть. Вот вам ещё один котик:
Милота, правда? Ладно, вернемся к нашим деревьям.
MerklePatriciaTrie
А вот с оставшимися методами будем разбираться по одному.
Метод get (как, в принципе, и остальные методы) будут у нас состоять из двух частей. Сам метод будет производить подготовку данных и приведение результата к ожидаемой форме, тогда как настоящая работа будет происходить внутри вспомогательного метода.
Основной метод чрезвычайно прост:
Впрочем, _get не сильно сложнее: для того, чтобы добраться до искомого узла, нам нужно пройти от корня весь предоставленный путь. Если в конце мы обнаружили узел с данными (Leaf или Branch) — ура, данные получены. Если же пройти не удалось — то искомый ключ отсутствует в дереве.
Ну и заодно напишем методы для сохранения и загрузки узлов. Они простые:
update
Метод update уже интереснее. Просто пройти до конца и вставить Leaf-узел получится далеко не всегда. Вполне вероятна ситуация, что точка разделения ключей будет находиться где-то внутри уже сохраненного Leaf или Extension узла. В таком случае придется их разделить и создать несколько новых узлов.
В целом, всю логику можно описать следующими правилами:
Давайте постепенно выражать это в коде. Почему постепенно? Потому что метод большой и скопом его понять будет тяжеловато.
Впрочем, ссылку на полный метод я оставлю тут.
Общей логики довольно мало, все самое интересное находится внутри if ов.
if type(node) == Node.Leaf
Сперва разберемся с Leaf узлами. С ними возможны всего 2 сценария:
Остаток пути, по которому мы идём, полностью совпадает с путём, хранящимся в Leaf-узле. В таком случае нам нужно просто поменять значение, сохранить новый узел и вернуть ссылку на него.
Пути отличаются.
В таком случае нужно создать Branch узел, который разделит эти два пути.
Если один из путей пуст — то его значение перекочует непосредственно в Branch-узел.
В противном случае, нам придется создать два Leaf-узла, укороченных на длину общей части путей + 1 ниббл (этот ниббл будет обозначен индексом соответствующей ветки Branch-ноды).
Также нужно будет проверить, есть ли общая часть пути, чтобы понять, нужно ли нам создавать ещё и Extension-узел.
В коде это будет выглядеть так:
Процедура _create_branch_node выглядит следующим образом:
if type(node) == Node.Extension
В случае с Extension-узлом всё похоже на Leaf-узел.
Если путь из Extension-узла является префиксом для нашего пути — просто рекурсивно движемся дальше.
В противном случае нам нужно сделать разделение с использованием Branch-узла, как и в вышеописанном случае.
if type(node) == Node.Branch
А вот с Branch-узлом всё просто. Если путь пустой — мы просто сохраняем в текущем Branch-узле новое значение. Если же путь не пустой — «откусываем» от него один ниббл и рекурсивно идём ниже.
Код, думаю, в комментариях не нуждается.
delete
Это крайне важно, так как в противном случае возможна ситуация, в которой для двух деревьев, содержащих одни и те же данные, будет отличаться корневой хеш. А такая «особенность», как вы понимаете, перечеркнет весь смысл данной структуры данных.
Выглядить остов метода delete будет следующим образом:
if type(node) == Node.Leaf
Самая простая часть. Мы добрались до конечного узла. И либо это искомый узел — и мы его просто удалим, либо это не тот узел, который мы ищем.
На всякий случай напомню, что «удаление» — не совсем настоящее удаление. Старые узлы остаются в хранилище и доступны, если создать дерево от старого корня. А вот в дереве от нового корня мы этот узел уже найти не сможем.
if type(node) == Node.Extension
C Extension-узлом программа действий следующая:
В коде это выглядит так:
if type(node) == Node.Branch
Ну, почти. Если мы удаляем Branch-узел, то вещи становятся несколько запутанными…
Почему? Потому что Branch-узел одновременно может выступать в роли Leaf-узла (хранить значение) и в роли набора Extension-узлов (хранить ссылки на другие узлы).
Соответственно, в результате удаления данный узел может стать ненужным. Если в нём не останется ссылок, но останется значение — ему на замену придет Leaf-узел. Если в нём нет значения и останется одна ссылка — его нужно будет заменить на Extension-узел. Если же останется хотя бы одна ссылка и значение, либо не будет значения, но ссылок сохранится 2 и более — то Branch-узел будет просто обновлен.
И как нам это распутывать? Давайте разбираться:
Сперва разбираемся с удалением:
В коде это выглядит вот так:
В результате мы имеем _DeleteAction и можем начать разбираться с текущим узлом.
Для этого подсчитаем количество непустых веток. Возможные варианты:
Метод _build_new_node_from_last_branch находит ту самую единственную ветку и создает из неё новый узел.
Если нижележащий узел — Leaf или Extension, то нам нужно добавить в начало хранимого в них пути ниббл, соотвтетствующий индексу ветки.
Если же нижележащий узел — Branch, то нам нужно создать дополнительный Extension узел, путь в котором будет состоять из одного ниббла, а ссылка будет вести на Branch.
Остальное
Это было сложно, но мы справились.
Ах да… Ещё тесты. Но тут, к нашему счастью, за нас всё продумали авторы Ethereum и разместили стандартные тестовые векторы для проверки реализаций тут. Описывать, как их подключить, я, пожалуй не буду. Но созданная нами реализация их проходит, поверьте на слово 🙂
Результаты
К чему же это всё было?
Ну, во-первых, я не теряю надежды на то, что кто-то тоже будет биться с реализацией этой структуры, и моя статья ему поможет понять, что к чему. Если это произойдет — то ура, всё было не зря и я доволен.
Во-вторых, мне хотелось показать, что ситуации, когда сражаться на доселе неизведанном поле алгоритмов и структур данных приходится — возможны. Не скажу, что это повод мучать кандидатов задачками на skip list и interval tree, но способность их написать — навык, определенно, полезный.
В-третьих, изложение материала полностью соответствует тому, как я сам разбирался с вопросом и писал код в первый раз. Не исключаю вероятности, что это может быть интересно как описание процесса знакомства с чем-то с нуля.
В-четвертых, это же просто увлекательно — изучать нечто новое.
В любом случае, статья окончена, и если вы дочитали до этого момента — спасибо вам за терпение!
Арты были взяты со следующих сайтов: 1, 2, 3. Спасибо их авторам! А вам рекомендую посмотреть, там еще много красивого.