Дерево Меркле

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

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

Їх також називають “двійковими хеш-деревами”.

Руйнування дерева Меркле

У блокчейні біткойнів блок транзакцій запускається через алгоритм генерування хешу, який являє собою рядок цифр і букв, за допомогою яких можна перевірити, що заданий набір даних збігається з вихідним набором транзакцій, не отримати оригінальний набір операцій. Проте програмне забезпечення Біткойн не запускає весь блок даних про транзакції – представляючи транзакції в середньому на 10 хвилин – за допомогою хеш-функції одночасно. Швидше кожна транзакція хешується, потім кожна пара транзакцій об’єднується і хешується разом, і так далі, поки не буде одного хешу для всього блоку. (Якщо існує непарна кількість транзакцій, одна транзакція подвоюється, а її хеш поєднується з собою.)

Візуалізовано, ця структура нагадує дерево. На діаграмі нижче “Т” позначає транзакцію, “Н” – хеш. Зверніть увагу, що зображення дуже спрощене; середній блок містить понад 500 транзакцій, а не вісім.

Хеші в нижньому ряду називаються “листям”, проміжні хеші – “гілками”, а хеш у верхній частині – “коренем”. Корінь Merkle даного блоку зберігається у заголовку: наприклад, коренем Merkle блоку # 482819 є e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Корінь поєднується з іншою інформацією (версія програмного забезпечення, хеш попереднього блоку, мітка часу, ціль складності та nonce), а потім запускається через хеш-функцію, щоб створити унікальний хеш блоку: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 у випадку з блоком 48 # 28 у випадку з block19. Цей хеш фактично не включений у відповідний блок, а наступний; він відрізняється від кореня Меркле.

Дерево 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 року під назвою ” Цифровий підпис на основі звичайної функції шифрування “. Меркле також винайшла криптографічне хешування.