Дерево Меркла в блокчейне

Дерево Меркла в блокчейне

В данной статье разберемся, что такое дерево Меркла (Merkle Tree) и в чем его преимущества. Также мы рассмотрим доказательство Меркла и почему применяют дерево Меркла в блокчейне.

Что такое дерево Меркла?

Данные/транзакции в блоке не хранятся в виде обычного текста. Вместо этого они хранятся в структуре данных, называемой деревом Меркла. Другими словами, дерево Меркла служит сводкой всех транзакций в блоке. Каждая транзакция в блоке уникальным образом хешируется хеш-функциями MD5, BLAKE2, SHA-1, SHA-256 для получения цифрового отпечатка всего набора транзакций. Каждая пара транзакций хешируется вместе хеш-функцией, и этот процесс продолжается до тех пор, пока не будет получен один хеш для всего блока.

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

Дерево Меркла транзакций A, B, C и D. Хеш ABCD является корнем/корневым хешем Меркла
Дерево Меркла транзакций A, B, C и D. Хеш ABCD является корнем/корневым хешем Меркла

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

Чтобы было проще, давайте разберем дерево Меркле на примере.

Предположим, что в блоке четыре транзакции, как показано на рисунке выше. Каждая из четырех транзакций (A, B, C и D) имеет уникальный хеш (Hash A, Hash B, Hash C и Hash D). Затем каждая пара этих хешированных транзакций объединяется вместе для создания другого хеша. В этом случае хешированная транзакция A объединяется с хешированной транзакцией B для создания нового хеша AB. С другой стороны, хешированная транзакция C объединяется с хешированной транзакцией D для создания нового хеша CD. Хеш AB и Хеш CD являются ветвями дерева Меркла. Затем хеш AB и хеш CD группируются вместе хеш-функцией для получения хеша ABCD, который является корнем/корневым хешем дерева Меркла. Корень Меркла затем сохраняется в заголовке блока.

Но теперь возникает вопрос, что такое этот заголовок блока?

Блок состоит из заголовка и тела. Заголовок блока содержит корень Меркла, метку времени, номер версии блока (указывает, какому набору правил проверки блока следовать), цель сложности, Nonce (однократно используемое число) и предыдущий хеш. С другой стороны, тело блока содержит все подтвержденные транзакции внутри блока.

Корень Меркла хранится в заголовке блока
Корень Меркла хранится в заголовке блока

Дерево Меркла с нечетным количеством транзакций

Приведенный выше пример иллюстрирует фундаментальный случай дерева Меркла. На каждом уровне имеется нужное количество листьев Меркла для формирования точных пар.

Но что произойдет, если у вас будет нечетное количество транзакций? Ведь это приведет к образованию нечетного количества листьев Меркла?

Например, предположим, что в блоке есть пять транзакций. Каждая из пяти транзакций (A, B, C, D и E) будет иметь уникальный хеш (Hash A, Hash B, Hash C, Hash D и Hash E). Пара хешированных транзакций A и B хешируется для получения хеша AB. Аналогично, пара хешированных транзакций C и D хешируется для получения хеша CD. Но хешированная транзакция E остается без пары для хеширования в новую ветвь.

Поскольку деревья Меркла являются бинарными по своей природе, для их работы необходимо, чтобы узлы листьев были четными. Поэтому, если в нем оказывается непарный хеш, то этот хеш копируется и объединяется в пару с самим собой. В нашем примере хеш E дублируется, чтобы соединиться с самим собой и образовать хеш EE. После этого хеш AB и хеш CD группируются и хешируются для создания нового хеша ABCD. С другой стороны, хеш EE дублируется и соединяется с самим собой, чтобы образовать хеш EEEE. Хеши ABCD и EEEE далее группируются и хешируются для получения одного хеша, т.е. корня Меркла.

Дерево Меркла с транзакциями A, B, C, D и E. Хеш ABCDEEEE является корнем/корневым хешем Меркла
Дерево Меркла с транзакциями A, B, C, D и E. Хеш ABCDEEEE является корнем/корневым хешем Меркла

Этот корневой хеш блока затем используется для поиска уникального действительного хеша блока с ведущими нулями.

Например, корень Меркла блока #72608 — a1c6d67c992a70fca66188e178d9ca7c20d5c775393948f19955be7f0952c0f.

Затем корневой хеш объединяется с другой информацией о блоке (номер блока, хеш предыдущего блока, метка времени и nonce) и прогоняется через хеш-функцию для получения уникального и достоверного хеша блока с ведущими нулями: 00001a03b7328189f5f7154681c5827a1b2fce2fcb5301a8e412e22ea9a7859.

Как только блок получает правильный хеш, он становится частью блокчейна, и в дальнейшем к этому блоку могут быть добавлены новые блоки.

Преимущества дерева Меркла

  • Каждый блок имеет уникальное хеш-значение, вычисляемое по корню Меркла. Блок также содержит хеш предыдущего блока, таким образом связывая один блок с другим в блокчейне. Если в какой-либо транзакции происходит изменение, то хеш этой транзакции меняется. Это изменение каскадом доходит до корня Меркла, изменяя значение корня и тем самым делая блок недействительным. Затем это отражается на последующем блоке, что приводит к изменению его хеша и, таким образом, делает недействительным весь блокчейн. Таким образом, дерево Меркла создает неизменяемую запись о транзакциях в блоке.
  • Блокчейн обычно состоит из сотен тысяч блоков, и каждый блок может содержать до нескольких тысяч транзакций, что делает пространство памяти и вычислительную мощность двумя большими проблемами при проверке данных. Если бы в блокчейне не было концепции деревьев Меркла, то каждый узел сети (нода) должен был бы хранить полную копию каждой транзакции, когда-либо происходившей в блокчейне. При подтверждении транзакции узел должен был бы сравнивать каждую запись построчно, чтобы убедиться, что его собственные записи точно совпадают с записями сети. Если бы между записями было какое-либо расхождение, это могло бы поставить под угрозу безопасность сети. Поэтому компьютер, используемый для проверки данных, должен был обладать гораздо большей вычислительной мощностью, чтобы сравнить записи и убедиться, что в них не было изменений. С другой стороны, деревья Меркла решают эту проблему, значительно сокращая объем данных, которые необходимо хранить для целей проверки. Они хешируют все записи в реестре, что эффективно отделяет доказательство данных от самих данных. Пользователи могут проверять отдельные блоки, а также проверять транзакции с помощью хешей. Таким образом, уменьшается количество вычислительной мощности, необходимой для проверки транзакций.
  • Деревья Меркла помогают исключить модификацию записей о транзакциях и двойные траты в блокчейне. Например, если кто-то попытается взломать запись в блокчейне, чтобы создать впечатление, что у него больше криптовалюты, чем есть на самом деле, любая такая ложная запись не будет соответствовать остальным хешам в дереве Меркла и, следовательно, будет отклонена сетью. Это происходит потому, что когда транзакция происходит в блокчейне, она не хранится как таковая. Вместо этого она проверяется. Транзакция хешируется хеш-функцией, а затем ее хеш сверяется со всеми остальными хешами в блокчейне, чтобы доказать, что ничего не было изменено или подделано.

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

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

Доказательства Меркла позволяют проверить конкретную транзакцию/содержание в большом массиве данных. В системах блокчейн существует два типа узлов:

  1. Узлы, хранящие полную историю блокчейна, называются «полными узлами».
  2. А другие узлы называются «облегченными нодами». Облегченная нода содержит только заголовки блоков (содержащие корень Меркла) вместо всей истории транзакций. Облегченная нода может проверять только транзакции, включенные в блок, без необходимости загрузки всего блокчейна.

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

Предположим, что облегченная нода хочет проверить, была ли транзакция D потеряна или подделана. Для этого полный узел посылает хеш-значения Hash C, Hash AB, Hash EFGH и корень Меркла на облегченную ноду. Сначала облегченная нода находит хеш транзакции D, т.е. Hash D, используя хеш-функцию. Затем Hash D вместе со значениями Hash C, Hash AB и Hash EFGH пересчитывается для создания корня Меркла/корневого хеша. Если вычисленный корень Меркла и оригинальный корень Меркла совпадают, то можно убедиться, что хеш D является подлинным листом дерева Меркла, и, таким образом, транзакция D является частью дерева Меркла. Напротив, если вычисленный корень Меркла и оригинальный корень Меркла не совпадают, то можно утверждать, что транзакция D была подделана.

Доказательство Меркла для транзакции D
Доказательство Меркла для транзакции D

Понравилась статья? Поделитесь в соцсетях

Похожие записи

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

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