Что такое дерево Меркла и как оно связано с криптовалютами?

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

Дерево Меркла. Источник: Gocoding

Зачем нужно хеш-дерево?

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

Ральф Меркл. Источник: Alchetron

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

Как организовано дерево Меркла в Биткоине?

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

Все транзакции в блоке Биткоина — это строки в шестнадцатеричном формате, они хешируются и представляются в виде идентификаторов транзакций (txid). Все txid в блоке хешируются, пока не будет получено единое хеш-значение блока. В процессе происходит построение дерева Меркла:

1. сначала вычисляются сами txid (Transaction ID), то есть хеши транзакций;
2. затем вычисляются хеши от суммы хешей транзакций. Дерево Меркла является бинарным, то есть при каждом новом этапе хеширования количество элементов дерева должно быть чётным. Если в блоке нечётное количество транзакций, хеш последней из них дублируется и складывается сам с собой;
3. из хешей суммы хешей транзакций вычисляются новые хеши. И так далее, пока не будет получен единый хеш (merkle root). Он указывается в заголовке блока.

Дерево Меркла в Биткоине. Источник: Github

Принцип работы дерева Меркла

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

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

Аналоги дерева Меркла

В статье рассмотрен самый простой бинарный вариант концепции, изобретённой Ральфом Мерклом. В нём каждый «родительский» хеш имеет два «наследника». В Биткоине хеш-дерево строится с использованием двойного хеширования SHA-256.

Antminer S9. Источник: Bitcoinist

Существуют более сложные интерпретации концепции. К примеру, в Эфириуме используется префиксное дерево Меркла. В каждом заголовке блока Эфириума содержится сразу три таких дерева: для транзакций, информации об их выполнении и состоянии. В отличие от бинарного дерева, значение узла префиксного зависит ещё и от соединений с другими узлами. Таким образом, значение является динамическим, а не фиксированным, то есть оно может изменяться без необходимости пересчитывать все хеши дерева.

Дерево Меркла в Эфириуме. Источник: Ethereum Stack Exchange

Ещё больше интересной информации о блокчейне можно найти в нашем крипточате. Также не забудьте подписаться на Два Биткоина в Яндекс Дзене.

ПОДПИСЫВАЙТЕСЬ НА НАШ КАНАЛ В ТЕЛЕГРАМЕ. БЛОКЧЕЙН — ЭТО ПРОСТО!