" - Что такое деревья Меркла и как они работают?
- Что такое деревья Веркла и как они работают?
- Какова важность деревьев Меркла и Веркла в блокчейне?
- Деревья Меркла против деревьев Веркла
Что такое деревья Меркла и как они работают?
Для блокчейна дерево Меркла, оно же Хеш-дерево, как мировое древо Иггдрасиль для викингов: все держится на нем.
Это было программное завление, призванное помочь вам осознать важность темы и побудить продолжить чтение. Потому как матчасть учить все-таки надо, хоть это и непросто.
Итак, что такое деревья Меркла?
Это структуры данных, используемые в криптовалютах, таких как биткоин и Ethereum.
Двоичное дерево использует алгоритмы криптографического хеширования и имеет листовые узлы, помеченные криптографическим хешем блока данных. Кроме того, у него есть нелистовые узлы, они помечены криптографическим хешем меток своих дочерних узлов. Каждый узел генерирует дайджест, который рекурсивно опирается на все характеристики своего поддерева, а к листьям добавляется один или несколько атрибутов. В древовидной структуре Меркла листья вычисляют хэш своих собственных атрибутов, а родительские узлы вычисляют дайджесты своих дочерних дайджестов, делая это слева направо.
Не очень понятно, да? Мы, кажется, немного запутались в ветках и листьях.
Вот более простое объяснение: дерево Меркла — полная структура данных в виде дерева, в листовых вершинах которого находятся хеши от блоков данных, а во внутренних – хеши от сложения значений в дочерних вершинах. Это связывает все элементы с информацией между собой.
Визуально процесс составления единого хеша напоминает дерево, от вершины которого расходятся "ветки" с хешами – отсюда и название.
Всё еще не очень понятно? Тогда зайдем с другой стороны. Начнем с того, кто он вообще такой – тот Меркл, чье это непростое дерево?
Ральф Чарльз Меркл (родился 2 февраля 1952 года) – американский ученый-компьютерщик, известный своими работами в области криптосистем с открытым ключом и хеширования, один из изобретателей криптографии с открытым ключом.
Ральф Меркл занимался проблемой создания более надежных цифровых подписей, для решения которой и разработал алгоритм, названный его именем.
Деревья Меркла эффективно проверяют правильность и целостность данных, снижая при этом требования к памяти для проверки.
Кроме того, по сравнению с другими структурами данных деревья Меркла занимают меньше места на диске, что является одним из их существенных преимуществ деревьев Меркла.
Блокчейн Ethereum использует дерево Меркла, называемое Merkle Patricia Trie: оно предлагает структуру данных, которая может использоваться для хранения всех привязок (ключ, значение) и аутентифицируется криптографически. Со временем оно обновляется, так как существует одно глобальное дерево состояний. Все данные контракта хранятся в хранилище. Каждый блок имеет свою собственную таблицу транзакций, в которой хранятся пары (ключ, значение). Каждый блок содержит отдельное дерево Receipts, которое никогда не обновляется.
Что такое деревья Веркла и как они работают?
Подобно деревьям Меркла, деревья Веркла (Verkle) позволяют организовать большое количество данных и создать краткий «свидетель» каждого элемента данных или группы связанных элементов, который может быть подтвержден кем-то, у кого есть доступ к корню дерева.
Наиболее важной особенностью деревьев Веркле является их эффективность в пробном размере. Дереву Веркле потребуется менее 150 байт для получения доказательства для дерева с миллиардом точек данных, тогда как типичному двоичныму дереву Меркла для этого необходимо около 1 килобайта.
В деревьях Веркла используется система проверки, называемая полиномиальными обязательствами: она основана на полиномиальных функциях для описания данных. Древовидная структура Verkle напоминает текущее дерево Merkle Patricia в Ethereum. По сути, каждый узел имеет одно из трех свойств:
- Он пуст.
- Это листовой узел с ключом и значением.
- Это промежуточный узел с определенным количеством дочерних узлов («шириной» дерева).
Деревья Веркла Джон Кузмаул представил в 2018 году, и с тех пор они пока не получили такой известности, как многие другие новые криптографические структуры. Однако это не делает деревья Веркла менее важными.
Деревья Веркла и Меркла похожи по структуре, единственное различие – древовидная структура Веркла более обширна. Если ширина увеличивается слишком сильно, доказательство начинает занимать слишком много времени. В результате доказательства становятся все короче и короче по мере увеличения ширины.
Какова важность деревьев Меркла и Веркла в блокчейне?
Деревья Меркла используются в биткойнах (BTC) и других криптовалютах для более эффективного и безопасного шифрования данных блокчейна.
Деревья Веркла позволяют использовать меньшие размеры доказательств, что особенно важно для предстоящих обновлений масштабирования Ethereum.
Как определить дерево Меркла? Листовые узлы, нелистовые узлы и корень Меркла — это три основные части дерева Меркла в контексте блокчейнов. Хэши транзакций или идентификаторы транзакций (TXID) находятся в листовых узлах, которые можно просмотреть в обозревателе блоков. Затем над листовыми узлами попарно хешируется слой нелистовых узлов. Нелистовые узлы хранят хэш двух конечных узлов, которые они представляют под собой.
Дерево сужается по мере его роста вверх, формируется вдвое меньше узлов на слой, когда уровни нелистовых узлов продолжают хешироваться вместе попарно. В последнем слое нелистовых узлов будут присутствовать два узла, которые устанавливают корень Меркла (используемый для проверки конечных узлов) и являются местом последнего хеширования в дереве Меркла.
Корень Меркла, хранящийся в части данных блока, можно сравнить с корнем Меркла, хранящимся в заголовке, что позволяет майнеру быстро идентифицировать любые манипуляции.
Доказательство Меркла объединяет доказываемое значение и значения хеширования, необходимые для восстановления корня Меркла. Кроме того, они поддерживают простую проверку платежей (SPV), которую можно использовать для аутентификации транзакции без загрузки всего блока или блокчейна. Это позволяет использовать крипто-кошелек или легкий клиентский узел для отправки и получения транзакций.
Деревья Веркла позволяют значительно уменьшить размер доказательств для большого объема данных по сравнению с деревьями Меркеля. Длина доказательства, обычно логарифмическая по размеру состояния, влияет на сетевое взаимодействие.
Доказательство Веркла свидетельствует о большом количестве сохраненных данных, которые может легко проверить любой, у кого есть корень дерева. При этом доказывающая сторона должна предложить единственное доказательство, демонстрирующее все связи родитель-потомок между всеми обязательствами на путях от каждого конечного узла к корню, вместо того, чтобы представлять все «сестринские узлы» на каждом уровне.
По сравнению с идеальными деревьями Меркла, размеры доказательств у дерева Веркла могут быть уменьшены в шесть-восемь раз (и более чем в 20-30 раз по сравнению с Merkle Patricia Trie, которые использует сейчас Ethereum).
Деревья Меркла против деревьев Веркла
Между обоими типами деревьев существует много различий, особенно в предоставлении доказательств.
Весь набор дочерних узлов в дереве Меркла, включая деревья Merkle Patricia, представляет собой свидетельство значения. Доказательство должно включать все узлы в дереве с любым родительским узлом, общим с узлом, который вы пытаетесь доказать. А в дереве Веркле вам необходимо указать только путь – и даже не нужно добавлять сестринские узлы.
Дерево Веркла служит той же цели, что и дерево Меркла. Однако деревья Веркла значительно более эффективны по размеру в байтах, что является их основным отличием.
Из-за своей древовидной структуры доказательства Меркла легко частично обновить, в то время как полиномиальные обязательства в деревьях Веркла требуют полного изменения всей кривой, для которой было бы сложно вычислить свидетелей.
За то, что люди во всем мире могут отправлять, получать и проверять транзакции с помощью криптокошельков, которые без проблем запускаются на персональном компьютере или смартфоне, нужно благодарить деревья Меркла – это важный вариант их использования.
А одним из важнейших вариантов использования деревьев Веркла является замена хэшей в дереве Меркла векторным обязательством, что повышает эффективность более широких факторов ветвления.
В общем, все деревья по-своему хороши и полезны.
