Ring signature

Come dimostrare "possiedo una di queste chiavi" senza dire quale

Prima: una semplice firma di Schnorr

Per capire i ring, vediamo prima come dimostrare la conoscenza di una chiave x per P = x·G:

1. Chi firma sceglie un α casuale e calcola α·G.
2. Calcola la sfida c = Hs(message ‖ α·G).
3. Calcola la risposta s = α − c·x. La firma è (c, s).
4. Il verificatore ricostruisce s·G + c·P = (α − cx)·G + c·x·G = α·G e controlla che Hs(message ‖ α·G) = c.

Senza conoscere x non si può trovare un s per un dato c: c dipende da α·G, che deve essere fissato prima di conoscere c.

L'idea del ring: chiudere la catena delle sfide

Ora abbiamo n chiavi pubbliche P₀ … Pₙ₋₁ e conosciamo la chiave di una sola, diciamo Pπ. Il trucco: ogni sfida si calcola dall'anello precedente, e la catena si chiude ad anello.

1. Nella posizione π della chiave reale, prendi un α casuale e calcola la sfida successiva: c_{π+1} = Hs(m ‖ α·G).
2. Per ogni chiave (estranea) successiva scegli un sᵢ casuale e calcola c_{i+1} = Hs(m ‖ sᵢ·G + cᵢ·Pᵢ). Fai il giro del ring.
3. Torna a π, conoscendo ora c_π. Perché il ring si chiuda serve s_π·G + c_π·P_π = α·G, cioè s_π = α − c_π·x. Questo si può calcolare solo conoscendo x.
4. Firma: (c₀, s₀, s₁, …, sₙ₋₁).

Il verificatore parte da c₀, percorre ogni anello con la stessa formula e controlla di essere tornato allo stesso c₀. Tutti gli anelli si somigliano: dalla firma non si capisce dove sia avvenuta la "chiusura".

Collegabilità: LSAG

Una ring signature semplice non impedisce che lo stesso output venga speso due volte in ring diversi. Per questo Monero usa una firma collegabile (linkable): chi firma pubblica una key image I = x·Hp(P_π) e in ogni anello dimostra in più che lo stesso x collega I e Hp(Pᵢ):

Due usi della stessa chiave producono la stessa I, e la rete rifiuta la seconda spesa.

MLSAG → CLSAG

In RingCT bisogna dimostrare non una ma due affermazioni per ogni membro del ring: la conoscenza della chiave dell'output e che la differenza dei commitment è un commitment a zero (vedi RingCT). All'inizio (2017) lo si faceva con MLSAG, in pratica due ring incollati insieme: due valori s per ogni membro del ring.

A ottobre 2020 (hard fork v13) è stato sostituito da CLSAG (Concise LSAG): le due chiavi in una posizione vengono fuse in una tramite una combinazione lineare casuale con coefficienti derivati da hash. Un solo s per membro del ring. La firma è diventata circa il 25% più piccola e più veloce da verificare.

Storia della dimensione del ring

Perché fissa? Se ognuno scegliesse la propria, una dimensione del ring non standard diventerebbe un'impronta del wallet.

Perché non 1000?

La dimensione di CLSAG e il tempo di verifica crescono in modo lineare con la dimensione del ring. Un ring da 1000 membri significa ~32 KB per input e una sincronizzazione dei nodi decine di volte più lenta. Sono stati studiati schemi con dimensione logaritmica (Triptych, Arcturus, Seraphis), ma alla fine Monero ha scelto l'opzione radicale: FCMP++, dove il "ring" è l'intera blockchain.