Un argumento de permutación es una prueba de que dos listas contienen los mismos elementos, pero posiblemente en un orden diferente. Por ejemplo, [2,3,1] es una permutación de [1,2,3] y viceversa.

El argumento de permutación es útil para probar que una lista es una versión ordenada de otra. Es decir, si la lista B tiene los mismos elementos que la lista A y los elementos de B están ordenados, entonces sabemos que el probador (prover) ordenó correctamente A.

Para determinar si dos listas son iguales, típicamente las ordenamos y las comparamos elemento por elemento.

Sin embargo, para saber que una lista está ordenada, necesitamos comprobar que 1) los elementos están en orden y 2) la salida del algoritmo de ordenamiento contiene los mismos elementos que las entradas.

Esto crea una dependencia circular: para saber que una lista es una permutación de la otra, tenemos que saber que sus versiones ordenadas son idénticas. Pero para saber que los algoritmos de ordenamiento se ejecutaron correctamente, tenemos que saber que la salida del ordenamiento es una permutación de la entrada.

Esto no es un problema en el código normal, pero en ZK debemos restringir cada paso de la computación.

Ya hemos mostrado cómo probar que una lista está ordenada. Este capítulo se centra en probar que dos listas son permutaciones la una de la otra.

Opción 1: Escribir restricciones para un algoritmo de ordenamiento

En un capítulo anterior, mostramos cómo escribir restricciones para el algoritmo Selection Sort. El algoritmo Selection Sort se ejecuta en tiempo $\mathcal{O}(n^2)$, por lo que tendrá $\mathcal{O}(n^2)$ restricciones. Podríamos usar un algoritmo más eficiente como merge sort para lograr lo mismo con $\mathcal{O}(n \log n)$ restricciones, pero existen soluciones mejores, como veremos pronto.

Opción 2: Intentar restringir un mapeo 1 a 1 directamente

Uno puede intentar escribir directamente un circuito que se satisfaga si y solo si una lista es una permutación de la otra. En otras palabras, cada elemento de una lista tiene un elemento coincidente en la otra lista y viceversa.

Por ejemplo, para probar que [a1, a2, a3] es una permutación de [b1, b2, b3], necesitamos mostrar un mapeo entre las dos; es suficiente probar que cada a_i se mapea a algún elemento en la lista b y cada b_i se mapea a algún elemento en la lista a.

Para crear un circuito que pruebe el mapeo dual, creamos una matriz de señales s definida de la siguiente manera:

Copy

               b1             b2             b3
    --------------------------------------------
a1 | s11 = (a1-b1)  s12 = (a1-b2)  s12 = (a1-b3)
a2 | s21 = (a2-b1)  s22 = (a2-b2)  s23 = (a2-b3)
a3 | s31 = (a3-b1)  s32 = (a3-b2)  s33 = (a3-b3)

Ten en cuenta que si una señal s es 0, entonces el elemento a y el elemento b correspondientes son iguales. Por ejemplo, si a3 == b1, entonces s31 será 0.

Si luego multiplicamos las señales s por filas y por columnas y restringimos sus productos para que sean señales o como se muestra a continuación, entonces las señales o serán cero si hay al menos un elemento coincidente.

Copy
     b1      b2      b3
a1  s11  ×  s12  ×  s13   =  o_row1
     ×       ×       ×
a2  s21  ×  s22  ×  s23   =  o_row2
     ×       ×       ×
a3  s31  ×  s32  ×  s33   =  o_row3
    ||      ||       ||
    o_col1  o_col2   o_col3

Si restringimos cada una de las señales o para que sea cero, entonces eso también restringe que cada elemento en a tenga al menos un elemento coincidente en b y viceversa. Considera la interpretación de las señales de salida:

• o_row1 es cero si y solo si a1 coincide con un elemento en b.
• o_row2 es cero si y solo si a2 coincide con un elemento en b.
• o_row3 es cero si y solo si a3 coincide con un elemento en b.
• o_col1 es cero si y solo si b1 coincide con un elemento en a.
• o_col2 es cero si y solo si b2 coincide con un elemento en a.
• o_col3 es cero si y solo si b3 coincide con un elemento en a.

Por lo tanto, si todas las señales o son cero, entonces cada elemento de cada lista tiene un elemento coincidente en la otra lista.

La desventaja de este enfoque es que el número de restricciones crece cuadráticamente con la longitud de la lista.

En su lugar, mostramos un método para probar que una lista es una permutación de la otra en tiempo lineal a la longitud de la lista.

Créditos: El resto de este artículo está fuertemente basado en esta documentación de Triton VM, simplemente mostramos una implementación en Circom y añadimos algunas explicaciones más amigables para principiantes.

Cómo funciona el argumento de permutación

Considera un polinomio escrito en la forma:

Su valor no cambia si el orden de la multiplicación cambia:

En otras palabras, permutar la multiplicación de los factores lineales del polinomio no cambia el valor del polinomio. (Un factor lineal es un término de la forma $(x - a)$).

No comprobamos si los polinomios son equivalentes multiplicando algebraicamente los términos. En su lugar, podemos usar una prueba de igualdad de polinomios mucho más eficiente llamada el lema de Schwartz-Zippel.

Esta prueba toma una muestra de un punto aleatorio para $x$ y lo introduce en los dos polinomios. Si tienen la misma evaluación, entonces con una probabilidad extremadamente alta, son el mismo polinomio (para entender por qué esta prueba es segura, por favor consulta el artículo enlazado arriba).

Esta técnica puede usarse para probar que los arrays $[a,b,c]$ y $[b,c,a]$ son permutaciones el uno del otro. Creamos un circuito que toma dos arrays $c_1,c_2,c_3,...,c_n$ y $d_1,d_2,d_3,...,d_n$ como entrada y luego construye los polinomios:

Finalmente, elige un punto aleatorio para $x$, evalúa los dos polinomios y restringe los productos para que sean iguales.

Para generar el punto aleatorio, llamémoslo $r$, usamos el hash de las entradas, es decir, haciendo un hash de la concatenación de los arrays:

De esta manera, el probador no puede intentar “hacer trampa” eligiendo un valor para $r$ donde los polinomios se intersecan. Una vez que el probador ha proporcionado los polinomios, no puede controlar el valor $r$ en el cual se evalúan estos polinomios.

Si el probador cambia los polinomios, el valor $r$ en el que se prueban también cambiará.

El siguiente circuito toma dos listas y comprueba si son permutaciones la una de la otra. La señal de array prodA contiene los términos:

• $\texttt{prodA[0] = } r - a_0$
• $\texttt{prodA[1] = prodA[0]} \cdot(r - a_1)$
• $\texttt{prodA[2] = prodA[1]} \cdot(r - a_2)$
• $\texttt{prodA[n - 1] = prodA[n - 2]}\cdot(r -a_{n-1})$

Así, la entrada final prodA[n - 1] contiene la evaluación del polinomio en r. Aquí, r es hash.out, que es el hash Poseidon de todas las entradas de los arrays a y b.

Copy

include "circomlib/poseidon.circom";

template IsPermutation(n) {
  signal input a[n];
  signal input b[n];

  // the random point will be the hash
  // of the concatenation of the arrays
  component hash = Poseidon(2 * n);
  for (var i = 0; i < n; i++) {
    hash.inputs[i] <== a[i];
    hash.inputs[i + n] <== b[i];
  }

  signal prodA[n];
  signal prodB[n];

  prodA[0] <== hash.out - a[0];
  prodB[0] <== hash.out - b[0];

  for (var i = 1; i < n; i++) {
    prodA[i] <== (hash.out - a[i]) * prodA[i - 1];
    prodB[i] <== (hash.out - b[i]) * prodB[i - 1];
  }

  // the evaluation of the polynomials at r = hash.out
  prodA[n - 1] === prodB[n - 1];
}

component main = IsPermutation(3);

/* INPUT = {
  "a": [1,2,3,4,5,6],
  "b": [1,2,3,4,6,5]
}
*/

Vulnerabilidad: No hacer hash de todos los elementos

Al generar puntos aleatorios de esta manera, el hash debe depender de todas las entradas de la computación. De lo contrario, un probador malicioso puede mantener el valor del hash fijo y ajustar los valores del array de salida hasta encontrar un punto de intersección del polinomio.

Una nota sobre la seguridad

Este algoritmo se basa en que los polinomios no iguales solo se intersecan en como máximo $d$ puntos, donde $d$ es el grado máximo de los dos polinomios. Si el tamaño del campo finito es mucho mayor que $d$, entonces podemos asumir que en la práctica, $p(r)\neq q(r)$ si $p$ y $q$ son polinomios no iguales y $r$ es un punto aleatorio. Circom utiliza un tamaño de campo finito que es ligeramente mayor que $2^{253}$. Si los polinomios tienen un grado de un millón, entonces la probabilidad de que $r$ sea un punto de intersección es aproximadamente $2^{20}/2^{253}$ o $1/2^{233}$ o $1$ en $10^{70}$. Esto es casi del mismo orden de magnitud que el número de átomos en el universo.

Sin embargo, si usáramos un campo finito muy pequeño, digamos del orden de 31 bits, entonces la probabilidad de $p(r)=q(r), q \ne p$ para un $r$ aleatorio no sería insignificante.