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   .). La 23e revue technique de Sin7Y démontrera le principe de Verkle Tree. ici   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   , tandis que pour branched-k, c'est   . log_2(n) (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   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 à   . (k−1) logk(n)  Si nous fixons   , la preuve sera réduite de   . k=1024 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   montre que   existe dans l'engagement   et   est la preuve de cet argument. π (H(k,v),π_03) H(k,v) C_0 π_03  De même,   signifie que   existe dans l'engagement   et   est la preuve de cet argument. (C_0,π_0) C_0 C_Root π_0  Dans l'article Verkle Tree, la méthode d'un tel engagement d'existence est appelée   . 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   ) sera obtenue tandis que la complexité de la preuve de construction et celle de la preuve de mise à jour sont   respectivement. Engagement vectoriel O(1 O(n^2),O(n)  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   respectivement. O(kn),O(klogk n ),O(logk n)  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   et un jeu de valeurs   , vous pouvez construire un polynôme (   ), satisfaisant   , et effectuer un engagement sur ce polynôme. (c_0,c_1,....,c_n) (y_1,y_2,....,y_n) interpolation de Lagrange P(c_i )=y_i    et   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). KZG10 IPA   Base   KZG pour point unique  Prenez KZG10 comme exemple. Pour le polynôme   , nous utilisons   pour représenter l'engagement polynomial. P(x) [P(s)]_1  Comme on le sait, pour   , si   , alors   . C'est-à-dire que si on pose   , alors   est un polynôme. P(x) P(z)=y (x−z)|(P(x)−y) Q(x)=(P (x)−y)/(x−z) Q(x)  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   sur   sont   , respectivement. Il faut donc définir deux polynômes : P(x) (z0,z1,....,zk−1) (y1,y2,....,yk−1)  Selon la description mentionnée ci-dessus, nous devons satisfaire   . Autrement dit, il existe un polynôme   , satisfaisant : V(x)|(P(x)−I(x)) Q(x)  Par conséquent, le prouveur doit fournir les engagements   pour   et   , et envoyer les engagements au vérificateur. [P(s)]_1,[Q(s)]_1 P(x) Q(x)  Le vérificateur calcule   localement et vérifie l'équation : [I(s)]_1,[V(s)]_2  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   , Verkle Tree a fait une grande amélioration sur la taille de la preuve. O (log_2n)  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 :  Prouver que la valeur de l'engagement du nœud interne B est le hachage (0101 0111 1010 1111, 1213) à l'index 1010.  Prouver que la valeur de l'engagement du nœud interne A est le hachage (cm_B) à l'index 0111.  Prouver que la valeur de l'engagement du nœud racine est le hachage (cm_A) à l'index 0101 ;  Utilisez   pour représenter les engagements mentionnés ci-dessus et les faire correspondre au polynôme   respectivement. C_0(InnernodeB),C_1(InnernodeA),C_2(Root) f_i(x)  Le prouveur doit donc prouver :   Compresser pour plusieurs polys  Pour simplifier, nous utiliserons   pour représenter l'index. z_i  Le démonstrateur doit prouver que pour l'ensemble de polynômes   , il satisfait les conditions suivantes aux points   , 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 : f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m− 1  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   , et rassemblez les polynômes quotient ci-dessus :  Supposons que si et seulement si chaque   est un polynôme,   sera un polynôme (la probabilité que les fractions entre   ) soient exactement décalées est très faible à cause des nombres aléatoires). r_0,r_1,....,r_m−1 q_i(x) g(x) q_i(x  Le prouveur effectue l'engagement sur le polynôme   et envoie   au vérificateur. g(x) [g(s)]_1  Ensuite, laissez le vérificateur croire que   est l'engagement envers le polynôme   . [g(s)]_1 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   et l'envoyer au vérificateur. π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1,  Le vérificateur effectue la vérification suivante :   Calculer   Vérifier   Propriétés clés  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   .) π  La valeur de   n'a pas besoin d'être fournie explicitement car il s'agit du hachage de la valeur de la couche suivante. y_i  La valeur de   n'a pas besoin d'être fournie explicitement car elle peut être jugée à partir de Key. x_i  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  Dankrad Feist, « PCS multiproofs using random evaluation »,   , consulté le : 2022-05-10. https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html  Vitalik Buterin, « Verkle trees »,   , consulté le : 2022-05-10. https://vitalik.ca/general/2021/06/18/verkle.html  John Kuszmaul, « Verkle Trees »,   , consulté le : 2022-05-10. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Ethereum

Twitter

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Cet audio est produit dans la langue originale de l'histoire !

Trop long; Pour lire

Plongez dans l'arbre Verkle pour Ethereum

Plongez dans l'arbre Verkle pour Ethereum

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Guide de l'architecte pour créer une architecture de référence pour un datalake IA/ML

Naviguer sur les eaux : développer des applications RAG de qualité production avec des lacs de données

Le guide complet pour réussir une migration vers le cloud : stratégies et bonnes pratiques

Nomades numériques, écoutez : ce que vous devez savoir sur le nouveau visa DTV de la Thaïlande

Guide de l'architecte pour créer une architecture de référence pour un datalake IA/ML

Naviguer sur les eaux : développer des applications RAG de qualité production avec des lacs de données

Le guide complet pour réussir une migration vers le cloud : stratégies et bonnes pratiques

Nomades numériques, écoutez : ce que vous devez savoir sur le nouveau visa DTV de la Thaïlande

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps