Zero-Knowledge Proofs (Dimostrazioni a conoscenza zero): cosa sono le zk-STARK e come funzionano?

1. Che cos'è?

Il sistema zk-STARK Proof of Reserves (PoR) sfrutta la teoria STARK, una complessa soluzione matematica. zk-STARK è l'acronimo di: Zero-Knowledge Scalable Transparent Argument of Knowledge, una tecnologia di prova crittografica basata sull'[idea] di Vitalik (https://vitalik.eth.limo/general/2022/11/19/proof_of_solvency.html) di rafforzare l'integrità e la privacy dei calcoli su blockchain. In questo articolo, ti presenteremo il suo funzionamento e spiegheremo il concetto matematico generale, ma se sei interessato ad approfondire l'argomento, inizia da qui o da qui.

Come funziona?

Figura 1. Tabella delle tracce di esecuzione e albero di Merkle creato per zk-STARK PoR

Fase 1: vincoli edilizi

Al fine di dimostrare la responsabilità del nostro exchange, facciamo tre dichiarazioni:

Dichiarazione 1: Abbiamo accumulato correttamente i valori di ogni utente, incluso il valore di ogni criptovaluta e il valore netto di ogni utente

Dichiarazione 2: L'exchange non ha creato un utente virtuale il cui valore netto sia negativo per ridurre la responsabilità totale dell'exchange (un singolo utente che ha saldi negativi è accettabile solo se il suo valore netto è superiore a 0)

Dichiarazione 3: Il valore totale che l'exchange rivendica è riferito a ogni singolo utente, quindi ogni utente dovrebbe essere in grado di verificare l'inclusione del proprio valore netto all'interno del valore totale

Per testare e verificare le dichiarazione di cui sopra, abbiamo bisogno di creare vincoli come:

Dichiarazione 1: Vincolo del saldo totale (vincolo di un corretto saldo totale)

uts: dimensione della traccia dell'utente, ovvero il numero di righe di tracce incluse nei dati di ciascun utente.

somma: saldo totale dell'utente

N: numero di utenti

Dichiarazione 2: Vincolo non negativo (vincolo di patrimonio netto positivo)

Dichiarazione 3: Vincolo di inclusione (vincolo di inclusione di tutto il saldo del conto cliente)

In base ai vincoli di cui sopra, creiamo una tabella di tracciamento per impegnare e verificare i saldi totali e la non negatività attraverso ispezioni a campione. Ecco come viene costruita la tabella di tracciamento (esempio esemplice: 3 utenti il cui valore massimo in usd è inferiore a 4^6 = 4096):

1. Inizializziamo una tabella con 32 righe e 5 colonne, e inseriamo i valori e gli ID dell'utente in riga, dove k % 8 = 6, e . Un gruppo di 8 righe è considerato un blocco e al suo interno sono presenti le informazioni sugli asset dell'utente   disposte in ordine inverso. Al primo utente vengono assegnati saldi virtuali 0, possiamo quindi pubblicarlo per dimostrare che l'accumulo di valori non parte da un valore negativo.

2. Accumuliamo i valori degli asset dell'utente uno per uno e compiliamo il risultato nelle  righe in cui k % 8 = 7, e , che rappresentano le ultime righe di ogni blocco

3. Continuiamo dividendo il valore totale di ogni utente per 4, riga per riga, in ordine inverso per ogni blocco. Lo facciamo per mantenere il valore netto dell'utente non negativo, controllando se le prime righe di ogni blocco sono zero. Se qualcuno ha un valore netto negativo, la prima riga del suo blocco non sarà zero perché un valore negativo (-x) risulterà essere (p - x) in un campo finito , che è un valore positivo molto grande.

4. Inseriamo numeri casuali per ogni utente e riempiamo gli spazi vuoti nella tabella con 0

Fase 2: Estensione polinomiale di basso grado Utilizzando i vincoli polinomiali di cui sopra, possiamo ottenere un polinomio di traccia di calcolo di lunghezza uts * N. Per motivi di sicurezza, eseguiamo l'impegno del polinomio su un dominio di valutazione più ampio, con il fattore di amplificazione del dominio come extension_factor.

Nel caso precedente, potremmo calcolare un polinomio p(x) da I(x). Quando usiamo un'extension_factor 8, calcoleremo altri 32(8-1)* punti su p(x).

Poiché due diversi polinomi con grado D condivideranno al massimo D punti, una coppia di polinomi di esempio con un polinomio valido (che soddisfa i vincoli di cui sopra) e un falso polinomio con grado D (che non soddisfa i vincoli di cui sopra) condividerà al massimo D punti. Ciò significa che un falso polinomio ha una possibilità di di superare un controllo a campione. Se eseguiamo l'ispezione del campionamento n volte, la possibilità diminuirà a .

Implementiamo l'extension_factor predefinito a 16 e il tempo di ispezione di campionamento predefinito a 16, quindi il livello di sicurezza sarà di 80 bit.

Fase 3: impegno polinomiale Calcoliamo il valore hash della traccia di calcolo e del corrispondente bilancio utente, l'ID utente e il valore del corrispondente polinomio di vincolo per ogni riga. Generiamo poi un albero di Merkle. La radice di Merkle è il valore di impegno del polinomio.

Fase 4: generazione della prova di campionamento Campioniamo i dati utilizzando la radice di Merkle come fonte casuale. Per evitare la perdita dei dati della traccia di calcolo, evitiamo i dati che presentano un indice di *k ** extension_factor durante il campionamento, e generiamo il percorso di prova di Merkle corrispondente all'indice di campionamento.

Eseguiamo le ispezioni di campionamento per verificare se il polinomio impegnato è un polinomio valido che soddisfa i vincoli elencati nella Fase 1. Come specificato nella Fase 2, i tempi delle ispezioni a campione influiranno sulla possibilità che la manomissione o la manipolazione abbia successo.

Fase 5: generazione di prove di basso grado

Possiamo controllare la probabilità di successo della manomissione o della manipolazione attraverso un'ispezione a campione. Tuttavia, come indicato nella Fase 2, è necessario assicurarsi che il grado del polinomio da verificare non sia superiore al grado di un polinomio valido. Per migliorare l'efficienza della dimostrazione, combiniamo linearmente tutti i polinomi di vincolo in un unico polinomio e generiamo una prova di basso grado. Anche i coefficienti di combinazione vengono generati utilizzando la radice di Merkle come fonte casuale.

Ad esempio, se vogliamo dimostrare che p0(x), p1(x) e p2(x) non sono maggiori dei gradi D, possiamo generare 2 coefficienti casuali dalla radice di Merkle generata al punto 3 e calcolare il polinomio lineare l(x) come:

k0 = hash(radice + "0")
k1 = hash(radice + "1")
l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

Se si può dimostrare che l(x) non è maggiore del grado D, allora la possibilità che il grado di uno qualsiasi di p0(x), p1(x) e p2(x) sia maggiore di D sarà vicino a 0

Fase 6: verifica del saldo totale In primo luogo, verifichiamo la prova di basso grado generata durante la Fase 5.

Viene quindi eseguita un'ulteriore verifica aperta sui dati a campione generati durante la Fase 4. Innanzitutto, è necessario verificare che i dati siano coerenti con l'impegno polinomiale e, in secondo luogo, verificare che i dati soddisfino i vincoli costruiti durante la Fase 1. Infine, vengono verificati i coefficienti di combinazione del polinomio di test di basso grado.

Fase 7: generazione della prova di inclusione dell'utente Per dimostrare che un utente specifico è incluso nell'importo totale richiesto dall'exchange, forniamo la traccia calcolata dell'utente, il saldo dell'utente, l'ID utente e un numero casuale corrispondente all'indice dell'utente. Forniamo anche il percorso Merkle corrispondente a questi dati.

Fase 8: verifica da parte dell'utente della prova di inclusione L'utente controlla il proprio saldo, ID, calcola il valore hash dei dati corrispondenti al proprio indice e verifica il valore hash sul nodo foglia dell'albero di Merkle, utilizzando il percorso Merkle fornito.

2. Come eseguire l'autoverifica di Proof of Reserves (PoR)?

2.1 Verifica del vincolo di inclusione zk-STARK

Teoria su come effettuare la verifica

Seguendo la procedura STARK, calcoleremo la tabella di tracciamento dell'esecuzione di tutti gli asset dell'utente come indicato di seguito, ed eseguiremo l'hash di ogni informazione dell'utente come tabella di tracciamento, che diventerà poi una foglia dell'albero di Merkle. Impegneremo successivamente le foglie in una radice di Merkle che sarà pubblicata durante ogni round di audit PoR.

Per verificare se i tuoi asset sono inclusi nella radice, ti forniremo il percorso Merkle per effettuare la verifica. Prima puoi calcolare la tua foglia eseguendo l'hash delle informazioni sull'asset, e poi verificare se la tua foglia è una foglia valida nell'albero e nella radice di Merkle che pubblichiamo.

Ad esempio, nella Figura 1, l'utente con ID id_k calcolerà hashk = hash("20" + "15" + "5" + "id_k" + "99821"), e gli altri dati all'interno della cornice quadrata rossa rappresenteranno la verifica del percorso di Merkle. Viene fornito uno strumento open source per consentire agli utenti di eseguire questa verifica.

Poiché le foglie dell'albero di Merkle sono hash, nessuna delle tue informazioni private verrà divulgata a terzi.

Come effettuare la verifica:

1. Per verificare se il saldo del tuo conto è stato incluso come foglia zk-STARK di Merkle, accedi al tuo conto OKX, visita "Audit" per visualizzare gli audit recenti e fai clic su "Dettagli" per visualizzare i dati dell'audit.

2. Ottieni i dati necessari alla verifica manuale facendo clic su "Copia dati".

3. Dopo aver fatto clic su "Copia dati", apri l'editor di testo (ad esempio utilizzando 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, e salva il file in una nuova cartella.

Il testo JSON è mostrato come di seguito:

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}

4. Scarica lo strumento di verifica open source OKXzk-STARKValidator

5. Salva lo strumento di verifica open source OKX zk-STARKValidator e il file JSON string insieme, all'interno della nuova cartella della Fase 3. Nel nostro caso, inseriamo lo strumento e il file di dati nella cartella "Download", denominata "proof-of-reserves" mostrata di seguito:

6. Apri zk-STARKValidator e verrà eseguito automaticamente il file di JSON string che hai salvato all'interno della cartella.

7. Controlla il risultato

• Se la verifica ha esito positivo, verrà mostrato il risultato "Convalida del vincolo di inclusione superata":

  

• Se la verifica fallisce, verrà visualizzato il risultato "Convalida del vincolo di inclusione fallita":

  

2.2 Verifica il saldo totale zk-STARK e il vincolo non negativo

Come effettuare la verifica:

Per verificare e dimostrare che gli asset che dichiariamo di detenere sono reali e che nessun utente detiene un patrimonio netto negativo, visita la nostra pagina "File audit” e scarica i file "zk-STARK" in Report di passività, quindi salvalo in una nuova cartella.

Decomprimi il file scaricato e troverai una cartella "sum proof data", che include migliaia di cartelle minori e una cartella principale. Ogni cartella contiene due file JSON denominati "sum_proof.json" e "sum_value.json".

Scarica lo strumento di verifica open source OKXzk-STARKValidator

Salva strumento di verifica open source OKXzk-STARKValidator e la cartella "sum proof data" insieme, all'interno della cartella creata nella Fase 1. Nel nostro caso, inseriamo lo strumento e il file di dati nella cartella "Download", denominata "proof-of-reserves", mostrata di seguito:

Apri zk-STARKValidator, e verrà eseguito automaticamente "sum proof data" che hai salvato nella cartella.

Controlla il risultato

Se la verifica ha esito positivo, verrà mostrato il risultato "Riepilogo totale e convalida del vincolo non negativo superati":

Se la verifica fallisce, verrà mostrato il risultato "Riepilogo totale e convalida del vincolo non negativo falliti":