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

Making security fun one episode at a time

Plongez dans l'arbre Verkle pour Ethereum

Plongez dans l'arbre Verkle pour Ethereum

Trop long; Pour lire

People Mentioned

Company Mentioned

Coin Mentioned

Sin7Y

About Author

ÉTIQUETTES

Languages

CET ARTICLE A ÉTÉ PARU DANS...

Plongez dans l'arbre Verkle pour Ethereum

Trop long; Pour lire

People Mentioned

Company Mentioned

Coin Mentioned

Sin7Y

About Author

ÉTIQUETTES

Languages

CET ARTICLE A ÉTÉ PARU DANS...

HISTOIRES CONNEXES