Нюансы упрощенной верификации данных: как работает Дерево Меркла

Что такое Дерево Меркла

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

Функция Дерева хешей названа в честь Ральфа Меркла, который описал ее в далеком 1979 году.

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

Допустим, условный пользователь «А» переводит условному пользователю «Б» 100 монет в централизованной системе. Тогда центральный узел сверяет баланс пользователя «А» и подтверждает этот перевод. Централизованный узел предоставляет информацию, на которую ориентируются все другие пользователи. То есть верифицировать информацию возможно только через обращение к центральному узлу.

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

Проблема верификации

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

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

Каждое хеш-значение можно «объединить» с другим соседним хеш-значением – это называется процессом конкатенации. В результате мы получаем новое хеш-значение. Его, в свою очередь, мы также объединяем с аналогично полученным хеш-значением. Процедура повторяется до тех пор, пока все не сведется к одному единому хеш-значению. В результате мы получаем однонаправленную хеш-функцию в виде полного бинарного (двоичного) дерева. Визуально это напоминает ветви:

Зачем нужно Дерево хешей

Дерево Меркла позволяет иерархически свести массив информации к одному единому хеш-значению. На практике это значит, что с помощью корневого значения (корень Меркла) мы можем проверить каждую транзакцию или, иначе говоря, доказать ее существование. Подобным образом происходит упрощенная проверка платежей, также известная как SPV, описанная Сатосши Накамото в Белой книге (White Paper) Биткоина. Конкретно, этому посвящены два раздела: №7 «Экономия дискового пространства» и №8 «Упрощенная проверка платежей».

Дерево Меркла в сети Биткоина

В разделе №7 Белой книги Биткоина автор пишет: «Чтобы хеш блока остался неизменным, все транзакции в блоке хранятся в виде хеш-дерева Меркла и лишь его корень включается в хеш блока».

Источник: bits.media/images/bitcoin_ru.pdf

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

Источник: bits.media/images/bitcoin_ru.pdf

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

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

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

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

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

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

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

Где помимо криптовалют используется Дерево Меркла

Биткоин и криптовалюты — далеко не единственный пример использования Дерева Меркла. На самом деле Дерево лежит в основе многих решений. Вот основные:

• Децентрализованные системы хранения данных. Например, протокол IPFS (InterPlanetary File System) использует Деревья Меркла для обеспечения целостности и подлинности файлов, хранящихся в сети. Когда пользователь загружает файл, тот разбивается на более мелкие фрагменты и каждый фрагмент хешируется с помощью криптографической хеш-функции. Затем хеш-значения используются для построения Дерева Меркла, которое позволяет проверять целостность файла. Более того, благодаря Дереву Мерклу в IPFS возможна адресация данных по их содержимому, а не местоположению, что составляет одно из главных преимуществ этого протокола.

• Безопасный обмен файлами. Платформа обмена файлами, такая как, например, BitTorrent, может использовать Дерево Меркла для обеспечения целостности и подлинности файлов, которыми обмениваются пользователи. Создавая Дерево Меркла для каждого файла, пользователи могут проверять целостность и подлинность частей файла, не загружая его целиком.

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

• Сетевая безопасность. Защищенный сетевой протокол, такой как TLS (Transport Layer Security), может использовать Деревья Меркла для обеспечения целостности и подлинности данных, передаваемых по сети. Благодаря созданию Дерева Меркла для каждого сообщения получатель может эффективно проверять целостность и подлинность информации без необходимости загружать сообщение целиком.

• Системы контроля версий. Система контроля версий (лучший пример сейчас – Git) может использовать Деревья Меркла для отслеживания изменений в кодовых базах и более эффективной совместной работы. Дерево Меркла создается для каждого коммита, поэтому разработчики могут эффективно проверять целостность/подлинность кода и его версии в любой момент времени.

• Сжатие данных. Алгоритм сжатия данных, такой как RLE (кодирование длины серии), может использовать Деревья Меркла для проверки целостности и подлинности данных при сжатии.

• Создание бэкапов. Дерево применяется при резервном копировании в Tahoe-LAFS. Эта функция позволяет создавать избыточные копии пользовательских файлов на нескольких серверах хранения, гарантируя доступность данных даже в случае сбоя или взлома некоторых серверов.

Вывод

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