Al realizar computaciones iterativas, como potencias, factoriales o el cálculo de la secuencia de Fibonacci, necesitamos “detener la computación” después de cierto punto.
Por ejemplo, si estamos calculando , multiplicaríamos por sí mismo siete veces. Sin embargo, la detención condicional no es posible en un circuito aritmético. Dado que los circuitos son de un tamaño fijo (el R1CS subyacente tiene un número fijo de filas y no se puede cambiar), deben ser lo suficientemente grandes como para contemplar cada exponente que nos interese calcular.
Por lo tanto, la solución es calcular todos los valores posibles hasta cierto límite superior al que esperamos calcular en la práctica. Luego, usamos un Quin selector para elegir el valor deseado.
Este capítulo muestra un ejemplo de cómo hacer esto con el factorial y la secuencia de Fibonacci, y deja el cálculo de la potencia como ejercicio.
Podemos pensar en cada una de estas computaciones como una máquina de estados que pasa por una transición de estado fija un número determinado de veces (donde el número de iteraciones se determina en el momento de la prueba y no está integrado en el circuito).
Estas secuencias solo tienen una computación posible en cada paso (por ejemplo, sumar los dos estados anteriores o multiplicar el estado anterior por algún número). Sin embargo, si agregamos ramificación condicional en cada estado, entonces tenemos todos los componentes necesarios para una computación con estado.
En este capítulo, solo mostraremos ejemplos donde hay un único cambio de estado posible y el número de cambios de estado es variable. En los próximos capítulos, mostraremos cómo hacer que la transición de estado en sí misma sea condicional, es decir, que tenga múltiples transiciones de estado posibles.
Ejemplo de factorial
Ahora mostraremos cómo escribir un circuito que demuestre que calculamos correctamente
donde es el factorial y es el módulo del campo por defecto.
Para calcular un factorial en un lenguaje de programación tradicional, como Python, el código sería el siguiente:
def factorial_mod_p(x, p):
if x == 0:
return 1
acc = 1
for i in range(1, x+1):
acc = (acc * i) % p
return acc
Sin embargo, el código anterior tendrá algunos problemas si se traduce directamente a Circom:
- Circom no soporta declaraciones condicionales if, por lo que la línea
if x == 0: return 0no compilará. - Circom no soporta bucles con un número desconocido de iteraciones. Dado que
xdetermina el valor del bucle, esto tampoco compilará. Circom se compila a un R1CS internamente, y el R1CS subyacente necesita tener un tamaño fijo y no puede cambiar su tamaño según el valor de las entradas.
Para que el código sea compatible con una representación de aritmetización como R1CS, necesitamos calcular el factorial desde cero hasta algún límite superior que pretendamos soportar.
Por ejemplo, si sabemos que nunca necesitaremos calcular un factorial mayor que 99, entonces debemos calcular todos los factoriales del 0 al 99 inclusive. Si queremos crear una prueba para el factorial de 80, todavía necesitamos calcular los factoriales del 0 al 99, pero usamos un Quin selector para devolver el resultado para 80.
Aquí hay un ejemplo en Python que no tiene declaraciones if y usa un bucle de longitud fija:
def factorial_mod_p(x, p):
assert x < 100
# allocate the array
ans = [0] * 100
ans[0] = 1 # 0! = 1
for i in range(1, 100):
ans[i] = (ans[i-1] * i) % p
return ans[x]
En cierto sentido, estamos creando un array de longitud 100 y rellenando los valores con el factorial de ese índice. Luego, “seleccionaremos” el factorial que nos interesa utilizando el Quin selector.
La traducción a Circom es directa:
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";
template factorial(n) {
signal input in;
signal output out;
// precompute factorials from 0 to n
signal factorials[n+1];
// compute the factorials
factorials[0] <== 1;
for (var i = 1; i <= n; i++) {
factorials[i] <== factorials[i - 1] * i;
}
// ensure that in < n
signal inLTn;
inLTn <== LessThan(252)([in, n]);
inLTn === 1;
// select the factorial of interest
component mux = Multiplexer(1, n);
mux.sel <== in;
// assign factorials into the multiplexer
for (var i = 0; i < n; i++) {
mux.inp[i][0] <== factorials[i];
}
out <== mux.out[0];
}
component main = factorial(100);
/*
INPUT = { "in": "3" }
*/
Una implementación insegura
Muchos ingenieros nuevos en Circom a menudo usan una solución “intuitiva” que evita cualquier problema con las restricciones cuadráticas y produce un código como el siguiente:
pragma circom 2.1.8;
include "./node_modules/circomlib/circuits/comparators.circom";
template factorial(n) {
signal input in;
signal output out;
signal factorials[n + 1];
// compute the factorials
var acc = 1;
for (var i = 1; i < n; i++) {
acc = acc * i;
}
out <-- acc;
}
component main = factorial(100);
Aunque out tendrá la respuesta correcta, la ausencia total de los operadores <== o === significa que el circuito no tiene restricciones.
En el código anterior, el programador ha producido un código para calcular correctamente el factorial, pero no para restringirlo.
Ejemplo de Fibonacci módulo p
En el ejemplo del factorial, tuvimos que “hardcodear” (fijar en el código) la entrada 0 de factorials como 1, ya que 0! = 1. En la secuencia de Fibonacci, los primeros dos números son 1, y todo lo posterior es la suma de los dos números anteriores en la secuencia. Por lo tanto, para el código de Fibonacci, fijamos directamente los dos primeros valores y luego calculamos el resto.
El siguiente circuito calcula la secuencia de Fibonacci hasta el n-ésimo número módulo p, y luego devuelve el número de Fibonacci de interés indicado por “in”.
include "./node_modules/circomlib/circuits/multiplexer.circom";
include "./node_modules/circomlib/circuits/comparators.circom";
template Fibonacci(n) {
assert(n >= 2); // so we don't break the hardcoding
signal input in; // compute the kth Fibonacci number
signal output out;
// precompute Fibonacci sequence from
// 0 to n
signal fib[n + 1];
// compute the factorials
fib[0] <== 1;
fib[1] <== 1;
for (var i = 2; i < n; i++) {
fib[i] <== fib[i - 1] + fib[i - 2];
}
// ensure that in < n
signal inLTn;
inLTn <== LessThan(252)([in, n]);
inLTn === 1;
// select the fibonacci number
// of interest
component mux = Multiplexer(1, n);
mux.sel <== in;
// assign Fibonacci into
// the Quin Selector
for (var i = 0; i < n; i++) {
mux.inp[i][0] <== fib[i];
}
out <== mux.out[0];
}
component main = Fibonacci(99);
/*
INPUT = {"in": 5}
*/
Como es habitual, es importante restringir de forma explícita cada actualización de la secuencia de Fibonacci, y no simplemente calcular el resultado en un bucle sin restricciones.
Ejercicio:
Completa el ejercicio pow en Circom Puzzles.