Casi todos los algoritmos ZK-Proof dependen del Lema de Schwartz-Zippel para lograr concisión.

El Lema de Schwartz-Zippel establece que si se nos dan dos polinomios $p(x)$ y $q(x)$ con grados $d_p$ y $d_q$ respectivamente, y si $p(x) \neq q(x)$, entonces el número de puntos donde $p(x)$ y $q(x)$ se intersecan es menor o igual a $\mathsf{max}(d_p, d_q)$.

Consideremos algunos ejemplos.

Polinomios de ejemplo y el Lema de Schwartz-Zippel

Una línea recta cruzando una parábola

Consideremos el polinomio $p(x) = x$ y $q(x) = x^2$. Se intersecan en $x = 0$ y $x = 1$.

Se intersecan en dos puntos, que es el grado máximo entre los polinomios $y = x$ e $y = x^2$.

Un polinomio de grado tres y un polinomio de grado uno

Consideremos los polinomios $p(x) = x^3$ y $q(x) = x$. Los polinomios se intersecan en $x = -1$, $x = 0$ y $x = 1$ y en ningún otro lugar. El número de intersecciones está limitado por el grado máximo de los polinomios, que en este caso es 3.

Polinomios en campos finitos y el Lema de Schwartz-Zippel

El Lema de Schwartz-Zippel se cumple para polinomios en campos finitos (es decir, todos los cálculos se realizan módulo un primo $p$).

Prueba de igualdad de polinomios

Podemos comprobar que dos polinomios son iguales verificando si todos sus coeficientes son iguales, pero esto toma un tiempo de $\mathcal{O}(d)$, donde $d$ es el grado del polinomio.

En su lugar, podemos evaluar los polinomios en un punto aleatorio $u$ y comparar las evaluaciones en un tiempo de $\mathcal{O}(1)$.

Es decir, en un campo finito $\mathbb{F}_{p}$, elegimos un valor aleatorio $u$ de $[0,p)$. Luego evaluamos $y_f=f(u)$ y $y_g=g(u)$. Si $y_f = y_g$, entonces una de dos cosas debe ser cierta:

1. $f(x) = g(x)$
2. $f(x) \neq g(x)$ y elegimos uno de los $d$ puntos donde se intersecan, donde $d = \mathsf{max}(\deg(f), \deg(g))$

Si $d \ll p$, entonces la situación 2 es improbable hasta el punto de ser despreciable.

Por ejemplo, si el campo $\mathbb{F}_{p}$ tiene $p \approx 2^{254}$ (un poco más pequeño que un uint256), y si los polinomios no tienen un grado superior a un millón, entonces la probabilidad de elegir un punto donde se intersecan es

Para dar una idea de la escala de esto, el número de átomos en el universo es de aproximadamente $10^{78}$ a $10^{82}$, por lo que es extremadamente improbable que elijamos un punto donde los polinomios se intersequen, si los polinomios no son iguales.

Uso del Lema de Schwartz-Zippel para comprobar si dos vectores son iguales

Podemos combinar la interpolación de Lagrange con el Lema de Schwartz-Zippel para comprobar si dos vectores son iguales.

Normalmente, comprobaríamos la igualdad de vectores comparando si cada uno de los $n$ componentes de los vectores son iguales.

En su lugar, si usamos un conjunto común de valores de $x$ (digamos $[1,2,..,n]$) para interpolar los vectores:

1. Podemos interpolar un polinomio para cada vector $f(x)$ y $g(x)$
2. Elegir un punto aleatorio $u$
3. Evaluar los polinomios en $u$
4. Comprobar si $f(u) = g(u)$

Aunque calcular los polinomios requiere más trabajo, la comprobación final es mucho menos costosa.

Aquí hay un ejemplo de cómo llevar a cabo este cálculo en Python:

Copy
import galois
import numpy as np

p = 103
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# arbitrary vectors
v1 =  GF(np.array([4,8,19]))
v2 =  GF(np.array([4,8,19]))


def L(v):
    return galois.lagrange_poly(xs, v)

p1 = L(v1)
p2 = L(v2)

import random
u = random.randint(0, p)

lhs = p1(u)
rhs = p2(u)

# only one check required
assert lhs == rhs

Uso del Lema de Schwartz-Zippel en las ZK Proofs

Nuestro objetivo final es que el probador envíe una pequeña cadena de datos al verificador que este último pueda comprobar rápidamente.

La mayoría de las veces, una prueba ZK es esencialmente un polinomio evaluado en un punto aleatorio.

La dificultad que tenemos que resolver es que no sabemos si el polinomio se evalúa honestamente; de alguna manera, tenemos que confiar en que el probador no está mintiendo cuando evalúa $f(u)$.

Pero antes de llegar a eso, necesitamos aprender a representar un circuito aritmético completo como un pequeño conjunto de polinomios evaluados en un punto aleatorio, que es la motivación de los Quadratic Arithmetic Programs.