Range proof e Bulletproofs+
Dimostrare che un numero nascosto sta tra 0 e 2⁶⁴ senza rivelarlo
Ogni output dimostra che il suo importo v sta in [0, 2⁶⁴). Questo chiude la falla degli "importi negativi". Monero usa Bulletproofs+ (da agosto 2022): una sola prova aggregata per transazione, la cui dimensione cresce in modo logaritmico, ~600 byte per 2 output.
L'idea: scomporre il numero in bit
Un numero in [0, 2⁶⁴) è fatto di 64 bit: v = b₀·1 + b₁·2 + b₂·4 + … + b₆₃·2⁶³, con ogni bᵢ ∈ {0, 1}. Se dimostri (1) che ogni bᵢ è davvero 0 o 1 e (2) che la somma pesata dei bit è uguale a v, allora v è sicuramente nell'intervallo.
La condizione "è un bit" è algebrica: bᵢ·(bᵢ − 1) = 0. Il compito diventa dimostrare che un insieme di numeri nascosti soddisfa un insieme di equazioni senza rivelare i numeri.
Evoluzione in Monero
| Periodo | Schema | Dimensione (2 output) | Come funziona |
|---|---|---|---|
| 2017–2018 | Borromean | ~13 KB | Ogni bit è un commitment separato + una ring signature "questo è un commitment a 0 o a 2ⁱ". Dimensione lineare. |
| Ott 2018 – Ago 2022 | Bulletproofs | ~700 byte | Argomento del prodotto interno: dimensione logaritmica, più output aggregati in un'unica prova. |
| da Ago 2022 | Bulletproofs+ | ~600 byte | Variante migliorata (prodotto interno pesato): ancora più piccola e veloce. |
Il passaggio a Bulletproofs nel 2018 ha reso le transazioni circa 10 volte più piccole e ha ridotto le commissioni in proporzione. Uno degli aggiornamenti più evidenti nella storia di Monero.
Come funziona Bulletproofs (intuizione)
- Chi dimostra (il prover) si impegna sul vettore di bit
a_Le sul vettorea_R = a_L − 1con un unico commitment di Pedersen vettoriale. - Il verificatore (tramite un hash, con Fiat–Shamir) invia sfide casuali
y, z. Tutte le 64 condizioni "è un bit" e la condizione sulla "somma" vengono incollate in un'unica equazione di prodotto interno⟨l, r⟩ = t. Le sfide casuali garantiscono che non si possa falsificare l'equazione combinata senza soddisfare tutte quelle originali. - Un prodotto interno di vettori di lunghezza n si dimostra in modo ricorsivo: a ogni passo i vettori vengono "piegati a metà" con una nuova sfida, e dopo
log₂ npassi resta un solo numero per ciascuno. Ogni passo invia 2 punti: da qui la dimensione logaritmica.
Aggregazione: per m output i vettori hanno lunghezza 64·m, e la dimensione cresce solo di 2·log₂ m punti. Per questo Monero limita gli output per transazione a 16 e completa fino a una potenza di due.
Pro e contro
+
- Nessun trusted setup (a differenza degli zk-SNARK in Zcash Sprout/Sapling).
- Si basa solo sulla difficoltà del logaritmo discreto: la stessa ipotesi del resto di Monero.
- Compatto e aggregabile.
- Molte prove si possono verificare insieme (verifica in batch).
−
- La verifica è lineare nel numero di bit: una quota considerevole del tempo di verifica di un blocco.
- Non resistente ai computer quantistici: un computer quantistico romperebbe il vincolo di Pedersen (potrebbe stampare denaro), anche se l'occultamento resterebbe.
FCMP++ usa una generalizzazione della stessa tecnica, i Generalized Bulletproofs, per dimostrare un percorso nell'albero di tutti gli output. Capire Bulletproofs è una buona base per le prove di FCMP++.