Что такое дерево Меркла: объясняем простыми словами

7 декабря 2022, 09:13 MSK
7 декабря 2022, 09:13 MSK

Количество информации, которая окружает современного человека, стремительно растет на фоне цифровизации. Данные нужно как-то хранить. Желательно, чтобы они не занимали много места и к ним можно было бы легко получить доступ. Решением проблемы стала концепция деревьев Меркла. Рассказываем, как она работает.

Хотите обсудить эффективность деревьев Меркла с криптоэнтузиастами или задать вопросы по концепции? Приходите в Телеграм-канал BeInCrypto. У нас не только новости и обзоры, но и живое общение с трейдерами, инвесторами и просто фанатами криптовалюты. Задавайте вопросы экспертам, участвуйте в промоакциях, будьте в курсе вместе с BeInCrypto.

В этой статье:

Что такое дерево Меркла

Дерево Меркла (анг. Merkle tree) – это концепция работы с данными. У нее есть и другие названия. Дерево Меркла также называют деревом хешей или хеш-деревом. При чем тут деревья, мы выясним чуть позже. А пока сосредоточимся на хешах.

Хеш или хеш-функция – технология преобразования записей в уникальный набор символов, который присущ только этому конкретному массиву данных. Детали конвертации зависят от выбранного алгоритма. Возьмем SHA-256, в котором число – количество бит (единица измерения количества информации). На этом алгоритме работает самая капитализированная криптовалюта – биткоин (BTC).

Хеширование на SHA-256 позволяет привести любой массив данных в строку из 64 символов. Вот пример:

Хеширование на SHA-256
Хеширование на SHA-256

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

Интересно!

В переводе с английского hash (хеш) – мешанина.

Кто создал концепцию

Автор концепции – американский криптограф Ральф Меркл. Он предложил схему компоновки данных в 1979 году. Но настоящая популярность пришла к концепции лишь с появлением криптовалют.

По состоянию на момент написания обзора, Ральф Меркл занят разработками в сфере молекулярных нанотехнологий. Вот одна из его лекций:

В чем смысл концепции: объясняем на простом примере

Смысл концепции дерева Меркла в том, чтобы как можно эффективнее систематизировать информацию и организовать ее безопасное хранение.

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

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

Вот какое решение проблемы предлагает концепция Меркла:

  • Полная систематизация библиотеки. Все экземпляры нужно избавить от упаковок, пакетов и другого «мусора», который может усложнить поиск. Каждая книга должна быть промаркирована и привязана к другой. Например, если мы говорим о сборнике стихов в трех томах, каждую из книг нужно снабдить отметкой о ее принадлежности к коллекции. При этом сами издания необходимо держать рядом. Также нужно сделать отметки о принадлежности книг конкретному человеку.
  • Создание копий состава библиотеки. Информации о метках книг и расположения каждого издания. Дубликаты записей необходимо хранить в безопасном месте. В случае кражи или подмены какого-либо экземпляра из коллекции, эта информация поможет быстро выявить изменения.
  • Организация безопасного хранения. Чтобы не полагаться на охранников и других третьих лиц, можно самостоятельно организовать систему оповещения, которая будет присылать сигналы на смартфон, в случае попытки проникновения в помещение.

Вот каких результатов, применимо к книгам, помогает добиться концепция Меркла:

  1. Контроль над коллекцией.
  2. Повышение эффективности системы хранения.
  3. Организация безопасного хранения без обязательного доверия третьей стороне.

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

Как работает концепция и при чем тут деревья

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

  • Желтые блоки (data block 1,2,3,4) – блоки с исходной информацией, какой именно – не важно. Например, в них могут быть стихи классиков.
  • Блоки hash (0-0, 0-1, 1-0, 1-1) – хеши желтых блоков. Помните, как мы превращали стихи в строку из 64 символов? Здесь произошло то же самое. Только длинные хеши схематично отобразили цифрами 0-0, 0-1, 1-0, 1-1.
  • Чтобы уменьшить количество информации, которую нужно хранить, 4 хеша желтых блоков превратили в 2 хеша (hash 0 и hash 1). Для этого каждую из пар хешей вновь прогнали через хеширование. На выходе получили 2 новых хеша – по одному на каждую пару.
  • Осталось 2 хеша. Вновь прогоняем пару через хеширование и получаем на выходе 1 хеш.
  • На выходе получаем «дерево» с одной «макушкой», в которой содержится конечный хеш (top hash).
Дерево Меркла
Схема дерева Меркла

Схема только что помогла нам значительно уменьшить размер стихов. При этом мы получили четкую последовательность шифрования.

Каждый вышестоящий хеш в нашем «дереве» – производное от предыдущих хешей. Если мы изменим хотя бы букву в стихотворении data block 1, то поменяется и top hash. Вот пример смены хеша при изменении исходного массива данных:

Изменение хеша
Как меняется хеш

Интересно!

Фрагменты данных, из которых, в итоге, составляют top hash, называют листьями.

Как хеш-дерево защищает данные

В этом месте на арену выходит децентрализованный принцип хранения информации на блокчейне. Напомним, блокчейн – это цепочка блоков, каждый из которых состоит из различной информации. Каждый блок блокчейна, как показано в схеме дерева Меркла, привязан к предыдущему.

Копии цепочек блока хранятся на компьютерах участников сети. Например, в случае с биткоином, они находятся на сетевых узлах – нодах. Такой подход к хранению данных называют децентрализованным.

А теперь представим, что кто-то попытался изменить информацию в одном из блоков биткоина. Подмена хотя бы одного символа приведет к потере согласования системы, ведь top hash изменится. Чтобы определить изменения, система может сравнить записи с копиями блокчейна других участников сети (ведь мошенник, который попытался изменить блок, не может одновременно получить доступ ко всем сетевым узлам биткоина, а значит большая часть копий будет содержать достоверную информацию).

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

Вот как схематично можно представить два подхода к хранению данных: централизованный (с единым центром управления) и децентрализованный (с несколькими центрами контроля, связанными друг с другом в одной сети):

Централизованные и децентрализованные системы
Схематичное изображение централизованных и децентрализованных систем
Интересно!

Деревья Меркла на блокчейне помогают подтверждать информацию. Например, криптобиржи могут использовать схему, чтобы предоставить клиентам доказательство сохранности активов.

Читайте свежие новости криптовалют на портале BeInCrypto и присоединяйтесь к дискуссии в нашем Телеграм-канале.

Дисклеймер

Вся информация на нашем сайте публикуется, основываясь на принципах добросовестности и только для общего ознакомления. Любые действия, основанные на информации, публикуемой на этом сайте, предпринимаются читателем исключительно под его собственную ответственность.
В разделе «База знаний» нашей приоритетной задачей является предоставление высококачественной информации. Мы тщательно определяем, изучаем и создаем образовательный контент, полезный для наших читателей.
Для поддержания этих стандартов на высоком уровне и дальнейшего создания качественного контента наши партнеры могут выплачивать нам вознаграждение за размещение информации о них в наших статьях. Однако такие выплаты никак не влияют на процессы создания объективного, честного и полезного контента.