Las pruebas de conocimiento cero a menudo parecen misteriosas porque la matemática detrás de ellas es muy avanzada. Queremos eliminar esta confusión y ayudar a todos a entender lo que realmente hacen las pruebas de conocimiento cero.Aunque todavía se sienten mágicas, creemos que la comunidad debe entender las ideas técnicas detrás de nuestro trabajo. En este post, presentamos un importante bloque de construcción utilizado en muchos sistemas de prueba de conocimiento cero: Después de eso, explicamos , uno de los tipos más populares y prácticos de esquemas de compromiso polinómico. polynomial commitment schemes KZG Describimos entonces cómo Y cómo Por último, mostramos cómo zk-rollups y Proto-Danksharding pueden trabajar juntos de manera suave y eficiente, algo que es posible específicamente porque . KZG is used inside zk-rollups Ethereum also uses KZG in Proto-Danksharding both systems use polynomial commitment schemes Why are we talking about polynomials? Polinomiales son poderosas herramientas matemáticas porque nos permiten representar objetos grandes o complejos de manera eficiente. Un ejemplo común es representar un vector n-dimensional de elementos de campo v usando un único polinomial. Lo hacemos construyendo un polinomial φ(x) que pasa a través de los puntos (i, v_i) para cada índice i = 1, 2, ..., n. Por ejemplo, el vector 3-dimensional v = [2, 0, 6] puede ser codificado por el polinomial porque la inclinación en los valores da , de , y En general, dado cualquier n puntos, siempre existe un polinomio único de grado a más de n − 1 que pasa a través de todos ellos. φ(x) = 4x² − 14x + 12 φ(1) = 2 φ(2) = 0 φ(3) = 6 El proceso de construir este polinomio se denomina interpolación polinómica, y una de las técnicas más ampliamente utilizadas es , que proporciona una fórmula directa para construir el polinomio a partir de los puntos dados. Usando este método, ahora sabemos cómo construir un polinomio de grado al máximo . Interpolación de Lagrange n − 1 from exactly n constraints En la sección anterior, hemos aprendido que si usted sabe , you can always determine one unique polynomial whose degree is at most Ahora, queremos ir un paso más allá y entender para encontrar realmente ese polinomio de las coordenadas de esos n puntos. n points n − 1 Cómo Un método común y simple para hacer esto se llama interpolación de Lagrange. Aunque las fórmulas oficiales pueden parecer complicadas, la idea básica es muy sencilla. La interpolación de Lagrange nos da una forma directa de construir el polinomio que pasa a través de todos los puntos dados. Por ejemplo, supongamos que queremos encontrar un polinomio de grado a un máximo de 2 (es decir, un polinomio cuadrado). Para hacer esto, necesitamos exactamente 3 puntos, y el polinomio debe satisfacer todas las tres de esas restricciones. Usando las coordenadas de estos 3 puntos, la interpolación de Lagrange construirá el polinomio exacto que se ajusta perfectamente a ellos. P φ(1) = 2 φ (2) = 0 φ(3) = 6 Para ello, construiremos 3 subpolinomios (uno por restricción) , y En el grado máximo . P₁ P₂ P₃ 2 Estos 3 subpolinomios deben seguir estas sub-condiciones: x P₁(x) P₂(x) P₃(x) 1 2 0 0 2 0 0 0 3 0 0 6 1 2 0 0 2 0 0 0 3 0 0 6 Each sub-polynomial evaluates to En todos los puntos, excepto uno. 0 Por último, hemos establecido: P(x) = P₁(x) + P₂(x) + P₃(x) Vamos a comprobar rápidamente, refiriéndose a la pestaña anterior, que Respeta todas sus limitaciones: P P(1) = P₁(1) + P₂(1) + P₃(1) = 2 + 0 + 0 = 2 P(2) = P₁(2) + P₂(2) + P₃(2) = 0 + 0 + 0 = 0 P(3) = P₁(3) + P₂(3) + P₃(3) = 0 + 0 + 6 = 6 Acabo de comprobar que respetar sus 3 restricciones. Ahora, vamos a construir , de y . P P₁ P₂ P₃ Building P₁ Using the , we can define P₁ as: factorised form P₁(x) = A(x − 2)(x − 3) Ya cumplen con las restricciones: P₁ P₁(2) = P₁(3) = 0 Ahora vamos a encontrar tales como: A P₁(1) = 2 Tenemos la siguiente ecuación: P₁(1) = A(1 - 2)(1 - 3) = 2 Lo que nos da: A = 2 Y por último: P₁(x) = 2(x − 2)(x − 3) Ahora cumple con sus tres subcondiciones. P₁ Edificio P2 Usando el Podemos definir como : Forma de fabricación P2 P₂(x) = B(x - 1)(x − 3) Ya cumplen con las restricciones: P2 P₂(1) = P₂(3) = 0 Ahora vamos a encontrar such as: B P₂(2) = 0 Tenemos la siguiente ecuación: P₂(2) = B(2 − 1)(2 − 3) = 0 Lo que nos da: B = 0 Y por último: P₁(x) = 0(x − 1)(x − 3) = 0 Ahora cumple con sus tres subcondiciones. P₂ Edificio P3. Usando el , we can define como : Forma de fabricación P3 P₃(x) = C(x − 1)(x − 2) Ya cumplen con las restricciones: P₃ P₃(1) = P₃(2) = 0 Ahora vamos a encontrar tales como: C P₃(3) = 6 Tenemos la siguiente ecuación: P₃(3) = C(3 - 1)(3 - 2) = 6 Lo que nos da: C = 3 Y por último: P₃(x) = 3(x - 1)(x - 2) Ahora cumple con sus tres subcondiciones. P₃ Building P As previously seen, P(x) = P₁(x) + P₂(x) + P₃(x) Replacing , and by their respective expression, we get: P₁ P₂ P₃ P(x) = (x - 2)(x - 3) + 0 + 3(x - 1)(x - 2) P(x) = (x² - 5x + 6) + 3(x² - 3x + 2) P(x) = x² - 5x + 6 + 3x² - 9x + 6 P(x) = 4x² - 14x + 12 After expansion and simplification, we obtain: P(x) = 4x² - 14x + 12 Checking P Vamos a comprobar rápidamente que Respeta las 3 restricciones: P P(1) = 4(1²) - 14(1) + 12 = 4 - 14 + 12 = 2 P(2) = 4(2²) - 14(2) + 12 = 16 - 28 + 12 = 0 P(3) = 4(3²) - 14(3) + 12 = 36 - 48 + 12 = 6 What are polynomial commitment schemes, and why are they useful? Los esquemas de compromiso polinómicos son herramientas especiales que permiten a alguien comprometerse a un polinómico entero sin mostrar lo que el polinómico realmente es. , lo que significa que no puede cambiar el mensaje después de comprometerse, y Los compromisos polinómicos siguen las mismas reglas, pero en lugar de comprometerse a un solo mensaje, se comprometen a un polinomio entero con muchos coeficientes. binding hiding La parte poderosa de los compromisos polinómicos es que más tarde puede probar el valor del polinómico en puntos específicos sin revelar el polinómico entero. Tiene el valor en , pueden hacerlo sin exponer el resto del polinomio. Simplemente dan una prueba corta que muestra El verificador no aprende nada más sobre el polinomio mismo.Esta característica es increíblemente útil en las pruebas de conocimiento cero, donde el objetivo es probar que algo es verdad sin revelar información adicional. ϕ(x) 66 x = 4 “ϕ(4) = 66” Another reason polynomial commitments are useful is that the commitment is much smaller than the polynomial. A polynomial may have hundreds or thousands of values, but the commitment can be just a single small group element, like 48 bytes. This is extremely important for blockchains, where storing or posting large data is expensive. By compressing a large polynomial into one tiny commitment, systems like y Puede ahorrar mucho espacio y reducir costes. zk-rollups Proto-Danksharding Para hacer esto más fácil de entender, imagina que Alice tiene un polinomio secreto, como φ(x) = 3x2 + 5x + 2. Ella no quiere revelar el polinomio, pero Bob quiere la prueba de que φ(4) = 66. Alice se compromete al polinomio usando un esquema de compromiso polinómico y envía a Bob el compromiso. Más tarde, ella revela sólo el valor 66 y proporciona una prueba corta que muestra que este valor es correcto para x = 4. Bob comprueba la prueba contra el compromiso y se convierte, sin aprender nunca nada más sobre el polinomio. Esta es la razón por la cual los compromisos polinómicos son herramientas poderosas en la criptografía moderna y esencial para sistemas blockchain escalables. KZG Polynomial Commitment KZG Compromiso Polinómico 1. Commitment En un compromiso polinomial, el probador primero convierte sus datos en un polinomial. Luego crean un especial "compromiso" criptográfico a este polinomial. Puede pensar en este compromiso como sellar el polinomial dentro de una caja cerrada: el probador no puede cambiarlo más tarde, y el verificador no puede ver lo que está dentro. Este paso garantiza dos cosas - el polinomial no se puede cambiar ( ) y su contenido permanece privado ( ) de binding hiding 2. Evaluation A continuación, el probador quiere probar algo sobre el polinomio Así que eligen un punto x, lo conectan al polinomio y calculan la respuesta. Sólo envían este valor y, más una pequeña prueba que muestra que el valor proviene del polinomio comprometido.El polinomio real permanece oculto todo el tiempo.Esto permite al probador mostrar el comportamiento del polinomio correctamente en un punto sin exponer al polinomio entero. Sin revelarlo y=P(x) 3. Verification Finally, the verifier checks if the value Realmente coincide con el polinomio comprometido en el punto . Using the commitment and the proof, the verifier performs a cryptographic check. If everything is valid, the verifier knows Si el probador intenta mentir o engañar, el paso de verificación lo atrapará. Esto hace que los compromisos polinómicos sean seguros y muy útiles en tecnologías como la prueba de conocimiento cero y la escalación de Ethereum. y x P(x)=y KZG Polynomial Commitment Scheme El esquema de compromiso polinomial de KZG KZG tiene . four main steps Step 1 - Trusted Setup Una configuración única hecha antes de que el sistema se ejecute. Elija un generador g de un grupo de curvas elípticas G (aparatos de soporte). Seleccione el grado máximo l del polinomio. Pick a secret random value: τ ∈ Fp Compute and publish: (g, g^τ, g^(τ^2), ...., g^(τ^l)) Only these powers of are public. gᵗ The value τ must remain secret forever. If someone knows τ, they can forge proofs. Step 2 - Commit to a Polynomial Suppose we have the polynomial: ϕ(x) = ∑ᵢ₌₀ˡ ϕᵢ xⁱ We want to compute the commitment: C = g^{ϕ(τ)} Although the committer cannot compute directly since he doesn’t know , he can compute it using the output of the setup g^{ϕ(τ)} τ τ Step 3 - Create a Proof for Evaluation ϕ(a)=b Para demostrar esto: ϕ(a)=b Calcular el coeficiente polinomial: q(x) = ϕ(x) - b / x - a Esto sólo es válido si la evaluación es correcta. Entonces comprueba la prueba: π = g^{q(τ)} Esta es la prueba de evaluación de KZG. Step 4 - Verification Dado por: Commitment C = g^{ϕ(τ)} prueba π = g^{q(τ)} Evaluation claim ϕ(a)=b El verificador verifica: e(c/g^b,g) = e(π,g^τ/g^a) Aquí e ( ⋅ , ⋅ ) es una . Bilingüismo en pareja This equation is equivalent to verifying: q(τ) = ϕ(τ) - b /τ - a Si el control de emparejamiento se mantiene, la evaluación se acepta como correcta. Breve explicación de la verificación de pareja LHS: = (τ)−b (C = g^{ϕ(τ)}) e(C/g^b, g) e(g,g)ϕ Los RHS: = El (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) La igualdad implica φ(τ)−b = q(τ)(τ−a), la identidad cuantitativa evaluada en τ, que aplica φ(a)=b si q(x) se formó correctamente. (q(x) = φ(x) - b / x - a) Breve explicación de la verificación de pareja LHS: = (τ)−b (C = g^{ϕ(τ)}) e(C/g^b, g) e(g,g)ϕ Los RHS: = El (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) La igualdad implica φ(τ)−b = q(τ)(τ−a), la identidad cuantitativa evaluada en τ, que aplica φ(a)=b si q(x) se formó correctamente. (q(x) = φ(x) - b / x - a) Use Cases: zk-rollups En zk-rollups, debemos demostrar que el trabajo realizado en la capa 2 (L2) es correcto. Para ello, todos los pasos del cálculo se convierten en una gran tabla (una matriz 2D). . Each column of this table represents one part of the computation, and each column can be turned into a polynomial. So instead of handling a huge matrix directly, we work with a list of polynomials. The correctness of the computation can then be described using mathematical rules between these polynomials. For example, imagine three columns of the table represent three polynomials: Generación de testigos A(x) de la b(x ) c(x) Una regla podría decir que a(x)⋅b(x)−c(x)=0 Esto significa “el primer polinomio multiplicado por el segundo debe ser igual al tercero”. la columna 1 × la columna 2 debe producir la columna 3. Instead of checking this rule for every possible value of x (which would be slow), zk-rollups check it only at a few random points. If the rule is correct at those random points, then with very high probability, the whole computation is correct. Si quiero comprobar si dos listas largas coinciden con una regla, no necesito comparar cada elemento: comprobar algunos elementos aleatorios generalmente me dice si la relación entera es válida. Example: Los esquemas de compromiso polinómico —como KZG— son perfectos para esto. El rollup se compromete a todos los polinomios que describen el cálculo L2 (algo como bloquearlos dentro de una caja criptográfica). Más tarde, el verificador puede pedir los valores de estos polinomios en puntos aleatorios específicos. Con esos valores y los compromisos, el verificador comprueba si las reglas de corrección se mantienen. Proto-Gracias de Ethereum (EIP-4844) es una actualización diseñada para hacer que sea mucho más barato para los rollups publicar sus datos en la capa 1 de Ethereum. Este tipo de transacción incluye un gran pedazo de datos llamado (aproximadamente 128 kB). sin embargo, este blob es contratos inteligentes o la capa de ejecución. contratos inteligentes sólo pueden ver un Para el blob, no para el blob. Proto-Gracias Transacciones de Blob Carrying blob not commitment Ahora la pregunta es: Una opción es tomar el blob y simplemente Pero el hashing es limitado: si solo almacenamos un hash, entonces más tarde no podemos probar nada sobre los datos dentro del blob sin revelar el blob entero. ¿Cómo debe Ethereum crear este compromiso con el blob? hash it En su lugar, podemos tratar el blob como un polinomial. (Anteriormente, explicamos cómo los vectores o los datos pueden ser representados como polinomios.) como KZG, Ethereum puede comprometerse al blob de una manera que no solo oculta los datos, sino que también permite la verificación de ciertas propiedades . polynomial commitment scheme Descargar todo el blob Esta capacidad es esencial para algo llamado DAS permite que los validadores verifiquen si el blob está disponible y correcto Gracias a la matemática detrás de los compromisos polinómicos, si suficientes muestras aleatorias son correctas, los validadores pueden estar muy seguros de que todo el blob está disponible. (Aunque el DAS no está incluido en la primera versión de Proto-Danksharding, se añadirá tan pronto como Ethereum continúe hacia “full Danksharding”). (DAS) Data Availability Sampling Sin descargar todos los 128 KB Data Availability Sampling Ethereum has chosen Los investigadores compararon varios esquemas y concluyeron que KZG proporciona el mejor equilibrio de eficiencia, tamaño de prueba y simplicidad para la hoja de ruta de Ethereum a corto y medio plazo. KZG How zk-rollups and Ethereum’s Proto-Danksharding interact zk-rollups y Proto-Danksharding de Ethereum pueden parecer sistemas separados, pero ambos utilizan compromisos KZG de maneras que les permiten trabajar juntos sin problemas. Scroll utiliza KZG para comprometerse con los cálculos realizados en la capa 2, mientras que Ethereum utiliza KZG para comprometerse con grandes bloques de datos publicados en la capa 1. Cuando Scroll termina de procesar un lote de transacciones L2 y calcula una nueva raíz de estado, debe publicar tres cosas en el L1 de Ethereum: T - la lista de transacciones L2, Si - la nueva raíz de estado después de que se apliquen esas transacciones, π - una prueba de que la raíz del nuevo estado es correcta. Ethereum debe verificar dos cosas: que la nueva raíz de estado Si es válida (lo que significa que las transacciones se ejecutaron correctamente), y that the transaction list is the one used to produce that state root. So there must be a way to link the transaction list with the proof . T exactly T π Ethereum stores como a Esto significa que el usuario sólo tiene acceso a un a ese blob - llamemos este compromiso Mientras tanto, la prueba También contiene compromisos de KZG a varios polinomios utilizados durante el cálculo, incluyendo el polinomio que representa la lista de transacciones. . T Blob de datos KZG commitment Cₜ π Cₚ Ahora tenemos dos compromisos diferentes de KZG ( Desde el blog y de la prueba) que representan la misma φt polinomial (la representación polinomial de la lista de transacciones). y Realmente se refiere a los mismos datos. Cₜ Cₚ Debe Cₜ Cₚ Para ello, utilizamos una técnica llamada . The idea is simple: La prueba de equivalencia La prueba de equivalencia Seleccione un valor aleatorio = hash(Ct Cp) Esto hace que z sea impredecible y único para estos dos compromisos. Both commitments are then “opened” at the point z, each producing a value . That is, prove that: a ϕₜ(z) = a under commitment , and Cₜ ϕₜ(z) = a under commitment . Cₚ Si ambos compromisos dan el mismo valor en el mismo punto aleatorio, entonces con una probabilidad extremadamente alta, representan el mismo polinomio. Ejemplo: Imagínese a dos personas, cada una afirmando que tienen el mismo polinomio secreto. En lugar de revelar el polinomio entero, cada una lo evalúa en un punto aleatorio, diciendo x = 103. Si ambas evaluaciones coinciden, la probabilidad de que tengan dos polinomios diferentes que coincidan en ese punto aleatorio exacto es astronómicamente pequeña. Imagínese a dos personas, cada una afirmando que tienen el mismo polinomio secreto.En lugar de revelar el polinomio entero, cada una lo evalúa en un punto aleatorio, digamos x = 103.Si ambas evaluaciones coinciden, la probabilidad de que tengan dos polinomios diferentes que coincidan en ese punto aleatorio exacto es astronómicamente pequeña. Example Esta misma lógica permite a Ethereum verificar que la lista de transacciones utilizada en la prueba es exactamente lo mismo que la lista de transacciones publicada en el blob. π A nice bonus is that this equivalence check works even if the two commitments use esquemas de compromiso polinómicos. por ejemplo, uno podría ser KZG y el otro FRI. Mientras ambos compromisos apoyan la apertura en un punto, el verificador puede compararlos, haciendo este enfoque muy flexible. Diferentes Diferentes Erasure Coding With Polynomials Otro concepto poderoso utilizado tanto en KZG como en PeerDAS es . This technique allows data to be recovered even if parts of it are missing. Using polynomials, we can take a small set of original values and extend them into a longer set by evaluating the polynomial at additional points. The key property is that Esto es exactamente cómo funciona la muestra de disponibilidad de datos (DAS) de Ethereum: los nodos no necesitan cada pieza de datos, solo una muestra aleatoria que les permite reconstruir la información original con alta probabilidad. erasure coding if the degree stays the same, the original data can be recovered from subset of enough points cualquier cualquier ¿Por qué son necesarios los compromisos polinómicos? ¿Por qué son necesarios los compromisos polinómicos? El uso de polinomios y códigos de borrado resuelve muchos problemas, pero crea uno nuevo: How do we prove that a piece of data truly belongs to the committed polynomial? Aquí es donde Un compromiso KZG permite: KZG polynomial commitments committing to a polynomial with a single small group element Probar que un punto de datos es una de las evaluaciones del polinomio Verificar la prueba sin descargar el polinomio o reconstruirlo Esta propiedad es esencial para el mapa de ruta de escala de Ethereum porque los validadores deben verificar la disponibilidad de datos de manera eficiente sin leer megabytes de datos blob. y rely on polynomials to split data into , de , y Cada blob es tratado como un polinomial cuyas evaluaciones llenan los datos. Cuando los datos se extienden y se arreglan en columnas, los validadores solo reciben pequeñas piezas, pero la estructura polinomial asegura que todas las piezas son consistentes. Cada prueba confirma que una celda específica corresponde al polinomio cometido en el encabezado del bloque. Pilares Proto-Gracias columns cells blobs KZG proofs Gracias a los compromisos polinómicos, Ethereum puede escalar de forma segura la disponibilidad de datos mientras reduce drásticamente la carga en los nodos individuales. y los peerdos. Página 4844 A continuación, echaremos un vistazo más de cerca a cómo funciona PeerDAS, cómo los compromisos de KZG juegan un papel clave en ello, y cómo la codificación de borrado permite a la red recuperar los datos perdidos. A continuación, echaremos un vistazo más de cerca a cómo funciona PeerDAS, cómo los compromisos de KZG juegan un papel clave en ello, y cómo la codificación de borrado permite a la red recuperar los datos perdidos.
