1. Introduction

Le dernier jour de 2023, Vitalik a partagé la feuille de route d'Ethereum pour 2023 sur Twitter, résumant les progrès d'Ethereum au cours de l'année. La section de la feuille de route "The Verge" décrit comment la technologie d'Ethereum pourrait vérifier les états de la blockchain de manière plus simple et plus efficace. Un concept clé mentionné là-bas est les Arbres Verkle. Alors, quels sont les Arbres Verkle, pourquoi Ethereum en a besoin et comment les Arbres Verkle résolvent-ils les problèmes? L'objectif de cet article est de répondre à ces questions pour les lecteurs sans entrer trop profondément dans la cryptographie et les mathématiques, aidant ainsi ceux qui ont une certaine compréhension d'Ethereum à saisir rapidement le concept des Arbres Verkle.

2. Requête vérifiable

La technologie de requête vérifiable est largement étudiée dans le domaine des bases de données traditionnelles, principalement utilisée pour résoudre les problèmes de confiance avec les bases de données externes. Dans de nombreux scénarios, les propriétaires de données peuvent choisir de ne pas stocker les données eux-mêmes, mais de confier leurs besoins en matière de base de données à un tiers pour fournir des services de base de données (tels que des bases de données cloud). Cependant, comme les tiers ne sont pas toujours dignes de confiance, la crédibilité des résultats de requête qu'ils renvoient aux utilisateurs est difficile à garantir. Les solutions actuelles de requête vérifiable pour les bases de données traditionnelles se situent principalement dans deux catégories : celles basées sur les ADS (structures de données authentifiées) et celles basées sur le calcul vérifiable.

ADS est une technique de requête vérifiable largement utilisée dans les bases de données traditionnelles, principalement basées sur des structures telles que les arbres de Merkle ou des structures cumulatives similaires. Avec l'évolution des outils cryptographiques, de nombreux chercheurs ont progressivement commencé à explorer l'utilisation de techniques de calcul vérifiable pour résoudre les problèmes liés aux requêtes non fiables. Certains schémas de calcul vérifiable basés sur des protocoles de preuve de connaissance nulle, tels que les SNARKs, peuvent indirectement prendre en charge des requêtes vérifiables pour des bases de données externes. Ces schémas prennent en charge une grande variété de types de requêtes et génèrent moins d'informations de vérification, mais ils ont des surcoûts computationnels plus élevés.

Actuellement, Ethereum utilise des arbres de Merkle pour implémenter des requêtes vérifiables, et la technologie Verkle Tree est également basée sur la technologie des arbres de Merkle. Par conséquent, commençons par introduire les arbres de Merkle pour aider les lecteurs à comprendre le rôle des requêtes vérifiables en utilisant un exemple.

3. Arbres de Merkle

3.1. Définition et Caractéristiques des Arbres de Merkle

Les arbres de Merkle sont une structure en forme d'arbre couramment utilisée en cryptographie, adaptée pour résoudre les problèmes d'intégrité des données. Ci-dessous se trouve une structure typique d'arbre de Merkle : les nœuds feuilles représentent les données d'origine ou leurs valeurs de hachage, et chaque nœud non-feuille (interne) contient le hachage combiné de ses nœuds enfants.

Les arbres de Merkle ont deux caractéristiques importantes :

1. Résistance à la falsification : Les arbres de Merkle sont généralement construits à l'aide de fonctions de hachage résistantes aux collisions, ce qui rend computationnellement impossible de trouver deux messages différents produisant la même valeur de hachage. À partir de la structure d'un arbre de Merkle, il est évident que toute modification des données de transaction dans un nœud feuille entraînera un changement de la valeur de hachage racine de l'arbre.
2. Vérification efficace de l'intégrité des grands ensembles de données : Les vérificateurs n'ont besoin de stocker que le hachage racine de l'arbre de Merkle pour vérifier l'intégrité de n'importe quelle donnée. Cela est réalisé sans transmettre l'ensemble complet des données, mais plutôt en utilisant les nœuds frères le long du chemin de la feuille à la racine, connu sous le nom de chemin de Merkle. Ces nœuds frères peuvent être utilisés pour reconstruire le hachage racine à des fins de vérification.

3.2. Comment construire une preuve de Merkle?

Dans un scénario de requête vérifiable commun, il y a un prouveur et un vérificateur. Le prouveur doit générer une preuve et l'envoyer au vérificateur. En ce qui concerne le réseau Ethereum, un scénario d'application typique est celui où un nœud léger (un client qui ne stocke que les en-têtes de bloc) interroge les données de transaction auprès d'un nœud complet ou d'un nœud d'archive (clients avec toutes les données) et obtient une preuve de Merkle pour vérifier localement si le résultat de la requête est correct.

La preuve de Merkle se compose des trois parties suivantes:

1. Le hachage racine de l'arbre de Merkle pour l'ensemble de données complet.
2. Le bloc de données dont l'intégrité doit être prouvée.
3. Le chemin de Merkle, qui inclut les valeurs de tous les nœuds frères sur le chemin du nœud feuille au nœud racine.

Parmi ceux-ci, le hachage racine de l'arbre de Merkle doit être envoyé au vérificateur à l'avance par un moyen fiable, et le vérificateur doit faire confiance à cette valeur. Dans Ethereum, la fiabilité des données de bloc est assurée par l'algorithme de consensus, et le hachage racine de l'arbre de Merkle est contenu dans l'en-tête de bloc.

Voici un exemple spécifique : lorsque le prouveur doit prouver au vérificateur que "4" est un bloc de données existant dans l'ensemble de données, et que le vérificateur détient le hachage de la racine de confiance "1d25" de l'arbre de Merkle complet de l'ensemble de données, alors le prouveur n'a besoin de fournir que toutes les données marquées en bleu. En supposant qu'il y ait n morceaux de données dans l'ensemble, au plus 𝘭𝘰𝘨₂(𝘯) calculs de hachage sont nécessaires pour vérifier la correction de tout bloc de données.

Les nœuds légers d'Ethereum ne synchronisent que les en-têtes de bloc, qui contiennent les racines des arbres de Merkle pour divers ensembles de données (arbre d'état, arbre de transaction, arbre de reçus). Lorsqu'un nœud léger interroge un nœud complet pour les données d'un nœud feuille particulier dans l'arbre, le nœud complet renvoie les données d'origine avec le chemin de preuve de Merkle correspondant. Cela permet au nœud léger de faire confiance à la correction du résultat de la requête.

3.3. Variantes des arbres de Merkle

S'appuyant sur les fondations des arbres de Merkle, ils peuvent être combinés et modifiés avec d'autres structures de données pour atteindre de nouvelles caractéristiques basées sur différents objectifs. Pour répondre à divers scénarios de requêtes vérifiables, les arbres de Merkle peuvent être étendus à diverses structures de données indexées, telles que les arbres de Merkle-B (MBT). Pour une exécution efficace des opérations telles que l'insertion, la suppression et la requête, l'équipe Ethereum a proposé l'arbre de Patricia de Merkle (MPT).

3.3.1. Arbre Merkle-B

L'arbre de Merkle-B (MBT) est principalement utilisé pour gérer les requêtes de plage vérifiables. Soit 𝑓 le ventilateur du MBT (le nombre de nœuds enfants pour chaque nœud). Basé sur la structure de l'arbre B+, chaque nœud interne du MBT, en plus de stocker 𝑓 — 1 clés d'index et des pointeurs vers 𝑓 nœuds enfants, maintient également les valeurs de hachage de tous ses nœuds enfants sous forme résumée. Ci-dessous est une représentation de la structure des nœuds feuilles et des nœuds internes dans un MBT.

Lorsqu'il est nécessaire de prouver que les données renvoyées d'une certaine requête de plage sont conformes à la plage spécifiée, le serveur qui calcule l'objet de vérification (VO) doit d'abord effectuer deux opérations de recherche descendante pour trouver les limites gauche et droite. Il doit également renvoyer toutes les données dans cette limite ainsi que les hachages de toutes les branches nécessaires pour construire le chemin vers le hachage racine.

L'inconvénient de cette structure de données est que le VO retourné ne peut prouver que les résultats de la requête sont dans la plage de requête demandée, mais il ne peut pas prouver que les résultats retournés sont complets.

3.3.2. Arbre de Patricia de Merkle

Si un arbre de Merkle naïf est utilisé pour fournir des requêtes vérifiables, le processus long et fastidieux de régénération de la racine de l'arbre de Merkle après chaque insertion ou suppression de données peut devenir significatif. De plus, cela nécessite la maintenance de arbres de recherche de données supplémentaires pour le stockage. L'Arbre de Patricia de Merkle (MPT) combine les attributs d'un arbre de Radix (arbre compact de préfixes) et d'un arbre de Merkle, lui permettant d'effectuer des insertions, des suppressions et des requêtes en temps O(log(N)). Pour une compréhension complète du MPT, les lecteurs peuvent se référer à des articles techniques détaillés sur le sujet. Cet article se contentera d'introduire quelques définitions de base et de fournir des exemples pour aider les lecteurs à comprendre rapidement le MPT.

La structure sous-jacente d'Ethereum utilise une base de données clé-valeur pour le stockage, ce qui signifie que les données sont stockées sous forme de paires clé-valeur. L'arbre de preuve de Merkle est également décomposé en paires clé-valeur pour le stockage. Nous définissons la structure logique des nœuds MPT comme suit :

• indice
• chemin
• données

Dans le contexte de l'Arbre de Patricia Merkle (MPT), l'“index” fait référence à la clé d'une paire clé-valeur, tandis que le “chemin” combiné avec les “données” constitue la valeur de la paire clé-valeur. L'index stocke en réalité le hachage du nœud de l'arbre de Merkle, et le chemin correspond à la chaîne de chemin utilisée dans l'arbre de préfixes pour trouver le nœud cible. Ethereum utilise des chaînes hexadécimales comme chaînes de chemin, et donc la largeur du MPT est de 16. Les données sont les données cibles correspondant au chemin.

Voici un exemple d'un MPT qui a été optimisé avec des préfixes compressés, stockant les données de paires clé-valeur suivantes :

{

‘cab8’: ‘chien’,

‘cabe’: ‘chat’,

'39': 'poulet',

'395' : 'canard',

‘56f0’: ‘cheval’

}

Pour trouver les données "canard" en utilisant le chemin "395", vous commenceriez par le hachage racine et avanceriez à travers hashA, hashC et hashD pour finalement atteindre les données cibles. Voici un guide étape par étape :

1. Racine de hachage : il s'agit du point d'entrée de l'arbre de hachage de Merkle Patricia (MPT), et vous l'utiliseriez pour trouver le premier nœud.
2. hashA: Basé sur le hachage racine, vous récupéreriez le nœud ou le contenu identifié par hashA. Comme le chemin est "395", vous recherchez la partie de l'arbre qui vous mènera à "3".
3. hashC: Après avoir accédé au contenu de hashA, vous continuez à suivre le chemin. Le prochain segment, "9", vous mène à hashC.
4. hashD: Enfin, en continuant sur le chemin, le dernier segment "5" vous pointe vers hashD, qui contient la valeur "canard".

À chaque étape du chemin, le MPT tire parti des propriétés à la fois de l'arbre Radix, pour trouver le chemin correct basé sur la clé, et de l'arbre de Merkle, pour garantir l'intégrité des données grâce à des liens de hachage. Les "chemins" dans l'arbre sont généralement représentés avec un codage hexadécimal, qui correspond au facteur de branchement de l'arbre de 16. Chaque nœud du chemin contient suffisamment de pointeurs de hachage (vers les nœuds enfants) et de valeurs pour vérifier l'intégrité des données et naviguer à travers l'arbre.

Veuillez noter que dans un vrai MPT, les chemins et les données seraient encodés et stockés dans un format spécifique, et des types supplémentaires de nœuds (comme les nœuds d'extension et les nœuds feuilles) aident à optimiser la structure pour l'efficacité dans différents scénarios.

4. Engagement de vecteur

Les schémas d'engagement[1] sont des primitives cryptographiques qui garantissent la confidentialité et l'intégrité des données. Ils sont largement utilisés dans des scénarios tels que les preuves de zéro connaissance et les calculs sécurisés entre plusieurs parties. Un schéma d'engagement de base est divisé en deux étapes : la phase d'engagement et la phase de révélation (ouverture).

1. Phase d'engagement : Dans cette phase, le committeur utilise un algorithme cryptographique pour lier un message à une valeur d'engagement et envoie cette valeur d'engagement au destinataire. À ce stade, l'engagement possède deux propriétés : le masquage et la liaison. Le masquage garantit que le contenu du message engagé est inconnu de tous sauf du committeur. La liaison garantit qu'une fois un engagement pris, il ne peut être modifié par quiconque, y compris le committeur.
2. Phase de révélation (ouverture) : Pendant cette phase, le commettant peut prouver au destinataire que la valeur d'engagement qu'il a reçue est un engagement valide envers le message original. L'engagement a la propriété de correction, ce qui signifie que si le commettant et le destinataire suivent correctement le protocole, le destinataire sera convaincu que la valeur d'engagement qu'il a reçue pendant la phase d'engagement est un engagement valide envers le message original.

Le Vector Commitment est un type spécial de schéma d'engagement proposé par Catalano et al. [2] qui permet à un engageur de s'engager à un ensemble ordonné de messages 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ et de révéler (ouvrir) à n'importe quelle position spécifiée pour prouver que le message 𝑚𝑖 est le ième message engagé. Dans les engagements vectoriels, s'engager signifie que personne ne peut ouvrir la même position pour révéler des messages différents.

Un schéma d'engagement de vecteur se compose généralement des algorithmes suivants:

5. Arbres Verkle

5.1. Définition et caractéristiques des arbres Verkle

Définition : Verkle Trees = Engagements Vectoriels + Arbres de Merkle.

Veuillez noter：Vitalik Buterin, le co-fondateur d'Ethereum, a blogMessage spécifiquement dédié à la présentation des arbres Verkle. Ce chapitre ajoute quelques antécédents et connaissances mathématiques basées sur son blog. Certaines données et illustrations dans le texte suivant sont tirées de son blog.

Les arbres Verkle (VTs) se caractérisent par la fourniture de preuves plus petites par rapport aux arbres Merkle. Pour des données à l'échelle de milliards d'entrées, un arbre Merkle pourrait générer des preuves d'environ 1 Ko, tandis que les preuves d'arbre Verkle peuvent être inférieures à 150 octets. Cette taille de preuve compacte est avantageuse pour la mise en œuvreclients sans état”.

La structure d'un arbre Verkle est quelque peu similaire à celle de l'arbre de Patricia de Merkle (MPT). Voici un exemple de sa structure. Les nœuds d'un arbre Verkle peuvent être : (i) Vides, (ii) Nœuds feuilles contenant une clé et sa valeur correspondante, ou (iii) Nœuds internes avec un nombre fixe de nœuds enfants. Ce nombre d'enfants est également appelé la « largeur » de l'arbre.

La différence entre VT (Verkle Trees) et MPT (Merkle Patricia Trees) réside principalement dans la manière dont la largeur de l'arbre (ou fan-out, qui fait référence au nombre de nœuds enfants qu'un nœud de l'arbre possède) affecte leur efficacité. Dans le cas de MPT, si la largeur est plus grande, elle a tendance à être moins efficace car une plus grande largeur signifie plus de nœuds frères, ce qui pourrait entraîner des temps de mise à jour plus longs pour le MPT et des tailles de preuve plus grandes. En revanche, pour VT, une largeur d'arbre plus grande donne des preuves plus petites. La seule restriction est que si la largeur est trop élevée, le temps nécessaire pour générer une preuve peut devenir plus long.

Dans l'Ethereum @vbuterin/verkle_tree_eip">design proposals for VTs, une largeur de 256 est suggérée, ce qui est significativement plus grand que les 16 actuels pour MPT. Une telle largeur importante est réalisable dans les VTs grâce à l'utilisation de techniques cryptographiques avancées, telles que les engagements vectoriels, qui permettent des preuves compactes indépendamment de la largeur de l'arbre. Cette technique de compression permet aux arbres Verkle de s'adapter plus efficacement en termes de taille de preuve. Le texte suivant expliquera plus en détail les fonctionnalités mentionnées ci-dessus.

5.2. Engagement et Preuve des Arbres Verkle

Voyons comment les preuves sont générées dans un MPT : La preuve doit inclure les valeurs de hash de tous les nœuds latéraux (ou nœuds sœurs) sur le chemin allant du nœud racine au nœud feuille cible. En prenant "4ce" comme exemple, les parties marquées en rouge dans le schéma ci-dessous sont les nœuds qui doivent être inclus dans la preuve retournée.

Dans les arbres Verkle, vous n'avez pas besoin de fournir des nœuds frères ; au lieu de cela, vous devez uniquement fournir le chemin avec quelques données supplémentaires comme preuve.

Alors comment générer des engagements pour un VT? La fonction de hachage utilisée pour le calcul n'est pas un hachage conventionnel mais utilise des engagements de vecteurs.

Après avoir remplacé la fonction de hachage par un algorithme de génération d'engagement à partir d'engagements vectoriels, le soi-disant hachage racine est maintenant un engagement racine. Si les données de n'importe quel nœud sont altérées, cela affectera finalement l'engagement racine.

Comment générer une preuve ? Comme le montre le diagramme ci-dessous, vous devez simplement fournir trois sous-preuves, chacune d'entre elles pouvant prouver qu'un nœud sur le chemin existe à une certaine position au sein de son nœud parent. Plus la largeur est grande, moins il y a de couches et, par conséquent, moins de sous-preuves sont nécessaires.

Dans les mises en œuvre pratiques, des engagements polynomiaux sont utilisés (qui peuvent être mis en œuvre de manière simple et efficace pour les engagements vectoriels), permettant un engagement envers un polynôme. Les deux schémas d'engagement polynomiaux les plus conviviaux pour l'utilisateur sont “Engagements de KZG” et “engagements polynomiaux de style pare-balles(le premier a une taille d'engagement de 48 octets, tandis que le dernier est de 32 octets).

Si vous utilisez les engagements et les preuves KZG, la preuve pour chaque nœud intermédiaire ne représente que 96 octets, ce qui correspond à une économie d'espace de près de trois fois par rapport à un arbre de Merkle de base (en supposant une largeur de 256).

La complexité temporelle théorique des opérations sur les arbres Merkle et les arbres Verkle est la suivante:

Le schéma de preuve Verkle introduit jusqu'à présent est assez basique; en fait, il existe d'autres stratégies d'optimisation avancées disponibles.

5.3. Optimisation: Fusion des Preuves

5.3.1. idée

Par rapport à la génération d'une preuve pour chaque couche d'engagements sur un chemin, la caractéristique des engagements polynomiaux peut être utilisée pour réaliser « la preuve de la relation parent-enfant entre tous les engagements sur le chemin avec une preuve de taille fixe, qui peut inclure un nombre illimité d'éléments ». Pour comprendre spécifiquement comment cela est accompli, il est nécessaire d'introduire certaines connaissances mathématiques pour l'explication. Cet article impliquera certaines formules mathématiques mais ne couvrira pas la partie cryptographique de la preuve en principe. Pour la méthode spécifique, veuillez vous référer àschéma qui met en œuvre des multipreuve par évaluation aléatoire.

5.3.2. Dérivation mathématique

Tout d'abord, introduisons quelques concepts de base sur les polynômes en mathématiques : comment effectuons-nous la réduction de polynôme, également connue sous le nom de réduction de degré d'un polynôme ?

En supposant que nous connaissons un polynôme 𝑃(𝑥) et sa valeur 𝑦₁ à 𝑥₁, c'est-à-dire 𝑃(𝑥₁) = 𝑦₁ .

Maintenant, considérez un nouveau polynôme 𝑃(𝑥) - 𝑦₁ , qui a une valeur nulle à (𝑥 = 𝑥₁) , car 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

Par conséquent, le polynôme 𝑃(𝑥) - 𝑦₁ a une racine à 𝑥 = 𝑥₁, ce qui signifie que (𝑥 - 𝑥₁) est un facteur de 𝑃(𝑥) - 𝑦₁.

En d'autres termes, nous pouvons l'exprimer sous la forme suivante: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) est un autre polynôme dont le degré est inférieur d'une unité à celui de 𝑃(𝑥). Cela est dû au fait que (𝑥 -𝑥₁ ) est un facteur de premier degré, ce qui réduit le degré total du polynôme.

Comment utiliser KZG pour prouver une seule valeur dans un vecteur?

Prenons l'engagement KZG10 comme exemple, pour le polynôme 𝑃(𝑥), supposons que son engagement polynômial est [ 𝑃(𝑠) ]₁.

Comme expliqué précédemment, pour le polynôme 𝑃(𝑥), si 𝑃(𝑧) = 𝑦, alors nous avons 𝑄(𝑥) = (𝑃(𝑥) - 𝑦)/(𝑥 - 𝑧)

Maintenant, le prouveur peut générer une preuve que le polynôme 𝑃(𝑥) satisfait 𝑃(𝑧) = 𝑦 : calculer [ 𝑄(𝑠) ]₁ et l'envoyer au vérificateur.

Le vérificateur doit vérifier 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

Comment utiliser KZG pour prouver plusieurs valeurs dans un vecteur?

Nous pouvons construire une preuve pour démontrer plusieurs valeurs dans un vecteur comme suit :

En utilisant cette méthode, peu importe le nombre de points de données dans le même vecteur qui doivent être vérifiés, seule une preuve de taille constante est requise.

Maintenant, regardons le schéma de l'arbre Verkle sans optimisation du point de vue de l'algorithme d'engagement KZG.

En utilisant la méthode de construction de la section "Comment utiliser KZG pour prouver une seule valeur dans un vecteur", le vérificateur peut construire des engagements pour les polynômes d'origine et de quotient pour chaque polynôme 𝑓ᵢ(𝑥), ce qui donne un total de 𝟐﹡𝑚 engagements KZG. Le vérificateur envoie tous ces engagements comme preuve pour vérification.

Cependant, comme mentionné précédemment, cette approche nécessite la génération de plusieurs preuves, et le vérificateur doit également effectuer plusieurs calculs de vérification. Nous devons trouver un moyen de compresser plusieurs preuves d'engagement.

Fusion des preuves

Le prouveur envoie la preuve [ 𝑞( 𝑠 )]₁ au vérificateur pour vérification.

Les preuves produites par ce schéma se composent d'un engagement, de deux preuves et d'une valeur, avec une taille de données constante. Finalement, après l'optimisation de fusion des preuves dans l'arbre Verkle, l'objet de données vérifiable envoyé au vérificateur comprend ce qui suit :

1. Preuve de taille constante
2. Les données des feuilles à prouver (paires clé-valeur)
3. Les valeurs d'engagement de tous les nœuds sur le chemin de la feuille à la racine (en supposant une largeur d'arbre de 256 avec 2³² nœuds, alors la profondeur moyenne est de 4, nécessitant seulement 3 valeurs d'engagement)

Notez que 𝑥ᵢ et 𝑦ᵢ n'ont pas besoin d'être explicitement fournis; ils peuvent tous être calculés.

5.3.3. performance

En ce qui concerne le schéma de fusion de preuve pour les arbres Verkle, la taille spécifique de la preuve générée est la suivante (L'unité de la ligne est milliard) :

Les données ci-dessus supposent l'utilisation d'un arbre de largeur 256, en employant le schéma d'engagement KZG (avec une taille d'engagement de 48 octets), et maximisent l'utilisation de l'arbre. En pratique, pour des distributions d'informations complètement aléatoires, la profondeur de l'arbre augmenterait d'environ 60 %, et la taille de chaque élément augmenterait de 30 octets. Si le schéma bulletproof est utilisé, alors la taille d'engagement serait de 32 octets.

5.4. Charge de calcul du prouveur et du vérificateur

1. Génération de preuve : Le coût de génération de preuves par le prouveur est lié à la largeur de l'arbre, mais chaque opération atomique nécessite un coût computationnel relativement faible, de sorte que les arbres Verkle avec une largeur comprise entre 256 et 1024 se comportent bien en termes d'algorithmes.
2. Vérification de la preuve : Vitalik a indiqué que l'algorithme de vérification est très rapide et peut généralement être terminé en moins de 100 ms, même lorsqu'il y a plusieurs milliers de valeurs à vérifier.
3. Lors de la mise à jour des arbres Verkle : mettre à jour l'arbre nécessite de recalculer toutes les valeurs d'engagement intermédiaires le long du chemin en raison de modifications des valeurs ou de la structure. Cependant, Vitalik a mentionné que, grâce à certaines propriétés de l'algorithme d'engagement polynomial, il est possible de concevoir une méthode qui précalcule des valeurs d'engagement alternatives et les stocke, réduisant ainsi le coût en temps de calcul lors des mises à jour, ce qui échange essentiellement de l'espace contre du temps.

6. Conclusions

Voici les mots originaux du blog de Vitalik, nous avons ajouté un paragraphe à la fin en guise de complément.

Les arbres Verkle sont une mise à niveau puissante des preuves de Merkle qui permettent des tailles de preuve beaucoup plus petites. Au lieu de devoir fournir tous les "noeuds soeurs" à chaque niveau, le prouveur n'a besoin de fournir qu'une seule preuve qui prouve toutes les relations parent-enfant entre tous les engagements le long des chemins de chaque nœud feuille à la racine. Cela permet de réduire la taille des preuves d'un facteur d'environ 6 à 8 par rapport aux arbres Merkle idéaux, et d'un facteur de plus de 20 à 30 par rapport aux arbres de Patricia hexary que Ethereum utilise aujourd'hui (!!).

Ils nécessitent une cryptographie plus complexe à mettre en œuvre, mais ils offrent la possibilité de gains importants en termes de scalabilité. À moyen terme, les SNARKs peuvent améliorer les choses davantage : nous pouvons soit SNARKer le vérificateur de preuve Verkle déjà efficace pour réduire la taille du témoin à presque zéro, soit revenir à des preuves Merkle SNARKées si/quand les SNARKs deviennent beaucoup plus performants (par exemple grâce à GKR, ou des fonctions de hachage très amicales aux SNARKs, ou des ASICs). Plus loin, la montée de l'informatique quantique forcera un passage à des preuves STARKed Merkle avec des hachages, car elle rend les homomorphismes linéaires dont dépendent les arbres Verkle non sécurisés. Mais pour l'instant, ils nous procurent les mêmes gains en termes de scalabilité que ceux que nous obtiendrions avec des technologies plus avancées, et nous avons déjà tous les outils nécessaires pour les mettre en œuvre efficacement.

À l'heure actuelle, de nombreux clients Ethereum ont fourni la mise en œuvre de l'arbre Verkle et des réseaux de test associés. La communauté discute encore du moment où les arbres Verkle seront lancés sur le réseau principal. Il est probable qu'ils seront mis en œuvre lors d'une mise à jour par fourche dure en 2024 ou 2025. Pour plus d'informations détaillées sur les arbres Verkle sur Ethereum, consultez https://verkle.info/ .

7. Référence

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Preuves de connaissance de divulgation minimale[J]. Journal des sciences informatiques et systèmes, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Engagements de vecteurs et leurs applications[C]//Cryptographie à clé publique - PKC 2013: 16e Conférence internationale sur la pratique et la théorie de la cryptographie à clé publique, Nara, Japon, 26 février - 1er mars 2013. Actes 16. Springer, 2013: 55-72.

Avertissement：

1. Cet article est reproduit à partir de [ZAN], Tous les droits d'auteur appartiennent à l'auteur original [AntChain Open Labs et ZAN]. Si des objections sont soulevées concernant cette réimpression, veuillez contacter le Porte Apprendreéquipe, et ils s'en occuperont rapidement.
2. Clause de non-responsabilité : Les points de vue et opinions exprimés dans cet article sont uniquement ceux de l'auteur et ne constituent aucun conseil en investissement.
3. Les traductions de l'article dans d'autres langues sont effectuées par l'équipe Gate Learn. Sauf mention contraire, la copie, la distribution ou le plagiat des articles traduits est interdite.