Дерево Меркла та його роль у блокчейні

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

У випадку з криптовалютами база даних на основі дерева Меркла допомагає безпечно поділити дані блока, не допускаючи їхньої втрати, пошкодження чи внесення змін. Такий спосіб роботи з даними дає змогу перевіряти дійсність конкретних трансакцій, не завантажуючи весь блокчейн на терабайти даних. Це надійний і безпечний криптографічний метод запуску блокчейну.

У результаті краху великої централізованої біржі (CEX) — FTX, багато бірж CEX сформували механізм підтвердження резервів (Proof of Reserves, PoR) на базі дерева Меркла у спробі запевнити користувачів у безпеці їхніх коштів. У цій статті розглядається суть дерева Меркла, його роль у блокчейні та способи перевірки користувачем коректності даних про його кошти за допомогою дерева Меркла.

Хто розробив дерево Меркла?

Ідею дерева Меркла запропонував інформатик Ральф Меркл, відомий працею над криптографією з відкритим ключем, у статті 1987 року «Цифровий підпис на основі традиційної функції шифрування». Меркл також придумав і криптографічне хешування.

Що таке дерево Меркла?

Дерево Меркла — це математична структура даних на основі хешу, яка об’єднує підсумкові дані про всі трансакції у блоці. У цей спосіб можна швидко й децентралізовано перевірити правильність даних. Завдяки своїм функціональним можливостям дерево Меркла використовується ефективніше й безпечніше в шифруванні даних блокчейну. 

Дерево Меркла часто використовується в однорангових мережах (P2P), де потрібен обмін інформацією та незалежна перевірка її коректності. Розгляньмо дерево Меркла та його особливості докладніше.

Структура дерева Меркла

Дерево Меркла або, іншими словами, хеш-дерево, має двійкову структуру дерева, де хеші даних трансакцій у нижньому рядку називаються «листовими вузлами», проміжні хеші — «нелистовими вузлами», а хеш у верхній частині — «коренем». Попри те, що більшість реалізацій хеш-дерева мають двійковий характер (кожен вузол має два дочірні вузли), дочірніх вузлів може бути набагато більше.

Джерело: Simplilearn

У структурі дерева Меркла видно, що всі трансакції згруповані парами. Кожна пара має обчислений хеш, що зберігається безпосередньо в материнському вузлі. Ці вузли також групуються в пари, а їхній хеш зберігається на наступному вищому рівні. Цей процес триває, поки не досягне кореня дерева Меркла.

Тепер розгляньмо кожен з вузлів докладніше.

Листові вузли

Це хеші кожної криптовалютної трансакції в блоці, які також називаються «ідентифікатор трансакції» (TXID). Ви бачите хеш трансакції, шукаючи її в провіднику блоків.

Нелистові вузли

Потім листові вузли попарно хешуються, і так над листовими вузлами формується шар нелистових вузлів. Їх називають нелистові вузли, тому що, на відміну від листових вузлів, вони зберігають хеш двох листових вузлів, які він представляє, і не містять ідентифікаторів трансакцій (або хешів). Тому хешів (або вузлів) у шарі нелистових вузлів над листовими вузлами вдвічі менше, ніж у шарі листових вузлів. Зі звуженням дерева догори ці шари нелистових вузлів продовжують хешуватись у парах, що в результаті дає вдвічі меншу кількість вузлів на шар. На останньому рівні нелистових вузлів є два вузли. Вони утворюють корінь Меркла і є точкою останнього хешування в дереві Меркла.

Корінь Меркла

У випадку з Bitcoin хеші всіх трансакцій об’єднуються в один хеш і зберігаються в заголовку блока. Цим хешем виступає саме корінь Меркла, також відомий під назвою «кореневий хеш». За допомогою цього кореня Меркла можна перевірити листові вузли (ідентифікатори/хеші трансакцій) в основі дерева Меркла. У разі застосування щодо криптовалют корінь Меркла забезпечує незмінність, неушкодженість і цілісність блоків даних.

Дерево Меркла є двійковим, тобто в дереві правильної структури загальна кількість різних листових вузлів має бути парною. Якщо кількість листових вузлів непарна, попередній хеш дублюється, щоб отримати парну кількість вузлів.

Джерело: Techskill Brew

Принцип роботи дерева Меркла

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

Дерево Меркла утворюється хешуванням різних пар вузлів, поки не залишиться лише один хеш, який і називається корінь Меркла. Ці дерева формуються знизу догори, і кожна трансакція складається з хешів. Кожний листовий вузол є окремим хешем даних. На відміну від них, нелистові вузли є хешами попередніх хешів.

Розгляньмо дерево Меркла, що складається з чотирьох трансакцій — D0, D1, D2 і D3. Кожна трансакція хешується, а хеш потім зберігається безпосередньо на листовому вузлі. У результаті цього утворюється хеш N0, N1, N2 і N3. Будь-яка послідовна пара листових вузлів отримує підсумок у материнському вузлі шляхом хешування хешу N0 і хешу N1. Так з’являється хеш N4. Якщо хеш N2 і хеш N3 разом хешуються, виникає хеш N5. Два нові хеші — N4 і N5 — також хешуються, і утворюється корінь Меркла.

Цей процес може відбуватися на великих наборах даних. Корінь Меркла відповідає за узагальнення даних, наявних у конкретних трансакціях. Усі вони зберігаються безпосередньо в заголовку блока. Цей підхід належно забезпечує цілісність даних. Якщо в певний момент змінюється один елемент трансакції, з ним автоматично змінюється і корінь Меркла.

Переваги дерева Меркла

Дерево Меркла для перевірки трансакцій має багато переваг для блокчейн-технології і криптовалютних платформ — від ефективної перевірки достовірності до простоти виявлення випадків втручання.

Ефективність перевірки достовірності даних

Перевірити легітимність трансакції можна практично миттєво. Особливе структурування даних зумовлює потребу в дуже малих обсягах пам’яті під час перевірки, а також у значно меншій обчислювальній потужності. 

Оскільки блокчейни зазвичай складаються з сотень тисяч блоків, кожен з яких може містити до кількох тисяч трансакцій, перевірка даних створює дві основні проблеми — обсяг пам’яті й обчислювальна потужність. Якби у блокчейні не існувало такого поняття як дерево Меркла, на кожному вузлі в мережі довелось би зберігати повну копію кожної трансакції, коли-небудь здійсненої у блокчейні. У рамках перевірки достовірності трансакції вузол мав би порівнювати кожен запис рядок за рядком на предмет того, чи записи в ньому точно збігаються з записами в мережі. Розбіжність між записами ставить безпеку мережі під загрозу. Тому, для порівняння записів на предмет відсутності змін комп’ютер мав би мати набагато більшу обчислювальну потужність. 

З іншого боку, дерево Меркла усуває цю проблему, різко скорочуючи обсяг даних, які потрібно зберігати локально для потреб перевірки. Воно хешує кожен запис у реєстрі, фактично відокремлюючи самі дані від їхнього підтвердження. Не знаючи всіх TXID у блоці, ви можете перевірити TXID за допомогою кореня Меркла в дереві Меркла. Дерево Меркла — це, по суті, чудовий спосіб підтвердження наявності якогось об’єкта в наборі даних, не завантажуючи весь набір. Відтак, для підтвердження трансакцій потрібна менша обчислювальна потужність.

Вища швидкість обробки

У результаті розподілу трансакцій у блоці між валідаторами, вони працюють паралельно, але кожен — над іншою трансакцією. Це набагато ефективніше за метод, де трансакції перевіряються послідовно, одна за одною.

Використання криптогаманця

Завдяки дереву Меркла стало можливим просте підтвердження платежу (Simple Payment Verification, SPV), яке дає змогу підтвердити трансакцію, не завантажуючи цілий блок чи блокчейн. Це дозволяє використовувати легкий вузол-клієнт, офіційно відомий під назвою «криптогаманець», для здійснення вихідних і вхідних трансакцій.

Виявлення випадків втручання

Хеш-структура дозволяє майнерам визначити можливі випадки втручання в трансакції. 

Для кожного блока за допомогою кореня Меркла генерується унікальне хеш-значення. Цей блок пов’язує один блок з іншим у блокчейні, включаючи хеш попереднього блоку. Щоразу, коли у трансакцію вносяться зміни, змінюється і її хеш. У результаті цієї зміни блок стає недійсним, бо вона торкається всіх рівнів аж до кореня Меркла, і його значення змінюється. Своєю чергою, це призводить до зміни хешу наступного блоку, тому решта блокчейну стає недійсною. Так дерево Меркла веде непорушні записи трансакцій блоку.

Завдяки цьому можна запобігти й дублюванню оплати. Якщо користувач намагається продублювати витрату такої ж суми цифрової валюти, для цієї трансакції формується хеш. Якщо він збігається з наявними записами в блокчейні, цю трансакцію відхиляють.

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

Дерево Меркла виявилося важливим елементом блокчейн-технології, бо воно забезпечує швидкість і простоту перевірки достовірності, неможливої з іншими методами. Завдяки дереву Меркла розробники можуть стискати надзвичайно великі набори даних, виключаючи зайві дані й перетворюючи решту даних на хеші. Дерево Меркла має цілу низку особливостей, а саме:

• істотна легкість структури;

• можливість ефективного масштабування;

• паливна ефективність;

• перевірка, чи трансакцію внесено в певний блок;

• базова аутентифікація платежу.

Proof of Reserves (PoR) на базі дерева Меркла

Як уже згадувалося, після краху FTX користувачів почало непокоїти питання захищеності їхніх коштів на CEX. У зв’язку з цим кілька бірж CEX розробили механізм підтвердження резерву (Proof of Reserves) на базі дерева Меркла. У цьому розділі йдеться про підтвердження за Мерклом і про способи перевірки користувачами своїх коштів.

Підтвердження за Мерклом

Підтвердження на базі дерева Меркла — це не ціле дерево Меркла, а його зріз. Він має вигляд масиву або послідовності (жовта ділянка на наступному графіку).

Усі листові вузли й інформація про баланс окремого користувача нашої компанії представлені на рисунку вузлами останнього рівня. Припустімо, що рожеві люди на рисунку — це очікувані отримувачі підтверджень. Ми робимо витяг помаранчевих елементів рисунка рівень за рівнем і представляємо користувачам підтверджувальні документи у порядку висоти. Важливо пам’ятати, що підтвердження за Мерклом складається з двох основних компонентів.

1. Прямі материнські вузли (тобто B і D) цього користувача у витяг не потрапляють.

2. Надається кореневий вузол, тобто корінь Меркла.

Візьмімо для прикладу 10 мільйонів користувачів. Висота дерева обчислюється за математичною формулою так: Log2(10 000 000) = 23,2534966642, тобто висота дерева складає 24 рівні. Відтак, кількість вузлів на рисунку, які свідомо не надаються користувачам, складає 24 - 2 = 22.

Дерево Меркла — це повноцінне двійкове дерево, яке дозволяє обчислити весь обсяг інформації про його материнський вузол на основі знання його лівого та правого вузлів. Вичерпна інформація складається з двох частин — дані про баланс і хеш-дані.

1. Даніпро баланс: дані материнського вузла можуть бути розділені лише на його нижні лівий і правий вузли.

2. Хеш-дані: за кожним вузлом наявні лише дані про баланс, дані про ієрархію дерева та хеш-дані дочірнього вузла (у кожному вузлі зберігаються підсумкові дані лівого та правого вузлів під ним).

Перевірка дерева Меркла передбачає обчислення шляхом виведення B і D і перевірки того, чи:

1. баланс відповідає принципу поділу; і

2. хеш є дійсним.

За допомогою функції хеш-підсумку дерева Меркла користувач може визначити, чи він входить до дерева в цілому, навіть не маючи інформації про кожен фіолетовий вузол на рисунку. Підтвердження за Мерклом є унікальним для кожного користувача. Наприклад, 24-рівневе дерево Меркла вимагає для перевірки інформації про баланс користувача масив з 23 елементів, який лише підтверджує достовірність даних про баланс користувача.

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

Перевірка коректності акаунта Bybit

Ви можете перевірити коректність даних про акаунт Bybit і залишок коштів двома способами.

Інструмент перевірки платформи

Це перший і єдиний у всій мережі спосіб, який зображає процес формування вузла перевірки дерева Меркла в інтуїтивно зрозумілій графічній формі на платформі компанії.

Інструмент самостійної перевірки

Вихідний код генерації дерева Меркла компанії та код перевірки є у відкритому доступі на github. З їхньою допомогою користувач може запрограмувати власну перевірку коректності. Процес обчислення дерева Меркла складається з величезної кількості обчислень на боці користувача, які зазвичай виконуються за допомогою великих даних і Java. 

*Відкритий код Java передбачає відкритість для користувачів без приховування жодної інформації.

Компанія Bybit відкрила такий код, і відтепер професійні користувачі можуть перевірити власний файл підтвердження дерева Меркла. Для цього його треба скопіювати на сторінці підтвердження резервів у власну «закріплену» версію системи, натиснувши кнопку Копіювати дані, і зберегти як файл під назвою myProof.json на локальному диску.

Способи застосування дерева Меркла в блокчейні

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

Bitcoin

На Bitcoin дерево Меркла використовується кількома способами, тому воно є невіддільним елементом платформи Bitcoin в цілому. Фактично ці дерева присутні в кожному заголовку блоку Bitcoin. У заголовок вноситься хеш кожної доступної в блоці трансакції. У випадку з Bitcoin корінь Меркла важливий як для майнінгу, так і для перевірки достовірності.

Майнінг

Блоки Bitcoin складаються із заголовків, які містять метадані, а також із великого списку трансакцій. Зазвичай він більший за заголовок блоку. Майнери хешують дані для створення результату, який відповідає певним умовам, необхідним під час перевірки коректності блоку. На знаходження дійсного блока майнерам може знадобитися здійснити трильйони окремих спроб. Для кожної з них потрібно змінити число в заголовку блоку. Попри те, що блок може містити тисячі окремих трансакцій, кожна з них повинна бути хешована.

Корінь Меркла дозволяє майнерам значно підвищити ефективність цього процесу. З початком процесу майнінгу достатньо всього внести трансакції в дерево Меркла, після чого кореневий хеш можна помістити в заголовок блока. На цьому етапі майнерові потрібно хешувати не весь блок, а лише його заголовок.

Перевірка достовірності

На Bitcoin задіяно ще один аспект кореня Меркла — кредитне плече, де на перший план виходять легкі клієнти. Коли вузол працює на відносно слабкому пристрої з обмеженими ресурсами, користувачі не можуть завантажити й хешувати кожну трансакцію в одному блоці. Натомість вони можуть запросити підтвердження за Мерклом, тобто підтвердження наявності трансакції в блоці. Оскільки під час перевірки достовірності задіяно менше хешів, ця процедура не вимагає такої великої кількості обчислювальних ресурсів.

Ethereum

Ethereum працює на базі дещо видозміненої версії дерева Меркла — дерево Меркла-Патриція. На відміну від Bitcoin з єдиним двійковим деревом, кожен блок у блокчейні Ethereum складається з трьох дерев Меркла. Кожен із трьох коренів має своє призначення.

Початковий корінь вважається коренем кожної трансакції. Другий корінь показує статус трансакції. А остаточний корінь є квитанцією трансакції. Переглянувши корінь Меркла, користувач може перевірити наявність трансакції в певному блоці, а також дізнатися баланс свого рахунку.

Платформа Hyperledger Fabric

Блокчейн-платформа Hyperledger Fabric використовує дерево Меркла для обчислення даних блока у вигляді хешу. Хеш-значення визначає ширину дерева Меркла. Дерева Меркла на платформі Hyperledger Fabric працюють так само, як і на платформі Bitcoin.

Підсумки

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