Деревья Меркле. Проверка “листьев” в ее составе

#алгоритм #хеширование #дерево #blockchain

Читаю интернет и не до конца понимаю одну вещь. Есть Дерево Меркля (или Меркле).
Допустим оно имеет N-количество отсортированных "листьев", представляющими блоки данных.
Как проверяется, что конкретный "блок" не находится в дереве?


    

Ответы

Ответ 1

Проверка принадлежности происходит очень просто - считается хеш блока, а потом просто
проверка с хешом во всех листьях. Если есть совпадение, дальше проверяется валидность
самого дерева, проходом от этого листа до корня дерева. Например, если это L2 на вашем
рисунке, тогда проверяется Hash(Hash(0-0), Hash(0-1)), и дальше корневой хеш: Hash(Hash(0),
Hash(1))

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

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

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

Пример с биткоин. Майнер непрерывно изменяет несколько байт в блоке, и считает хеш,
что бы получить хеш начинающийся с множества нулей. В это время приходят новые транзакции,
и нужно быстро пересчитать хеш в корне дерева (который является частью блока). Для
этого понадобится всего O(log n) операций пересчета хеша. Если майнер решил выкинуть
транзакцию с блока, и включить другую (с большей комиссией), все так же нужно O(log
n) пересчетов.