Схемы обязательств и проверяемая случайность

Как «запечатать» решение заранее и как получить случайность, которой можно доверять.

Схема обязательств (commitment scheme) — протокол, который позволяет зафиксировать значение, не раскрывая его, а позже доказать, что раскрытое значение — именно то, что было зафиксировано, без возможности подмены.

Зачем это знать

Во многих протоколах важно «сходить первым, но не раскрыться»: сделать ставку, не показав её соперникам; зафиксировать прогноз, чтобы потом нельзя было сказать «я так и думал»; внести вклад в случайность, который никто не успеет подкрутить. Без криптографии тут легко смошенничать. Схемы обязательств и проверяемая случайность дают честность по построению — и это базовые кирпичи, на которых стоят ZKP, аукционы и блокчейн-протоколы.

Аналогия: запертый ящик

Обязательство — как непрозрачный ящик с замком. Вы кладёте записку (значение), запираете и отдаёте ящик собеседнику. Он видит, что вы уже определились, но прочитать не может (hiding — скрытность). Позже вы отдаёте ключ; собеседник открывает и читает записку. Подменить её вы не можете — ящик был у него (binding — связывание). Два свойства обязательны и в паре:

• Hiding: по обязательству нельзя узнать спрятанное значение.
• Binding: после фиксации нельзя «раскрыть» обязательство как другое значение.

Как это работает под капотом

Простейшая схема — на криптографической хеш-функции. Чтобы зафиксировать значение m, берут случайную «соль» r (nonce) и публикуют commit = Hash(m || r). Чтобы раскрыть — показывают m и r; проверяющий пересчитывает хеш и сверяет.

Фиксация:  выбрать случайный r;  commit = Hash(m || r)   → опубликовать commit
Раскрытие: показать (m, r)
Проверка:  Hash(m || r) == commit ?

binding ← стойкость хеша к коллизиям (нельзя найти другие m', r' с тем же хешем)
hiding  ← случайный r (без него короткое m можно подобрать перебором)

Соль r критична: без неё, если m из небольшого набора (скажем, «орёл»/«решка» или ставка из круглых сумм), противник просто перехеширует все варианты и узнает значение. Случайный r делает перебор бессмысленным.

Почему два свойства тянут в разные стороны и почему хеш-схема их балансирует? Binding опирается на стойкость хеша к коллизиям: чтобы «переоткрыть» обязательство как другое значение, нужно найти пару (m', r') с тем же хешем, а для криптостойкой функции это вычислительно невозможно. Hiding опирается на случайность соли и на то, что хеш не «протекает» сведениями о входе. Бывают схемы с разной строгостью этих гарантий — например, perfectly hiding (значение скрыто абсолютно, даже для противника с неограниченной мощью, но binding лишь вычислительный) и наоборот; в учебной хеш-схеме оба свойства вычислительные, и для большинства протоколов этого достаточно.

Классический сценарий: честный «подбрось монету» по сети

Двое играют в орлянку, не доверяя друг другу и не находясь рядом.

• Алиса загадывает бит a, фиксирует commit = Hash(a || r) и отправляет только commit.
• Боб, не зная a, открыто называет свой бит b.
• Алиса раскрывает a и r; результат — a XOR b.

Ни одна сторона не может подыграть: Алиса зафиксировала a до ответа Боба (binding), а Боб выбирал, не зная a (hiding). Это honest coin flip — кирпич многих протоколов.

Проверяемая случайность (VRF)

Проверяемая случайная функция (verifiable random function, VRF) — функция, которая по входу и приватному ключу выдаёт псевдослучайный результат вместе с доказательством; любой с публичным ключом может проверить, что результат вычислен честно, но не может предсказать его заранее.

Чем VRF отличается от обычного хеша или генератора? Результат хеша всякий может пересчитать — он не «принадлежит» владельцу ключа. Результат обычного ГПСЧ нельзя публично проверить. VRF совмещает три свойства:

• Псевдослучайность: без приватного ключа выход неотличим от случайного и непредсказуем.
• Проверяемость: по публичному ключу, входу и доказательству любой убедится, что выход подлинный.
• Уникальность: для данного входа и ключа выход ровно один — владелец не может «выбрать» удобный результат из нескольких.

(output, proof) = VRF_prove(secret_key, input)
VRF_verify(public_key, input, output, proof) → true / false

Свойства: непредсказуемо без ключа · проверяемо публично · единственный output на (key, input)

Где это применяется

• Commitment: тайные ставки в аукционах, фиксация прогнозов и заявок, фундамент ZKP (доказывающий «запечатывает» промежуточные значения).
• Честные лотереи и розыгрыши: VRF даёт случайного победителя, которого организатор не подкрутил и который проверяем всеми.
• Блокчейн: в protocol-of-stake VRF честно и непредсказуемо выбирает, кто формирует следующий блок (лидер-выбор), защищая от манипуляций; commitment-схемы лежат в основе схем «commit–reveal» для общей случайности.

Как защититься и применять грамотно

Главные грабли обязательств — забытая или неслучайная соль (ломает hiding) и слабая хеш-функция (теоретически ломает binding через коллизии): берите криптостойкий хеш и полноценно случайный r. Для случайности на нескольких участниках одного commit мало — нужна схема «commit–reveal», где все фиксируются до раскрытия, иначе последний раскрывающийся подкрутит итог; либо используйте VRF/пороговые источники случайности. И помните: VRF доказывает, что число вычислено по правилам, но честность всей лотереи зависит ещё и от того, кто контролирует вход функции.

Итоги

• Обязательство фиксирует значение скрытно (hiding) и без возможности подмены (binding); простейшая реализация — Hash(m || r) со случайной солью.
• Случайная соль обязательна: без неё значение из малого набора вскрывается перебором.
• VRF выдаёт непредсказуемый, но публично проверяемый и единственный результат для пары (ключ, вход).
• Применения — тайные ставки и честные «подбрось монету», проверяемые лотереи, выбор лидера и общая случайность в блокчейне.