Деревья Меркла широко используются в Биткойне и Эфириуме.
Давайте поговорим о них!
Кто они такие?
Дерево Меркла – это структура данных, предназначенная для доказательства включений.
Как создать дерево Меркла?
Чтобы создать дерево Меркла, возьмите упорядоченный список и хешируйте его элементы с помощью хеш-функции (например, SHA256).
Возьмем пример.
У нас есть упорядоченный список биткойн-транзакций с именами A, B, C и D.
Мы объединим две последующие транзакции и хэшируем их, чтобы получить родительский объект Merkle.
Этот родитель будет представлять оба хэша транзакции.
Merkle Parent = хэш объединения левой транзакции + правой транзакции)
Родители Merkle объединяются и хешируются для достижения Корня Merkle.
Merkle Root = Хэш конкатенации левого родителя Merkle + правого родителя Merkle)
Что произойдет, если в упорядоченном списке будет нечетное количество транзакций?
- Вы продублируете последний элемент в списке
- Затем добавьте его в конец списка, чтобы создать четное количество элементов для последующего хеширования.
Возьмем пример.
У нас есть упорядоченный список биткойн-транзакций с именами A, B и C.
Дерево Меркла будет выглядеть так.
Компоненты деревьев Меркла
- Меркл Рут
- Родители Меркла
- Листья: Нижний ряд хэшей
- Внутренние узлы: все узлы, кроме листьев
Идея деревьев Merkle
Идея их использования заключается в том, чтобы найти один хеш, который может представлять весь упорядоченный список.
Этот единственный хэш и есть Merkle Root.
Как они используются в Биткойне/Эфириуме?
- Допустим, вы покупаете кофе за биткойны.
- Вы отправите биткойны на кошелек владельца кофейни.
- Эта транзакция должна быть проверена, а затем добавлена в блокчейн.
- Вы получите свой кофе, как только это произойдет.
За кулисами кошелек владельца кофейни должен подтвердить, что эта транзакция действительна и что она была проверена и добавлена в блок в блокчейне с использованием Proof Of Work.
- В этом легко убедиться, когда у кошелька есть доступ ко всему блокчейну, содержащему данные всех предыдущих действительных транзакций.
- Блокчейн Биткойн/Эфириум занимает несколько сотен ГБ.
- При хранении на устройстве с кошельком это может занимать много места.
- Вместо того, чтобы загружать всю цепочку блоков, можно загрузить заголовок блока (представленный как Merkle Root).
- Поскольку этот заголовок блока добывается с помощью Proof of Work, владелец кофейни может быть уверен, что эта транзакция действительна.
- Это называется Проверка доказательством включения.
Подробное использование дерева Меркла
Допустим, интересующая вас транзакция — C.
- Вам будут предоставлены данные Hash D и Merkle Parent of AB (предоставленные полным узлом)
- С помощью этих данных вы можете вычислить корень Меркла из ABCD.
- Сравните это с заголовком блока, подтвержденным Proof-of-work.
- Если они совпадают, то транзакция действительна.
И да, тогда можно пить кофе!
Возвращаясь к первому утверждению статьи,
Дерево Меркла – это структура данных, предназначенная для доказательства включений.
Надеюсь, теперь вы это хорошо понимаете!
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Больше контента в публикации Level Up Coding.
Подписывайтесь: Twitter, LinkedIn, Newsletter
Level Up меняет рекрутинг технических специалистов 👉 Присоединяйтесь к нашему коллективу талантов