Дерева Меркла проти дерев Веркла, пояснення
Що таке дерева Меркла і як вони працюють?
Дерево, яке використовує криптографічні хеш-алгоритми, називають деревом Меркла.
Хеш-дерево, також відоме як дерево Меркла, має позначені листові вузли криптографічними хешами блоків даних. Крім того, воно має позначені не-листові вузли хешами міток дочірніх вузлів.
Кожен вузол створює дайджест, який рекурсивно залежить від усіх характеристик у своїй піддереві, а також додає одну або кілька атрибутів до листових вузлів. У структурі дерева Меркла листові вузли обчислюють хеш власних характеристик, а батьківські вузли обчислюють дайджести із конкатенації дайджестів своїх дочірніх вузлів (зліва направо).
А хто ж створив дерева Меркла? Ральф Меркл розробив дерева Меркла у 1988 році для створення сильніших цифрових підписів. Дерева Меркла ефективно перевіряють правильність і цілісність даних, знижуючи при цьому вимоги до пам’яті для перевірки. Крім того, порівняно з іншими структурами даних, дерева Меркла займають менше дискового простору, що є однією з ключових переваг цієї структури.
Отже, чи є Ethereum деревом Меркла? Блокчейн Ethereum використовує дерево Меркла, яке називається Merkle Patricia trie. Воно пропонує структуру даних, яка може використовуватися для зберігання всіх пар ключ-значення з криптографічною автентифікацією.
Крім того, всі спроби з дерева Меркла в шарі виконання Ethereum використовують Merkle Patricia Trie. Державне дерево оновлюється з часом, оскільки існує єдине глобальне державне дерево. Усі дані контракту зберігаються в дереві зберігання. Кожен блок має власне дерево транзакцій, яке зберігає пари ключ-значення. У кожному блоці є окреме дерево квитанцій, яке ніколи не оновлюється.
Що таке дерева Веркла та як вони працюють?
Подібно до дерев Меркла, дерева Веркла дозволяють упорядковувати великий обсяг даних та створювати короткий “свідок” для кожного елемента даних чи групи даних, який можна підтвердити, маючи доступ до кореня дерева.
Однак найбільш важливою характеристикою дерев Веркла є їх ефективність у плані розміру доказів. Для дерева з мільярдом точок даних дерево Веркла вимагатиме менше 150 байтів для створення доказу, тоді як звичайне бінарне дерево Меркла потребує близько 1 кілобайта. Дерева Веркла застосовують систему доказів під назвою поліноміальні зобов’язання, які базуються на поліноміальних функціях для опису даних.
А хто ж створив дерева Веркла? У 2018 році Джон Кузмаул представив дерева Веркла, які досі не настільки відомі, як багато інших важливих криптографічних структур. Структура дерев Веркла схожа із поточним деревом Merkle Patricia в Ethereum. По суті, кожен вузол має одну з трьох властивостей:
- Вузол є пустим.
- Це листовий вузол із ключем і значенням.
- Це проміжний вузол із визначеною кількістю дочірніх вузлів (ширина дерева).
Хеш значень дочірніх вузлів використовується для розрахунку значення проміжного вузла. Однак дерева Веркла є масштабнішими, ніж дерева Меркла-Патріції, що є однією з їх переваг і відмінностей у структурі. Єдине обмеження полягає в тому, що зі збільшенням ширини доказів генерація доказів починає вимагати більше часу. Таким чином, довжина доказу зменшується зі збільшенням ширини.
Яке значення мають дерева Меркла і Веркла у блокчейні?
Дерева Меркла використовуються в Bitcoin і інших криптовалютах для ефективнішого та безпечнішого шифрування блокчейн-даних. Дерева Веркла дозволяють зменшити розмір доказів, що особливо важливо для майбутніх оновлень масштабованості Ethereum.
Як визначити дерево Меркла? Листові вузли, не-листові вузли та корінь Меркла є трьома основними частинами дерева Меркла у контексті блокчейну. Хеші транзакцій або ID транзакцій (TXIDs) зберігаються у листових вузлах, які можна переглядати у досліднику блоків. Вище за рівнем листових вузлів знаходиться шар не-листових вузлів, які хешуються попарно. Не-листові вузли зберігають хеш двох вузлів, що знаходяться нижче них.
Пов’язано: Що таке блокчейн і як він працює?
Шар не-листових вузлів створює все менше вузлів, зменшуючись удвічі з кожним шаром. На фінальному рівні не-листових вузлів два залишкові вузли утворюють корінь Меркла (використовується для перевірки листових вузлів), де проходить останній хеш у дереві Меркла.
Корінь Меркла, збережений у даних блоку, можна порівняти з коренем Меркла, збереженим у заголовку, що дозволяє майнеру швидко виявляти маніпуляції. Докази Меркла поєднують значення, яке потрібно підтвердити, та хеш-значення для визначення кореня Меркла. Вони також підтримують спрощену перевірку платежів (SPV), яка дозволяє підтверджувати транзакції без завантаження всього блоку або блокчейну. Це дозволяє використовувати крипто-гаманці або полегшені вузли для здійснення транзакцій.
Дерева Веркла забезпечують суттєве скорочення розмірів доказів для великого обсягу даних у порівнянні з деревами Меркла. У дереві Веркла докази можуть бути зменшені у розмірах у 6-8 разів у порівнянні з ідеальними деревами Меркла або навіть у 20-30 разів у порівнянні із Merkle Patricia деревами Ethereum.
Дерева Меркла проти дерев Веркла
Між двома типами дерев існує багато відмінностей, особливо стосовно надання доказів Меркла і Веркла.
Повний набір сестринських вузлів у дереві Меркла, включаючи дерева Меркла-Патріції, є доказом значення. Доказ повинен включати всі вузли в дереві, які мають будь-який спільний батьківський вузол з вузлом, який ви хочете підтвердити. У той час як у дереві Веркла потрібно лише вказати шлях плюс трохи додаткової інформації як доказ — навіть не потрібно додавати сестринські вузли.
Основна ідея дерева Веркла полягає в заміні криптографічних хеш-функцій на векторні зобов’язання. Дерево Веркла виконує ту ж функцію, що й дерево Меркла. Однак з точки зору розміру в байтах вони набагато ефективніші, що є основною різницею.
Завдяки своїй деревоподібній структурі, докази Меркла легко оновлюються частково, тоді як поліноміальні зобов’язання в деревах Веркла потребують повної зміни всієї кривої, що ускладнює обчислення свідків.
Використання дерев Меркла дозволяє людям у всьому світі легко проводити транзакції з криптогаманцями навіть на персональних комп’ютерах або смартфонах. На противагу, одне з ключових застосувань дерев Веркла — це заміна хешів на векторне зобов’язання, підвищуючи ефективність дерева з ширшими галуженнями.
Придбайте ліцензію на цю статтю. Працює завдяки SharpShark.
