1. Introduzione
ZK-SNARK è un sistema di prova crittografica che consente a un'entità di dimostrare che qualcosa è vero senza rivelare altre informazioni.
Gli ZK-SNARK sono utili in molteplici applicazioni e campi, come blockchain e calcolo verificabile. Una notevole applicazione blockchain viene utilizzata in ZK-Rollups.
Gli ZK-Rollup sono blockchain di secondo livello costruiti sopra altre blockchain (come Ethereum) che utilizzano ZK-SNARK (o altri sistemi di prova crittografica) per dimostrare la validità delle transizioni di stato. Cioè, ogni volta che viene effettuato un nuovo aggiornamento della rete (viene aggiunto un nuovo batch di transazioni), viene calcolato un nuovo stato della rete e viene generata una prova della validità di questo stato. Il punto è che è necessaria una sola entità per generare questa prova e chiunque può quindi fidarsi della sua validità.
Le proprietà desiderate fornite da ZK-Rollups sono solitamente (i) scalabilità e/o (ii) protezione della privacy. Gli ZK-Rollup sono talvolta chiamati Rollup dell'efficacia quando è richiesta solo la scalabilità.
Per calcolare prove in ZK-Rollup progettati per estendere l'EVM di Ethereum, è possibile utilizzare ZK-EVM. In senso stretto, ZK-EVM è un insieme di programmi crittografici (circuiti) responsabili della generazione di prove a conoscenza zero (ZKP), sebbene a volte colloquialmente si riferisca anche allo ZK-Rollup universale compatibile con EVM nel suo insieme.
2.Definizione ZK-SNARK
Uno SNARK è una prova concisa che una certa affermazione è vera. Formalmente dimostra la conoscenza della traccia di esecuzione di un algoritmo che produce una soluzione corretta ad un determinato problema. Piuttosto, dimostra la conoscenza di valori non pubblici e non costanti che eseguono il tracciamento. Questi valori nel loro insieme sono spesso chiamati testimoni. Gli elementi del testimone, cioè le parti dell'input all'algoritmo, costituiscono testimoni indipendenti perché esistono prima dell'esecuzione dell'algoritmo e non sono determinati da altri elementi della traccia di esecuzione. Il valore pubblico non costante della traccia di esecuzione, che specifica l'istanza del problema che l'algoritmo risolve, è chiamato istruzione pubblica.
ZK-SNARK sta per Argomento di conoscenza succinta non interattiva a conoscenza zero.
S – Semplicità
Semplicità - la dimostrazione è "breve" e il tempo di verifica è "rapido":
Una prova "breve" significa che la dimensione della prova è sublineare, rispetto alla dimensione del testimone.
Un tempo di verifica "rapido" significa che il tempo di esecuzione del verificatore dovrebbe (i) essere sublineare nella dimensione del testimone e (ii) essere lineare nell'affermazione pubblica.
Ma in realtà, vogliamo che sia non solo "conciso" ma anche "livello logaritmico polinomiale".
Ciò significa che la dimensione della prova e il tempo di verifica sono quasi indipendenti dalla dimensione del testimone.
Dimostrare che la dimensione di π non dovrebbe crescere più velocemente di alcune volte costanti il quadrato del logaritmo della dimensione del testimone w (per w sufficientemente grande):
La dimensione della prova dipende dallo specifico protocollo ZK-SNARK. Per Plonky2 è O(log^2(|w|)), ma questo è il caso "peggiore". Ad esempio, per i classici PLONK e Groth16, la dimensione della dimostrazione è O(1), che è una costante.
Il tempo di verifica t_v non dovrebbe essere superiore a qualche volta costante il quadrato del logaritmo del testimone w, e lineare nella dimensione della dichiarazione pubblica x (x e w sono abbastanza grandi quando solo uno di essi cambia dimensione).
N - Non interattivo: la generazione della prova avviene senza ricevere alcun dato dal verificatore.
ARK - Prova della conoscenza - Simile alle dimostrazioni regolari, ma il suono vale solo contro dimostratori limitati polinomialmente, mentre nelle dimostrazioni il suono vale contro dimostratori computazionalmente illimitati. Parleremo del concetto di suono nel prossimo paragrafo.
ZK - Zero Knowledge - Nessuna rivelazione di testimoni.
3. Proprietà degli ZK-SNARK
Gli ZK-SNARK hanno tre proprietà principali, come descritto di seguito:
Completezza: se il dimostratore conosce la corretta traiettoria di esecuzione dell'algoritmo, allora il verificatore deve credere che il dimostratore abbia questa conoscenza.
Solidità della conoscenza: a meno che il dimostratore non conosca effettivamente la traiettoria di esecuzione corretta, non può convincere il verificatore di conoscerla, ma c'è una probabilità molto piccola.
Conoscenza zero: il verificatore non sa nulla della traiettoria di esecuzione tranne che è corretta.
4. Sistema di prova PLONKish ZK-SNARK
4.1 Introduzione ai PLONKish ZK-SNARK e alle loro funzioni
Per essere applicato ad un determinato algoritmo, il sistema di dimostrazione ZK-SNARK necessita di conoscere il sistema di equazioni sul campo finito. Queste equazioni descrivono la relazione tra i valori nella tabella delle traiettorie di esecuzione dell'algoritmo (the struttura dati che memorizza la traiettoria di esecuzione) per garantire che il calcolo sia Integrità. Il linguaggio utilizzato per esprimere questo sistema di equazioni (chiamato anche sistema di vincoli) è chiamato aritmetica.
Il sistema di dimostrazione PLONKish ZK-SNARK utilizza l'aritmetica con una potenza espressiva maggiore rispetto ai sistemi di dimostrazione più vecchi. Il primo ci consente di utilizzare equazioni di sistemi di vincolo di forma polinomiale arbitraria sulle variabili di vincolo, mentre per i sistemi di dimostrazione più vecchi (cioè sistemi basati su R1CS) queste equazioni erano sotto forma di polinomi lineari e quadratici. Questa caratteristica fa sì che il sistema di prova PLONKish ZK-SNARK abbia un impatto positivo sull'efficienza computazionale del prover e ne facilita l'applicazione a vari algoritmi. Pertanto, negli ultimi anni sono apparsi molti sistemi di prova PLONKish ZK-SNARK, come il classico PLONK, Halo2, Kimchi, Plonky2, HyperPlonk, ecc.
In Taiko utilizziamo una variante del sistema di prova Halo2 basato sullo schema di impegno polinomiale KZG.
Il sistema di prova PLONKish ZK-SNARK è costituito da tre componenti:
4.2 Piano degli impegni
Lo schema della promessa consente a un committer di pubblicare un valore, chiamato promessa, che vincola il committer a un messaggio senza rivelare il messaggio stesso. Il committente può quindi aprire il commit ed esporre il messaggio impegnato, o parte di esso, al verificatore, che può verificare se le informazioni esposte sono coerenti con il commit.
Diversi autori descrivono un diverso numero di algoritmi che compongono uno schema di impegno. Dovremmo però menzionare almeno quattro di questi algoritmi:
Setup: prende alcuni parametri iniziali come input e genera parametri di setup. Le impostazioni specificano (i) a cosa ci impegniamo (ad esempio, per lo schema di impegno del polinomio unario, specifichiamo il dominio dei coefficienti e il grado massimo del polinomio a cui ci impegniamo) e (ii) il livello di sicurezza in bit. Possiamo semplicemente definire il livello di sicurezza come segue: se occorre O(2^n) tempo per violare un sistema di crittografia, allora il sistema di crittografia avrà un livello di sicurezza di n bit.
Promessa: una promessa che genera messaggi in base a parametri impostati.
Apertura parziale: genera una prova di apertura parziale specifica per una parte selezionata del messaggio (ad esempio, il valore di un polinomio unario impegnato per alcuni parametri), oltre all'impostazione dei parametri.
Validazione: utilizzare un'attestazione parzialmente aperta e impostare parametri per verificare se le informazioni esposte dal prover sono la parte specificata del messaggio corrispondente all'impegno specificato.
*Per alcuni schemi di commit, gli algoritmi "setup" e "open" potrebbero non esistere (ad esempio, quando si utilizza una funzione hash per impegnare valori di grandi dimensioni).
Il piano di impegno dovrebbe avere le seguenti caratteristiche:
Vincolo: una volta che il prover si impegna in un messaggio specifico, sarà vincolato al messaggio a cui si è impegnato;
Nascondere: promessa di non rivelare alcuna informazione sul messaggio. L'occultamento può essere perfetto, ovvero una prova parzialmente aperta non rivela alcuna informazione sulla parte non interrogata del messaggio (ad es. impegno KZG), o non perfetto, ovvero una prova parzialmente aperta rivela alcune parti delle suddette informazioni (ad es. impegno polinomiale).
Gli schemi di impegno possono essere suddivisi in diverse tipologie in base all'oggetto target: impegno a elemento singolo; impegno vettoriale polinomiale;
Gli schemi di impegno polinomiale sono l'unico tipo utilizzato direttamente nel sistema di dimostrazione PLONKish ZK-SNARK. Per i sistemi di dimostrazione di cui sopra (come il classico PLONK, Halo2, Kimchi, Plonky2, ecc.), lo schema di impegno polinomiale univariato è molto importante. Tuttavia, ora ci sono alcuni nuovi metodi PLONKish ZK-SNARK basati su schemi di impegno polinomiale multilineare (ad esempio HyperPlonk).
4.3 Prova Oracle interattiva
Una prova oracolare interattiva è una prova interattiva in cui il verificatore ha "accesso all'oracolo" per ottenere i messaggi del prover, può interrogarli in modo probabilistico e non ha bisogno di leggere i messaggi dell'intero prover.
4.4 Euristica Fiat-Shamir
L'euristica Fiat-Shamir fornisce un modo per trasformare argomenti interattivi (moneta pubblica) in argomenti non interattivi. Intuitivamente, l'idea è quella di sostituire la sfida casuale del validatore con l'hash del messaggio precedente, ma le specifiche non sono generalmente specificate.
*Il Public Coin Protocol è un protocollo in cui i validatori inviano solo elementi casuali.
4.5 Principio di funzionamento del sistema di prova ZK-SNARK stile PLONK
Nel sistema di prova ZK-SNARK, per dimostrare la conoscenza del testimone viene utilizzato un metodo di prova Oracle interattivo modificato, che utilizza impegni polinomiali per fornire accesso Oracle al messaggio del prover e lo rende privo di interazione attraverso l'euristica Fiat-Shamir. In questa sezione spiegheremo in dettaglio il costruttore indicato.
Ricordiamo che l'applicazione del sistema di dimostrazione ZK-SNARK a un algoritmo richiede la costruzione di un sistema di vincoli corrispondente. Per poterlo costruire, definiamo la struttura della tabella delle tracce di esecuzione dell'algoritmo e i valori costanti in essa contenuti. Usiamo il termine "circuito" per riferirci alla struttura complessa di una tabella di traccia di esecuzione popolata solo con costanti e il corrispondente sistema di vincoli. Per generare una dimostrazione ZK-SNARK per un'istanza di esecuzione di un algoritmo, dobbiamo sintetizzare un'istanza di circuito che sia un'istanza corrispondente della tabella di traccia del circuito e di esecuzione dell'algoritmo (ovvero, una tabella che specifica costanti, testimoni, e valori della dichiarazione pubblica) combinazione.
Consideriamo la struttura della tabella di tracciamento utilizzata da un sistema di prova ZK-SNARK in stile PLONK. Tutte le colonne in tale tabella appartengono a uno dei tre tipi, che denominiamo in base alla terminologia utilizzata in Halo2 e descriviamo come segue:
Colonne fisse: le loro celle contengono costanti dalla tabella di traccia dell'esecuzione;
Colonna Istanza: utilizzata per archiviare i valori delle dichiarazioni pubbliche;
Colonna dei suggerimenti: dove vengono archiviati tutti i dati dei testimoni (compresi i valori dei testimoni indipendenti e i risultati segreti calcolati).
Volendo riassumere, notiamo quanto segue:
Tabella della traccia di esecuzione (tipo PLONKish) = colonne fisse + colonne di istanza + colonne di suggerimenti; circuito = tabella di traccia dell'esecuzione contenente solo costanti + sistema di vincoli; circuito + testimoni nella sua tabella + dichiarazioni pubbliche nella sua tabella; dichiarazione pubblica, valore testimone indipendente) → Istanza del circuito Applicare il sistema di prova ZK-SNARK a un determinato algoritmo = descrivere il circuito + definire il processo di sintesi.
Perché il termine "circuito" è ampiamente utilizzato in questo contesto? Inizialmente, quando erano disponibili solo i sistemi di prova ZK-SNARK basati su R1CS, era conveniente rappresentare il sistema di vincoli sotto forma di un circuito aritmetico, il cui output deve essere zero. Riteniamo che nel contesto di PLONKish SNARKs il termine "circuito" sia utilizzato per ragioni storiche. Ad ogni modo, consideriamo brevemente il circuito aritmetico utilizzato per le versioni precedenti di ZK-SNARK.
Il circuito aritmetico per gli SNARK basati su R1CS definisce un polinomio di n variabili su un campo finito e ha uno schema di valutazione. Inizialmente, è rappresentato come un grafico aciclico diretto (DAG):
include:
Input pubblico x, utilizzato per specificare il valore della dichiarazione pubblica;
Ingresso segreto w, utilizzato per specificare il valore del testimone indipendente;
Porte aritmetiche utilizzate per specificare addizione e moltiplicazione su campi finiti.
Consideriamo un esempio di circuito aritmetico nel campo dei numeri razionali.
Partiamo dal basso e lavoriamo con le porte più basse del diagramma, ovvero (2 x 4 = 8) e (4 + 11 = 15), salvando questi valori come valori intermedi;
Successivamente saliamo di una riga (alla seconda riga) e calcoliamo la somma dei due valori intermedi (che abbiamo ottenuto nella fase precedente), ovvero (8 + 15 = 23);
Dato che abbiamo solo tre porte e le abbiamo attraversate tutte, 23 è il nostro risultato finale.
Dopo che il sistema di prova PLONKish ZK-SNARK ha sintetizzato l'istanza del circuito, le colonne di ciascuna tabella di traccia di esecuzione dell'istanza vengono codificate come polinomi su campi finiti nel modo seguente. Supponiamo che C_j(x) sia un polinomio che descrive la colonna j e ω sia una radice primitiva 2^k-esima, dove k viene scelto in modo tale che 2^k sia leggermente più grande dell'altezza iniziale dell'istanza della tabella. L'istanza della tabella viene popolata con righe casuali (solo con celle diverse da zero nelle colonne suggerite) per contenere 2^k righe e C_j(ω^i) è impostato sul valore della i-esima riga della j-esima colonna dell'istanza della tabella specificata. Il ruolo del riempimento per gli attributi a conoscenza zero verrà spiegato più avanti.
L'affermazione "ω è una radice primitiva 2^k-esimo" significa che ω^(2^k) = 1, e abbiamo ω^t ≠ 1 per qualsiasi intero positivo t inferiore a 2^k.
Il sistema di vincoli viene convertito in forma di equazione polinomiale sostituendo le variabili in esso contenute con i corrispondenti polinomi ottenuti dai polinomi di colonna, sostituendo "x volte ω elevato a una certa potenza" al posto di x.
Ad esempio, consideriamo l'equazione del sistema di vincoli s(i) * (a(i) * b(i) - c(i+1)) = 0. Ciò significa che se s(i) è diverso da zero, allora a(i) * b(i) deve essere uguale a c(i+1). Qui a, b e c sono le colonne suggerite, s è la colonna fissa e i è il numero di riga corrente.
Questo vincolo può essere applicato a tutte le 2^k righe come segue. Siano S(x), A(x), B(x) e C(x) polinomi nelle colonne a, b, c e s rispettivamente. Ci auguriamo pertanto:
Ciò significa che tutti gli elementi di questo insieme devono essere radici di S(x) * (A(x) * B(x) - C(x * ω)). Pertanto, questo polinomio deve essere divisibile per:
Perché ω è una radice primitiva di ordine 2^k.
Z(x) = x^(2^k) - 1 è chiamato "polinomio evanescente" perché è 0 per tutti gli x che sono elementi del gruppo moltiplicativo ciclico generato da ω. Pertanto, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 significa che i vincoli di cui sopra valgono per tutte le 2^k righe.
Supponiamo che P_0(x), P_1(x), ... , P_m(x) siano vincoli applicati a tutte le 2^k righe e siano coerenti con il polinomio S(x) * (A(x) * B(x) considerato sopra ) - C(x * ω)) ha una forma simile. Se α viene scelto casualmente dal verificatore dal campo finito, allora
Ciò significa che con una probabilità estremamente elevata tutti questi vincoli sono soddisfatti per tutte le 2^k righe. Questa equazione significa che possiamo trovare un polinomio quoziente T(x) tale che
Pertanto, affinché il verificatore creda che il prover conosca il contenuto della tabella della traccia di esecuzione che soddisfa tutti gli m vincoli con una probabilità molto alta, è sufficiente dimostrare che per un α selezionato casualmente, il prover ha le occorrenze P_0 (x), P_1(x ),..., i polinomi di colonna suggeriti e i polinomi di quoziente T(x) in P_m(x) soddisfano questa equazione polinomiale. Il verificatore può farlo chiedendo al dimostratore di trovare il valore di un dato polinomio in un punto scelto casualmente dal verificatore tra i punti non radice ζ di Z(x), e di valutare entrambi i lati di quell'equazione in quel punto ζ Credo che il dimostratore probabilmente conosca questi polinomi. Questo metodo può essere dimostrato dal lemma di Schwartz-Zippel.
Per rendere la generazione della prova non interattiva, tutti i valori casuali generati dal verificatore nella versione interattiva dovrebbero essere ottenuti utilizzando l'euristica Fiat-Shamir.
Per vincolare il prover al suo polinomio di proposta e al polinomio quoziente T(x), viene utilizzato uno schema di impegno polinomiale. Il dimostratore assume impegni su questi polinomi, apre questi impegni su ζ (o su ζ * ω^q se qualche vincolo influisce sulle righe i e i + q) e crea una dimostrazione che include (I) questi impegni, (II) Il valore del polinomio in ζ (o sopra ζ * ω^q se necessario) e (III) la corrispondente dimostrazione aperta. In realtà, per rendere la dimostrazione più breve, utilizzare l'apertura multipla, ovvero generare una piccola dimostrazione per i valori di tutti i punti del polinomio. Pertanto la dimostrazione è concisa.
Per soddisfare la proprietà di conoscenza zero, righe selezionate casualmente dal prover vengono aggiunte all'istanza della tabella di traccia di esecuzione, rendendo la sua altezza pari a 2^k righe. Queste righe hanno solo celle diverse da zero nella colonna dei suggerimenti perché solo la colonna dei suggerimenti contiene i dati che vogliamo nascondere. Fatelo prima di costruire i polinomi della colonna della proposta in modo che il numero di coppie di "valori di parametro" rivelate durante il periodo di apertura dell'impegno sia inferiore al numero di coppie aggiunte casualmente per ciascun polinomio. Pertanto, per ciascun polinomio della colonna della proposta, la quantità di informazioni necessarie per recuperarlo dopo l'apertura dell'impegno è maggiore della quantità di informazioni del testimone. Questa situazione si traduce in una conoscenza zero.
Durante la fase di preelaborazione, tutte le istanze del circuito di esecuzione eseguono alcuni degli stessi calcoli, inclusa l'impostazione e il calcolo di polinomi di colonna fissi e i loro impegni per lo schema di impegno polinomiale. La porzione di dati prodotta da questi calcoli viene utilizzata dal verificatore ed è spesso chiamata chiave di verifica. Allo stesso modo, può essere definito il concetto di chiave di prova. Lo schema di impegno polinomiale sottostante determina se le impostazioni di attendibilità vengono effettuate durante la fase di preelaborazione.
