En comparación con Merkle Tree, Verkle Tree se ha mejorado mucho en el tamaño de prueba como parte fundamental de la actualización ETH2.0. Cuando se trata de datos con un tamaño de mil millones, la prueba de Merkle Tree tomará 1kB, mientras que la prueba de Verkle Tree solo necesita no más de 150 bytes.  El concepto Verkle Tree se propuso en 2018 (se pueden encontrar más detalles   ). La revisión técnica número 23 de Sin7Y demostrará el principio de Verkle Tree. aquí   Árbol Merkle  Antes de profundizar en Verkle Tree, es importante comprender el concepto de Merkle Tree. Merkle Tree es un acumulador común, que se puede usar para demostrar que existe un elemento en el acumulador, como se muestra en la siguiente figura:   Para probar que (clave: valor) = (06: 32) existe en el Árbol (marcado en verde), la Prueba debe contener todos los nodos marcados en rojo en la figura.  El verificador puede calcular la Raíz de acuerdo con el método que se muestra en la Figura 1 y luego compararla con la Raíz esperada (marcada en gris).  Es predecible que con la profundidad y el ancho del árbol aumentando, el tamaño de la prueba también será mayor (para branched-2, la complejidad es   , mientras que para branched-k, es   . log_2(n) (k−1)log_k (n)  Además, el verificador necesita realizar una gran cantidad de cálculos Hash desde el nivel básico hasta el nivel superior. Por lo tanto, el aumento de la profundidad y el ancho del Árbol conduce al aumento de la carga de trabajo del verificador, lo cual es inaceptable.   Árbol Verkle - Concepto  Simplemente aumentar el ancho del árbol puede reducir su profundidad, pero el tamaño de la prueba no se reducirá porque el tamaño de la prueba cambia del   original a   . log_2(n) (k−1)log_k(n)  Es decir, para cada capa, el probador debe proporcionar   información de nodo adicional. En el artículo Verkle Tree, John Kuszmaul mencionó un esquema para reducir la complejidad de la prueba a   . (k−1) logk(n)  Si establecemos   , la prueba se reducirá   . k=1024 log_2(k) = 10 veces  El diseño de Verkle Tree se muestra de la siguiente manera:   Para cada nodo, hay dos piezas de información: (1) valor; (2) prueba de existencia   . Por ejemplo, la marca verde   muestra que   existe en el compromiso   y   es la prueba de este argumento. π (H(k,v),π_03) H(k,v) C_0 π_03  De manera similar,   significa que   existe en el compromiso   y   es la prueba de este argumento. (C_0,π_0) C_0 C_Root π_0  En el artículo Verkle Tree, el método de tal compromiso de existencia se llama   . Si se utiliza el esquema de compromiso Vector para ejecutar el compromiso de existencia para los datos originales, se obtendrá la Prueba con complejidad   ), mientras que la complejidad de la Prueba de construcción y la de la Prueba de actualización son   respectivamente. compromiso vectorial O(1 O(n^2),O(n)  Por lo tanto, para lograr un equilibrio, el esquema K-ary Verkle Tree se usa en el artículo Verkle Tree (como se muestra en la Figura 2) para hacer que la complejidad de la construcción Demostración, actualización Demostración y Demostración sea   respectivamente. O(kn),O(klogk n ),O(logk n)  La comparación de rendimiento específico se muestra en la Tabla 1:  En este artículo, no pretendemos proporcionar una introducción detallada a algunos esquemas de compromiso de vector específicos, que John Kuszmaul ha explicado bien en su artículo.  Afortunadamente, en comparación con el vector de compromiso, tenemos una herramienta más eficiente llamada polinomio de compromiso.  Dado un grupo del conjunto de coordenadas   y un conjunto de valores   , puede construir un polinomio (   ), que satisface   , y realice un compromiso con este polinomio. (c_0,c_1,....,c_n) (y_1,y_2,....,y_n) interpolación de Lagrange P(c_i )=y_i    e   son esquemas de compromiso polinómico comunes (en este punto, el compromiso es un punto en la curva elíptica, típicamente entre 32 y 48 bytes de tamaño). KZG10 IPA   Base   KZG para punto único  Tome KZG10 como ejemplo. Para el polinomio   , usamos   para representar el compromiso del polinomio. P(x) [P(s)]_1  Como todos sabemos, para   , si   , entonces   . Es decir, si ponemos   , entonces   es un polinomio. P(x) P(z)=y (x−z)|(P(x)−y) Q(x)=(P (x)−y)/(x−z) Q(x)  Ahora, generamos una prueba para P(x)P(x) para satisfacer P(z)=yP(z)=y. Es decir, calcular [Q(s)]1[Q(s)]1 y enviarlo al verificador, quien debe verificar:  Debido a que s es un punto elegido al azar en el dominio finito F, la probabilidad de que el probador tenga un mal comportamiento exitoso es grado (Q) / P (   ). lema de Schwartz-Zippel   KZG para múltiples puntos  Ahora, queremos probar que los valores del polinomio   en   son   , respectivamente. Por lo tanto, necesitamos definir dos polinomios: P(x) (z0,z1,....,zk−1) (y1,y2,....,yk−1)  De acuerdo con la descripción mencionada anteriormente, necesitamos satisfacer   . Es decir, existe un polinomio   que satisface: V(x)|(P(x)−I(x)) Q(x)  Por lo tanto, el Demostrante debe proporcionar los compromisos   para   y   y enviar los compromisos al verificador. [P(s)]_1,[Q(s)]_1 P(x) Q(x)  El verificador calcula   localmente y verifica la ecuación: [I(s)]_1,[V(s)]_2  Está claro que el tamaño de la prueba es constante sin importar cuántos puntos haya. Si elegimos la curva BLS12-381, el tamaño de prueba es de solo 48 bytes, lo cual es muy eficiente.   Árbol Verkle - ETH  En comparación con Merkle Tree, en el que para probar la existencia de un elemento, el probador aún necesita proporcionar la prueba con un tamaño   , Verkle Tree ha mejorado mucho el tamaño de la prueba. O (log_2n)  Veamos un ejemplo simple de Verkle Tree.   Se puede ver que, de manera similar a la estructura Merkle Patricia Tree, los nodos se pueden dividir en tres tipos: nodo vacío, nodo interno y nodo de hoja.  El ancho de cada árbol de nodos internos es 16 (0000->1111 en hexadecimal). Para probar que el estado del nodo hoja es (0101 0111 1010 1111 -> 1213), necesitamos realizar el compromiso con el nodo interno A y el nodo interno B:  Demuestre que el valor del compromiso del nodo interno B es hash (0101 0111 1010 1111, 1213) en el índice 1010.  Demuestre que el valor del compromiso del nodo interno A es hash (cm_B) en el índice 0111.  Demuestre que el valor del compromiso del nodo Root es hash (cm_A) en el índice 0101;  Utilice   para representar los compromisos mencionados anteriormente y corresponderlos con el polinomio   respectivamente. C_0(InnernodeB),C_1(InnernodeA),C_2(Root) f_i(x)  Por lo tanto, el Prover necesita probar:   Comprimir para Múltiples Polis  Para hacerlo más fácil, usaremos   para representar el índice. z_i  El probador necesita probar que para el conjunto polinomial   , satisface las siguientes condiciones en los puntos   , respectivamente:  De acuerdo con la descripción anterior (KZG para punto único), para cada polinomio existe un polinomio cociente que satisface:  Prover necesita realizar el compromiso con el polinomio original y el polinomio cociente, y enviarlo al Verificador: f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m− 1  El verificador ejecuta la verificación:  Es obvio que no queremos que el verificador ejecute tantas operaciones de emparejamiento (es caro). Por lo tanto, necesitamos ejecutar Compress de la siguiente manera.  Genere algunos números aleatorios   y reúna los polinomios de cociente anteriores:  Suponga que si y solo si cada   es un polinomio,   será un polinomio (la probabilidad de que las fracciones entre   ) se compensen exactamente es muy baja debido a los números aleatorios). r_0,r_1,....,r_m−1 q_i(x) g(x) q_i(x  El probador realiza el compromiso con el polinomio   y envía   al verificador. g(x) [g(s)]_1  A continuación, permita que el verificador crea que   es el compromiso con el polinomio   . [g(s)]_1 g(x)  Observe la forma del polinomio g(x)g(x), que se puede escribir como:  Elija un valor tt al azar y hay:  Defina el polinomio:  Su compromiso se puede calcular con el siguiente método:  Entonces el valor del polinomio h(x)−g(x)h(x)−g(x) en el punto tt es:  Calcular el polinomio cociente   . q(x)=(h(x)−g(x)−y)/(x−z)  Calcular el compromiso   y enviarlo al verificador. π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1,  El verificador realiza la siguiente verificación:   Calcular   Verificar   Propiedades clave  Se puede probar cualquier número de puntos utilizando este esquema sin cambiar el tamaño de la prueba. (Para cada compromiso, hay una prueba   ). π  No es necesario proporcionar explícitamente el valor de   , ya que es el hash del valor de la siguiente capa. y_i  No es necesario proporcionar explícitamente el valor de   , ya que se puede juzgar a partir de la clave. x_i  La información pública utilizada incluye el par clave/valor a probar y los compromisos correspondientes desde el nivel básico hasta el nivel superior.   Referencias  Dankrad Feist, "PCS multiproofs usando evaluación aleatoria",   , consultado: 2022-05-10. https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html  Vitalik Buterin, "Árboles de Verkle",   , consultado: 2022-05-10. https://vitalik.ca/general/2021/06/18/verkle.html  John Kuszmaul, "Verkle Trees",   , consultado: 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

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Sumérjase profundamente en Verkle Tree para Ethereum

Sumérjase profundamente en Verkle Tree para Ethereum

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

La fuga rápida del sistema Claude Sonnet 3.5: un análisis forense

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

La fuga rápida del sistema Claude Sonnet 3.5: un análisis forense

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

De los foros a los feeds: cómo los algoritmos de las redes sociales influyen en la interacción digital

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps