Merkle Tree

Гаманець показує, що платіж включено до блока. Як це перевірити, не завантажуючи весь вміст? Тут допомагає Merkle Tree. Транзакції спочатку представляють хешами — короткими криптографічними відбитками. Їх поступово об’єднують в один спільний відбиток, корінь. Заголовок містить цей Merkle root і пов’язує блок із його транзакціями. Корінь не є архівом, з якого можна відновити всі платежі; він слугує для перевірки наданих даних. [1] [2]

Уявіть чотири транзакції A, B, C і D. Беремо їхні відбитки, з’єднуємо A з B й обчислюємо новий хеш AB. Так само з C і D отримуємо CD. Насамкінець з’єднуємо відбитки AB і CD та обчислюємо корінь. Літери лише позначають транзакції й проміжні результати, а не справжні хеші. Процес нагадує перевернуте дерево: багато листків через гілки сходяться до одного кореня. Більше транзакцій додає рівні, але принцип незмінний. [3]

Для перевірки B ви маєте її дані й обчислюєте відбиток. Достатньо отримати відбиток A і спільний відбиток CD разом із правильним порядком. З A і B утворюєте AB, потім з AB і CD обчислюєте корінь та порівнюєте його з коренем у заголовку. Цей додатковий шлях називається Merkle proof. Вміст A, C і D не потрібен. Для збалансованого дерева з 1024 транзакцій шлях містить 10 сусідніх хешів. Тож доказ зростає значно повільніше за повний список транзакцій. [2] [3]

Збіг доказу з коренем не означає, що можна сліпо довіряти наданому заголовку. Потрібно також перевірити Proof of Work: чи відповідає результат майнінгових обчислень установленій складності? Окремо перевіряють зв’язок заголовка з відповідним ланцюжком. Навіть після цього Merkle proof не перевіряє всі підписи й дотримання правил усіма транзакціями блока. Це робить Full Node. Тому описана у whitepaper спрощена перевірка платежів SPV має інші припущення безпеки, ніж повна валідація. Реорганізація також може вивести блок з активної гілки: його вміст і далі можна підтвердити, але місце платежу в поточній історії може змінитися. [2]

У звичайному дереві Bitcoin листки — це ідентифікатори txid у порядку транзакцій блока, починаючи з Coinbase Transaction — особливої транзакції, через яку майнер отримує винагороду за блок. Пари з’єднують як байти й двічі хешують SHA-256. Якщо на рівні лишається останній хеш без пари, для цього обчислення його подвоюють; нового платежу не виникає. Для єдиної транзакції її txid одразу є коренем. Подвоєння вимагає ретельних перевірок дублікатів в реалізації. Оновлення протоколу SegWit також відокремлює дані witness, наприклад підписи. З блоком їх пов’язує ще один криптографічний відбиток, записаний у Coinbase Transaction. Цей відбиток називається witness commitment. Звичайне дерево txid не можна плутати з деревом witness. [3] [4]