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

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

Все о деревьях Меркле

История Merkle Trees началась в далеком 1979 году с парня по имени Ральф Меркл. Учась в аспирантуре Стэнфордского университета, Меркл написал научную работу под названием "Сертифицированная цифровая подпись". В этом эссе Меркл описал метод создания цифровых подписей и создал новый, чрезвычайно эффективный метод создания криптографических доказательств. Другими словами, он разработал процесс проверки данных, который позволит компьютерам выполнять свою работу намного, намного быстрее, чем когда-либо прежде.

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

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

Итак, что же такое Дерево Меркла? Давайте узнаем.

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

Все эти свойства позволяют хэш-функциям создавать электронные отпечатки определенных входных данных. Используя хэш-функции, сети blockchain создают криптографический хэш - электронный отпечаток пальца - каждой транзакции. Криптографический хэш транзакции называется просто ID транзакции. Почти в каждом протоколе блокчейна идентификатор каждой транзакции представляет собой 64-символьную (256-битную) буквенно-цифровую строку данных.

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

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

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

Что такое корень Меркле?

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

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

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

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

Простой пример дерева Меркла

Чтобы прояснить эту концепцию, давайте рассмотрим очень простой пример дерева Меркла. Представьте, что в одном конкретном блоке было выполнено 8 транзакций. В действительности идентификаторы транзакций состоят из 64 символов, но для простоты давайте представим, что они состоят всего из 8 символов. Чтобы было еще проще, давайте будем использовать только цифры (и совсем не будем обращать внимания на буквы).

Итак, в этом примере наши идентификаторы восьми транзакций будут такими:

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

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

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

Вот как будет выглядеть наше дерево Меркла:

Обратите внимание, что количество кодов сокращается вдвое с каждым шагом вниз по дереву Меркла. Мы начинаем с 8 идентификаторов транзакций и, пройдя всего 3 шага, получаем один код - корень Меркла. В этом примере наш корень Меркла - это код в нижнем поле: 12345678.

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

Эффективность и скорость: преимущества деревьев Меркла

Предположим, что в нашем примере мы хотим подтвердить ID транзакции. Боб говорит, что заплатил Алисе определенную сумму Биткойнов, и сообщает нам, что идентификатор транзакции - 88888888. Он также отправляет нам 3 хэша: 77777777, 55556666 и 11223344. Это вся информация, которую необходимо отправить или получить, чтобы подтвердить платеж Боба Алисе.

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

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

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

Затем мы берем второй код, который прислал нам Боб, 55556666, и хэшируем его с новым кодом 77778888, который мы только что получили. Это, конечно же, дает число 55667788.

Наконец, мы хэшируем третий код, который дал нам Боб, 11223344, с другим новым кодом, который мы получили, 55667788, и в итоге получаем правильный корень Меркла: 12345678.

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

Процедуры проверки стали простыми с помощью дерева Меркле

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

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

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

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

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

Отказ от ответственности：

1. Эта статья перепечатана с сайта[komodo]. Все авторские права принадлежат оригинальному автору[Delton Rhodes]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Предупреждение об ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.