Деревья Меркла: как блокчейн помнит каждую note

Оригинальное исследование от Annkkitaaa

Как свести миллионы commitments к одному крошечному отпечатку

Серия: Zcash from First Principles . Статья 4 . Деревья Меркла Для кого: новички. Мы опираемся на Статью 3 (хеширование и commitments). Если вы понимаете, что такое отпечаток и commitment, вы готовы. Что вы получите: интуитивно понятное и корректное представление о деревьях Меркла, о том, как доказать принадлежность, не раскрывая, какой именно элемент вы имеете в виду, и как именно это становится деревом note commitments в Zcash.

Статья 0 описывала «публичную доску», на которой хранится каждая когда-либо созданная note и которая только растёт. Теперь вы, вероятно, уже догадываетесь, что на неё прикрепляется: commitments (Статья 3), запечатанные конверты. Но настоящая доска содержала бы сотни миллионов таких элементов. Как сеть это хранит, проверяет и позволяет вам доказать, что ваш конверт есть на доске, не указывая на него? Ответом служит одна из самых элегантных структур в информатике: дерево Меркла.

1. Почему это должно вас волновать?

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

Проблема первая: целостность в большом масштабе. Если в списке 300 миллионов записей, как кому-либо убедиться, что ни одна из них не была тайно изменена? Проверять заново 300 миллионов элементов при каждом взгляде — безнадёжная затея.

Проблема вторая: приватное доказательство принадлежности. Чтобы потратить note (Статья 0), вы должны доказать, что ваш commitment действительно находится на доске. Но если вы укажете на него («это запись номер 4,201,337!»), вы тут же деанонимизируете себя. Вам нужно доказать: «мой конверт находится где-то на этой доске» — не раскрывая, какой именно.

Дерево Меркла решает обе задачи сразу. Оно сжимает весь список в один-единственный отпечаток и позволяет доказать принадлежность с помощью маленького доказательства, скрывающего позицию.

2. Интуиция: турнир отпечатков

Представьте сетку турнира на выбывание, только вместо игроков дальше проходят отпечатки.

• Внизу каждый фрагмент данных получает собственный отпечаток (свой хеш из Статьи 3). Это листья.
• Объедините их по парам. Два отпечатка в каждой паре хешируются вместе и образуют один родительский отпечаток.
• Затем объедините по парам уже родителей, снова захешируйте каждую пару, и так далее.
• Продолжайте, пока наверху не останется один отпечаток. Этот чемпион и есть корень Меркла.

Самое важное свойство напрямую вытекает из лавинного эффекта (Статья 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), скрывается даже сам путь, и вы доказываете: «моя note находится в дереве», не раскрывая ни саму note, ни её позицию. Это полностью решает вторую проблему.

5. От дерева Меркла к дереву note commitments в Zcash

Теперь мы можем точно сформулировать, чем на самом деле является «публичная доска» из Статьи 0:

Дерево note commitments — это дерево Меркла, у которого листьями являются note commitments. Каждый раз, когда где-либо в мире создаётся note, её commitment добавляется как следующий лист, а корень обновляется.

Несколько конкретных деталей:

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

Одна вещь, которую дерево не решает: двойные траты

Дерево доказывает, что note существует. Но само по себе оно не мешает вам потратить одну и ту же note дважды. За это отвечает множество nullifier из Статьи 0: отдельная коллекция «токенов аннулирования». Когда вы тратите note, вы публикуете её nullifier, и сеть отклоняет любой nullifier, который уже встречала раньше.

Таким образом, эти две публичные структуры выполняют взаимодополняющие роли, и именно их раздельность разрывает связь между рождением note и её смертью:

6. Честная оговорка

Как обычно, здесь есть упрощения. Настоящие инкрементальные деревья Меркла отслеживают «пограничные» узлы, чтобы обновлять корень без полной перестройки; сеть хранит окно недавних anchor, а не только самый последний, чтобы новые блоки не ломали кошельки; а пустые листья используют заранее определённое значение-заполнитель. Мы также рисовали аккуратные бинарные деревья с красивыми степенями двойки. Ничто из этого не меняет интуицию: листья из commitments, попарно хешируемые до одного корня, и короткие доказательства принадлежности. К точной бухгалтерии мы вернёмся в статье о протоколе.

7. Краткое резюме

• Дерево Меркла хеширует данные в листья, а затем хеширует пары вверх по дереву, пока не останется один корень.
• Благодаря лавинному эффекту, корень является отпечатком всего списка: измените один лист — и корень изменится. Одно маленькое значение удостоверяет огромный набор данных.
• Доказательство принадлежности (путь аутентификации) — это просто соседние хеши на пути подъёма к корню, около log_2(n) хешей, поэтому доказательства остаются маленькими даже для миллиардов листьев.
• Если такая проверка выполняется внутри доказательства с нулевым разглашением, она скрывает, какой именно лист вы имеете в виду, позволяя доказать: «моя note находится в дереве», не раскрывая ни саму note, ни её позицию.
• Дерево note commitments в Zcash — это инкрементальное дерево Меркла из note commitments глубиной 32, корень которого называется anchor; в Sapling для него используются Pedersen, а в Orchard — Sinsemilla.
• Дерево доказывает существование; отдельное множество nullifier предотвращает двойные траты. Именно их раздельность и разрывает связь между рождением note и её смертью.

Глоссарий

FAQ

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

Нуждается ли проверяющий во всём дереве? Нет. Проверяющему нужен только корень плюс ваш короткий путь аутентификации. В этом и состоит вся идея.

Почему именно глубина 32? Она ограничивает дерево примерно четырьмя миллиардами notes, что даёт большой запас, при этом сохраняя доказательство принадлежности (и его стоимость внутри схемы) фиксированного и управляемого размера.

Если корень меняется с каждой новой note, как старые доказательства остаются действительными? Сеть хранит окно недавних корней (anchor), поэтому доказательство, сделанное относительно немного более старого anchor, всё ещё проверяется. В статье о протоколе это будет сформулировано точно.

Проверьте свою интуицию

В нашем дереве с 4 листьями предположим, что злоумышленник тайно заменяет лист C на другое значение, но оставляет опубликованный корень неизменным. Что у него пойдёт не так и почему он не может незаметно это исправить? (Ответ ниже.)

Что дальше

Статья 5 . Доказательства с нулевым разглашением: кульминация. Теперь у нас есть notes, commitments и дерево, и мы постоянно говорим: «доказано с нулевым разглашением». Статья 5 наконец объяснит, как можно доказать истинность утверждения — что ваша note находится в дереве, что ваш nullifier корректен, что баланс денег сходится, — не раскрывая ничего из этого.

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