Este capítulo muestra cómo intercambiar dos señales en una lista de señales. Esta es una subrutina importante para un algoritmo de ordenamiento. De manera más general, las listas son un bloque de construcción fundamental para funciones más interesantes como funciones hash o el modelado de memoria en una CPU, por lo que debemos aprender a actualizar sus valores.

Intercambiar dos elementos en una lista es una de las primeras cosas que aprenden los programadores, una solución típica se ve de la siguiente manera:

Copy
# s and t are indexes of array arr
def swap(arr, s, t):
  temp = arr[s];
  arr[s] = arr[t];
  arr[t] = temp;
  return arr

Sin embargo, en un circuito ZK, esta operación puede ser sorprendentemente complicada.

• Primero, no podemos indexar directamente un array de señales. Para ello, necesitamos usar un Quin selector.
• Segundo, no podemos “escribir en” una señal dentro de un array de señales porque las señales son inmutables.

En su lugar, necesitamos crear un nuevo array y copiar los valores antiguos al nuevo array, sujeto a las siguientes condiciones:

• Si estamos en el índice s, escribimos el valor de arr[t]
• Si estamos en el índice t, escribimos el valor de arr[s]
• De lo contrario, escribimos el valor original

Cada escritura que hacemos en el nuevo array es una operación condicional.

El Quin selector se explicó en un capítulo anterior — no replicaremos el código aquí para ahorrar espacio.

Intercambio en Circom

El siguiente componente intercambiará el elemento en el índice s con el elemento en el índice t y devolverá un nuevo array. (El siguiente código tiene un error, ¡intenta encontrarlo! La respuesta se da más adelante).

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];
  
  // we do not check that
  // s < n or t < n
  // because the Quin selector
  // does that

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }
  
  // qss.out holds in[s]
  // qst.out holds in[t]

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s,
    // write in[t]
    // if we are at index t,
    // write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    out[i] <==  branchS[i] + branchT[i] + branchNorST[i];
  }
}

Ten en cuenta que la declaración condicional final

Copy
branchS[i] <== IdxEqS[i].out * qst.out;
branchT[i] <== IdxEqT[i].out * qss.out;
branchNorST[i] <== IdxNorST[i].out * in[i];
out[i] <==  branchS[i] + branchT[i] + branchNorST[i];

no se puede escribir como

Copy
out[i] <==  IdxEqS[i].out * qst.out + IdxEqT[i].out * qss.out + IdxNorST[i].out * in[i]

porque eso produciría un error de restricciones no cuadráticas (hay más de una multiplicación en la restricción).

Encuentra el error

Hay un error en el código de arriba — ¿puedes encontrarlo antes de desplazarte hacia abajo?

El error en el código

El problema con el código de arriba es que no tiene en cuenta el hecho de que el valor en s podría ser igual al valor en t (s == t). En esa circunstancia, el valor escrito en el índice será el valor en ese índice sumado a sí mismo.

Solucionando el problema

Para evitar esto, necesitamos detectar explícitamente si s == t y multiplicar ya sea branchS o branchT por cero para evitar duplicar el valor. En otras palabras, si los interruptores para s y t están ambos activos, entonces el valor resultante sería s + t. Pero no queremos eso, queremos que el valor permanezca efectivamente sin cambios seleccionando branchS o branchT arbitrariamente (tendrán el mismo valor):

Copy
template Swap(n) {
  signal input in[n];
  signal input s;
  signal input t;
  signal output out[n];

  // NEW CODE to detect if s == t
  signal sEqT;
  sEqT <== IsEqual()([s, t]);

  // get the value at s
  component qss = QuinSelector(n);
  qss.idx <== s;
  for (var i = 0; i < n; i++) {
    qss.in[i] <== in[i];
  }

  // get the value at t
  component qst = QuinSelector(n);
  qst.idx <== t;
  for (var i = 0; i < n; i++) {
    qst.in[i] <== in[i];
  }

  component IdxEqS[n];
  component IdxEqT[n];
  component IdxNorST[n];
  signal branchS[n];
  signal branchT[n];
  signal branchNorST[n];
  for (var i = 0; i < n; i++) {
    IdxEqS[i] = IsEqual();
    IdxEqS[i].in[0] <== i;
    IdxEqS[i].in[1] <== s;

    IdxEqT[i] = IsEqual();
    IdxEqT[i].in[0] <== i;
    IdxEqT[i].in[1] <== t;

    // if IdxEqS[i].out + IdxEqT[i].out
    // equals 0, then it is not i ≠ s and i ≠ t
    IdxNorST[i] = IsZero();
    IdxNorST[i].in <== IdxEqS[i].out + IdxEqT[i].out;

    // if we are at index s, write in[t]
    // if we are at index t, write in[s]
    // else write in[i]
    branchS[i] <== IdxEqS[i].out * qst.out;
    branchT[i] <== IdxEqT[i].out * qss.out;
    branchNorST[i] <== IdxNorST[i].out * in[i];
    
    // multiply branchS by zero if s equals T
    out[i] <==  (1-sEqT) * (branchS[i]) + branchT[i] + branchNorST[i];
  }
}

Conclusión

Cualquier manipulación de un array en Circom requiere crear un nuevo array y copiar los valores antiguos al nuevo, excepto donde ocurre la actualización.

Al usar este patrón en un bucle, podemos hacer cosas como ordenar una lista, modelar estructuras de datos como pilas y colas, e incluso cambiar el estado de una CPU o VM. Veremos ejemplos de esto en los siguientes capítulos.