Plongez dans l'arbre Verkle pour Ethereum

Par rapport à Merkle Tree, Verkle Tree a été beaucoup amélioré dans la taille Proof en tant qu'élément essentiel de la mise à niveau ETH2.0. Lorsqu'il s'agit de données d'une taille d'un milliard, la preuve Merkle Tree prendra 1 Ko, tandis que la preuve Verkle Tree ne nécessite pas plus de 150 octets.

Le concept Verkle Tree a été proposé en 2018 (Plus de détails peuvent être trouvés ici .). La 23e revue technique de Sin7Y démontrera le principe de Verkle Tree.

Arbre Merkel

Avant de creuser dans Verkle Tree, il est important de comprendre le concept de Merkle Tree. Merkle Tree est un accumulateur commun, qui peut être utilisé pour prouver qu'un élément existe dans l'accumulateur, comme illustré dans la figure suivante :

Pour prouver que (clé : valeur) = (06 : 32) existe dans l'arbre (marqué en vert), la preuve doit contenir tous les nœuds marqués en rouge dans la figure.

Le vérificateur peut calculer la racine selon la méthode illustrée à la figure 1, puis la comparer avec la racine attendue (marquée en gris).

Il est prévisible qu'avec l'augmentation de la profondeur et de la largeur de l'arbre, la taille de la preuve sera également plus grande (pour branched-2, la complexité est log_2(n) , tandis que pour branched-k, c'est (k−1)log_k (n) .

De plus, le vérificateur doit effectuer un grand nombre de calculs de hachage du niveau de base au niveau supérieur. Ainsi, l'augmentation de la profondeur et de la largeur de l'Arbre conduit à l'augmentation de la charge de travail du vérificateur, ce qui est inacceptable.

Arbre Verkle - Concept

Le simple fait d'augmenter la largeur de l'arbre peut réduire sa profondeur, mais la taille de la preuve ne sera pas réduite car la taille de la preuve passe de log_2(n) à (k−1)log_k(n) .

Autrement dit, pour chaque couche, le prouveur doit fournir (k−1) informations de nœud supplémentaires. Dans l'article Verkle Tree, John Kuszmaul a mentionné un schéma pour réduire la complexité de la preuve à logk(n) .

Si nous fixons k=1024 , la preuve sera réduite de log_2(k) = 10 fois .

La conception de l'arbre Verkle est illustrée comme suit :

Pour chaque nœud, il y a deux informations : (1) valeur ; (2) preuve d'existence π . Par exemple, la marque verte (H(k,v),π_03) montre que H(k,v) existe dans l'engagement C_0 et π_03 est la preuve de cet argument.

De même, (C_0,π_0) signifie que C_0 existe dans l'engagement C_Root et π_0 est la preuve de cet argument.

Dans l'article Verkle Tree, la méthode d'un tel engagement d'existence est appelée Engagement vectoriel . Si le schéma d'engagement Vector est utilisé pour exécuter l'engagement d'existence pour les données d'origine, la complexité de la preuve avec O(1 ) sera obtenue tandis que la complexité de la preuve de construction et celle de la preuve de mise à jour sont O(n^2),O(n) respectivement.

Par conséquent, pour trouver un équilibre, le schéma K-ary Verkle Tree est utilisé dans l'article Verkle Tree (comme illustré à la figure 2) pour rendre la complexité de la construction de la preuve, de la mise à jour de la preuve et de la preuve en O(kn),O(klogk n ),O(logk n) respectivement.

La comparaison des performances spécifiques est présentée dans le tableau 1 :

Dans cet article, nous n'avons pas l'intention de fournir une introduction détaillée à certains schémas d'engagement de vecteurs spécifiques, que John Kuszmaul a bien expliqués dans son article.

Heureusement, par rapport à l'engagement vectoriel, nous disposons d'un outil plus efficace appelé engagement polynomial.

Étant donné un groupe du jeu de coordonnées (c_0,c_1,....,c_n) et un jeu de valeurs (y_1,y_2,....,y_n) , vous pouvez construire un polynôme ( interpolation de Lagrange ), satisfaisant P(c_i )=y_i , et effectuer un engagement sur ce polynôme.

KZG10 et IPA sont des schémas d'engagement polynomiaux courants (à ce stade, l'engagement est un point sur la courbe elliptique, généralement d'une taille comprise entre 32 et 48 octets).

Base

KZG pour point unique

Prenez KZG10 comme exemple. Pour le polynôme P(x) , nous utilisons [P(s)]_1 pour représenter l'engagement polynomial.

Comme on le sait, pour P(x) , si P(z)=y , alors (x−z)|(P(x)−y) . C'est-à-dire que si on pose Q(x)=(P (x)−y)/(x−z) , alors Q(x) est un polynôme.

Maintenant, nous générons une preuve pour que P(x)P(x) satisfasse P(z)=yP(z)=y. Autrement dit, calculez [Q(s)]1[Q(s)]1 et envoyez-le au vérificateur, qui doit vérifier :

Parce que s est un point choisi au hasard dans le domaine fini F, la probabilité d'un mauvais comportement réussi du démonstrateur est degré(Q)/P ( lemme de Schwartz–Zippel ).

KZG pour plusieurs points

Maintenant, nous voulons prouver que les valeurs du polynôme P(x) sur (z0,z1,....,zk−1) sont (y1,y2,....,yk−1) , respectivement. Il faut donc définir deux polynômes :

Selon la description mentionnée ci-dessus, nous devons satisfaire V(x)|(P(x)−I(x)) . Autrement dit, il existe un polynôme Q(x) , satisfaisant :

Par conséquent, le prouveur doit fournir les engagements [P(s)]_1,[Q(s)]_1 pour P(x) et Q(x) , et envoyer les engagements au vérificateur.

Le vérificateur calcule [I(s)]_1,[V(s)]_2 localement et vérifie l'équation :

Il est clair que la taille de la preuve est constante quel que soit le nombre de points. Si nous choisissons la courbe BLS12-381, la taille de preuve n'est que de 48 octets, ce qui est très efficace.

Verkle Tree - ETH

Par rapport à Merkle Tree, dans lequel pour prouver l'existence d'un élément, le prouveur doit toujours fournir la preuve avec une taille O (log_2n) , Verkle Tree a fait une grande amélioration sur la taille de la preuve.

Voyons un exemple simple de Verkle Tree.

On peut voir que, à l'instar de la structure Merkle Patricia Tree, les nœuds peuvent être divisés en trois types - nœud vide, nœud interne et nœud feuille.

La largeur de chaque arbre de nœud interne est de 16 (0000->1111 en hexadécimal). Pour prouver que l'état du nœud feuille est (0101 0111 1010 1111 -> 1213), nous devons effectuer l'engagement vers le nœud interne A et le nœud interne B :

1. Prouver que la valeur de l'engagement du nœud interne B est le hachage (0101 0111 1010 1111, 1213) à l'index 1010.

   
   

2. Prouver que la valeur de l'engagement du nœud interne A est le hachage (cm_B) à l'index 0111.

   
   

3. Prouver que la valeur de l'engagement du nœud racine est le hachage (cm_A) à l'index 0101 ;

Utilisez C_0(InnernodeB),C_1(InnernodeA),C_2(Root) pour représenter les engagements mentionnés ci-dessus et les faire correspondre au polynôme f_i(x) respectivement.

Le prouveur doit donc prouver :

Compresser pour plusieurs polys

Pour simplifier, nous utiliserons z_i pour représenter l'index.

Le démonstrateur doit prouver que pour l'ensemble de polynômes f_0(x),f_1(x),....,f_m−1(x) , il satisfait les conditions suivantes aux points z_0,z_1,....,z_m− 1 , respectivement :
D'après la description précédente (KZG pour Single point), pour chaque polynôme, il existe un polynôme quotient satisfaisant :
Le prouveur doit effectuer l'engagement sur le polynôme d'origine et le polynôme quotient, et l'envoyer au vérificateur :

Le vérificateur exécute la vérification :
Il est évident que nous ne voulons pas que le vérificateur exécute autant d'opérations d'appariement (c'est cher). Par conséquent, nous devons exécuter une compression comme suit.

Générez des nombres aléatoires r_0,r_1,....,r_m−1 , et rassemblez les polynômes quotient ci-dessus :
Supposons que si et seulement si chaque q_i(x) est un polynôme, g(x) sera un polynôme (la probabilité que les fractions entre q_i(x ) soient exactement décalées est très faible à cause des nombres aléatoires).

Le prouveur effectue l'engagement sur le polynôme g(x) et envoie [g(s)]_1 au vérificateur.

Ensuite, laissez le vérificateur croire que [g(s)]_1 est l'engagement envers le polynôme g(x) .

Observez la forme du polynôme g(x)g(x), qui peut s'écrire :

Choisissez une valeur tt au hasard et il y a :

Définissez le polynôme :

Son engagement peut être calculé selon la méthode suivante :

Alors la valeur du polynôme h(x)−g(x)h(x)−g(x) au point tt est :

Calculer le polynôme quotient q(x)=(h(x)−g(x)−y)/(x−z) .

Calculer l'engagement π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1, et l'envoyer au vérificateur.

Le vérificateur effectue la vérification suivante :

1. Calculer

   

2. Vérifier

   

Propriétés clés

1. N'importe quel nombre de points peut être prouvé en utilisant ce schéma sans changer la taille de la preuve. (Pour chaque engagement, il existe une preuve π .)

   
   

2. La valeur de y_i n'a pas besoin d'être fournie explicitement car il s'agit du hachage de la valeur de la couche suivante.

   
   

3. La valeur de x_i n'a pas besoin d'être fournie explicitement car elle peut être jugée à partir de Key.

   
   

4. L'information publique utilisée comprend le couple clé/valeur à prouver et les engagements correspondants du niveau de base au niveau supérieur.

Références

1. Dankrad Feist, « PCS multiproofs using random evaluation », https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html , consulté le : 2022-05-10.

   
   

2. Vitalik Buterin, « Verkle trees », https://vitalik.ca/general/2021/06/18/verkle.html , consulté le : 2022-05-10.

   
   

3. John Kuszmaul, « Verkle Trees », https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf , consulté le : 2022-05-10.