Дерево Меркля - это структура данных, которая используется в приложениях информатики. В биткойнах и других криптовалютах деревья Merkle служат для более эффективного и безопасного кодирования данных блокчейна.
Их также называют «бинарными хеш-деревьями».
Разрушение дерева Меркле
В блокчейне биткойна блок транзакций запускается с помощью алгоритма генерации хэша, который представляет собой строку из цифр и букв, которую можно использовать для проверки того, что данный набор данных совпадает с исходным набором транзакций, но не получить оригинальный набор транзакций. Однако программное обеспечение Биткойн не выполняет весь блок данных транзакций, представляющих в среднем 10-минутные транзакции, одновременно через хэш-функцию. Скорее каждая транзакция хэшируется, затем каждая пара транзакций объединяется и хэшируется вместе и так далее, пока не будет одного хэша для всего блока. (Если существует нечетное количество транзакций, одна транзакция удваивается, и ее хэш объединяется с самим собой.)
Визуализированная, эта структура напоминает дерево. На приведенной ниже диаграмме буквой T обозначена транзакция, а буквой H - хеш. Обратите внимание, что изображение очень упрощено; средний блок содержит более 500 транзакций, а не восемь.
Хэши в нижнем ряду называются «листьями», промежуточные хэши - «ветвями», а хэш в верхней части - «корнем». Корень Merkle данного блока хранится в заголовке: например, корень Merkle блока # 482819 - это e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Корень объединяется с другой информацией (версия программного обеспечения, хэш предыдущего блока, временная метка, цель сложности и одноразовый номер), а затем проходит через хэш-функцию для создания уникального хэша блока: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 в блоке case в блоке 4828, Этот хеш фактически не включен в соответствующий блок, но следующий; это отличается от корня Меркле.
Дерево Merkle полезно, потому что оно позволяет пользователям проверять определенную транзакцию, не загружая весь блокчейн (более 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 года под названием «Цифровая подпись на основе обычной функции шифрования». Меркл также изобрел криптографическое хеширование.
