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

(Nota del traductor: la tecnología presentada en este artículo generalmente se denomina "Compromiso KZG10" en la comunidad de criptografía, y lleva el nombre de las iniciales de los apellidos de los tres autores. Pero cuando se introdujo en el ecosistema Ethereum, se simplificó como "Compromiso Kate ", incluso los desarrolladores principales lo llaman así. Esto es una falta de respeto a los otros dos autores y no debe continuar. En esta traducción, siempre que el autor original use "Compromiso de Kate", se traducirá como "Compromiso KZG10".) Descargo de responsabilidad  ;: Este artículo solo recopila y vincula muchos resultados publicados, y los honores correspondientes (incluidas las imágenes vinculadas en este artículo) deben pertenecer a los autores/desarrolladores correspondientes. P.D. : Un agradecimiento especial al canal de discordia de I+D de Ethereum (en particular @vbuterin y @piper) por ayudarme a comprender algunos aspectos de la promesa KZG10. Además, gracias a @vbuterin por ayudar a revisar este artículo. PPS : este artículo está escrito para el beneficio del equipo de lodestar; lodestar es un gran cliente ETH PoS basado en mecanografiado, que puede hacer que los servicios de Ethereum estén en todas partes, y también abrió el interés del autor en el ecosistema de Ethereum y la comprensión innovadora. Espero que este artículo también sea útil para otros desarrolladores/técnicos de todo el mundo. Este artículo sigue la convención de creación libre CC0 y el autor ha renunciado a todos los derechos. Sirva como una guía útil para familiarizar a los lectores, resuma el uso propuesto de los compromisos KZG10 en el contexto de Ethereum y brinde orientación para una comprensión profunda. El propósito de este artículo es más un resumen que un rigor, sin embargo, puede hacer clic en los enlaces adjuntos al artículo y tendrán explicaciones más detalladas. Nota-1: El valor hash es un compromiso con la preimagen hash, que se utiliza para verificar la integridad de los datos hash. (Nota del traductor: en realidad, esto no es muy riguroso. Debido a que la función hash a menudo es difícil de cumplir con las propiedades requeridas por el "esquema de compromiso".) Por ejemplo, suponga que h1 = H (t1, t2, t3 ..), entonces Proporcione h1 al verificador (por ejemplo, colóquelo en el encabezado del bloque) y luego proporcione un bloque falso (t1, t2', t3...), la otra parte calcula rápidamente el valor del bloque falso Después el valor hash, si encuentra que los dos no coinciden, puede rechazar razonablemente su bloque falsificado. De manera similar, el nodo raíz de un árbol Merkle es un compromiso con todos los nodos hoja organizados por un índice específico (ruta). O simplemente, una promesa a un mapeo de índices => valores (desde valores de índice hasta valores numéricos). Y la "prueba" aquí es la   rama Merkle de una hoja (rama merkle)   y (esta rama en cada capa)   hashes hermanos (hashes hermanos), con estos datos, puede nivelar el hash hacia arriba y juzgar si el leaf es consistente con este árbol Merkle (existe en este árbol Merkle) por si el valor hash final es consistente con el nodo raíz. Mira la introducción aquí  : ). Nota-2: La relación correspondiente entre el mapeo de datos y un polinomio índices => valores  dicho mapeo de datos puede expresarse como un polinomio  f(x), y f(índice)=valor (interpolado por Lagrange. Puede ser sabe que debe existir un polinomio que satisfaga esta condición). " f(índice)=valor " suele denominarse forma evaluada, mientras que " f(x)=a0+ a1.x + a2.x^2... " es su forma de coeficiente. Intuitivamente, en realidad ajustamos un polinomio de acuerdo con todos los puntos (índice, valor) en el mapa. Columnista de Forbes: la red blockchain descentralizada se está preparando para subvertir el mercado de talentos: el columnista de Forbes Roomy Khan publicó un artículo que las tecnologías emergentes de blockchain y cifrado están promoviendo redes de datos descentralizadas peer-to-peer (P2P), eliminando así la necesidad de un control central y reduce el valor de la plataforma de agregador-distribuidor. La red blockchain opera a través de un protocolo descentralizado, y las actividades de verificación y mantenimiento de registros están descentralizadas y automatizadas mediante la subcontratación a los usuarios de la red de la plataforma, eliminando así una entidad de control central. Blockchain y la inteligencia artificial (IA) pueden llevar la adquisición de talento para una fuerza laboral bajo demanda al siguiente nivel. Al enriquecer las interacciones P2P globales, las aplicaciones blockchain y cripto están preparadas para interrumpir el mercado de talentos y satisfacer las necesidades de la economía de conciertos en un mundo pospandémico. [2021/6/28 0:10:30] Para simplificar el cálculo y garantizar la coincidencia uno a uno entre el polinomio y el mapeo de datos, no usamos el valor del índice como la x de f(x) , pero use  w^index, que es  f(w^index)=valor, donde w es la raíz unitaria del grado d (es decir,  w^d = 1  y w es un número complejo) , y d es el grado del polinomio (también podemos incluir el número máximo de valores de índice). Por lo tanto, podemos utilizar la Transformada Rápida de Fourier para lograr cálculos de polinomios eficientes, como la multiplicación y la división. En la forma de evaluación, su complejidad computacional será O(d), y se puede realizar en O(d*log(d ))  dentro de la complejidad de volver a convertir a la forma de coeficiente. Por lo tanto, es bueno mantener  d  pequeño. Nota-2.1: El estado de Ethereum es un mapeo de direcciones a estados de cuenta (direcciones => (versión, saldo, nonce, codeHash, storageRoot)). Actualmente, Ethereum utiliza árboles de Merkle (más específicamente, "árboles de Patricia Merkle") como compromisos para los datos de EVM (estado de EVM, transacciones en bloque y recibos de transacciones, y quizás, más recientemente, código de contrato). Este tipo de método de compromiso puede: insertar/actualizar datos bloque por bloque y generar un nuevo hash raíz (es decir, compromiso) de manera incremental El verificador puede verificar y probar la estructura de árbol del prefijo bloque por bloque (incluso transacción por transacción ) Esta función de actualización bloque por bloque se proporciona aquí. Dado un árbol de prefijos con  d  bifurcaciones y  N  hojas, cualquier cambio en un nodo hoja requiere actualizar los nodos  O(log-d(N))  (es decir, la hoja el número de nodos en la ruta conectada al nodo raíz) para calcular un nuevo valor raíz que refleje el nuevo estado; esto requiere un  (d-1)*O(log-d(N))  valores hash hermanos/Compromiso adicional para ser utilizado como datos testigo (testigo) para el tiempo y el espacio (se supone que sirven a los nodos de luz). Un bloque se puede considerar como una actualización por lotes que necesita cambiar  m  hojas aleatorias y  m<<N. Debido a que solo se espera que una pequeña cantidad de nodos compartan testigos y cálculos, el Orden (complejidad) de cada actualización no cambiará mucho. En los siguientes casos, el problema será más grave (debido al tamaño de los datos testigo): algunos protocolos que usan sincronización rápida, como  beam sync (sincronización de fotones), descargarán y verificarán rápidamente el encabezado del bloque para capturar arriba con el último maestro La parte superior de la cadena y participa en el consenso de la Red. Tenga en cuenta que no construirá un estado completo antes de participar en el consenso, pero (en el consenso) construirá gradualmente un estado completo al obtener los datos testigo del estado perdido/descargado Cuando sirven  nodos ligeros , solo se preocupan por sí mismos y solo quieren obtener una parte específica del estado de la cadena de bloques. Cuando la red es completamente sin estado, todas las transacciones y operaciones de contrato deben ir acompañadas de un testigo relevante datos para probar La corrección de la entrada y salida de datos (Nota del traductor: el traductor agrega negrita) en el modelo de fragmentación de cadena de bloques donde el verificador se barajará en diferentes fragmentos. Construir un estado completo no es realista Merkelización de código, acceso al código requiere datos de testigos para estos bloques de código En el protocolo de vida útil del estado, el acceso a las cuentas vencidas requiere volver a adjuntar los datos de testigos del estado para reconstruir el estado de la cuenta (Nota del traductor: es necesario explicar que en la red Ethereum actual , las transacciones y los bloques no tienen los datos testigo descritos anteriormente. Es decir, la escala de los datos testigo propagados por la red no tiene una relación constante con el tamaño de las transacciones/bloques. Las dos primeras situaciones resultan ser una de las pocas situaciones en las que el testigo los datos deben propagarse bajo el protocolo actual de Ethereum. Nos preocupamos por la escala de los datos estatales por completo debido a la necesidad de una dirección de mejora del protocolo: "apatridia". Los últimos cuatro casos están todos relacionados con la apatridia y, por supuesto, la cantidad de ser propagado es más que el teórico. Sin embargo, es inapropiado utilizar el cálculo teórico anterior como punto de referencia para la comparación. —— Incluso Code Merkel Este esquema de guardar datos estatales en el estado sin estado también se clasificará como un esquema que hace la situación más grave.) En un experimento del proyecto Ethereum sin estado, apareció evidencia de bloque de  1 MB  (de los cuales la mayoría de ellos son evidencia de Merkel), y se expandirá varias veces cuando ocurra un ataque. Una solución es cambiar a un "árbol de Merkle binario", es decir, bajar  d , de modo que, aunque la profundidad (altura) del árbol aumente, todavía sea  O(log(N))  Escala. Para un esquema de compromiso que compromete datos en el encabezado del bloque, las siguientes características son propiedades ideales: la cantidad de datos de prueba es pequeña, se puede introducir en el encabezado del bloque y todavía tiene una fuerte garantía de seguridad. se utiliza cierto compromiso Se genera un subconjunto de datos fragmentados que es lo suficientemente pequeño como para evidenciar mejor que la cantidad de datos es constante Para rastrear datos, los compromisos deben ser fáciles de cambiar gradualmente KZG10 Las soluciones basadas en compromiso son lo que buscó resultado . Nota del traductor: Se puede ver que el autor tiene tres compromisos. KZG10 puede considerarse como otro esquema hash, excepto que lo que hash no son "bytes" (datos), sino polinomios. De hecho, es el valor de evaluación polinomio f(x) en un punto fijo secreto s , pero se expresan en una curva elíptica, a saber  ;[f(s)]=f([s ]). Esto requiere una configuración de inicio confiable (igual que el evento de génesis de la cadena de bloques zcash) para generar [s], [s^2], ... [s^d] (para que el polinomio requiera x^ i  ), y  d  es el orden máximo del polinomio. Aquí [t] significa el valor de la curva elíptica en el punto t, es decir, t, que es el punto de generación del grupo de suma de la curva elíptica () y suma t veces (equivalente a módulo Fp, módulo Fp ) . Todos los cálculos en una curva elíptica se realizan módulo Fp, lo que impone un límite en la curva. Nota 3.0: En el mapeo de  índices=>valores , todos los valores deben estar expresados ​​como elementos en una curva elíptica, es decir, [valor], para calcular el compromiso (detallado más adelante). Esto pone un límite al tamaño del valor (para que sea el valor de  módulo Fp ). En la curva BLS, probablemente esté entre 31 y 32 bytes. Para simplificar, el tamaño de un valor está limitado a 31 bytes, y cualquier valor mayor se fragmenta y representa correctamente (o trunca) por su valor de índice. Nota 3.1: [t] puede considerarse como el valor hash de t, porque recuperar t de [t] es un problema de logaritmo discreto (problema de logaritmo discreto), que es difícil de hacer para una curva segura. Nota 3.2: s es un valor secreto que nunca debe ser revelado a nadie/todos, pero la curva elíptica apunta [s], [s^2]…[s^d] y en otros valores A en una elíptica curva [s]'  (su punto de generación es ' y solo necesita saber [s]' ) debe generar y Hacerlo público y que todos lo sepan. Eso es lo que hace la configuración de inicio. Estos  parámetros del sistema definen la seguridad de todo el sistema, ya que  su exposición permite a los atacantes construir contenido arbitrario evidencia. Por lo tanto, en una ceremonia de puesta en marcha que involucre a N participantes, deben combinar los s locales a través del acuerdo, de modo que mientras un participante sea honesto y destruya los s proporcionados por sí mismo después de participar, el sistema estará seguro. Es decir, el modelo de confianza es un modelo 1/N, cuanto mayor es N, menor es el riesgo. Nota 3-3: []  es una operación lineal, es decir, [x]+[y]=[x+y], y a[x]=[ax]. Como se mencionó anteriormente, expresamos el mapeo de datos (valor de índice => valor) como  f(w^index)=valor, que es la forma de evaluación de un polinomio. También se puede decir que usamos estos (w^ index,value) Los puntos se ajustan a una curva (polinomio).

Tags：

Binance Apps