El Quin Selector es un patrón de diseño que nos permite usar una señal como índice para un array de señales.

Como requisito previo, asumimos que el lector ha leído el capítulo sobre Sentencias Condicionales en Circom.

El siguiente código no compila, pero ilustra lo que estamos intentando lograr:

Copy
template ArraySelect(n) {

  signal input in[n];
  signal input index;
  
  signal output out;
  
  // won't compile -- non-quadratic constraints
  out <== in[index];
}

Para expresar algo condicional en Circom, multiplicamos la rama deseada por uno y las demás por cero, y luego sumamos todas las ramas. Las ramas en cero no tendrán ningún efecto sobre la suma. El Quin Selector sigue la misma lógica: multiplicamos el índice deseado por 1 y el resto por cero, para luego sumar el resultado.

Como ejemplo, supongamos que nuestro array de entrada es in = [5,9,14,20]. Seleccionar el elemento en el índice 2 significa que calculamos:

En otras palabras, hacemos un cálculo de producto interno entre [5,9,14,20] y [0,0,1,0], lo cual da como resultado 14.

Cada «interruptor» se convierte en 0 o 1 si index es igual al índice deseado.

Copy
include "./node_modules/circomlib/comparators.circom";

template ArraySelect(n) {

  signal input in[n];
  signal input index;
  signal output out;
  
  component eqs[n];
  
  // prod keeps a running product
  signal prod[n];
  
  // prod = 1 * in[i] if i == index else 0
  for (var i = 0; i < n; i++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== index;
    
    prod[i] <== eqs[i].out * in[i];
  }
  
  // sum the result
  var sum;
  for (var i = 0; i < n; i++) {
    sum += prod[i];
  }
  
  out <== sum;
}

El código anterior no restringe que el índice sea menor que el tamaño del array. Si el índice está fuera de los límites, entonces el código devolverá 0 como resultado. La implementación del Quin Selector en DarkForest incluye una verificación de rango en index, por lo que remitimos al lector a esa plantilla, en la cual se basaron los ejemplos anteriores:

Copy
// out is the sum of in
template CalculateTotal(n) {
  signal input in[n];
  signal output out;

  signal sums[n];

  sums[0] <== in[0];

  for (var i = 1; i < n; i++) {
      sums[i] <== sums[i-1] + in[i];
  }

  out <== sums[n-1];
}

template QuinSelector(choices) {
  signal input in[choices];
  signal input idx;
  signal output out;
  
  // Ensure that idx < choices
  component lessThan = LessThan(252);
  lessThan.in[0] <== idx;
  lessThan.in[1] <== choices;
  lessThan.out === 1;

  component calcTotal = CalculateTotal(choices);
  component eqs[choices];

  // For each item, check whether its index equals the input idx.
  for (var i = 0; i < choices; i ++) {
    eqs[i] = IsEqual();
    eqs[i].in[0] <== i;
    eqs[i].in[1] <== idx;

    // eqs[i].out is 1 if the idx matches. As such, at most one input to
    // calcTotal is not 0.
    calcTotal.in[i] <== eqs[i].out * in[i];
  }

  // Returns 0 + 0 + 0 + item
  out <== calcTotal.out;
}

Como optimización, el paso component lessThan = LessThan(252); no necesita 252 bits para asegurar que idx sea menor que choices. Dependiendo de nuestra aplicación, podríamos usar un número mucho menor de bits para hacer la comparación y ahorrar en la cantidad de restricciones generadas internamente.

Implementación del Quin Selector en Circomlib

El multiplexor en la biblioteca Circomlib logra lo mismo que el Quin Selector. Sin embargo, indexa un array bidimensional y devuelve un array unidimensional. Por ejemplo, dado el array in = [[5,5],[6,6],[7,7]] e idx = 1, devolvería [6, 6].

El componente tiene las siguientes entradas y salidas:

Copy
template Multiplexer(wIn, nIn) {
  signal input inp[nIn][wIn];
  signal input sel;
  signal output out[wIn];

  // ...
}

Usando el ejemplo in = [[5,5],[6,6],[7,7]], wIn sería 2 y nIn sería 3. La señal sel es el índice a elegir; por ejemplo, si sel = 1 entonces out = [6,6].

En lugar de recorrer el array en un bucle y comprobar si el índice es igual (IsEqual) al valor sel, el Multiplexer genera una «máscara» de puros ceros con un 1 en el índice deseado y multiplica esa máscara por la entrada. Por ejemplo, si sel = 1 genera la máscara [0,1,0] y multiplica la entrada por esa máscara.

Aquí hay un ejemplo de uso del multiplexor de Circomlib:

Copy
include "circomlib/multiplexer.circom";

template MultiplexerExample(n) {
  signal input in[n];
  signal input k;
  signal output out;

  component mux = Multiplexer(1, n);

  for (var i = 0; i < n; i++) {
    mux.inp[i][0] <== in[i];
  }
  mux.sel <== k;

  out <== mux.out[0];
}

component main = MultiplexerExample(4);

/* INPUT = {
  "in": [3, 7, 9, 11],
  "k": "1"
} */

Nota Histórica

A este algoritmo se le llamaba «Linear Scan» en el artículo de xjsnark, que es anterior a la implementación de eth Dark Forest. Crédito a 0xerhant por señalar esto.