Хеширование и коммитменты: магический запечатанный конверт

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

Как зафиксировать секрет публично и больше никогда не иметь возможности солгать о нём

Серия: Zcash from First Principles . Статья 3 . Хеширование и коммитменты Для кого: новички. Мы опираемся на Статью 1 (конечные поля) и Статью 2 (эллиптические кривые), но интуитивное понимание здесь самодостаточно. Что вы поймёте: чёткое понимание хеш-функций, того, что на самом деле означают "hiding" и "binding", и как Zcash строит коммитменты note, лежащие в основе каждого приватного платежа.

В Статье 0 мы описали «магический запечатанный конверт»: нечто, что можно прикрепить к публичной доске и тем самым доказать существование конверта, скрывая его содержимое, и что потом уже невозможно подменить. Мы пообещали объяснить, как такое вообще возможно. Именно этому и посвящена данная статья. Нам понадобятся два ингредиента: хеш-функции и коммитменты.

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

Представьте, что вы предсказываете исход выборов и хотите доказать постфактум, что сделали этот прогноз заранее. Вы не можете просто объявить свой прогноз (это влияет на людей или вызывает обвинения, будто вы его изменили). Но и держать его полностью в секрете нельзя (тогда вы позже ничего не сможете доказать).

Вам нужен способ сейчас публично зафиксировать значение так, чтобы:

• никто не мог понять, что именно вы зафиксировали (пока это остаётся секретом), и
• позже, когда вы его раскроете, вы не могли солгать о том, каким оно было.

Этот механизм «зафиксировать сейчас, раскрыть позже, без возможности солгать» называется коммитментом, и в Zcash он используется повсюду. Значение и владелец note фиксируются в коммитменте в момент создания note. Чтобы построить коммитменты, нам сначала нужен их главный рабочий инструмент: хеш-функция.

2. Интуиция: отпечаток данных

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

У хорошего криптографического отпечатка есть четыре свойства. Воспринимайте их интуитивно, а не как уравнения:

И есть ещё одно поведение, из-за которого такие отпечатки кажутся почти магическими:

Эффект лавины (проверено)

Измените входные данные хоть на малейшую величину — и отпечаток изменится полностью, без какого-либо сходства со старым. Вот два реальных отпечатка SHA-256 для сообщений, различающихся всего одним символом:

H("Pay Bob 5 ZEC") = 6e2dc1a954c70cc865f18ea8cb70b7b56eeaf6ca42b380824a55d65dc342f34b
H("Pay Bob 6 ZEC") = 76abc346d8d3053f76a9ae18b617af71f02729a73ec6a51732d2d94934e4217f

Из 64 шестнадцатеричных символов 59 различаются. Один символ на входе — и на выходе совершенно не связанный с ним отпечаток. Именно поэтому нельзя постепенно подталкивать вход к целевому отпечатку: здесь нет никакого сигнала «теплее / холоднее», за которым можно было бы следовать.

3. От отпечатка к коммитменту

Вот соблазнительная, но неверная идея: чтобы сделать коммитмент к секретному значению v, просто опубликовать его отпечаток H(v).

Это хорошо вас привязывает (вы не сможете позже заявить другое v, потому что для этого понадобилась бы коллизия). Но это не скрывает значение. Если множество возможных значений невелико, атакующий просто вычисляет отпечатки всех кандидатов и сравнивает. Делаете коммитмент к «да» или «нет»? Он хеширует оба варианта и мгновенно узнаёт, какой вы выбрали. Детерминированность, которая только что была нашим другом, теперь выдаёт секрет.

Исправление выражается одним словом: случайность.

Коммитмент — это отпечаток вашего значения, смешанный со свежим случайным числом: commitment = H(v, r) где r — секретное случайное значение «ослепления» (blinding).

Теперь одно и то же v каждый раз даёт по-разному выглядящий коммитмент, потому что r разное. Два свойства, которые нам были нужны, наконец выполняются одновременно:

Чтобы позже открыть (раскрыть) коммитмент, вы публикуете v и r; любой может заново вычислить H(v, r) и проверить, что оно совпадает. Вы зафиксировали значение. Это и есть тот самый магический запечатанный конверт из Статьи 0, воплощённый в реальность.

Два вывода, которые стоит запомнить навсегда: binding возникает благодаря стойкости хеша к коллизиям; hiding обеспечивается случайным фактором ослепления r.

4. Два способа построить конверт

Есть два распространённых рецепта, и Zcash использует оба.

Последняя строка показывает, почему коммитменты Pedersen так важны в Zcash. Поскольку commit(v_1) + commit(v_2) является корректным commit(v_1 + v_2), протокол может позже доказать, что входящие деньги равны исходящим, складывая коммитменты, и всё это без раскрытия ни одной суммы. Мы сохраним этот факт для Статьи 6.

5. Тонкость, которая формирует весь Zcash: ZK-friendly хеширование

Вот идея, которую большинство вводных материалов упускают, и это как раз тот момент, где стоит подчеркнуть встречу «математики и инженерии».

SHA-256 — превосходный отпечаток для повседневных вычислений. Но Zcash не просто вычисляет хеши; ему нужно доказывать внутри zero-knowledge proof, что хеш был вычислен корректно (Статья 5 объясняет почему). И тут есть проблема: zero-knowledge proof работает на языке арифметики конечных полей (Статья 1), тогда как SHA-256 построен из побитовых операций (сдвиги, AND, XOR). Выразить все эти побитовые действия через арифметику полей чрезвычайно дорого, из-за чего доказательства становятся огромными и медленными.

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

Именно это инженерное требование — «это должно быть дёшево доказывать» — объясняет, почему Zcash изобрёл и принял специальные хеш-функции вместо того, чтобы везде использовать SHA-256.

6. Где это живёт в Zcash

Zcash использовал разные хеши в разных версиях своей конструкции, и каждый выбирался под конкретную задачу:

Имена, которые стоит узнавать, — это Pedersen и Sinsemilla (хеши в стиле коммитментов, построенные из точек на кривой, поэтому они наследуют суперсилу «складываемости» и дёшево доказываются) и Poseidon (хеш на арифметике полей, специально созданный для zero-knowledge circuits). Когда в Статье 0 говорилось, что содержимое note запечатывается в коммитмент, именно этот механизм и выполняет запечатывание.

Так что открытый вопрос из Статьи 0 — «как запечатанный конверт может скрывать своё содержимое и при этом быть невозможным для подделки?» — теперь закрыт: сокрытие обеспечивается случайным фактором ослепления, а связывание — стойкостью к коллизиям или ловушкой эллиптической кривой.

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

Мы упростили изложение ради ясности. Реальные схемы коммитментов точно задают, как кодируются v и r и какие генераторы используются; у свойств "hiding" и "binding" есть разные варианты (совершенное и вычислительное) с точными определениями безопасности; и мы не показали внутреннее устройство Pedersen, Sinsemilla или Poseidon. Ничто из этого не меняет интуицию: коммитмент — это отпечаток плюс случайность, который сейчас скрывает, а навсегда связывает. Детали вернутся — с явными пометками — когда они понадобятся в статье о протоколе.

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

• Хеш-функция — это отпечаток для данных: детерминированный, быстрый в прямом направлении, односторонний, стойкий к коллизиям, с эффектом лавины (один бит на входе — и совершенно другой отпечаток на выходе).
• Коммитмент позволяет сейчас публично зафиксировать значение и позже раскрыть его, не имея возможности солгать.
• Публикация голого отпечатка H(v) связывает, но не скрывает. Добавление случайного фактора ослепления, H(v, r), это исправляет: hiding за счёт r, binding за счёт стойкости к коллизиям.
• Zcash использует как коммитменты на основе хеша, так и коммитменты Pedersen; коммитменты Pedersen дополнительно складываются, и Статья 6 использует это свойство для приватного доказательства баланса значений.
• Поскольку хеши должны быть доказуемы внутри zero-knowledge proof, Zcash использует ZK-friendly хеши, построенные на арифметике полей (Pedersen, Sinsemilla, Poseidon), а не SHA-256 повсюду.

Глоссарий

FAQ

Почему бы просто не зашифровать значение вместо того, чтобы делать к нему коммитмент? Шифрование — это про секретность, которую потом можно расшифровать. Коммитмент — это про binding: гарантию того, что позже вы не сможете изменить свой ответ. Это разные задачи.

Если коммитменты скрывают значение, как тогда вообще кто-то проверяет соблюдение правил? Для этого и нужны zero-knowledge proofs (Статья 5): они доказывают, что скрытое значение подчиняется правилам, не раскрывая его.

Раз Zcash местами избегает SHA-256, значит ли это, что SHA-256 сломан? Нет. С SHA-256 всё в порядке, и Zcash по-прежнему его использует. Просто его дорого доказывать внутри схемы, поэтому для этой конкретной задачи и существуют ZK-friendly хеши.

Откуда берётся случайное r и кто его хранит? Оно генерируется заново при создании note и известно владельцу note. Это часть того, что делает каждую note уникальной и приватной.

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

Вы делаете коммитмент к своему прогнозу на выборы как H(v, r) и публикуете его. Друг настаивает, что для простоты вам стоит публиковать просто H(v). В одном предложении: почему это плохая идея, если возможны только два исхода? (Ответ ниже.)

Что дальше

Статья 4 . Деревья Merkle: теперь у нас накапливаются миллионы коммитментов. Статья 4 показывает, как Zcash организует их в единое дерево, чей маленький корневой отпечаток представляет всю историю целиком, и как можно доказать, что ваша note находится в этом дереве, не раскрывая какая именно. Это и есть настоящая форма «публичной доски» из Статьи 0.

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