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

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

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

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

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

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

История происхождения и понятие

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

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

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

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

• распределенные базы данных используют технологию для синхронизации записей;

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

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

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

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

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

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

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

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

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

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

• принадлежат ли данные дереву Меркла;

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

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

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

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

• для каждой транзакции генерируется хэш;

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

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

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

• дерево для поддержания состояния

• дерево для поддержания транзакций

• дерево для поддержания квитанций

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

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

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

• проверить наличие транзакции в блоке;

• подтвердить существование определенного адреса;

• определить баланс пользователя;

• узнать результат выполнения операции или смарт-контракта.

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

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