Що таке дерево Меркле? Простий посібник із дерев Merkle

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

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

Усе про дерева Меркле

Історія Merkle Trees починається в далекому 1979 році з хлопця на ім'я Ральф Меркл. Під час навчання в аспірантурі Стенфордського університету Меркл написав наукову роботу під назвою « Сертифікований цифровий підпис ». У цьому есе Меркл описав метод створення цифрових підписів і створив новий, надзвичайно ефективний метод створення криптографічних доказів. Іншими словами, він розробив процес перевірки даних, який дозволив би комп’ютерам виконувати свою роботу набагато, набагато швидше, ніж будь-коли раніше.

Меркл назвав свою ідею «Підписи дерев» або «Автентифікація дерев». Зараз ця ідея більш відома як дерево Меркла, назване на честь винахідника.

Не буде перебільшенням сказати, що Merkle Trees революціонізували світ криптографії та, як наслідок, принцип роботи зашифрованих комп’ютерних протоколів. Насправді дерева Меркла неодноразово згадуються в есе Сатоші Накамото 2008 року , яке представило світу біткойн. Вони широко використовуються в протоколі Bitcoin.

Отже, що ж таке дерево Меркла? Давай дізнаємось.

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

Усі ці властивості дозволяють хеш-функціям створювати електронні відбитки певного введення. Використовуючи хеш-функції, блокчейн-мережі створюють криптографічний хеш — електронний відбиток — кожної транзакції. Криптографічний хеш транзакції просто називається ідентифікатором транзакції. Майже для кожного протоколу блокчейну кожен ідентифікатор транзакції є 64-символьним (256-бітним) буквено-цифровим рядком даних.

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

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

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

Що таке корінь Меркле?

Один 256-бітний рядок, який створює дерево Меркла, називається коренем Меркла. Кожен блок у блокчейні має рівно один. І, як ми щойно згадували, корінь Merkle є важливою частиною даних, оскільки він дозволяє комп’ютерам перевіряти інформацію з неймовірною швидкістю та ефективністю.

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

Наприклад, припустімо, що один блок містить 512 транзакцій. Дерево Merkle розпочнеться з групування цих 512 ідентифікаторів транзакцій у 256 пар. Потім ці 256 пар ідентифікаторів транзакцій пройшли б математичний процес — функцію хешування або алгоритм хешування, як його іноді називають, — і ми б отримали 256 нових 64-символьних криптографічних хешів.

Той самий процес відбувається знову. Ці 256 нових хешів будуть об’єднані в пари та перетворені на 128 хешів. Процес повторюється, щоразу зменшуючи кількість хешів наполовину, поки не залишиться лише один хеш. Цей єдиний хеш є нашим коренем Merkle.

Простий приклад дерева Меркле

Щоб зрозуміти цю концепцію, давайте розглянемо дуже простий приклад дерева Меркла. Уявіть, що на одному конкретному блоці було виконано 8 транзакцій. Насправді ідентифікатори транзакцій складаються з 64 символів, але для простоти припустімо, що вони містять лише 8 символів. Щоб зробити це ще простіше, давайте використовувати лише цифри (і взагалі ігнорувати літери).

Отже, у цьому прикладі наші вісім ідентифікаторів транзакцій будуть такими:

• 11111111
• 22222222
• 33333333
• 44444444
• 55555555
• 66666666
• 77777777
• 88888888

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

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

Ось так виглядало б наше Дерево Меркла:

Зверніть увагу, що кількість кодів скорочується вдвічі на кожному кроці вниз по Дереву Меркла. Ми починаємо з 8 ідентифікаторів транзакцій і лише після 3 кроків отримуємо один код — корінь Merkle. У цьому прикладі наш корінь Merkle — це код у нижньому полі: 12345678.

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

Ефективність і швидкість: переваги дерев Меркле

Припустімо, що ми хочемо підтвердити ідентифікатор транзакції в нашому поточному прикладі. Боб каже, що він заплатив Алісі певну суму біткойнів, і повідомляє нам, що ідентифікатор транзакції – 88888888. Він також надсилає нам 3 хеші: 77777777, 55556666 і 11223344. Це вся інформація, яку потрібно надіслати або отримати, щоб підтвердити платіж Боба Алісі.

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

Ось як це працює. Ми вже маємо Merkle Root блоку, тому Бобу не потрібно надсилати нам його. Він надсилає нам свій ідентифікатор транзакції та 3 додаткові хеші, які ми перерахували вище. Він також надсилає крихітну інформацію про порядок і розташування, у якому слід використовувати хеші. Тепер все, що нам потрібно зробити, це запустити алгоритм хешування на наборі даних, які надав Боб.

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

Потім ми беремо другий код, який надіслав нам Боб, 55556666, і хешуємо його новим кодом 77778888, який ми щойно отримали. Це, звичайно, дає число 55667788.

Нарешті, ми хешуємо третій код, який нам надав Боб, 11223344, з іншим новим кодом, який ми отримали, 55667788, і отримуємо правильний корінь Merkle: 12345678.

Зауважте, що нам потрібні лише 3 коди від Боба, і нам потрібно лише три рази запустити алгоритм хешування, щоб переконатися, що транзакція Боба дійсна. Це означає, що наш комп’ютер виконав менше половини роботи, яка була б потрібна для перевірки всього Дерева Меркла. Оригінальна діаграма дерева Меркла містить 15 чисел, а алгоритм хешування потрібно виконати 7 разів. Але для перевірки транзакції Боба не потрібно більше половини цього дерева!

Процедури перевірки спрощено з Merkle Tree

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

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

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

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

Дерева Merkle також є основоположною концепцією у вирішенні платформи Komodo проблеми масштабованості блокчейна. Рішення Komodo для масштабування забезпечує повну взаємодію блокчейнів і дозволить Komodo обробляти транзакції швидше, ніж будь-який інший сервіс обробки платежів на планеті. Наразі нова технологія масштабування Komodo обробляє понад 20 000 транзакцій на секунду в середовищі тестування.

Відмова від відповідальності:

1. Цю статтю передруковано з [komodo]. Усі авторські права належать оригінальному автору [Делтон Роудс]. Якщо є заперечення щодо цього передруку, будь ласка, зв’яжіться з командою Gate Learn , і вони негайно розглянуть це.
2. Відмова від відповідальності: погляди та думки, висловлені в цій статті, належать виключно автору та не є жодною інвестиційною порадою.
3. Переклади статті на інші мови виконує команда Gate Learn. Якщо не зазначено вище, копіювання, розповсюдження або плагіат перекладених статей заборонено.