Vitalik Buterin tramite il Blog di Vitalik Buterin

Questo è uno specchio del post su https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

Questa è la terza parte di una serie di articoli che spiegano come funziona la tecnologia alla base di zk-SNARKs; gli articoli precedenti su programmi di aritmetica quadratica ed accoppiamenti di curve ellittiche sono una lettura obbligatoria e questo articolo presuppone la conoscenza di entrambi i concetti. Si presuppone anche una conoscenza di base di cosa sono gli zk-SNARK e cosa fanno. Guarda anche L'articolo di Christian Reitwiessner qui per un'altra introduzione tecnica.

Negli articoli precedenti abbiamo introdotto il programma di aritmetica quadratica, un modo di rappresentare qualsiasi problema computazionale con un'equazione polinomiale che è molto più suscettibile a varie forme di inganno matematico. Abbiamo anche introdotto gli accoppiamenti di curve ellittiche, che consentono una forma molto limitata di crittografia omomorfica unidirezionale che consente di eseguire il controllo dell'uguaglianza. Ora inizieremo da dove ci eravamo fermati e utilizzeremo gli accoppiamenti di curve ellittiche, insieme ad alcuni altri trucchi matematici, per consentire a un sperimentatore di dimostrare di conoscere una soluzione per un particolare QAP senza rivelare nient'altro sulla soluzione reale.

Questo articolo si concentrerà sul Protocollo Pinocchio di Parno, Gentry, Howell e Raykova del 2013 (spesso chiamato PGHR13); ci sono alcune variazioni sul meccanismo di base, quindi uno schema zk-SNARK implementato nella pratica potrebbe funzionare in modo leggermente diverso, ma i principi di base rimarranno in generale gli stessi.

Per cominciare, entriamo nel presupposto crittografico chiave alla base della sicurezza del meccanismo che utilizzeremo: il *conoscenza dell'esponente*presupposto.

Fondamentalmente, se ottieni una coppia di punti � e �, dove �⋅�=�, e ottieni un punto �, allora non è possibile ottenere �⋅� a meno che � non sia “derivato” da � in qualche modo che conosci. Ciò può sembrare intuitivamente ovvio, ma in realtà questo presupposto non può essere derivato da nessun altro presupposto (ad esempio, durezza logaritmica discreta) che usiamo solitamente quando dimostriamo la sicurezza dei protocolli basati su curve ellittiche, e quindi zk-SNARK in effetti si basa su un approccio in qualche modo fondamenta più traballanti rispetto alla crittografia a curva ellittica più in generale, sebbene sia ancora abbastanza robusta da essere d'accordo con la maggior parte dei crittografi.

Ora, vediamo come può essere utilizzato. Supponiamo che una coppia di punti (�,�) cada dal cielo, dove �⋅�=�, ma nessuno sa quale sia il valore di �. Ora, supponiamo che io crei una coppia di punti (�,�) dove �⋅�=�. Quindi, l'ipotesi KoE implica che l'unico modo in cui avrei potuto ottenere quella coppia di punti era prendere � e � e moltiplicare entrambi per un fattore r che conosco personalmente. Nota anche che grazie alla magia degli accoppiamenti di curve ellittiche, controllando che �=�⋅� in realtà non richiede di saperlo � – invece puoi semplicemente verificare se �(�,�)=�(�,�).

Facciamo qualcosa di più interessante. Supponiamo di avere dieci coppie di punti che cadono dal cielo: (�1,�1),(�2,�2)…(�10,�10). In tutti i casi, ��⋅�=��. Supponiamo che io ti fornisca quindi una coppia di punti (�,�) dove �⋅�=�. Cosa sai adesso? Sai che � è una combinazione lineare �1⋅�1+�2⋅�2+...+�10⋅�10, di cui conosco i coefficienti �1,�2...�10. Cioè, l’unico modo per arrivare a tale coppia di punti (�,�) è prendere alcuni multipli di �1,�2…�10 e sommarli insieme, e fare lo stesso calcolo con �1,�2… �10.

Tieni presente che, dato un insieme specifico di �1...�10 punti per il quale potresti voler controllare le combinazioni lineari, non puoi effettivamente creare i relativi punti �1...�10 senza sapere cosa sia �, e se sai cosa � allora puoi creare una coppia (�,�) dove �⋅�=� per qualunque � tu voglia, senza preoccuparti di creare una combinazione lineare. Quindi, affinché funzioni, è assolutamente imperativo che chiunque crei quei punti sia affidabile e li elimini effettivamente, una volta creati i dieci punti. Da qui deriva il concetto di “configurazione affidabile”..

Si ricordi che la soluzione di un QAP è un insieme di polinomi (�,�,�) tali che �(�)⋅�(�)−�(�)=�(�)⋅�(�), dove:

• � è una combinazione lineare di un insieme di polinomi {�1…��}
• � è la combinazione lineare di {�1…��} con gli stessi coefficienti
• � è una combinazione lineare di {�1…��} con gli stessi coefficienti

Gli insiemi {�1…��},{�1…��} e {�1…��} e il polinomio � fanno parte della formulazione del problema.

Tuttavia, nella maggior parte dei casi reali, �,� e � sono estremamente grandi; per qualcosa con molte migliaia di porte circuitali come una funzione hash, i polinomi (e i fattori per le combinazioni lineari) possono avere molte migliaia di termini. Quindi, invece di chiedere al dimostratore di fornire direttamente le combinazioni lineari, useremo il trucco che abbiamo introdotto sopra per far sì che il dimostratore dimostri che sta fornendo qualcosa che è una combinazione lineare, ma senza rivelare nient'altro.

Potresti aver notato che il trucco sopra funziona su punti di curve ellittiche, non su polinomi. Quindi, ciò che realmente accade è che aggiungiamo i seguenti valori alla configurazione attendibile:

• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...

Puoi pensare a t come a un "punto segreto" in cui viene valutato il polinomio. � è un “generatore” (un punto casuale della curva ellittica specificato come parte del protocollo) e �,��,�� e �� sono “rifiuti tossici”, numeri che devono assolutamente essere cancellati a tutti i costi, altrimenti chi li avrà potrà fare prove false. Ora, se qualcuno ti dà una coppia di punti �, � tale che �⋅��=� (promemoria: non abbiamo bisogno di �� per verificarlo, poiché possiamo fare un controllo di abbinamento), allora sai che quello che che ti stanno dando è una combinazione lineare di �� polinomi valutati in ��.

Quindi fin qui il prover deve dare:

• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��

Si noti che il dimostratore in realtà non ha bisogno di sapere (e non dovrebbe sapere!) �,��,�� o �� per calcolare questi valori; piuttosto, il prover dovrebbe essere in grado di calcolare questi valori solo dai punti che stiamo aggiungendo all'impostazione attendibile.

Il passo successivo è assicurarsi che tutte e tre le combinazioni lineari abbiano gli stessi coefficienti. Possiamo farlo aggiungendo un altro insieme di valori all'impostazione attendibile: �⋅(��(�)+��(�)+��(�))⋅�, dove � è un altro numero che dovrebbe essere considerato “tossico” rifiuti" e scartati non appena la configurazione attendibile è stata completata. Possiamo quindi chiedere al prover di creare una combinazione lineare con questi valori con gli stessi coefficienti e utilizzare lo stesso trucco di abbinamento di cui sopra per verificare che questo valore corrisponda al �+�+� fornito.

Infine, dobbiamo dimostrare che �⋅�−�=�⋅�. Lo facciamo ancora una volta con un controllo di accoppiamento:

�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))

Dove �ℎ=�⋅�(�). Se la connessione tra questa equazione e �⋅�−�=�⋅� non ha senso per te, torna indietro e leggi la articolo sugli accoppiamenti.

Abbiamo visto sopra come convertire �,� e � in punti di curva ellittica; � è solo il generatore (cioè il punto della curva ellittica equivalente al numero uno). Possiamo aggiungere �⋅�(�) alla configurazione attendibile. � è più difficile; � è solo un polinomio e prevediamo con molto poco anticipo quali saranno i suoi coefficienti per ogni singola soluzione QAP. Pertanto, dobbiamo aggiungere ancora più dati alla configurazione attendibile; nello specifico la sequenza:

�,�⋅�,�⋅�2,�⋅�3,�⋅�4….

Nella configurazione attendibile di Zcash, la sequenza qui arriva fino a circa 2 milioni; questo è il numero di potenze di � necessarie per assicurarti di essere sempre in grado di calcolare �(�), almeno per l'istanza QAP specifica a cui tengono. E con ciò, il sperimentatore può fornire tutte le informazioni affinché il verificatore possa effettuare il controllo finale.

C'è un altro dettaglio di cui dobbiamo discutere. Nella maggior parte dei casi non vogliamo solo dimostrare in astratto che esiste una soluzione per qualche problema specifico; piuttosto, vogliamo dimostrare la correttezza di qualche soluzione specifica (ad esempio, dimostrare che se prendi la parola "mucca" e la sottoponi a SHA3 un milione di volte, il risultato finale inizia con 0x73064fe5), o che una soluzione esiste se limiti alcuni dei parametri. Ad esempio, in un'istanza di criptovaluta in cui gli importi delle transazioni e i saldi dei conti sono crittografati, vuoi dimostrare di conoscere una chiave di decrittazione k tale che:

1. decrypt(old_balance, k) >= decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)

Il cifrato old_balance, tx_value ed new_balance dovrebbero essere specificati pubblicamente, poiché questi sono i valori specifici che stiamo cercando di verificare in quel particolare momento; solo la chiave di decrittazione dovrebbe essere nascosta. Sono necessarie alcune lievi modifiche al protocollo per creare una “chiave di verifica personalizzata” che corrisponda ad alcune restrizioni specifiche sugli input.

Adesso facciamo un passo indietro. Prima di tutto, ecco l'algoritmo di verifica nella sua interezza, per gentile concessione di Ben Sasson, Tromer, Virza e Chiesa:

La prima riga riguarda la parametrizzazione; in sostanza, puoi pensare alla sua funzione come quella di creare una "chiave di verifica personalizzata" per l'istanza specifica del problema dove sono specificati alcuni argomenti. La seconda riga è il controllo della combinazione lineare per �,� e �; la terza riga è la verifica che le combinazioni lineari abbiano gli stessi coefficienti, e la quarta riga è la verifica del prodotto �⋅�−�=�⋅�.

Complessivamente, il processo di verifica consiste in alcune moltiplicazioni di curve ellittiche (una per ciascuna variabile di input "pubblica") e cinque controlli di accoppiamento, uno dei quali include un'ulteriore moltiplicazione di accoppiamento. La dimostrazione contiene otto punti della curva ellittica: una coppia di punti ciascuno per �(�),�(�) e �(�), un punto �� per �⋅(�(�)+�(�)+�(� )) e un punto �ℎ per �(�). Sette di questi punti sono sulla curva �� (32 byte ciascuno, poiché è possibile comprimere la coordinata �� in un singolo bit) e nell'implementazione di Zcash un punto (��) è sulla curva attorcigliata in ��2 (64 byte), quindi la dimensione totale della prova è ~288 byte.

Le due parti computazionalmente più difficili della creazione di una dimostrazione sono:

• Dividendo (�⋅�−�)/� per ottenere � (algoritmi basati su Trasformata di Fourier veloce può farlo in tempo subquadratico, ma è comunque piuttosto impegnativo dal punto di vista computazionale)
• Effettuare le moltiplicazioni e le addizioni della curva ellittica per creare i valori �(�),�(�),�(�) e �(�) e le loro coppie corrispondenti

Il motivo fondamentale per cui creare una dimostrazione è così difficile è il fatto che quella che era una singola porta logica binaria nel calcolo originale si trasforma in un'operazione che deve essere elaborata crittograficamente attraverso operazioni su curva ellittica se ne stiamo ricavando una dimostrazione a conoscenza zero . Questo fatto, insieme alla superlinearità delle trasformate veloci di Fourier, significa che la creazione della prova richiede circa 20–40 secondi per una transazione Zcash.

Un’altra domanda molto importante è: possiamo provare a rendere la configurazione affidabile un po’… meno esigente in termini di fiducia? Sfortunatamente non possiamo renderlo completamente trustless; l’ipotesi KoE stessa preclude la creazione di coppie indipendenti (��,��⋅�) senza sapere cosa sia �. Tuttavia, possiamo aumentare notevolmente la sicurezza utilizzando il calcolo multipartitico "di" - ovvero costruendo la configurazione di fiducia tra le parti in modo tale che finché almeno uno dei partecipanti ha eliminato i propri rifiuti tossici, allora sei a posto. .

Per avere un'idea di come eseguire questa operazione, ecco un semplice algoritmo per prendere un set esistente (�,�⋅�,�⋅�2,�⋅�3...) e "aggiungervi" il proprio segreto in modo che tu abbia bisogno sia del tuo segreto che del segreto precedente (o della serie precedente di segreti) per imbrogliare.

Il set di output è semplicemente:

�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…

Nota che puoi produrre questo set conoscendo solo il set originale e i suoi componenti, e il nuovo set funziona allo stesso modo del vecchio set, tranne che ora usi �⋅� come "rifiuto tossico" invece di �. Finché tu e la persona (o le persone) che hanno creato il set precedente non riuscite a eliminare i vostri rifiuti tossici e successivamente non colludete, il set è “sicuro”.

Fare questo per la configurazione attendibile completa è un po’ più difficile, poiché sono coinvolti diversi valori e l’algoritmo deve essere eseguito tra le parti in diversi round. Si tratta di un'area di ricerca attiva per vedere se l'algoritmo di calcolo multipartitico può essere ulteriormente semplificato e fatto in modo da richiedere meno cicli o reso più parallelizzabile, poiché più si può fare, più parti diventa possibile includere nella procedura di configurazione attendibile. . È ragionevole capire perché una configurazione fidata tra sei partecipanti che si conoscono e lavorano insieme potrebbe mettere a disagio alcune persone, ma una configurazione fidata con migliaia di partecipanti sarebbe quasi indistinguibile dall'assenza totale di fiducia - e se sei davvero paranoico , puoi entrare e partecipare tu stesso alla procedura di configurazione ed essere sicuro di aver eliminato personalmente il tuo valore.

Un'altra area di ricerca attiva è l'uso di altri approcci che non utilizzano accoppiamenti e lo stesso paradigma di configurazione affidabile per raggiungere lo stesso obiettivo; Vedere La recente presentazione di Eli ben Sasson per un'alternativa (ma attenzione, è matematicamente complicato almeno quanto lo sono gli SNARK!)

Un ringraziamento speciale ad Ariel Gabizon e Christian Reitwiessner per la revisione.

• Distribuzione di contenuti basati su SEO e PR. Ricevi amplificazione oggi.
• PlatoData.Network Generativo verticale Ai. Potenzia te stesso. Accedi qui.
• PlatoAiStream. Intelligenza Web3. Conoscenza amplificata. Accedi qui.
• PlatoneESG. Carbonio, Tecnologia pulita, Energia, Ambiente, Solare, Gestione dei rifiuti. Accedi qui.
• Platone Salute. Intelligence sulle biotecnologie e sulle sperimentazioni cliniche. Accedi qui.
• BlockOffset. Modernizzare la proprietà della compensazione ambientale. Accedi qui.
• Fonte: Platone Data Intelligence.