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