Перейти к содержимому
ecdsa.com

Дерево Меркла

Двоичное дерево хешей, в котором каждый внутренний узел содержит хеш двух своих потомков, поэтому один корневой хеш фиксирует все листья, а включение элемента или то, что дерево только дополнялось, можно подтвердить доказательством логарифмического размера.
Другие написанияhash treeMerkle rootinclusion proofconsistency proof

Certificate Transparency (RFC 6962, § 2.1; RFC 9162, § 2.1) определяет хеширование, которое используется в большинстве журналов прозрачности: листья вычисляются как SHA-256(0x00 ‖ data), а узлы — как SHA-256(0x01 ‖ left ‖ right); префиксы не позволяют выдать лист за внутренний узел. Доказательству включения одной записи из миллиона нужно около 20 хешей; доказательство согласованности показывает, что более новое дерево продолжает старое и история не переписана.

На этой структуре построены журналы CT, Rekor из Sigstore, база контрольных сумм Go (sum.golang.org), корень транзакций Bitcoin (с другой конструкцией на двойном SHA-256 и известной особенностью с дублированием листьев), Git и большинство хранилищ с адресацией по содержимому, а также подписи на основе хеш-функций XMSS, LMS и SLH-DSA.

Журналы прозрачности публикуют подписанные заголовки дерева (signed tree heads, или checkpoints); свидетели (witnesses) заверяют их своими подписями, поэтому журнал, который показывает разным клиентам разную историю, можно уличить.

Стандарты и ссылки

Все термины