Дерево Меркла

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

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

Их также называют «двоичными хеш-деревьями».

Разрушение Дерева Меркла

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

Визуально эта структура напоминает дерево. На диаграмме ниже «T» обозначает транзакцию, «H» — хэш. Обратите внимание, что изображение сильно упрощено; средний блок содержит более 500 транзакций, а не восемь.

Хеши в нижней строке называются «листьями», промежуточные хеши — «ветвями», а хеш-значения вверху — «корнем». Корень Меркла данного блока сохраняется в заголовке: например, корень Меркла блока # 482819 — это e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Корень объединяется с другой информацией (версия программного обеспечения, хэш предыдущего блока, временная метка, цель сложности и одноразовый номер), а затем проходит через хеш-функцию для получения уникального хеш-кода блока: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 # 481928 в случае блока. Фактически, этот хеш включается не в соответствующий блок, а в следующий; он отличается от корня Меркла.

Дерево Меркла полезно, потому что оно позволяет пользователям проверять конкретную транзакцию без загрузки всей цепочки блоков (более 130 гигабайт на конец августа 2017 года). Например, предположим, что вы хотите убедиться, что транзакция T D  включена в блок на диаграмме выше. Если у вас есть корневой хеш (H ABCDEFGH ), процесс похож на игру в судоку: вы запрашиваете сеть о H D, и она возвращает H C, H AB и H EFGH. Дерево Меркла позволяет вам проверить, что все учтено с помощью трех хешей: с учетом H AB, H C, H EFGH и корня H ABCDEFGH, H D  (единственный отсутствующий хеш) должен присутствовать в данных.

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