Что такое дерево Меркла и чем оно полезно криптоинвестору

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

Разобравшись с понятием Дерево Меркла, станет понятно, как работает технология Блокчейн. Вот что предстоит узнать:

• Что такое Деревья Меркла, и как они сжимают большое количество информации?
• Доказательство Меркла что это такое, и как оно работает?
• Почему Дерево Меркла эффективно?

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

• Разбираться в теме мы начнём с понятия хеширования.
• Хеширование — это преобразование вводных данных произвольного содержания и размера в одну строку.

Как работает хэширование

Вводные данные получают уникальную строку на выходе, даже если эти данные почти идентичны.

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

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

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

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

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

Верхний хэш (Top Hash) — это значение, которое содержит в себе всю информацию вводных данных. Он же корневой хэш или корневой узел.

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

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

Как результат, вместо данных, вы получаете одну строчку. Это удобно при сравнении информации, потому что вам не нужно сравнивать её всю, достаточно будет сравнить один корень с другим (Top Hash). Если корни совпадают, наборы данных одинаковы.

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

Возникает вопрос: может ли дерево Меркла делать что-либо, кроме как проверять ВЕСЬ набор данных?

Да! Можно проверить, есть ли в дереве определённые данные, или нет.

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

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

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

В примерах есть только 4 набора информации, но на практике, деревья могут быть развернуты для миллионов, миллиардов и триллионов данных.

По мере увеличения набора данных, деревья Меркла становятся все более и более эффективными. Как по согласованию, так и по проверке.

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

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

В начале говорилось: “Разобравшись с понятием дерево Меркла вы так же сможете понять как работает технология блокчейн.”

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

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

Что такое деревья Меркла?

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

Как работают деревья Меркла?

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

Что такое доказательство Меркла?

С помощью этого доказательства можно узнать, есть в дереве нужная информация или нет.

Что такое дерево Меркла? | Все, что нужно знать

14.07.2022

УглубленныйТехнические основы

УглубленныйТехнические основы

Главное

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

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

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

Создателем концепции хеш-дерева является профессор Ральф Меркл.

Он изобрел способ представления цифровых подписей в 1979 году. Патентом на технологию владеет Стэнфордский университет.

Ученый предложил использовать бинарное хеш-дерево. Меркл также внес значительный вклад в развитие криптографии. Он известен благодаря публикации 1987 года «Цифровая подпись, основанная на обычной функции шифрования».

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

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

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

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

Построение дерева Меркла выполняется снизу вверх. Значения в листовых вершинах получают хешированием фрагментов данных. Узлы следующего уровня содержат хеш от суммы двух дочерних.

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

Если число элементов нечетное, один из них дублируется или переносится на следующий уровень в неизменном виде.

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

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

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

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

Для оптимизации вычислений узлы биткоина формируют заголовки. Они включают следующие элементы:

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

Данные: Bitcoin.org.

Заголовок не включает транзакции и занимает 80 байт. Поскольку он формируется каждые десять минут, объем данных увеличивается на 4,2 мегабайта за год.

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

1. Находятся хеши (идентификаторы) транзакций, включенных в блок: hash(L1), hash(L2), hash(L3) и так далее. Они формируют листья дерева.
2. На следующий уровень помещаются хеши от суммы двух соседних идентификаторов: hash(hash(L1) + hash(L2)). В бинарном дереве число узлов на каждом уровне должно быть четным. В ином случае хеш из последней ячейки дублируется и помещается в дополнительный элемент.
3. Процесс хеширования суммы данных повторяется до получения корня Меркла.

Данные: Wikipedia.

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

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

Хеш-деревья позволяют упростить проверку принадлежности транзакции определенному блоку и обеспечить целостность информации при ее передаче. Метод необходим для упрощенной верификации платежей. Сатоши Накамото предложил использовать SPV в white paper биткоина.

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

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

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

Метод SPV позволяет легкому клиенту эффективно взаимодействовать с блокчейном и снижает объем загружаемой информации. Например, размер блока с пятью транзакциями может составлять 500 килобайт, а доказательство Меркла занимает всего 140 байт.

Бинарное дерево Меркла хорошо подходит для массива, представленного в виде списка. Его структура остается неизменной, что удобно для хеширования транзакций. В Ethereum применяется другой способ представления данных — префиксное дерево.

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

Данные: Wikipedia.

В отличие от биткоина, блокчейн Ethereum использует три хеш-дерева:

• транзакций;
• состояний;
• дерево, содержащее данные о результатах выполнения транзакций.

В заголовок блока входят три корневых хеша. Ethereum позволяет создавать легкие клиенты, способные выполнять базовый набор операций:

• проверить наличие транзакции в блоке;
• подтвердить существование определенного адреса;
• определить баланс пользователя;
• узнать результат выполнения операции или смарт-контракта.

Данные: Ethereum Stack Exchange.

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

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

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

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

Префиксное дерево позволяет решить указанные трудности. В Ethereum каждый элемент структуры имеет 16 дочерних. Этот подход оптимален для кодирования узлов в шестнадцатеричном формате.

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

Нашли ошибку в тексте? Выделите ее и нажмите CTRL+ENTER

Рассылки ForkLog: держите руку на пульсе биткоин-индустрии!

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

Содержание

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

https://www.youtube.com/watch?v=6b2LRLzUBPQ\u0026pp=ygVq0KfRgtC-INGC0LDQutC-0LUg0LTQtdGA0LXQstC-INCc0LXRgNC60LvQsCDQuCDRh9C10Lwg0L7QvdC-INC_0L7Qu9C10LfQvdC-INC60YDQuNC_0YLQvtC40L3QstC10YHRgtC-0YDRgw%3D%3D

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

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

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

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

Вы, наверное, думаете: «Неужели все так сложно?». К счастью, здесь нам и пригодятся деревья Меркла, позволяющие разбить файл на части. Например, файл размером 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, а значит, нужно повторно его загрузить.

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

Думаете, как начать работу с криптовалютами? Купите биткоин на Binance!

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

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

 

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

Майнинг

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

https://www.youtube.com/watch?v=6b2LRLzUBPQ\u0026pp=YAHIAQE%3D

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

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

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

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

Верификация

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

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

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

Предположим, нам нужна информация о транзакции, TXID которой — hD. При наличии hC мы можем вычислить hCD. Затем нам понадобится hAB для вычисления hABCD.

Наконец, с помощью hEFGH можно проверить, соответствует ли полученный корень Меркла корню в заголовке блока.

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

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

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

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

Как это работает: Деревья Меркла в биткойн сети

Узлы в блокчейн-сети анонимны и работают в условиях отсутствия доверия.

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

Решить проблему и упростить процесс помогают деревья Меркла. Что это такое, как используется, какие существуют альтернативы — расскажем далее.

/ изображение Allison Harger CC

Дерево Меркла — как оно «выглядит»

Блоки в биткойн-блокчейне — это перманентно записываемые файлы, которые содержат информацию о проведенных пользователями транзакциях. Дополнительно каждый блок содержит Generation Transaction (или Coinbase Transaction) — это транзакция с информацией об адресе с наградой за решение блока, которая всегда стоит первой в списке.

Все транзакции в блоке представлены как строки в шестнадцатеричном формате (raw transaction format), которые хешируются для получения идентификаторов транзакций (txid). На их основе строится хеш блока, который учитывается последующим блоком, обеспечивая неизменяемость и связность реестра.

Единое хеш-значение блока собирается при помощи дерева Меркла, концепция которого была запатентована Ральфом Мерклом (Ralph Charles Merkle) в 1979 году.

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

/ изображение MrTsepa CC

Построение дерева происходит следующим образом:

1. Вычисляются хеши транзакций, размещенных в блоке: hash(L1), hash(L2), hash(L3) и так далее.
2. Вычисляются хеши от суммы хешей транзакций, например hash(hash(L1) + hash(L2)). Так как дерево Меркла является бинарным, то число элементов на каждой итерации должно быть четным. Поэтому если блок содержит нечетное количество транзакций, то последняя дублируется и складывается сама с собой: hash (hash(L3) + hash(L3)).
3. Далее, вновь вычисляются хеши от суммы хешей. Процесс повторяется, пока не будет получен единый хеш — корень дерева Меркла (merkle root). Он является криптографическим доказательством целостности блока (то есть того, что все транзакции находятся в заявленном порядке). Значение корня фиксируется в заголовке блока.

В биткойн-блокчейне деревья Меркла строятся с использованием двойного хеширования SHA-256. Вот пример хеширования строки hello:

• Первый раунд SHA-256:
• Второй раунд:
• А вот пример реализации деревьев Меркла, используемой биткойном, на Python (результаты работы функции вы можете найти в репозитории на GitHub по ссылке):

2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50 
import hashlib

def merkle_root(lst):
sha256d = lambda x: hashlib.sha256(hashlib.sha256(x).digest()).digest()
hash_pair = lambda x, y: sha256d(x[::-1] + y[::-1])[::-1]

if len(lst) == 1: return lst[0]

if len(lst) % 2 == 1:
lst.append(lst[-1])
return merkle_root([ hash_pair(x, y)
for x, y in zip(*[iter(lst)] * 2) ])

Для чего нужны хеш-деревья

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

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

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

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

Аналоги деревьев Меркла

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

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

Для обхода ограничения исследователи и разработчики модернизируют уже существующие алгоритмы и разрабатывают новые. Например, в блокчейн-платформе Ethereum используется так называемое префиксное дерево Меркла (Trie).

Это структура данных, хранящая ассоциативный массив с ключами.

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

В Ethereum заголовок блока содержит сразу три префиксных дерева Меркла: для транзакций, информации об их выполнении и состоянии. Такой подход позволил легким клиентам получать от системы ответы на вопросы: «Есть ли транзакция в указанном блоке?», «Сколько монет на счету?» и «Каким будет состояние системы после выполнения этой транзакции?».

В качестве еще одной альтернативы классическим деревьям Меркла выступает метод комбинирования хеш-значений HashFusion, предложенный Hewlett Packard Labs. Как отмечают в компании, новый подход позволяет рассчитывать значения хешей поэтапно. Компоненты хеша вычисляются сразу, как только данные становятся доступны, а потом объединяются друг с другом при необходимости.

HashFusion подразумевает построение частей хеша с помощью бинарной функции объединения. Она является ассоциативной и некоммутативной, поэтому её можно использовать для объединения хешей в момент формирования. Это позволяет уменьшить объемы памяти, необходимые для их хранения. Работа бинарной функции строится следующим образом: она принимает на вход значения хешей (генерируемых классическими хеширующими функциями) и конвертирует их в матрицы целых чисел. После чего матрицы перемножаются, а результат обратно превращается в байтовый массив фиксированной длины. Представители компании HPE заявляют, что HashFusion реализует более гибкие структуры, по сравнению с деревьями Меркла, которые позволяют обновлять существующие хеши и выборочно удалять/вставлять новые значения. Авторы надеются, что в будущем технология найдет применение в файловых системах, облачных решениях и распределенных реестрах.

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

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

Также можно отметить модифицированный алгоритм организации цифровых подписей eXtended Merkle Signature Scheme (XMSS) и алгоритм SPHINCS.

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

P.S. 25 января в Киеве Bitfury проведет бесплатный воркшоп, во время которого будут разобраны практические особенности разработки с помощью Exonum. Наши специалисты расскажут и покажут, как развернуть собственный блокчейн и как написать сервис. Встреча будет полезна разработчикам на Rust, C++ и JavaScript, делающим первые шаги в блокчейн-разработке, а также тем, кто уже пробовал создавать блокчейн-решения.

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

Что такое “Дерево Меркла”, и почему криптобиржи вспомнили о нем после коллапса FTX :: РБК.Крипто

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

Одна из крупнейших до последнего времени криптобирж 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 и обвал биткоина». Что произошло на крипторынке
• — Команда Future Fund FTX ушла в отставку
• — Хакеры взломали протокол DFX Finance и украли криптовалюту на $4 млн
• — BlockFi объявила о приостановке вывода средств для клиентов
• — ВТБ протестирует операции с цифровым рублем в мобильном приложении
• Больше новостей о криптовалютах вы найдете в нашем телеграм-канале РБК-Крипто.

Древо Меркла. Что это и как его используют в смарт контрактах. Объясняю понятным языком

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

Эти переменные могут называться по-разному, но смысл обычно один и тот же.

В статье мы разберем как работает эта система, построим свое двоичное древо и напишем смарт контракт с проверкой есть ли кошелек в вл на Solidity!

Да кто такой этот ваш Древо Меркла

Пример дерева

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

• ◉ Вся структура данных которую мы рассматриваем называется древом.
• ◉ Каждый элемент в древе называется листком, а несколько элементов — листьями, по аналогии с реальными деревьями.
• ◉ Путь от верхнего элемента до нужного нам листка называется веткой.
• ◉ Все Древо Меркла — это 32 байтная строка, называемая рутом.
• ◉ Меркель пруф — это путь из 32 байтного массива хэшей от рута до проверяемого кошелька (его хэша).

Сами листья не могут являтся числом или массивом. Каждый лист — это хэш, чаще всего keccak256 помещаемых нами данных.

1. Шифр — это обратимая функция, а хэш — необратимая.
2. То есть, например, если мы знаем, что строка зашифрована шифром Цезаря под ключом 2 (то есть изменение вперед на 2 буквы) то мы можем ее расшифровать.
3. А если мы знаем, что строка захэширована, например, алгоритмом Keccak256, то, зная хэш, мы не сможем ее расхэшовать и узнать, что это была за строка (точнее можем, но только если мы будем перебирать все возможные слова, хэшировать каждое и сравнивать с искомым хэшем).

Дети древа меркла выглядят так, как вы видите сверху на картинке (сори за пейнт).

Это все понятно, но зачем его использовать, если можно все данные хранить в массиве/списке?

• Вот мы и пришли к вопросу, зачем Древо Меркла используют в смарт контрактах.
• ◉ Древо Меркла позволяет значительно облегчить нагрузку, так как при проверке, есть ли нужный хэш в древе, нужно пройти всего лишь по одной ветке, и нет необходимости перепроверять абсолютно все ветки.
• Если бы мы хранили в смарте массив из адресов, то тогда потребовалось гораздо больше газа, ведь все адреса хранились бы в блокчейне. Помимо этого, для проверки, есть ли кошелек в WL, потребовалось бы проходиться по всему массиву, что съедало бы больше газа при минте
• А так получается, что в блокчейне сохраняется только одна строчка из 32 байтов — рут хэш, нужный как раз таки для проверок, есть ли кошель в вайтлисте.

Второе преимущество — это безопасность.

◉ Во первых, поскольку Древо состоит из хэшей, не получится узнать чужие кошельки в WL (т.к. по хэшу нельзя получить исходную строку).

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

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

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

Кодинг

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

Итак, открываем вашу IDE (если кому интересно, я использую коммерческую версию WebStorm) и устанавливаем две библиотеки, которые нам понадобятся. Первая нужна, чтобы превратить строку в keccak256, а вторая — чтобы создать древо.

$ npm i keccak256 merkletreejs

Бум! Все установилось и теперь начинаем кодить.

Для начала импортируем две библиотеки которые мы установили выше:

const { MerkleTree } = require(«merkletreejs»);
const keccak256 = require('keccak256');

Теперь создадим массив из кошельков которые у нас в WL:

const addresses = [«0x5B38Da6a701c568545dCfcB03FcB875f56beddC4″,»0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2»];

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

const buf2hex = x => «0x» + x.toString(«hex»);

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

const leaves = addresses.map(address => keccak256(address));

Затем наконец-то создаем наше Древо:

const tree = new MerkleTree(leaves, keccak256, { sortPairs: true });

И получаем нужный нам рут хэш, который мы далее сохраним в смарт контракте:

const merkleRootString = buf2hex(tree.getRoot());

Теперь реализуем получение пруфа для кошелька:

const leaf = keccak256(«0x5B38Da6a701c568545dCfcB03FcB875f56beddC4»);
const proof = tree.getProof(leaf);
const proofString = «[» + proof.map(x => `»${buf2hex(x.data)}»`) + «]»

proofString это есть нужный нам пруф, который мы можем ввести в контракт и все пройдет.

Напишем простую реализацию смарт-контракта на Solidity, проверяющего есть ли кошель в WL.

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

pragma solidity ^0.8.4;

import «@openzeppelin/contracts/utils/cryptography/MerkleProof.sol»;

Создаем сам контракт, изначально задаем меркель рут, и добавляем функцию для проверки, которая вернет true если кошель в WL, и false если нет.

contract SimpleMerkleTree {
bytes32 merkleRoot = 0xeeefd63003e0e702cb41cd0043015a6e26ddb38073cc6ffeb0ba3e808ba8c097;
function checkIsAddressInWl(bytes32[] memory _merkleProof) public view returns(bool) {
return MerkleProof.verify(_merkleProof, merkleRoot, keccak256(abi.encodePacked(msg.sender)));
}
}

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

Created with ❤️ by https://t.me/crypto_satana || https://t.me/scissor_eth