Bulletproofs

Bulletproofs — это протокол доказательства с нулевым разглашением (zero-knowledge proof), позволяющий верификатору убедиться в истинности некоторого утверждения, не раскрывая при этом никакой дополнительной информации, кроме самого факта его истинности. Отличительной особенностью Bulletproofs является отсутствие необходимости в доверенной настройке (trusted setup) и короткий размер доказательства, который растёт логарифмически от размера доказываемого утверждения. Протокол был разработан в 2017 году группой криптографов, включая Бенедикта Бюнца, Джонатана Боуэна, Дэна Бонеха и Грега Максвелла.

История и предпосылки создания

Разработка Bulletproofs была мотивирована потребностью в эффективных и практичных доказательствах с нулевым разглашением для использования в криптовалютах и блокчейн-системах. Существовавшие на тот момент протоколы, такие как zk-SNARKs, обладали рядом существенных недостатков: они требовали доверенной настройки, которая создавала риск компрометации системы, и имели сложную вычислительную структуру. Кроме того, доказательства zk-SNARKs были несовместимы с квантовыми вычислениями (не были постквантовыми).

В 2017 году вышла работа «Bulletproofs: Short Proofs for Confidential Transactions and More», в которой авторы представили новый тип доказательств с нулевым разглашением, лишённый этих недостатков. Название «Bulletproofs» (от англ. bullet — пуля) отражает их устойчивость к атакам и компактность — доказательство «летит, как пуля», не раскрывая лишней информации.

Основные свойства

Отсутствие доверенной настройки

В отличие от zk-SNARKs, которые требуют генерации общих эталонных параметров (common reference string) в ходе доверенной церемонии, Bulletproofs не нуждаются в доверенной настройке. Это означает, что для их работы не требуется доверять какой-либо третьей стороне или группе лиц, что существенно повышает безопасность и децентрализацию системы.

Логарифмический размер доказательства

Размер доказательства в Bulletproofs растёт как O(log n), где n — размер доказываемого утверждения (например, количество транзакций или число битов в секрете). Для сравнения, у классических доказательств с нулевым разглашением размер обычно линейный (O(n)). Например, для доказательства корректности 64-битного числа размер доказательства Bulletproofs составляет около 1,5 килобайт, тогда как у линейных протоколов он был бы в десятки раз больше.

Постквантовая устойчивость

Bulletproofs основаны на предположении о сложности дискретного логарифмирования в эллиптических кривых, которое, как считается, не поддаётся эффективному взлому с помощью квантовых компьютеров (в отличие от некоторых других криптографических схем). Это делает их перспективными для использования в постквантовой эпохе.

Интерактивность и неинтерактивность

Исходный протокол Bulletproofs является интерактивным — он требует нескольких раундов обмена сообщениями между доказывающим и верификатором. Однако с помощью преобразования Фиата — Шамира (Fiat-Shamir heuristic) его можно сделать неинтерактивным, что позволяет использовать его в блокчейн-системах, где требуется однократная отправка доказательства.

Устройство и принцип работы

Математическая основа

Bulletproofs строятся на основе внутренних произведений (inner product arguments) и полиномиальных коммитментов (polynomial commitments). Доказывающий представляет утверждение в виде системы линейных уравнений и доказывает, что существует решение, удовлетворяющее определённым ограничениям, не раскрывая само решение.

Основные этапы

1. Коммитмент: Доказывающий фиксирует секретное значение (например, сумму транзакции) с помощью криптографического обязательства (commitment), например, схемы Педерсена (Pedersen commitment).
2. Доказательство: Доказывающий генерирует доказательство, которое показывает, что закоммиченное значение удовлетворяет заданным условиям (например, находится в определённом диапазоне, не является отрицательным и т.д.).
3. Верификация: Верификатор проверяет доказательство, не узнавая при этом самого секретного значения.

Протокол доказательства диапазона (Range Proof)

Наиболее распространённое применение Bulletproofs — это доказательство того, что число находится в заданном диапазоне (например, от 0 до 2^64). Для этого число представляется в двоичной системе счисления, и доказывающий показывает, что каждый бит равен 0 или 1, а также что сумма этих битов с соответствующими весами даёт исходное число.

Применение

Криптовалюты и конфиденциальные транзакции

Bulletproofs широко используются в криптовалютах для обеспечения конфиденциальности транзакций. Например, в криптовалюте Monero (XMR) Bulletproofs применяются для скрытия сумм переводов, при этом позволяя верификаторам убедиться, что суммы не являются отрицательными и не превышают баланс отправителя. В 2018 году Monero перешла на Bulletproofs, что позволило сократить размер транзакций примерно на 80% и снизить комиссии.

Блокчейн-платформы

Протокол используется в различных блокчейн-проектах, таких как Mina (ранее Coda), где Bulletproofs применяются для доказательства корректности состояния блокчейна без его полной загрузки. Также Bulletproofs интегрированы в платформу Ethereum (организация признана нежелательной в РФ) через смарт-контракты для реализации приватных транзакций и децентрализованных приложений.

Другие области

• Системы голосования: Bulletproofs позволяют проверить, что голос отдан за одного из кандидатов, не раскрывая, за кого именно.
• Финансовые системы: Доказательство платёжеспособности без раскрытия баланса.
• Аутентификация: Доказательство знания пароля без его передачи.

Критика и ограничения

Вычислительная сложность

Хотя размер доказательства логарифмический, процесс генерации доказательства может быть вычислительно затратным. Для больших утверждений (например, доказательство диапазона для 256-битного числа) время генерации может составлять несколько секунд на обычном компьютере, что может быть неприемлемо для некоторых приложений реального времени.

Время верификации

Верификация Bulletproofs также требует значительных вычислительных ресурсов, хотя и меньше, чем генерация. В некоторых системах это может стать узким местом.

Ограниченная выразительность

Bulletproofs изначально разработаны для доказательства линейных утверждений (например, диапазонов, равенств). Для более сложных утверждений (например, произвольных вычислений) требуются другие протоколы, такие как zk-STARKs.

Сравнение с другими протоколами

Интересные факты

• Название «Bulletproofs» было выбрано авторами, чтобы подчеркнуть, что протокол «не пробиваем» для атак, в отличие от некоторых других схем.
• В 2018 году команда Monero провела аудит безопасности Bulletproofs, в результате которого не было найдено критических уязвимостей.
• Bulletproofs могут быть использованы для создания «доказательств с нулевым разглашением для всех NP-проблем», что делает их теоретически универсальными, хотя на практике их применение ограничено вычислительной сложностью.

Источники

• Bünz, B., Bootle, J., Boneh, D., et al. (2017). «Bulletproofs: Short Proofs for Confidential Transactions and More».
• Документация криптовалюты Monero (getmonero.org).
• Исследовательские работы по доказательствам с нулевым разглашением (ZKProof Standards).