Curve Trees, Helios e Selene
Un albero di Merkle con punti al posto degli hash, in cui dimostrare un percorso richiede pochi kilobyte
Un Curve Tree è un albero di Merkle in cui l'"hash" di un genitore è un commitment di Pedersen vettoriale sulle coordinate dei figli. I livelli dell'albero si alternano tra due curve, Helios e Selene, che formano un ciclo: le coordinate dei punti di una curva sono scalari dell'altra. Questo rende economico dimostrare ogni livello del percorso.
Ripasso sugli alberi di Merkle
Un albero di Merkle calcola l'hash dei dati a coppie (o a gruppi), poi l'hash degli hash, fino a un'unica radice. Per dimostrare che un elemento è nell'albero si mostra il percorso: i fratelli a ogni livello. Il percorso ha lunghezza log n.
Ma noi dobbiamo dimostrare il percorso a conoscenza zero, senza mostrare né la foglia né i fratelli. Questo significa codificare il "calcolo di un hash" in un circuito aritmetico e dimostrare il circuito. Gli hash ordinari (Keccak, SHA) sono molto costosi in circuiti del genere: decine di migliaia di vincoli per hash.
L'idea dei Curve Trees
Usare come "hash" un commitment di Pedersen vettoriale:
È un buon hash per il nostro scopo (trovare una collisione è difficile quanto il logaritmo discreto), e in un circuito aritmetico è quasi gratuito, se i numeri xᵢ sono scalari della curva su cui vivono i Gᵢ.
Il problema: i figli sono punti sulla curva E₁, quindi le loro coordinate sono elementi del campo base di E₁. Per usarle come scalari serve una curva E₂ il cui campo degli scalari coincida con il campo base di E₁. Al livello successivo, il contrario. Una coppia del genere si chiama ciclo di curve.
Helios e Selene
Per Monero è stato scelto un ciclo speciale "ancorato" a Ed25519: le coordinate dei punti di Ed25519 stanno nel campo F_p, p = 2²⁵⁵ − 19, e una curva del ciclo (Selene) ha esattamente questo F_p come campo degli scalari. Così le foglie (coordinate di O, I, C su Ed25519) si possono "hashare" direttamente su Selene, poi le coordinate dei punti di Selene su Helios, e così via, alternando.
I nomi vengono dalle divinità greche del Sole (Helios) e della Luna (Selene): due curve che "orbitano" l'una attorno all'altra.
Come si dimostra il percorso
Per ogni livello chi dimostra non mostra il punto genitore stesso ma una sua rerandomizzazione (il punto più un multiplo casuale di un altro generatore), e dimostra in un circuito sulla curva corrispondente:
- "conosco i figli, uno dei quali è il punto rerandomizzato del livello precedente";
- "questi figli, combinati con i generatori, danno il genitore (rerandomizzato)".
Per verificare in modo efficiente le operazioni sulla curva all'interno del circuito si usano i divisori (la tecnica di Liam Eagen): invece di una moltiplicazione scalare passo dopo passo, si dimostra una proprietà di una funzione razionale sulla curva, cosa molto più economica. Vedi Generalized Bulletproofs e divisori.
Tutti i livelli su una curva sono dimostrati da un unico Generalized Bulletproof, quelli sull'altra da un secondo. Il risultato sono due prove la cui dimensione cresce con la profondità dell'albero, cioè in modo logaritmico con il numero di output.
Aggiornare l'albero
Quando un output supera il blocco di 10 blocchi, il nodo lo aggiunge all'albero e ricalcola il percorso fino alla radice. Un commitment vettoriale si aggiorna in modo incrementale: aggiungere un figlio significa sommare x·Gᵢ al genitore, senza ricalcolare gli altri. In caso di riorganizzazione della catena, le modifiche vengono annullate.
Si potrebbe dimostrare un percorso in un normale albero di Merkle con uno SNARK (come fa Zcash). Ma gli SNARK più diffusi richiedono o un trusted setup o ipotesi crittografiche che vanno oltre il logaritmo discreto. Curve Trees + Bulletproofs restano nel mondo del "solo logaritmo discreto, nessun setup" in cui Monero vive fin dall'inizio.