Технический › FCMP++

Перерандомизация входа

Как потратить выход из дерева, не показав, какой именно

Коротко

В FCMP++ вход транзакции — не ссылка на выход, а его «перекрашенная» копия: к каждой точке выхода прибавляется случайное кратное отдельного генератора. Получившиеся точки неотличимы от случайных, но тратящий знает «краску» и может доказать: (1) снятие краски даёт какой-то лист дерева и (2) он знает ключ этого листа.

Зачем вообще перерандомизировать

Membership proof доказывает утверждение «точка X — лист дерева». Если опубликовать сам выход O, доказывать уже нечего: все видят, какой выход тратится. Если не публиковать ничего, то нечего связать с key image и обязательством суммы. Нужна середина: публикуем что-то, что математически связано с выходом, но эту связь видит только тратящий.

Такой приём — «перерандомизация» (re-randomization). В RingCT роль похожего приёма играл псевдовыход C̃: то же обязательство суммы, но с новой маской. FCMP++ применяет ту же идею ко всем частям выхода.

Из чего состоит лист

лист = ( O.x, I.x, C.x ) x-координаты трёх точек Ed25519: ключ выхода O, генератор key image I = Hp(O), обязательство C

O и C берутся прямо из выхода в блокчейне, I узел вычисляет сам при добавлении выхода в дерево. В дерево кладутся только координаты (числа), а не сами точки — так их удобнее «хешировать» на следующем уровне (см. Curve Trees).

Формулы перерандомизации

Тратящий выбирает четыре случайных скаляра r_o, r_i, r_r_i, r_c и публикует:

ПубликуетсяФормулаЧто прячет
ÕO + r_o·Tкакой ключ выхода тратится
ĨI + r_i·Uгенератор key image этого выхода
Rr_i·V + r_r_i·Tобязательство к r_i — нужно, чтобы связать Ĩ с key image
C̃C + r_c·Gкакое обязательство суммы тратится (как псевдовыход в RingCT)

T, U, V — фиксированные генераторы, полученные хешированием в точку; их логарифмы относительно G и друг друга никто не знает. Это критично: если бы кто-то знал T = t·G, он мог бы «перекрашивать» одну компоненту в другую.

лист дерева (публичен) O I = Hp(O) C + r_o·T + r_i·U + r_c·G вход транзакции Õ Ĩ (+ R) C̃ без r — связь между левым и правым столбцом не видна

Что доказывается про эти точки

Транзакция содержит два доказательства, и они делят работу:

  1. Membership proof (внутри арифметической схемы над Helios/Selene) доказывает: существует лист (O, I, C) в дереве с корнем ρ, и существуют r_o, r_i, r_r_i, r_c, такие что опубликованные Õ, Ĩ, R, C̃ получены по формулам выше.
  2. SA+L (вне схемы, на Ed25519) доказывает: тратящий знает x, y такие, что Õ = x·G + (y + r_o)·T, и key image L = x·I — используя только опубликованные Õ, Ĩ, R.

Обратите внимание: membership proof не знает ничего о ключах траты, а SA+L ничего не знает о дереве. Это разделение позволяет, например, отдать построение membership proof другому устройству, не давая ему права тратить.

Почему это безопасно

  • Скрытие: r_o·T — случайная точка подгруппы, поэтому Õ распределена равномерно, как бы ни выглядел O. Сравнивать Õ с выходами бесполезно — это показывает инструмент.
  • Нельзя подделать лист: чтобы «снять краску» с выдуманной точки и попасть в настоящий лист, нужно решить дискретный логарифм между генераторами.
  • Нельзя подменить сумму: баланс проверяется по C̃, а membership proof гарантирует, что C̃ отличается от настоящего C листа только на кратное G — то есть сумма та же.
  • Нельзя потратить дважды: L = x·I зависит только от выхода, а не от r; при второй трате получится тот же L.