Generalized Bulletproofs e divisori

Su cosa si regge la prova del percorso nell'albero, senza trusted setup

Cos'è un "circuito aritmetico"

Qualsiasi calcolo si può scomporre in passi elementari "moltiplica due numeri" e "somma con coefficienti" in un campo finito. Un insieme di tali passi è un circuito aritmetico. Una prova a conoscenza zero mostra "conosco valori per tutti i fili del circuito tali che tutte le equazioni siano soddisfatte" senza rivelare i valori.

In Bulletproofs il circuito è semplice e fisso: "questi 64 numeri sono bit, e sommati danno l'importo". In FCMP++ è più complesso: a ogni livello dell'albero bisogna verificare che il figlio scelto sia tra i figli del nodo e che il nodo sia calcolato correttamente a partire da essi.

Generalized Bulletproofs

I Bulletproofs ordinari ricevono in ingresso commitment di Pedersen separati. I Generalized Bulletproofs (Eagen, Kamp, Parker e altri) permettono di fornire al circuito commitment vettoriali: un solo punto fissa molti numeri insieme. È esattamente ciò che serve all'albero: l'"hash" di un nodo è un commitment vettoriale sulle coordinate dei suoi figli (vedi Curve Trees). Il circuito riceve il nodo in ingresso e può ragionare sul suo contenuto.

Stesse proprietà di Bulletproofs:

• nessun trusted setup;
• la dimensione della prova cresce in modo logaritmico con la dimensione del circuito;
• la verifica è lineare nella dimensione del circuito ma si presta bene al batch: verificare molte prove insieme costa meno che una per una.

Il problema: la moltiplicazione scalare dentro un circuito

La rerandomizzazione richiede di verificare nel circuito qualcosa come Õ = O + r_o·T. Moltiplicare un punto per uno scalare da 255 bit "di petto" significa centinaia di raddoppi e addizioni di punti, ciascuno con diverse moltiplicazioni nel campo. Sono migliaia di vincoli per operazione, e la prova sarebbe enorme.

Divisori: verificare invece di calcolare

L'idea di Liam Eagen ("Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity"): per assicurarsi che i punti P₁ … Pₙ sommino a zero non serve sommarli. Basta presentare una funzione razionale f sulla curva i cui zeri stiano esattamente in quei punti (il suo divisore) e verificare un'unica identità algebrica in un punto casuale (una sfida del verificatore).

La moltiplicazione r·T si scrive come somma Σ bᵢ·(2ⁱ·T) sui bit di r, cioè come somma di punti, e si verifica con un solo divisore. Il numero di vincoli scende di circa un ordine di grandezza.

Due circuiti, due curve

I livelli dell'albero si alternano tra Selene e Helios. L'aritmetica di ogni livello è naturale nel campo di una delle due curve, quindi la prova di appartenenza è composta da due Generalized Bulletproofs: uno su Selene (i livelli Selene e la verifica della rerandomizzazione della foglia, le cui coordinate sono elementi del campo di Ed25519), l'altro su Helios. Sono collegati tramite nodi rerandomizzati condivisi.

Dimensione e costo

La dimensione della prova dipende dalla profondità dell'albero e dall'ampiezza dei nodi. Con centinaia di milioni di output e nodi ampi decine di figli, la profondità è di pochi livelli. A grandi linee, un input FCMP++ occupa diversi kilobyte e la verifica costa un ordine di grandezza più di CLSAG; gli sviluppatori continuano a ottimizzare entrambi gli aspetti (verifica in batch, prove multi-input). Le cifre esatte sono nei rapporti di benchmark della release.