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

Статьи

Деревья Merkle против деревьев Werkle

  • Что такое деревья Меркла и как они работают?
  • Что такое деревья Веркла и как они работают?
  • Какова важность деревьев Меркла и Веркла в блокчейне?
  • Деревья Merkle против деревьев Werkle

Что такое деревья Меркла и как они работают?

Для блокчейна дерево Меркла, оно же хеш-дерево, как мировое древо Иггдрасиль для викингов: на нем все держится.

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

Так что же такое деревья Меркла?

Это структуры данных, используемые в криптовалютах, таких как Биткойн и Эфириум.

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

Деревья Merkle против деревьев Werkle



Не очень понятно, да? Кажется, мы немного запутались в ветвях и листьях.

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

Визуально процесс составления единого хеша напоминает дерево, от вершины которого расходятся «ветви» с хешами — отсюда и название.

Все еще не очень понятно? Тогда пойдем на другую сторону. Начнем с того, кто он вообще такой — тот самый Меркле, чье это непростое дерево?

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

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

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

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

Блокчейн Ethereum использует дерево Меркла, называемое Merkle Patricia Trie: оно предлагает структуру данных, которая может использоваться для хранения всех привязок (ключ, значение) и криптографически аутентифицируется. Он обновляется с течением времени, так как существует одно глобальное дерево состояний. Все данные контракта хранятся в хранилище. Каждый блок имеет свою собственную таблицу транзакций, в которой хранятся пары (ключ, значение). Каждый блок содержит отдельное дерево квитанций, которое никогда не обновляется.

Что такое деревья Веркла и как они работают?

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

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

В деревьях Веркла используется система проверки, называемая полиномиальными обязательствами: она опирается на полиномиальные функции для описания данных. Древовидная структура Verkle напоминает текущее дерево Merkle Patricia в Ethereum. По сути, каждый узел имеет одно из трех свойств:

  • Пусто.
  • Это листовой узел с ключом и значением.
  • Это промежуточный узел с определенным количеством дочерних узлов («шириной» дерева).

Деревья Merkle против деревьев Werkle

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

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

Какова важность деревьев Меркла и Веркла в блокчейне?

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

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

Как идентифицировать дерево Меркла? Листовые узлы, нелистовые узлы и корень Меркла — это три основные части дерева Меркла в контексте блокчейнов. Хэши транзакций или идентификаторы транзакций (TXID) находятся в листовых узлах, которые можно просмотреть в обозревателе блоков. Затем над листовыми узлами попарно хешируется слой нелистовых узлов. Нелистовые узлы хранят хэш двух конечных узлов, которые они представляют внизу.

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

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

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

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

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

По сравнению с идеальными деревьями Merkle, размеры доказательств Verkle Tree могут быть уменьшены в шесть-восемь раз (и более чем в 20-30 раз по сравнению с Merkle Patricia Trie, который в настоящее время использует Ethereum).

Деревья Merkle против деревьев Werkle

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

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

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

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

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

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

В общем, все деревья хороши и по-своему полезны.


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

Стать Digital профессионалом.

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

Информация для Вас была полезна?
0
0
0
0
0
0
0

Похожие статьи

Кнопка «Наверх»