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

Творцем концепції хеш-дерева є професор Ральф Меркл. Він винайшов спосіб представлення цифрових підписів 1979 року. Патентом на технологію володіє Стенфордський університет.

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

Для чого потрібне дерево Меркла?

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

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

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

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

Як працює дерево Меркла?

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

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

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

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

Як дерево Меркла використовується в біткоїні?

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

Для оптимізації обчислень вузли біткоїна формують заголовки. Вони включають такі елементи:

• номер версії блоку;
• хеш попереднього блоку;
• корінь дерева Меркла;
• тимчасову мітку;
• мету складності майнінгу;
• одноразовий код (nonce), використаний під час генерації блоку.

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

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

1. Знаходяться хеші (ідентифікатори) транзакцій, включених до блоку: hash(L1), hash(L2), hash(L3) і так далі. Вони формують листя дерева.
2. На наступний рівень поміщаються хеші від суми двох сусідніх ідентифікаторів: hash(hash(L1) + hash(L2)). У бінарному дереві число вузлів на кожному рівні має бути парним. В іншому випадку хеш з останнього осередку дублюється і поміщається в додатковий елемент.
3. Процес хешування суми даних повторюється до отримання кореня Меркла.

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

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

Які переваги дає дерево Меркла?

Хеш-дерева дають змогу спростити перевірку приналежності транзакції до певного блоку і забезпечити цілісність інформації під час її передачі. Метод необхідний для спрощеної верифікації платежів. Сатоші Накамото запропонував використовувати SPV у white paper біткоїна.

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

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

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

Метод SPV дає змогу легкому клієнту ефективно взаємодіяти з блокчейном і знижує обсяг завантажуваної інформації. Наприклад, розмір блоку з п’ятьма транзакціями може становити 500 кілобайт, а доказ Меркла займає всього 140 байт.

Яке дерево хешів використовується в Ethereum?

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

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

На відміну від біткоїна, блокчейн Ethereum використовує три хеш-дерева:

• транзакцій;
• станів;
• дерево, що містить дані про результати виконання транзакцій.

У заголовок блоку входять три кореневих хеші. Ethereum дає змогу створювати легкі клієнти, здатні виконувати базовий набір операцій:

• перевірити наявність транзакції в блоці;
• підтвердити існування певної адреси;
• визначити баланс користувача;
• дізнатися результат виконання операції або смарт-контракту.

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

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

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

Корінь дерева має визначатися виключно даними і не залежати від його параметрів. Відповідно необхідна можливість внесення оновлень у будь-якому порядку.

Префіксне дерево дає змогу вирішити зазначені труднощі. В Ethereum кожен елемент структури має 16 дочірніх. Цей підхід оптимальний для кодування вузлів у шістнадцятковому форматі.

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