Технический › Сколько?

Обязательства Педерсена

Как сложить суммы, которых не видно, и убедиться, что баланс сходится

Коротко

Сумма v прячется в точку C = y·G + v·H, где y — случайная «маска». Обязательства можно складывать: сумма обязательств — обязательство к сумме сумм. Сеть проверяет, что Σ входов − Σ выходов − комиссия·H — это обязательство к нулю, не узнавая ни одной суммы.

Что такое обязательство

Обязательство (commitment) — это «запечатанный конверт с числом». У него два свойства:

  • Скрывающее (hiding): по конверту нельзя узнать число.
  • Связывающее (binding): открыть конверт как другое число нельзя.

Обязательство Педерсена на эллиптической кривой:

C = y·G + v·H v — сумма в атомарных единицах (1 XMR = 10¹² единиц), y — случайный ослепляющий множитель (blinding factor), G и H — две независимые точки

Без маски y было бы C = v·H, и сумму легко подобрать перебором (сумм не так много). Маска делает C неотличимым от случайной точки.

Почему важен второй генератор H

H получена хешированием G в точку, поэтому никто не знает число k, такое что H = k·G. Если бы кто-то знал k, он мог бы «переоткрыть» обязательство: y·G + v·H = (y + k·v)·G + 0·H = (y + k(v − v'))·G + v'·H — и печатать деньги из воздуха. Неизвестность k — ровно то, на чём держится связывающее свойство.

Гомоморфизм: складываем не глядя

C₁ + C₂ = (y₁ + y₂)·G + (v₁ + v₂)·H

Сумма двух конвертов — конверт с суммой. Поэтому сеть может проверить закон сохранения:

C_in (5 XMR)сумма не видна = C_out1 (3 XMR)получателю + C_out2 (1.99)сдача + 0.01·Hкомиссия C_in − C_out1 − C_out2 − fee·H = (y_in − y₁ − y₂)·G + 0·H → это обязательство к нулю: точка вида z·G

Остаётся доказать, что разность действительно имеет вид z·G (а не z·G + что-то·H). Для этого достаточно подписать её как публичный ключ: подпись получится, только если вы знаете z и в разности нет компоненты H. Комиссия публична, поэтому её обязательство — просто fee·H без маски.

Псевдовыходы: как это работает с кольцами

Есть загвоздка: на входе у нас кольцо из 16 выходов, и мы не можем сказать, чьё обязательство настоящее. Решение RingCT — псевдовыходное обязательство C̃ (pseudo-out):

  1. для каждого входа отправитель создаёт новое обязательство C̃ = y'·G + v·H с той же суммой, но новой маской;
  2. маски выбираются так, чтобы Σ C̃ = Σ C_out + fee·H точно (баланс проверяется по псевдовыходам);
  3. в CLSAG для каждого члена кольца доказывается, что C_i − C̃ — обязательство к нулю для настоящего члена: C_π − C̃ = (y − y')·G.

Так кольцевая подпись одновременно доказывает владение выходом и то, что сумма псевдовыхода равна сумме настоящего входа.

Как получатель узнаёт сумму и маску

Отправитель и получатель разделяют секрет Hs(8rA ‖ i) (см. одноразовые адреса). Из него выводятся:

y = Hs( "commitment_mask" ‖ Hs(8rA ‖ i) )
amount_enc = v ⊕ Keccak( "amount" ‖ Hs(8rA ‖ i) )[0..8]

Зашифрованная сумма (8 байт) лежит в транзакции. Получатель расшифровывает v, вычисляет y и проверяет, что y·G + v·H совпадает с C в блокчейне.

А что мешает записать отрицательную сумму?

Все вычисления идут по модулю l. «−1» — это l − 1, огромное число. Можно создать выход на 1000 XMR и выход на «−999 XMR», баланс сойдётся, и 999 XMR появятся из ниоткуда. Обязательства этого не видят. Поэтому каждый выход сопровождается доказательством диапазона.