Conversión de circuitos algebraicos a R1CS (Sistema de restricciones de rango uno)

Last updated on Jan 22, 2026

Este artículo explica cómo convertir un conjunto de restricciones aritméticas en un Rank One Constraint System (R1CS).

El enfoque de este recurso es la implementación: cubrimos muchos más casos extremos de esta transformación que otros materiales, discutimos optimizaciones y explicamos cómo la biblioteca Circom lo lleva a cabo.

Requisitos previos

Asumimos que el lector entiende cómo usar circuitos aritméticos (circuitos zk) para representar la validez de un cálculo.
El lector está familiarizado con la aritmética modular. Todas las operaciones aquí ocurren en un campo finito, por lo que $-5$ realmente significa el inverso aditivo de $5$ módulo $p$ y $2/3$ significa el inverso multiplicativo de $3$ módulo $p$ multiplicado por $2$ .

Resumen de Rank 1 Constraint System

Un Rank 1 Constraint System (R1CS) es un circuito aritmético con el requisito de que cada restricción de igualdad tenga una multiplicación (y ninguna restricción en el número de sumas).

Esto hace que la representación del circuito aritmético sea compatible con el uso de emparejamientos bilineales (bilinear pairings). La salida de un emparejamiento $G_1 \bullet G_2 \rightarrow G_T$ no puede ser emparejada de nuevo, ya que un elemento en $G_T$ no puede ser utilizado como parte de la entrada de otro emparejamiento. Por lo tanto, solo permitimos una multiplicación por restricción.

El vector witness

En un circuito aritmético, el witness es una asignación a todas las señales que satisface las restricciones de la ecuación.

En un Rank 1 Constraint System, el vector witness es un vector de $1 \times n$ que contiene el valor de todas las variables de entrada, la variable de salida y los valores intermedios. Demuestra que has ejecutado el circuito de principio a fin, conociendo tanto la entrada, la salida, como todos los valores intermedios.

Por convención, el primer elemento siempre es 1 para facilitar algunos cálculos, lo cual demostraremos más adelante.

Por ejemplo, si tenemos la restricción

z = x^2y

para la cual afirmamos conocer la solución, entonces eso debe significar que conocemos $x$ , $y$ y $z$ . Debido a que los Rank One Constraint Systems requieren exactamente una multiplicación por restricción, las restricciones del polinomio anterior deben escribirse como

\begin{align*} v₁ = xx \\ z = v₁y \end{align*}

Un witness significa que no solo conocemos $x$ , $y$ y $z$ , sino que debemos conocer cada variable intermedia en esta forma expandida. Específicamente, nuestro witness es un vector:

[1, z, x, y, v₁]

donde cada término tiene un valor que satisface las restricciones anteriores.

Por ejemplo,

[1, 18, 3, 2, 9]

es un witness válido porque cuando sustituimos los valores,

[\text{constante} = 1, z = 18, x = 3, y = 2, v₁ = 9]

satisface las restricciones

\begin{align*} v_1 = x*x \rightarrow 9 = 3\cdot3\\ z = v_1*y \rightarrow 18 = 9\cdot2 \end{align*}

El término 1 adicional no se usa en este ejemplo y es una conveniencia que explicaremos más adelante.

Ejemplo 1: Transformando $z = x \cdot y$ en un Rank 1 Constraint System

Para nuestro ejemplo, diremos que estamos probando que $41 \times 103 = 4223$ .

Por lo tanto, nuestro vector witness es $[1, 4223, 41, 103]$ como una asignación a $[1, z, x, y]$ .

Antes de que podamos crear un R1CS, nuestras restricciones deben tener la forma

result = left_hand_side × right_hand_side

Afortunadamente para nosotros, ya lo está

\underbrace{z}_\text{resultado} = \underbrace{x}_\text{lado izquierdo} \times \underbrace{y}_\text{lado derecho}

Este es obviamente un ejemplo trivial, pero los ejemplos triviales suelen ser un excelente punto de partida.

Para crear un R1CS válido, necesitas una lista de fórmulas que contengan exactamente una multiplicación.

Más adelante discutiremos cómo manejar casos que no tienen exactamente una multiplicación, como $z = x³$ o $z = x³ + y$ .

Nuestro objetivo es crear un sistema de ecuaciones de la forma:

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

Donde $O$ , $L$ y $R$ son matrices de tamaño $n$ x $m$ ( $n$ filas y $m$ columnas).

La matriz $\mathbf{L}$ codifica la variable en el lado izquierdo de la multiplicación y $\mathbf{R}$ codifica las variables en el lado derecho de la multiplicación. $\mathbf{O}$ codifica las variables de resultado. El vector $\mathbf{a}$ es el vector witness.

Específicamente, $\mathbf{L}$ , $\mathbf{R}$ y $\mathbf{O}$ son matrices con el mismo número de columnas que el vector witness $\mathbf{a}$ , y cada columna representa la misma variable que utiliza el índice.

Así que para nuestro ejemplo, el witness tiene 4 elementos $(1, z, x, y)$ , por lo que cada una de nuestras matrices tendrá 4 columnas, entonces $m = 4$ .

El número de filas corresponderá al número de restricciones en el circuito. En nuestro caso, solo tenemos una restricción: $z = x * y$ , por lo que solo tendremos una fila, entonces $n = 1$ .

Saltemos a la respuesta y expliquemos cómo la obtuvimos.

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

\underbrace{\begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix}}_{\mathbf{O}}\mathbf{a} = \underbrace{\begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix}}_{\mathbf{L}}\mathbf{a}\circ \underbrace{\begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix}}_{\mathbf{R}}\mathbf{a}

\begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}= \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}\circ \begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}

En este ejemplo, cada elemento en la matriz sirve como una variable indicadora de si la variable a la que corresponde la columna está presente o no. (Técnicamente, es el coeficiente de la variable, pero llegaremos a eso más adelante).

Para los términos del lado izquierdo, $x$ es la única variable presente en el lado izquierdo de la multiplicación, así que si las columnas representan $[1, z, x, y]$ , entonces…

$\mathbf{L}$ es $[0, 0, 1, 0]$ , porque $x$ está presente y ninguna de las otras variables lo está.

$\mathbf{R}$ es $[0, 0, 0, 1]$ porque la única variable en el lado derecho de la multiplicación es $y$ , y

$\mathbf{O}$ es $[0, 1, 0, 0]$ porque solo tenemos la variable $z$ en la “salida” de la multiplicación.

No tenemos ninguna constante en ninguna parte, por lo que la columna del 1 es cero en todas partes (discutiremos cuándo no es cero más adelante).

Esta ecuación es correcta, lo cual podemos verificar en Python

import numpy as np

# define the matrices
O = np.matrix([[0,1,0,0]])
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])

# witness vector
a = np.array([1, 4223, 41, 103])

# Multiplication `*` is element-wise, not matrix multiplication.
# Result contains a bool indicating an element-wise indicator that the equality is true for that element.
result = np.matmul(O, a) == np.matmul(L, a) * np.matmul(R, a) 

# check that every element-wise equality is true
assert result.all(), "result contains an inequality"

Puede que te estés preguntando cuál es el punto de esto, ¿no estamos simplemente diciendo que $41 \times 103 = 4223$ de una manera mucho menos compacta?

Estarías en lo correcto.

Un R1CS puede ser bastante verboso, pero se mapean perfectamente a Quadratic Arithmetic Programs (QAPs), los cuales pueden hacerse sucintos. Pero no nos ocuparemos de los QAPs aquí.

Pero este es un punto importante del R1CS. Un R1CS comunica exactamente la misma información que las restricciones aritméticas originales, pero con solo una multiplicación por restricción de igualdad. En este ejemplo, solo tenemos una restricción, pero agregaremos más en el siguiente ejemplo.

Ejemplo 2: Transformando r = x * y * z * u

En este ejemplo ligeramente más complicado, ahora tenemos que lidiar con variables intermedias. Cada fila de nuestro cálculo solo puede tener una multiplicación, por lo que debemos dividir nuestra ecuación de la siguiente manera:

\begin{align*} v_1 &= xy \\ v_2 &= zu \\ r &= v_1v_2 \end{align*}

No hay ninguna regla que diga que teníamos que dividirlo así, lo siguiente también es válido:

\begin{align*} v_1 &= xy \\ v_2 &= v_1z \\ r &= v_2u \end{align*}

Usaremos la primera transformación para este ejemplo.

Tamaño de $\mathbf{L}$ , $\mathbf{R}$ y $\mathbf{O}$

Debido a que estamos lidiando con 7 variables $(r, x, y, z, u, v_1, v_2)$ , nuestro vector witness tendrá ocho elementos (siendo el primero la constante 1) y nuestras matrices tendrán ocho columnas.

Debido a que tenemos tres restricciones, las matrices tendrán tres filas.

Términos del lado izquierdo y términos del lado derecho

Este ejemplo reforzará fuertemente la idea de un “término del lado izquierdo” y un “término del lado derecho”. Específicamente, $x$ , $z$ y $v_1$ son términos del lado izquierdo, e $y$ , $u$ y $v_2$ son términos del lado derecho.

\underbrace{ \begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} }_\text{ Términos de Salida } \begin{matrix} =\\ =\\ = \end{matrix} \underbrace{ \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} }_\text{ Términos del Lado Izquierdo } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underbrace{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix} }_\text{ Términos del Lado Derecho }

Construyendo la matriz $\mathbf{L}$ a partir de los términos del lado izquierdo

Construyamos la matriz A. Sabemos que tendrá tres filas (ya que hay tres restricciones) y ocho columnas (ya que hay ocho variables).

\begin{bmatrix} & l_{1,2} & l_{1,3} & l_{1,4} & l_{1,5} & l_{1,6} & l_{1,7} & l_{1,8} \\ & l_{2,2} & l_{2,3} & l_{2,4} & l_{2,5} & l_{2,6} & l_{2,7} & l_{2,8} \\ & l_{3,2} & l_{3,3} & l_{3,4} & l_{3,5} & l_{3,6} & l_{3,7} & l_{3,8} \\ \end{bmatrix}

Nuestro vector witness se multiplicará por esto, así que definamos nuestro vector witness para que tenga el siguiente diseño:

\begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2 \end{bmatrix}

Esto nos informa qué representan las columnas de $\mathbf{L}$ :

\mathbf{L} = \begin{bmatrix} l_{1, 1} & l_{1, r} & l_{1, x} & l_{1, y} & l_{1, z} & l_{1, u} & l_{1, v_1} & l_{1, v_2} \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_1} & l_{2, v_2} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

Primera fila de $\mathbf{L}$

En la primera fila, para la primera variable izquierda, tenemos $v₁ = xy$ :

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \\ z \\ v_1 \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

Esto significa que, con respecto al lado izquierdo, la variable $x$ está presente y ninguna otra variable está presente. Por lo tanto, transformamos la primera fila de la siguiente manera:

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_1} & l_{2, v_2} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

Recuerda que las columnas de $\mathbf{L}$ están etiquetadas de la siguiente manera:

\begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2\\ \end{bmatrix}

y vemos que el $1$ está en la columna de $x$ .

Segunda fila de $\mathbf{L}$

Continuando hacia abajo, vemos que solo $z$ está presente para el lado izquierdo de nuestro sistema de ecuaciones.

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \\ \color{green}{z} \\ v_1 \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

Por lo tanto, establecemos todo en esa fila como cero, excepto la columna que representa $z$ .

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

Tercera fila de $\mathbf{L}$

Finalmente, tenemos a $v₁$ como la única variable presente en los operadores del lado izquierdo en la tercera fila

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \\ z \\ \color{violet}{v_1} \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

Esto completa la matriz $\mathbf{L}$

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \\ \end{bmatrix}

La siguiente imagen debería hacer más claro el mapeo:

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \\ \color{green}{z} \\ \color{violet}{v_1} \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix} \space\space\space\space \begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \\ \end{bmatrix} \end{array} \end{array}

Transformación alternativa de $\mathbf{L}$

Podríamos lograr este mismo ejercicio expandiendo los valores del lado izquierdo de

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

como

\begin{align*} v_1 &= (0\cdot 1 + 0\cdot r + \boxed{1\cdot x} + 0\cdot y + 0\cdot z + 0\cdot u + 0\cdot v_1 + 0\cdot v_2) \times y\\ v_2 &= (0\cdot 1 + 0\cdot r + 0\cdot x + 0\cdot y + \boxed{1\cdot z} + 0\cdot u + 0\cdot v_1 + 0\cdot v_2) \times u\\ r &= (0\cdot 1 + 0\cdot r + 0\cdot x + 0\cdot y + 0\cdot z + 0\cdot u + \boxed{1\cdot v_1} + 0\cdot v_2) \times v_2 \\ \end{align*}

Podemos hacer eso porque agregar términos cero no cambia los valores. Solo tenemos que ser cuidadosos de expandir las variables cero para que tengan las mismas “columnas” que como hemos definido el vector witness.

Y luego, si extraemos los coeficientes (mostrados en recuadros) de la expansión anterior,

\begin{align*} v_1 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{1}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times y\\ v_2 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{1}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times u\\ r &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{1}\cdot v_1 + \boxed{0}\cdot v_2) \times v_2 \\ \end{align*}

Obtenemos la misma matriz para $\mathbf{L}$ que generamos hace un momento.

\mathbf{L}=\begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

Construyendo la matriz $\mathbf{R}$ a partir de los términos del lado derecho

R = \begin{bmatrix} r_{1,1} & r_{1,r} & r_{1,x} & r_{1,y} & r_{1,z} & r_{1,u} & r_{1,v_1} & r_{1,v_2} \\ r_{2,1} & r_{2,r} & r_{2,x} & r_{2,y} & r_{2,z} & r_{2,u} & r_{2,v_1} & r_{2,v_2} \\ r_{3,1} & r_{3,r} & r_{3,x} & r_{3,y} & r_{3,z} & r_{3,u} & r_{3,v_1} & r_{3,v_2} \\ \end{bmatrix}

La matriz $\mathbf{R}$ representa los términos del lado derecho de nuestra ecuación:

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}}{\boxed{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}}}

La matriz $\mathbf{R}$ debe tener unos (1s) que representen a $y$ , $u$ y $v_2$ . La fila en la matriz corresponde a la fila de la restricción aritmética, es decir, podemos enumerar las restricciones (filas) de la siguiente manera:

\begin{matrix} (1) \\ (2) \\ (3) \\ \end{matrix} \space\space \begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}}{\boxed{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}}}

Así que la primera fila tiene 1 en la columna de $y$ , la segunda fila tiene 1 en la columna de $u$ , y la tercera fila tiene 1 en la columna de $v_2$ . Todo lo demás es cero.

Esto resulta en lo siguiente para la matriz $\mathbf{R}$ :

\begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \end{array} \end{array}

Este diagrama ilustra la transformación.

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}} {\boxed{ \begin{matrix} \color{red}{y} \\ \color{green}{u} \\ \color{violet}{v_2} \\ \end{matrix} }} \space\space\space\space \begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 &\color{violet}{1} \\ \end{bmatrix} \end{array} \end{array}

Construyendo la matriz $\mathbf{O}$

Queda como ejercicio para el lector determinar que la matriz $\mathbf{O}$ es

\mathbf{O}=\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}

usando las etiquetas de columnas consistentes con las matrices anteriores.

A modo de recordatorio, $\mathbf{C}$ se deriva del resultado de la multiplicación

\underset{\mathbf{C}}{ \boxed{\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix}}} \begin{matrix} =\\ =\\ = \end{matrix} \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

Y las etiquetas de las columnas son las siguientes

\begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{array} \end{array}

Verificando nuestro trabajo para $r = x \cdot y \cdot z \cdot u$

import numpy as np

# enter the A B and C from above
L = np.matrix([[0,0,1,0,0,0,0,0],
              [0,0,0,0,1,0,0,0],
              [0,0,0,0,0,0,1,0]])
              
R = np.matrix([[0,0,0,1,0,0,0,0],
              [0,0,0,0,0,1,0,0],
              [0,0,0,0,0,0,0,1]])
              
O = np.matrix([[0,0,0,0,0,0,1,0],
              [0,0,0,0,0,0,0,1],
              [0,1,0,0,0,0,0,0]])

# random values for x, y, z, and u
import random
x = random.randint(1,1000)
y = random.randint(1,1000)
z = random.randint(1,1000)
u = random.randint(1,1000)

# compute the algebraic circuit
r = x * y * z * u
v1 = x*y
v2 = z*u

# create the witness vector
a = np.array([1, r, x, y, z, u, v1, v2])

# element-wise multiplication, not matrix multiplication
result = np.matmul(O, a) == np.multiply(np.matmul(L, a), np.matmul(R, a))

assert result.all(), "system contains an inequality"

Ejemplo 3: Suma con una constante

¿Qué pasa si queremos construir un rank one constraint system para lo siguiente?

z = x * y + 2

Aquí es donde resulta útil esa columna del 1.

La suma es gratis

Probablemente hayas escuchado la afirmación “la suma es gratis” (addition is free) en el contexto de ZK-SNARKs. Lo que eso significa es que no tenemos que crear una restricción adicional cuando tenemos una operación de suma.

Podríamos escribir la fórmula anterior como

\begin{align*} v_1 = xy \\ z = v_1 + 2 \\ \end{align*}

pero eso haría que nuestro R1CS fuera más grande de lo necesario.

En su lugar, podemos escribirlo como

-2 + z = xy

Entonces la variable $z$ y la constante $-2$ se “combinan” automáticamente cuando multiplicamos $\mathbf{a}$ por $\mathbf{O}$ con nuestro vector witness.

Nuestro vector witness tiene la forma [1, z, x, y], por lo que nuestras matrices $\mathbf{L}$ , $\mathbf{R}$ y $\mathbf{O}$ son las siguientes:

\mathbf{L} = \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix}

\mathbf{R} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix}

\mathbf{O} = \begin{bmatrix} -2 & 1 & 0 & 0 \\ \end{bmatrix}

Siempre que haya constantes aditivas, simplemente las colocamos en la columna del $1$ , la cual por convención es la primera columna.

Nuevamente, hagamos algunas pruebas unitarias sobre nuestras matemáticas:

import numpy as np
import random

# Define the matrices
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])
O = np.matrix([[-2,1,0,0]])

# pick random values to test the equation
x = random.randint(1,1000)
y = random.randint(1,1000)
z = x * y + 2 # witness vector
a = np.array([1, z, x, y])

# check the equality
result = O.dot(a) == np.multiply(np.matmul(L, a), R.dot(a))
assert result.all(), "result contains an inequality"

Ejemplo 4: Multiplicación con una constante

En todos los ejemplos anteriores, nunca multiplicamos variables por constantes. Es por eso que las entradas en el R1CS siempre eran 1. Como habrás adivinado del ejemplo anterior, la entrada en las matrices tiene el mismo valor que la constante por la cual se multiplica la variable, como mostrará el siguiente ejemplo.

Calculemos la solución para

z = 2x^2 + y

Ten en cuenta que cuando decimos “una multiplicación por restricción” nos referimos a la multiplicación de dos variables. La multiplicación con una constante no es una multiplicación “verdadera” porque en realidad es la suma repetida de la misma variable.

La siguiente solución es válida, pero crea filas innecesarias:

\begin{align*} v_1 &= xx \\\\ z &= 2v_1 + y\\\\ \end{align*}

La solución más óptima es la siguiente:

-y + z = 2xx

Usando la solución más óptima, nuestro vector witness tendrá la forma [1, out, x, y].

Las matrices se definirán de la siguiente manera:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 2 & 0 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & -1 \\ \end{bmatrix} \\ \end{align*}

Al multiplicar simbólicamente lo anterior por [1, z, x, y] en la forma r1cs, recuperamos nuestra ecuación original:

\begin{bmatrix} 0 & 1 & 0 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix} = \begin{bmatrix} 0 & 0 & 2 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix}\circ \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix}

z - y = 2xx

z = 2x^2 + y

así que sabemos que configuramos $\mathbf{L}$ , $\mathbf{R}$ y $\mathbf{O}$ correctamente.

Aquí tenemos una fila (restricciones) y una multiplicación “verdadera”. Como regla general:

El número de restricciones en un Rank One Constraint System debería ser igual al número de multiplicaciones no constantes.

Ejemplo 5: Una restricción grande

Hagamos algo menos trivial que incorpore todo lo aprendido anteriormente

Supongamos que tenemos la siguiente restricción:

z = 3x^2y + 5xy - x - 2y + 3

La dividiremos de la siguiente manera:

\begin{align*} v_1 &= 3xx \\ v_2 &= v_1y \\ -v_2 + x + 2y - 3 + z &= 5xy \\ \end{align*}

Nota cómo todos los términos de suma se han movido a la izquierda (esto es lo que hicimos en el ejemplo de suma, pero aquí es más evidente).

Dejar el lado derecho como $5xy$ en la tercera fila es arbitrario. Podríamos dividir ambos lados por 5 y hacer que la restricción final sea

\frac{-v_2}{5} + \frac{x}{5} + \frac{2y}{5} - \frac{3}{5} + \frac{z}{5}= xy

Sin embargo, esto no cambia el witness, por lo que ambas son válidas. Dado que todo se realiza en un campo finito, esta operación es multiplicar el lado izquierdo y el lado derecho por el inverso multiplicativo de 5.

Nuestro vector witness tendrá la forma

[1, z, x, y, v_1, v_2]

Y nuestras matrices tendrán tres filas, ya que tenemos tres restricciones:

\begin{align*} \color{red}{v_1} &= \color{green}{3x}\color{violet}{x} \\ \color{red}{v_2} &= \color{green}{v_1}\color{violet}{y} \\ \color{red}{-v_2 + x + 2y - 3 + z} &= \color{green}{5x}\color{violet}{y} \\ \end{align*}

Hemos marcado la salida $\mathbf{O}$ en rojo, el lado izquierdo $\mathbf{L}$ en verde, y el lado derecho $\mathbf{R}$ en violeta. Esto produce las siguientes matrices:

L = \begin{bmatrix} 0 & 0 & \textcolor{green}{3} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \textcolor{green}{1} & 0 \\ 0 & 0 & \textcolor{green}{5} & 0 & 0 & 0 \\ \end{bmatrix}

R = \begin{bmatrix} 0 & 0 & \textcolor{violet}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & \textcolor{violet}{1} & 0 & 0 \\ 0 & 0 & 0 & \textcolor{violet}{1} & 0 & 0 \\ \end{bmatrix}

O = \begin{bmatrix} 0 & 0 & 0 & 0 & \textcolor{red}{1} & 0 \\ 0 & 0 & 0 & 0 & 0 & \textcolor{red}{1} \\ \textcolor{red}{-3} & \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{2} & 0 & \textcolor{red}{-1} \\ \end{bmatrix}

con las etiquetas de columna

\begin{bmatrix}1 & \text{out} & x & y & v_1 & v_2\end{bmatrix}

Revisemos nuestro trabajo como de costumbre.

import numpy as np
import random

# Define the matrices
L = np.array([[0,0,3,0,0,0],
               [0,0,0,0,1,0],
               [0,0,5,0,0,0]])

R = np.array([[0,0,1,0,0,0],
               [0,0,0,1,0,0],
               [0,0,0,1,0,0]])

O = np.array([[0,0,0,0,1,0],
               [0,0,0,0,0,1],
               [-3,1,1,2,0,-1]])

# pick random values for x and y
x = random.randint(1,1000)
y = random.randint(1,1000)

# this is our orignal formula
out = 3 * x * x * y + 5 * x * y - x - 2 * y + 3 # the witness vector with the intermediate variables inside
v1 = 3*x*x
v2 = v1 * y
w = np.array([1, out, x, y, v1, v2])

result = O.dot(w) == np.multiply(L.dot(w),R.dot(w))
assert result.all(), "result contains an inequality"

Los Rank 1 Constraint Systems no requieren comenzar con un solo polinomio

Para mantener las cosas simples, hemos estado usando ejemplos de la forma $z = xy + ...$ pero la mayoría de las restricciones aritméticas realistas van a ser un conjunto de restricciones aritméticas, no solo una.

Por ejemplo, supongamos que estamos probando que un arreglo $[x₁, x₂, x₃, x₄]$ es binario y $v$ es menor que 16. El conjunto de restricciones será

\begin{align*} x₁² &= x₁\\ x₂² &= x₂\\ x₃² &= x₃\\ x₄² &= x₄ \\ v &= 8x₄ + 4x₃ + 2x₂ + x₁ \end{align*}

Para convertir esto en un rank one constraint system, notamos que la fila final no tiene ninguna multiplicación, por lo que podemos sustituir $x_1$ en la primera restricción:

\begin{align*} x₁² &= v - 8x₄ - 4x₃ - 2x₂\\ x₂² &= x₂\\ x₃² &= x₃\\ x₄² &= x₄ \\ \end{align*}

Asumiendo que nuestro vector witness es $[1, v, x_1, x_2, x_3, x_4]$ , podemos crear el R1CS de la siguiente manera:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & -2 & -4 & -8 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \end{align*}

Hacer la sustitución no es estrictamente necesario, pero ahorra una fila en el R1CS. En una sección posterior, mostraremos un R1CS válido donde no hacemos la sustitución.

Todo se hace módulo un primo en r1cs

En los ejemplos anteriores, usamos aritmética tradicional en aras de la simplicidad, pero las implementaciones del mundo real usan aritmética modular en su lugar.

La razón es simple: codificar números como 2/3 conduce a números de punto flotante de mal comportamiento que son computacionalmente intensivos y propensos a errores.

Si hacemos todas nuestras matemáticas módulo un número primo, digamos 23, entonces codificar $2/3$ es sencillo. Es lo mismo que $2 \cdot 3^{-1}$ , y multiplicar por dos y elevar a la potencia de negativo 1 son procesos directos en aritmética modular.

Implementación en Circom.

En Circom, un lenguaje para construir Rank 1 Constraint Systems, el campo finito usa el número primo $21888242871839275222246405745257275088548364400416034343698204186575808495617$ (esto es igual al orden de la curva BN128 que discutimos en Elliptic Curves over Finite Fields).

Esto significa que $-1$ en esa representación es

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# 1 - 2 = -1
(1 - 2) % p

# 21888242871839275222246405745257275088548364400416034343698204186575808495616

Circom para out = x * y

Si escribimos out = x * y en Circom, se vería como lo siguiente:

pragma circom 2.0.0;

template Multiply2() {
    signal input x;
    signal input y;
    signal output out;

    out <== x * y;
 }

component main = Multiply2();

Convirtamos esto en un archivo R1CS e imprimamos el archivo R1CS

circom multiply2.circom --r1cs --sym
snarkjs r1cs print multiply2.r1cs

Obtenemos la siguiente salida:

Esto se ve un poco diferente a nuestra solución R1CS, pero en realidad está codificando la misma información.

Aquí están las diferencias en la implementación de Circom:

Las columnas con valor cero no se imprimen
Circom escribe $\mathbf{O}\mathbf{a} = \mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}$ como $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$

¿Qué pasa con el 21888242871839275222246405745257275088548364400416034343698204186575808495616 que es realmente -1?

La solución de Circom es

\begin{align*} A &= \begin{bmatrix} 0 & 0 & -1 & 0 \end{bmatrix}\\ B &= \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}\\ C &= \begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix} \end{align*}

Aunque los unos negativos puedan ser inesperados, con el vector witness [1 out x y], esto es en realidad consistente con la forma $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ . (Veremos en un segundo que Circom efectivamente usó esta asignación de columnas).

Puedes sustituir los valores para $x$ , $y$ y out y ver que la ecuación $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ se cumple.

Veamos la asignación de variables a columnas de Circom. Recompilemos nuestro circuito con un solver wasm:

circom multiply2.circom --r1cs --wasm --sym

cd multiply2_js/

Creamos el archivo input.json

echo '{"x": "11", "y": "9"}' > input.json

Y calculamos el witness

node generate_witness.js multiply2.wasm input.json witness.wtns

snarkjs wtns export json witness.wtns witness.json

cat witness.json

Obtenemos el siguiente resultado:

Está claro que Circom está usando el mismo diseño de columnas que hemos estado usando: [1, out, x, y], ya que $x$ se estableció en $11$ e $y$ en $9$ en nuestro input.json.

Si usamos el witness generado de Circom (reemplazando el número masivo con -1 para mayor legibilidad), entonces vemos que el R1CS de Circom es correcto

\begin{align*} \mathbf{a} &= \begin{bmatrix} 1 & 99 & 11 & 9 \end{bmatrix}\\ \mathbf{L} &= \begin{bmatrix} 0 & 0 & -1 & 0 \end{bmatrix} \rightarrow \mathbf{L}\mathbf{a} = -11\\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \rightarrow \mathbf{R}\mathbf{a} = 9\\ \mathbf{O} &= \begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix} \rightarrow \mathbf{O}\mathbf{a} = -99 \end{align*}

\begin{align*} Aw \cdot Bw - Cw &= 0\\ (-11)(9) - (-99) &= 0 \\ -99 + 99 &= 0 \end{align*}

$\mathbf{L}$ tiene un coeficiente de $-1$ para $x$ , $\mathbf{R}$ tiene un coeficiente de $+1$ para $y$ , y $\mathbf{O}$ tiene $-1$ para $\text{out}$ . En forma modular, esto es idéntico a lo que la terminal generó arriba:

Revisando el resto de nuestro trabajo

A modo de repaso, las fórmulas que exploramos fueron

\begin{align} z &= x * y \\ z &= x * y * z * u \\ z &= x * y + 2 \\ z &= 3x^2 y + 5xy - x - 2y + 3 \end{align}

Acabamos de hacer (1) en la sección anterior, para esta sección ilustraremos el principio de que el número de multiplicaciones no constantes es el número de restricciones.

El circuito para (2) es:

pragma circom 2.0.8;

template Multiply4() {
    signal input x;
    signal input y;
    signal input z;
    signal input u;
    
    signal v1;
    signal v2;
    
    signal out;
    
    v1 <== x * y;
    v2 <== z * u;
    
    out <== v1 * v2;
}

component main = Multiply4();

Con todo lo que hemos discutido hasta ahora, la salida de Circom y las anotaciones deberían explicarse por sí solas.

Con eso en mente, nuestras otras fórmulas deberían tener las siguientes restricciones:

\begin{align} z &= x * y && \text{1 restricción} \\ z &= x * y * z * u && \text{3 restricciones} \\ z &= x * y + 2 && \text{1 restricción} \\ z &= 3x^2 y + 5xy - x - 2y + 3 && \text{3 restricciones} \end{align}

Queda como ejercicio para el lector escribir los circuitos de Circom y verificar lo anterior.

No necesitas un witness para calcular el R1CS

Nota que en el código de Circom nunca proporcionamos el witness antes de calcular el R1CS. Proporcionamos el witness antes para hacer el ejemplo menos abstracto y para facilitar la revisión de nuestro trabajo, pero no es necesario. ¡Esto es importante, porque si un verificador necesitara un witness para construir un R1CS, entonces el probador tendría que revelar la solución oculta!

Cuando decimos “witness” nos referimos a un vector con valores poblados. El verificador conoce la “estructura” del witness, es decir, las asignaciones de variables a columnas, pero no conoce los valores.

Un R1CS es válido incluso si no está optimizado

Una transformación válida de un polinomio a un R1CS no es única. Puedes codificar el mismo problema con más restricciones, lo cual es menos eficiente. Aquí hay un ejemplo.

En algunos tutoriales de R1CS, las restricciones para una fórmula como

z = x² + y

se transforman en

\begin{align*} v₁ &= x x \\ z &= v₁ + y \end{align*}

Como hemos notado, esto no es eficiente. Sin embargo, creas un R1CS válido para esto usando la metodología de este artículo. Simplemente agregamos una multiplicación ficticia de esta manera:

\begin{align*} v₁ &= x x \\ z &= (v₁ + y) * 1 \end{align*}

Nuestro vector witness tiene la forma $[1, z, x, y, v1]$ y $\mathbf{L}$ , $\mathbf{R}$ , y $\mathbf{O}$ se definen de la siguiente manera:

\mathbf{L} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

\mathbf{R} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix}

\mathbf{O} = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix}

La segunda fila de $\mathbf{L}$ lleva a cabo la suma, y la multiplicación por uno se logra utilizando el primer elemento de la segunda fila de $\mathbf{R}$ .

Esto es perfectamente válido, pero la solución tiene una fila y una columna más de lo que necesita.

¿Qué pasa si no hay multiplicaciones?

¿Qué pasa si queremos codificar el siguiente circuito?

z = x + y

Esto es bastante inútil en la práctica, pero en aras de la completitud, puede resolverse con una multiplicación ficticia por uno.

out = (x + y)*1

Con nuestro diseño típico del vector witness de $[1, z, x, y]$ , tenemos las siguientes matrices:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 1 & 1 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix} \end{align*}

Los Rank One Constraint Systems son por conveniencia

El documento original para Groth16 no tiene ninguna referencia al término Rank One Constraint System. Un R1CS es práctico desde la perspectiva de la implementación, pero desde una perspectiva matemática pura, simplemente etiqueta y agrupa explícitamente los coeficientes de las diferentes variables. Así que cuando lees trabajos académicos sobre el tema, generalmente falta porque es un detalle de implementación de un concepto más abstracto.

Recursos útiles

Esta herramienta web calcula R1CS para un conjunto de restricciones (pero solo funciona con una variable de entrada y una de salida).
El famoso ejemplo de Vitalik de x**3 + x + 5 == 35
El tutorial de R1CS del blog Zero knowledge

Aprende más con RareSkills

Esta publicación de blog se extrajo de los materiales de aprendizaje en nuestro curso de zero knowledge.