Evaluando un Programa Aritmético Cuadrático en un Trusted Setup

Last updated on Jan 5, 2026

Evaluar un Programa Aritmético Cuadrático (QAP) en una configuración confiable permite a un probador demostrar que un QAP se satisface sin revelar el testigo mientras usa una prueba de tamaño constante.

Específicamente, los polinomios del QAP se evalúan en un punto desconocido $\tau$ . La ecuación del 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)

estará equilibrada si el vector $\mathbf{a}$ satisface la ecuación, y desequilibrada con abrumadora probabilidad en caso contrario.

El esquema mostrado aquí no es una Prueba ZK segura, pero es un paso intermedio para mostrar cómo funciona Groth16.

Un ejemplo concreto

Para hacer esto un poco menos abstracto, digamos que las matrices del Sistema de Restricciones de Rango 1 (R1CS) $\mathbf{L}$ , $\mathbf{R}$ , y $\mathbf{O}$ tienen 3 filas y 4 columnas.

\mathbf{L}\mathbf{a} \circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}

Dado que tenemos 3 filas, significa que nuestros polinomios de interpolación serán de grado 2. Debido a que tenemos 4 columnas, cada matriz resultará en 4 polinomios (para un total de 12 polinomios).

Nuestro QAP será

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

Notación y preliminares

Nos referimos a los puntos generadores de la curva elíptica en los grupos $\mathbb{G}_1$ y $\mathbb{G}_2$ como $G_1$ y $G_2$ respectivamente. Un elemento en $\mathbb{G}_1$ se denota como $[X]_1$ . Un elemento en $\mathbb{G}_2$ se denota como $[X]_2$ . Donde pueda haber ambigüedad con los subíndices referidos a índices en una lista, decimos $X \in \mathbb{G}_1$ o $X \in \mathbb{G}_2$ . Un emparejamiento de curva elíptica entre dos puntos se denota como $[X]_1 \bullet [Y]_2$ .

Sea $\mathbf{L}_{(*,j)}$ la $j$ -ésima columna de $\mathbf{L}$ . En nuestro ejemplo, las filas serán $(1,2,3)$ y las columnas $(1,2,3,4)$ . Sea $\mathcal{L}(\mathbf{L}_{(*,j)})$ el polinomio obtenido al ejecutar la interpolación de Lagrange en la $j$ -ésima columna de $\mathbf{L}$ usando los valores $x$ $(1,2,3)$ y siendo los valores $y$ los valores de la $j$ -ésima columna.

Puesto que tenemos 4 columnas, obtenemos cuatro polinomios de $\mathbf{L}$

\begin{align*} u_1(x) = \mathcal{L}(\mathbf{L}_{(*,1)}) =u_{12}x^2 + u_{11}x+u_{10}\\ u_2(x) = \mathcal{L}(\mathbf{L}_{(*,2)}) =u_{22}x^2 + u_{21}x+u_{20}\\ u_3(x) = \mathcal{L}(\mathbf{L}_{(*,3)}) =u_{32}x^2 + u_{31}x+u_{30}\\ u_4(x) = \mathcal{L}(\mathbf{L}_{(*,4)}) =u_{42}x^2 + u_{41}x+u_{40}\\ \end{align*}

cuatro polinomios de $\mathbf{R}$

\begin{align*} v_1(x) = \mathcal{L}(\mathbf{R}_{(*,1)}) =v_{12}x^2 + v_{11}x+v_{10}\\ v_2(x) = \mathcal{L}(\mathbf{R}_{(*,2)}) =v_{22}x^2 + v_{21}x+v_{20}\\ v_3(x) = \mathcal{L}(\mathbf{R}_{(*,3)}) =v_{32}x^2 + v_{31}x+v_{30}\\ v_4(x) = \mathcal{L}(\mathbf{R}_{(*,4)}) =v_{42}x^2 + v_{41}x+v_{40}\\ \end{align*}

y cuatro polinomios de $\mathbf{O}$

\begin{align*} w_1(x) = \mathcal{L}(\mathbf{O}_{(*,1)}) =w_{12}x^2 + w_{11}x+w_{10}\\ w_2(x) = \mathcal{L}(\mathbf{O}_{(*,2)}) =w_{22}x^2 + w_{21}x+w_{20}\\ w_3(x) = \mathcal{L}(\mathbf{O}_{(*,3)}) =w_{32}x^2 + w_{31}x+w_{30}\\ w_4(x) = \mathcal{L}(\mathbf{O}_{(*,4)}) =w_{42}x^2 + w_{41}x+w_{40}\\ \end{align*}

Un polinomio $p_{ij}$ representa el $i$ -ésimo polinomio y el $j$ -ésimo coeficiente (potencia). Por ejemplo, $j=2$ significa el coeficiente asociado con $x^2$ .

El QAP para nuestro ejemplo es

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

donde $t(x) = (x - 1)(x - 2)(x - 3)$ y $h(x)$ es

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

Los grados de los polinomios en el QAP con respecto al tamaño del R1CS

Un par de observaciones sobre los grados de los polinomios en el caso general:

El grado de $u(x)$ y $v(x)$ podría ser tan alto como $n - 1$ porque interpolan $n$ puntos, donde $n$ es el número de filas en el R1CS.
El grado de $w(x)$ podría ser tan bajo como 0 si la suma de los polinomios $\sum_{i=0}^m a_iw_i(x)$ da como resultado el polinomio cero, es decir, si los coeficientes se cancelan aditivamente entre sí.
$t(x)$ es de grado $n$ por definición.
Multiplicar polinomios suma sus grados, y dividir polinomios resta sus grados.

Por lo tanto, h(x) será como máximo de grado $n - 2$ porque

\underbrace{n - 1}_{ \deg{u(x)}} + \underbrace{n - 1}_{\deg{v(x)}} - \underbrace{n}_{\deg{t(x)}} = n - 2

Expandiendo los términos

Si expandimos las sumas de nuestro ejemplo anterior, obtenemos lo siguiente

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= a_1(u_{12}x^2 + u_{11}x+u_{10}) + a_2(u_{22}x^2 + u_{21}x+u_{20}) + a_3(u_{32}x^2 + u_{31}x+u_{30}) + a_4(u_{42}x^2 + u_{41}x+u_{40})\\ &= (a_1u_{12}+a_2u_{22}+a_3u_{32}+a_4u_{42})x^2 + (a_1u_{11}+a_2u_{21}+a_3u_{31}+a_4u_{41})x + (a_1u_{10}+a_2u_{20}+a_3u_{30}+a_4u_{40})\\ &=u_{2a}x^2+u_{1a}x+u_{0a}\\ \sum_{i=1}^4 a_iv_i(x) &= a_1(v_{12}x^2 + v_{11}x+v_{10}) + a_2(v_{22}x^2 + v_{21}x+v_{20}) + a_3(v_{32}x^2 + v_{31}x+v_{30}) + a_4(v_{42}x^2 + v_{41}x+v_{40})\\ &= (a_1v_{12}+a_2v_{22}+a_3v_{32}+a_4v_{42})x^2 + (a_1v_{11}+a_2v_{21}+a_3v_{31}+a_4v_{41})x + (a_1v_{10}+a_2v_{20}+a_3v_{30}+a_4v_{40})\\ &=v_{2a}x^2+v_{1a}x+v_{0a}\\ \sum_{i=1}^4 a_iw_i(x) &= a_1(w_{12}x^2 + w_{11}x+w_{10}) + a_2(w_{22}x^2 + w_{21}x+w_{20}) + a_3(w_{32}x^2 + w_{31}x+w_{30}) + a_4(w_{42}x^2 + w_{41}x+w_{40})\\ &= (a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2 + (a_1w_{11}+a_2w_{21}+a_3w_{31}+a_4w_{41})x + (a_1w_{10}+a_2w_{20}+a_3w_{30}+a_4w_{40})\\ &=w_{2a}x^2+w_{1a}x+w_{0a}\\ \end{align*}

En cada uno de los casos, dado que estamos sumando 4 polinomios de grado 2, obtenemos un polinomio de grado 2.

En general, la expresión $\sum_{i=1}^m a_ip_i(x)$ produce un polinomio con a lo sumo la misma potencia que $p(x)$ (podría ser menor, si por ejemplo $(a_1w_{12}+a_2w_{22}+a_3w_{32}+a_4w_{42})x^2$ sumara 0). Por conveniencia, hemos introducido los coeficientes $p_{ia}$ donde $i$ es la potencia del coeficiente y $_a$ significa que combinamos los polinomios con el testigo $\mathbf{a}$ .

Aquí están los polinomios después de reducirlos de esta manera:

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= u_{2a}x^2+u_{1a}x+u_{0a}\\ \sum_{i=1}^4 a_iv_i(x) &= v_{2a}x^2+v_{1a}x+v_{0a}\\ \sum_{i=1}^4 a_iw_i(x) &= w_{2a}x^2+w_{1a}x+w_{0a}\\ \end{align*}

Combinando una configuración confiable con un QAP

Ahora podemos aplicar la cadena de referencia estructurada de la configuración confiable para evaluar los polinomios.

Es decir, dada una cadena de referencia estructurada

[\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], \space\Omega_i \in \mathbb{G}_1, \space\Theta_i \in \mathbb{G}_2

la cual fue calculada en la configuración confiable como

\begin{align*} [\Omega_2, \Omega_1, G_1] &= [\tau^2G_1, \tau G_1, G_1], \space\Omega_i \in \mathbb{G}_1\\ [\Theta_2, \Theta_1, G_2] &= [\tau^2G_2, \tau G_2, G_2], \space\Theta_i \in \mathbb{G}_2 \end{align*}

Podemos calcular

\begin{align*} [A]_1 &=\sum_{i=1}^4 a_iu_i(\tau) = \langle[u_{2a}, u_{1a}, u_{0a}],[\Omega_2, \Omega_1, G_1]\rangle\\ [B]_2 &=\sum_{i=1}^4 a_iv_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Theta_2, \Theta_1, G_2]\rangle\\ [C]_1 &=\sum_{i=1}^4 a_iw_i(\tau) = \langle[v_{2a}, v_{1a}, v_{0a}],[\Omega_2, \Omega_1, G_1]\rangle \\ \end{align*}

Aquí, $u_i(\tau), v_i(\tau), w_i(\tau)$ significan que los polinomios fueron evaluados usando la cadena de referencia estructurada generada a partir de $\tau$ en la configuración confiable, no significa “sustituir $\tau$ y evaluar los polinomios”. Dado que $\tau$ fue destruido después de la configuración confiable, el valor $\tau$ es desconocido.

Hemos calculado la mayor parte del QAP utilizando el srs, pero aún no hemos calculado $h(x)t(x)$ :

\underbrace{\sum_{i=1}^m a_iu_i(x)}_{[A]_1}\underbrace{\sum_{i=1}^m a_iv_i(x)}_{[B]_2} = \underbrace{\sum_{i=1}^m a_iw_i(x)}_{[C]_1} + \underbrace{h(x)t(x)}_{??}

Calculando $h(x)t(x)$

Recuerde que el grado de $t(x)$ es 3 (generalmente $n$ ) y el grado de $h(x)$ es 1 (generalmente $n - 2$ ). Si los multiplicamos, podríamos obtener hasta un polinomio de grado 3, lo cual es más de lo que proporciona la ceremonia de potencias de tau. En su lugar, la ceremonia de potencias de tau debe ajustarse para proporcionar una cadena de referencia estructurada para $h(x)t(x)$ .

La persona que realiza la configuración confiable conoce $t(x)$ , que es simplemente $(x - 1)(x - 2)...(x - n)$ . Sin embargo, $h(x)$ es un polinomio calculado por el probador y modificado en base a los valores de $\mathbf{a}$ , por lo que no puede conocerse durante la configuración confiable.

Tenga en cuenta que no podemos evaluar $h(\tau)$ y $t(\tau)$ por separado (usando una cadena de referencia estructurada) y luego emparejarlos. Eso no daría como resultado un elemento $\mathbb{G}_1$ que es lo que necesitamos.

SRS para productos de polinomios

Observe que todos los siguientes cálculos dan como resultado el mismo valor:

El polinomio $h(x)t(x)$ evaluado en $u$ , o $(h(x)t(x))(u)$
$h(u)$ multiplicado por $t(u)$ , o $h(u)t(u)$ ( $h$ evaluado en $u$ y $t$ evaluado en $u$ )
$h(x)$ multiplicado por la evaluación $t(u)$ , luego evaluado en $u$ , es decir $(h(x)t(u))(u)$

Usaremos el tercer método para calcular $h(\tau)t(\tau)$ . Suponga, sin pérdida de generalidad, que $h(x)$ es $3x^2 + 6x + 2$ y $t(u) = 4$ . El cálculo sería

h(x)t(u) = (3x^2 + 6x + 2) \cdot 4 = 12x^2 + 24x + 8

Si sustituimos $u$ en $12x^2 + 24x + 8$ , eso sería $h(u)t(u)$ .

Sin embargo, evaluar este polinomio en $\tau$ requeriría que el probador conociera $\tau$ . La idea clave aquí es que el cálculo anterior puede estructurarse como:

h(u)t(u) = \langle[3, 6, 2], [4u^2, 4u, 4]\rangle=12u^2+24u+8

Si la configuración confiable proporciona $[4u^2, 4u, 4]$ , y el probador proporciona $[3, 6, 2]$ , entonces el probador puede calcular $h(u)t(u)$ sin conocer $u$ , porque todo lo que involucra a $u$ está en el vector derecho del producto interno.

Cadena de referencia estructurada para $h(\tau)t(\tau)$

Para crear una cadena de referencia estructurada para $h(\tau)t(\tau)$ , creamos $n - 1$ evaluaciones de $t(\tau)$ multiplicadas por potencias sucesivas de $\tau$ .

[\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] = [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, ..., \tau t(\tau)G_1, t(\tau)G_1]

(De forma un poco confusa, un polinomio de grado $k$ tiene $k+1$ términos, por lo tanto generamos $k - 1$ evaluaciones para un polinomio de grado $k - 2$ . Tenga en cuenta que Upsilon comienza en ${n-1}$ y termina en 0).

Aquí, $n$ es el número de filas en el R1CS, y establecimos que $h$ no puede tener un grado mayor a $n - 2$ .

Para usar la cadena de referencia estructurada para calcular $h(\tau)t(\tau)$ , el probador hace lo siguiente:

h(\tau)t(\tau) = \langle[h_{n-2}, h_{n-3}, ..., h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] \rangle

Evaluando un QAP en una configuración confiable

Ahora unimos todo. Supongamos que tenemos un R1CS con matrices de $n$ filas y $m$ columnas. A partir de esto, podemos aplicar la interpolación de Lagrange para convertirlo en un 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)

Los términos de la suma producirán cada uno un polinomio de grado $n - 1$ (un polinomio de Lagrange tiene un grado menos que el número de puntos que interpola), y el polinomio $h(x)$ tendrá a lo sumo grado $n - 2$ , y $t(x)$ tendrá grado $n$ .

Una configuración confiable genera un elemento de campo aleatorio $\tau$ y calcula:

\begin{align*} [\Omega_{n-1},\Omega_{n-2},..., \Omega_1, G_1] &= [\tau^{n-1}G_1, \tau^{n-2}G_1,\dots, \tau G_1, G_1]\\ [\Theta_{n-1}, \Theta_{n-2}, ..., \Theta_1, G_2] &= [\tau^{n-1}G_2, \tau^{n-2}G_2,\dots, \tau G_2, G_2]\\ [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0] &= [\tau^{n-2}t(\tau)G_1, \tau^{n-3}t(\tau)G_1, ..., \tau t(\tau)G_1, t(\tau)G_1] \end{align*}

Note que las cadenas de referencia estructuradas necesitan tener suficientes términos para acomodar los polinomios en el QAP.

Luego, la configuración confiable destruye $\tau$ y publica las cadenas de referencia estructuradas:

([\Omega_2, \Omega_1, G_1], [\Theta_2, \Theta_1, G_2], [\Upsilon_{n-2}, \Upsilon_{n-3}, ..., \Upsilon_1, \Upsilon_0])

El probador evalúa los componentes del QAP de la siguiente manera:

\underbrace{\sum_{i=1}^m a_iu_i(x)}_{A}\underbrace{\sum_{i=1}^m a_iv_i(x)}_B = \underbrace{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}_{C}

\begin{align*} [A]_1 &=\sum_{i=1}^m a_iu_i(\tau) = \langle[u_{{n-1}a}, u_{{n-2}a}, \dots, u_{1a}, u_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle\\ [B]_2 &=\sum_{i=1}^m a_iv_i(\tau) = \langle[v_{{n-1}a}, v_{{n-2}a}, \dots, v_{1a}, v_{0a}],[\Theta_{n-1}, \Theta_{n-2}, \dots, \Theta_1, G_2]\rangle\\ [C]_1 &=\sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) = \langle[w_{{n-1}a}, w_{{n-2}a}, \dots, w_{1a}, w_{0a}],[\Omega_{n-1}, \Omega_{n-2}, \dots, \Omega_1, G_1]\rangle \\ &+\langle[h_{n-2}, h_{n-3}, \dots, h_1, h_0], [\Upsilon_{n-2}, \Upsilon_{n-3}, \dots, \Upsilon_1, \Upsilon_0] \rangle\\ \end{align*}

El probador publica $([A]_1, [B]_2, [C]_1)$ y el verificador puede comprobar que

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

Si el testigo $\mathbf{a}$ satisface el QAP, entonces la ecuación anterior estará equilibrada. Pero el hecho de que la ecuación esté equilibrada no garantiza que el probador conozca un $\mathbf{a}$ que la satisfaga porque el probador puede publicar puntos arbitrarios de la curva elíptica y el verificador no sabe si realmente se derivan del QAP.

La prueba es muy pequeña

Observe que la prueba solo consta de tres puntos de la curva elíptica. Si un elemento de $\mathbb{G}_1$ tiene un tamaño de 64 bytes, y un elemento de $\mathbb{G}_2$ tiene un tamaño de 128 bytes, entonces la prueba es de solo 256 bytes. ¡Esto es cierto independientemente del tamaño del R1CS!

Cuanto mayor sea el R1CS, más trabajo tiene el probador, pero el trabajo del verificador permanece constante.

La solución a este problema se describe en el siguiente capítulo sobre el protocolo Groth16.

La prueba sigue siendo de tamaño constante en Groth16, como se puede ver en el código fuente de Tornado Cash en el struct llamado Proof.

Publicado originalmente el 28 de agosto de 2023