Definición formal (la más importante)
Un protocolo ZKP para un lenguaje ( L ) cumple:
Existe un prover ( P ) y un verifier ( V )
Se define así:
[
\forall x \in L,\ \exists w:\ R(x, w) = 1
]
Donde:
( x ) = instancia pública
( w ) = witness (secreto)
( R(x,w) ) = relación verificable (circuito)
Las 3 propiedades clave (esto ES la “base” del ZKP)
1. Completitud
Si el prover es honesto:
[
\Pr[V(x) = \text{accept}] = 1
]
2. Solidez (Soundness)
Si el prover NO conoce el secreto:
[
\Pr[V(x) = \text{accept}] \leq \epsilon
]
(ε es muy pequeño)
3. Cero conocimiento (Zero-Knowledge)
Existe un simulador ( S ):
[
\text{View}_V(P(x,w)) \approx S(x)
]
- Significa que el verificador no aprende nada nuevo
Forma práctica usada en ZKP modernos
En sistemas como ZoKrates o Circom:
[
\text{Probar: } \exists w \ \text{tal que} \ C(x, w) = 0
]
Donde:
( C ) = circuito (constraints)
( x ) = inputs públicos
( w ) = inputs privados
Ejemplo concreto (muy típico)
[
\text{Demostrar que conoces } x \text{ tal que:}
]
[
H(x) = y
]
Sin revelar ( x )
Versión tipo “SNARK” (más avanzada)
Un zk-SNARK típicamente se expresa como:
[
\pi = \text{Prove}(pk, x, w)
]
[
\text{Verify}(vk, x, \pi) = \text{true}
]
Donde:
( pk ) = proving key
( vk ) = verification key
( \pi ) = proof
Conexión con la caverna de Alibaba
( w ) = contraseña
( x ) = problema (la puerta)
( R(x,w)=1 ) = “puedes abrir la puerta”
Resumen corto
La “fórmula central” de ZKP es:
[
\exists w:\ R(x,w)=1
]
👉 Demostrar que sabes ( w )
👉 Sin revelar ( w )
zk-SNARK: el uso de QAP (Quadratic Arithmetic Programs).
🧠 1. De circuito a polinomios (idea clave)
En herramientas como Circom o ZoKrates, todo parte así:
[
C(x, w) = 0
]
Ese circuito se transforma en polinomios:
( A_i(x) )
( B_i(x) )
( C_i(x) )
Y un vector de valores:
( a = (a_1, a_2, ..., a_n) )
🔢 2. Fórmula central del QAP
Aquí está el corazón del zk-SNARK:
[
\left( \sum_i a_i A_i(x) \right)\left( \sum_i a_i B_i(x) \right) - \left( \sum_i a_i C_i(x) \right) = H(x) \cdot Z(x)
]
🔍 Qué significa cada cosa
( a_i ): valores del circuito (inputs + witness)
( A_i, B_i, C_i ): polinomios derivados del circuito
( Z(x) ): polinomio objetivo (raíces en puntos de evaluación)
( H(x) ): polinomio “cociente”
👉 Esta ecuación garantiza que todas las constraints se cumplen
⚙️ 3. Intuición simple
Lado izquierdo = “resultado del circuito”
Lado derecho = “múltiplo de algo que debe ser cero en puntos clave”
👉 Si no se cumplen las constraints → no es divisible → prueba inválida
🔐 4. Cómo aparece la prueba (SNARK)
Luego se construye:
[
\pi = \text{Prove}(pk, x, w)
]
[
\text{Verify}(vk, x, \pi) = \text{true}
]
Pero internamente, lo que se está probando es:
👉 que la ecuación del QAP se cumple
👉 sin revelar ( w )
🧩 5. Rol de los polinomios Z(x)
[
Z(x) = (x - r_1)(x - r_2)\cdots(x - r_n)
]
Donde ( r_i ) son puntos asociados a cada constraint.
👉 Si algo falla → la división no es exacta
🔒 6. Por qué es “zero knowledge”
Se agregan:
blinding factors (aleatoriedad)
compromisos criptográficos
👉 Así el verificador ve:
que la ecuación es válida
pero no los valores ( a_i )
🧠 7. Resumen brutal
Un zk-SNARK prueba:
[
\text{“Existe } w \text{ tal que el circuito es válido”}
]
reduciéndolo a:
[
\text{“Este polinomio divide perfectamente a otro”}
]
8. Traducción mental (clave)
Circuito → constraints
Constraints → polinomios
Polinomios → divisibilidad
Divisibilidad → prueba criptográfica
----------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------
👉 demostrar que conoces ( x ) tal que
[
x \cdot x = y
]
sin revelar ( x )
1. Convertir a circuito
Primero lo escribimos como circuito:
Input público: ( y )
Witness (secreto): ( x )
Constraint:
[
x \cdot x - y = 0
]
2. Vector de variables
Definimos el vector:
[
a = [1, x, y]
]
👉 El 1 siempre está (para constantes)
3. Forma R1CS (clave antes del QAP)
Queremos:
[
(A \cdot a) \cdot (B \cdot a) = (C \cdot a)
]
Para este caso:
( A = [0, 1, 0] ) → selecciona ( x )
( B = [0, 1, 0] ) → selecciona ( x )
( C = [0, 0, 1] ) → selecciona ( y )
Entonces:
[
(x)(x) = y
]
4. Pasar a QAP (polinomios)
Como solo hay 1 constraint, usamos un punto ( r_1 )
Construimos polinomios tales que:
( A(x) = x ) evaluado en ( r_1 )
( B(x) = x )
( C(x) = y )
Formalmente:
[
A_1(t),\ B_1(t),\ C_1(t)
]
5. Fórmula del QAP aplicada
\left(\sum_i a_i A_i(t)\right)\left(\sum_i a_i B_i(t)\right) - \left(\sum_i a_i C_i(t)\right) = H(t)Z(t)
En este caso concreto:
[
(x)(x) - y = H(t)\cdot Z(t)
]
6. Polinomio Z(t)
Como hay 1 constraint:
[
Z(t) = (t - r_1)
]
7. Qué debe cumplirse
Para que la prueba sea válida:
[
x^2 - y = 0
]
👉 Entonces el lado izquierdo es divisible por ( Z(t) )
8. Qué prueba el SNARK
El prover demuestra que:
conoce ( x )
tal que ( x^2 = y )
pero el verificador solo ve la prueba, no ( x )
9. Intuición final (muy importante)
Este ejemplo muestra todo el pipeline:
Ecuación simple → ( x^2 = y )
Circuito → constraint
Constraint → R1CS
R1CS → QAP
QAP → prueba criptográfica
10. Traducción mental útil
Esto equivale a decir:
👉 “sé la raíz cuadrada de ( y )”
👉 sin decir cuál es
No comments :
Post a Comment