Простое руководство по пониманию деревьев и корней Меркла

Содержание
Что такое дерево Меркла?
Как работают деревья Меркла?
Почему корни Меркла используются в Биткойне?
Добыча
Проверка
Заключительные мысли

Что такое дерево Меркла?Идея дерева Меркла возникла в начале 1980-х годов у Ральфа Меркла — ученого-компьютерщика, наиболее известного своими работами в области криптографии с открытым ключом.
Дерево Меркла — это структура, используемая для эффективной проверки целостности данных в заданном наборе данных, и она особенно важна в контексте одноранговых сетей, где участникам необходимо обмениваться информацией и проверять ее независимо друг от друга.
Хэш-функции являются неотъемлемой частью древовидных структур Меркла, поэтому мы рекомендуем прочитать статью «Что такое хэш?». Прежде чем продолжить чтение этой статьи.

Как работают деревья Меркла?Допустим, вы хотите скачать большой файл. В случае программного обеспечения с открытым исходным кодом вам обычно необходимо проверить, соответствует ли хэш-значение загруженного вами файла значению, которое разработчики сделали общедоступным. Если да, то вы знаете, что файл, который есть на вашем компьютере, совпадает с их файлом.
Если хэш-значения не совпадают, то у вас проблема. Либо вы загрузили вредоносный файл, выдающий себя за программу, либо загрузка не удалась, поэтому она не работает. Если загрузка не удалась, вы, вероятно, не обрадуетесь, если вам придется некоторое время ждать загрузки файла. Затем вам придется начать процесс заново и надеяться, что на этот раз все пройдет хорошо.
В этом случае вы могли бы подумать, если бы был более простой способ сделать это.  К счастью, именно здесь на помощь приходит дерево Меркла. С помощью этого дерева файл разбивается на части. Если размер файла составляет 50 ГБ, вы можете разделить его на 100 частей, каждая по 0,5 ГБ, и загружать их по частям. По сути, это то, что вы делаете, когда используете торрент-файлы. 
В этом случае источник файла предоставит вам хэш-значение, известное как корень Меркла. Это единственное значение представляет собой представление каждой части данных, составляющих ваш файл, но корень Меркла значительно упрощает проверку данных. 
Для простоты мы рассмотрим этот пример, где мы используем файл размером 8 ГБ, разделенный на 8 частей, и пометим эти разные части буквами от A до H. Затем каждая часть будет проходить через хеш-функцию: в результате получается 8 различных значений хеш-функции.

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

Что ж, теперь у нас есть кое-что, что имеет немного больше смысла. У нас есть хеш-значения всех частей, поэтому, если одна из них неверна, вы узнаете об этом, сравнив ее с исходным хэш-значением, верно? Возможно, но это также крайне неэффективно, если файл состоит из тысяч частей, вы действительно собираетесь разделить их все, а затем так тщательно сравнивать результаты?
Нет, вместо этого мы возьмем каждую пару хеш-значений, сложим их вместе, а затем хешируем. Итак, мы хэшируем hA + hB,  hC + hD,  hE + hF и  hG + hH так, чтобы в итоге у нас было 4 хеш-значения, затем мы выполняем еще один раунд хеширования для этих значений, в конечном итоге достигая 2 хэш-значений. Наконец, мы хэшируем оставшиеся два значения, чтобы получить основное значение хеш-функции — корень Меркла (или корневое значение хеш-функции).

Структура выглядит как перевернутое дерево, где в последнем ряду есть листья, которые собираются вместе, образуя узлы и, в конечном итоге, корень.

Теперь у нас есть корень Merkle, который представляет загруженный нами файл. Это значение корневого хэша можно сравнить со значением, предоставленным источником, и если они совпадают, отлично! Но если хеш-значения различаются, это дает нам уверенность в том, что данные были изменены, то есть одна или несколько частей создали другое хеш-значение, поэтому любая простая модификация данных даст нам совершенно другой корень Меркла. . 
К счастью, у каждого из нас есть простой способ проверить, какая часть неисправна. В данном случае, скажем, эта часть — hE. Сначала запросите у пира два значения хеш-функции, которые создали корень Меркла (hABCD и hEFGH). Ваше значение hABCD должно совпадать с его значением, поскольку в этом поддереве нет ошибок. Но это не относится к значению hEFGH, поэтому вам следует проверить это значение. Затем вы запрашиваете значения hEF и hGH и сравниваете их со своими собственными значениями. Вы обнаружите, что значение hGH в порядке, а затем поймете, что значение hEF является причиной проблемы. Наконец, вы сравните хеш-значения hE и hF, и теперь вы знаете, что hE неверен, поэтому можете повторно загрузить этот фрагмент.
Короче говоря, дерево Меркла создается путем разделения данных на несколько частей, которые затем итеративно хешируются для формирования корня Меркла. Затем вы можете эффективно проверить, произошла ли ошибка с фрагментом данных. Как мы увидим в следующем разделе, есть и другие интересные приложения.

Хотите начать торговать цифровыми валютами? Купите биткойны (BTC) на Binance прямо сейчас!

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

ДобычаБлок Биткойна состоит из двух частей. Первая часть — это раздел хранения блока, представляющий собой часть фиксированного размера, содержащую метаданные для блока. Вторая часть представляет собой список транзакций переменного размера, но обычно он намного больше по размеру, чем раздел блочного хранилища.
Майнерам необходимо неоднократно хешировать данные, чтобы получить выходные данные, соответствующие конкретным условиям для добычи действительного блока. Они могут сделать триллионы попыток, прежде чем найдут правильный блок. При каждой попытке они меняют случайное число в разделе хранилища блока (частный код), чтобы получить другой результат. Однако большая часть массы остается прежней. Количество транзакций может составлять тысячи транзакций, и вам придется каждый раз их хешировать.
Корень Меркла значительно упрощает процесс: когда вы начинаете майнинг, вы помещаете в ряд все транзакции, которые хотите включить, и создаете дерево Меркла. Затем вы помещаете полученное значение корневого хэша (32 байта) в раздел блочного хранилища. Затем при майнинге все, что вам нужно сделать, — это хэшировать раздел хранилища блоков, а не весь блок.
Этот метод работает, поскольку его невозможно подделать, эффективно суммируя все транзакции блоков в компактном формате. И вы не можете найти действительный раздел блочного хранилища, а затем изменить список транзакций позже, потому что это изменит корень Меркла. Когда блок отправляется на другие узлы, он вычисляет корень из списка транзакций, и если он не соответствует тому, что указано в разделе хранения блоков, блок отклоняется.

ПроверкаЕсть еще одно интересное свойство корней Меркла, которым мы можем воспользоваться. Эта функция важна для простого программного обеспечения узлов (узлов, которые не несут полную копию цепочки блокчейна). Если вы используете узел на машине с ограниченными ресурсами, вы не хотите загружать и хэшировать все транзакции блока. Вместо этого вы можете запросить доказательство Меркла — доказательство, предоставленное всем узлом, которое подтверждает транзакцию. существует в определенном блоке. Это часто называют упрощенной проверкой платежей (SPV), и это было подробно объяснено Сатоши Накамото в техническом отчете о Биткойне.

Для проверки HD нам нужны только хэш-значения, показанные красным.

Давайте рассмотрим, например, сценарий, в котором мы хотим узнать информацию о транзакции с идентификатором транзакции HD. Если нам доступно значение hC, мы можем найти hCD. Затем нам понадобится  haB для вычисления hABCD. Наконец, в случае hEFGH мы можем проверить, соответствует ли полученный корень Меркла тому, что находится в разделе блочного хранилища. Если они совпадают, это свидетельствует о том, что транзакция существовала в блоке, поскольку было бы практически невозможно сгенерировать одно и то же значение хеш-функции с разными данными.
В предыдущем примере нам нужно было выполнить хеширование только три раза, а без доказательства Меркла нам пришлось бы выполнить его 7 раз. Поскольку сегодня блоки содержат тысячи транзакций, использование доказательства Меркла экономит много времени и вычислительных ресурсов.

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