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