Найти тему

Откуда растут корни дерева Меркла в блокчейне?

Оглавление

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

Привет, это команда «Шард». Что это за дерево такое, зачем оно нужно и как человеку разобраться с этими растениями, не впав в депрессию от обилия сложных абстракций, математических доказательств и цифр? Попробуем с этим разобраться.

Зачем это решение нужно

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

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

Откуда взялось понятие «дерево Меркла»?

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

Дадим определение рассматриваемому понятию. Дерево Меркла — это структура данных, используемая в криптографии и информатике для проверки целостности хранимых или передаваемых данных.

С помощью дерева Меркла решаются задачи в разных областях знаний:

  • файловые системы используют их для проверки информации на наличие ошибок;
  • распределенные базы данных используют технологию для синхронизации записей;
  • в блокчейнах Bitcoin и Ethereum хэш-деревья позволяют проводить упрощенную верификацию при совершении транзакций.

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

Блокчейн сеть Bitcoin содержит цепочку блоков, которые создаются и записываются в сети последовательно один за одним.

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

По хэшам транзакций можно отслеживать движение своих средств в сети блокчейн. Платформа ШАРД позволяет производить поиск информации о транзакциях по txid (хэшу) в поисковой строке на главном экране.

-2

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

Для проверки корректности массива (функция верификации) и его целостности корневой хэш необходимо сравнить с эталонным значением. Фрагментами могут являться данные о транзакциях или части файлов.

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

Визуально структура Меркла выглядит как перевёрнутое дерево, а хэши блоков его ветви, транзакции - листья:

-3

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

  • принадлежат ли данные дереву Меркла;
  • являются ли достоверными данные являющихся частью набора данных, без сохранения всего набора данных (набор данных это и есть транзакции и блоки);
  • определенный набор данных (хэши транзакций) является валидным, поскольку включен в более крупный набор данных (хэш блока), не раскрывая ни полный набор данных, ни его подмножества.

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

В функционировании сети “Ethereum” тоже применяются деревья Меркл, однако несколько сложнее. Оно называется префиксное дерево, при этом базовые принципы схожие с сетью “Bitcoin”:

  • для каждой транзакции генерируется хэш;
  • затем выбираются пары и для каждой пары генерируется хэш;
  • таким образом, последний оставшийся хэш становится корневым.

Заголовок блока в сети содержит три дерева Меркла:

  • дерево для поддержания состояния;
  • дерево для поддержания транзакций;
  • дерево для поддержания квитанций;
  • каждый блок ссылается на хэш своего предыдущего блока.
-4

Префиксное дерево позволяет хранить информацию в ассоциативном массиве. Строки являются ключами, которые определяют положения его элементов. Для формирования структуры ветви дерева обозначаются различными символами так, чтобы ключ элемента однозначно его идентифицировал.

Сеть Ethereum позволяет создавать «легкие клиенты» (не требующие больших вычислений), на персональных компьютерах, ноутбуках и смартфонах способные выполнять базовый набор операций:

  • проверить наличие транзакции в блоке;
  • подтвердить существование определенного адреса;
  • определить баланс пользователя;
  • узнать результат выполнения операции или смарт-контракта.

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

* * *

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