В различных статьях, посвященных криптовалютам, можно встретить такое определение, как дерево Меркла. Особенно часто данное понятие мелькает в WhitePaper ICO. В данной статье мы постараемся доступно объяснить, что же такое дерево Меркла и почему оно так важно для цифровых валют.
Что такое дерево Меркла?
Дерево Меркла – это одна из разновидностей хеш-функций, позволяющих преобразовать любой массив данных в строку определенного размера. Проще говоря, на входе функция получает какие-то данные, которые затем трансформируются в череду цифр двоичного кода. Этот набор цифр всегда уникален и не повторяется для различных входных данных.
Дерево Меркла часто называют деревом хеша. Для него свойственны следующие особенности:
- С использованием дерева Меркла можно присваивать уникальный идентификатор любому документу.
- Дерево Меркла способно участвовать в проверку целостности цифровых документов.
- С помощью такой хеш-функции можно восстанавливать утраченные файлы.
Хешевое дерево известно уже достаточно давно. Его разработал Ральф Меркл еще в 1979 году. Если говорить о его структуре, то она на самом деле напоминает дерево. В узлах системы располагаются хеши, полученные от дочерних узлов. В конечных узлах скрываются хеши самих блоков данных.
Если рассмотреть такой алгоритм в более понятном ключе, то работает он следующим образом:
- В систему поступает большое количество данных (Data block 1 — Data block 4).
- Из каждого кластера данных формируются хеши, которые затем опять хешируются.
- Повторное хеширование продолжается до тех пор, пока в системе не останется всего одно значение хеша – корень Меркла.
Таким образом, можно преобразовать сколько угодно большой объем данный, сведя его к одному единственному хешу.
Как дерево хешей используется в Bitcoin?
Обычно в файловых системах деревья хешей используются для проверки данных на ошибки, а биткоине – для возможности проведения упрощенной верификации платежей (SPV). Клиенты, использующие такую функцию, называют легкими – они хранят только заголовки блоков, а не полное их содержимое.
Легкие клиенты для верификации транзакций не пересчитывают все хеши, а запрашивают только доказательство Меркла. В его состав входит тот самый корень Меркла и ветку, которые содержат хеши от самой транзакции до корня. Это позволяет не использовать весь объем информации о транзакциях, а обращаться к конкретной транзакции.
Подобный механизм, использующий дерево Меркла, позволяет существенно снизить нагрузку на сеть и ускорить процесс проведения. Например, 5 переводов максимального размера в сумме весят около 500 килобайт, при этом дерево Меркла при таких же условиях будет иметь размер не более 140 килобайт.
Стоит отметить, что деревья хешей используются не только в биткоине, но и ряде других криптовалют. Например, в Ethereum применяется префиксное дерево Меркла. Также существуют и другие аналогичные структуры с некоторыми особенностями и поправками. Об этом мы поговорим в другой публикации.
140 байт, а не килобайт.