Содержание
Концепция дерева Меркла была предложена в начале 1980-х годов Ральфом Мерклом — ученым-информатиком, известным своими работами в области
криптографии с открытым ключом.
Дерево Меркла — это структура для верификации данных в наборе. Она широко применяется в области
одноранговых сетей, где участникам необходимо обмениваться информацией и подвергать ее независимой проверке.
В основе структуры дерева Меркла лежат хеш-функции, поэтому мы рекомендуем сначала ознакомиться со статьей
Что такое хеширование?, а затем вернуться к данной теме.
Предположим, вы скачиваете большой файл. При использовании
программы с открытым исходным кодом, вам нужно проверить, совпадает ли хеш скачанного файла с опубликованным хешем разработчиков. Если совпадает, то файл на вашем компьютере полностью аналогичен их файлу.
Если же хеши отличаются, то либо вы загрузили вредоносный файл, маскирующийся под программу, либо он был скачан неправильно и не будет работать. Проблемы с загрузкой тоже доставляют неприятности, особенно если она заняла много времени. В этом случае нужно будет заново загружать файл и надеяться, что в этот раз все пройдет хорошо.
Вы, наверное, думаете: «Неужели все так сложно?». К счастью, здесь нам и пригодятся деревья Меркла, позволяющие разбить файл на части. Например, файл размером 50 ГБ можно разделить на 100 фрагментов по 0,5 ГБ. В этом случае он будет загружаться по частям подобно тому, как файлы загружаются через торрент.
Основная цель процесса — получить единый хеш под названием корень Меркла, который представляет каждый фрагмент данных файла. Используя корень Меркла, мы можем значительно упростить проверку данных.
В качестве примера возьмем файл размером 8 ГБ, разделенный на 8 частей. Каждый фрагмент получает имя от A до H, а затем передается через хеш-функцию с целью получить 8 различных хешей.
Каждый из восьми фрагментов проходит через хеш-функцию, чтобы сгенерировать свой хеш.
Итак, с этим мы разобрались. Мы получили хеш всех фрагментов, значит, можем сравнить его с исходным и узнать, какой их них неисправен, верно? Возможно, но это будет крайне неэффективно. В нашем файле всего восемь фрагментов, но если их будут тысячи, станете ли вы хешировать их все и сравнивать результаты?
Вряд ли. Вместо этого нужно взять каждую пару хешей, объединить их и хешировать вместе. Таким образом мы хешируем hA + hB, hC + hD, hE + hF и hG + hH и получаем четыре хеша. Затем проводим еще один раунд хеширования, чтобы хешей стало два. Наконец, хешируем оставшуюся пару и получаем основной хеш — корень Меркла (или корневой хеш).
Структура напоминает перевернутое дерево. В нижнем ряду находятся «листья», которые переходят в ноды, а те — в корень.
Вот мы и получили корень Меркла, представляющий скачанный файл. Теперь можем сравнить корневой хеш с оригинальным хешем создателя. Если они совпадают, то все отлично! Если же хеши разные, значит, данные были изменены, то есть один или несколько фрагментов создали другой хеш. Таким образом, любая модификация данных даст совершенно другой корень Меркла.
К счастью, мы можем легко найти неверный фрагмент. Допустим, это hE. Для начала запросите последние два хеша, которые создали корень Меркла (hABCD и hEFGH). Значение вашего hABCD будет совпадать с оригинальным, поскольку в этом сегменте нет ошибок, но hEFGH будет отличаться, то есть следует проверять именно его. Далее запрашиваем hEF и hGH и сравниваем со своими. Поскольку hGH будет совпадать, нам нужен hEF. Наконец, сравниваем хеши hE и hF. Так мы выяснили, что неправильный фрагмент — это hE, а значит, нужно повторно его загрузить.
Резюмируем, что дерево Меркла создается путем разделения данных на множество частей, которые затем многократно хешируются для формирования корня Меркла. Эта система позволяет легко проверить, все ли в порядке с каждой частью данных. В следующем разделе мы рассмотрим другие возможности ее применения.
Думаете, как начать работу с криптовалютами? Купите биткоин на Binance!
У деревьев Меркла есть много вариантов использования, но сейчас нас интересует их применение в
блокчейне. Деревья Меркла необходимы в работе с
биткоинами и многими другими криптовалютами, являются неотъемлемой частью каждого
блока и находятся в
заголовках блоков. Чтобы получить листья дерева, мы используем хеш каждой транзакции (
TXID), включенной в блок.
В этом случае корень Меркла выполняет несколько задач. Далее мы рассмотрим их применение в майнинге криптовалюты и верификации транзакций.
Майнинг
Блок с биткоинами состоит из двух частей. Первая часть — это заголовок блока, сегмент фиксированного размера, содержащий
метаданные для блока. Вторая часть представляет собой список транзакций, размер которых обычно намного больше заголовка, но может варьироваться.
Майнерам необходимо многократно хешировать данные, чтобы получить результат, соответствующий определенным условиям, и добыть валидный блок. На его поиск могут уйти триллионы попыток, так как майнерам необходимо менять случайное число в заголовке блока (
nonce), чтобы получить новый результат, но большая часть блока останется прежней. В блоке могут быть тысячи транзакций, и каждый раз придется хешировать их все.
Корень Меркла значительно упрощает этот процесс. Во время майнинга все нужные транзакции выстраиваются в дерево Меркла. Корневой хеш (32 байта) помещается в заголовок блока, после чего хешируется только заголовок блока, а не весь блок.
Этот способ защищен от несанкционированного доступа и позволяет эффективно суммировать все транзакции блока в компактном формате. При этом найти валидный заголовок блока и затем изменить список транзакций невозможно, так как это изменит корень Меркла. Когда блок отправляется другим нодам, они вычисляют корень из списка транзакций. Если он не совпадает с корнем в заголовке, блок отклоняется.
Верификация
Давайте рассмотрим еще одно полезное свойство корней Меркла, которое касается упрощенных нод (которые не содержат полную копию блокчейна). Если вы используете ноду на устройстве с ограниченными ресурсами, то вам не обязательно загружать и хешировать все транзакции блока. Вместо этого вы можете просто запросить у полной ноды доказательство Меркла — подтверждение, что ваша транзакция находится в определенном блоке. Этот метод был подробно описан
Сатоши Накамото в whitepaper Биткоина и зачастую называется упрощенной проверкой платежей (SPV).
Для проверки hD необходимы только хеши красного цвета.
Предположим, нам нужна информация о транзакции, TXID которой — hD. При наличии hC мы можем вычислить hCD. Затем нам понадобится hAB для вычисления hABCD. Наконец, с помощью hEFGH можно проверить, соответствует ли полученный корень Меркла корню в заголовке блока. Если да, то это доказывает, что транзакция была включена в блок, так как создать один и тот же хеш с другими данными практически невозможно.
В приведенном выше примере мы хешировали только три раза, тогда как без доказательства Меркла это пришлось бы делать семь раз. Поскольку блоки могут содержать тысячи транзакций, использование доказательств Меркла помогает сэкономить много времени и вычислительных ресурсов.
Деревья Меркла доказали свою эффективность в компьютерных технологиях. Они невероятно полезны в блокчейнах и позволяют легко проверять информацию в распределенных системах, не перегружая сеть лишними данными.
Без деревьев Меркла (и корней Меркла) блоки
биткоина и других
криптовалют были бы очень громоздкими. И хотя в случае упрощенных нод могут возникать проблемы с конфиденциальностью и безопасностью, доказательства Меркла позволяют с минимальными расходами узнать, были ли транзакции включены в блок.
