Дерево Меркла — полная структура данных в виде дерева, в листовые вершинах которого находятся хеши от блоков данных, а внутренние вершины содержат хеши от сложения значений в дочерних вершинах. Это связывает все элементы с информацией между собой. В итоге всё выглядит так.
Дерево Меркла. Источник: Gocoding
Хеш — результат преобразования хеш-функции, то есть функции, которая преобразовывает массив входных данных произвольной длины в выходную строку установленной длины в соответствии с определённым алгоритмом.
Содержание
Зачем нужно хеш-дерево?
В централизованной системе правдивость информации не является проблемой, так как все её составляющие полагаются на один централизованный узел. Вам не нужно беспокоиться о подлинности денег, когда вы получаете перевод на свой банковский счёт.
Ральф Меркл. Источник: Alchetron
А вот в децентрализованной сети всё не так просто. Каждый её узел сам отвечает за правдивость передаваемой информации, поэтому подтвердить подлинность её полного объёма очень проблематично — как минимум из-за количества всех транзакций в сети. По крайней мере, без дерева Меркла. Последнее позволяет оптимизировать процесс представления данных с помощью хеширования.
Как организовано дерево Меркла в Биткоине?
Хеш-функция — это процесс преобразования входных данных в битовую строку установленной длинны. Полученная строка, хеш, очень сильно зависит от массива входящих данных. Если даже один символ из всего массива будет изменён, полученный хеш примет совсем другое значение.
Все транзакции в блоке Биткоина — это строки в шестнадцатеричном формате, они хешируются и представляются в виде идентификаторов транзакций (txid). Все txid в блоке хешируются, пока не будет получено единое хеш-значение блока. В процессе происходит построение дерева Меркла:
- сначала вычисляются сами txid (Transaction ID), то есть хеши транзакций;
- затем вычисляются хеши от суммы хешей транзакций. Дерево Меркла является бинарным, то есть при каждом новом этапе хеширования количество элементов дерева должно быть чётным. Если в блоке нечётное количество транзакций, хеш последней из них дублируется и складывается сам с собой;
- из хешей суммы хешей транзакций вычисляются новые хеши. И так далее, пока не будет получен единый хеш (merkle root). Он указывается в заголовке блока.
Дерево Меркла в Биткоине. Источник: Github
Визуально процесс составления единого хеша напоминает дерево, от вершины которого расходятся "ветки" с хешами. Собственно, отсюда и название.
Принцип работы дерева Меркла
Процесс составления дерева Меркла похож на «свёртывание данных». Благодаря ему огромный список транзакций или любой другой массив информации можно представить всего одной строкой. Вся прелесть в том, что если где-нибудь в списке этих самых транзакций мы поменяем всего один символ, следующий «уровень» дерева будет уже совсем другим и конечный хеш — то есть «верхушка» дерева — тоже поменяется.
Иными словами, в блок нельзя подставить другую транзакцию или поменять данные уже существующих. Вот почему дерево Меркла считается эффективным способом записи транзакций в блокчейн. Существует также понятие Merkle Proof — это принцип проверки правдивости информации с помощью хешей. Вместо изучения всего массива данных достаточно изучить отдельные хеши в дереве, что сильно снижает затраты вычислительной мощности на весь процесс.
Аналоги дерева Меркла
В статье рассмотрен самый простой бинарный вариант концепции, изобретённой Ральфом Мерклом. В нём каждый «родительский» хеш имеет два «наследника». В Биткоине хеш-дерево строится с использованием двойного хеширования SHA-256.
Вы могли слышать "SHA-256" при выборе ASIC-майнеров Биткоина, которые работают именно на этом алгоритме.
Antminer S9. Источник: Bitcoinist
Существуют более сложные интерпретации концепции. К примеру, в Эфириуме используется префиксное дерево Меркла. В каждом заголовке блока Эфириума содержится сразу три таких дерева: для транзакций, информации об их выполнении и состоянии. В отличие от бинарного дерева, значение узла префиксного зависит ещё и от соединений с другими узлами. Таким образом, значение является динамическим, а не фиксированным, то есть оно может изменяться без необходимости пересчитывать все хеши дерева.
Дерево Меркла в Эфириуме. Источник: Ethereum Stack Exchange
Ещё больше интересной информации о блокчейне можно найти в нашем крипточате. Также не забудьте подписаться на Два Биткоина в Яндекс Дзене.
ПОДПИСЫВАЙТЕСЬ НА НАШ КАНАЛ В ТЕЛЕГРАМЕ. БЛОКЧЕЙН — ЭТО ПРОСТО!
