Дерево Меркле - це структура даних, яка використовується в додатках з інформатики. У біткойнах та інших криптовалютах дерева Merkle служать для кодування даних blockchain більш ефективно та безпечно.
Їх також називають «двійковими деревами хешу».
Порушення дерева Меркла
У блокчейні bitcoin блок транзакцій проводиться за допомогою алгоритму для генерації хеша, який представляє собою рядок цифр і букв, за допомогою яких можна перевірити, чи заданий набір даних такий самий, як і початковий набір транзакцій, але не отримати оригінальний набір транзакцій. Однак програмне забезпечення Bitcoin не виконує весь блок даних про транзакції - що становить 10 хвилин в середньому - через хеш-функцію за один раз. Швидше хешируйте кожну транзакцію, потім кожна пара транзакцій об'єднується і хеширується разом і так далі, поки не буде одного хешу для всього блоку. (Якщо є непарна кількість транзакцій, одна транзакція подвоюється, а хеш - зв'язується з самим собою.)
Візуалізована ця структура нагадує дерево. На діаграмі нижче "T" позначає транзакцію, H - хеш. Зауважте, що зображення сильно спрощене; середній блок містить понад 500 транзакцій, а не вісім.
Хеші в нижньому ряду називаються "листям", проміжні хеші - "гілками", а хеш вгорі - як "корінь". Корінь Меркле заданого блоку зберігається у заголовку: наприклад, корінь Меркле блоку # 482819 є e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Корінь поєднується з іншою інформацією (версія програмного забезпечення, хеш попереднього блоку, часова мітка, цільова складність і відсутність), а потім виконується через хеш-функцію, щоб створити унікальний хеш блоку: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 4828 у випадку. Цей хес насправді не включений у відповідний блок, але наступний; він відрізняється від кореня Меркле.
Дерево Merkle корисно, оскільки дозволяє користувачам перевірити певну транзакцію, не завантажуючи весь блокчейн (понад 130 гігабайт на кінець серпня 2017 року). Наприклад, скажіть, що ви хотіли переконатися, що транзакція T D включена до блоку на схемі вище. Якщо у вас є кореневий хеш (H ABCDEFGH), процес схожий на гру в судоку: ви запитуєте мережу про H D, і він повертає H C, H AB і H EFGH. Дерево Меркле дозволяє переконатися, що все враховується трьома хешами: дані H AB, H C, H EFGH, а корінь H ABCDEFGH, H D (єдиний відсутній хеш) повинен бути присутнім у даних.
Дерева Меркле названі на честь Ральфа Меркле, який запропонував їх у документі 1987 року під назвою "Цифровий підпис на основі функції звичайного шифрування". Меркле також винайшов криптографічний хешинг.
