Дерево Меркла
Основные достоинства блокчейна — безопасность хранения и неизменность данных внутри сети. Они достигаются за счет соединения ячеек в цепочку и криптошифрования. Однако модель такой связи родилась до реализации первой блокчейн-сети. В материале читатели узнают, как устроено дерево Меркла и в какой степени оно участвует в криптотехнологии. Расскажем о формах концепции, разработанных за 30 лет с момента создания, а также об основных сильных и слабых сторонах такой модели.
Что такое дерево Меркла
Это способ организации данных, который помогает легко проверить точность и обеспечить безопасность цифровых сведений. В структуре Меркла каждый массив исследуется, сжимается и шифруется. Ему присваивается код, который называют хешем. Такие значения уникальны и тесно связаны с данными, записанными в массив.
Кто придумал концепцию
Разработка схем связи началась в 1950-х гг. Тогда они обрели вид перевернутого дерева. Важным этапом в создании концепции признан 1979 год, когда американский ученый и инженер Ральф Меркл (Ralph Merkle) представил свою структуру связи данных. Модель получила название по фамилии автора — дерево Меркла (в англоязычном варианте — Merkle Tree). Позднее концепция стала основой блокчейн-технологии.
С 1990-х хеш-дерево применяют в структуре криптографических протоколов — а именно в качестве ключевого элемента в генерации цифровых подписей и подтверждения подлинности транзакций. Их также разрабатывал Ральф Меркл.
Зачем нужны хеш-деревья
Безопасность цифровой информации — основная особенность такого вида связи. За 30 лет с момента внедрения концепция остается актуальной. Она успешно применяется в различных областях информационных систем. На ее основе построены интернет-соединения, алгоритмы криптографического шифрования и большая часть блокчейн-технологий.
Структура
С развитием информационных возможностей и компьютеров данных стало слишком много. Большие массивы сложно обрабатывать, поэтому требовалось сократить их объемы. Для сжатия сведений созданы хеш-функции.
Ральф Меркл предложил универсальную схему соединения полученных значений. В верхней части структуры расположен главный хеш-код — идентификатор цепочки. Другое его название — корень Меркла. Каждый узел в схеме также получает свой хеш, а «листья» соответствуют отдельным блокам.
Принцип работы
Сначала каждый массив информации собирается в единый блок. Для него создается «заголовок» фиксированной длины (хеш-код).
Затем фразы кодируются попарно, и для каждой связки вычисляется новое значение. Процесс повторяется для всех блоков в структуре — один раз и до тех пор, пока не получится единый корневой итог (хеш «дерева»).
В такой концепции есть важное свойство: данные нельзя подделать. Если это произойдет, то корень в блоке изменится. Сначала сгенерируется обновленный заголовок, затем по цепочке поменяются коды следующих ячеек.
Схему Меркла используют для транзакций, формирования блоков и построения сети. В последовательных цепочках подтверждать подлинность нужно для каждой ячейки. В то же время Merkle Tree использует только корень. Анализировать каждое «дерево» целиком становится не нужно. Главное значение выступает гарантией проверки информации внутри структуры.
У классической концепции Меркла есть доработанная версия — с несколькими хеш-функциями. В таком алгоритме используют разные способы шифрования. Например, самый популярный из видов кодирования SHA-256 усиливают дополнительной хеш-функцией SHA-3, BLAKE2 или другими.
Существует еще один вариант хеш-дерева Меркла — Merkle Patricia Tree (MPT), который подходит для поиска сведений внутри древовидной структуры. Традиционная Merkle Tree в первую очередь используется в сверке подлинности информации, записанной в дереве. Структуры также задействуют одновременно — например, в сети Ethereum.
Основной способ заработка на обмене цифровых активов ― спекулятивная торговля. Трейдеры...
Initial Coin Offering или первичное предложение монет — удобный способ сбора средств для запуска и...
Монета Bitcoin, созданная в 2009 году, стала первым успешным цифровым активом. Появление...
Аналоги
Способ связи Меркла не единственный вид организации данных. Существуют десятки хеш-деревьев. Одни помогают увеличивать скорость поиска необходимых сведений. Другие — сортируют информацию по выбранному условию. Деревья помогают организовать хранение данных и создавать системы индексации на основе определенных элементов строк.
Среди концепций существуют следующие виды:
- Бинарное или двоичное дерево (Binary Tree). В этом способе каждый узел включает не более двух потомков (левого и правого). Концепция применятся для реализации структур данных.
- Бинарное дерево поиска (Binary Search Tree, BST). Усложненная версия предыдущего способа. В ней узлы создают условия для сортировки (ключи), по которым выполняют поиск элементов. Способ также дает возможность удалять или вставлять новую информацию.
- AVL-дерево. Название получено по первым буквам фамилий авторов. Ими стали советские ученые Адельсон-Вельский и Ландис. Разработанная ими схема построена на BST-структуре. Здесь в каждом узле ограничивается высота. Параметр используют для поиска и обновления данных в структуре.
- Красно-черное дерево. Очередное сбалансированное — двоичная схема, в которой корень и листья черные. Красные узлы составляются на основе пар значений противоположного цвета.
- Префиксное и суффиксное деревья. Хеши в них создаются с учетом начала или окончания строк. Модель Меркла стала продолжением связи на основе префиксного варианта.
- B-дерево. Такая концепция создает ключи в каждом узле, а также делит данные на несколько блоков. Хеш-деревья организуют информацию во внешних носителях с последовательным доступом — например, на жестких дисках.
Влияние на криптоиндустрию
Первые блокчейн-цепочки — например, сети Bitcoin, Ethereum — построены на основе дерева Меркла. Благодаря ему создается цепочка, в которой нельзя подменить данные в уже существующих ячейках. Функции, унаследованные блокчейном из концепции Меркла, представлены в таблице.
| Особенность | Комментарий |
|---|---|
| Каждый блок содержит хеш-сумму транзакций и коды предыдущих ячеек. Это делает цепочки устойчивыми к изменениям. | |
| При анализе записей узлам необходимо сравнить небольшое количество информации — например, только хеш-заголовки ячеек. Это особенно важно в майнинге, здесь узлы соревнуются за добавление новых решений в блокчейн. | |
| Изменение информации в одной ячейке приводит к генерации новой хеш-суммы, в том числе в последующих элементах цепочки. Это усложняет подделку или удаление транзакций. | |
| Хранение сжатых и зашифрованных данных помогает быстрее проводить записи в сети. Однако в современных блокчейн-цепях такой скорости недостаточно. Для решения проблемы создают сайдчейн-сети. | |
| Проверка транзакций в алгоритме также построена на основе этой модели |
Как дерево Меркла применяется в блокчейне
Данная структура стала фундаментом одного из главных криптопроцессов — майнинга. По концепции Меркла выполняются все транзакции и создаются блокчейны. Пользователи ищут хеши и получают за это награду в цифровых валютах. Со стороны действия сети структура дает быстрое подтверждение подлинности — верификацию.
Майнинг
Первые блокчейны создавались на системе доказательства работы — Proof-of-Work (PoW). Чтобы получить хеш-значение, нужно решить задачу с использованием оборудования. Когда результат найден, блок считается закрытым, выплачивается награда в криптовалюте. Технику (и владельцев оборудования) называют майнерами, а процесс — добычей цифровых активов.
По сути данные о транзакциях организуются в блоке по типу дерева Меркла. Полученный результат, который закрывает ячейку, становится корневым хешем.
Однако в связи блоков также есть элементы Merkle Tree. Например, в каждой следующей ячейке используется конец предыдущего корня. Так концепция участвует на разных этапах создания цепочки.
Верификация
Дерево Меркла помогает работать с существующей связью блоков. Можно оценить подлинность записанных данных — иными словами, выполнить верификацию. Для этого сверяются главные значения — хеш-коды блоков и корня. Если они совпадают, то транзакции признаются подлинными и следующий блок присоединяется к концу цепочки.
Пройди опрос и получи в подарок скидку на торговую комиссию и книгу о криптовалюте
Более сбалансированный вариант Merkle Patricia Tree (MPT) оптимизирует поиск информации в блокчейне. Для этого алгоритм использует в структуре ключи. По ним узлы (ноды) быстро находят нужную транзакцию или сведения в дереве. В таком способе анализируются выбранные хеши. Не нужно перебирать каждый код, указанный в блоке.
В части случаев подтверждение выполняется на основе целостности данных о транзакциях. Например, можно оценивать только последние корневые хеши в сети.
Преимущества и недостатки хеш-деревьев
У концепции есть как сильные, так и слабые стороны. Для сравнения они перечислены в таблице.
| Преимущества | Недостатки |
|---|---|
| Инвариантность данных. Хеш-деревья усложняют подделку информации. Корневое значение будет сигнализировать об этом. | Затраты на создание блока (дерева). Для добычи хеша в криптосети требуется производительное оборудование. Однако сложность поиска постоянно растет, поэтому вычислительные ресурсы нужно регулярно увеличивать. |
| Скорость работы. С помощью связи Меркла делаются выводы на основе хешей и без затрат ресурсов на анализ массива. | Односторонняя структура. Защита от изменения данных в цепочке считается и преимуществом, и недостатком. Отменить ошибочно созданную транзакцию нельзя. |
| Экономия места. Хеш-деревья уменьшают размер блоков, так как они хранят только корень структуры. | Отсутствие гарантии. Возможна небольшая вероятность поиска одинаковых хеш-значений для разных блоков. Это называется коллизией. Поэтому 100%-ной гарантии надежности дать нельзя. |
| Быстрый доступ к данным. Концепция помогает дополнительно индексировать транзакции. | Ограничения по размеру. Сведения в дереве Меркла хранятся в сжатом виде. Однако информации образуется много, и это замедляет работу с ней. Поэтому требуются дополнительные методы оптимизации: новые алгоритмы шифрования, хардфорки сетей и не только. Такие изменения помогают сжимать данные, ускорять добычу блока и повышать объем ячеек. |
| Безопасность. Хеш-деревья построены на криптографических алгоритмах шифрования. Это защищает сети против атак и фальсификации данных. | Зависимость со структурой. Эффективность хеш-деревьев связана с правильной схемой построения и организацией массива. Такую концепцию сложно внедрить в уже существующую сеть с большими объемами информации. |
Упрощенная проверка оплаты
Часть анализа целостности данных проводится по заголовкам блоков. Такой сценарий участвует в упрощенной проверке оплаты (SPV). В первую очередь он повышает пропускную способность криптографических и традиционных сетей.
Узлы проверяют операции в схеме Меркла и экономят ресурсы при обмене данных. Другими словами, чем меньше объем информации при передаче, тем быстрее проводится подтверждение. SPV делает более эффективными и легкими операции на устройствах с недостаточно производительными ресурсами — например, мобильных телефонах.
Часто задаваемые вопросы
Это процесс сбора информации в блок и создание зашифрованного кода. В майнинге по сути выполняется хеширование транзакций за выплату вознаграждения.
По такой структуре созданы репозитории — например, ресурс GitHub. На нем можно найти исходный код как для блокчейн-продуктов, так и для классических приложений и сайтов.
Это возможность восстановления в структуре Меркла. Например, при необходимости есть опция загрузить прежнюю версию данных или выбрать в схеме более подходящую.
Иначе их называют алгоритмами хеширования или майнинга. Существуют уже несколько десятков таких способов. Самые популярные SHA-256, Ethash и Scrypt.
Простые алгоритмические функции можно раскодировать. Однако, если использовалось криптошифрование, разгадать хеш очень сложно. Потребуются десятки лет. Если применить комбинацию из нескольких алгоритмов криптографии, декодирование может занять миллионы лет.
