Количество информации, которая окружает современного человека, стремительно растет на фоне цифровизации. Данные нужно как-то хранить. Желательно, чтобы они не занимали много места и к ним можно было бы легко получить доступ. Решением проблемы стала концепция деревьев Меркла. Рассказываем, как она работает.
Хотите обсудить эффективность деревьев Меркла с криптоэнтузиастами или задать вопросы по концепции? Приходите в Телеграм-канал BeInCrypto. У нас не только новости и обзоры, но и живое общение с трейдерами, инвесторами и просто фанатами криптовалюты. Задавайте вопросы экспертам, участвуйте в промоакциях, будьте в курсе вместе с BeInCrypto.
В этой статье:
- Что такое дерево Меркла
- Кто создал концепцию
- В чем смысл концепции: объясняем на простом примере
- Как работает концепция и при чем тут деревья
- Как хеш-дерево защищает данные
Что такое дерево Меркла
Дерево Меркла (анг. Merkle tree) – это концепция работы с данными. У нее есть и другие названия. Дерево Меркла также называют деревом хешей или хеш-деревом. При чем тут деревья, мы выясним чуть позже. А пока сосредоточимся на хешах.
Хеш или хеш-функция – технология преобразования записей в уникальный набор символов, который присущ только этому конкретному массиву данных. Детали конвертации зависят от выбранного алгоритма. Возьмем SHA-256, в котором число – количество бит (единица измерения количества информации). На этом алгоритме работает самая капитализированная криптовалюта – биткоин (BTC).
Хеширование на SHA-256 позволяет привести любой массив данных в строку из 64 символов. Вот пример:
Согласитесь, строчка из 64 символов «весит» меньше, чем томик Бродского. Поэтому хранение информации в хешированном виде не требует большого объема памяти. Следовательно, не нужно тратиться на организацию дополнительных хранилищ. При этом чем меньше запись – тем легче ей оперировать. Поэтому хеширование, в том числе, ускоряет работу систем.
В переводе с английского hash (хеш) – мешанина.
Кто создал концепцию
Автор концепции – американский криптограф Ральф Меркл. Он предложил схему компоновки данных в 1979 году. Но настоящая популярность пришла к концепции лишь с появлением криптовалют.
По состоянию на момент написания обзора, Ральф Меркл занят разработками в сфере молекулярных нанотехнологий. Вот одна из его лекций:
В чем смысл концепции: объясняем на простом примере
Смысл концепции дерева Меркла в том, чтобы как можно эффективнее систематизировать информацию и организовать ее безопасное хранение.
Представьте, что у вас есть коллекция книг: одни – на английском, другие – редкие экземпляры классиков, третьи – коллекционные издания, четвертые – энциклопедии. Они лежат в одной куче на арендованном у малознакомого человека складе. Некоторые – в громоздких упаковках, другие – в пакетах. Если вам потребуется определенная книга из коллекции на поиски, вероятно, уйдет много времени. При этом никто не гарантирует, что интересующий том будет с сохранности.
Неразбериха – не единственный недостаток такого способа хранения книг. Складское помещение могут ограбить. При этом владелец книг вряд ли сможет сразу же обнаружить потерю, так как разобраться в куче литературы будет непросто.
Вот какое решение проблемы предлагает концепция Меркла:
- Полная систематизация библиотеки. Все экземпляры нужно избавить от упаковок, пакетов и другого «мусора», который может усложнить поиск. Каждая книга должна быть промаркирована и привязана к другой. Например, если мы говорим о сборнике стихов в трех томах, каждую из книг нужно снабдить отметкой о ее принадлежности к коллекции. При этом сами издания необходимо держать рядом. Также нужно сделать отметки о принадлежности книг конкретному человеку.
- Создание копий состава библиотеки. Информации о метках книг и расположения каждого издания. Дубликаты записей необходимо хранить в безопасном месте. В случае кражи или подмены какого-либо экземпляра из коллекции, эта информация поможет быстро выявить изменения.
- Организация безопасного хранения. Чтобы не полагаться на охранников и других третьих лиц, можно самостоятельно организовать систему оповещения, которая будет присылать сигналы на смартфон, в случае попытки проникновения в помещение.
Вот каких результатов, применимо к книгам, помогает добиться концепция Меркла:
- Контроль над коллекцией.
- Повышение эффективности системы хранения.
- Организация безопасного хранения без обязательного доверия третьей стороне.
С появлением блокчейна и криптовалют концепция деревьев Меркла нашла новое применение – с ее помощью можно организовать безопасное, высокоэффективное хранение цифровых данных.
Как работает концепция и при чем тут деревья
Теперь давайте разберемся, при чем же тут деревья. Для этого нужно подключить воображение и посмотреть на схематичное изображение хеш-дерева на картинке ниже. Вот что на ней изображено:
- Желтые блоки (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 и присоединяйтесь к дискуссии в нашем Телеграм-канале.
Дисклеймер
Согласно правилам Trust Project, образовательный контент на этом сайте публикуется только для общего ознакомления. Политика BeInCrypto — предоставлять качественную и правдивую информацию, проводить собственные исследования, а также создавать информативный и полезный контент для читателей. BeInCrypto может рассказывать о своих партнерах в своих материалах по обоюдной договоренности, однако эти договоренности не делают контент предвзятым или вводящим в заблуждение. Вся ответственность за любые действия, которые читатель предпринимает на основании информации, размещенной на нашем сайте, лежит на самом читателе. Также обратите внимание, что наши «Условия и положения», «Политика конфиденциальности» и «Дисклеймеры» были обновлены.
