Para hacer que la transformación de R1CS a QAP sea menos abstracta, usemos un ejemplo real.
Supongamos que estamos codificando el circuito aritmético
Convertido a un Rank 1 Constraint System, esto se convierte en
Necesitamos elegir una característica del campo finito sobre el cual haremos esto. Cuando más adelante combinemos esto con curvas elípticas, el orden de nuestro campo primo debe ser igual al orden de la curva elíptica. (No hacer que ambos coincidan es un error muy común).
Pero por ahora, elegiremos un número pequeño para que esto sea manejable. Elegiremos el número primo 79.
Primero, definimos nuestras matrices , y de la siguiente manera:
import numpy as np
# 1, out, x, y, v1, v2, v3
L = np.array([
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, -5, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1],
])
R = np.array([
[0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0],
])
O = np.array([
[0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, -1, 0],
])
Para verificar que construimos el R1CS correctamente (¡es muy fácil equivocarse al hacerlo manualmente!) creamos un witness válido y realizamos la multiplicación de matrices:
x = 4
y = -2
v1 = x * x
v2 = v1 * v1 # x^4
v3 = -5*y * y
z = v3*v1 + v2 # -5y^2 * x^2
# witness
a = np.array([1, z, x, y, v1, v2, v3])
assert all(np.equal(np.matmul(L, a) * np.matmul(R, a), np.matmul(O, a))), "not equal"
Aritmética de campos finitos en Python
El siguiente paso es convertir esto en un arreglo de campo. Hacer aritmética modular en Numpy se volverá muy complicado, pero es sencillo con la biblioteca galois. Esto se introdujo en nuestro artículo sobre campos finitos, pero aquí hay un breve repaso de cómo usarlo:
import galois
GF = galois.GF(79)
a = GF(70)
b = GF(10)
print(a + b)
# prints 1
No podemos darle valores negativos como GF(-1) o lanzará una excepción. Para convertir números negativos a su representación congruente en el campo, podemos sumarles el orden de la curva. Para evitar el desbordamiento de los valores positivos, aplicamos el módulo con el orden de la curva.
L = (L + 79) % 79
R = (R + 79) % 79
O = (O + 79) % 79
Nuestras nuevas matrices son
## New values of L, R, O
'''
L
[[ 0 0 1 0 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 74 0 0 0]
[ 0 0 0 0 0 0 1]]
R
[[ 0 0 1 0 0 0 0]
[ 0 0 0 0 1 0 0]
[ 0 0 0 1 0 0 0]
[ 0 0 0 0 1 0 0]]
O
[[ 0 0 0 0 1 0 0]
[ 0 0 0 0 0 1 0]
[ 0 0 0 0 0 0 1]
[ 0 1 0 0 0 78 0]]
'''
Ahora podemos convertirlas en arreglos de campo simplemente envolviéndolas con GF. También necesitaremos volver a calcular nuestro witness, porque contiene valores negativos.
L_galois = GF(L)
R_galois = GF(R)
O_galois = GF(O)
x = GF(4)
y = GF(-2 + 79) # we are using 79 as the field size, so 79 - 2 is -2
v1 = x * x
v2 = v1 * v1 # x^4
v3 = GF(-5 + 79)*y * y
out = v3*v1 + v2 # -5y^2 * x^2
witness = GF(np.array([1, out, x, y, v1, v2, v3]))
assert all(np.equal(np.matmul(L_galois, witness) * np.matmul(R_galois, witness), np.matmul(O_galois, witness))), "not equal"
Interpolación polinómica en campos finitos
Ahora, necesitamos convertir cada una de las columnas de las matrices en una lista de polinomios de galois que interpolen las columnas. Los puntos que interpolaremos son x = [1,2,3,4], ya que tenemos 4 filas.
def interpolate_column(col):
xs = GF(np.array([1,2,3,4]))
return galois.lagrange_poly(xs, col)
# axis 0 is the columns.
# apply_along_axis is the same as doing a for loop over the columns and collecting the results in an array
U_polys = np.apply_along_axis(interpolate_column, 0, L_galois)
V_polys = np.apply_along_axis(interpolate_column, 0, R_galois)
W_polys = np.apply_along_axis(interpolate_column, 0, O_galois)
Si volvemos a ver el contenido de nuestras matrices, esperamos que los dos primeros polinomios de U_polys y V_polys sean cero, y que la primera columna de W_polys también sea cero.
Ejecutamos la siguiente comprobación de validez:
print(U_polys[:2])
print(V_polys[:2])
print(W_polys[:1])
# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79))]
El término Poly(0, GF(79)) es simplemente un polinomio donde todos los coeficientes son cero.
Se anima al lector a evaluar los polinomios en los valores del R1CS para comprobar que interpolan los valores de la matriz correctamente.
Calculando h(x)
Ya sabemos que será ya que hay cuatro filas.
A modo de recordatorio, esta es la fórmula para un Quadratic Arithmetic Program. El vector es el witness:
Cada uno de los términos representa el producto interno del witness con los polinomios de interpolación de las columnas. Es decir, cada uno de los términos de la suma es efectivamente el producto interno entre y
def inner_product_polynomials_with_witness(polys, witness):
mul_ = lambda x, y: x * y
sum_ = lambda x, y: x + y
return reduce(sum_, map(mul_, polys, witness))
term_1 = inner_product_polynomials_with_witness(U_polys, witness)
term_2 = inner_product_polynomials_with_witness(V_polys, witness)
term_3 = inner_product_polynomials_with_witness(W_polys, witness)
Para calcular , simplemente despejamos la variable. Ten en cuenta que no podemos calcular a menos que tengamos un witness válido, de lo contrario habrá un residuo.
# t = (x - 1)(x - 2)(x - 3)(x - 4)
t = galois.Poly([1, 78], field = GF) * galois.Poly([1, 77], field = GF) * galois.Poly([1, 76], field = GF) * galois.Poly([1, 75], field = GF)
h = (term_1 * term_2 - term_3) // t
A diferencia de poly1d de numpy, la biblioteca galois no nos indicará si hay un residuo, por lo que necesitamos comprobar si la fórmula del QAP sigue siendo cierta.
assert term_1 * term_2 == term_3 + h * t, "division has a remainder"
La comprobación ejecutada arriba es muy similar a lo que el verificador comprobará.
El esquema anterior no funcionará cuando evaluemos los polinomios en un punto oculto proveniente de un trusted setup. Sin embargo, la computadora que realice el trusted setup todavía tendrá que ejecutar muchos de los cálculos anteriores.
Resumen
En este artículo, presentamos el código en Python para convertir un R1CS en un QAP.
Aprende más con RareSkills
Este material pertenece a nuestro Zero Knowledge Course.