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
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
$$
($\epsilon$ es muy pequeño)
3. Cero conocimiento (Zero-Knowledge)
$$
\text{View}_V(P(x,w)) \approx S(x)
$$
El verificador no aprende nada nuevo
Forma práctica usada en ZKP modernos
$$
\text{Probar: } \exists w \ \text{tal que} \ C(x, w) = 0
$$
- $C$ = circuito
- $x$ = inputs públicos
- $w$ = inputs privados
Ejemplo concreto
$$
\text{Demostrar que conoces } x \text{ tal que } H(x) = y
$$
Sin revelar $x$
Versión tipo SNARK
$$
\pi = \text{Prove}(pk, x, w)
$$
$$
\text{Verify}(vk, x, \pi) = \text{true}
$$
- $pk$ = proving key
- $vk$ = verification key
- $\pi$ = proof
Resumen
$$
\exists w:\ R(x,w)=1
$$
Demostrar que sabes $w$ sin revelarlo
QAP (Quadratic Arithmetic Programs)
1. Circuito a polinomios
$$
C(x, w) = 0
$$
- $A_i(x)$
- $B_i(x)$
- $C_i(x)$
Vector:
$$
a = (a_1, a_2, ..., a_n)
$$
2. Fórmula central del QAP
$$
\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)
$$
3. Polinomio Z(x)
$$
Z(x) = (x - r_1)(x - r_2)\cdots(x - r_n)
$$
Ejemplo completo
Demostrar que conoces $x$ tal que:
$$
x \cdot x = y
$$
1. Circuito
$$
x \cdot x - y = 0
$$
2. Vector
$$
a = [1, x, y]
$$
3. R1CS
$$
(A \cdot a)(B \cdot a) = (C \cdot a)
$$
Con:
- $A = [0,1,0]$
- $B = [0,1,0]$
- $C = [0,0,1]$
$$
x \cdot x = y
$$
4. QAP
$$
(x)(x) - y = H(t)\cdot Z(t)
$$
5. Z(t)
$$
Z(t) = (t - r_1)
$$
6. Condición
$$
x^2 - y = 0
$$
Resumen final
Esto equivale a decir:
👉 “sé la raíz cuadrada de $y$” sin revelarla