Groth16 Explicado

Last updated on Mar 16, 2026

El algoritmo Groth16 permite que un Programa Aritmético Cuadrático (QAP) sea calculado por un prover sobre puntos de curva elíptica derivados en un trusted setup, y verificado rápidamente por un verifier. Utiliza puntos auxiliares de curva elíptica del trusted setup para evitar pruebas falsificadas.

Prerrequisitos

Este artículo es un capítulo en el RareSkills Book of Zero Knowledge Proofs. Se asume que estás familiarizado con los capítulos anteriores.

Notación

Nos referimos a un punto de curva elíptica que pertenece al grupo de curva elíptica $\mathbb{G}_1$ como $[x]_1$ y a un punto de curva elíptica que pertenece al grupo de curva elíptica $\mathbb{G}_2$ como $[x]_2$ . Un emparejamiento entre $[x]_1$ y $[x]_2$ se denota como $[x]_1\bullet[x]_2$ y produce un elemento en $\mathbb{G}_{12}$ . Las variables en negrita como $\mathbf{a}$ son vectores, las letras mayúsculas en negrita como $\mathbf{L}$ son matrices, y los elementos de campo (a veces referidos informalmente como “escalares”) son letras minúsculas como $d$ . Todas las operaciones aritméticas ocurren en un campo finito con una característica que es igual al orden del grupo de curva elíptica.

Dado un circuito aritmético (circuito ZK), lo convertimos en un sistema de restricciones de rango 1 (R1CS) $\mathbf{L}\mathbf{a}\circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$ con matrices de dimensión de $n$ filas y $m$ columnas con un vector testigo (witness) $\mathbf{a}$ . Luego, podemos convertir el R1CS a un Programa Aritmético Cuadrático (QAP) interpolando las columnas de las matrices como valores $y$ sobre los valores $x$ $[1,2,...,n]$ . Dado que $\mathbf{L}$ , $\mathbf{R}$ y $\mathbf{O}$ tienen $m$ columnas, terminaremos con tres conjuntos de $m$ polinomios:

\begin{array}{} u_1(x),...,u_m(x) & m \text{ polinomios interpolados en las }m \text{ columnas de } \mathbf{L}\\ v_1(x),...,v_m(x)& m \text{ polinomios interpolados en las }m \text{ columnas de } \mathbf{R}\\ w_1(x),...,w_m(x)& m \text{ polinomios interpolados en las }m \text{ columnas de } \mathbf{O}\\ \end{array}

A partir de esto, podemos construir un Programa Aritmético Cuadrático (QAP):

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

donde

t(x) = (x - 1)(x - 2)\dots(x - n)

h(x) = \frac{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)}

Si un tercero crea una cadena de referencia estructurada (srs) mediante una ceremonia de powers of tau, entonces el prover puede evaluar los términos de suma (los términos $\sum a_if_i(x)$ ) en el QAP en un punto oculto $\tau$ . Supongamos que las cadenas de referencia estructuradas se calculan de la siguiente manera:

\begin{align*} [\Omega_{n-1}, \Omega_{n-2},\dots,\Omega_2,\Omega_1,G_1] &= [\tau^nG_1,\tau^{n-1}G_1,\dots,\tau G_1,G_1] && \text{srs para } G_1 \\ [\Theta_{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_1,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && \text{srs para } G_2\\ [\Upsilon_{n-2},\Upsilon_{n-3},\dots,\Upsilon_1,\Upsilon_0]&=[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] && \text{srs para }h(\tau)t(\tau)\\ \end{align*}

Nos referimos a $f(\tau)$ como un polinomio evaluado en una cadena de referencia estructurada $[\tau^dG_1,...,\tau^2G_1,\tau G_1,G_1]$ mediante el producto interno:

f(\tau) = \sum_{i=1}^d f_i\Omega_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Omega_d,\Omega_{d-1},...,G_1]\rangle

o para el srs de $\mathbb{G}_2$ :

f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Theta_d,\Theta_{d-1},...,G_2]\rangle

$f(\tau)$ es una abreviatura para la expresión anterior, y produce un punto de curva elíptica. No significa que el prover conozca $\tau$ .

El prover puede evaluar su QAP en el trusted setup calculando:

\begin{align*} [A]_1 &= \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) \end{align*}

Los detalles de este cálculo se discuten en nuestro tutorial Quadratic Arithmetic Programs over Elliptic Curves.

Si el QAP está equilibrado, entonces se cumple la siguiente ecuación:

[A]_1\bullet[B]_2 \stackrel{?}= [C]_1\bullet G_2

Motivación

Simplemente presentar $([A]_1, [B]_2, [C]_1)$ no es un argumento convincente de que el prover conoce $\mathbf{a}$ tal que el QAP está equilibrado.

El prover simplemente puede inventar valores $a$ , $b$ , $c$ donde $ab = c$ , calcular

\begin{align*} [A]_1 &= aG_1\\ [B]_2 &= bG_2\\ [C]_1 &= cG_1 \end{align*}

y presentarlos como puntos de curva elíptica $[A]_1$ , $[B]_2$ , $[C]_1$ al verifier.

Por lo tanto, el verifier no tiene idea de si $([A]_1, [B]_2, [C]_1)$ fueron el resultado de un QAP satisfecho o no.

Necesitamos forzar al prover a ser honesto sin introducir demasiada sobrecarga computacional. El primer algoritmo en lograr esto fue “Pinocchio: Nearly Practical Verifiable Computation”. Esto fue lo suficientemente utilizable como para que ZCash basara la primera versión de su blockchain en él.

Sin embargo, Groth16 logró hacer lo mismo en muchos menos pasos, y el algoritmo todavía se usa ampliamente en la actualidad, ya que ningún algoritmo desde entonces ha producido un algoritmo tan eficiente para el paso de verificación (aunque otros algoritmos han eliminado el trusted setup o reducido significativamente la cantidad de trabajo para el prover).

Actualización para 2024: Un artículo titulado de manera bastante triunfal “Polymath: Groth16 is not the limit” publicado en Cryptology demuestra un algoritmo que requiere menos pasos del verifier que Groth16. Sin embargo, no se conocen implementaciones del algoritmo al momento de escribir este documento.

Previniendo la falsificación Parte 1: Introduciendo $\alpha$ y $\beta$

Una fórmula de verificación “irresoluble”

Supongamos que actualizamos nuestra fórmula de verificación a lo siguiente:

[A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2

Nota que estamos usando notación aditiva para el grupo $G_{12}$ por conveniencia.

Aquí, $[D]_{12}$ es un elemento de $G_{12}$ y tiene un logaritmo discreto desconocido.

Ahora mostramos que es imposible para que un verifier proporcione una solución $([A]_1, [B]_2, [C]_1)$ a esta ecuación, sin conocer el logaritmo discreto de $[D]_{12}$ .

Ataque 1: Falsificando A y B y derivando C

Supongamos que el prover selecciona aleatoriamente $a’$ y $b’$ para producir $[A]₁$ y $[B]₂$ e intenta derivar un valor $[C’]$ que sea compatible con la fórmula del verifier.

[A]_1 \bullet [B]_2 \stackrel{?}= [D]_{12} + [C]_1\bullet G_2

Conociendo los logaritmos discretos de $[A]₁$ y $[B]₂$ , el prover malicioso intenta resolver para $[C’]$ haciendo

\begin{align*}\underbrace{[A]_1\bullet [B]_2 - [D]_{12}}_{\chi_{12}}=[C']_1\bullet G_2\\ [\chi]_{12}=[C']_1\bullet G_2 \end{align*}

La línea final requiere que el prover resuelva el logaritmo discreto de $\chi_{12}$ , por lo que no puede calcular un logaritmo discreto válido para $[C']_1$ .

Ataque 2: Falsificando C y derivando A y B

Aquí el prover elige un punto aleatorio $c'$ y calcula $[C']_1$ . Debido a que conoce $c'$ , puede intentar descubrir una combinación compatible de $a'$ y $b'$ tal que

\begin{align*}[A]_1 \bullet [B]_2 &\stackrel{?}= \underbrace{[D]_{12} + [C]_1\bullet G_2}_{[\zeta]_{12}}\\ [A]_1 \bullet [B]_2 &\stackrel{?}=[\zeta]_{12} \end{align*}

Esto requiere que el prover, dado $[\zeta]_{12}$ , proponga un $[A]₁$ y un $[B]₂$ que se emparejen para producir $[\zeta]_{12}$ .

Al igual que en el problema del logaritmo discreto, dependemos de suposiciones criptográficas no probadas de que este cálculo (descomponer un elemento de $\mathbb{G}_{12}$ en un elemento de $\mathbb{G}_1$ y $\mathbb{G}_2$ ) es inviable. En este caso, la suposición de que no podemos descomponer $[\zeta]_{12}$ en $[A]₁$ y $[B]₂$ se llama la Suposición Bilineal de Diffie-Hellman (Bilinear Diffie-Hellman Assumption). El lector interesado puede ver una discusión relacionada sobre la Decisional Diffie-Hellman Assumption.

(No probada no significa poco confiable. Si puedes encontrar una forma de probar o refutar esta suposición, ¡la fama y la fortuna te esperan! En la práctica, no se conoce una forma de descomponer $[\zeta]_{12}$ en $[A]₁$ y $[B]₂$ y se cree que es computacionalmente inviable).

Cómo se usan $\alpha$ y $\beta$

En la práctica, Groth16 no utiliza un término $[D]_{12}$ . En cambio, el trusted setup genera dos escalares aleatorios $\alpha$ y $\beta$ y publica los puntos de curva elíptica $([\alpha]_1,[\beta]_2)$ calculados como:

\begin{align*} [α]_1 &= α G_1 \\ [β]_2 &= β G_2 \end{align*}

A lo que nos referimos como $[D]_{12}$ es simplemente $[\alpha]_1 \bullet [\beta]_2$ .

Rederivando las fórmulas de prueba y verificación

Para hacer la fórmula de verificación $[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1\bullet[\beta]_2 + [C]_1\bullet G_2$ “resoluble”, necesitamos alterar nuestra fórmula del QAP para incorporar $\alpha$ y $\beta$ .

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

Ahora considera qué sucede si introducimos los términos $\theta$ y $\eta$ en el lado izquierdo de la ecuación:

\left(\boxed{\theta}+\sum_{i=1}^m a_iu_i(x)\right)\left(\boxed{\eta} +\sum_{i=1}^m a_iv_i(x)\right) =

=\boxed{\theta\eta} + \boxed{\theta}\sum_{i=1}^m a_iv_i(x) + \boxed{\eta}\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)

Podemos sustituir los términos más a la derecha usando la definición original del QAP:

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}

Ahora podemos introducir un QAP “expandido” con la siguiente definición:

\left(\theta+\sum_{i=1}^m a_iu_i(x)\right)\left(\eta +\sum_{i=1}^m a_iv_i(x)\right) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

Como un adelanto de hacia dónde vamos, si reemplazamos $\theta$ con $[\alpha]_1$ y $\eta$ con $[\beta]_2$ , obtenemos la fórmula de verificación actualizada de antes:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2

donde

\underbrace{\left([\alpha]_1+\sum_{i=1}^m a_iu_i(\tau)\right)}_{[A]_1}\underbrace{\left([\beta]_2 +\sum_{i=1}^m a_iv_i(\tau)\right)}_{[B]_2} =[\alpha]_1\bullet[\beta]_2 + \underbrace{\left(\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)\right)}_{[C]_1} \bullet G_2

El prover puede calcular $[A]_1$ y $[B]_2$ sin conocer $\tau$ , $\alpha$ o $\beta$ . Dada la cadena de referencia estructurada (potencias de $\tau$ ) y los puntos de curva elíptica $([α]_1,[β]_2)$ , el prover calcula $[A]_1$ y $[B]_2$ como

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ \end{align*}

Aquí, $a_iu_i(\tau)$ no significa que el prover conozca $\tau$ . El prover está usando la cadena de referencia estructurada $[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1]$ para calcular $u_i(\tau)$ para $i=1,2,\dots,m$ y el srs de $G_2$ para $[B]_2$ .

Sin embargo, actualmente no es posible calcular $[C]_1$ sin conocer $\alpha$ y $\beta$ . El prover no puede emparejar $[\alpha]_1$ con $\sum a_iu_i(\tau)$ y $[\beta]_2$ con $\sum a_iv_i(\tau)$ porque eso crearía un punto en $\mathbb{G}_{12}$ , mientras que el prover necesita un punto en $\mathbb{G}_1$ para $[C]_1$ .

En su lugar, el trusted setup necesita precalcular $m$ polinomios para el problemático término $C$ del QAP expandido.

\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau)

Con un poco de manipulación algebraica, combinamos los términos de las sumas en una sola suma:

=\sum_{i=1}^m (\alpha a_iv_i(\tau)+\beta a_iu_i(\tau) + a_iw_i(\tau))

y factorizamos $a_i$ :

=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}

El trusted setup puede crear $m$ polinomios evaluados en $\tau$ a partir del término recuadrado anterior, y el prover puede usar eso para calcular la suma. Los detalles exactos se muestran en la siguiente sección.

Resumen del algoritmo hasta ahora

Pasos del trusted setup

Concretamente, el trusted setup calcula lo siguiente:

\begin{align*} \alpha,\beta,\tau &\leftarrow \text{escalares aleatorios}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs para } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs para } \mathbb{G}_2\\ [\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] &\leftarrow \text{srs para }h(\tau)t(\tau)\\ [\Psi_1]_1 &= (\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau))G_1\\ [\Psi_2]_1 &= (\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau))G_1\\ &\vdots\\ [\Psi_m]_1 &= (\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau))G_1\\ \end{align*}

El trusted setup publica

([\alpha]_1,[\beta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs para }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Pasos del prover

El prover calcula

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

Nota que reemplazamos el polinomio “problemático”

=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}

(el que contenía $\alpha$ y $\beta$ ) con

\sum_{i=1}^m a_i[\Psi_i]_1

Pasos del verifier

El verifier calcula:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2

Soportando inputs públicos

La fórmula del verifier hasta ahora no soporta inputs públicos, es decir, hacer pública una porción del testigo (witness).

Por convención, las porciones públicas del witness son los primeros $\ell$ elementos del vector $\mathbf{a}$ . Para hacer públicos esos elementos, el prover simplemente los revela:

[a_1, a_2, \dots, a_\ell]

Para que el verifier pruebe que esos valores fueron de hecho utilizados, el verifier debe llevar a cabo parte del cálculo que el prover estaba haciendo originalmente.

Específicamente, el prover calcula:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

Nota que solo el cálculo de $[C]_1$ cambió – el prover solo usa los términos $a_i$ y $\Psi_i$ desde $\ell + 1$ hasta $m$ .

El verifier calcula los primeros $\ell$ términos de la suma:

[X]_1=\sum_{i=1}^\ell a_i\Psi_i

Y la ecuación de verificación es:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet G_2 + [C]_1\bullet G_2

Parte 2: Separando los inputs públicos de los inputs privados con $\gamma$ o $\delta$

Falsificando pruebas por el mal uso de $\Psi_i$ para $i\leq\ell$

La suposición en la ecuación anterior es que el prover solo está usando de $\Psi_{\ell+1}$ a $\Psi_m$ para calcular $[C]_1$ , pero nada impide que un prover deshonesto use de $\Psi_1$ a $\Psi_{\ell}$ para calcular $[C]_1$ , lo que lleva a una prueba falsificada.

Por ejemplo, aquí está nuestra ecuación de verificación actual:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + [C]_1\bullet G_2

Si expandimos el término C subyacente, obtenemos lo siguiente:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + \sum_{i=1}^\ell a_i\Psi_i + \underbrace{\left(\sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\right)}_C \bullet G_2

Supongamos, por ejemplo y sin pérdida de generalidad, que $\mathbf{a} = [1,2,3,4,5]$ y $\ell=3$ . En ese caso, la parte pública del witness es $[1,2,3]$ y la parte privada es $[4,5]$ .

La ecuación final sería la siguiente:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+3\Psi_3)\bullet G2 + \underbrace{(4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

Sin embargo, nada impide que el prover cree una porción válida del witness público como [1,2,0] y mueva la porción pública anulada a la parte privada del cálculo de la siguiente manera:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+\boxed{0\Psi_3})\bullet G2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

La ecuación anterior es válida, pero el witness no satisface necesariamente las restricciones originales.

Por lo tanto, necesitamos evitar que el prover use de $\Psi_1$ a $\Psi_{\ell}$ como parte del cálculo de $[C]_1$ .

Introduciendo $\gamma$ y/o $\delta$

Para evitar el problema anterior, el trusted setup introduce un nuevo escalar: $\gamma$ o $\delta$ para forzar a que $\Psi_{\ell+1}$ a $\Psi_m$ estén separados de $\Psi_1$ a $\Psi_{\ell}$ . Para hacer esto, el trusted setup divide (multiplica por el inverso modular) los términos privados (que constituyen $[C]_1$ ) por $\delta$ y/o los términos públicos (que constituyen $[X]_1$ , la suma que calcula el verifier) por $\gamma$ .

Dado que el término $h(\tau)t(\tau)$ está incrustado en $[C]_1$ , esos términos también necesitan ser divididos por $\delta$ . Si tanto $\delta$ como $\gamma$ tienen un logaritmo discreto desconocido, entonces la falsificación descrita anteriormente, junto con otros métodos posibles, se evitan. Este método se utilizó en los trusted setups basados en Sapling de Zcash, donde $\gamma$ simplemente se deja en $G_2$ y $\delta$ todavía se actualiza desde $G_2$ a un valor aleatorio en etapas posteriores del trusted setup.

\begin{align*} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{escalares aleatorios}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs para } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs para } \mathbb{G}_2\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow \text{srs para }h(\tau)t(\tau)\\ \\ &\text{porción pública del witness}\\ [\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{porción privada del witness}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\ &\vdots\\ [\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\ \end{align*}

El trusted setup publica

([\alpha]_1,[\beta]_2,[\gamma]_2,[\delta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs para }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Los pasos del prover son los mismos que antes:

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\\ \end{align*}

Y los pasos del verifier ahora incluyen emparejar con $[\gamma]_2$ y/o $[\delta]_2$ para cancelar los denominadores:

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

Parte 3: Haciendo cumplir el verdadero zero knowledge: r y s

Nuestro esquema aún no es verdaderamente zero knowledge. Si un atacante es capaz de adivinar nuestro vector witness (lo cual es posible si solo hay un rango pequeño de inputs válidos, ej. votación secreta de direcciones privilegiadas), entonces puede verificar que su suposición es correcta comparando su prueba construida con la prueba original.

Como ejemplo trivial, supongamos que nuestra afirmación es que $x_1$ y $x_2$ son ambos ya sea $0$ o $1$ . El circuito aritmético correspondiente sería

\begin{align*} x_1 (x_1 - 1) = 0\\ x_2 (x_2 - 1) = 0 \end{align*}

Un atacante solo necesita adivinar cuatro combinaciones para descubrir cuál es el witness. Es decir, adivinan un witness, generan una prueba y ven si su respuesta coincide con la prueba original.

Para evitar que adivinen, el prover necesita añadir “salt” a su prueba, y la ecuación de verificación debe ser modificada para acomodar el salt.

El prover muestrea dos elementos de campo aleatorios $r$ y $s$ y los añade a $A$ y $B$ para hacer el witness impredecible – un atacante tendría que adivinar tanto el witness como los salts $r$ y $s$ :

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau) + r[\delta]_1\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_2\\ [B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau) + s[\delta]_1\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau) + As+Br-rs[\delta]_1\\ \end{align*}

Para derivar la fórmula de verificación final, ignoremos temporalmente que no conocemos los logaritmos discretos de los términos con letras griegas y calculemos el lado izquierdo de la ecuación de verificación $AB$ :

\underbrace{\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)}_A \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)}_B

Expandiendo los términos obtenemos:

\alpha\beta+\alpha\sum_{i=1}^m a_iv_i(x)+\alpha s\delta + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta

Podemos seleccionar los términos originales para $C$

\alpha\beta+\boxed{\alpha\sum_{i=1}^m a_iv_i(x)}+\alpha s\delta + \boxed{\beta\sum_{i=1}^m a_iu_i(x)} + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+\sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta

Y combinarlos a la izquierda, dejando los nuevos términos a la derecha:

\alpha\beta + \boxed{\alpha\sum_{i=1}^m a_iv_i(x) + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+ \underline{\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + r\delta s\delta}

Reorganizamos además los términos subrayados para escribirlos en términos de $As\delta$ y $Br\delta$ de la siguiente manera. También dividimos $r\delta s\delta$ en $rs\delta^2 + rs\delta^2 - rs\delta^2$ :

=\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2 + r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2 - rs\delta^2

Agrupamos los términos con $s$ y $r$ :

=\left(\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2\right) + \left(r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2\right) - rs\delta^2

Factorizamos $s\delta$ y $r\delta$ :

=\underbrace{\left(\alpha+ \sum_{i=1}^m a_iu_i(x) + r\delta\right)s\delta}_{As\delta} + \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)r\delta}_{Br\delta} - rs\delta^2

Sustituimos $A$ y $B$ :

=As\delta + Br\delta - rs\delta^2

Así que nuestra ecuación final es

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\sum_{i=1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2

Ahora la dividimos en las porciones pública y privada:

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\underbrace{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}_\text{pública} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2}_\text{privada}

Queremos que la porción pública y la porción privada estén separadas por $\gamma$ y $\delta$ respectivamente:

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As\delta + Br\delta - rs\delta^2

$\delta$ se cancela en algunos de los términos:

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right)

Ahora separamos esta ecuación en las porciones del verifier y del prover. Los términos recuadrados son la porción del verifier, los términos con llave inferior (underbrace) son los términos que proporciona el prover:

\underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}_{[A]_1}\underbrace{(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)}_{[B]_2}=\boxed{\alpha\beta}+\boxed{\gamma}\boxed{\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma}} + \boxed{\delta}\underbrace{\left(\frac{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Br - rs\delta\right)}_{[C]_1}

Algoritmo de Prueba Groth16

Ahora estamos listos para mostrar el algoritmo Groth16 de principio a fin. El trusted setup y los pasos de verificación permanecen sin cambios respecto al ejemplo anterior donde incorporamos $\gamma$ y $\delta$ . Solo el cálculo del prover cambia para incorporar $r$ y $s$ .

Trusted Setup

\begin{align*} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{escalares aleatorios}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs para } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs para } \mathbb{G}_2\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow \text{srs para }h(\tau)t(\tau)\\ \\ &\text{porción pública del witness}\\ [\Psi_1]_1 &= \frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1\\ [\Psi_2]_1 &= \frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{porción privada del witness}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+2}(\tau)}{\delta}G_1\\ &\vdots\\ [\Psi_{m}]_1 &= \frac{\alpha v_{m}(\tau) + \beta u_{m}(\tau) + w_{m}(\tau)}{\delta}G_1\\ \end{align*}

El trusted setup publica

([\alpha]_1,[\beta]_1[\beta]_2,[\gamma]_2,[\delta]_1[\delta]_2,\text{srs}_{G_1},\text{srs}_{G_2},\text{srs para }h(\tau)t(\tau),[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)

Pasos del Prover

El prover tiene un witness $\mathbf{a}$ y genera escalares aleatorios $r$ y $s$ .

\begin{align*} [A]_1 &= [\alpha]_1 + \sum_{i=1}^m a_iu_i(\tau)+r[\delta]_1\\ [B]_1 &= [\beta]_1 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_1\\ [B]_2 &= [\beta]_2 + \sum_{i=1}^m a_iv_i(\tau)+s[\delta]_2\\ [C]_1 &= \sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1\\ \end{align*}

El prover publica $([A]_1, [B]_2, [C]_1, [a_1,...,a_\ell])$ .

Pasos del Verifier

El verifier comprueba

\begin{align*} [X]_1&=\sum_{i=1}^\ell a_i\Psi_i\\ [A]_1\bullet[B]_2 &\stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 \end{align*}

Verificando Groth16 en Solidity

En este punto, tienes suficiente conocimiento para entender el código de verificación de la prueba en Solidity. Aquí está el código de verificación de la prueba de Tornado Cash. Se anima al lector a leer el código fuente de cerca. Si el lector se siente cómodo con la programación en ensamblador (assembly) de Solidity, entonces entender este código fuente no será difícil ya que los nombres de las variables son consistentes con los de este artículo.

También hay soporte de bibliotecas para Groth16 en Solana.

Problemas de seguridad a tener en cuenta

Groth16 es maleable

Las pruebas Groth16 son maleables. Dada una prueba válida

$([A]_1, [B]_2, [C]_1)$ , un atacante puede calcular la negación del punto de $[A]_1$ y $[B]_2$ y presentar una nueva prueba como $([A']_1, [B']_2, [C]_1)$ donde $[A']_1 = \mathsf{neg}([A]_1)$ y $[B']_2 = \mathsf{neg}([B]_2)$ .

Para ver que $[A]_1\bullet[B]_2 = [A']_1\bullet[B']_2$ , considera el siguiente código:

from py_ecc.bn128 import G1, G2, multiply, neg, eq, pairing

# chosen arbitrarily
x = 10
y = 100
A = multiply(G1, x)
B = multiply(G2, y)

A_p = neg(A)
B_p = neg(B)

assert eq(pairing(B, A), pairing(B_p, A_p))

Intuitivamente, el atacante está multiplicando $A$ y $B$ por $-1$ , y $(-1)\times(-1)$ se cancela a sí mismo en el emparejamiento.

Por lo tanto, si la fórmula de verificación acepta

[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

entonces también aceptará

\mathsf{neg}([A]_1)\bullet\mathsf{neg}([B]_2) \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2

La defensa contra este ataque se describe en la siguiente sección.

Puedes ver una prueba de concepto (proof of concept) de este ataque en este artículo.

El prover puede crear un número ilimitado de pruebas para el mismo witness

Esto no es un “problema de seguridad” per se – es necesario para lograr Zero Knowledge. Sin embargo, la aplicación necesita un mecanismo para rastrear qué hechos ya han sido probados y no puede depender de la singularidad de la prueba para lograrlo.

Aprende más con RareSkills

Nuestra capacidad para publicar material como este de forma gratuita depende del apoyo continuo de nuestros estudiantes. Considera inscribirte en nuestro Zero Knowledge Bootcamp, Web3 Bootcamps, o conseguir un trabajo en RareTalent.

Publicado originalmente el 31 de agosto de 2023

Prerrequisitos

Notación

Motivación

Previniendo la falsificación Parte 1: Introduciendo α\alphaα y β\betaβ

Una fórmula de verificación “irresoluble”

Ataque 1: Falsificando A y B y derivando C

Ataque 2: Falsificando C y derivando A y B

Cómo se usan α\alphaα y β\betaβ

Rederivando las fórmulas de prueba y verificación

Resumen del algoritmo hasta ahora

Pasos del trusted setup

Pasos del prover

Pasos del verifier

Soportando inputs públicos

Parte 2: Separando los inputs públicos de los inputs privados con γ\gammaγ o δ\deltaδ

Falsificando pruebas por el mal uso de Ψi\Psi_iΨi​ para i≤ℓi\leq\elli≤ℓ

Introduciendo γ\gammaγ y/o δ\deltaδ

Parte 3: Haciendo cumplir el verdadero zero knowledge: r y s

Algoritmo de Prueba Groth16

Trusted Setup

Pasos del Prover

Pasos del Verifier

Verificando Groth16 en Solidity

Problemas de seguridad a tener en cuenta

Groth16 es maleable

El prover puede crear un número ilimitado de pruebas para el mismo witness

Aprende más con RareSkills

Previniendo la falsificación Parte 1: Introduciendo $\alpha$ y $\beta$

Cómo se usan $\alpha$ y $\beta$

Parte 2: Separando los inputs públicos de los inputs privados con $\gamma$ o $\delta$

Falsificando pruebas por el mal uso de $\Psi_i$ para $i\leq\ell$

Introduciendo $\gamma$ y/o $\delta$