Loading...
Serie: Zcash from First Principles . Articolo 4 . Alberi di Merkle Pubblico: nuovi arrivati. Costruiamo a partire dall'Articolo 3 (hashing e commitment). Se sai cos'è un'impronta digitale e cos'è un commitment, sei pronto. Cosa porterai con te: un quadro intuitivo e corretto degli alberi di Merkle, di come provare l'appartenenza senza rivelare a quale elemento ti riferisci, ed esattamente di come tutto questo diventa l'albero dei commitment delle note di Zcash.
L'Articolo 0 ha descritto una "bacheca pubblica" che contiene ogni nota mai creata e che si limita a crescere. Ormai puoi intuire cosa vi è appuntato: i commitment (Articolo 3), le buste sigillate. Ma una bacheca reale ne conterrebbe centinaia di milioni. Come fa la rete a memorizzarli, a verificarli e a permetterti di provare che la tua busta è sulla bacheca senza indicarla? La risposta è una delle strutture più eleganti dell'informatica: l'albero di Merkle.
Due problemi compaiono nel momento in cui si ha una gigantesca lista pubblica di commitment.
Problema uno: integrità su larga scala. Se la lista ha 300 milioni di voci, come fa chiunque a confermare che nemmeno una sia stata segretamente alterata? Ricontrollare 300 milioni di elementi a ogni sguardo è impossibile.
Problema due: appartenenza privata. Per spendere una nota (Articolo 0), devi provare che il tuo commitment è realmente sulla bacheca. Ma se lo indichi ("è la voce numero 4.201.337!"), ti sei appena deanonimizzato. Devi provare "la mia busta è da qualche parte su questa bacheca" senza rivelare quale.
Un albero di Merkle risolve entrambi i problemi in un colpo solo. Comprime l'intera lista in un'unica impronta e ti permette di provare l'appartenenza con una prova minuscola che nasconde la posizione.
Immagina un tabellone a eliminazione di un torneo, ma invece di avanzare i giocatori, vengono combinate le impronte digitali.
La proprietà più importante in assoluto deriva direttamente dall'effetto valanga (Articolo 3):
La radice è un'impronta di tutto ciò che sta sotto di essa. Cambia una qualsiasi foglia, anche di un solo bit, e la sua impronta cambia, il che cambia il suo genitore, che cambia quel genitore, fino in cima. La radice cambia. Quindi un piccolo valore di radice certifica l'integrità dell'intera lista. Questo risolve il Problema uno.
Costruiamo l'albero a quattro foglie qui sopra con vere impronte SHA-256 sulle foglie A, B, C, D (i digest sono mostrati troncati per leggibilità):
hA = 559aead08264... hB = df7e70e50215...
hC = 6b23c0d5f35d... hD = 3f39d5c348e5...
hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...
ROOT = H(hAB , hCD) = 1b3faa3fcc5e...
Tutto si riduce a "fai l'hash di una cosa, poi fai l'hash di coppie di hash." Niente di più esotico dell'Articolo 3, disposto ad albero.
Ora il Problema due. Diciamo che vuoi provare che la foglia C è nell'albero, a qualcuno che conosce solo la radice. Non gli consegni l'intero albero. Gli consegni solo le impronte necessarie per risalire da C alla radice, chiamate percorso di autenticazione (o prova di Merkle):
Per provare che
Cè nell'albero, fornisci:
- il suo fratello
hD, e- il suo zio
hAB.
Il verificatore, conoscendo solo la radice, ricalcola la risalita:
step 1: H(hC , hD) = hCD (combine C with its sibling)
step 2: H(hAB , hCD) = ROOT? (combine with the uncle)
Calcolato per davvero: questo produce 1b3faa3fcc5e..., che corrisponde alla radice. La foglia è provata essere nell'albero.
Due cose rendono tutto questo potente:
n foglie ne fornisci solo circa log_2(n). Per un miliardo di foglie, sono all'incirca 30 hash, non un miliardo. La prova cresce a malapena anche quando l'albero esplode di dimensioni.Ora possiamo dire con precisione cos'è davvero la "bacheca pubblica" dell'Articolo 0:
L'albero dei commitment delle note è un albero di Merkle le cui foglie sono commitment di note. Ogni volta che una nota viene creata in qualsiasi parte del mondo, il suo commitment viene aggiunto come foglia successiva e la radice viene aggiornata.
Alcuni dettagli reali:
2^(32) (oltre quattro miliardi di) note.
L'albero prova che una nota esiste. Non impedisce di per sé di spendere la stessa nota due volte. Quel compito appartiene all'insieme dei nullifier dell'Articolo 0: una collezione separata di "gettoni di annullamento." Quando spendi, pubblichi il nullifier della nota e la rete rifiuta qualsiasi nullifier che abbia già visto.
Quindi le due strutture pubbliche svolgono ruoli complementari, e tenerle separate è esattamente ciò che recide il legame tra la nascita di una nota e la sua morte:
| Struttura | Domanda a cui risponde | Aggiornata quando |
|---|---|---|
| Albero dei commitment delle note | "Questa nota esiste?" | Una nota viene creata (commitment aggiunto) |
| Insieme dei nullifier | "Questa nota è già stata spesa?" | Una nota viene spesa (nullifier pubblicato) |
Semplificazioni, come al solito. I veri alberi di Merkle incrementali tengono traccia dei nodi di "frontiera" così che la radice possa aggiornarsi senza ricostruire tutto; la rete conserva una finestra di anchor recenti, non solo l'ultima, così che i portafogli non si rompano a ogni nuovo blocco; e le foglie vuote usano un valore di padding definito. Abbiamo inoltre disegnato alberi binari con ordinate potenze di due. Niente di tutto questo cambia l'intuizione: foglie di commitment, sottoposte ad hashing a coppie fino a un'unica radice, con brevi prove di appartenenza. La contabilità esatta tornerà nell'articolo sul protocollo.
| Termine | Significato in parole semplici |
|---|---|
| Merkle tree | Un albero di hash; le foglie sono impronte di dati, i genitori applicano l'hash ai propri figli |
| Leaf | Un nodo in fondo; in Zcash, un commitment di nota |
| Merkle root | L'unica impronta in cima che riassume l'intero albero |
| Authentication path / Merkle proof | Gli hash dei fratelli necessari a provare che una foglia è nell'albero |
| Incremental Merkle tree | Un albero di Merkle solo in aggiunta (le foglie vengono solo aggiunte) |
| Anchor | Una radice di Merkle a cui una spesa fa riferimento come "lo stato dell'albero contro cui sto provando" |
| Nullifier set | La collezione separata di marcatori-di-spesa che blocca le doppie spese |
Perché un albero e non semplicemente una lunga lista di hash? Una lista piatta ti costringerebbe a rivelare o elaborare ogni voce per provare l'appartenenza. Un albero ti dà prove di dimensione logaritmica e un'unica radice per l'integrità.
Il verificatore ha bisogno dell'intero albero? No. Il verificatore ha bisogno solo della radice più il tuo breve percorso di autenticazione. È tutto qui.
Perché proprio profondità 32? Limita l'albero a circa quattro miliardi di note, che è ampio margine, mantenendo al contempo la prova di appartenenza (e il suo costo in-circuito) di dimensione fissa e gestibile.
Se la radice cambia a ogni nuova nota, come fanno le vecchie prove a restare valide? La rete ricorda una finestra di radici recenti (anchor), così che una prova fatta contro un anchor leggermente più vecchio sia comunque verificabile. L'articolo sul protocollo rende tutto questo preciso.
Nel nostro albero a 4 foglie, supponi che un attaccante scambi segretamente la foglia C con un valore diverso ma lasci invariata la radice pubblicata. Cosa va storto per lui, e perché non può sistemarlo in silenzio? (Risposta sotto.)
Cambiare C cambia hC (effetto valanga), che cambia hCD = H(hC, hD), che cambia ROOT = H(hAB, hCD). Quindi la radice ricalcolata non corrisponde più alla radice pubblicata, e la manomissione viene rilevata. Per "sistemarlo in silenzio" dovrebbe trovare un C diverso che produca lo stesso hC, ovvero una collisione di hash, irrealizzabile per l'Articolo 3. L'integrità regge.
Articolo 5 . Prove a conoscenza zero: il crescendo. Abbiamo ora costruito note, commitment e l'albero, e continuiamo a dire "provato a conoscenza zero." L'Articolo 5 spiega finalmente come puoi provare che un'affermazione è vera, che la tua nota è nell'albero, che il tuo nullifier è corretto, che il denaro è bilanciato, senza rivelare nulla di tutto ciò.
Parte della serie Zcash from First Principles per ZecHub. Licenza CC BY-SA 4.0.