Дерева Меркла: Як один хеш перевіряє мільйони записів

Один хеш для верифікації всього

Дерево Меркла, назване на честь Ральфа Меркле його патенту 1979 року, є бінарним деревом, де кожен лист містить криптографічний хеш блоку даних, а кожний внутрішній вузол містить хеш конкатенації хешів двох своїх дочірніх вузлів. Результатом є один хеш кореня, який підсумовує кожен байт кожного блоку нижче нього — зміна одного біта будь-де в даних призводить до зміни листявого хешу, що змінює його батьківський вузол, що змінює його батьківський вузол, усіма шляхом до зовсім іншого кореня. Це дозволяє системам, такими як Git, BitTorrent, ZFS, Certificate Transparency та кожному великому блокчейну перевіряти величезні набори даних за допомогою одного невеликого, фіксованого розміру відбитків пальців.

leaf0..leaf3 = H(block0)..H(block3)
node10 = H(leaf0 || leaf1)      node11 = H(leaf2 || leaf3)
root   = H(node10 || node11)
// flip one bit in block2 -> leaf2 changes -> node11 changes -> root changes

Перевірка членства без усього набору даних

Властивість, яка робить дерева Меркла корисними в практиці, а не лише елегантними, це доказ Меркла (також відомий як аудитний шлях або доказ включення): щоб довести, що певний блок є частиною дерева з відомим коренем, потрібно надати лише цей блок та хеш брата на кожному рівні шляхом до кореня — O(log n) хешів для n листків, замість усього набору даних. Перевіряючий перераховує шлях від блоку вгору і перевіряє, чи він збігається з відомим коренем.

// довести, що leaf2 знаходиться під `root`, враховуючи братів [leaf3, node10] h = H(leaf2) h = H(h || leaf3) // об'єднання з братом на рівні 1 (leaf2 - лівий потомок) h = H(node10 || h) // об'єднання з братом на рівні 2 (це піддерево - правий потомок) assert(h === root) // O(log n) хешів доводять членство в множині з n елементів Для дерева по мільйон листків це приблизно 20 обчислень хешів для доведення членства — перевірка займає мікросекунди навіть на телефоні, що є точною властивістю, на яку покладаються легкі клієнти Bitcoin (SPV): легкий клієнт може підтвердити, що транзакція включена в блок, перевіряючи ~20-хеш доказ Меркла проти заголовка блоку, без завантаження або зберігання повного блоку.

// prove leaf2 is under `root`, given siblings [leaf3, node10]
h = H(leaf2)
h = H(h || leaf3)     // combine with sibling at level 1 (leaf2 is left child)
h = H(node10 || h)    // combine with sibling at level 2 (this subtree is right child)
assert(h === root)    // O(log n) hashes prove membership in a set of n items

Чому блокчейни використовують їх

Кожен блок у Bitcoin та Ethereum зберігає Merkle корінь усіх своїх транзакцій в заголовку, а не самі транзакції всередині хешованого заголовка. Це відознє розмір того, що потрібно хешувати для консенсусу (фіксований невеликий заголовок) від кількості транзакцій у блоці, і це означає, що будь-яке маніпулювання з будь-якою транзакцією, хоч наскільки глибоко в дереві, можна виявити лише по заголовку. Ethereum йде ще далі з Merkle Patricia trie — Merkle дерево об'єднане з radix trie — щоб зробити всю базу даних облікових записів/стану самою перевіряємоюся та ефективно оновлювати одну ключову за раз, а не потребуючи перехешування статичного списку.

Універсальність стійкості до зіткнень є всією моделлю безпеки

Кожна гарантія тут ґрунтується на тому, що основна функція хешування стійка до зіткнень: обчислювально неможливо знайти два різних вхідні дані, які хешуються в один і той же вихід. Якщо нападник зможе знайти зіткнення H(x) = H(y) для x ≠ y, він може замінити дані листка без зміни кореня, мовчки підробивши Merkle-підтвердження. Саме тому дерева Меркла відійшли від MD5 і SHA-1, коли було продемонстровано практичні зіткнення проти них, а сучасні реалізації використовують SHA-256 або Keccak/SHA-3.

Більш тонкий напад, другий напад на попередження про зображення, проти простих дерев Меркла, використовує той факт, що хеш внутрішнього вузла та хеш листка можуть мати структурно ідентичні характеристики, якщо ви не розрізняєте їх — нападник може іноді представити внутрішній вузол як листок і створити здавалося б дійсне підтвердження для даних, які насправді не були листом. Стандартною оборонною мірою, яка використовується в BIP Біткоїна та RFC про Прозорість сертифікатів, є розділення доменів: префіксуйте хеші листя окремим байтом (наприклад 0x00) і хеші внутрішніх вузлів іншим (0x01), щоб хеш листка ніколи не міг бути помилково сприйнятий як хеш внутрішнього вузла або замінений ним.

Будівництво одного ефективно

Будівництво дерева знизу вгору з n листів потребує загалом O(n) хеш-операцій (n листів стають n/2 внутрішніми вузлами, потім n/4 і так далі – геометрична серія, що дорівнює трохи менше 2n). Для непарної кількості листів на певному рівні стандартною практикою є дублювання останнього хешу замість того, щоб залишати його без пари, хоча деякі реалізації замість цього безпосередньо просувають його – важливим є те, що незалежно від обраного стандарту, він повинен бути застосований послідовно як будівельником дерева, так і всіма перевірювачами, інакше докази, згенеровані одним, не зможуть підтвердитися проти іншого.

Часті запитання

Спробуйте наживо

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