🎓 Хеш, commit-reveal и HMAC

Зачем эта заметка

Провабли-фейр кости стоят на трёх криптопримитивах. 🎓 Что такое CSPRNG разобрал первый кирпич — откуда берётся непредсказуемый сид. Здесь — три остальных: хеш-функция, коммитмент (commit-reveal) и HMAC, а также главный инсайт — почему бросок делает не генератор случайных чисел, а PRF. Как всё собрано в рабочий алгоритм — 06 Честность кубиков.

---

1. Хеш-функция — односторонняя «мясорубка»

Криптографическая хеш-функция (у нас SHA-256) превращает вход любого размера в фиксированный дайджест (256 бит). Три свойства, на которых всё держится:

• Детерминизм. Один и тот же вход → всегда один и тот же дайджест.
• Односторонность (preimage resistance). По дайджесту нельзя восстановить вход — только перебор, а $2^{256}$ неперебираем.
• Стойкость к коллизиям. Нельзя найти два разных входа с одинаковым дайджестом (и по данному входу — второй с тем же дайджестом).

Плюс лавинный эффект: смена одного бита входа меняет ~половину бит выхода — дайджест не «протекает» информацией о входе.

flowchart LR
    in["вход любого размера<br/>(32 байта serverSeed)"] --> H["SHA-256"]
    H --> out["дайджест — 256 бит<br/>7e3ad1…2136f"]
    out -. "обратно — НЕЛЬЗЯ<br/>(односторонность)" .-> in
    style out fill:#14532d,color:#fff

---

2. Коммитмент — запечатанный конверт

Коммитмент позволяет «зафиксировать значение, не раскрывая его», а позже доказать, что оно не менялось. У него два свойства, и оба нам нужны:

• Hiding (скрытность): по коммиту нельзя узнать секрет — следует из односторонности хеша.
• Binding (связанность): нельзя позже подсунуть другой секрет под тот же коммит — следует из стойкости к коллизиям.

Реализация — просто хеш секрета: $commit=\text{SHA-256}(serverSeed)$.

Почему без отдельной «соли»

Hiding честного commit = H(x) держится, только если x сам высокоэнтропийный. Если бы мы коммитили кость $\mathrm{1..6}$, противник хешнул бы все 6 вариантов и вскрыл конверт. Но serverSeed — 256 случайных бит от CSPRNG, перебрать нельзя → соль не нужна. Вот зачем сид обязан быть криптостойким.

Отсюда протокол commit-reveal — две фазы:

flowchart TD
    subgraph P1["Фаза 1 — COMMIT (до партии)"]
        s["serverSeed (секрет)"] --> c["commit = SHA-256(seed)"]
        c --> pub["публикуется игрокам<br/>СЕЙЧАС"]
    end
    subgraph P2["Фаза 2 — REVEAL (после партии)"]
        rev["сервер раскрывает serverSeed"] --> chk{"SHA-256(seed)<br/>== commit?"}
        chk -->|да| ok["сид тот же — не подменён ✓"]
        chk -->|нет| bad["ПОЙМАН читер ✗"]
    end
    P1 -.->|"партия идёт"| P2
    style ok fill:#14532d,color:#fff
    style bad fill:#7f1d1d,color:#fff

Между фазами сервер связан своим сидом: конверт уже у игроков, поменять карточку нельзя. Именно поэтому в CSPRNG так важна backtracking resistance — публикация коммита не должна помогать вычислить сид.

---

3. HMAC — это PRF, а не RNG

Вот сердце всей схемы и самый частый источник путаницы.

HMAC (Hash-based Message Authentication Code) — это хеш с ключом:

${\mathrm{HMAC}}_K(m)=H((K\oplus opad)\Vert H((K\oplus ipad)\Vert m))$

Нам важно не «аутентификация сообщения», а то, что HMAC — это PRF (Pseudo-Random Function): семейство функций, проиндексированных ключом $K$, такое что без знания ключа выход неотличим от истинно случайной функции.

Ставим ключом serverSeed, сообщением — «что бросаем» (клиентские сиды + номер хода), и получаем:

$\text{roll}(ply)=\mathrm{HMAC}\text{-}SHA256(\underset{\text{ключ}}{\underbrace{serverSeed}},\underset{\text{сообщение}}{\underbrace{clientSeeds\Vert ply}})$

Два свойства этого выхода одновременно:

1. Детерминированность — при известных ключе и сообщении бросок пересчитывается точно. Это и делает игру проверяемой: после reveal любой считает те же кости.
2. Непредсказуемость без ключа — пока serverSeed в конверте, предсказать бросок нельзя, даже зная все прошлые броски и оба клиентских сида.

CSPRNG ≠ PRF — в чём разница

	CSPRNG	PRF (HMAC)
Что это	поток случайных бит	функция вход → выход
Детерминизм	нет — каждый вызов новый	да — f(key, msg) воспроизводима
Секрет	внутреннее состояние	ключ
Роль в костях	сгенерировать serverSeed (1 раз)	вычислить каждый бросок

Игроку нужна воспроизводимость броска (чтобы перепроверить) — значит бросок обязан быть детерминированной функцией, то есть PRF, а не выходом RNG. RNG нужен лишь чтобы родить непредсказуемый ключ для этой функции.

Тот же приём в «большой» криптографии

Детерминированный ECDSA (RFC 6979) выводит секретный nonce подписи как HMAC_DRBG(приватный ключ, hash(сообщение)) — ровно тот же трюк «детерминированно, но непредсказуемо без ключа», чтобы убрать зависимость от качества RNG в момент подписи. Наши кости — это тот же паттерн под настольную игру.

---

4. Почему нужны ОБА кирпича

Ни CSPRNG, ни PRF по отдельности не дают честность:

• Только CSPRNG (сервер бросает стойким генератором, «доверьтесь») — непроверяемо. Смещённый или багнутый оператор незаметен.
• Только PRF без commit — сервер подберёт serverSeed после того, как увидит клиентские сиды, под нужный исход.

Честность рождается из композиции: commit фиксирует сид до появления клиентской энтропии, а PRF делает броски воспроизводимыми.

flowchart TD
    sr["SecureRandom<br/>(CSPRNG)"] -->|"1 раз"| seed["serverSeed (32 байта)"]
    seed --> commit["SHA-256 → commit<br/>📢 публикуется ДО игры"]
    seed -->|"ключ"| hmac["HMAC-SHA256"]
    cw["clientSeed белых"] -->|"сообщение"| hmac
    cb["clientSeed чёрных"] -->|"сообщение"| hmac
    ply["номер хода ply"] -->|"сообщение"| hmac
    hmac --> bytes["псевдослучайные байты"]
    bytes --> rej["rejection sampling"]
    rej --> dice["🎲 три кости 1..6"]
    seed -.->|"после партии: REVEAL + проверка commit"| commit
    style commit fill:#14532d,color:#fff
    style dice fill:#1e3a8a,color:#fff

Формальная гарантия: доказуемо, что сервер закоммитил сид до того, как увидел клиентские сиды, не менял его и произвёл каждый бросок по опубликованной формуле. Что сид сам по себе «хорошо случаен» по отдельности не доказывается — но это и не нужно: клиентская энтропия, пришедшая после commit, не даёт оператору подобрать выгодный сид, даже если бы он хотел.

---

5. От байт к костям — modulo bias и rejection sampling

Последний шаг — превратить псевдослучайные байты HMAC в кость $\mathrm{1..6}$. Наивное байт % 6 смещает распределение. Байт пробегает $\mathrm{0..255}$, а $256=42\cdot 6+4$:

flowchart LR
    b["байт 0..255<br/>(256 значений)"] --> mod{"% 6"}
    mod --> r0["остаток 0,1,2,3<br/>← по 43 байта"]
    mod --> r1["остаток 4,5<br/>← по 42 байта"]
    style r0 fill:#7f1d1d,color:#fff

Остатки $0,1,2,3$ приходят из 43 байтов каждый, а $4,5$ — из 42. Значит кости $1,2,3,4$ чуть вероятнее $5,6$ — маленькое, но измеримое смещение, которого честной игре быть не должно.

Лечение — rejection sampling: отбрасываем байты $\ge 252$ (где $252=42\cdot 6$ — наибольшее кратное шести в пределах байта). Оставшиеся $\mathrm{0..251}$ — ровно $252$ значения, делятся на 6 нацело → каждая грань равновероятна:

$\text{кость}=(b\mathrm{mod}6)+1,\text{если }b<252;\text{иначе }b\text{ отбрасывается}$

Если байтов блока не хватило на три кости — берётся следующий HMAC-блок (со счётчиком в хвосте сообщения). Точная as-built формула сообщения и wire-контракт — в 06 §Точный алгоритм.

---

Связанное

• 🎓 Что такое CSPRNG — первый кирпич: откуда берётся непредсказуемый serverSeed.
• 06 Честность кубиков — провабли-фейр и верификация — сборка всех примитивов в рабочий алгоритм + пошаговая верификация партии на Python.
• ADR-0008 — почему именно commit-reveal (а не голый CSPRNG или блокчейн).