Restricciones en Circom

Un Rank 1 Constraint System tiene como máximo una multiplicación entre señales por restricción. A esto se le llama una restricción “cuadrática”. Cualquier restricción que contenga una operación distinta a la suma o multiplicación será rechazada por Circom con el error “Non quadratic constraints are not allowed”.

Los siguientes dos ejemplos no compilarán porque tienen más de una multiplicación de señales por restricción.

Ejemplo 1 de restricción no cuadrática

Compilar lo siguiente resultará en el siguiente error: [T3001]: Non quadratic constraints are not allowe

Copy
template QuadraticViolation1() {
  signal input a;
  signal input b;
  signal input c;
  signal input d;
  
  // two multiplications per constraint
  // is not allowed
  a * b === c * d;
}

Ejemplo 2 de restricción no cuadrática

De manera similar al ejemplo anterior, la siguiente restricción tiene dos multiplicaciones entre señales.

Copy
template QuadraticViolation2() {
  signal input a;
  signal input b;
  signal input c;
  signal input d;
  
  // two multiplications per constraint
  // is not allowed
  a * b * c === d;
}

Las multiplicaciones por constantes no cuentan

Por lo tanto, los siguientes ejemplos compilarán, a pesar de que hay más de una multiplicación.

Copy
a * b === c;

2*a * 3*b === 4*c; // integer coefficients allowed

a * b + c === d; // addition and one multiplication allowed

a + b + c === d; // multiplication is optional

a * b + c === d + e + f; // no restrictions on number of additions

Forma cuadrática y R1CS

Recuerda que en la aritmetización, aplanamos nuestro programa de verificación en una serie de pasos intermedios, donde cada paso intermedio solo contiene una única multiplicación entre variables desconocidas.

Considera el siguiente ejemplo de verificación:

Copy
def someProblem(x, y, out):
  res = y^2 + 4*(x^2)*y -2 
  assert out == res, "incorrect inputs";

La conversión a un R1CS nos daría:

Copy
v1  === y * y
v2  === x * x 
out === v1 + (4v2 * y) - 2

• El formato R1CS requiere que reestructuremos el problema en pasos intermedios que solo tengan 1 operación de multiplicación entre señales para adherirse a la limitación de la restricción cuadrática.
• Esto crea nuestro sistema de restricciones.

En consecuencia, la representación R1CS sería:

Copy
//     Cw = Aw * Bw
       v1  = y * y
       v2  = x * x 
out -v1 +2 = (4v2 * y)

Dado que previamente nos aseguramos de que solo hubiera 1 multiplicación por restricción, podemos expresar el sistema de restricciones en forma vectorial, lo cual es un R1CS.

Ejemplos de operadores no multiplicativos que causan una restricción no cuadrática

Si se utiliza una operación ilegal (distinta a la suma o la multiplicación) en una restricción, el compilador de Circom reportará el error “Non quadratic constraints are not allowed!”.

Aquí proporcionamos algunos ejemplos.

Ejemplo 1: Las señales no se pueden usar para indexar arreglos de señales

La siguiente operación resultará en una violación de restricciones cuadráticas. No existe una traducción directa de la indexación de arreglos a sumas y multiplicaciones. El siguiente código resulta en el error Non-quadratic constraint was detected statically, using unknown index will cause the constraint to be non-quadratic:

Copy
template KMustEqual5(n) {

  signal input in[n];
  signal input k;
  
  // not allowed
  in[k] === 5;
}

Todavía es técnicamente posible lograr la indexación de arreglos, pero esto requiere una solución más compleja que mostraremos en un capítulo posterior.

Ejemplo 2: Las señales no pueden usar operaciones como % y <<

Las siguientes restricciones crearán una violación del tipo “Non quadratic constraints are not allowed!”:

Copy
template Example() {
  signal input a;
  signal input b;
  
  // not allowed
  a === b % 5;
  
  // not allowed
  a === b << 2;
}

Cómo maneja Circom la división

De manera un tanto sutil, Circom permitirá la “división” por una constante, porque simplemente puede ser reemplazada por la multiplicación por el inverso multiplicativo de ese número. Como tal, el siguiente código es válido:

Copy
template Example() {
  signal input a;
  signal input b;
  
  a === b / 2;
}

component main = Example();

Sin embargo, dividir señales no está permitido porque eso significa que calculamos el inverso multiplicativo de la señal, lo cual no tiene una traducción directa a solo suma y multiplicación. El cálculo del inverso multiplicativo se realiza usualmente con el algoritmo de Euclides extendido, el cual requiere bucles y declaraciones condicionales — operaciones que no pueden expresarse de forma nativa con suma y multiplicación.

Copy
template Example() {
  signal input a;
  signal input b;
  signal input c;
  
  // not allowed
  a === b / c;
}

component main = Example();

Por el contrario, la resta de señales sí está permitida porque se traduce directamente en la multiplicación por la constante -1:

Copy
template Example() {
  signal input a;
  signal input b;
  
  // allowed
  a === b - a;
  
  // equivalent
  a === b + -1*a
}

component main = Example();

La división entera, a diferencia de la multiplicación por el inverso modular, se representa con \ y no está permitido aplicarla a señales:

Copy
template Example() {
  signal input a;
  signal input b;
  
  // can only use \ with variables
  // not signals
  a === b \ 2;
}

component main = Example();

Para las variables, se tiene tanto la división entera como la división “normal” (es decir, la multiplicación por el inverso multiplicativo del divisor).

Para las señales, por otro lado, solo se permite la división “normal” (en el sentido anterior).

Resumen

Una restricción solo puede tener una multiplicación entre señales, pero no hay límite en el número de sumas.

Podría parecer que esta restricción hace imposible expresar cualquier cálculo interesante más allá de la aritmética simple, pero veremos más adelante en esta serie de tutoriales que existen numerosos e ingeniosos patrones de diseño para eludir esta limitación.

Una vez que entendamos los patrones de diseño, podremos combinarlos para modelar algoritmos mucho más complejos.