Ce dont vous aurez besoin:
- une formation en informatique
- les bases d'Ethereum
- les bases du calcul (optimisation des contraintes)
Ce que vous obtiendrez:
- les bases des SNARK à connaissance zéro
- les bases des arbres Merkle
- comment Ethereum pourrait évoluer vers des milliers de transactions par seconde grâce aux SNARK
Les SNARK permettent à un prouveur de prouver à un vérificateur qu'il a une solution W au problème F avec des entrées partagées / connues X, sans révéler W.
Trouver la solution au problème pourrait nécessiter une énorme quantité de puissance de calcul et de mémoire.
Ainsi, le vérificateur peut être à 100% sûr que le prouveur a fonctionné correctement (et a trouvé une solution), sans ni refaire le travail par elle-même pour vérifier la solution, ni connaître la solution du tout. C'est magique!
Le processus se déroule en 3 étapes:
- SETUP - Le problème F (qui doit être exprimé sous forme de programme arithmétique quadratique, voir ci-dessous) est préparé pour les SNARK. Ce processus est très gourmand en mémoire et en calcul selon la complexité du problème (→ le nombre d'entrées et de contraintes → la dimension de la matrice du problème de satisfaction des contraintes). Le joueur qui effectue l'installation (pourrait être le vérificateur lui-même) doit être approuvé par toutes les parties, car la sortie de l'installation est utilisée dans les phases suivantes. La configuration se fait généralement en utilisant libsnark, une bibliothèque C ++ qui est l'implémentation la plus populaire pour zkSNARKs.
- PROUVER - Le Prouveur, qui a une solution W pour le problème F avec des entrées partagées X (peut-être qu'il / elle a dépensé d'énormes quantités de CPU et de mémoire pour le trouver!), Utilise libsnark et la sortie du installation phase pour créer une preuve 𝚷. Ce processus est certainement très gourmand en mémoire et en calcul (en fonction de la complexité du problème, comme ci-dessus). La taille de la sortie (c'est-à-dire la preuve 𝚷) est plutôt succincte et constante indépendamment de la complexité du problème. Le prouveur doit faire confiance à qui a effectué la phase de configuration, car il utilise sa sortie…
- VÉRIFICATION - Un vérificateur - donnant en entrée la sortie de la phase de configuration, les entrées partagées X et la preuve 𝚷 - vérifie la preuve. Si la vérification est réussie, le prouveur a réussi à prouver à un vérificateur qu'il a trouvé la solution W au problème F… sans révéler W! La bonne partie est que non seulement la preuve est succincte et a toujours la même longueur .., le processus de vérification est rapide et ne nécessite pas du tout de mémoire / calcul. Contrairement aux deux phases précédentes… la vérification peut se faire facilement avec un smartphone en quelques millisecondes!
Un bon récapitulatif (la source):
Comment cela peut-il arriver? Eh bien, c'est la magie de Merlin! Si vous voulez obtenir les maths derrière cela, partir d'ici.
Comment puis-je transformer mon logiciel en un programme arithmétique quadratique?
Comme mentionné ci-dessus, le problème F de la phase de configuration doit être un programme arithmétique quadratique. Les règles du jeu sont difficiles:
- Les entrées de votre logiciel doivent être des nombres. Convertissez vos éléments (tableaux, chaînes, etc.) en nombres. C'est insignifiant.
- Un «système d'équations à contrainte quadratique» signifie:
où x est le vecteur à n dimensions de vos entrées, m est le nombre de contraintes (c'est-à-dire le nombre d'équations de votre système), C est la matrice des coefficients n par n et q est un vecteur à coefficients n dimensions. Si vous n'aimez pas la matrice et les vecteurs, voici le cas n = 3 et m = 2 (3 entrées, 2 contraintes):
- La mise en œuvre est un circuit arithmétique, ce qui signifie que le résultat est Problème résolu (le système est résolu, c'est-à-dire que tous les polynômes sont égaux à 0) ou Problème non résolu (tous les autres cas). En d'autres termes: «ces entrées sont / ne sont pas l'une des solutions à ce problème».
- Les coefficients C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 sont les contraintes du système. C'est essentiellement ce qui définit votre logiciel. Changez-les… et vous obtiendrez un autre logiciel! Revenir au fonctionnement des SNARK: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 sont les entrées de la phase de configuration. La sortie de la phase de configuration (dont vous avez besoin pour prouver et vérifier) est donc strictement liée à ces C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 et ne fonctionne que pour ce problème. Si vous les modifiez, vous définissez un autre logiciel / problème et vous devez relancer la phase de configuration! x₁, x₂,…, x𝗇 sont les variables (c'est-à-dire ce que vous devez deviner pour obtenir la solution d'un système). Donc, quand nous disons «Cher prouveur, pourriez-vous s'il vous plaît trouver une solution secrète W pour le problème F avec des entrées partagées / publiques X», nous voulons dire par exemple «Cher prouveur, pouvez-vous trouver les valeurs x₁, x₂,…, x𝗇 qui résolvent le système avec, par exemple, x₇ = 2393, x₅₂₆ = 5647? " Vous pouvez faire ce que vous voulez avec tous les x𝗇, à l'exception de x₇ et x₅₂₆, qui sont limités aux entrées partagées / publiques.
C'est une vie difficile mais vous pouvez survivre… Si vous avez besoin de boucles, vous pouvez les déplier en répétant plusieurs fois la même opération. Ou si vous avez besoin par exemple de x₁⁴ x₂⁵, vous définissez une nouvelle entrée x₃ = x₁⁴ x₂⁵ et utilisez x₃ dans vos contraintes. Il s'agit avant tout d'ajouter des variables et des contraintes… Même pour des logiciels assez simples, il est facile d'atteindre des centaines de millions ou des milliards d'entrées et de contraintes!
Veut en savoir plus? Lis ici. Et consultez également cette base code_to_r1cs.py d'Ethereum / recherche.
Qu'est-ce qu'un arbre Merkle?
Une fonction de hachage est une règle qui mappe une entrée de taille arbitraire à une sortie de taille fixe. On pourrait inventer une fonction de hachage assez inutile "Concaténer les deux premiers avec les deux dernières lettres" qui transforme "Woody Allen" en "Woen" et "Paul McCartney" en "Paey".
Un arbre Merkle est une structure de données où chaque parent est le hachage de ses deux fils. En haut, vous trouverez la racine, qui est le hachage des deux fils de niveau 1. En bas, chaque feuille est le hachage d'une entrée externe.
Utilisation de notre fonction de hachage fictive «Woody Allen» → «Woen»:
Lorsqu'une feuille change, la modification est propagée jusqu'à la racine. Si ANTHONY change, également ANNY (feuille), CENY et CECO (racine) changent. Quelle que soit la feuille qui change, la racine change aussi.
Vous n'avez pas besoin de l'arborescence entière pour recalculer la racine. Dans notre exemple, si ANTHONY change et que vous connaissez à la fois JACO et CECILY, vous pouvez facilement recalculer la racine même si vous ignorez complètement JAMES, MARCO, JAES et MACO. Pour les grands arbres, cela fait gagner beaucoup de temps!
Alors qu'est-ce?
Les arbres Merkle sont parfaits pour les contrôles d'intégrité des données. Habituellement: vous savez quelle est la racine valide et vous vérifiez que les données reçues correspondent à cette racine. Par exemple: une partie de confiance qui ne peut pas vous donner l'ensemble complet des données des prénoms des personnes sur Terre (pas de temps, pas de bande passante ou peut-être qu'il / elle n'a pas du tout les données) ne vous donne que la racine (par exemple «CECO»). Afterwords: vous recevez des millions de prénoms, en référence au numéro de feuille, par des milliers de personnes non fiables. Eh bien, puisque vous avez la bonne racine, vous pouvez vérifier sur qui vous pouvez compter, qui vous donne de fausses données…
Les merkles font aussi partie de votre vie! Lorsque vous téléchargez un fichier Torrent de 3 Go, votre fichier est divisé en millions de petits morceaux. Le hachage de chaque morceau est stocké dans une feuille. Puisque vous savez quelle est la racine valide de l'arborescence, chaque fois que vous recevez un morceau du fichier par quelqu'un, vous pouvez vérifier s'il est correct. Si ce n'est pas le cas, vous pouvez demander le même morceau à quelqu'un d'autre.
Vous pouvez le faire même si vous n'avez pas encore téléchargé tout l'arbre / toutes les feuilles: si vous savez que la racine est CECO et que vous faites confiance à JACO… lorsque vous recevez le morceau ANTHONY, vous pouvez le vérifier même si vous n'avez pas téléchargé pourtant les morceaux MARCO et JAMES.
Pourquoi les arbres Merkle sont utiles dans la technologie des registres distribués est simple: vous utilisez des protocoles de consensus (lents, coûteux) uniquement pour atteindre un consensus sur la racine. Ensuite, les nœuds non fiables du réseau peuvent partager efficacement et directement des données… et peuvent dormir en sécurité grâce à des contrôles d'intégrité avec la racine.
Quand Dieu a demandé à Ethereum de choisir 2 superpuissances parmi la sécurité, l'évolutivité et la décentralisation… Ethereum a sacrifié l'évolutivité. En fait, il n'y a pas de plafond fort sur les «transactions par seconde»: le plafond concerne la quantité de gaz de chaque bloc - ce qui est, simplifiant, la quantité d'opérations que je peux faire dans chaque bloc. Cette limite est de 8 millions de gaz. Cela pourrait signifier de nombreuses transactions «minuscules» (aucune donnée attachée aux transactions, aucune opération à exécuter sur ces données) ou quelques transactions importantes. C'est aux nœuds d'Ethereum, qui soumettent des transactions, et aux mineurs d'Ethereum, qui incluent dans le bloc les transactions qui paient plus.
Un bloc est extrait chaque ~ 15 secondes. Cela signifie environ 32 millions de gaz par minute, ce qui n'est certainement pas suffisant si nous voulons que les applications d'Ethereum soient généralisées.
Soit dit en passant: arrêtez-vous avec ces comparaisons fastidieuses entre Ethereum et Visa. Un système centralisé toujours être plus rapide qu'Ethereum… par conception! Ils font des choses différentes et vous en avez besoin dans différentes situations. Si vous n'avez pas besoin de décentralisation et d'un environnement sans confiance… vous devez bien sûr choisir Visa. En bref: le fait que votre mélangeur tourne plus vite que votre lave-linge ne signifie pas que vous nettoierez votre pantalon dans un mélangeur!
Mettons le puzzle ensemble! Imaginez que vous puissiez «compresser» de nombreuses petites transactions en une seule grande transaction grâce aux SNARK. Si le gaz dépensé par cette grande transaction est inférieur à la somme du gaz dépensé par les petites transactions, cela signifie que vous économisez du gaz.
Et économiser du gaz signifie:
- Les utilisateurs dépensent moins pour l'ensemble des transactions → Ce serait un coup de pouce pour l'ensemble de l'écosystème
- Pouvoir mettre plus de choses dans un bloc → Ethereum tourne plus vite que votre mélangeur!
Comment cela fonctionne ?
Il y a des utilisateurs, un relayer (ou plusieurs relais) qui agrège les transactions et un contrat intelligent.
- Les utilisateurs désireux de jouer à ce jeu envoient leur Ether (ou jetons) à un contrat intelligent audité publiquement. Pour chaque nouveau joueur, une nouvelle feuille dans un arbre Merkle est créée. La feuille comprend des informations sur le propriétaire de l'Ether (son adresse, qui est également la clé publique), le montant d'Ether et le nonce (le compteur de transactions de ce compte, qui est 0 lorsque la feuille est ajoutée)
- Lorsque A souhaite envoyer Ether à B (ils doivent tous deux avoir une feuille / un compte dans le contrat intelligent), A emballe une transaction, qui comprend l'adresse du decompte, le à compte, le Nonce du compte from, le montant d'Ether à transférer et la Signature de la transaction (signé avec la clé privée du compte «from», évidemment). Il envoie ensuite la transaction emballée au relayer.
- Le relayer regroupe toutes les transactions reçues dans une fenêtre de temps donnée (par exemple une heure), met à jour l'arborescence Merkle avec les nouveaux montants des soldes et crée une preuve SNARK qui prouve que toutes les signatures et la racine de la nouvelle arborescence Merkle sont valides. Le relayer envoie enfin le nouvel état et la preuve au contrat intelligent.
- Le contrat intelligent valide la preuve en chaîne. S'il est valide, il enregistre la racine de l'arbre Merkle du nouvel état dans la mémoire interne du contrat.
Fondamentalement, la racine de l'arbre Merkle représente l'état complet de tous les comptes. Et vous ne pouvez pas le changer (= voler de l'argent) à moins que vous ne puissiez prouver la validité des signatures dont les transactions conduisent au nouvel état résumé par la nouvelle racine que vous soumettez.
En bref: les utilisateurs ont des transactions super rapides et presque gratuites, comme sur Coinbase, sans avoir besoin de faire confiance au relayer, qui ne peut rien faire, contrairement à Coinbase, sans votre signature.
Il s'agit d'une chaîne latérale non dépositaire dont l'état est résumé par une racine d'arbre Merkle.
Connectons ce que nous avons appris ci-dessus sur les SNARK avec ce que nous venons de discuter de la mise à l'échelle. Il existe différentes façons de procéder. Je vais comparer 2 recettes: Vitalik's version et barryWhiteHat's version.
Le SETUP se fait par…
Le gars qui démarre le projet, qui crée également le contrat intelligent. Plus il est auditable, mieux c'est. Vous devez lui faire confiance… c'est un configuration de confiance!
Le contrat intelligent sauve…
2 racines Merkle (valeurs en octets32): la première arborescence contient les adresses des comptes (signatures publiques), les soldes des autres comptes et les nonces
LA PREUVE se fait par…
Le relayer
Le relayer envoie au smart contract…
- les 2 racines Merkle du nouvel état (adresse arbre et balances + arbre nonces)
- la liste des transactions, sans signatures. «Chaque transaction coûte 68 gaz par octet. Par conséquent, pour un transfert régulier, nous pouvons nous attendre à ce que le coût marginal soit de 68 * 3 (de) + 68 * 3 (à) + 68 * 1 (frais) + 68 * 4 + 4 * 2 (montant) + 68 * 2 (nonce), ou 892 gaz "
Les entrées connues du processus PROVING sont…
- les 2 racines anciennes de Merkle
- les 2 nouvelles racines étatiques de Merkle
- liste des transactions
Le processus PROVING prouve que…
Donné
- les 2 racines anciennes de Merkle (déjà stockées dans le contrat)
- les 2 nouvelles racines de l'état Merkle (envoyées dans la transaction agr.)
- la liste des transactions (envoyée dans la transaction agr.)
… Le relayer a des signatures valides pour passer de l'état avec 2 anciennes racines à l'état avec 2 nouvelles racines avec ces transactions.
LA VÉRIFICATION se fait par…
Le contrat intelligent (codé en solidité, vyper, comme vous l'aimez!)
Les entrées connues du processus de VÉRIFICATION sont…
Les mêmes entrées connues du processus de PROVING, clairement…!
Limites d'évolutivité
Chaque transaction agrégée utilise 650 k de gaz pour la vérification SNARK (coûts fixes) plus ~ 900 gaz de coût marginal par transaction (cela coûte d'envoyer des données!). Donc, en utilisant le bloc entier, le relayer peut agréger au plus:
ce qui signifie ~ 544 tx par seconde
barryWhiteHat's version
Le SETUP se fait par…
Le gars qui démarre le projet.
Le contrat intelligent sauve…
1 racine Merkle avec l'état actuel. Chaque feuille est l'état haché d'un compte.
Vouloir engendrent un compte?
state = AccountState (pubkey, balance, nonce)
state.index = self._tree.append (state.hash ())
LA PREUVE se fait par…
Le relayer
Le relayer envoie au smart contract…
- preuve 𝚷
- la racine New State Merkle
- preuve 𝚷
Les entrées connues du processus PROVING sont…
- la racine de Merkle Old State
- la racine New State Merkle
Le processus PROVING prouve que…
Donné
- la racine Old Merkle (déjà stockée dans le contrat)
- la racine New Merkle (senti dans la transaction agr.)
… Le relayer a une liste de transactions avec des signatures valides pour passer de l'état avec l'ancienne racine à l'état avec la nouvelle racine
LA VÉRIFICATION se fait par…
Le contrat intelligent (codé en solidité, vyper, comme vous l'aimez!)
Les entrées connues du processus de VÉRIFICATION sont…
Les mêmes entrées connues du processus de PROVING, clairement…!
Limites d'évolutivité
Le relayer n'envoie pas les données des transactions au contrat intelligent (ce qui est coûteux), donc la limite est en fait la quantité de gaz pour vérifier la preuve SNARK.
Mentionner celle d'Howard Wu travail sur l'exécution de la phase PROVING de SNARK sur des systèmes distribués, barryWhiteHat avec optimisme indique qu'il est possible de confirmer 16666 transactions dans un énorme SNARK (1 milliard de contraintes!).
barryWhiteHat également pense il est possible de vérifier la preuve 𝚷 en chaîne avec du gaz 500k, ce qui signifie que vous pouvez mettre 16 SNARK (8 millions / 500k) par bloc, ce qui est ~ 1.07 SNARK par seconde… ce qui signifie ~ 17,832 XNUMX tx par seconde (16,666 1.07 * XNUMX).
Vers l'infini et au-delà
- Tout ce qui brille n'est pas or / 1. La quantité de puissance de calcul et de mémoire dont vous avez besoin dans la phase de test peut être littéralement choquante. Surtout dans la version de barryWhiteHat, où une partie de la complexité est déplacée hors chaîne. barry écrit «Sur un ordinateur portable avec 7 Go de RAM et 20 Go d'espace de swap, il a du mal à regrouper 20 transactions par seconde». Eh bien, si l'objectif est de 17,832 XNUMX tx par seconde… LOL. Cela introduit des défis de calcul parallèle non triviaux. Mais si le coût moyen par transaction est beaucoup moins cher que l'option sans SNARK ordinaire… le jeu en vaut la chandelle.
- Tout ce qui brille n'est pas or / 2. Il y a un problème de disponibilité des données! Étant donné que seule la racine de l'arborescence est enregistrée dans le contrat, vous devez être sûr qu'une version complète de l'arborescence (ou, c'est la même chose, l'historique complet des transactions) est toujours disponible. Si les données ne sont pas disponibles, le relayer, même avec des transactions signées valides, ne peut rien faire car il / elle ne peut pas prouver Old State → Transactions → New State.
- Pour que le relayer soit sans confiance et que les Ethers dans le contrat aient la même valeur que les Ethers en dehors (problème de liquidité) ... les utilisateurs devraient pouvoir retirer de l'argent du contrat intelligent quand ils le souhaitent, sans avoir recours à un relayer (spécifique). Comment? Ce n'est pas dans la portée de ce poste 101, mais vous pouvez lire à ce sujet dans les liens ci-joints.
- Vous voulez mieux comprendre comment l'état actuel (adresses, soldes et nonces) peut être géré avec un arbre Merkle? Ajouter une feuille, mettre à jour une feuille, etc.? Check-out cette bibliothèque (fichier de test ici) qui utilise ce sous-jacent module. Merci HarryR!
- Vous voulez configurer votre environnement personnel Ethereum-SNARKs? Commençons hors chaîne avec C ++ (Setup, Proving, Verifying) ici. Ensuite, vous pouvez passer à Ethereum (n'oubliez pas, seule la vérification se fait en chaîne!) Avec Zokrates (repo, documentation pour commencer).
- Que diriez-vous d'utiliser des accumulateurs RSA au lieu des arbres Merkle? Google “Accumulateurs rsa ethereum” commencer…
Chin!
Twitter @marco_derossi
- 7
- Compte
- Tous
- parmi
- disponibilité
- Basics
- Milliards
- cas
- Change
- Contrôles
- coinbase
- informatique
- Consensus
- contrat
- Costs
- Courant
- État actuel
- DApps
- données
- ensemble de données
- La décentralisation
- Dimension
- Ledger distribué
- technologie de registre distribué
- Environment
- Éther
- Ethereum
- EU
- EV
- faux
- finalement
- Prénom
- Test d'anglais
- fonction
- jeu
- GAS
- GitHub
- Don
- Or
- Bien
- l'
- guide
- hachage
- ici
- Haute
- Histoire
- Comment
- hr
- HTTPS
- majeur
- Des centaines
- ia
- indice
- d'information
- IP
- IT
- Emploi
- ACTIVITES
- portatif
- gros
- conduire
- Ledger
- Niveau
- LG
- Bibliothèque
- Liquidité
- Liste
- Courant dominant
- Map
- moyenne
- million
- mineurs
- de l'argent
- mois
- Le Plus Populaire
- Bougez
- noms
- réseau et
- nœuds
- numéros
- Opérations
- de commander
- Autre
- propriétaire
- Payer
- Personnes
- joueur
- Populaire
- power
- Privé
- Clé privée
- Programme
- Projet
- preuve
- Prouve
- public
- Clé publique
- résumer
- rsa
- pour le running
- des
- économie
- Évolutivité
- Escaliers intérieurs
- mise à l'échelle
- Sciences
- sécurité
- set
- Partager
- commun
- Shorts
- étapes
- Taille
- sleep
- smart
- contrat intelligent
- smartphone
- So
- Logiciels
- solidité
- Solutions
- RÉSOUDRE
- Space
- Dépenses
- Commencer
- j'ai commencé
- Région
- États
- réussi
- combustion propre
- Système
- Technologie
- tester
- fiable
- Tokens
- top
- torrent
- transaction
- Transactions
- La confiance
- Actualités
- utilisateurs
- Plus-value
- Vérification
- visa
- W
- WHO
- des mots
- Activités principales
- vos contrats
- vaut
- X