Presentamos los compromisos de KZG con Ethereum: la perspectiva de un ingeniero (parte 2)

Dry Goods | Presentamos el compromiso de KZG con Ethereum: la perspectiva de un ingeniero (parte 1) (continuación) ¿Qué es el compromiso de KZG10? Nota 3.6: Si los  [s],[s^2]...[s^d]  calculados por la configuración de inicio solo calculan el exponente d, este conjunto de valores no se puede utilizar para generar ningún polinomio con un pedido mayor que d promesa. viceversa. Dado que no hay forma de multiplicar dos puntos para obtener un tercer punto en una curva segura,  [s^(d+k)]  es un (¡nunca!) valor que no se puede encontrar, por lo que uno puede Eso es , cualquier compromiso  c(f)  solo puede representar un polinomio cuyo orden sea menor o igual que d. Nota 3.7: Las pruebas que utilizan compromisos KZG10 básicamente prueban que el resultado de  f(x) - algún resto  se puede descomponer de cierta manera, pero esto requiere una forma de  multiplicar estos factores y compararlos con el original compromiso C(f)=f([s]). Para esto, necesitamos una "ecuación de emparejamiento", que es una multiplicación que toma dos puntos de una curva y los compara con otro punto de la curva, porque no podemos multiplicar directamente los dos puntos de la curva para obtener el punto de la curva resultante. Nota 3.8: Las dos propiedades anteriores se pueden usar para probar que el orden k del polinomio f(x) representado por un cierto compromiso c(f) es menor que d. En resumen, el compromiso KZG10 puede tener buenas propiedades: el proceso de verificación del compromiso es: (por el generador de bloques) proporcionar el valor del polinomio subyacente en cualquier punto  r  y=f(r) , y Divide el polinomio q(x)=(f(x)-y)/(x-r) valor en [s] punto (es decir, q([s])), y empareja con  Ecuación  para comparar el compromiso proporcionado previamente f[s]. Esto se llama compromiso de apertura en el punto r, y q([s]) es la prueba. Es fácil ver que q(s)  es simplemente  p(s)-r  dividido por  s-r , que resulta ser lo que comprobamos con la ecuación apareada, es decir, comprobar (f( [s] )-[y]) * '= q([s]) * [s-r]'   p(s)-r). En la versión no interactiva y determinista, Fiat Shamir Heuristic proporciona una forma de obtener un punto r que es relativamente aleatorio: porque la aleatoriedad solo está relacionada con la entrada que estamos tratando de probar, es decir, siempre que haya ya es un compromiso  c=f([s]) , r se puede obtener mediante el hash de todas las entradas (r=Hash(C,..)), y el  proponente del compromiso  es responsable de proporcionar el punto de apertura  ; y pruebas. Utilizando polinomios de Lagrange precalculados, tanto f([s])  como  q([s])  se pueden calcular directamente en el  formulario de evaluación . Para calcular el valor de apertura en r, es necesario convertir f(x) en la forma de coeficiente de  f(x)=a0+ a1*x^1....  (es decir, extraer  a0 , a1, ...). Esto se puede lograr mediante la  Transformada Rápida de Fourier Inversa  con complejidad  O(d log d), pero incluso aquí hay un algoritmo alternativo disponible, dentro de la complejidad de  O(d)  El cálculo se realiza sin utilizar la transformada rápida inversa de Fourier. Puede usar un solo punto de apertura y evidencia para probar múltiples valores de f(x), es decir, los valores correspondientes a múltiples valores de índice, índice1=>valor1, índice2=>valor2 .. (utilizado para calcular la demostración) el polinomio de división q(x) ahora se convierte en el resto del cociente de f(x) dividido por el polinomio cero z(x) =(x-w^index1)*(x-w^index2)...(x-w ^indexk)  Es  r(x) ( r(x)  es un polinomio de orden máximo k, por  index1=>valor1, index2=>valor2  ;… indexk= valork  interpolación) comprobar ( f([s])-r([s]) )* ' = q([s]) * z([s]') en la cadena PoS En la configuración de co-inicio, donde los bloques de datos compartidos se representan como polinomios de orden bajo (y se expanden al doble usando los mismos polinomios de  ajuste  para la  codificación de borrado ), la promesa KZG puede ser se utiliza para verificar cualquier fragmento aleatorio y verificar y garantizar la disponibilidad de datos sin obtener puntos de datos hermanos. Esto abre la posibilidad de muestreo aleatorio. Ahora, para un estado con un máximo posible de  2^28  claves de cuenta, necesita polinomios de grado de al menos  2^28  para generar  compromisos planos (en realidad, claves de cuenta). El espacio total será mucho, mucho más grande). Al actualizar e insertar, habrá algunos inconvenientes. Cualquier cambio en cualquiera de las cuentas desencadenará un nuevo cálculo del compromiso (y, lo que es más problemático, los datos/pruebas de los testigos). Actualización del compromiso KZG10 Cualquier cambio en cualquier valor de índice => valor punto, como cambiar el indexk, requiere actualizar el compromiso utilizando el polinomio de Lagrange correspondiente. La complejidad es de aproximadamente O(1) por actualización. Sin embargo, dado que f(x) también ha cambiado, todos los testigos  q_i([s]) , es decir, todos los testigos del i-ésimo par clave-valor, también deben actualizarse. La complejidad total es de O(N). Si no mantenemos el  q_i([s]) testigo precalculado, cualquier dato de testigo debe calcularse desde cero, lo que requiere O(N) una Construcción de un compromiso KZG10 actualizado con complejidad  sqrt(N)  Por lo tanto, para realizar el cuarto punto del esquema de compromiso ideal, necesitamos una construcción especial: Verkle trie. El estado de Ethereum que debe representarse es aproximadamente 2^28 aproximadamente igual a 16^7 aproximadamente igual a 250 millones pares clave-valor. Si solo usamos compromisos fijos (entonces necesitamos un orden de al menos 2^28). Aunque nuestra evidencia es siempre un elemento de curva elíptica de 48 bytes, cualquier inserción o actualización requiere operaciones  O(N)  para actualizar todos los datos testigo calculados previamente (es decir,   ;q_i(s) , porque f(x) ha cambiado); incluso, si no hay datos de testigos precalculados, cada dato de testigo necesita gastar  O(N)  para volver a calcular. Por lo tanto, necesitamos reemplazar la estructura plana con una estructura llamada  árbol Verkle , que es una estructura de árbol como un árbol Merkle. Es decir, como un árbol de Merkle, se construye un árbol de compromiso, por lo que podemos garantizar que el orden  d  es relativamente pequeño (pero también debe ser tan alto como 256 o 1024). Cada nodo principal codifica un compromiso con sus nodos secundarios, y un nodo secundario es un mapa cuyos valores de índice se almacenan en su nodo principal. De hecho, el compromiso del nodo principal codifica el nodo secundario con hash, porque la entrada del el compromiso está normalizado, valor de 32 bytes (véase la Nota 3.0 anterior). Un nodo hoja codifica un compromiso con un hash de 32 bytes de los datos que almacena, o salta directamente a los datos si su uso de los datos de 32 bytes coincide con la propuesta de  árbol de estado  mencionada en el siguiente capítulo. mismo. Para proporcionar pruebas para una sucursal (similar a las pruebas de sucursales de Merkel), se puede generar una prueba de compromiso de múltiples valores  D, E  alrededor de un punto t relativamente aleatorio utilizando la generación herurística fiat shamir. Complejidad Aquí hay un análisis de  pruebas de varios valores de Verkle Actualizar/insertar nodos hoja index=>value requiere actualizar log_d(N) commitments~ log_d(N) para generar pruebas, el probador necesita calcular el valor de  f_i(X)/(X-z_i) en [s]  para generar D , la complejidad total O(d log_d N) , pero se puede ajustar para ahorrar precálculo cuando actualizando/insertando, y la complejidad será O d log_d(N) cálculo m ~ O( log_d(N)) f_i(t)  Para calcular h(t), el total es O (d log_d N) Para calcular π, ρ , debe dividir la suma de  m~ log_d N polinomios exponenciales. Se tarda aproximadamente  O(d log_d N)  en obtener la forma evaluada del numerador para calcular el tamaño de la prueba de división (incluido el compromiso de rama utilizado para calcular  E ) más la complejidad de la verificación ~  O(log_d(N)) es una estructura de árbol único del árbol Verkle de estado ETH propuesto, almacena el  encabezado  y   bloques de código de la cuenta, y   bloques de elementos de almacenamiento, y el compromiso del nodo es de order d=256 El polinomio combina la dirección y el encabezado/espacio de almacenamiento para derivar una  storageKey de 32 bytes, que es esencialmente una tupla  (address, sub_key, leaf_key)  que representa las primeras 30 de las claves derivadas. Los bytes se utilizan para construir pivotes de nodos de árbol Verkle comunes. Los últimos 2 bytes son un subárbol con una altura de árbol de 2, lo que significa un máximo de 65536 bloques de 32 bytes. Para datos básicos, este subárbol con una altura de árbol de 2 tiene la la mayoría Hay compromisos de 4 hojas para cubrir el encabezado y el código Debido a que un bloque es 65536*32 bytes se representa como un solo recuento de palabras, por lo que puede haber muchos subárboles en el árbol principal para almacenar una cuenta Esquema de precios de gas Eventos de acceso tipo  (dirección, sub_clave, hoja_clave)  Cada evento de acceso especializado cobra  WITNESS_CHUNK_COST Cada combinación especializada de  dirección, sub_clave  cobra WITNESS_BRANCH_COST adicional código Código Merkle Se convertirá automáticamente en parte del árbol verkle (como parte de el árbol de estado unificado). El encabezado y el código de un bloque forman parte de un árbol de compromiso con una altura de árbol de 2. Un solo bloque tiene un máximo de 4 piezas de datos testigo, que se cobran respectivamente WITNESS_CHUNK_COST , acceso al la cuenta debe cargarse una vez WITNESS_BRANCH_COSTETH Uno de los objetivos de PoS es poder enviar un volumen de datos de aproximadamente 1,5 MB/s (entienda este rendimiento como el rendimiento de los cambios de estado, por lo que es el rendimiento de la transacción que se puede utilizar por L2 rollup, y finalmente es el rendimiento del L1 EVM). Para lograr esto, se deben emitir y verificar muchas propuestas de bloques paralelos en un plazo de 12 segundos, es decir, debe haber múltiples fragmentos (alrededor de 64) y cada fragmento debe publicar el suyo propio en cada bloque de datos. Si se admiten más de 2/3 de los votos, el bloque de la cadena de balizas contendrá bloques de datos fragmentados y la regla de selección de bifurcación también determinará si se puede basar en la disponibilidad de datos de todos los bloques de datos en el bloque de la cadena de balizas y sus ancestros. Conviértete en el bloque de la cadena principal. Nota 3: la fragmentación en este momento no es una cadena y cualquier orden implícita debe ser interpretada por el protocolo L2. Las promesas de KZG también se pueden usar para crear esquemas de validez y disponibilidad de datos. Los clientes pueden verificar la disponibilidad sin acceder a los datos completos publicados por el proponente de fragmentos

Tags：

Ripple