Деревья Меркла: все, что вам нужно знать

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

Объявление ни к чему не привело, потому что они наткнулись на ту же самую преграду, с которой сталкиваются все: деревья Меркла. Не команда безопасности. Не брандмауэр. А математическая статья 1979 года, которую до сих пор никто не превзошёл.

Вот о чём идёт речь. Прежде всего. https://academy.bit2me.com/en/quien-es-ralph-merkle/

Историческая справка о деревьях Меркла

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

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

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

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

Их ключевое значение заключается в их способности обеспечить эффективное криптографическое доказательство согласованности и целостности данных.

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

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

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

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

Основные концепции деревьев Меркла

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

Хэш-функции и их роль в деревьях Меркла

A хеш-функция Это математический алгоритм, который принимает на вход элемент данных и выдает на выходе значение фиксированного размера, называемое хеш-значением или хеш-кодом.

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

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

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

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

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

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

Структура данных деревьев Меркла

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

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

Иерархическая структура деревьев Меркла позволяет эффективно проверять целостность данных.

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

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

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

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

Свойства и характеристики деревьев Меркла

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

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

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

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

III. Компактное представлениеДеревья Меркла предлагают компактное представление больших наборов данных. Вместо хранения или передачи всего набора данных, необходимо передавать только корневое хеш-значение.

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

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

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

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

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

v. Безопасность.Безопасность деревьев Меркла основана на свойстве устойчивости к коллизиям выбранной хеш-функции.

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

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

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

Почему вашему мобильному криптокошельку не нужно загружать весь блокчейн

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

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

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

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

Вы проверяете целостность по корневому элементу Меркла, а не по всей цепочке из 600 ГБ. Гарантия безопасности одинакова; вычислительные затраты составляют лишь малую часть от полной стоимости.

Именно поэтому для проверки вашей транзакции в Cash App Bitcoin не требуется серверная комната. Для этого достаточно одного доказательства Меркла.

Примеры использования и реальные примеры деревьев Меркла

Деревья Меркла находят применение в различных областях. Вот несколько примеров:

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

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

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

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

Этот шаблон, корневой ключ Меркла, публикуемый в блокчейне, с индивидуальными подтверждениями, предоставляемыми во время получения, — теперь является стандартным механизмом для списков разрешенных NFT, распределения протоколов DeFi и ретроактивных аирдропов на Ethereum и Solana.

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

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

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

Они гарантируют, что сертификат не был изменен и что он связан с доверенным корневым сертификатом.

v. Одноранговые сети: В одноранговых сетях деревья Меркла могут использоваться для проверки целостности общих ресурсов. Участники могут быстро проверить согласованность данных, получаемых от других участников.

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

Verkle Trees — следующая версия уже в разработке

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

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

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

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

По состоянию на 2026 год деревья Веркла остаются в стадии активных исследований и тестирования в тестовых сетях Ethereum. Они еще не развернуты в основной сети.

Все последствия, включая обратную совместимость и производительность в масштабе, все еще оцениваются.

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

Строительство дерева Меркла

1. Листовые узлы и их роль в деревьях Меркла

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

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

2. Алгоритм хеширования для генерации хешей конечных узлов

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

Алгоритм хеширования принимает элемент данных на вход и выдает на выходе хеш-значение фиксированного размера. Это хеш-значение однозначно представляет элемент данных и служит его идентификатором в дереве Меркла.

3. Расчет хешей родительских узлов

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

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

4. Рекурсивное построение структуры дерева Меркла

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

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

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

Процесс проверки деревьев Меркла

После построения дерева Меркла мы можем использовать его для проверки целостности данных.

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

Вот обзор процесса проверки:

Шаг 1: Поиск данных

Извлекаются или реконструируются блоки данных, требующие проверки.

Шаг 2: Генерация доказательств

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

Шаг 3: Расчет корневого хеша

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

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

Шаг 4: Проверка

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

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

Это позволяет быстро проводить проверку даже больших деревьев Меркла.

Связанный: Доказательство работы (PoW): что это такое и как оно работает как механизм консенсуса

Заключение

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

Ральф Меркл решил эту задачу в 1979 году. Он не думал о биткоине — он думал о том, как аутентифицировать открытые ключи.

То, что он создал, оказалось ответом на вопрос, который интернет не задаст ещё тридцать лет: как можно доверять данным, которые вы не создавали, в сети, которую вы не контролируете, и которые проверены людьми, которых вы никогда не встречали?

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