Дерево Меркла або хеш-дерево (назване на честь Ральфа Меркла, який запатентував його у 1979 році) – це дерево, в якому кожен листовий вузол визначається криптографічним хешем блоку даних, а кожен не листовий вузол – криптографічним хешем міток своїх дочірніх вузлів. Більшість реалізацій дерева Меркла є бінарними (кожен вузол має два дочірні вузли), але теоретично вони можуть мати набагато більше дочірніх вузлів.
Біткоїн використовує дерево Меркла для ефективнішого шифрування даних блокчейну. В такий спосіб можна представити всі транзакції, що містяться у блоці за допомогою хешів. З практичної точки зору такий підхід дозволяє досягти швидкої та надійної перевірки цілісності та незмінності всіх представлених даних. Уперше застосував дерево Меркла до мережі Біткоїна безпосередньо сам Сатоші Накамото.
Демонстрація того, що листовий вузол є частиною певного двійкового хеш-дерева, вимагає обчислення кількості хешів, пропорційної логарифму кількості листових вузлів дерева; така схема обчислення відрізняється від хеш-списків, де кількість хешів пропорційна кількості самих листових вузлів.
Для підтвердження інформації з дерева Меркла використовується спеціальний математичний метод – корінь Меркла. У такий спосіб протокол Біткоїна може гарантувати, що блоки даних, які надсилаються через пірингову мережу, є цілими, неушкодженими та незмінними. Як наслідок – ефективно нейтралізуються ризики подвійної трати чи інші маніпуляції з коїнами.
Хеш-функція відображає будь-який тип довільних даних будь-якої довжини у вихідні дані фіксованого розміру. Щобільше, навіть незначна зміна у початкових даних призводитиме до зовсім іншого хешу. У Біткоїні використовується надійний алгоритм хешування SHA256.
Наприклад, слово «Bitcoin» буде представлено таким хешем: b4056df6691f8dc72e56302ddad345d65fead3ead9299609a826e2344eb63aa4
А «Bitcoin!» – таким: b81bf654dc352f66a0fcb51da8a260b60cf4a92dcf01f04f5f523961d9f6a6d7
Зазначимо, що хеш став зовсім іншим, а загальна кількість знаків залишилася незмінною.
Використання хеш-функцій у протоколі Біткоїна доречно через наступні причини. По-перше, вони детерміністичні, тобто одна й та сама інформація буде завжди асоціюватися з тим самим хешем (за умови, що використовується той самий алгоритм хешування). По-друге, досягається максимальна ефективність у розрахунках і обчисленнях. Отже, наявні енергоресурси використовуються у найбільш ефективний спосіб.
Насамкінець після створення певного алгоритму хешування до нього вже неможливо внести зміни. Таким чином досягається захищеність від впливу розробників чи інших несанкціонованих спроб змінити презентацію даних. Стабільність хешів сприяє сталій роботі мережі та інтеграції різноманітних функцій у такий спосіб, який відповідає інформаційним потребам власників BTC.
Дерево Меркла представляє всі транзакції в блоці й генерує цифровий відбиток усього набору операцій, що дозволяє користувачеві перевірити, чи включена певна транзакція в блок. Дерева Меркла створюються шляхом багаторазового хешування пар вузлів, поки не залишиться тільки один хеш; він відомий як корінь Меркла або кореневий хеш. Вони будуються знизу, використовуючи ідентифікатори транзакцій, які є хешами окремих операцій. Кожна не листова вершина є хешем попереднього хешу, а кожна листова вершина є хешем даних транзакції.
Використання дерева Меркла є одним зі способів практичної реалізації ідей Біткоїна у найбільш ефективний і надійний спосіб. Його можна використовувати для перевірки цілісності даних. Порівняно з іншими структурами даних, дерево Меркла займає дуже мало оперативної пам’яті.
У разі відсутності дерева Меркла кожна повна нода повинна була б зберігати повну копію кожної транзакції біткоїна, яка коли-небудь була здійснена. Такий великий обсяг даних заважав би більшості біткоїнерів використовувати повні ноди. Як наслідок – мережа могла б бути більш вразливої до спроб подвійної трати чи інших типів атак.
Іншою перевагою дерев Меркла є те, що їх можна розбити на невеликі фрагменти даних для перевірки. Отже, користувач може ефективно перевірити наявність та коректність певних транзакцій. Таким чином, уможливлюється взаємний контроль над операціями та підтримується функціонування повністю децентралізованої системи, що не потребує довіри до третіх осіб.
До того ж формат даних є ефективним, а перевірка цілісності даних займає лише кілька хвилин. Через те, що такі перевірки не потребують значних обчислювальних ресурсів та часу, вони можуть бути незалежно реалізовані різними учасниками мережі. З одного боку, всі учасники мережі можуть прийти до певного консенсусу щодо цілісності даних, а ефективний контроль створить додаткові стимули до дотримання правил мережі та здійснення лише коректних транзакцій.
Дерева Меркла хешують записи в реєстрі, таким чином відокремлюючи доказ даних від самих даних. Навіть перевірка невеликого обсягу інформації дозволяє підтвердити цілісність транзакцій, фокусуючись на необхідних доказах даних. У такий спосіб наочно реалізується один із базових принципів біткоїнерів: «Не довіряй – перевіряй».
Стрімкий розвиток мережі Біткоїна та залучення нових користувачів призводить до експоненційного зростання обсягу транзакцій. Традиційні методи не дозволяють перевірити цілісність і коректність транзакцій швидко і якісно. Але ці проблеми можуть ефективно розв’язуватися за допомогою дерев Меркла, що аналізують докази даних не завантажуючи безпосередньо самі дані. Частини дерев Меркла також можуть аналізуватися незалежно, сприяючи таким чином задоволенню потреб учасників.