Plongez dans l'arbre Verkle pour Ethereum by@sin7y
1,712 lectures

Plongez dans l'arbre Verkle pour Ethereum

2022/05/20
par @sin7y 1,712 lectures
tldt arrow
FR
Read on Terminal Reader

Trop long; Pour lire

Verkle Tree est un accumulateur commun, qui peut être utilisé pour prouver qu'un élément existe dans les accumulateurs. Par rapport à l'arbre Merkle, VerKle Tree a été beaucoup amélioré dans la taille Proof en tant qu'élément essentiel de la mise à niveau ETH2.0. La 23e revue technique de Sin7Y démontrera le principe du principe. Lorsqu'il s'agit de données d'une taille d'un milliard, la preuve de l'arbre de Merkle prendra 1 Ko, tandis que la preuve de l'arbre de Verkle n'aura pas besoin de plus de 150 octets.

People Mentioned

Mention Thumbnail

Company Mentioned

Mention Thumbnail

Coin Mentioned

Mention Thumbnail
featured image - Plongez dans l'arbre Verkle pour Ethereum
Sin7Y HackerNoon profile picture

@sin7y

Sin7Y

Sin7Y is a tech team that explores layer 2, cross-chain,...

react to story with heart

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 :

Figure 1 : Arbre de Merkle

Figure 1 : Arbre de Merkle

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 :

Figure 2. Arbre de Verkle

Figure 2. Arbre de Verkle

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 :

image

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 :

image

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 :

image

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 :

image

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 :

image

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.

Figure 3. Arbre de Verkle pour ETH

Figure 3. Arbre de Verkle pour ETH

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 :

image

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 :

image
D'après la description précédente (KZG pour Single point), pour chaque polynôme, il existe un polynôme quotient satisfaisant :
image
Le prouveur doit effectuer l'engagement sur le polynôme d'origine et le polynôme quotient, et l'envoyer au vérificateur :

image

Le vérificateur exécute la vérification :

image
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 :

image
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 :

image

Choisissez une valeur tt au hasard et il y a :

image

Définissez le polynôme :

image

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

image

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

image

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

    image

  2. Vérifier

    image

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.

HISTOIRES CONNEXES

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa