Що таке Merkle Tree?

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

Міф

Merkle Tree «зберігає» всі транзакції сам по собі. Насправді не зовсім так. Він зберігає лише компактні відбитки цих транзакцій, а дерево можна відтворити з сирих записів у будь-який момент, коли це потрібно.

Як працює Merkle Tree

Уявіть блок платежів, який потребує швидкого перевіреного підсумку. Ось як працює Merkle Tree простими словами:

Крок 1: Почніть зі списку елементів, наприклад транзакцій, кожен з них є листком дерева.
Крок 2: Перетворіть кожен елемент на короткий відбиток за допомогою хеш функції.
Крок 3: Об’єднуйте сусідні відбитки попарно, зводьте кожну пару разом і знову хешуйте, щоб отримати їхній батьківський вузол.
Крок 4: Повторюйте попарування та хешування вгору по рівнях, поки не залишиться один верхній відбиток. Це і є корінь набору, Merkle root.
Крок 5: Щоб довести, що один елемент належить набору, потрібні лише цей елемент та короткий шлях із сусідніх відбитків. Швидко і компактно.

Ось і все: маленькі докази, велика впевненість.

Чому Merkle Tree має значення

Підсумовуючи великі масиви транзакційних даних в один компактний відбиток, Merkle Tree робить перевірку швидкою і недорогою.

Перевага: Ви можете перевірити належність без завантаження всього блоку, економлячи час і трафік.
Погляд: Це відповідає сучасному принципу: довіряй і перевіряй, від Rolex до Reddit ниток.
Актуальність: Ви зустрінете це в блоках Bitcoin, у квитанціях Ethereum, у списках дозволених для NFT, у ейрдропах і в rollups.

Порада

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

Ключові характеристики Merkle Tree

Ось що робить його особливим і корисним:

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

Варіанти

Merkle Tree має кілька популярних різновидів, з якими ви можете зіткнутися:

Бінарний: Класичне дерево на основі пар, використовується в блоках Bitcoin.
Merkle Patricia: Підхід на основі префіксного дерева для даних ключ значення, використовується в стані та квитанціях Ethereum.
Рідкісний: Велике індексоване дерево, де більшість листків порожні, підходить для компактних доказів належності і неналежності.
Verkle: Новіший родич з коротшими доказами для великих ступенів розгалуження, розглядається для майбутніх оновлень.

Нагадування

Докази Merkle Tree є достовірними лише стільки, скільки достовірним є заголовок або контрольна точка, які ви приймаєте. Якщо ви довіряєте неправильному кореню, навіть найчистіший доказ нічого не доводить.

Приклад

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

Цікавинка

Ральф Меркл запропонував цю ідею наприкінці сімдесятих як студентський проєкт, і вона довгий час залишалася в академічних колах, поки Сатоші не використав її в Bitcoin. Доказ того, що хороші ідеї довго служать.

Підсумок

Підсумок? Merkle Tree дає швидкі, компактні докази того, що щось належить до великого набору, без зайвого навантаження на завантаження.

Merkle Tree