4,000 lecturas

Sumérjase profundamente en Verkle Tree para Ethereum

por Sin7Y2022/05/20

Demasiado Largo; Para Leer

Verkle Tree es un acumulador común, que se puede usar para probar que existe un elemento en los acumuladores. 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. La revisión técnica número 23 de Sin7Y demostrará el principio del principio. 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.

People Mentioned

Company Mentioned

Coin Mentioned

featured image - Sumérjase profundamente en Verkle Tree para Ethereum

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 aquí ). La revisión técnica número 23 de Sin7Y demostrará el principio de Verkle Tree.

Á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 log_2(n) , mientras que para branched-k, es (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 log_2(n) original a (k−1)log_k(n) .

Es decir, para cada capa, el probador debe proporcionar (k−1) información de nodo adicional. En el artículo Verkle Tree, John Kuszmaul mencionó un esquema para reducir la complejidad de la prueba a logk(n) .

Si establecemos k=1024 , la prueba se reducirá 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 (H(k,v),π_03) muestra que H(k,v) existe en el compromiso C_0 y π_03 es la prueba de este argumento.

De manera similar, (C_0,π_0) significa que C_0 existe en el compromiso C_Root y π_0 es la prueba de este argumento.

En el artículo Verkle Tree, el método de tal compromiso de existencia se llama compromiso vectorial . Si se utiliza el esquema de compromiso Vector para ejecutar el compromiso de existencia para los datos originales, se obtendrá la Prueba con complejidad O(1 ), mientras que la complejidad de la Prueba de construcción y la de la Prueba de actualización son O(n^2),O(n) respectivamente.

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 O(kn),O(klogk n ),O(logk n) respectivamente.

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 (c_0,c_1,....,c_n) y un conjunto de valores (y_1,y_2,....,y_n) , puede construir un polinomio ( interpolación de Lagrange ), que satisface P(c_i )=y_i , y realice un compromiso con este polinomio.

KZG10 e IPA 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).

Base

KZG para punto único

Tome KZG10 como ejemplo. Para el polinomio P(x) , usamos [P(s)]_1 para representar el compromiso del polinomio.

Como todos sabemos, para P(x) , si P(z)=y , entonces (x−z)|(P(x)−y) . Es decir, si ponemos Q(x)=(P (x)−y)/(x−z) , entonces Q(x) es un polinomio.

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 P(x) en (z0,z1,....,zk−1) son (y1,y2,....,yk−1) , respectivamente. Por lo tanto, necesitamos definir dos polinomios:

De acuerdo con la descripción mencionada anteriormente, necesitamos satisfacer V(x)|(P(x)−I(x)) . Es decir, existe un polinomio Q(x) que satisface:

Por lo tanto, el Demostrante debe proporcionar los compromisos [P(s)]_1,[Q(s)]_1 para P(x) y Q(x) y enviar los compromisos al verificador.

El verificador calcula [I(s)]_1,[V(s)]_2 localmente y verifica la ecuación:

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 O (log_2n) , Verkle Tree ha mejorado mucho el tamaño de la prueba.

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 C_0(InnernodeB),C_1(InnernodeA),C_2(Root) para representar los compromisos mencionados anteriormente y corresponderlos con el polinomio f_i(x) respectivamente.

Por lo tanto, el Prover necesita probar:

Comprimir para Múltiples Polis

Para hacerlo más fácil, usaremos z_i para representar el índice.

El probador necesita probar que para el conjunto polinomial f_0(x),f_1(x),....,f_m−1(x) , satisface las siguientes condiciones en los puntos z_0,z_1,....,z_m− 1 , 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:

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 r_0,r_1,....,r_m−1 y reúna los polinomios de cociente anteriores:
Suponga que si y solo si cada q_i(x) es un polinomio, g(x) será un polinomio (la probabilidad de que las fracciones entre q_i(x ) se compensen exactamente es muy baja debido a los números aleatorios).

El probador realiza el compromiso con el polinomio g(x) y envía [g(s)]_1 al verificador.

A continuación, permita que el verificador crea que [g(s)]_1 es el compromiso con el polinomio 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 π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1, y enviarlo al verificador.

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 y_i , ya que es el hash del valor de la siguiente capa.
No es necesario proporcionar explícitamente el valor de x_i , ya que se puede juzgar a partir de la clave.
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.