Дерево Меркла (Merkle Tree) — хеш-дерево, полное двоичное дерево, структура которого используется для верификации данных и хранения транзакций в блокчейнах криптовалют. Данный алгоритм позволяет получить один хеш для большого количества фрагментов данных. Свое название алгортим получил благодаря структуре похожей на дерево и своему создателю Ральфу Мерклу.
Как работает Дерево Меркла?
Дерево Меркла заполняется снизу вверх, где к каждому блоку данных применяется хеширование, а полученные значения записываются в листья дерева. Блоки, которые находятся уровнем выше, заполняются значением суммы хешем двух дочерних блоков. Этот процесс повторяется до того момента, пока не будет получено верхнее значение или Корень Меркла (Merkle Root).
В блокчейне Bitcon используется хеш-функция SHA256. Другие блокчейны могут использовать другие принципы шифрования для создания Дерева Меркла.
Для чего нужно Дерево Меркла?
Информация в блокчейне распределена между множеством независимых улов. Обмен данными между такими узлами требует точной проверки полученных данных, что требует больших вычислительных мощностей. Благодаря использованию дерева Меркла, можно значительно снизить объем передаваемых данных и оптимизировать их проверку, снизив таким образом нагрузку на узлы.
Блок данных в Bitcoin хранит только значение Корня Меркла транзакций. После создания определенного количества блоков, данные о старых транзакциях можно удалять для экономии дискового пространства. Благодаря такому подходу, становится возможной упрощенная проверка транзакции, достаточно передавать только заголовок блока и путь к нужной транзакции.
Чем больше транзакций в блоке, тем выше эффективность данного алгоритма:
| Количество транзакций | Приблизительный размер блока | Размер пути в хешах | Размер пути в байтах |
|---|---|---|---|
| 16 транзакций | 4Kb | 4 хеша | 128 |
| 512 транзакций | 128Kb | 9 хешей | 288 |
| 2048 транзакций | 512Kb | 11 хешей | 352 |
| 65535 транзакций | 16Mb | 16 хешей | 512 |
История концепции
Концепция Дерева Меркла была предложена профессором Стэндфордского университета Ральфом Мерклом в 1979 году. Он предложил использование полного двоичного дерева. Кроме данной работы, Меркл известен по публикации «Цифровая подпись, основанная на обычной функции шифрования», которую он опубликовал в 1987 году.
Криптовалюты не являются первым применением Дерева Меркла, до появления Bitcoin, алгоритм уже использовался в p2p-сетях.
