Un Trusted Setup es un mecanismo que los ZK-SNARKs utilizan para evaluar un polinomio en un valor secreto.

Observa que un polinomio $f(x)$ puede ser evaluado calculando el producto interno de los coeficientes con potencias sucesivas de $x$:

Por ejemplo, si $f(x)=3x^3+2x^2+5x+10$, entonces los coeficientes son $[3,2,5,10]$ y podemos calcular el polinomio como

En otras palabras, normalmente pensamos en evaluar $f(2)$ para el polinomio anterior como

pero también podríamos evaluarlo como

Ahora supongamos que alguien elige un escalar secreto $\tau$ y calcula

y luego multiplica cada uno de esos puntos por el punto generador de un grupo criptográfico de curva elíptica. El resultado sería el siguiente:

Ahora cualquiera puede tomar la cadena de referencia estructurada (SRS, por sus siglas en inglés) $[\Omega_3, \Omega_2, \Omega_1, G_1]$ y evaluar un polinomio de grado tres (o menor) en $\tau$.

Por ejemplo, si tenemos un polinomio de grado 2 $g(x)=4x^2+7x+8$, podemos evaluar $g(\tau)$ tomando el producto interno de la cadena de referencia estructurada con el polinomio:

¡Ahora hemos calculado $g(\tau)$ sin saber qué es $\tau$!

A esto también se le llama un trusted setup porque, aunque nosotros no sabemos cuál es el logaritmo discreto de $g(\tau)$, la persona que creó la cadena de referencia estructurada sí lo sabe. Esto podría llevar a la filtración de información en el futuro, por lo que confiamos en que la entidad que crea el trusted setup elimine $\tau$ y no lo recuerde de ninguna manera.

Ejemplo en Python

Copy
from py_ecc.bn128 import G1, multiply, add
from functools import reduce

def inner_product(points, coeffs):
    return reduce(add, map(multiply, points, coeffs))

## Trusted Setup
tau = 88
degree = 3

# tau^3, tau^2, tau, 1
srs = [multiply(G1, tau**i) for i in range(degree,-1,-1)]

## Evaluate
# p(x) = 4x^2 + 7x + 8
coeffs = [0, 4, 7, 8]

poly_at_tau = inner_product(srs, coeffs)

Verificando que un Trusted Setup se haya generado correctamente

Dada una cadena de referencia estructurada, ¿cómo sabemos siquiera que sigue la estructura $[x^d, x^{d-1},\dots,x,1]$ y que no fue elegida al azar?

Si la persona que realiza el trusted setup también proporciona $\Theta=\tau G_2$, podemos validar que la cadena de referencia estructurada son de hecho potencias sucesivas de $\tau$.

donde $e$ es un emparejamiento bilineal. Intuitivamente, estamos calculando $\tau\cdot\tau^i$ en el lado izquierdo y $1\cdot\tau^{i+1}$ en el lado derecho.

Para validar que $\Theta$ y $\Omega_1$ tienen los mismos logaritmos discretos (se supone que $\Omega_1$ es $\tau G_1$), podemos verificar que

Generación de una cadena de referencia estructurada como parte de una computación multipartita

No es una buena suposición de confianza creer que la persona que generó la cadena de referencia estructurada realmente eliminó $\tau$.

A continuación describimos el algoritmo para que múltiples partes creen colaborativamente la cadena de referencia estructurada, y siempre que una de ellas sea honesta (es decir, elimine $\tau$), entonces los logaritmos discretos de la cadena de referencia estructurada serán desconocidos.

Alice genera la cadena de referencia estructurada $([\Omega_n,...,\Omega_2,\Omega_1, G_1],\Theta)$ y se la pasa a Bob.

Bob verifica que el SRS es “correcto” utilizando las comprobaciones de la sección anterior. Luego, Bob elige su propio parámetro secreto $\gamma$ y calcula

Ten en cuenta que los logaritmos discretos del srs ahora son

Si Alice o Bob eliminan su $\tau$ o $\gamma$, entonces los logaritmos discretos del srs final no son recuperables.

Por supuesto, no necesitamos limitar los participantes a dos; podríamos tener tantos participantes como quisiéramos.

Esta computación multipartita se conoce a menudo informalmente como la ceremonia powers of tau.

El uso de un Trusted Setup en ZK-SNARKs

Evaluar un polinomio en una cadena de referencia estructurada no revela información sobre el polinomio al verificador (verifier), y el probador (prover) no sabe en qué punto está evaluando. Veremos más adelante que este esquema ayuda a evitar que el probador haga trampa y contribuye a mantener su testigo (witness) en conocimiento cero (zero knowledge).