Дерева Меркла: як блокчейн пам’ятає кожну ноту

Оригінальне дослідження від Annkkitaaa

Підсумовування мільйонів commitment’ів в одному крихітному відбитку

Серія: Zcash from First Principles . Стаття 4 . Дерева Меркла Аудиторія: новачки. Ми спираємося на Статтю 3 (хешування та commitments). Якщо ви знаєте, що таке відбиток і commitment, ви готові. Що ви зрозумієте після прочитання: інтуїтивно зрозумілу й коректну картину дерев Меркла, як доводити належність без розкриття того, який саме елемент ви маєте на увазі, і як саме це стає деревом commitments нот у Zcash.

Стаття 0 описала «публічну дошку», що містить кожну ноту, коли-небудь створену, і лише постійно зростає. Тепер ви вже можете здогадатися, що саме на неї прикріплюється: commitments (Стаття 3), запечатані конверти. Але справжня дошка містила б сотні мільйонів таких записів. Як мережа це зберігає, перевіряє й дозволяє вам довести, що ваш конверт є на дошці, не вказуючи на нього? Відповідь — одна з найелегантніших структур у комп’ютерних науках: дерево Меркла.

1. Чому це має вас цікавити?

Щойно у вас з’являється гігантський публічний список commitments, виникають дві проблеми.

Проблема перша: цілісність у великому масштабі. Якщо список має 300 мільйонів записів, як хтось може підтвердити, що жоден із них не був таємно змінений? Повторно перевіряти 300 мільйонів елементів щоразу — безнадійно.

Проблема друга: приватне доведення належності. Щоб витратити ноту (Стаття 0), ви маєте довести, що ваш commitment справді є на дошці. Але якщо ви вкажете на нього («це запис номер 4,201,337!»), ви щойно деанонімізували себе. Вам потрібно довести: «мій конверт десь на цій дошці», не розкриваючи який саме.

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

2. Інтуїція: турнір відбитків

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

• Унизу кожен фрагмент даних має свій власний відбиток (його хеш зі Статті 3). Це листки.
• З’єднайте їх у пари. Два відбитки кожної пари хешуються разом в один батьківський відбиток.
• З’єднайте батьківські вузли в пари, хешуйте кожну пару разом і так далі.
• Продовжуйте, доки на вершині не залишиться один-єдиний відбиток. Цей чемпіон і є коренем Меркла.

Найважливіша властивість прямо випливає з avalanche effect (Стаття 3):

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

3. Справжнє дерево, обчислене точно

Побудуймо дерево з чотирма листками, показане вище, з реальними відбитками SHA-256 для листків A, B, C, D (дайджести скорочено для зручності читання):

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

Усе зводиться до «хешуй річ, а потім хешуй пари хешів». Нічого екзотичнішого за Статтю 3, просто організованого у вигляді дерева.

4. Хитра частина: доведення належності без розкриття позиції

Тепер Проблема друга. Скажімо, ви хочете довести, що листок C є в дереві, комусь, хто знає лише корінь. Ви не передаєте йому все дерево. Ви передаєте лише відбитки, потрібні, щоб піднятися від C до кореня; це називається шлях автентифікації (або доказ Меркла):

Щоб довести, що C є в дереві, надайте:

• його сусідній елемент hD, і
• його «дядька» hAB.

Верифікатор, знаючи лише корінь, повторно обчислює підйом:

step 1:  H(hC , hD)        = hCD       (поєднати C з його сусіднім елементом)
step 2:  H(hAB , hCD)      = ROOT?     (поєднати з «дядьком»)

Якщо обчислити це насправді, отримаємо 1b3faa3fcc5e..., що збігається з коренем. Доведено, що листок належить дереву.

Дві речі роблять це потужним:

• Він крихітний. Для 4 листків ви надали 2 хеші. Для дерева з n листків ви надаєте лише приблизно log_2(n) хешів. Для мільярда листків це приблизно 30 хешів, а не мільярд. Доказ майже не збільшується, навіть коли дерево вибухово зростає в розмірі.
• Це зерно приватності. Доказ показує, що ваш листок є десь у дереві. Коли цю саму перевірку виконують усередині доказу з нульовим розголошенням (Стаття 5), приховується навіть сам шлях, тож ви доводите «моя нота є в дереві», не розкриваючи ні саму ноту, ні її позицію. Це повністю розв’язує Проблему другу.

5. Від дерева Меркла до дерева commitments нот у Zcash

Тепер ми можемо точно сформулювати, чим насправді є «публічна дошка» зі Статті 0:

Дерево commitments нот — це дерево Меркла, чиїми листками є commitments нот. Щоразу, коли десь у світі створюється нота, її commitment додається як наступний листок, а корінь оновлюється.

Кілька реальних подробиць:

• Воно лише зростає. Листки додаються, але ніколи не видаляються. Це називається інкрементальним деревом Меркла. (Це відповідає фразі зі Статті 0: «дошка ніколи нічого не зриває».)
• Корінь називається anchor. Коли ви витрачаєте ноту, ваша транзакція посилається на нещодавній anchor і доводить, із нульовим розголошенням, що commitment вашої ноти міститься в дереві з цим коренем.
• Фіксована глибина. Shielded-дерева Zcash мають глибину 32, тобто можуть вмістити до 2^(32) (понад чотири мільярди) нот.
• Хешування, дружнє до ZK. Дерево не будується за допомогою SHA-256. Sapling хешує дерево за допомогою Pedersen hashes, а Orchard використовує Sinsemilla (обидва зі Статті 3), саме для того, щоб підйом перевірки належності було дешево доводити всередині схеми.

Одна річ, з якою дерево не працює: подвійні витрати

Дерево доводить, що нота існує. Але саме по собі воно не заважає вам витратити ту саму ноту двічі. Цю роботу виконує множина nullifier зі Статті 0: окрема колекція «токенів погашення». Коли ви витрачаєте ноту, ви публікуєте її nullifier, а мережа відхиляє будь-який nullifier, який уже бачила раніше.

Отже, ці дві публічні структури виконують взаємодоповнювальні ролі, і саме їхнє розділення розриває зв’язок між народженням ноти та її смертю:

6. Чесне застереження

Спрощення, як завжди. Реальні інкрементальні дерева Меркла відстежують вузли «frontier», щоб корінь можна було оновлювати без повної перебудови; мережа зберігає вікно нещодавніх anchor, а не лише найновіший, щоб кожен новий блок не ламав гаманці; а порожні листки використовують визначене padding-значення. Ми також малювали бінарні дерева з акуратними степенями двійки. Ніщо з цього не змінює інтуїцію: листки з commitments, які попарно хешуються аж до одного кореня, з короткими доказами належності. До точного бухгалтерського обліку ми повернемося в статті про протокол.

7. Підсумок

• Дерево Меркла хешує дані в листки, а потім хешує пари догори, доки не залишиться один-єдиний корінь.
• Завдяки avalanche effect, корінь є відбитком усього списку: змініть один листок — і корінь зміниться. Одне невелике значення засвідчує величезний набір даних.
• Доказ належності (шлях автентифікації) — це просто сусідні хеші вздовж підйому до кореня, приблизно log_2(n) хешів, тож докази залишаються маленькими навіть для мільярдів листків.
• Якщо це виконується всередині доказу з нульовим розголошенням, така перевірка належності приховує, який саме листок ви маєте на увазі, доводячи «моя нота є в дереві» без розкриття ні ноти, ні її позиції.
• Дерево commitments нот у Zcash — це інкрементальне дерево Меркла з commitments нот, глибиною 32, чий корінь називається anchor; Sapling хешує його за допомогою Pedersen, а Orchard — за допомогою Sinsemilla.
• Дерево доводить існування; окрема множина nullifier запобігає подвійним витратам. Саме їхнє розділення розриває зв’язок між народженням ноти та її смертю.

Глосарій

FAQ

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

Чи потрібне верифікатору все дерево? Ні. Верифікатору потрібен лише корінь плюс ваш короткий шлях автентифікації. У цьому й полягає вся суть.

Чому саме глибина 32? Вона обмежує дерево приблизно чотирма мільярдами нот, що дає великий запас, і водночас зберігає доказ належності (і його вартість усередині схеми) фіксованого й керованого розміру.

Якщо корінь змінюється з кожною новою нотою, як старі докази залишаються чинними? Мережа пам’ятає вікно нещодавніх коренів (anchor), тож доказ, створений щодо трохи старішого anchor, усе ще перевіряється. Стаття про протокол формулює це точно.

Перевірте свою інтуїцію

У нашому дереві з 4 листками припустімо, що зловмисник таємно замінює листок C на інше значення, але залишає опублікований корінь незмінним. Що для нього піде не так і чому він не може непомітно це виправити? (Відповідь нижче.)

Що далі

Стаття 5 . Докази з нульовим розголошенням: кульмінація. Ми вже побудували ноти, commitments і дерево, і весь час повторюємо «доведено з нульовим розголошенням». У Статті 5 нарешті пояснюється, як можна довести, що твердження істинне, що ваша нота є в дереві, що ваш nullifier правильний, що баланс коштів зберігається, — не розкриваючи нічого з цього.

Частина серії Zcash from First Principles для ZecHub. Ліцензія CC BY-SA 4.0.