Технический › Кто отправитель?

Кольцевые подписи

Как доказать «я владею одним из этих ключей», не говоря каким

Коротко

Кольцевая подпись доказывает, что подписант знает приватный ключ к одному из n публичных ключей кольца, не раскрывая, к какому. Monero использует линкуемую версию — к подписи прилагается key image, чтобы нельзя было потратить один выход дважды. Сегодняшняя схема называется CLSAG, размер кольца — 16.

Сначала — обычная подпись Шнорра

Чтобы понять кольцо, сначала разберём, как доказать знание одного ключа x для P = x·G:

  1. Подписант берёт случайное α и вычисляет α·G.
  2. Вычисляет «вызов» c = Hs(сообщение ‖ α·G).
  3. Вычисляет ответ s = α − c·x. Подпись — это (c, s).
  4. Проверяющий восстанавливает s·G + c·P = (α − cx)·G + c·x·G = α·G и проверяет, что Hs(сообщение ‖ α·G) = c.

Без знания x подобрать s под заданный c невозможно: c зависит от α·G, которое нужно зафиксировать до того, как узнаешь c.

Идея кольца: замкнуть цепочку вызовов

Теперь у нас n публичных ключей P₀ … Pₙ₋₁, и мы знаем ключ только к одному, скажем Pπ. Трюк: каждый вызов вычисляется из предыдущего звена, и цепочка замыкается в кольцо.

P₀ (π) P₁ P₂ P₃ P₄ P₅ c₁ c₂ c₃ c₄ c₅ c₀ cᵢ₊₁ = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ) π — настоящий ключ: единственное место, где кольцо «замыкается» с помощью x для остальных sᵢ просто случайны
  1. На позиции настоящего ключа π берём случайное α и вычисляем следующий вызов: c_{π+1} = Hs(m ‖ α·G).
  2. Для каждого следующего (чужого) ключа выбираем случайный sᵢ и считаем c_{i+1} = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ). Обходим кольцо по кругу.
  3. Возвращаемся к π, уже зная c_π. Чтобы кольцо сошлось, нужно s_π·G + c_π·P_π = α·G, то есть s_π = α − c_π·x. Это можно вычислить только зная x.
  4. Подпись: (c₀, s₀, s₁, …, sₙ₋₁).

Проверяющий стартует с c₀, проходит все звенья по одной формуле и проверяет, что вернулся в тот же c₀. Все звенья выглядят одинаково — по подписи нельзя понять, где было «замыкание».

Линкуемость: LSAG

Простая кольцевая подпись не мешает потратить один и тот же выход дважды в разных кольцах. Поэтому Monero использует линкуемую подпись: подписант публикует key image I = x·Hp(P_π) и в каждом звене дополнительно доказывает, что тот же самый x связывает I и Hp(Pᵢ):

c_{i+1} = Hs( m ‖ sᵢ·G + cᵢ·Pᵢ ‖ sᵢ·Hp(Pᵢ) + cᵢ·I )

Два использования одного ключа дадут одинаковый I — и сеть отклонит вторую трату.

MLSAG → CLSAG

В RingCT нужно доказать не одно, а два утверждения на каждый член кольца: знание ключа выхода и то, что разность обязательств — обязательство к нулю (см. RingCT). Сначала (2017) это делали подписью MLSAG — по сути, два кольца, склеенные вместе: на каждого члена кольца по два s.

В октябре 2020 года (хардфорк v13) её заменили на CLSAG (Concise LSAG): два ключа на позиции сворачиваются в один через случайную линейную комбинацию с коэффициентами-хешами. На каждого члена кольца — один s. Подпись стала примерно на 25% меньше и быстрее проверяется.

W_i = μ_P·P_i + μ_C·(C_i − C̃)     доказываем знание ключа к W_π

История размера кольца

КогдаМинимум участниковКомментарий
20141 (без приманок)Наследие CryptoNote: «0-mixin» транзакции разрешены
20163Хардфорк, запрет нулевых колец
20175Вместе с RingCT
апрель 20187После исследований цепной реакции (chain reaction)
октябрь 201811, фиксированноРазмер кольца стал одинаковым у всех
август 202216, фиксированноХардфорк v15 (вместе с Bulletproofs+ и view tags)

Почему размер фиксирован? Если бы каждый выбирал сам, нестандартный размер кольца стал бы отпечатком кошелька.

Почему не 1000?

Размер CLSAG и время проверки растут линейно с размером кольца. Кольцо на 1000 участников — это ~32 КБ на каждый вход и в десятки раз более медленная синхронизация узлов. Схемы с логарифмическим размером (Triptych, Arcturus, Seraphis) исследовались, но в итоге Monero выбрал радикальный вариант — FCMP++, где «кольцо» — весь блокчейн.