Bulletproofs простыми словами: как проверяются скрытые суммы

Bulletproofs — это короткие доказательства диапазона с нулевым разглашением, которые позволяют криптовалюте скрывать сумму каждой транзакции, а каждой ноде — по-прежнему проверять, что монеты не были созданы из ничего. В этом руководстве объясняется, что такое обязательства Педерсена, зачем скрытым суммам доказательства диапазона, как Bulletproofs делают эти доказательства компактными и как Blocknet использует их на каждом выходе.

Что такое Bulletproofs?

Статья Bulletproofs: Short Proofs for Confidential Transactions and More была представлена на симпозиуме IEEE Symposium on Security and Privacy в 2018 году. Авторы создали их для конфиденциальных транзакций, в которых суммы в блокчейне заменены обязательствами. Чтобы понять, зачем вообще нужно такое доказательство, начнём с обязательства.

Что такое обязательство Педерсена?

Обязательство (коммитмент) — это криптографическая версия запечатанного конверта. Вы кладёте внутрь число, показываете всем конверт и позже можете доказать, что было внутри. Никто не может прочитать число по конверту, а вы не можете потом подменить его другим.

Обязательство Педерсена, описанное Торбеном Педерсеном в 1991 году, делает это с помощью точек эллиптической кривой. Чтобы создать обязательство для суммы v, кошелёк выбирает случайный секрет r, который называется ослепляющим множителем (blinding factor), и вычисляет:

C = v·G + r·H

G и H — две фиксированные публичные точки на кривой, выбранные так, чтобы никто не знал, как выразить одну через кратное другой. Результат C — одна 32-байтовая точка. У неё два свойства:

• Скрытие. Поскольку r случаен, C выглядит как случайная точка. Два обязательства для одной и той же суммы никак не связаны между собой, и само обязательство ничего не говорит наблюдателю о v.
• Связывание. После публикации C кошелёк не может раскрыть его как другую сумму. Для этого пришлось бы решить задачу дискретного логарифма на кривой.

Как ноды проверяют транзакцию, которую не могут прочитать?

Сложение двух обязательств даёт (v1 + v2)·G + (r1 + r2)·H, что само является обязательством для v1 + v2. Отправитель подбирает ослепляющие множители так, чтобы их сумма на входах равнялась сумме на выходах. Если и суммы сходятся, разность между суммой входов и суммой выходов равна ровно нулю, и любая нода может это проверить.

Комиссия сети — единственное публичное число в транзакции. Ноды превращают её в обязательство с нулевым ослепляющим множителем и добавляют на сторону выходов, так что проверка выглядит так: входы = выходы + комиссия.

Зачем скрытым суммам доказательства диапазона?

Арифметика обязательств работает по модулю очень большого числа — порядка группы кривой, примерно 2^252. В такой арифметике «отрицательная» сумма — это просто огромная положительная. Кто-то мог бы потратить вход стоимостью 10 монет и создать два выхода: один на 11 монет и один на «минус 1». Обязательства идеально сойдутся, и из ничего появится 1 монета, скрытая от любого наблюдателя.

Доказательство диапазона закрывает эту лазейку. Оно доказывает, что сумма внутри обязательства лежит между 0 и 2^64, не говоря, какова она. Когда каждый выход ограничен таким образом, несколько выходов никогда не дадут в сумме число, достаточно большое, чтобы выйти за порядок группы, поэтому сходящиеся обязательства означают сходящиеся суммы.

В ранних схемах конфиденциальных транзакций использовались доказательства диапазона, размер которых рос линейно с числом бит. Bulletproofs растут только с логарифмом, и 64-битное доказательство занимает всего несколько сотен байт.

Как работают Bulletproofs?

Bulletproof доказывает диапазон в три шага.

1. Разложить сумму на биты. 64-битная сумма превращается в вектор из 64 бит. Доказывающий создаёт обязательство для этого вектора и показывает о нём два факта: каждый элемент равен 0 или 1, а биты, взвешенные степенями двойки, в сумме дают сумму, скрытую в обязательстве.
2. Свести эти факты к одному скалярному произведению. С помощью случайных вызовов доказывающий сворачивает все эти условия в одно утверждение о скалярном произведении двух векторов. Поскольку вызовы случайны, ложное утверждение проходит лишь с пренебрежимо малой вероятностью.
3. Доказать скалярное произведение делением пополам. В каждом раунде доказывающий отправляет две точки кривой, L и R, и оба вектора сворачиваются до половины длины. После log2(64) = 6 раундов остаётся одна пара чисел.

Именно это деление пополам определяет размер. В аннотации статьи размер доказательства диапазона указан как 2·log2(n) + 9 элементов группы и поля для n-битного диапазона. Для 64 бит это 12 точек из шести раундов плюс ещё 9, всего 21 элемент, или 672 байта, если каждый элемент занимает 32 байта.

Доказательство неинтерактивно. Вместо живого проверяющего, который отправляет вызовы, обе стороны получают их, хешируя запись доказательства, — это стандартный приём, известный как эвристика Фиата — Шамира. Bulletproofs также не нужна доверенная настройка: генераторы публичны и выводятся открыто, а безопасность опирается только на предположение о сложности дискретного логарифма. Несколько доказательств можно агрегировать, добавляя лишь логарифмическое число элементов, а проверку можно выполнять пакетно.

Кто использует Bulletproofs?

Monero включил Bulletproofs в обновлении сети 18 октября 2018 года (релиз v0.13.0), чтобы уменьшить размер транзакций. Библиотека bulletproofs на Rust от проекта dalek-cryptography реализует их над группой Ristretto кривой Curve25519, и криптографическая библиотека Blocknet построена на ней.

Как Blocknet скрывает каждую сумму?

В Blocknet каждый выход каждой транзакции содержит обязательство Педерсена вместо суммы, и каждый выход несёт собственное 64-битное доказательство Bulletproof. Приватность — часть формата транзакций без прозрачного режима, поэтому отправить платёж с видимой суммой невозможно.

Вот что проверяет нода, прежде чем принять транзакцию:

• Каждое доказательство диапазона. Bulletproof каждого выхода должен проходить проверку относительно его обязательства, доказывая, что сумма лежит между 0 и 2^64. Доказательства используют запись с меткой «Blocknet Range Proof», которая привязывает каждое доказательство к Blocknet.
• Баланс. Каждый вход содержит обязательство псевдовыхода, и кольцевая подпись доказывает, что оно скрывает ту же сумму, что и настоящая монета, которая тратится, не раскрывая, какой это участник кольца. Затем нода проверяет, что псевдовыходы в сумме дают выходы плюс комиссию.
• Новые монеты. Награда за блок следует публичному графику, поэтому для смайненного выхода нода восстанавливает обязательство, которое ожидает на этой высоте, и проверяет совпадение.

Это можно увидеть в обозревателе Blocknet. На странице транзакции суммы указаны как «hidden · Pedersen commitments», а у каждого выхода показаны обязательство, зашифрованное мемо и доказательство диапазона «672 bytes · Bulletproof» — ровно тот размер, который предсказывает расчёт выше.

Получатель при этом видит настоящую цифру. Каждый выход содержит сумму, зашифрованную секретом, общим для кошельков отправителя и получателя, и кошелёк получателя расшифровывает её приватным ключом просмотра. Сумму видят два участника платежа и больше никто.

Скрытые суммы работают вместе с другими уровнями Blocknet: кольцевые подписи по 16 выходам скрывают отправителя, одноразовые стелс-адреса скрывают получателя, а Dandelion++ скрывает, где транзакция вошла в сеть. Руководство по функциям приватности Blocknet разбирает каждый из них.

Получите собственные приватные BNT

Простой способ получить монеты со скрытыми суммами — намайнить их. Blocknet использует требовательное к памяти доказательство работы Argon2id, которое можно майнить на обычном компьютере, а seine майнит его на вашем CPU вместе с любыми GPU NVIDIA и настраивается сам, без конфигурации. Каждая выплата, которую отправляет вам bntpool.com, приходит как приватный выход с обязательством и Bulletproof. Руководство по майнингу проведёт вас от загрузки до принятых шар за несколько минут.