ZKP (Zero-Knowledge Proofs)

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

La Caverna de Alibaba

La expresión “caverna de Alibaba” en el contexto de ZKP (Zero-Knowledge Proofs) se refiere a un ejemplo clásico para explicar cómo alguien puede demostrar que sabe un secreto sin revelarlo. Es una analogía muy usada en criptografía.

---

 La “Caverna de Alibaba” (concepto)

Imagina esto:

• Hay una cueva en forma de círculo con dos caminos (A y B).

• En el fondo hay una puerta secreta que solo se abre con una contraseña.

• Una persona (Peggy) dice que conoce la contraseña.

• Otra persona (Victor) quiere verificarlo sin que Peggy revele la contraseña.

---

 Cómo funciona la prueba

1. Peggy entra a la cueva por A o B (sin que Victor vea cuál).

2. Victor entra después y le grita: “¡Sal por A!” o “¡Sal por B!”

3. Si Peggy realmente conoce la contraseña:

   • Puede abrir la puerta secreta y salir por el camino que Victor pidió.

4. Si NO conoce la contraseña:

   • Solo puede salir por donde entró → tiene 50% de probabilidad de acertar.

 Repitiendo esto muchas veces, Victor gana confianza de que Peggy sí sabe el secreto, sin que nunca lo revele.

---

Qué representa en ZKP

• Peggy = el prover

• Victor = el verifier

• La contraseña = el secreto

• La puerta = una función difícil de invertir (criptográfica)

Este modelo captura las propiedades clave de los ZKP:

1. Completitud → si sabes el secreto, siempre puedes demostrarlo

2. Solidez (soundness) → si no lo sabes, es muy difícil engañar

3. Cero conocimiento → no revelas el secreto

---

Cómo se conecta con herramientas reales

Esto es solo una analogía. En sistemas reales como:

• ZoKrates

• Circom

• Noir

• Cairo

…la “puerta secreta” se transforma en:

• circuitos aritméticos

• constraints

• polinomios (SNARKs/STARKs)

---

 Intuición final

La caverna de Alibaba te enseña esto:

- Puedes probar conocimiento sin revelar información

- Eso es exactamente lo que hacen los ZKP modernos, pero con matemáticas en lugar de cuevas

---

---