Site icon Crypto Week

Arborescence Verkle | Blog de la Fondation Ethereum

Un arbre Verkle est un schéma d’engagement qui fonctionne comme un arbre Merkle, mais a des témoins beaucoup plus petits. Cela fonctionne en remplaçant les hachages dans un arbre de Merkle par un engagement de vecteur, ce qui rend les facteurs de ramification plus larges plus efficaces.

Merci à Kevaundray Wedderburn pour ses commentaires sur le message.

Aperçu

Pour plus de détails sur le fonctionnement des arbres verkle, voir :


L’objectif de cet article est d’expliquer l’agencement concret du projet d’arbre verkle EIP. Il est destiné aux développeurs clients qui souhaitent implémenter des arborescences verkle et qui recherchent une introduction avant d’approfondir l’EIP.

Les arbres Verkle introduisent un certain nombre de changements dans la structure arborescente. Les changements les plus significatifs sont :

  • un passage de clés de 20 octets à des clés de 32 octets (à ne pas confondre avec des adresses de 32 octets, qui est un changement distinct) ;
  • la fusion des tentatives de compte et de stockage ; et enfin
  • L’introduction du verkle trie lui-même, qui utilise des engagements vectoriels au lieu de hachages.

Comme schéma d’engagement vectoriel pour l’arbre verkle, nous utilisons Les engagements de Pedersen. Les engagements de Pedersen sont basés sur des courbes elliptiques. Pour une introduction aux engagements de Pedersen et comment les utiliser comme engagements polynomiaux ou vectoriels à l’aide des arguments de produit interne, voir ici.

La courbe que nous utilisons est Bandersnatch. Cette courbe a été choisie parce qu’elle est performante, et aussi parce qu’elle permettra aux SNARK efficaces dans BLS12_381 de raisonner sur l’arbre verkle à l’avenir. Cela peut être utile pour les cumuls ainsi que pour permettre une mise à niveau où tous les témoins peuvent être compressés dans un SNARK une fois que cela devient pratique, sans avoir besoin d’une autre mise à jour d’engagement.

L’ordre de la courbe/la taille du champ scalaire de bandersnatch est p = 13108968793781547619861935127046491459309155893440570251786403306729687672801, qui est un nombre premier de 253 bits. En conséquence, nous ne pouvons nous engager en toute sécurité que sur des chaînes de bits d’au plus 252 bits, sinon le champ déborde. Nous avons choisi un facteur de branchement (largeur) de 256 pour l’arbre verkle, ce qui signifie que chaque engagement peut s’engager jusqu’à 256 valeurs de 252 bits chacune (ou pour être précis, des entiers jusqu’à p – 1). Nous écrivons ceci comme Commettre(v₀, v₁, …, v₂₅₅) s’engager sur la liste v de longueur 256.

Disposition de l’arbre verkle

L’un des objectifs de conception avec l’EIP verkle tree est de rendre les accès aux positions voisines (par exemple, le stockage avec presque la même adresse ou des morceaux de code voisins) peu coûteux à accéder. Pour ce faire, une clé est constituée d’un tige de 31 octets et un suffixe d’un octet pour un total de 32 octets. Le schéma de clé est conçu pour que les emplacements de stockage « proches » soient mappés à la même racine et à un suffixe différent. Pour plus de détails, veuillez consulter le Projet EIP.

L’arbre verkle lui-même est alors composé de deux types de nœuds :

  • Nœuds d’extensionqui représentent 256 valeurs avec le même radical mais des suffixes différents
  • Nœuds internesqui ont jusqu’à 256 enfants, qui peuvent être d’autres nœuds internes ou des nœuds d’extension.

L’engagement envers un nœud d’extension est un engagement envers un vecteur à 4 éléments ; les positions restantes seront 0. C’est :

C₁ et C₂ sont deux engagements supplémentaires qui s’engagent sur toutes les valeurs dont la racine est égale à tige. La raison pour laquelle nous avons besoin d’engagements est que les valeurs ont 32 octets, mais nous ne pouvons stocker que 252 bits par élément de champ. Un seul engagement ne suffirait donc pas à stocker 256 valeurs. Ainsi, à la place, C₁ stocke les valeurs des suffixes 0 à 127, et C₂ stocke 128 à 255, où les valeurs sont divisées en deux afin de s’adapter à la taille du champ (nous y reviendrons plus tard.)

L’extension ainsi que les engagements C₁ et C₂ sont appelés « arbre d’extension et de suffixe » (EaS en abrégé).


Figure 1 Représentation d’une promenade à travers un arbre verkle pour la clé 0xfe0002abcd..ff04: le chemin passe par 3 nœuds internes avec 256 enfants chacun (254, 0, 2), un nœud d’extension représentant abcd..ff et les deux engagements d’arborescence de suffixes, y compris la valeur de 04, v₄. Notez que tige est en fait les 31 premiers octets de la clé, y compris le chemin à travers les nœuds internes.

Engagement envers les valeurs nœuds feuilles

Chaque nœud d’arbre d’extension et de suffixe contient 256 valeurs. Parce qu’une valeur a une largeur de 256 bits et que nous ne pouvons stocker que 252 bits en toute sécurité dans un élément de champ, quatre bits seraient perdus si nous essayions simplement de stocker une valeur dans un élément de champ.

Pour contourner ce problème, nous avons choisi de partitionner le groupe de 256 valeurs en deux groupes de 128 valeurs chacun. Chaque valeur de 32 octets d’un groupe est divisée en deux valeurs de 16 octets. Ainsi, une valeur vᵢ∈ ?₃₂ est transformée en v⁽ˡᵒʷᵉʳ⁾ᵢ ∈ ?₁₆ et v⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ ?₁₆ tel que V⁽ˡᵒʷᵉʳ⁾ᵢ ++ V⁽ᵘᵖᵖᵉʳ⁾ᵢ = Vᵢ.

Un « marqueur de feuille » est ajouté au v⁽ˡᵒʷᵉʳ⁾ᵢ, pour faire la différence entre une feuille qui n’a jamais été consultée et une feuille qui a été écrasée par des 0. Aucune valeur n’est jamais supprimée d’un arbre verkle. Ceci est nécessaire pour les programmes d’expiration d’état à venir. Ce marqueur est défini au 129e bit, c’est-à-dire V⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = V⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ si Vᵢ a été accessible auparavant, et v⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0 si Vᵢ n’a jamais été accessible.

Les deux engagements C₁ et C₂ sont alors définis comme

Engagement des nœuds d’extension

L’engagement à un nœud d’extension est composé d’un « marqueur d’extension », qui est juste le nombre 1, les deux engagements de sous-arbre C₁ et C₂, et le tige de la clé menant à ce nœud d’extension.

Contrairement aux nœuds d’extension de l’arbre Merkle-Patricia, qui ne contiennent que la section de la clé qui relie le nœud interne parent au nœud interne enfant, la tige couvre toute la clé jusqu’à ce point. En effet, les arbres verkle sont conçus avec des preuves sans état à l’esprit : si une nouvelle clé est insérée qui « divise » l’extension en deux, l’aîné n’a pas besoin d’être mis à jour, ce qui permet une preuve plus petite.

Engagement des nœuds internes

Les nœuds internes ont la méthode de calcul la plus simple pour leurs engagements : le nœud est vu comme un vecteur de 256 valeurs, qui sont la (représentation du champ de) l’engagement racine de chacun de leurs 256 sous-arbres. L’engagement pour un sous-arbre vide est 0. Si le sous-arbre n’est pas vide, alors l’engagement pour le nœud interne est

où les Cᵢ sont les enfants du nœud interne, et 0 si un enfant est vide.

Insertion dans l’arbre

La figure 2 est une illustration du processus d’insertion d’une nouvelle valeur dans l’arbre, qui devient intéressant lorsque les tiges entrent en collision sur plusieurs octets initiaux.

Figure 2 La valeur v₁₉₂ est insérée à l’emplacement 0000010000…0000 dans un arbre verkle contenant uniquement la valeur v₁₂₇ à l’emplacement 0000000000…0000. Étant donné que les tiges diffèrent au troisième octet, deux nœuds internes sont ajoutés jusqu’à l’octet différent. Ensuite, un autre arbre « extension et suffixe » est inséré, avec une racine complète de 31 octets. Le nœud initial est intact et C²₀ a la même valeur que C⁰₀ avant l’insertion.

Arbres moins profonds, épreuves plus petites

La structure arborescente verkle crée des arbres moins profonds, ce qui réduit la quantité de données stockées. Sa véritable puissance, cependant, vient de la capacité de produire des preuves plus petites, c’est-à-dire des témoins. Cela sera expliqué dans le prochain article.

Source https://blog.ethereum.org/en/2021/12/02/verkle-tree-structure

Quitter la version mobile