Зміст
Концепція дерева Меркла була запропонована на початку 80-х років Ральфом Мерклем – вченим, фахівцем з комп'ютерної техніки, відомим своєю роботою в області
криптографії з публічним ключем.
Дерево Меркла – це структура, яка використовується для ефективної перевірки цілісності даних у наборі. Вони особливо цікаві в контексті
однорангових мереж, де учасникам необхідно обмінюватись та незалежно перевіряти інформацію.
Хеш-функції лежать в основі деревоподібних структур Меркла, тому ми рекомендуємо вам ознайомитися зі статтею
Що таке хешування? перш ніж продовжити.
Припустимо, ви хочете завантажити великий файл. При роботі з
програмним забезпеченням із відкритим вихідним кодом вам, як правило, потрібно перевірити, чи збігається хеш завантаженого вами файлу з хешем, опублікованим розробниками. Якщо це так, ви знаєте, що файл, який є на вашому комп'ютері, такий самий, як і у них.
Якщо хеші не збігаються, у вас проблема. Ви або завантажили шкідливий файл, що маскується під програмне забезпечення, або він завантажився некоректно і, отже, не працюватиме. В останньому випадку ви, ймовірно, не будете раді, якщо вам довелося чекати деякий час, доки файл завантажиться. Тепер вам потрібно перезапустити процес та сподіватися, що він пройде вдало.
Ви могли б подумати "Якби тільки був більш простий спосіб зробити це". На щастя, саме тут на допомогу приходять дерева Меркла. З одним із них ваш файл буде розбитий на шматки. Якби це був файл розміром 50 ГБ, ви могли б розділити його на 100 частин, кожна з яких мала б розмір 0,5 ГБ. Потім він завантажуватиметься частинами. По суті це те, що ви робите, коли завантажуєте файли через торрент.
У цьому випадку ваше джерело надасть вам хеш, відомий як "Корінь Меркла". Цей єдиний хеш є репрезентацією кожного фрагмента даних, що складають ваш файл. Але корінь Меркла значно спрощує перевірку даних.
Для простоти давайте візьмемо приклад, у якому використовуємо файл розміром 8 ГБ, розбитий на вісім частин. Назвемо різні фрагменти від A до H. Потім кожен фрагмент проходить через хеш-функцію, що дає вісім різних хешів.
Ми пропускаємо кожен із наших восьми фрагментів через хеш-функцію, щоб отримати їхні хеші.
Нарашті, у нас є щось, що має трохи сенсу. У нас є хеш всіх фрагментів, тому якщо один з них помилковий, ми про це дізнаємося, порівнявши його з вихідним, вірно? Можливо, але це також неймовірно неефективно. Якщо у вашому файлі тисячі фрагментів, ви дійсно збираєтеся хешувати їх усі та ретельно порівнювати результати?
Ні. Натомість ми візьмемо кожну пару хешів, об'єднаємо їх, а потім хешуємо разом. Отже, ми хешуємо hA + hB, hC + hD, hE + hF, та hG + hH. У результаті маємо чотири хеші. Потім ми робимо ще один раунд хешування з ними, щоб отримати два. Нарешті, ми хешуємо два, що залишилися, щоб отримати наш головний хеш – корінь Меркла (або кореневий хеш).
Структура має вигляд перевернутого дерева. У нижньому ряду у нас є листя, яке об'єднується для отримання нод і, нарешті, корінь.
Тепер у нас є корінь Меркла, який репрезентує завантажений файл. Ми можемо порівняти цей кореневий хеш із тим, що наданий джерелом. Якщо він збігається – ідеально! Але якщо хеші відрізняються, ми можемо бути впевнені, що дані були змінені. Іншими словами, один або декілька фрагментів створили інший хеш. Таким чином, будь-яка невелика модифікація даних дасть нам зовсім інший корінь Меркла.
На щастя, ми маємо зручний спосіб перевірити, який фрагмент несправний. У нашому випадку, припустимо, це hE. Ви повинні почати з запиту рангу двох хешей, які створили корінь Меркла (hABCD та hEFGH). Ваше значення hABCD має збігатися з їх значенням, оскільки в цьому піддереві немає помилок. Але hEFGH цього не зробить, так що ви повинні перевірити його. Потім ви здійснюєте запит на hEF та hGH, і порівнюєте їх зі своїми. hGH буде виглядати нормально, тому ви знаєте, що hEF є винуватцем. Нарешті, ви порівнюєте хеші hE та hF. Тепер ви знаєте, що hE неправильний, тому ви можете повторно завантажити цей фрагмент.
Підсумовуючи, дерево Меркла створюється шляхом поділу даних на безліч частин, які потім багаторазово хешуються для формування кореня Меркла. Потім ви можете ефективно перевірити, чи не пішло щось не так з частиною даних. Як ми побачимо в наступному розділі, є й інші цікаві застосування.
Хочете почати торгувати криптовалютою? Купуйте Bitcoin на Binance!
Існує декілька варіантів використання дерев Меркла, але тут ми зосередимося на їхній важливості у
блокчейнах. Дерева Меркла необхідні для
Bitcoin та багатьох інших криптовалют. Вони є невід'ємним компонентом кожного
блоку, де їх можна знайти у
заголовках блоків. Щоб отримати листя для нашого дерева, ми використовуємо хеш транзакції (
TXID) кожної транзакції, включеної до блоку.
У цьому випадку коріння Меркла служить для декількох цілей. Давайте подивимося на їхнє застосування в майнінгу криптовалюти та перевірці транзакцій.
Майнінг
Bitcoin блок складається із двох частин. Перша частина – це заголовок блоку, сегмент фіксованого розміру, що містить
метадані для блоку. Друга частина є списком транзакцій, розмір якого варіюється, але, як правило, набагато більше, ніж заголовок.
Майнерам необхідно багаторазово хешувати дані, щоб отримати результат, який відповідає певним умовам для майнінгу дійсного блоку. Вони можуть зробити трильйони спроб, перш ніж знайдуть хоч один. З кожною спробою вони змінюють випадкове число у заголовку блоку (
nonce), щоб отримати інший результат. Але велика частина блоку залишається незмінною. Транзакцій може бути тисячі, і вам все одно доведеться щоразу їх хешувати.
Корінь Меркла значно спрощує процес. Коли ви починаєте майнінг, ви ставити всі транзакції в чергу, які хочете включити, і будуєте дерево Меркла. Ви поміщаєте отриманий кореневий хеш (32 байти) у заголовок блоку. Потім, коли ви займаєтеся майнінгом, вам потрібно хешувати лише заголовок блоку, а не весь блок.
Це працює, тому що процес захищено від несанкціонованого доступу. Ви ефективно підсумовуєте всі транзакції блоку в компактному форматі. Ви не можете знайти дійсний заголовок блоку, а потім змінити список транзакцій, тому що це змінить корінь Меркла. Коли блок надсилається іншим нодам, вони обчислюють корінь зі списку транзакцій. Якщо він не збігається з тим, що в заголовку, вони відхиляють блок.
Верифікація
Є ще одна цікава властивість коріння Меркла, яку ми можемо використати. Це стосується легких клієнтів (нод, які не містять повної копії блокчейну). Якщо ви використовуєте ноду на пристрої з обмеженими ресурсами, вам не потрібно завантажувати та хешувати всі транзакції блоку. Натомість ви можете здійснити запит на доказ Меркла – свідоцтво, надане повною нодою яке доводить, що ваша транзакція знаходиться у певному блоці. Це частіше називають спрощеною перевіркою платежів, або SPV, і було докладно описано
Сатоші Накамото у whitepaper Bitcoin.
Для перевірки hD нам потрібні лише хеші, показані червоним кольором.
Розглянемо сценарій, в якому ми хочемо дізнатися інформацію про транзакцію, TXID якої дорівнює hD. Якщо нам надати hC, ми можемо отримати hCD. Потім нам потрібно hAB для обчислення hABCD. Нарешті, за допомогою hEFGH ми можемо перевірити, чи збігається корінь Меркла з коренем із заголовка блоку. Якщо так, то це доказ того, що транзакція була включена в блок – створити той самий хеш з іншими даними практично неможливо.
У наведеному вище прикладі нам потрібно було хешувати лише тричі. Без доказу Меркла нам довелося б зробити це сім разів. Оскільки блоки містять тисячі транзакцій, використання доказів Меркла економить нам багато часу та обчислювальних ресурсів.
Дерева Меркла зарекомендували себе як дуже корисні для комп'ютерних наук. Як ми побачили, вони неймовірно цінні в блокчейнах. У розподілених системах дерева Меркла дозволяють легко перевіряти інформацію, не перевантажуючи мережу непотрібними даними.
Без дерев Меркла (і коріння Меркла), блоки
Bitcoin та інших
криптовалют не були б такими компактними, як сьогодні. І хоча в легких клієнтах не вистачає конфіденційності та безпеки, докази Меркла дозволяють користувачам перевіряти, чи їх транзакції були включені в блок з мінімальними витратами.
