Дерево Меркла
Хеш-дерево, в котором каждый внутренний узел — хеш своих потомков. Зная только корневой хеш, можно проверить целостность всего содержимого дерева. Ральф Меркл, 1979 год.
Лежит в основе: Bitcoin (корень Меркла транзакций в каждом блоке), Git (хеш коммита — корень деревьев хешей), IPFS (контентная адресация), Certificate Transparency, BitTorrent (проверка фрагментов), ZFS/Btrfs (целостность ФС). Доказательство Меркла: достаточно O(log n) хешей, чтобы доказать включение конкретного листа. Современные варианты — разреженные деревья Меркла и деревья Веркла. Патент истёк в 2002 году → с тех пор взрывной рост применения.