Информатика · объяснение и практика

Дерево Меркла: как ветвь проверки связана с доверенным корнем

Доказательство включения в дерево Меркла: соседние хеши, порядок объединения и необходимость доверенного корня.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Безопасность и надёжность данных · Учебная карта

В маршруте Случайность, численные оценки и целостность · 10 тем

Главная мысль

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

Построим дерево четырёх самостоятельных записей

Пусть упорядочены записи «кедр», «липа», «ива», «дуб». Обозначим их хеши a, b, c, d, не подставляя короткие числа вместо криптографического алгоритма. Левый узел равен H(a,b), правый — H(c,d), корень — H(H(a,b),H(c,d)). Запятая здесь означает однозначное упорядоченное кодирование пары.

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

Восстановим ветвь для второй записи

Проверяющий получил «липа», левый сосед a и хеш всей правой половины q=H(c,d). Сам вычисляет b по правилам листа, затем p=H(a,b) и r=H(p,q). При этом положение второй записи определяет, что a стоит слева, а q — справа. Поменять местами аргументы без последствий нельзя.

Если r совпал с заранее доверенным корнем данного дерева, ветвь подтверждает включение указанной записи в этой позиции при криптографических предположениях схемы. Для четырёх листьев понадобились два соседних хеша, а не все четыре исходные записи. При другом размере правила обработки неполной ветви должны быть заданы отдельно.

Пример

Для «липа» путь: a слева, затем q справа. Проверка: H(H(a,b),q)=доверенный корень.

Путь содержит недостающие соседние узлы, а не список всех предков, уже вычисляемых из проверяемой записи.

Что такая проверка не обещает

Злоумышленник способен создать свой набор и его правильный корень. Если проверяющий без независимого доверия примет оба, математическое совпадение не подтвердит нужный исходный набор. Корень должен быть связан с проверенным источником, версией и при необходимости размером дерева.

Доказательство включения одной записи также не утверждает, что весь список законен, полон или осмыслен. Для журналов с добавлением отдельно проверяют согласованность версий; это другая задача. Полезная дисциплина ответа — назвать запись, позицию, версию корня и проверяемое свойство, не обещая от одной ветви больше, чем она доказывает.

От чтения к действию

А теперь — вы

В четырёхлистном дереве проверяют четвёртую запись с хешем d. Дан сосед c слева и хеш всей левой половины p. Как восстановить корень при сохранении порядка?

Частые вопросы

Нужно передавать все исходные записи?

Для одной ветви обычно достаточно соседних хешей по пути и необходимых метаданных; размер зависит от формы дерева.

Корень от отправителя уже является доказательством доверия?

Нет. Его происхождение и связь с нужным набором должны быть установлены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться