Что такое дерево Меркла? Руководство для начинающих по этому компоненту блокчейна

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

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

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

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

Краткая информация

Криптографические хэш-функции

Проще говоря, хэш-функция — это любая функция, которая используется для сопоставления данных произвольного размера (входных данных) с выходными данными фиксированного размера. К входным данным применяется алгоритм хеширования, и полученный результат фиксированной длины называется хешем.

Многие алгоритмы хеширования широко доступны и могут быть выбраны в соответствии с вашими потребностями.

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

Например, если в качестве входных данных у вас есть следующие наборы данных, приведенные ниже, результирующие выходные данные уникальны для каждого входных данных. Обратите внимание, что во втором и третьем примерах, хотя разница входных данных составляет всего одно слово, результирующие выходные данные совершенно разные.

Это очень важно, поскольку позволяет проводить «отпечатки пальцев» данных.

Криптографическая хеш-функция, изображение из Википедии.

Поскольку длина выходных данных (хеш-сумма в примере) всегда такая же, как определяется используемым алгоритмом хеширования, огромные объемы данных можно идентифицировать исключительно по их результирующему хешу.

В системах, содержащих огромные объемы данных, преимущества возможности хранить и идентифицировать данные с выходными данными фиксированной длины могут привести к значительной экономии места на хранилище и помочь повысить эффективность.

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

Блокчейны — это связанные списки, которые содержат данные и хеш-указатель, указывающий на предыдущий блок, создавая цепочку связанных блоков, отсюда и название «блокчейн».

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

Это представлено (в случае алгоритма SHA-256) выходными данными (хешем), например:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Хэш выше — это отпечаток всего состояния блокчейна до него. Состояние блокчейна до нового блока (в виде хешированных данных) является входными данными, а полученный хеш — выходными данными.

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

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

Деревья Меркла и доказательства Меркла

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

Листовые узлы — это самый нижний уровень узлов в дереве. На первый взгляд это может показаться трудным для понимания, но если вы посмотрите на часто используемый рисунок ниже, понять его станет гораздо проще.

Пример двоичного хеш-дерева, Изображение из Википедии.

Важно отметить, что нелистовые узлы или «ветви» (представленные хешем 0-0 и хешем 0-1) слева являются хешами своих соответствующих дочерних элементов L1 и L2. Кроме того, обратите внимание, что ветвь Hash 0 является хешем своих объединенных дочерних ветвей Hash 0-0 и Hash 0-1.

Приведенный выше пример представляет собой наиболее распространенную и простую форму дерева Меркла, известную как двоичное дерево Меркла. Как видите, существует верхний хэш, который является хешем всего дерева и называется корневым хешем. По сути, деревья Меркла — это структура данных, которая может принимать «n» хешей и представлять их одним хешем.

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

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

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

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

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

Дерево выгодно для распределения больших наборов данных на управляемые более мелкие части, где барьер для проверки целостности существенно снижается, несмотря на общий больший размер данных.

Корневой хеш можно использовать в качестве отпечатка пальца для всего набора данных, включая всю базу данных, или для представления всего состояния блокчейна. В следующих разделах мы обсудим, как Биткойн и другие системы реализуют деревья Меркла.

Деревья Меркла в Биткойне

Криптографическая хеш-функция, используемая Биткойном, представляет собой алгоритм SHA-256. Это означает «Алгоритм безопасного хеширования», выходные данные которого имеют фиксированную длину 256 бит. Основная функция деревьев Меркла в Биткойне — хранить и, в конечном итоге, сокращать транзакции в каждом блоке.

Как упоминалось ранее, блоки в блокчейне связаны через хэши предыдущего блока. В Биткойне каждый блок содержит все транзакции внутри этого блока, а также заголовок блока, который состоит из:

• Номер версии блока
• Хэш предыдущего блока
• Timestamp
• Целевой уровень сложности майнинга
• данное время
• Корневой хеш Меркла

Изображение ниже взято из технического документа Биткойна и иллюстрирует, как дерево Меркла вписывается в каждый блок.

Транзакции включаются майнерами в блоки и хешируются как часть дерева Меркла, что приводит к корню Меркла, который хранится в заголовке блока. Эта конструкция имеет ряд явных преимуществ.

В частности, как указано в техническом документе, это позволяет существовать узлам простой проверки платежей (SPV), также известным как «облегченные клиенты». Этим узлам не нужно загружать весь блокчейн Биткойна, а только заголовки блоков самой длинной цепочки.

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

Кроме того, реализация деревьев Меркла в Биткойне позволяет сокращать блокчейн в целях экономии места. Это результат того, что в заголовке блока хранится только корневой хеш, поэтому старые блоки можно обрезать, удаляя ненужные ветви дерева Меркла, сохраняя при этом только те, которые необходимы для доказательства Меркла.

Реализация деревьев Меркла в других блокчейнах и системах

Хотя Биткойн был первым блокчейном, реализовавшим деревья Меркла, многие другие блокчейны реализуют аналогичные древовидные структуры Меркла или даже более сложные версии.

Кроме того, реализация дерева Меркла не ограничивается только блокчейнами и применяется ко множеству других систем.

Ethereum, будучи еще одной наиболее узнаваемой криптовалютой, также является отличным примером другой реализации дерева Меркла. Поскольку Ethereum является полной по Тьюрингу платформой для создания гораздо более сложных приложений, он использует более сложную версию дерева Меркла, называемую деревом Меркла Патриции, которая на самом деле представляет собой три отдельных дерева Меркла, используемых для трех типов объектов. Подробнее об этих деревьях можно узнать здесь.

Наконец, деревья Меркла являются важным компонентом распределенных систем контроля версий, таких как Git и IPFS. Их способность легко обеспечивать и проверять целостность данных, передаваемых между компьютерами в формате P2P, делает их бесценными для этих систем.

Заключение

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

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