Commitment Schemes и Pedersen

В 2018 году Monero уменьшил размер транзакций на 80%, не раскрыв ни одной суммы. Как можно проверить, что в транзакции нет мошенничества, если все суммы зашифрованы? Ответ в криптографических конвертах - commitment schemes. Они позволяют доказать факт без раскрытия содержимого: 'Я отправил ровно столько, сколько получил - проверь, но суммы не узнаешь.'

• **Monero** - каждая транзакция скрывает суммы через Pedersen commitments + Bulletproofs, обеспечивая финансовую приватность
• **Mimblewimble (Grin, Beam)** - весь протокол построен вокруг Pedersen commitments: транзакции = комбинации commitments, блоки можно 'схлопывать' (cut-through)
• **Закрытые аукционы и голосования** - commitment schemes позволяют зафиксировать выбор до момента подсчёта, предотвращая манипуляции

Предварительные знания

• Elliptic Curves (ECC)

Свойство скрытия (Hiding)

Представьте аукцион в закрытом формате. Каждый участник пишет свою ставку на бумаге и запечатывает в конверт. Конверты сдают организатору. Потом все конверты вскрываются одновременно. **Пока конверт запечатан - никто не знает ставку внутри.** Это и есть свойство hiding.

**Hiding (скрытие)** - по commitment нельзя определить, к какому значению он привязан. Зная `C = Commit(v)`, вычислить `v` невозможно.

Простейший commitment scheme построен на хешировании. Допустим, Алиса хочет зафиксировать число `42`, не раскрывая его:

**Без nonce hiding ломается!** Если commitment = Hash(value), а пространство значений маленькое (например, ставки от 1 до 100), атакующий просто перебирает все 100 хешей и находит исходное значение.

Различают два вида hiding. **Computational hiding** - вычислительно невозможно найти значение (опирается на сложность задачи). **Perfect (information-theoretic) hiding** - даже с бесконечной вычислительной мощностью значение не определить, потому что одному commitment может соответствовать несколько значений.

Свойство связывания (Binding)

Второе свойство commitment scheme - **binding**. После отправки commitment подменить значение невозможно. Конверт запечатан - открыть его и подложить другую записку не получится.

**Binding (связывание)** - невозможно найти два разных значения `v1 != v2`, для которых `Commit(v1) == Commit(v2)`. Автор зафиксирован в своём выборе.

В hash commitment binding опирается на **collision resistance** хеш-функции. Если SHA-256 устойчива к коллизиям, то нельзя найти пару `(v1, r1)` и `(v2, r2)` таких, что `H(v1 || r1) = H(v2 || r2)` при `v1 != v2`.

Компромисс: Perfect Hiding vs Perfect Binding

Существует фундаментальный trade-off: **нельзя одновременно иметь perfect hiding и perfect binding**. Приходится выбирать одно из двух в «perfect» варианте, а второе - в «computational».

**Hash commitment** - binding идеальный (коллизий в SHA-256 не бывает на практике), но hiding только вычислительный. **Pedersen commitment** наоборот - hiding идеальный (каждый C соответствует бесконечному количеству пар (v, r)), но binding опирается на сложность задачи дискретного логарифма.

Для блокчейнов чаще важнее **perfect hiding** - чтобы суммы транзакций были скрыты от всех, даже от квантового компьютера (пока commitment не раскрыт). Поэтому выбирают Pedersen.

Pedersen Commitment

Torben Pedersen в 1991 году предложил commitment scheme на эллиптических кривых, который обладает **perfect hiding** и **гомоморфными свойствами** - именно то, что нужно для конфиденциальных транзакций.

Формула

**Критическое требование:** никто не должен знать `k` такое, что `H = k * G`. Если `k` известен, binding ломается: зная `k`, можно подобрать `r'` для любого `v'`, чтобы `C = v' * G + r' * H`. Обычно `H` генерируют через hash-to-curve из ничего не значащей строки ("nothing up my sleeve").

Гомоморфные свойства

Главная суперспособность Pedersen commitment - **аддитивная гомоморфность**. Можно складывать commitments, и результат будет commitment к сумме значений:

Применение: Confidential Transactions

В **Monero** и **Mimblewimble** (Grin, Beam) суммы транзакций скрыты с помощью Pedersen commitments. Вместо открытых сумм в блокчейне хранятся точки на кривой. Валидаторы проверяют баланс, складывая commitments - если сумма входов минус сумма выходов равна нулевому commitment, значит деньги не создались из воздуха.

Range Proofs

Pedersen commitment скрывает суммы и позволяет проверить баланс. Но есть проблема: **что мешает отправить отрицательную сумму?**

**Без range proof Pedersen commitment бесполезен для транзакций.** Злоумышленник может создавать монеты из воздуха, используя отрицательные значения.

Идея Range Proof

**Range proof** - это доказательство того, что значение `v` в commitment `C = v*G + r*H` лежит в допустимом диапазоне, например `0 <= v < 2^64`, без раскрытия самого `v`.

Базовая идея: представить `v` в двоичном виде `v = b0 + 2*b1 + 4*b2 + ...`, создать commitment для каждого бита и доказать, что каждый бит равен 0 или 1. Если все биты неотрицательны, значит и `v >= 0`.

Bulletproofs: Компактные Range Proofs

Наивный range proof для 64-битного числа требует 64 отдельных доказательства - это огромный размер. В 2017 году Bunz, Bootle и другие представили **Bulletproofs** - метод, который сжимает доказательство логарифмически.

**Monero** перешёл на Bulletproofs в 2018, сократив размер транзакций на **80%** и комиссии пропорционально. Bulletproofs+ (2020) дали ещё ~6% сжатия.

Применение в протоколах

• **Monero** - Bulletproofs+ для скрытия сумм в каждой транзакции
• **Mimblewimble (Grin, Beam)** - Bulletproofs как обязательная часть протокола
• **Zcash Orchard** - использует другой подход (Halo 2), но решает ту же задачу
• **Elements/Liquid** (сайдчейн Bitcoin) - Confidential Transactions с Bulletproofs

Ключевые идеи

• **Commitment scheme** - криптографический конверт с двумя свойствами: hiding (содержимое скрыто) и binding (содержимое нельзя подменить)
• **Нельзя достичь perfect hiding и perfect binding одновременно** - фундаментальный trade-off. Hash commitment дает perfect binding, Pedersen - perfect hiding
• **Pedersen commitment `C = v*G + r*H`** обладает аддитивной гомоморфностью: можно проверить баланс транзакции (входы == выходы), не раскрывая сумм
• **Range proofs** необходимы для предотвращения атак с отрицательными суммами. Bulletproofs сжали их с 5 KB до 0.7 KB - именно поэтому Monero в 2018 уменьшил транзакции на 80%

Связанные темы

Commitment schemes - мост между эллиптическими кривыми и доказательствами с нулевым разглашением:

• Эллиптические кривые (ECC) — Pedersen commitment строится на операциях с точками эллиптической кривой и сложности задачи дискретного логарифма
• Threshold Cryptography — Distributed key generation использует Pedersen commitments для верификации долей секрета (Verifiable Secret Sharing)
• Zero-Knowledge Proofs — Commitment schemes - базовый примитив для ZKP. Range proofs - частный случай zero-knowledge доказательств

Вопросы для размышления

• При разработке системы тайного голосования - какой вариант commitment scheme предпочесть: hash commitment или Pedersen? Почему?
• В Mimblewimble можно удалять промежуточные транзакции из блока (cut-through). Как гомоморфность Pedersen commitments делает это возможным?
• Если бы квантовые компьютеры сломали задачу дискретного логарифма, какое свойство Pedersen commitment пострадает - hiding или binding? Какие последствия это имело бы для Monero?

Связанные уроки

• bc-02-hashing — Hash-based commitment schemes use cryptographic hashes for hiding; hashing is prerequisite
• bc-03-merkle — Merkle trees are a specific commitment structure for sets of values
• bc-13-kzg — KZG is a polynomial commitment scheme; understanding the abstract commitment concept is required first
• bc-09-threshold-crypto — Threshold schemes often use commitments (Pedersen commitments in Shamir sharing); the concepts compose
• crypto-35-blockchain-crypto