Construyendo una prueba de conocimiento cero a partir de un R1CS

Last updated on Oct 31, 2024

Dado un circuito aritmético codificado como un Rank 1 Constraint System, es posible crear una prueba ZK de que se tiene un testigo (witness), aunque no una que sea sucinta. Este artículo describe cómo lograrlo.

Una prueba de conocimiento cero para un R1CS se logra convirtiendo el vector testigo en puntos de curva elíptica sobre campos finitos y reemplazando el producto de Hadamard con un emparejamiento bilineal para cada fila.

Dado un Rank 1 Constraint System donde cada matriz tiene $n$ filas y $m$ columnas, lo escribimos como

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

Donde $\mathbf{L}$ , $\mathbf{R}$ , $\mathbf{O}$ son matrices con $n$ filas y $m$ columnas, y $\mathbf{a}$ es el vector testigo (que contiene una asignación que satisface cada una de las señales en el circuito aritmético). El vector $\mathbf{a}$ tiene 1 columna y $m$ filas, y $\circ$ es la multiplicación elemento por elemento (producto de Hadamard).

En forma expandida, se ve así:

\left[ \begin{array}{ccc} l_{1,1} & \cdots & l_{1,m} \\ \vdots & \ddots & \vdots \\ l_{n,1} & \cdots & l_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] \circ \left[ \begin{array}{ccc} r_{1,1} & \cdots & r_{1,m} \\ \vdots & \ddots & \vdots \\ r_{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right] = \left[ \begin{array}{ccc} o_{1,1} & \cdots & o_{1,m} \\ \vdots & \ddots & \vdots \\ o_{n,1} & \cdots & o_{n,m} \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_m \end{array} \right]

= \left[ \begin{array}{ccc} a_1 l_{1,1} + \cdots + a_m l_{1,m} \\ \vdots \\ a_1 l_{n,1} + \cdots + a_m l_{n,m} \end{array} \right] \circ \left[ \begin{array}{ccc} a_1 r_{1,1} + \cdots + a_m r_{1,m} \\ \vdots \\ a_1 r_{n,1} + \cdots + a_m r_{n,m} \end{array} \right] = \left[ \begin{array}{ccc} a_1 o_{1,1} + \cdots + a_m o_{1,m} \\ \vdots \\ a_1 o_{n,1} + \cdots + a_m o_{n,m} \end{array} \right]

= \left[ \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \end{array} \right] \circ \left[ \begin{array}{ccc} \sum_{i=1}^m a_i r_{1,i} \\ \sum_{i=1}^m a_i r_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i r_{n,i} \end{array} \right] = \left[ \begin{array}{ccc} \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i o_{n,i} \end{array} \right]

= \begin{array}{ccc} \sum_{i=1}^m a_i l_{1,i} \sum_{i=1}^m a_i r_{1,i} = \sum_{i=1}^m a_i o_{1,i} \\ \sum_{i=1}^m a_i l_{2,i} \sum_{i=1}^m a_i r_{2,i} = \sum_{i=1}^m a_i o_{2,i} \\ \vdots \\ \sum_{i=1}^m a_i l_{n,i} \sum_{i=1}^m a_i r_{n,i} = \sum_{i=1}^m a_i o_{n,i} \end{array}

En esta configuración, podemos demostrar a un verificador que tenemos un vector testigo $\mathbf{a}$ que satisface el R1CS simplemente dándole el vector $\mathbf{a}$ , ¡pero con la obvia desventaja de que esto no es una prueba de conocimiento cero!

Algoritmo de prueba de conocimiento cero para un R1CS.

Si “encriptamos” el vector testigo multiplicando cada entrada por $G_1$ o $G_2$ , ¡las matemáticas seguirán funcionando correctamente!

Para entender esto, considera que si llevamos a cabo la multiplicación de matrices

\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4 \\ 5 \end{bmatrix} = \begin{bmatrix} 14 \\ 32 \end{bmatrix}

y también

\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \begin{bmatrix} 4G_1 \\ 5G_1 \end{bmatrix} = \begin{bmatrix} 14G_1 \\ 32G_1 \end{bmatrix}

Los logaritmos discretos de los dos puntos de la curva elíptica en la segunda multiplicación de matrices tienen el mismo valor que los elementos de la primera multiplicación de matrices.

En otras palabras, cada vez que multiplicamos el vector columna por una fila en la matriz cuadrada, llevamos a cabo dos multiplicaciones de puntos de curva elíptica y una suma de curva elíptica.

Notación para curvas elípticas

Decimos que $[aG_1]_1$ es un punto de curva elíptica en $\mathbb{G}_1$ creado al multiplicar el elemento del campo $a$ por $G_1$ . Decimos que $[aG_2]_2$ es un punto de curva elíptica en $\mathbb{G}_2$ generado al multiplicar $a$ con el generador $G_2$ . Debido al problema del logaritmo discreto, no podemos extraer $a$ dado $[aG_1]_1$ o $[aG_2]_2$ . Dado un punto $A \in \mathbb{G}_1$ y $B \in \mathbb{G}_2$ , decimos que el emparejamiento (pairing) de los dos puntos es $A\bullet B$ .

Pasos del probador

Encriptemos nuestro vector $\mathbf{a}$ multiplicando cada entrada con el punto generador $G_1$ para producir el punto de curva elíptica $[a_iG_1]_1$ .

Para la matriz $\mathbf{L}$ , estamos haciendo lo siguiente:

\left[ \begin{array}{ccc} l_{1,1} & \cdots & l_{1,m} \\ \vdots & \ddots & \vdots \\ l_{n,1} & \cdots & l_{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_1]_1 \\ \vdots \\ [a_m G_1]_1 \end{array} \right] = \left[ \begin{array}{ccc} l_{1,1}[a_1 G_1]_1 & + \cdots + & l_{1,m}[a_m G_1]_1 \\ \vdots & \ddots & \vdots \\ l_{n,1}[a_1 G_1]_1 & + \cdots + & l_{n,m}[a_m G_1]_1 \end{array} \right] = \left[ \begin{array}{c} \sum_{i=1}^m l_{1,i}[a_i G_1]_1 \\ \sum_{i=1}^m l_{2,i}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m l_{n,i}[a_i G_1]_1 \end{array} \right]

Anticipando que el producto de Hadamard se convierta en una lista de emparejamientos de curvas elípticas, podemos usar puntos $G_2$ para encriptar también el vector $\mathbf{a}$ de modo que el verificador pueda hacer el emparejamiento.

\left[ \begin{array}{ccc} r_{1,1} & \cdots & r_{1,m} \\ \vdots & \ddots & \vdots \\ r_{n,1} & \cdots & r_{n,m} \end{array} \right] \left[ \begin{array}{c} [a_1 G_2]_2 \\ \vdots \\ [a_m G_2]_2 \end{array} \right] = \left[ \begin{array}{ccc} r_{1,1}[a_1 G_2]_2 & + \cdots + & r_{1,m}[a_m G_2]_2 \\ \vdots & \ddots & \vdots \\ r_{n,1}[a_1 G_2]_2 & + \cdots + & r_{n,m}[a_m G_2]_2 \end{array} \right] = \left[ \begin{array}{c} \sum_{i=1}^m r_{1,i}[a_i G_2]_2 \\ \sum_{i=1}^m r_{2,i}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m r_{n,i}[a_i G_2]_2 \end{array} \right]

Después de esta operación, tenemos una sola columna de puntos de curva elíptica en $G_1$ originada por la multiplicación $\mathbf{L}\mathbf{a}$ y una sola columna de puntos $G_2$ de $\mathbf{R}\mathbf{a}$ .

El siguiente paso ingenuo sería encriptar el vector $\mathbf{a}$ con puntos $G_{12}$ para que el verificador pueda emparejar el resultado de $\mathbf{L}\mathbf{a}$ con $\mathbf{R}\mathbf{a}$ para ver si es igual a $\mathbf{O}\mathbf{a}$ , pero los puntos $G_{12}$ son masivos, por lo que preferiríamos que el verificador empareje los puntos de curva elíptica de $\mathbf{O}\mathbf{a}$ en $G_1$ y luego empareje cada entrada con un punto $G_2$ . Emparejar con un punto $G_2$ es, en cierto sentido, “multiplicar por uno” pero convirtiendo el punto $G_1$ en un punto $G_{12}$ .

El probador luego entrega el vector $G_1$ y el vector $G_2$ al verificador.

Paso de verificación

Por lo tanto, el paso de verificación se convierte en

\left[ \begin{array}{c} \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \\ \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m l_{i,1}[a_i G_1]_1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \end{array} \right] \stackrel{?}{=} \left[ \begin{array}{c} \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \\ \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \\ \vdots \\ \sum_{i=1}^m o_{i,1}[a_i G_1]_1 \end{array} \right] \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \left[ \begin{array}{c} G_2 \\ G_2 \\ \vdots \\ G_2 \end{array} \right]

= \begin{array}{c} \sum_{i=1}^m l_{i,1}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,1}[a_i G_2]_2 \\ \sum_{i=1}^m l_{i,2}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,2}[a_i G_2]_2 \\ \vdots \\ \sum_{i=1}^m l_{i,n}[a_i G_1]_1\bullet \sum_{i=1}^m r_{i,n}[a_i G_2]_2 \end{array} \stackrel{?}{=} \begin{array}{c} \sum_{i=1}^m o_{i,1}[a_i G_1]_1\bullet G_2 \\ \sum_{i=1}^m o_{i,2}[a_i G_1]_1\bullet G_2 \\ \vdots \\ \sum_{i=1}^m o_{i,n}[a_i G_1]_1 \bullet G_2 \end{array}

Los vectores anteriores de elementos $G_{12}$ serán iguales elemento por elemento si y solo si el probador ha proporcionado un testigo válido.

Bueno, casi. Llegaremos a eso en una sección posterior.

Primero debemos mencionar un detalle de implementación importante

Entradas públicas

Si nuestra afirmación de conocimiento es “Conozco $x$ tal que $x³ + 5x + 5 = y$ donde $y = 155$ ”, entonces nuestro vector testigo probablemente se verá de la siguiente manera:

[1, y, x, v]

donde $v = x^2$ . En este caso, necesitamos que $[1, y]$ sean públicos. Para lograrlo, simplemente no encriptamos los dos primeros elementos del testigo. El verificador comprobará las salidas públicas, luego encriptará las entradas públicas multiplicándolas con un punto $G_1$ o $G_2$ para que la fórmula de verificación no cambie.

Lidiando con un probador malicioso.

Debido a que los vectores están encriptados, el verificador no puede saber de inmediato si el vector de puntos $\mathbb{G}₁$ encripta los mismos valores que el vector de puntos $\mathbb{G}₂$ .

Es decir, el probador está suministrando $\mathbf{a}G_1$ y $\mathbf{a}G_2$ . Dado que el verificador no conoce los logaritmos discretos del vector de puntos, ¿cómo sabe el verificador que el vector de puntos $\mathbb{G}₁$ tiene los mismos logaritmos discretos que el vector de puntos $\mathbb{G}₂$ ?

El verificador puede comprobar la igualdad de los logaritmos discretos (sin conocerlos) emparejando ambos vectores de puntos con un vector del generador opuesto y comprobando que los puntos $\mathbb{G}_{12}$ resultantes sean iguales. Específicamente,

\begin{bmatrix} a_1G_1 \\ a_2G_1 \\ \vdots \\ a_mG_1 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_2 \\ G_2 \\ \vdots \\ G_2 \end{bmatrix} \stackrel{?}{=} \begin{bmatrix} a_1G_2 \\ a_2G_2 \\ \vdots \\ a_mG_2 \end{bmatrix} \begin{matrix} \bullet \\ \bullet \\ \vdots \\ \bullet \end{matrix} \begin{bmatrix} G_1 \\ G_1 \\ \vdots \\ G_1 \end{bmatrix}

Este algoritmo es mayormente académico

Este algoritmo es muy ineficiente para el verificador. Si las matrices en el R1CS son grandes (y para algoritmos interesantes, lo serán), entonces el verificador tiene que hacer muchos emparejamientos y sumas de curvas elípticas. La suma de curvas elípticas es bastante rápida, pero los emparejamientos de curvas elípticas son lentos (y cuestan mucho gas en Ethereum).

Sin embargo, es bueno ver que en esta etapa, las pruebas de conocimiento cero son posibles, y si tienes una buena comprensión de las operaciones de curvas elípticas (y no has olvidado tu aritmética de matrices), no son difíciles de entender.

Haciendo que esta técnica sea verdaderamente de conocimiento cero

Tal como está ahora, nuestro vector testigo no puede ser desencriptado, sin embargo, puede ser adivinado. Si un atacante (alguien que intenta descubrir el testigo sin encriptar) usa alguna información auxiliar para hacer una suposición fundamentada sobre el testigo, puede comprobar su trabajo multiplicando su vector testigo adivinado por los generadores de puntos de la curva elíptica y viendo si el resultado es el mismo que los vectores testigo del probador.

Aprenderemos cómo defendernos de la adivinación de testigos en nuestra cobertura de Groth16.

Además, ten en cuenta que nadie usa el algoritmo descrito en el mundo real, ya que es demasiado ineficiente. Sin embargo, si lo implementas, te ayudará a practicar la implementación de aritmética de curvas elípticas significativa y a construir una prueba de conocimiento cero funcional de extremo a extremo (casi).

Puedes ver un ejemplo de implementación del algoritmo descrito aquí por Obront en este repositorio.

Aprende más con RareSkills

Este material es de nuestro Zero Knowledge Course.

Publicado originalmente el 26 de agosto de 2023