Дерево хешей дерево меркла

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

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

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

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

Как устроены деревья Меркла?

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

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

Вы, наверное, думаете: «Неужели все так сложно?». К счастью, здесь нам и пригодятся деревья Меркла, позволяющие разбить файл на части. Например, файл размером 50 ГБ можно разделить на 100 фрагментов по 0,5 ГБ. В этом случае он будет загружаться по частям подобно тому, как файлы загружаются через торрент.

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

В качестве примера возьмем файл размером 8 ГБ, разделенный на 8 частей. Каждый фрагмент получает имя от A до H, а затем передается через хеш-функцию с целью получить 8 различных хешей.

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

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

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

Структура напоминает перевернутое дерево. В нижнем ряду находятся «листья», которые переходят в ноды, а те — в корень.

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

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

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

Почему корни Меркла используются в биткоине?

У деревьев Меркла есть много вариантов использования, но сейчас нас интересует их применение в блокчейне. Деревья Меркла необходимы в работе с биткоинами и многими другими криптовалютами, являются неотъемлемой частью каждого блока и находятся в заголовках блоков. Чтобы получить листья дерева, мы используем хеш каждой транзакции (TXID), включенной в блок.

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

Майнинг

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

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

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

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

Верификация

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

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

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

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

Резюме

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

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

Источник

Как снизить вероятность новых «криптопузырей». Биржи нашли способ

Одна из крупнейших до последнего времени криптобирж FTX, переживает острый кризис ликвидности и близка к банкротству. Нехватка средств была вызвана тем, что клиенты начали стремительно выводить активы в конце прошлой недели. Это случилось после того, как стало известно о проблемах с резервами у аффилированной с биржей компании Alameda и о нецелевом использовании FTX клиентских средств. Криптосообщество обратило внимание на непрозрачность финансовой отчетности этих компаний. В связи с драматической ситуацией вокруг FTX многие другие криптоплатформы поспешили обнародовать данные о своих резервах. Binance 10 ноября опубликовала адреса своих горячих и холодных кошельков и подтвердила наличие активов в различных криптовалютах на сумму $70 млрд. Кроме того, платформа сообщила, что внедрит механизм проверки резервов Proof-of-Reserve по методу «Дерева Меркла».

Вслед за этим еще несколько крупных криптовалютных площадок (KuCoin, Poloniex, Huobi, OKX, Bybit) обязались ввести такие проверки активов. А биржа Gate.io напомнила, что уже третий год проводит такой аудит. В этой статье мы разберем, что такое «Дерево Меркла», и как использование этого метода подтверждения резервов может повлиять на криптосообщество.

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

Дерево Меркла — это концепция построения данных, которая была запатентована в 1982 году выпускником университетов Беркли и Стэнфорда Ральфом Мерклом. Это изобретение американского криптографа позволило упростить проверку информации в криптографии. Информация о всех транзакциях в блокчейне хешируется: массив данных преобразуется в набор из букв и цифр фиксированной длины с помощью математического алгоритма (хеш-функции). Для любого объема вводных данных длина хеша будет оставаться одинаковой. «Листья» на Дереве Меркла — это хеши транзакций, следующие за ними внутренние вершины — хеши, включающие результаты сложения «листьев». И так до самого корня, то есть хеша, включающего в себя информацию со всего дерева.

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

Дерево Меркла позволяет эффективно и безопасно проверять содержимое больших структур данных, говорит сооснователь ENCRY Foundation Роман Некрасов. Кроме того, по словам эксперта, оно используется для верификации этой информации и определения ее целостности. Суть проверки по «Дереву Меркла» заключается в «аудите» состояния блокчейна без необходимости его полного скачивания, поскольку алгоритм позволяет получить один хеш для множества блоков блокчейна, объяснил управляющий партнер GMT Legal Андрей Тугарин. Он пояснил, что это возможно благодаря тому, что при использовании этого метода собираются не все блоки целиком, а только их заголовки, которые включают минимум необходимых данных. На централизованных биржах активы пользователей контролируются самой платформой. Потенциально биржа может злоупотреблять этим и использовать средства клиентов без их ведома в своих целях. В результате, пользователи могут столкнутся с огромными рисками, начиная от задержек с выводом средств и заканчивая потерей активов из-за неплатежеспособности криптопроекта. Недоступность информации о финансовом положении бирж все сильнее уменьшают доверие к ним пользователей. Публикация криптобиржами информации о своих резервах в виде «Дерева Меркла» позволит клиентам получать прозрачную информации о состоянии резервов криптобирж, а соответственно, и обеспечении своих активов, отметил Тугарин.

В чем преимущества «Дерева Меркла» перед другими методами

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

Как это повлияет на криптосообщество

Практика раскрытия информации о резервах с помощью этого метода может не только повысить уровень доверия пользователей к биржам, считает Тугарин. По его словам, это также поможет снизить вероятность возникновения новых «криптопузырей». Кроме того, юрист полагает, что недавние заявления от бирж могут быть связаны с тенденциями мирового законодательства по регулированию оборота криптоактивов, которое нас ожидает уже в 2023 году. Прозрачность резервов станет чуть ли не основной обязанностью любого поставщика услуг, связанных с цифровыми активами, в том числе с эмиссией стейблкоинов, уверен Тугарин. Об этом прямо свидетельствуют положения законопроектов Lummis-Gillibrand в США и Mica (Markets in Crypto-Assets) в Евросоюзе, рассказал юрист. Он напомнил, что главные цели этих документов состоят в формировании единого подхода к регулированию криптовалют и формировании единых стандартов защиты пользователей̆. — Подкаст «Крах FTX и обвал биткоина». Что произошло на крипторынке

Больше новостей о криптовалютах вы найдете в нашем телеграм-канале РБК-Крипто.

Источник