Дерево Меркла (Merkle Tree)
Кратко: Дерево Меркла — это структура данных, которая используется в информатике и криптографии для проверки целостности хранимых или передаваемых данных.
Дерево Меркла — это структура данных, которая используется в информатике и криптографии для проверки целостности хранимых или передаваемых данных. Оно попарно объединяет хеши множества фрагментов данных в один хеш, который называется корнем Меркла.
Почему это важно
Блокчейны, такие как Bitcoin, хранят корень Меркла всех транзакций в заголовке каждого блока. Поскольку каждый хеш зависит от данных под ним, изменение даже одной транзакции меняет корень, поэтому подделку легко обнаружить. Дерево Меркла также позволяет лёгкому кошельку подтвердить, что транзакция находится в блоке, с помощью короткого доказательства из нескольких хешей, не загружая весь блок. Некоторые криптобиржи используют деревья Меркла в отчётах о подтверждении резервов (proof of reserves), чтобы пользователи могли проверить, что их баланс был учтён.
Пример
Возьмём четыре транзакции: A, B, C и D. Каждая из них хешируется. Хеши A и B объединяются и снова хешируются, так же как и хеши C и D. Наконец, эти два результата хешируются вместе и образуют корень. Чтобы доказать, что транзакция C включена, нужны только хеш D, объединённый хеш A и B и корень.