Хабрахабр

Merkle Tree: ржавое и быстрое

image

Недавно открыл для себя язык Rust. Всем привет! Теперь решил копнуть немного глубже, для этого необходимо что-то посерьёзнее списка. О своих первых впечатлениях поделился в предыдущей статье. В этой статье я хочу: Выбор мой пал на дерево Меркла.

  • рассказать про эту структуру данных
  • посмотреть на то, что уже есть в Rust
  • предложить свою реализацию
  • сравнить производительность

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

В чём проблема

Цепочка блоков в сети имеет очень большой размер (для bitcoin это более 200 ГБ), и далеко не все узлы могут её выкачать. Дерево Меркла было изобретено ещё в 1979 году, но приобрело свою популярность благодаря blockchain. Тем не менее им нужно знать о факте включения той или иной транзакции в блок. Например, телефоны или кассовые аппараты. Для этого был придуман протокол SPV — Simplified Payment Verification.

Как устроено дерево

Для построения следующего уровня попарно берутся хеши соседних листьев, конкатенируются и вычисляется хеш от результата конкатенации, что проиллюстрировано на картинке в заголовке. Это бинарное дерево, листьями которого являются хеши любых объектов. Если убрать или добавить элемент, то корень изменится. Таким образом, корень дерева представляет собой хеш всех листьев.

Как работает дерево

Например, нас интересует транзакция Tx2, для неё доказательством будет (Hash3, Hash01). Имея дерево Меркла можно построить доказательство включения транзакции в блок как путь от хеша транзакции до корня. Клиент выкачивает только заголовок блока с его хешом. Этот механизм и используется в SPV. Затем делает проверку, для Tx2 это будет: Имея интересующую транзакцию, он запрашивает доказательство у узла содержащего всю цепочку.

hash(Hash01, hash(Hash2, Hash3)) = Root Hash

Этот подход делает невозможным подделку доказательства, т. Полученный результат сравнивается с корнем из заголовка блока. в этом случае не сойдётся результат проверки с содержимым заголовка. к.

Судя по Github, на данный момент 56, это больше чем на С и С++ вместе взятых. Rust молодой язык, но на нём уже написано много реализаций дерева Меркла. Хотя Go делает их как стоячих с 80 реализациями.

Для своего сравнения я выбрал эту имплементацию по количеству звёзд у репозитория.

е. Это дерево построено самым очевидным способом, т. Как я уже заметил, такой подход не вполне Rust-friendly. представляет собой граф объектов. Например, невозможно сделать двунаправленную связь от детей к родителям.

Если лист с нужным хешем найден, то путь до него и будет результатом. Построение доказательства происходит через поиск в глубину.

Что можно улучшить

Код моего vector-merkle-tree находится на Github. Делать просто (n+1)-ю реализацию мне было неинтересно, поэтому я подумал об оптимизации.

Хранение данных

Это решение будет намного лучше с точки зрения локальности данных: больше попаданий в кеш и лучше предзагркзка. Первое что приходит в голову, это переложить дерево на массив. Удобным фактом является то, что все хеши имеют одинаковую длину, т.к. Обход объектов, разбросанных по памяти, занимает больше времени. Дерево Меркла в массиве будет выглядеть так:
image вычисляются одним алгоритмом.

Доказательство

Таким образом, когда листа нет, не нужно обходить всё дерево, а если есть, то можно сразу перейти к нему и подняться до корня, строя доказательство. При инициализации дерева можно создать HashMap с индексами всех листьев. В своей имплементации я сделал HashMap опциональным.

Конкатенация и хеширование

Всё ведь и так понятно — берём два хеша, склеиваем их и вычисляем новый хеш. Казалось бы, что тут можно улучшить? hash(H0, H1) ≠ hash(H1, H0). Но дело в том, что эта функция некоммутативная, т.е. Это делает алгоритм сложнее для реализации, и добавляет необходимость хранить лишние данные. Из-за этого при построении доказательства нужно запоминать с какой стороны находится соседний узел. Для примера я приводил Tx2, c учётом коммутативности проверка будет выглядеть так: Всё очень легко исправить, достаточно просто отсортировать два узла перед хешированием.

hash(hash(Hash2, Hash3), Hash01) = Root Hash

Когда не надо заботиться о порядке, алгоритм проверки выглядит как простая свёртка массива:

pub fn validate(&self, proof: &Vec<&[u8]>) -> bool { proof[2..].iter() .fold( get_pair_hash(proof[0], proof[1], self.algo), |a, b| get_pair_hash(a.as_ref(), b, self.algo) ).as_ref() == self.get_root()
}

Нулевой элемент это хеш искомого объекта, первый — его сосед.

Для этих целей я использовал фреймворк criterion. Рассказ был бы неполным без сравнения производительности, которое заняло у меня в несколько раз больше времени, чем реализация самого дерева. Всё тестирование происходит через интерфейс TreeWrapper, который был реализован для обоих подопытных: Исходники самих тестов находятся тут.

pub trait TreeWrapper<V> { fn create(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn find(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String); fn validate(&self, c: &mut Criterion, counts: Vec<usize>, data: Vec<Vec<V>>, title: String);
}

Тут я не собираюсь сравнивать разные библиотеки. Оба дерева работают с одной криптографией ring. Взял самую распространённую.

Деревья сравниваются на массивах различной длины: (500, 1000, 1500, 2000, 2500 3000). В качестве объектов хеширования используются случайно сгенерированные строки. 2500 — 3000 это примерное число транзакций в блоке биткоина на данный момент.

Т. На всех графиках по оси X — число элементов массива (или количество транзакций в блоке), по Y — среднее время на выполнение операции в микросекундах. чем больше, тем хуже. е.

Создание дерева

Для массива с 500 элементами в 1,5 раза, а для 3000 элементов уже в 3,6 раза. Хранение всех данных дерева в одном массиве сильно превосходит по производительности граф объектов. Чётко виден нелинейный характер зависимости сложности от объёма входных данных в стандартной реализации.

Заполнение дополнительной структуры данных добавляет где-то 20%, но зато позволяет намного быстрее искать объекты при построении доказательства.
image Так же в сравнение я добавил два варианта векторного дерева: с HashMap и без него.

Построение доказательства

С увеличением входных данных, она только усугубляется. Тут видна явная неэффективность поиска в глубину. Если данные предварительно захешированы, то время операции практически не зависит от числа элементов. Важно понимать, что искомыми объектам являются листы, поэтому сложности log(n) быть не может. Без хеширования, сложность растет линейно и заключается в поиске перебором.
image

Валидация доказательства

Она не зависит от структуры дерева, т.к. Это последняя операция. Я полагаю, что основную сложность тут составляет вычисление хеша.
image работает с результатом построения доказательства.

  • Способ хранения данных сильно влияет на производительность. Когда всё в одном массиве — это намного быстрее. И сериализовать такую структуру будет очень просто. Общий объём кода тоже уменьшается.
  • Конкатенация узлов с сортировкой сильно упрощает код, но не делает его быстрее.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть