Di cosa avrai bisogno:
- uno sfondo di informatica
- le basi di Ethereum
- le basi del calcolo (ottimizzazione dei vincoli)
Che cosa si ottiene:
- le basi degli SNARK a conoscenza zero
- le basi degli alberi di Merkle
- come Ethereum potrebbe ridimensionare a migliaia di transazioni al secondo grazie a SNARKs
Gli SNARK consentono a un Prover di dimostrare a un Verificatore di avere una soluzione W al problema F con input condivisi / noti X, senza rivelare W.
Trovare la soluzione al problema potrebbe richiedere un'enorme quantità di potenza e memoria computazionale.
Quindi il verificatore può sostanzialmente essere sicuro al 100% che Prover abbia funzionato correttamente (e trovato una soluzione), senza ri-fare il lavoro da solo per verificare la soluzione né conoscerne affatto la soluzione. È magico!
Il processo prevede 3 passaggi:
- IMPOSTARE - Il problema F (che deve essere espresso come programma aritmetico quadratico, vedi sotto) è preparato per gli SNARK. Questo processo richiede molta memoria e un'elevata elaborazione informatica a seconda della complessità del problema (→ Il numero di input e vincoli → La dimensione della matrice del problema di soddisfazione dei vincoli). Il giocatore che esegue l'installazione (potrebbe essere lo stesso verificatore) deve essere considerato attendibile da tutte le parti, poiché l'output dell'installazione viene utilizzato nelle fasi successive. La configurazione viene solitamente eseguita utilizzando libsnark, una libreria C ++ che è l'implementazione più popolare per zkSNARKs.
- LIEVITAZIONE - Il Prover, che ha una soluzione W per il problema F con input condivisi X (forse ha speso enormi quantità di CPU e memoria per trovarlo!), Usa libsnark e l'output di Impostare fase per creare una prova 𝚷. Questo processo richiede molta memoria e un'elevata intensità di elaborazione (a seconda della complessità del problema, come sopra). La dimensione dell'output (cioè prova 𝚷) è invece concisa e costante indipendentemente dalla complessità del problema. Il Prover deve fidarsi di chi ha eseguito la fase di installazione, poiché usa il suo output ...
- VERIFICA - Un verificatore - che fornisce come input l'output della fase di installazione, gli input condivisi X e la prova 𝚷 - controlla la prova. Se la verifica ha esito positivo, il Prover è riuscito a dimostrare a un verificatore di aver trovato la soluzione W al problema F ... senza rivelare W! La parte bella è che non solo la prova è succinta e ha sempre la stessa lunghezza .., il processo di verifica è veloce e non richiede molta memoria / elaborazione. A differenza delle due fasi precedenti ... la verifica può essere facilmente eseguita con uno smartphone in millisecondi!
Un buon riassunto (source):
Come può succedere? Bene, è la magia di Merlino! Se vuoi approfondire la matematica, inizia da qui.
Come posso trasformare il mio software in un programma aritmetico quadratico?
Come accennato in precedenza, il problema F della fase di installazione deve essere un programma aritmetico quadratico. Le regole del gioco sono difficili:
- Gli input del tuo software dovrebbero essere numeri. Converti le tue cose (array, stringhe, ecc.) In numeri. È banale.
- Un "sistema di equazioni quadraticamente vincolato" significa:
dove x è il vettore n-dimensionale dei tuoi input, m è il numero di vincoli (cioè il numero di equazioni del tuo sistema), C è la matrice dei coefficienti n-per-n e q è un vettore dei coefficienti n-dimensionale. Se non ti piacciono la matrice e i vettori, ecco il caso n = 3 e m = 2 (3 input, 2 vincoli):
- L'implementazione è un circuito aritmetico, il che significa che il risultato è Problema risolto (il sistema è risolto, cioè tutti i polinomi sono uguali a 0) o Problema non risolto (tutti gli altri casi). In altre parole: "questi input sono / non sono una delle soluzioni a questo problema".
- I coefficienti C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 sono i vincoli del sistema. Questo è fondamentalmente ciò che definisce il tuo software. Modificali ... e otterrai un altro software! Tornando al funzionamento di SNARK: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 sono l'input della fase di installazione. L'output della fase di installazione (necessaria per il provisioning e la verifica) è quindi strettamente correlato a quelli C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 e funziona solo per quel problema. Se li cambi, stai definendo un altro software / problema e devi rieseguire la fase di installazione! x₁, x₂,…, x𝗇 sono le variabili (cioè ciò che devi indovinare per ottenere una soluzione di sistema). Quindi quando diciamo "Caro Prover, potresti trovare una soluzione segreta W per il problema F con input condivisi / pubblici X" intendiamo ad esempio "Caro Prover, puoi trovare i valori x₁, x₂, ..., x𝗇 che risolvono il sistema con, ad esempio, x₇ = 2393, x₅₂₆ = 5647? ” Puoi fare quello che vuoi con tutti gli x𝗇, ad eccezione di x₇ e x₅₂₆, che sono vincolati agli input condivisi / pubblici.
È una vita difficile ma puoi sopravvivere ... Se hai bisogno di anelli, puoi dispiegarli ripetendo la stessa operazione molte volte. Oppure, se è necessario ad esempio x₁⁴ x₂⁵, si definisce un nuovo input x₃ = x₁⁴ x₂⁵ e si usa x₃ nei propri vincoli. Si tratta solo di aggiungere variabili e vincoli ... Anche per software piuttosto semplici è facile raggiungere centinaia di milioni o miliardi di input e vincoli!
Voglio sapere di più? Leggere qui. E dai un'occhiata anche a questo di base code_to_r1cs.py da ethereum / ricerca.
Che cos'è un albero Merkle?
Una funzione hash è una regola che mappa un input di dimensione arbitraria su un output di dimensione fissa. Potremmo inventare una funzione hash piuttosto inutile "Concatena i primi due con le ultime due lettere" che trasforma "Woody Allen" in "Woen" e "Paul McCartney" in "Paey".
Un albero Merkle è una struttura di dati in cui ogni genitore è l'hash dei suoi due figli. Nella parte superiore trovi la radice, che è l'hash dei due figli del livello 1. Nella parte inferiore, ogni foglia è l'hash di un input esterno.
Usando la nostra funzione hash "Woody Allen" → "Woen":
Quando una foglia cambia, la modifica viene propagata fino alla radice. Se ANTHONY cambia, cambiano anche ANNY (foglia), CENY e CECO (Root). Qualunque foglia cambi, cambia anche la radice.
Non è necessario l'intero albero per ricalcolare la radice. Nel nostro esempio, se ANTHONY cambia e conosci sia JACO che CECILY, puoi facilmente ricalcolare la radice anche se ignori completamente JAMES, MARCO, JAES e MACO. Per alberi enormi questo fa risparmiare molto tempo!
E allora?
Gli alberi Merkle sono ottimi per i controlli di integrità dei dati. Di solito: sai qual è la radice valida e controlli che i dati ricevuti corrispondano a quella radice. Ad esempio: una parte fidata che non può fornirti l'intero set di dati dei nomi delle persone sulla Terra (nessun tempo, nessuna larghezza di banda o forse non ha affatto i dati) ti dà solo la radice (ad es. “CECO”). Postfazioni: ricevi milioni di nomi, con riferimento al numero foglia, da migliaia di parti non attendibili. Bene, poiché hai la radice corretta puoi controllare su chi puoi contare, chi ti sta dando dati falsi ...
Anche gli alberi di merkle fanno parte della tua vita! Quando scarichi un file Torrent da 3 GB, il tuo file viene diviso in milioni di piccoli pezzi. L'hash di ogni blocco è memorizzato in una foglia. Poiché sai qual è la radice dell'albero valida, ogni volta che ricevi una parte del file da qualcuno, puoi verificare se è corretta. In caso contrario, puoi chiedere lo stesso pezzo a qualcun altro.
Puoi farlo anche se non hai ancora scaricato l'intero albero / tutte le foglie: se sai che la radice è CECO e ti fidi di JACO ... quando ricevi il pezzo ANTHONY puoi verificarlo anche se non hai scaricato eppure i pezzi MARCO e JAMES.
Perché gli alberi di Merkle siano utili nella tecnologia di contabilità distribuita è semplice: si utilizzano protocolli di consenso (lenti, costosi) solo per raggiungere il consenso sulla radice. Quindi i nodi non attendibili della rete possono condividere in modo efficiente e diretto i dati ... e possono dormire sani e salvi grazie ai controlli di integrità con il Root.
Quando Dio chiese a Ethereum di scegliere 2 superpoteri tra Sicurezza, Scalabilità e Decentramento ... Ethereum sacrificò la Scalabilità. In realtà non esiste un limite massimo per le "transazioni al secondo": il limite riguarda la quantità di gas di ciascun blocco - che è, semplificando, la quantità di operazioni che posso fare in ciascun blocco. Questo limite è di 8 milioni di gas. Ciò potrebbe significare molte transazioni "minuscole" (nessun dato allegato alle transazioni, nessuna operazione da eseguire su tali dati) o poche transazioni di grandi dimensioni. Spetta ai nodi di Ethereum, che inviano le transazioni, e ai minatori di Ethereum, che includono nel blocco le transazioni che pagano di più.
Viene estratto un blocco ogni ~ 15 secondi. Ciò significa ~ 32 milioni di gas al minuto, il che sicuramente non è sufficiente se vogliamo che le dapps di Ethereum diventino mainstream.
A proposito: basta con quei noiosi paragoni tra Ethereum e Visa. Sarà un sistema centralizzato sempre essere più veloce di Ethereum ... di progettazione! Fanno cose diverse e tu ne hai bisogno in diverse situazioni. Se non hai bisogno del decentramento e di un ambiente privo di fiducia ... ovviamente dovresti scegliere Visa. In breve: il fatto che il tuo frullatore giri più velocemente della lavatrice non significa che pulirai i pantaloni in un frullatore!
Mettiamo insieme il puzzle! Immagina di poter "comprimere" molte piccole transazioni in un'unica grande transazione grazie a SNARK. Se il gas speso da questa grande transazione è inferiore alla somma del gas speso dalle piccole transazioni, significa che stai risparmiando gas.
E risparmiare gas significa:
- Gli utenti spendono meno per le transazioni complessive → Questa sarebbe una spinta per l'intero ecosistema
- Essere in grado di mettere più cose in un blocco → Ethereum gira più velocemente del tuo frullatore!
Come funziona?
Ci sono utenti, un relayer (o più relayer) che aggrega le transazioni e un contratto intelligente.
- Gli utenti disposti a giocare a questo gioco inviano i propri Ether (o token) a un contratto intelligente verificato pubblicamente. Per ogni nuovo giocatore viene creata una nuova foglia in un albero Merkle. La foglia include informazioni sul proprietario dell'Ether (il suo indirizzo, che è anche la chiave pubblica), la quantità di Ether e nonce (il contatore delle transazioni di quel conto, che è 0 quando viene aggiunta la foglia)
- Quando A vuole inviare Ether a B (entrambi devono avere un leaf / account nel contratto intelligente), A impacchetta una transazione, che include l'indirizzo del daaccount, il a account, il nonce dell'account from, il quantità di Ether da trasferire e il firma della transazione (firmato con la chiave privata dell'account "from", ovviamente). Invia quindi la transazione imballata al relayer.
- Il relayer aggrega tutte le transazioni ricevute in una determinata finestra temporale (ad esempio un'ora), aggiorna l'albero di Merkle con gli importi dei nuovi saldi e crea una prova SNARK che dimostra che tutte le firme e la radice del nuovo albero di Merkle sono valide. Il relè infine invia il nuovo stato e la prova al contratto intelligente.
- Il contratto intelligente convalida la prova on-chain. Se è valido, salva la radice dell'albero Merkle del nuovo stato nella memoria interna del contratto.
Fondamentalmente, la radice dell'albero di Merkle raffigura l'intero stato di tutti gli account. E non puoi cambiarlo (= rubare denaro) a meno che tu non possa dimostrare la validità delle firme le cui transazioni portano al Nuovo stato riassunto dalla nuova radice che stai inviando.
In breve: gli utenti hanno transazioni super veloci e quasi gratuite, come su Coinbase, senza la necessità di fidarsi del relayer, che non può fare nulla, a differenza di Coinbase, senza la tua firma.
È una catena laterale non riservata il cui stato è riassunto da una radice dell'albero di Merkle.
Colleghiamo ciò che abbiamo appreso in precedenza sugli SNARK con ciò che abbiamo appena discusso sul ridimensionamento. Esistono diversi modi per farlo. Comparerò 2 ricette: Vitalik's versione e barryWhiteHat's versione.
Il SETUP viene eseguito da ...
Il ragazzo che avvia il progetto, che crea anche il contratto intelligente. Più è udibile, meglio è. Dovresti fidarti di lui / lui ... è a installazione affidabile!
Il contratto intelligente salva ...
2 radici Merkle (valori bytes32): il primo albero contiene gli indirizzi dei conti (firme pubbliche), i saldi dei conti secondari e i nonces
PROVING è fatto da ...
Il relè
Il relè invia al contratto intelligente ...
- le 2 radici Merkle del Nuovo stato (indirizza albero e saldi + albero nonces)
- l'elenco delle transazioni, senza firme. “Ogni transazione costa 68 gas per byte. Quindi, per un trasferimento regolare, possiamo aspettarci che il costo marginale sia 68 * 3 (da) + 68 * 3 (a) + 68 * 1 (commissione) + 68 * 4 + 4 * 2 (importo) + 68 * 2 (nonce) o 892 gas "
Gli input noti del processo PROVING sono ...
- le 2 vecchie radici Merkle dello stato
- le 2 nuove radici Merkle dello stato
- elenco delle transazioni
Il processo PROVING dimostra che ...
Dato
- le 2 vecchie radici Merkle dello stato (già memorizzate nel contratto)
- le 2 nuove radici Merkle dello stato (inviate nella transazione aggr.)
- l'elenco delle transazioni (inviato nella transazione aggregata)
... il relayer ha firme valide per passare dallo stato con 2 vecchie radici allo stato con 2 nuove radici con quelle transazioni.
LA VERIFICA viene eseguita da ...
Il contratto intelligente (codificato nella solidità, vyper, come preferisci!)
Gli input noti del processo di VERIFICA sono ...
Gli stessi processi di PROVING noti input, chiaramente ...!
Limiti alla scalabilità
Ogni transazione aggregata utilizza 650k di gas per la verifica SNARK (costo fisso) più ~ 900 gas di costo marginale per transazione (costa inviare dati!). Quindi, usando l'intero blocco, il relè può aggregare al massimo:
che significa ~ 544 tx al secondo
barryWhiteHat di versione
Il SETUP viene eseguito da ...
Il ragazzo che inizia il progetto.
Il contratto intelligente salva ...
1 radice Merkle con lo stato corrente. Ogni foglia è lo stato con hash di un account.
Vuoi creare un account?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
PROVING è fatto da ...
Il relè
Il relè invia al contratto intelligente ...
- prova 𝚷
- la radice Merkle del nuovo stato
- prova 𝚷
Gli input noti del processo PROVING sono ...
- la radice di Merkle del vecchio stato
- la radice Merkle del nuovo stato
Il processo PROVING dimostra che ...
Dato
- la radice di Old Merkle (già memorizzata nel contratto)
- la radice di New Merkle (senti nella transazione aggr.)
... il relayer ha un elenco di transazioni con firme valide per passare dallo stato con la vecchia radice allo stato con la nuova radice
LA VERIFICA viene eseguita da ...
Il contratto intelligente (codificato nella solidità, vyper, come preferisci!)
Gli input noti del processo di VERIFICA sono ...
Gli stessi processi di PROVING noti input, chiaramente ...!
Limiti alla scalabilità
Il relè non sta inviando i dati delle transazioni al contratto intelligente (che è costoso), quindi il limite è in realtà la quantità di gas per verificare la prova SNARK.
Menzionando Howard Wu's lavoro sull'esecuzione della fase PROVING di SNARK su sistemi distribuiti, barryWhiteHat ottimisticamente afferma che è possibile confermare 16666 transazioni in un enorme SNARK (1 miliardo di vincoli!).
barryWhiteHat anche pensa della ricerca di mercato è possibile verificare la prova 𝚷 sulla catena con 500k di gas, il che significa che è possibile inserire 16 SNARK (8 milioni / 500k) per blocco, che è ~ 1.07 SNARKs al secondo ... il che significa ~ 17,832 tx al secondo (16,666 * 1.07).
Verso l'infinito e oltre
- Tutto ciò che luccica non è oro / 1. La quantità di potenza di calcolo e memoria necessaria nella fase di prova può essere letteralmente scioccante. Soprattutto nella versione di barryWhiteHat, dove parte della complessità viene spostata off-chain. scrive Barry "Su un laptop con 7 GB di RAM e 20 GB di spazio di scambio fa fatica ad aggregare 20 transazioni al secondo". Bene, se l'obiettivo è 17,832 tx al secondo ... LOL. Questo introduce sfide di calcolo parallelo non banali. Ma se il costo medio in $ per transazione è molto più economico dell'ordinaria opzione no-SNARKs ... il gioco vale la candela.
- Tutto ciò che luccica non è oro / 2. Esiste un problema rilevante di disponibilità dei dati! Poiché nel contratto viene salvata solo la radice dell'albero, è necessario assicurarsi che sia sempre disponibile un'intera versione dell'albero (o, è la stessa, l'intera cronologia delle transazioni). Se i dati non sono disponibili, il relayer, anche con transazioni firmate valide, non può fare nulla perché non può provare il vecchio stato → Transazioni → Nuovo stato.
- Affinché il relayer sia privo di fiducia e gli Ethers nel contratto abbiano lo stesso valore di Ethers all'esterno (problema di liquidità) ... gli utenti dovrebbero essere in grado di prelevare denaro dal contratto intelligente quando vogliono, senza fare affidamento su un relayer (specifico). Come? Questo non rientra nell'ambito di questo post 101, ma puoi leggerlo nei link allegati.
- Vuoi capire di più su come gestire lo stato attuale (indirizzi, saldi e nonces) con un albero Merkle? Aggiunta di una foglia, aggiornamento di una foglia, ecc.? Check-out questa biblioteca (file di prova qui) che utilizza questo sottostante modulo. Grazie HarryR!
- Vuoi configurare il tuo ambiente personale Ethereum-SNARKs? Iniziamo off-chain con C ++ (Setup, Proving, Verifica) qui. Quindi puoi passare a Ethereum (non dimenticare, solo la verifica viene eseguita sulla catena!) Con Zokrates (pronti contro termine, le documentazione per iniziare).
- Che ne dici di usare gli accumulatori RSA invece degli alberi Merkle? Google “Accumulatori rsa ethereum” iniziare…
Buon divertimento!
Twitter @marco_derossi
- 7
- Il mio account
- Tutti
- tra
- disponibilità
- Nozioni di base
- Miliardo
- casi
- il cambiamento
- Controlli
- coinbase
- informatica
- Consenso
- contratto
- Costi
- Corrente
- Stato attuale
- DApp
- dati
- set di dati
- Decentramento
- Dimensioni
- Ledger distribuito
- tecnologia della contabilità distribuita
- Ambiente
- etere
- Ethereum
- EU
- EV
- falso
- Infine
- Nome
- Gratis
- function
- gioco
- GAS
- GitHub
- Dare
- Oro
- buono
- grande
- guida
- hash
- qui
- Alta
- storia
- Come
- hr
- HTTPS
- Enorme
- centinaia
- ia
- Index
- informazioni
- IP
- IT
- Lavoro
- Le
- laptop
- grandi
- portare
- Ledger
- Livello
- LG
- Biblioteca
- Liquidità
- Lista
- corrente principale
- Maps
- medie
- milione
- minatori
- soldi
- mese
- Più popolare
- cambiano
- nomi
- Rete
- nodi
- numeri
- Operazioni
- minimo
- Altro
- proprietario
- Paga le
- Persone
- giocatore
- Popolare
- energia
- un bagno
- chiave privata
- Programma
- progetto
- prova
- dimostra
- la percezione
- chiave pubblica
- ricapitolare
- rsa
- norme
- running
- sicura
- risparmio
- Scalabilità
- Scala
- scala
- Scienze
- problemi di
- set
- Condividi
- condiviso
- Corti
- Un'espansione
- Taglia
- sonno
- smart
- smart contract
- smartphone
- So
- Software
- solidità
- Soluzioni
- RISOLVERE
- lo spazio
- Spendere
- inizia a
- iniziato
- Regione / Stato
- stati
- di successo
- sistema
- SISTEMI DI TRATTAMENTO
- Tecnologia
- test
- tempo
- Tokens
- top
- torrente
- delle transazioni
- Le transazioni
- Affidati ad
- Aggiornamenti
- utenti
- APPREZZIAMO
- Convalida
- Visa
- W
- OMS
- parole
- Lavora
- lavori
- valore
- X