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

Главное

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

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

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

Кто и когда изобрел концепцию дерева Меркла?

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

Ученый предложил использовать бинарное хеш-дерево. Меркл также внес значительный вклад в развитие криптографии. Он известен благодаря публикации 1987 года «Цифровая подпись, основанная на обычной функции шифрования».

Для чего нужно дерево Меркла?

Централизованная система предоставляет данные из одного источника, на который полагаются все пользователи. Последний гарантирует корректность полученной информации.

Блокчейн является распределенной базой данных. Информация в ней хранится на множестве независимых узлов (нод). Нода не может принять сообщения от других участников без их проверки. Узлу необходимо определить, содержит ли блок корректные транзакции.

Для снижения вычислительных затрат можно использовать деревья Меркла. Они позволяют уменьшить объем загружаемых данных и оптимизировать их проверку благодаря хешированию.

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

Как работает дерево Меркла?

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

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

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

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

Как дерево Меркла используется в биткоине?

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

Для оптимизации вычислений узлы биткоина формируют заголовки. Они включают следующие элементы:

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

Заголовок не включает транзакции и занимает 80 байт. Поскольку он формируется каждые десять минут, объем данных увеличивается на 4,2 мегабайта за год.

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

1. Находятся хеши (идентификаторы) транзакций, включенных в блок: hash(L1), hash(L2), hash(L3) и так далее. Они формируют листья дерева.
2. На следующий уровень помещаются хеши от суммы двух соседних идентификаторов: hash(hash(L1) + hash(L2)). В бинарном дереве число узлов на каждом уровне должно быть четным. В ином случае хеш из последней ячейки дублируется и помещается в дополнительный элемент.
3. Процесс хеширования суммы данных повторяется до получения корня Меркла.

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

В августе 2017 года реализовано обновление протокола Segregated Witness. Последнее использует другое структурирование транзакционных данных, что позволяет уменьшить размер блока. Принятие обновления снизило нагрузку на блокчейн биткоина.

Какие преимущества дает дерево Меркла?

Хеш-деревья позволяют упростить проверку принадлежности транзакции определенному блоку и обеспечить целостность информации при ее передаче. Метод необходим для упрощенной верификации платежей. Сатоши Накамото предложил использовать SPV в white paper биткоина.

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

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

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

Метод SPV позволяет легкому клиенту эффективно взаимодействовать с блокчейном и снижает объем загружаемой информации. Например, размер блока с пятью транзакциями может составлять 500 килобайт, а доказательство Меркла занимает всего 140 байт.

Какое дерево хешей используется в Ethereum?

Бинарное дерево Меркла хорошо подходит для массива, представленного в виде списка. Его структура остается неизменной, что удобно для хеширования транзакций. В Ethereum применяется другой способ представления данных — префиксное дерево.

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

В отличие от биткоина, блокчейн Ethereum использует три хеш-дерева:

• транзакций;
• состояний;
• дерево, содержащее данные о результатах выполнения транзакций.

В заголовок блока входят три корневых хеша. Ethereum позволяет создавать легкие клиенты, способные выполнять базовый набор операций:

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

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

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

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

Корень дерева должен определяться исключительно данными и не зависеть от его параметров. Соответственно необходима возможность внесения обновлений в любом порядке.

Префиксное дерево позволяет решить указанные трудности. В Ethereum каждый элемент структуры имеет 16 дочерних. Этот подход оптимален для кодирования узлов в шестнадцатеричном формате.

В префиксном дереве для получения ключа необходимо указать подряд символы, соответствующие ветвям. Они определяют путь от корня до выбранного элемента. Значение ключа является динамическим, что позволяет добавлять или удалять новые узлы.

Что еще почитать?

Что такое обернутый токен?

Что такое блокчейн-оракул?

Что такое токен управления?

Что такое хардфорк?