Дерево Меркла организует хеши данных в дерево, верхний хеш которого, корень Меркла, представляет зафиксированный набор. Каждый родитель вычисляется из дочерних узлов по установленным правилам. Изменение листа обычно меняет хеши вдоль его пути к корню.
Проверка одного элемента
Доказательство включения предоставляет соседние хеши для пересчёта этого пути, а не все элементы набора. В сбалансированном двоичном дереве с восемью листьями для одного листа обычно нужны три соседних хеша и сведения о расположении. Проверяющему также нужны сам элемент или его хеш и доверенный корень.
Использование в Bitcoin
Bitcoin фиксирует идентификаторы транзакций корнем Меркла в заголовке каждого блока. Правила построения задают порядок транзакций, попарное хеширование и дублирование при нечётном числе элементов на уровне. Другие системы могут использовать иные структуры деревьев и кодирование.
Что доказывает проверка
Действительное доказательство показывает, что элемент входит в набор, представленный эталонным корнем, при допущениях о стойкости хеша. Само по себе оно не доказывает действительность транзакции, текущую неизрасходованность выхода или финальность цепочки. Корень также не раскрывает все исходные данные: для полной проверки они должны быть доступны отдельно.