Дерево Меркла — бінарне дерево, у якому кожен листок — фрагмент даних, кожен внутрішній вузол — криптографічний хеш двох дочірніх, а один кореневий хеш фіксує вміст усього дерева. Це одна з базових структур даних Bitcoin і основа підтвердження резервів. Названа на честь Ральфа Меркла, який запатентував її у 1979 році. У Bitcoin використовується з генезис-блоку 2009 року.
Що дає ця структура
Для криптовалют важливі дві властивості:
Компактна фіксація. Один 32-байтовий кореневий хеш представляє будь-який обсяг даних. Дерево Меркла з мільйона транзакцій усе одно дає один 32-байтовий корінь.
Ефективний доказ належності. Щоб довести, що конкретна транзакція є в дереві, потрібен лише шлях від листка до кореня — для дерев із мільйонами листків це зазвичай 20–32 хеші. Той, хто перевіряє, хешує свої дані разом із наданим шляхом; якщо обчислений корінь збігається з опублікованим, належність доведено.
Де дерева Меркла трапляються у вашому плані зберігання
Три конкретні приклади:
Підтвердження резервів на біржах. Частина великих бірж публікує PoR на основі дерева Меркла. Баланс кожного користувача — листок дерева, а опублікований корінь фіксує загальну суму. Кожен може сам перевірити, що його баланс враховано, пройшовши шлях від свого листка до опублікованого кореня.
Будова блоку Bitcoin. Кожен блок містить корінь дерева Меркла всіх своїх транзакцій. Легкі клієнти (SPV, simple payment verification) так доводять, що транзакція є в підтвердженому блоці, не завантажуючи весь блок.
Розподіл ейрдропів. Багато ейрдропів публікують список тих, хто має право на отримання, у вигляді дерева Меркла. Кожна адреса з сумою — листок, а корінь записується в смартконтракт ейрдропу. Щоб отримати токени, користувач подає шлях у дереві, доводячи, що його адреса там є.
Як перевірити свій баланс у PoR біржі
Якщо біржа має такий інструмент, порядок зазвичай такий:
- Увійдіть в акаунт і знайдіть розділ підтвердження резервів.
- Сторінка покаже ID вашого акаунта, хеш вашого листка й шлях із сусідніх хешів від листка до кореня.
- Порівняйте показаний кореневий хеш із тим, що опубліковано на публічній сторінці PoR.
- Якщо збігаються, ваш баланс перевірено враховано в опублікованій загальній сумі.
Математика така: хеш вашого листка разом із першим сусіднім хешем дає хеш наступного рівня. Той разом із наступним сусіднім — рівень вище. І так до верхівки дерева, де результат має збігтися з опублікованим коренем.
Чого корінь дерева Меркла не доводить
Дерево Меркла фіксує дані на момент побудови. Воно не доводить, що дані правильні (біржа могла внести неправильні баланси), не доводить, що відповідні активи справді існують (для цього потрібні окремі підтвердження зобов'язань і резервів), і не доводить, що в дереві є всі акаунти (біржа могла деякі просто пропустити).
Тому надійне PoR поєднує дерево Меркла для зобов'язань з окремим криптографічним підтвердженням адрес резервів і незалежним аудитом. Дерево Меркла необхідне, але його недостатньо.
Що почитати далі: Підтвердження резервів, CEX.