Tecnico › FCMP++

Rerandomizzazione degli input

Come spendere un output dell'albero senza mostrare quale

In breve

In FCMP++ un input di transazione non è un riferimento a un output ma una sua copia "riverniciata": a ogni punto dell'output viene aggiunto un multiplo casuale di un generatore separato. I punti risultanti sono indistinguibili da punti casuali, ma chi spende conosce la "vernice" e può dimostrare: (1) che togliendola si ottiene una foglia dell'albero, e (2) che conosce la chiave di quella foglia.

Perché rerandomizzare

Una prova di appartenenza dimostra l'affermazione "il punto X è una foglia dell'albero". Se pubblichiamo l'output O stesso, non resta nulla da nascondere: tutti vedono quale output viene speso. Se non pubblichiamo nulla, non c'è nulla a cui legare la key image e il commitment dell'importo. Serve una via di mezzo: pubblicare qualcosa di matematicamente legato all'output, in cui solo chi spende possa vedere il legame.

Questo trucco è la rerandomizzazione. In RingCT un trucco simile era lo pseudo-output C̃: lo stesso commitment dell'importo, ma con una nuova maschera. FCMP++ applica la stessa idea a ogni parte dell'output.

Di cosa è fatta una foglia

leaf = ( O.x, I.x, C.x ) coordinate x di tre punti Ed25519: la chiave dell'output O, il generatore della key image I = Hp(O), il commitment C

O e C arrivano direttamente dall'output sulla catena; I viene calcolato dal nodo quando aggiunge l'output all'albero. Nell'albero entrano solo le coordinate (numeri), non i punti stessi: così è più facile "hasharle" al livello successivo (vedi Curve Trees).

Le formule della rerandomizzazione

Chi spende sceglie quattro scalari casuali r_o, r_i, r_r_i, r_c e pubblica:

PubblicatoFormulaCosa nasconde
ÕO + r_o·Tquale chiave di output viene spesa
ĨI + r_i·Uil generatore della key image di quell'output
Rr_i·V + r_r_i·Tun commitment a r_i, necessario per collegare Ĩ alla key image
C̃C + r_c·Gquale commitment dell'importo viene speso (come lo pseudo-output di RingCT)

T, U, V sono generatori fissi ottenuti tramite hash a punto; nessuno conosce i loro logaritmi rispetto a G o tra loro. È fondamentale: se qualcuno conoscesse T = t·G, potrebbe "riverniciare" una componente nell'altra.

foglia dell'albero (pubblica) O I = Hp(O) C + r_o·T + r_i·U + r_c·G input della transazione Õ Ĩ (+ R) C̃ senza r, il legame tra la colonna sinistra e la destra è invisibile

Cosa si dimostra su questi punti

La transazione contiene due prove che si dividono il lavoro:

  1. La prova di appartenenza (in un circuito aritmetico su Helios/Selene) dimostra: esiste una foglia (O, I, C) nell'albero con radice ρ, ed esistono r_o, r_i, r_r_i, r_c tali che i valori pubblicati Õ, Ĩ, R, C̃ seguono le formule sopra.
  2. SA+L (fuori dal circuito, su Ed25519) dimostra: chi spende conosce x, y con Õ = x·G + (y + r_o)·T, e la key image è L = x·I, usando solo i valori pubblicati Õ, Ĩ, R.

Nota che la prova di appartenenza non sa nulla delle chiavi di spesa, e SA+L non sa nulla dell'albero. Questa separazione permette, per esempio, di delegare la prova di appartenenza a un altro dispositivo senza dargli il diritto di spendere.

Perché è sicuro

  • Occultamento: r_o·T è un punto casuale del sottogruppo, quindi Õ è distribuito uniformemente qualunque aspetto abbia O. Confrontare Õ con gli output è inutile: lo strumento lo mostra.
  • Niente foglie false: per "togliere la vernice" da un punto inventato e finire su una foglia reale bisognerebbe risolvere un logaritmo discreto tra generatori.
  • Niente scambio di importi: il bilancio si verifica su C̃, e la prova di appartenenza garantisce che C̃ differisce dal vero C della foglia solo per un multiplo di G: quindi l'importo è lo stesso.
  • Niente doppia spesa: L = x·I dipende solo dall'output, non da r; una seconda spesa produce la stessa L.