Введение в Merkle Tree

Криптовалюта и последствия этого явления: Введение в Merkle Tree
Цель этой публикации — предоставить обзор основной структуры данных Merkle Tree и точку перехода для более сложных тем, связанных с деревьями Merkle.
Ознакомившись с понятиями «Биткоин» и «Криптовалютные технологии», можно узнать основы того, как структуры данных на основе хэшей могут использоваться для проверки целостности данных в одноранговых системах.

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

Merckle Tree выглядит примерно так:
a, b, c и d — некоторые элементы данных (файлы, общедоступные / закрытые ключи, JSON и т. д.), а H — хеш-функция. Если кто не знает, хэш-функция действует как «цифровой отпечаток» какой-либо части данных, сопоставляя ее с простой строкой с малой вероятностью, что любая другая часть данных будет отображаться в одну и ту же строку. Каждый узел создается путем хеширования конкатенации его «родителей» в дереве. Дерево Merkle здесь является двоичным деревом, большинство деревьев Merkle — двоичным, но на таких платформах, как Ethereum, используются недвоичные деревья Merkle. Стоит рассмотреть двоичный случай, так как он наиболее распространен.

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

После построения данные могут быть проверены с использованием только корневого хэша в логарифмическом времени до количества листов (это также известно как Merkle-Proof). Аудиторские работы заново воссоздают ветвь, содержащую кусок данных от корня до проверяемой части данных. Если провести аудит c (если есть корневой хеш), нужно будет дать H (d) и H (H (a) + H (b)). Хэш c, чтобы получить H ©, затем конкатенировать и хэш H © с H (d), затем объединить и хэш в результате этого с H (H (a) + H (b)). Если результатом была та же строка, что и корневой хэш, это означало бы, что c действительно является частью данных в Merkle Tree.

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

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

Выбранные методы реализации

Полная версия кода объясняет основную часть методов создания и аудита дерева. Методы build_tree и _audit являются методами экземпляра из более крупного класса.

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

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

Приложения

Недавно Merkle Trees получили много внимания из-за их использования в приложениях blockchain. Во многих одноранговых (P2P) системах (а не только в блокчейнах!) Люди должны иметь возможность запрашивать данные от ненадежных сверстников с некоторым доказательством того, что те, кто их отправили, являются частью реального контента, который они запрашивали.

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

Аналогичная проблема применима к криптовалютам, таким как Bitcoin и Ethereum: если кто-то утверждает, что в какой-то транзакции другой партнер заплатил им, как узел в сети может проверить, действительно ли транзакция действительно произошла? Один из вариантов заключается в том, что узел мог хранить всю историю каждой транзакции, которая когда-либо происходила, однако это является запретительным с точки зрения затрат времени и пространства для этого узла. Merkle Trees предоставляют решение, обеспечивающее экономию времени и пространства для узлов в сети. Создавая Merkle Tree из данных транзакции в каждом блоке, транзакции можно проверять в логарифмическом времени вместо линейного времени. Кроме того, он открывает дверь для некоторых клиентов биткоина, которые могут сэкономить место, только сохраняя корень дерева Merkle: не нужно хранить каждую транзакцию, которая когда-либо происходила в истории, огромная ценность!

Помимо блоков и торрентов, Merkle Trees рассматривают использование в любой системе, которая должна эффективно обнаруживать несоответствия:
Органы сертификации (CA) используют систему как средство прозрачности сертификатов. Здесь пары открытых и закрытых ключей рассматриваются как листья дерева Merkle. Это один из механизмов CA, используемых для предотвращения ситуаций, когда один ЦС может «пойти на изгнание» и попытаться сертифицировать домен без владельца домена, зная о сертификации.

Есть высоко масштабируемые базы данных, такие как Apache Cassandra и Dynamo DBhandling сбои для баз данных реплик в сети. Этот процесс известен как «Анти-энтропия».

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

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

0 комментариев

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.