Хешування і комітменти: магічний запечатаний конверт

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

Як публічно замкнути секрет і ніколи не мати змоги збрехати про нього

Серія: Zcash from First Principles . Стаття 3 . Хешування і комітменти Аудиторія: новачки. Ми спираємося на Статтю 1 (скінченні поля) і Статтю 2 (еліптичні криві), але інтуїція тут є самодостатньою. Що ви зрозумієте після прочитання: чітке розуміння хеш-функцій, того, що насправді означають "приховування" і "зв’язування", і того, як Zcash будує комітменти нот, на яких ґрунтується кожен приватний платіж.

У Статті 0 ми описали "магічний запечатаний конверт": щось, що можна прикріпити до публічної дошки як доказ існування конверта, водночас приховуючи його вміст, і що ніколи не можна буде потім підмінити. Ми пообіцяли пояснити, як таке взагалі можливе. Ось ця стаття. Нам потрібні два інгредієнти: хеш-функції і комітменти.

1. Чому це має вас хвилювати?

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

Вам потрібен спосіб зафіксувати значення зараз, публічно, так, щоб:

• ніхто не міг визначити, що саме ви зафіксували (воно поки що лишається таємницею), і
• пізніше, коли ви це розкриєте, ви не могли збрехати про те, яким воно було.

Цей механізм "зафіксувати зараз, розкрити пізніше, без можливості збрехати" називається комітментом, і він зустрічається в Zcash всюди. Значення ноти та її власник зафіксовані в комітменті в ту саму мить, коли ноту створено. Щоб побудувати комітменти, нам спершу потрібен їхній робочий інструмент: хеш-функція.

2. Інтуїція: відбиток пальця для даних

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

Хороший криптографічний відбиток має чотири властивості. Тримайте їх у голові як інтуїції, а не як рівняння:

І ще одна поведінка, через яку ці відбитки здаються майже магічними:

Ефект лавини (перевірено)

Змініть вхідні дані на найменшу дрібницю — і відбиток зміниться повністю, без жодної схожості зі старим. Ось два справжні відбитки 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 — це секретне випадкове значення "засліплення".

Тепер те саме v щоразу породжує комітмент з іншим виглядом, бо r щоразу інше. Дві властивості, які ми хотіли, нарешті одночасно виконуються:

Щоб відкрити (розкрити) комітмент пізніше, ви публікуєте v і r; будь-хто повторно обчислює H(v, r) і перевіряє, що воно збігається. Ви зафіксувалися. Ось і магічний запечатаний конверт зі Статті 0, втілений у реальність.

Два висновки, які варто запам’ятати назавжди: зв’язування походить від стійкості хешу до колізій; приховування походить від випадкового фактора засліплення r.

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

Є два поширені рецепти, і Zcash використовує обидва.

Саме останній рядок пояснює, чому комітменти Pedersen такі важливі в Zcash. Оскільки commit(v_1) + commit(v_2) є коректним commit(v_1 + v_2), протокол згодом може довести, що вхідні кошти дорівнюють вихідним, просто додаючи комітменти, і все це без розкриття жодної суми. Ми збережемо цей факт до Статті 6.

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

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

SHA-256 — чудовий відбиток для повсякденних обчислень. Але Zcash не просто обчислює хеші; він має доводити, всередині доказу з нульовим розголошенням, що хеш був обчислений правильно (Стаття 5 пояснює, чому). І тут є нюанс: доказ із нульовим розголошенням працює мовою арифметики скінченних полів (Стаття 1), тоді як SHA-256 побудований із бітових операцій (зсувів, AND, XOR). Виразити всі ці бітові операції через арифметику полів надзвичайно дорого, через що докази стають великими й повільними.

Тому криптографи Zcash розробили хеш-функції, внутрішня будова яких уже є арифметикою полів, що робить їх дешевими для доведення:

Саме цей інженерний тиск, "це має бути дешево для доведення," і є причиною того, чому Zcash винайшов і впровадив спеціальні хеш-функції замість того, щоб усюди просто брати SHA-256.

6. Де це живе в Zcash

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

Імена, які варто впізнавати, — це Pedersen і Sinsemilla (хеші у стилі комітментів, побудовані з точок кривої, тож вони успадковують суперсилу "складання" і дешево доводяться) та Poseidon (хеш на арифметиці полів, спеціально створений для схем з нульовим розголошенням). Коли у Статті 0 йшлося, що вміст ноти запечатано в комітменті, саме це і є механізмом запечатування.

Тож відкрите питання зі Статті 0, "як запечатаний конверт може приховувати свій вміст і водночас бути неможливим для підробки?", тепер закрите: приховування завдяки випадковому фактору засліплення, зв’язування завдяки стійкості до колізій або пастці кривої.

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

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

8. Підсумок

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

Глосарій

FAQ

Чому б просто не зашифрувати значення замість того, щоб робити комітмент? Шифрування — це про таємність, яку потім можна розшифрувати. Комітмент — це про зв’язування: гарантію того, що ви не зможете змінити свою відповідь пізніше. Це різні задачі.

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

SHA-256 зламаний, якщо Zcash у деяких місцях його уникає? Ні. SHA-256 цілком надійний, і Zcash досі його використовує. Просто його дорого доводити всередині схеми, саме тому для цієї конкретної задачі існують ZK-friendly хеші.

Звідки береться випадкове r, і хто його зберігає? Воно генерується заново під час створення ноти і відоме власнику ноти. Це частина того, що робить кожну ноту унікальною та приватною.

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

Ви робите комітмент до свого прогнозу виборів як H(v, r) і публікуєте його. Друг наполягає, що для простоти слід публікувати просто H(v). В одному реченні: чому це погана ідея, якщо можливі лише два результати? (Відповідь нижче.)

Що далі

Стаття 4 . Дерева Merkle: тепер у нас накопичуються мільйони комітментів. Стаття 4 показує, як Zcash організовує їх в одне дерево, чий крихітний кореневий відбиток представляє всю історію, і як можна довести, що ваша нота є в цьому дереві, не розкриваючи, яка саме. Ось справжня форма "публічної дошки" зі Статті 0.

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