что такое дерево меркла
Merkle Tree Proof: Дерево Меркла В Эфире и Блокчейне
Деревья Меркла зарекомендовали себя очень полезными в ряде приложений информатики, они невероятно ценны в блокчейнах. 
Как работают деревья Меркла?
Предположим, вы хотите скачать большой файл. При использовании программного обеспечения с открытым исходным кодом вы обычно хотите проверить, соответствует ли хэш загруженного файла хешу, опубликованному разработчиками. Если да, то вы знаете, что файл на вашем компьютере точно такой же, как и у них.
Если хеши не совпадают, у вас проблема. Вы либо загрузили вредоносный файл, замаскированный под программное обеспечение, либо он загрузился некорректно и, следовательно, не будет работать. В последнем случае вы, вероятно, не будете слишком счастливы, если вам придется некоторое время подождать, пока файл загрузится. Теперь вам нужно перезапустить процесс и надеяться, что он снова не испортится.
Вы думаете, если бы существовал более простой способ сделать проверить целостность файла?
К счастью, именно здесь на помощь приходят деревья Меркла. С помощью одного из них ваш файл разбивается на части. Если бы это был файл размером 50 ГБ, вы могли бы разделить его на сто частей, каждый размером 0,5 ГБ. Затем он будет загружен по частям. По сути, это то, что вы делаете, когда загружаете торрент-файлы.
В этом случае ваш источник предоставит вам хеш, известный как корень Меркла (англ. Merkle Roots). Этот единственный хеш представляет собой представление каждого фрагмента данных, из которого состоит ваш файл. Но корень Меркла значительно упрощает проверку данных.
Мы передаем каждый из восьми фрагментов через хеш-функцию, чтобы получить их хеш-коды.
Хорошо, у нас есть кое-что, что имеет немного больше смысла. У нас есть хэш всех фрагментов, поэтому, если один из них неисправен, мы узнаем, сравнив его с исходным, верно?
Возможно, но это тоже невероятно неэффективно. Если в вашем файле тысячи фрагментов, действительно ли вы собираетесь хешировать их все и тщательно сравнивать результаты?
Структура выглядит как перевернутое дерево. В нижнем ряду у нас есть листья, из которых складываются узлы и, наконец, корень.
Оставайтесь на связи.
Добавляйте этот блог в закладки потому, что здесь самая правдивая и экспертная информация!
Антон Састрпцин
Является старшим аналитиком фондового рынка ММВБ. Работает в сфере финансовых услуг с 2014 года.
Дата изменения: 17.06.2021
Поделиться
Вам также может понравиться
Феникс Майнер Скачать 5.9b (Ethereum AMD/NVIDIA) [2021]
Африка и Криптовалюта: Близится Запрет [Причины]
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, делающим первые шаги в блокчейн-разработке, а также тем, кто уже пробовал создавать блокчейн-решения.
Узнать дополнительную информацию о мероприятии и спикерах, а также зарегистрироваться на событие можно по ссылке.
Что такое дерево Меркла и как они используются в криптовалютах?
В различных статьях, посвященных криптовалютам, можно встретить такое определение, как дерево Меркла. Особенно часто данное понятие мелькает в WhitePaper ICO. В данной статье мы постараемся доступно объяснить, что же такое дерево Меркла и почему оно так важно для цифровых валют.
Что такое дерево Меркла?
Дерево Меркла – это одна из разновидностей хеш-функций, позволяющих преобразовать любой массив данных в строку определенного размера. Проще говоря, на входе функция получает какие-то данные, которые затем трансформируются в череду цифр двоичного кода. Этот набор цифр всегда уникален и не повторяется для различных входных данных.
Дерево Меркла часто называют деревом хеша. Для него свойственны следующие особенности:
Хешевое дерево известно уже достаточно давно. Его разработал Ральф Меркл еще в 1979 году. Если говорить о его структуре, то она на самом деле напоминает дерево. В узлах системы располагаются хеши, полученные от дочерних узлов. В конечных узлах скрываются хеши самих блоков данных.
Если рассмотреть такой алгоритм в более понятном ключе, то работает он следующим образом:
Таким образом, можно преобразовать сколько угодно большой объем данный, сведя его к одному единственному хешу.
Как дерево хешей используется в Bitcoin?
Обычно в файловых системах деревья хешей используются для проверки данных на ошибки, а биткоине – для возможности проведения упрощенной верификации платежей (SPV). Клиенты, использующие такую функцию, называют легкими – они хранят только заголовки блоков, а не полное их содержимое.
Легкие клиенты для верификации транзакций не пересчитывают все хеши, а запрашивают только доказательство Меркла. В его состав входит тот самый корень Меркла и ветку, которые содержат хеши от самой транзакции до корня. Это позволяет не использовать весь объем информации о транзакциях, а обращаться к конкретной транзакции.
Подобный механизм, использующий дерево Меркла, позволяет существенно снизить нагрузку на сеть и ускорить процесс проведения. Например, 5 переводов максимального размера в сумме весят около 500 килобайт, при этом дерево Меркла при таких же условиях будет иметь размер не более 140 килобайт.
Стоит отметить, что деревья хешей используются не только в биткоине, но и ряде других криптовалют. Например, в Ethereum применяется префиксное дерево Меркла. Также существуют и другие аналогичные структуры с некоторыми особенностями и поправками. Об этом мы поговорим в другой публикации.