Las funciones hash amigables con ZK son funciones hash que requieren muchas menos restricciones para probarse y verificarse que las funciones hash criptográficas tradicionales.
Funciones hash como SHA256 o keccak256 hacen un uso intensivo de operadores a nivel de bits como XOR o la rotación de bits. Probar la correcta ejecución de XOR o la rotación de bits requiere representar el número como 32 bits, lo que requiere 32 señales separadas. Dado que el tamaño de palabra predeterminado de las funciones hash tradicionales es de 32 bits, las operaciones en este tipo de datos requieren 32 señales.
Una función hash amigable con ZK utiliza el elemento de campo nativo como tipo de datos predeterminado y evita las operaciones que descomponen el elemento de campo en bits. Las operaciones nativas en los elementos de campo son solo la suma y la multiplicación, por lo que las operaciones de la función hash amigable con ZK deben utilizar únicamente la suma y la multiplicación modular.
Las propiedades de una función hash que nos interesan son:
- Resistencia a la preimagen — dada la salida de un hash, calcular la entrada debería ser inviable.
- Resistencia a colisiones — dado un par de entrada-salida, debería ser computacionalmente inviable encontrar otra entrada que produzca la misma salida.
- Pseudoaleatoriedad — la salida debería parecer aleatoria — no debería haber ninguna relación estadística entre la entrada y la salida.
Describiremos a alto nivel cómo funcionan dos de las funciones hash amigables con ZK más populares, Minimal Multiplicative Complexity (MiMC) y Poseidon. Sin embargo, un análisis de por qué son seguras está fuera del alcance de este artículo. De hecho, la seguridad de estas funciones hash — a pesar de ser las más probadas en batalla — sigue siendo en cierto modo una cuestión abierta.
MiMC
La entrada a esta función hash es un solo elemento de campo y la salida es un solo elemento de campo.
MiMC inicializa 91 constantes aleatorias y las almacena en un arreglo C. Estas podrían calcularse de manera determinista y transparente, como por ejemplo tomando la cadena “MiMC” y aplicando el hash 91 veces con SHA256, y cada hash sirve como número aleatorio. Estas constantes son fijas, públicas y conocidas por todas las partes. Convencionalmente, C[0] = 0. Luego, MiMC toma un elemento de campo como su entrada y calcula iterativamente:
donde es un exponente fijo, a menudo 3 o 7. es una constante que se establece en 0 (la razón por la que proporcionamos una entrada solo para establecerla en cero se discutirá más adelante).
Para que MiMC sea seguro, debe cumplirse que gcd(e, p - 1) == 1, donde gcd es el máximo común divisor. Para el tamaño de campo predeterminado de Circom, gcd(3, p - 1) ≠ 1 pero gcd(7, p - 1) = 1.
from math import gcd
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
gcd(3, p - 1)
# 3
gcd(7, p - 1)
# 1
Por lo tanto, Circomlib proporciona MiMC7 como un hash (donde 7 es el exponente). Dicho esto, las bibliotecas que utilizan otros tamaños de campo podrían usar e = 3 (para entender por qué ocurre esto, consulte el recurso enlazado al final del artículo).
A continuación se muestra un ejemplo mínimo de uso de MiMC7 con una sola entrada:
include "circomlib/mimc.circom";
template ExampleMiMC() {
signal input a;
signal output out;
component hash = MiMC7(91);
hash.x_in <== a;
hash.k <== 0;
out <== hash.out;
}
Si deseamos pasar múltiples elementos de campo al hash y generar un solo elemento de campo como salida, utilizamos el siguiente enfoque:
- Aplicamos el hash al primer elemento de entrada.
- La salida de ese hash se convierte en el valor de
kpara el siguiente hash. - La entrada del siguiente hash es la siguiente parte de la entrada.
Esto se puede visualizar de la siguiente manera:
La plantilla MultiMiMC7 logra esto por nosotros:
include "circomlib/mimc.circom";
template ExampleMultiMiMC(n) {
signal input in[n];
signal output out;
component hash = MultiMiMC7(n, 91);
for (var i = 0; i < n; i++) {
hash.in[i] <== in[i];
}
hash.k <== 0;
out <== hash.out;
}
Poseidon
Poseidon es similar a MiMC, excepto que agrega un paso de multiplicación de matrices. Es decir, si la entrada es un solo elemento, se expande a [0, input], y este vector se multiplica por una serie de matrices de 2 x 2 cuidadosamente ajustadas. “Ajuste cuidadoso” aquí significa que tiene una cierta propiedad criptográfica en la que no profundizaremos aquí.
Por lo tanto, en lugar de que un solo elemento pase por una serie de sumas y exponenciaciones (como en MiMC), en Poseidon un vector pasa por una serie de sumas elemento por elemento, multiplicaciones de matrices (que producen un vector de la misma dimensión) y exponenciaciones.
Aunque la multiplicación de matrices añade más restricciones, crea más “dispersión” en el hash, por lo que Poseidon no necesita tantas rondas como MiMC.
A continuación se muestra un ejemplo mínimo de uso de Poseidon con una sola entrada:
include "circomlib/poseidon.circom";
template Example(n) {
signal input in[n];
signal output out;
component hash = Poseidon(n);
for (var i = 0; i < n; i++) {
hash.inputs[0] <== in[i];
}
out <== hash.out;
}
component main = Example(1);
/* INPUT = {
"in": [5]
} */
Para utilizar más de una señal de entrada, cambiamos el argumento de plantilla n para Poseidon al valor deseado y proporcionamos el arreglo del tamaño correcto.
Rendimiento de Poseidon vs MiMC
Para los hashes que toman una sola entrada, el R1CS subyacente de MiMC tiene 364 restricciones:
mientras que Poseidon tiene 213:
Ahora, comparemos el número de restricciones generadas cuando tenemos dos entradas.
Para MiMC7, el número de restricciones se duplica con dos entradas:
Pero para Poseidon, el número de restricciones apenas aumenta:
La razón principal de este rendimiento superior es que, a diferencia de MiMC, Poseidon no rehace el hash para cada elemento de campo en la entrada. En su lugar, para aplicar el hash a una entrada más grande, utiliza una matriz más grande para multiplicar el vector de entrada. El Poseidon de Circomlib no admite entradas mayores a 17 elementos de campo. Si necesitamos aplicar un hash a un conjunto de datos grande, esto puede ser problemático. Sin embargo, si estamos construyendo un árbol de Merkle, solo necesitamos aplicar el hash a dos entradas.
En busca de aún más seguridad
Como se mencionó anteriormente, las propiedades de seguridad de Poseidon y MiMC no se comprenden tan bien como las de funciones hash altamente probadas en batalla como SHA-256.
Existe una función hash amigable con ZK con suposiciones de seguridad aún más fuertes que Poseidon y MiMC, la cual está basada en curvas elípticas. Se cree ampliamente que calcular el logaritmo discreto de puntos de una curva elíptica es inviable sin una computadora cuántica. El hash de Pedersen es una función hash amigable con ZK que utiliza operaciones de curva elíptica como subrutina central para calcular el hash. Realizar aritmética de curva elíptica en un circuito no será tan eficiente como Poseidon o MiMC, pero es más eficiente que los hashes criptográficos tradicionales.
Recompensas por Errores en MiMC y Poseidon
Actualmente, la Ethereum Foundation ofrece una recompensa de $20,000 por encontrar una colisión de hash en una variante del hash MiMC descrito en este artículo.
La Ethereum Foundation también apoya financieramente en la actualidad la investigación sobre la seguridad de Poseidon a través de la Poseidon Cryptanalysis Initiative. El fundador de Ethereum ha indicado que Ethereum podría cambiar a usar Poseidon como la función hash de elección para Ethereum con el fin de hacer que el estado de la red sea más fácil de probar utilizando ZK.
Agradecimientos
Se consultó el siguiente recurso de Risc Zero durante la creación de este artículo: