Dimostrazioni a prova zero: cosa sono gli zk-STARK e come funzionano? (zk-Stark V2)

Che cosa sono la Proof of Reserve e la Dimostrazione a conoscenza zero?

Proof of Reserve (PoR)

Si tratta di un processo degli exchange di criptovalute per dimostrare di avere abbastanza asset per coprire tutti i saldi dei clienti. In questo modo cresce la fiducia, perché l’exchange si assume le proprie responsabilità. Il modo più semplice per dimostrarlo è pubblicare sia gli importi degli asset dell'exchange che un elenco dei saldi degli utenti in modo che tutti possano verificarlo:

• Il totale delle detenzioni degli asset degli utenti che OKX afferma di detenere è la somma del saldo totale degli asset di ogni utente.

• Il saldo totale di ogni utente è superiore a zero e i loro asset sono contabilizzati, coprendo le loro passività e garantendo che ogni utente abbia un patrimonio netto positivo.

• Il valore totale che l'exchange rivendica tiene conto di ogni singolo utente, quindi ogni utente dovrebbe essere in grado di verificare l'inclusione del proprio valore netto nel valore totale.

Tuttavia, rivelare questi saldi può compromettere la privacy degli utenti. Per risolvere questo problema, utilizziamo un metodo chiamato Dimostrazione a conoscenza zero (ZKP) per proteggere la privacy degli utenti.

Dimostrazione a conoscenza zero (ZKP)

È una tecnica di sicurezza che consente agli exchange di criptovalute di dimostrare che un'affermazione è vera senza rivelare ulteriori informazioni.

Nel nostro caso, vogliamo dimostrare di avere fondi sufficienti senza condividere dettagli specifici dell'utente. La maggior parte degli ZKP rientra in due categorie:

• zk-SNARK

• zk-STARK

Utilizziamo zk-STARK perché è più sicuro e ha un'assunzione di sicurezza minima. In questo articolo, spiegheremo come utilizziamo zk-STARK per proteggere la privacy degli utenti mentre dimostriamo la nostra solvibilità.Prima di continuare, è utile comprendere alcuni termini di base del ZKP, come Circuito, Merkle tree e Impegni.

I principianti possono consultare molte risorse per comprendere gli aspetti basilari. Gli utenti avanzati possono invece fare riferimento al Corso MOOC e alla monografia accademica.

Come funziona zk-STARK?

Creiamo un Merkle tree utilizzando l'hash di ciascun conto utente come foglie. Ogni conto mostra saldi in USD per vari token (ades., BTC, ETH). Per gestire questi saldi, separiamo i suoi saldi in patrimoni netti non negativi e debiti per ciascun token. In questo modo, lavoriamo solo con numeri positivi, rendendo più facile gestire i calcoli ed evitare errori.

Ad esempio:

• Se il saldo del token BTC di un utente è A, il suo patrimonio netto BTC è A e il debito BTC è 0

• Se il saldo del token ETH di un utente è -B, il suo patrimonio netto corrispondente è 0 e il debito è B

Successivamente, costruiamo un Merkle tree con questi valori dei conti come foglie. La radice dell'albero funge da un valore singolo che rappresenta tutti i saldi degli utenti. Ogni utente può dimostrare che il proprio conto fa parte di questo albero utilizzando un Percorso Merkle che mostra come il proprio conto si collega alla radice.

Pubblichiamo anche il patrimonio netto totale e il debito sommati su tutti i token e gli utenti. Poi, creiamo una Dimostrazione a conoscenza zero (ZKP) per mostrare due cose:

• Prova della somma: i valori di patrimonio netto e debito nel Merkle tree si sommano correttamente

• Prova non negativa: il patrimonio netto totale di ogni utente è maggiore del proprio debito totale

Quando cerchiamo di verificare il Merkle tree per un gran numero di conti, il processo diventa troppo grande da gestire in una sola volta. Per superare questa situazione, suddividiamo i conti in gruppi più piccoli chiamati batch. Ogni batch viene elaborato separatamente utilizzando circuiti batch, che controllano la parte inferiore del Merkle tree.

La divisione in batch non solo lo rende gestibile, ma ci consente anche di eseguire questi controlli contemporaneamente (elaborazione parallela). Una volta ottenuti i risultati da ciascun batch, utilizziamo un altro strato di circuiti, chiamati circuiti ricorsivi, per combinare e verificare tutti i batch insieme, fino a quando non abbiamo dimostrato l'intero Merkle tree.

Che cos'è il Circuito batch?

Il circuito batch prende 1.024 conti (conto₀, conto₁,..., conto_1.023) come input e genera tre output principali: un hash (h_batch), un valore totale di patrimonio netto (e_batch) e un valore totale di debito (d_batch). Controlla che:

• Il patrimonio netto totale denominato in USD di ciascun conto sia maggiore del suo debito totale.

• e_batch è la somma di tutti i valori del patrimonio netto denominati in USD in questi conti

• d_batch è la somma di tutti i valori del debito denominati in USD su questi conti

• h_batch è la radice del Merkle tree creato utilizzando gli hash dei conti

• Non c'è overflow durante la somma per e_batch e d_batch

Che cos'è un circuito ricorsivo?

Il circuito ricorsivo prende 64 prove diverse (π₀, ..., π₆₃), hash (h₀, ..., h₆₃), patrimoni netti (e₀, ..., e₆₃₎, e debiti (d₀, ..., d₆₃) dai circuiti di livello inferiore come input. Combina questi input e produce tre output: un nuovo hash (h_ricorsivo), patrimonio netto totale (e_ricorsivo) e debito totale (d_ricorsivo). Controlla che:

• Ciascuna delle 64 dimostrazioni è valida

• Ogni prova π₀, ..., π₆₃ dal circuito di livello inferiore è valido

• e_ricorsivo è la somma di e₀, ..., e₆₃

• d_ricorsivo è la somma di d₀, ..., d₆₃

• h_ricorsivo è l'hash della concatenazione di h₀, ..., h₆₃, i.e.

  • h_ricorsivo = Hash (h₀ || h₁ || ... || h₆₃₎

• Non c'è overflow durante la somma per e_ricorsivo e d_ricorsivo

Qual è la relazione tra circuiti batch e circuiti ricorsivi?

Il diagramma sottostante illustra come il circuito batch e i circuiti ricorsivi si collegano e scambiano dati tra di loro. Tieni presente che nel diagramma, duplichiamo i circuiti a scopo illustrativo, ma nella nostra implementazione utilizziamo solo un circuito per ogni livello.

Il nostro Merkle tree è strutturato in modo leggermente diverso. Nei 10 livelli inferiori, ogni nodo genitore ha due figli, mentre nei livelli superiori, ogni genitore ha 64 figli. Questo avviene perché i circuiti batch gestiscono la parte inferiore e i circuiti ricorsivi gestiscono la parte superiore. Il diagramma sottostante utilizza un esempio con "Alice" per mostrare il Merkle tree e la sua prova di Merkle (colorata di verde).

Per ulteriori dettagli tecnici, su come ad esempio adattiamo i numeri di conto per soddisfare la dimensione del batch o scegliere il giusto algoritmo di hash, visita questa pagina.

Progressi nella zk-PoR Versione 2

La nostra versione zk-PoR 2 ha fatto diversi progressi rispetto alla versione precedente:

• Maggiore efficienza: Ora è cinquanta volte più veloce della versione precedente. Sono necessarie tre ore su una singola macchina a 10 core, rispetto alle 36 ore della versione precedente utilizzando nove macchine a 64 core. Questa accelerazione è dovuta all'uso del framework Plonky2, che compila circuiti codificati in Rust in un linguaggio macchina efficiente invece di utilizzare script Python più lenti. Abbiamo anche migliorato Plonky2 per eseguire alcuni calcoli su GPU, riducendo il tempo di un ulteriore 30%.

• Migliore verificabilità: Con la Versione 2, utilizziamo un framework di alto livello che gestisce per noi dettagli crittografici complessi. Questo rende il nostro codice più chiaro, più leggibile e meno soggetto a errori.

• Prova concisa: La dimensione della prova V2 (~500KB) è solo 0.05% di V1 (~1.2 GB). Grazie al metodo ricorsivo, le prove possono essere aggregate e condensate ripetutamente in un'unica prova.

Come posso eseguire l'auto-verifica della Proof of Reserves (PoR)?

Ecco come puoi controllare se il saldo del tuo asset è incluso come foglia Merkle zk-STARK:

1. Accedi al tuo conto OKX, vai su Asset e seleziona rapporto PoR

2. Seleziona Dettagli per visualizzare i tuoi dati di audit

   

3. Ottieni i dati di cui hai bisogno per la verifica manuale selezionando Copia dati

   

4. Dopo aver selezionato Copia dati, apri l'editor di testo (ades. usando il notebook) quindi incolla e salva la stringa JSON come file. Il file deve terminare con il nome "_inclusion_proof.json." La stringa JSON contiene il saldo del tuo conto e un'istantanea del percorso Merkle, quindi salva il file in una nuova cartella

5. Apri un editor di testo (ades., Notebook), quindi incolla e salva la stringa JSON come file. Il nome del file deve terminare con "_inclusion_proof.json." Salva il file in una nuova cartella.

   • La stringa JSON contiene il saldo del tuo conto e un'istantanea del percorso Merkle.

   • Il testo JSON è mostrato di seguito:

     {"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}}

6. Scarica lo strumento di verifica open-source di OKX: zk-STARKValidator

7. Salva lo strumento di verifica open-source di OKX, zk-STARKValidator, e il file della stringa JSON insieme nella nuova cartella creata nel Passaggio 5. Nel nostro caso, abbiamo posizionato lo strumento e il file di dati nella cartella Download, chiamata "proof-of-reserves", come mostrato di seguito:

   

8. Apri lo zk-STARKValidator; eseguirà automaticamente il file JSON che hai salvato nella cartella

9. Controlla il risultato:

   • Se la verifica ha esito positivo, verrà mostrato il risultato La validazione del vincolo di inclusione è stata superata:

     

   • Se la verifica non riesce, verrà mostrato il risultato La validazione del vincolo di inclusione è fallita:

     

Come posso verificare il saldo totale zk-STARK e il vincolo di non negatività?

Ecco come puoi verificare la veridicità degli asset che affermiamo di detenere e che nessun utente abbia un patrimonio netto negativo:

1. Vai alla nostra pagina Proof of Reserve e seleziona Rapporto di passività

2. Scarica il file zk-STARK e salvalo in una nuova cartella

   

3. Decomprimi il file per estrarre un file "sum_proof_data.json”

   

4. Scarica lo strumento di verifica open-source di OKX: zk-STARKValidator

5. Salva lo strumento di verifica open-source di OKX, zk-STARKValidator, e il file "sum_proof_data.json" insieme nella nuova cartella creata nel Passaggio 2. Nel nostro caso, abbiamo posizionato lo strumento e il file di dati nella cartella Download, chiamata "proof-of-reserves", come mostrato di seguito:

   

6. Apri zk-STARKValidator; eseguirà automaticamente il file dati di prova della somma che hai salvato nella cartella.

7. Controlla il risultato

   • Se la verifica ha esito positivo, verrà mostrato il risultato La validazione di somma totale e vincolo non negativo è stata superata:

     

   • Se la verifica ha esito negativo, verrà mostrato il risultato La validazione di somma totale e vincolo non negativo è fallita:

     

Per scoprire ulteriori dettagli tecnici, il nostro sistema di Proof of Reserves è open-source e disponibile per la revisione e l’utilizzo su github.