zk-SNARK: argomenti succinti non interattivi

Uno zk-SNARK (Zero-Knowledge Succinct Non-interactive ARgument of Knowledge) è una prova che soddisfa tre proprietà: (1) è zero-knowledge, (2) è succinta (prova molto piccola, verifica rapida indipendentemente dalle dimensioni del calcolo), (3) è non interattiva (un'unica stringa di prova).

I protocolli Sigma funzionano per asserzioni semplici (conoscenza del logaritmo discreto). Per calcoli complessi — «ho eseguito correttamente questa funzione su input privati» — serve un sistema di prove generico. Gli SNARK dimostrano calcoli arbitrari con un tempo di verifica O(1).

Il calcolo viene prima espresso come circuito aritmetico: un grafo aciclico diretto di porte di addizione e moltiplicazione su un campo finito. Esempio: dimostrare di conoscere x tale che x^3 + x + 5 = 35 senza rivelare x=3. Il circuito ha circa 5 porte.

Un circuito aritmetico viene convertito in R1CS: un insieme di vincoli (A*z)*(B*z) = C*z, dove z è un vettore contenente tutti i valori dei wire. Ogni porta di moltiplicazione diventa un vincolo. Il prover deve trovare z che soddisfi tutti i vincoli senza rivelare i wire privati.

R1CS viene convertito in un QAP: polinomi A(x), B(x), C(x) tali che A(x)*B(x)-C(x) sia divisibile per un polinomio obiettivo t(x) se e solo se i vincoli sono soddisfatti. Il prover dimostra di conoscere un quoziente polinomiale H(x) senza rivelare il witness.

Groth16 (2016) è lo SNARK generico più efficiente. Dopo un trusted setup (generazione del CRS), il prover produce una prova composta da 3 elementi del gruppo (~192 byte per BLS12-381). Verifica: 3 operazioni di pairing. La prova ha dimensione costante indipendentemente dalle dimensioni del circuito.

Groth16 richiede un trusted setup per ogni circuito: generare il toxic waste (un segreto casuale), calcolare la Common Reference String e poi distruggere il toxic waste. Se il segreto sopravvive, un avversario può falsificare le prove. Le cerimonie multipartitiche (Powers of Tau) distribuiscono la fiducia.

PLONK (2019) usa un trusted setup universale: un'unica cerimonia funziona per tutti i circuiti fino a un determinato limite di dimensione. Non serve un setup per ogni circuito. Compromesso: prove leggermente più grandi rispetto a Groth16. Utilizzato nelle implementazioni ZK-EVM (Polygon Hermez, zkSync Era).

Gli STARK (Scalable Transparent ARguments of Knowledge) non richiedono un trusted setup e usano funzioni hash (sicure anche post-quantum). Compromesso: prove più grandi (decine di KB rispetto a 200 byte). Utilizzati in StarkWare/StarkNet e nel linguaggio Cairo. Gli SNARK sono più piccoli; gli STARK sono resistenti ai computer quantistici.

Groth16 usa pairing bilineari: e: G1 × G2 → GT, dove e(a*P, b*Q) = e(P,Q)^{ab}. Questo consente di verificare identità polinomiali nell'esponente senza rivelare i valori. La curva BLS12-381 è ottimizzata per pairing Groth16 efficienti.

Tempo di generazione di una prova Groth16 per un circuito con 10^6-gate: circa 10 secondi su una CPU moderna. Verifica: ~1 ms. Questa asimmetria è intenzionale: il prover, che ha eseguito il calcolo pesante, svolge il lavoro; il verifier, cioè il nodo blockchain, svolge un lavoro quasi nullo.

Gli zk-SNARK dimostrano calcoli arbitrari con prove di dimensione costante. Pipeline: calcolo → circuito aritmetico → R1CS → QAP → prova SNARK. Groth16 è il più efficiente (trusted setup per ogni circuito); PLONK usa un setup universale. Prossimo argomento: applicazioni delle ZKP nella blockchain.