Range proofs и Bulletproofs+
Доказать, что спрятанное число лежит между 0 и 2⁶⁴, не раскрывая его
Каждый выход доказывает, что его сумма v лежит в диапазоне [0, 2⁶⁴). Это закрывает «отрицательные суммы». Monero использует Bulletproofs+ (с августа 2022): одно агрегированное доказательство на всю транзакцию, размер растёт логарифмически — ~600 байт для 2 выходов.
Идея: разложить число на биты
Число из диапазона [0, 2⁶⁴) — это 64 бита: v = b₀·1 + b₁·2 + b₂·4 + … + b₆₃·2⁶³, где каждый bᵢ ∈ {0, 1}. Если доказать, что (1) каждое bᵢ — действительно 0 или 1 и (2) взвешенная сумма битов равна v, то v заведомо в диапазоне.
Условие «бит» записывается алгебраически: bᵢ·(bᵢ − 1) = 0. Задача сводится к доказательству того, что набор спрятанных чисел удовлетворяет набору уравнений — без раскрытия чисел.
Эволюция в Monero
| Период | Схема | Размер (2 выхода) | Как работает |
|---|---|---|---|
| 2017–2018 | Borromean | ~13 КБ | Каждый бит — отдельное обязательство + кольцевая подпись «это обязательство к 0 или к 2ⁱ». Линейный размер. |
| окт. 2018 – авг. 2022 | Bulletproofs | ~700 байт | Inner-product argument: логарифмический размер, агрегация нескольких выходов в одно доказательство. |
| с авг. 2022 | Bulletproofs+ | ~600 байт | Улучшенный вариант (weighted inner product): ещё меньше и быстрее. |
Переход на Bulletproofs в 2018 году уменьшил транзакции примерно в 10 раз и во столько же снизил комиссии. Это одно из самых заметных обновлений Monero за всю историю.
Как работает Bulletproofs (интуиция)
- Доказывающий фиксирует вектор битов
a_Lи векторa_R = a_L − 1одним векторным обязательством Педерсена. - Проверяющий (через хеш, Fiat–Shamir) присылает случайные вызовы
y, z. Все 64 условия «бит» и одно условие «сумма» склеиваются в одно равенство скалярного произведения двух векторов⟨l, r⟩ = t. Случайность вызовов гарантирует, что подогнать склеенное равенство без выполнения всех исходных нельзя. - Скалярное произведение векторов длины n доказывается рекурсивно: на каждом шаге векторы «складываются пополам» с новым вызовом, и после
log₂ nшагов остаётся по одному числу. На каждом шаге передаются 2 точки — отсюда логарифмический размер.
Агрегация: для m выходов векторы длины 64·m, а размер растёт лишь на 2·log₂ m точек. Поэтому Monero ограничивает число выходов в транзакции 16 и дополняет до степени двойки.
Плюсы и минусы
+
- Не нужен доверенный setup (в отличие от zk-SNARK в Zcash Sprout/Sapling).
- Опирается только на сложность дискретного логарифма — то же предположение, что и всё остальное в Monero.
- Компактно и агрегируется.
- Проверку многих доказательств можно делать пакетно (batch verification).
−
- Проверка линейна по числу битов — заметная доля времени проверки блока.
- Не квантово-устойчиво: квантовый компьютер сломает связывающее свойство Педерсена (сможет печатать деньги), хотя скрывающее свойство останется.
FCMP++ использует обобщение той же техники — Generalized Bulletproofs — чтобы доказывать путь в дереве всех выходов. Так что понимание Bulletproofs — хороший фундамент для понимания доказательств FCMP++.