En este tutorial, implementaremos el hash MD5 en Circom tanto para calcular el hash como para restringir en Circom que se haya calculado correctamente.
Aunque la función hash MD5 no es criptográficamente segura (ya que se han encontrado colisiones), la mecánica es similar a la de las funciones hash criptográficamente seguras.
Es importante destacar que la función hash MD5 se puede aprender rápidamente. El siguiente video de 14 minutos explica cómo funciona el hash MD5. Recomendamos verlo primero:
https://www.youtube.com/watch?v=5MiMK45gkTY
Para crear una prueba de que conocemos la preimagen del hash MD5 sin revelarla, necesitamos demostrar que ejecutamos cada paso del hash correctamente y produjimos un resultado determinado. Este tutorial muestra cómo diseñar las restricciones para cada transición de estado.
Específicamente, el hash MD5 tiene las siguientes subrutinas:
- Bitwise AND, OR, NOT y XOR
- LeftRotate
- Suma de números de 32 bits y desbordamiento (overflow) en
- La función
Func, que combina los registrosB,CyDutilizando operadores a nivel de bits - El paso de relleno (padding) al principio, que añade un bit 1 después de la entrada y coloca la longitud (en bits) de la entrada
Además, la salida de MD5 se escribe generalmente como un número de 128 bits en formato big-endian. Supongamos que tenemos un valor de 128 bits 0x1234567890ABCDEF1122334455667788
En big-endian, se escribiría como:
0x12 0x34 0x56 0x78 0x90 0xAB 0xCD 0xEF 0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88
En little-endian, sería:
0x88 0x77 0x66 0x55 0x44 0x33 0x22 0x11 0xEF 0xCD 0xAB 0x90 0x78 0x56 0x34 0x12
Necesitaremos una rutina separada para invertir el orden de los bytes de little endian a big endian. La mayoría de las implementaciones de hash tienen como salida el formato big endian, por lo que para comparar fácilmente nuestro resultado con bibliotecas establecidas, queremos que nuestra implementación tenga la salida en formato big endian. Más adelante crearemos un componente ToBytes para esto.
Aunque hay una cantidad significativa de indexación de arrays, el índice que usamos es determinista y se basa en la iteración del hash, por lo que no hay necesidad de un selector Quin en ninguna parte de las restricciones del hash: podemos fijar directamente en el código (hardcode) la indexación del array.
Construyendo un prototipo de MD5 en Python
Al construir algo tan complejo como una función hash, es una buena idea crear una implementación de referencia en un lenguaje más familiar y más fácil de depurar como Python, para luego traducir el código de Python a Circom.
Aquí está la implementación en Python de MD5 (que por simplicidad solo admite 448 bits de entrada). Está fuertemente inspirada en esta otra implementación de Utkarsh87. Hemos intentado hacer que las funciones se comporten “como componentes”, para que la traducción a Circom sea más directa.
Algunas notas de implementación:
- La suma módulo se realiza sumando los números y luego llamando a la función
Overflow32(). - Aceptamos las entradas como un array de bytes, no como un array de bits.
- El byte
0x80se ve como10000000en binario. Esto nos permite rellenar la entrada con un solo bit al final. - La salida está en formato big-endian.
s = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
K = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391]
iter_to_index = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9]
def Overflow32(x):
return x & 0xFFFFFFFF
def leftRotate(x, amount):
#x &= 0xFFFFFFFF
xo = Overflow32(x)
return Overflow32((xo << amount | xo >> (32 -amount)))
def func(B, C, D, i):
out = None
# note that i will be 1..64 inclusive
if i <= 16:
out = (B & C) | (~B & D)
elif i > 16 and i <= 32:
out = (D & B) | (~D & C)
elif i > 32 and i <= 48:
out = B ^ C ^ D
elif i > 48 and i <= 64:
out = C ^ (B | ~D)
else:
assert False, "1) What"
return out
# concatenates four bytes to become 32 bits
def To32BitWord(byte1, byte2, byte3, byte4):
return byte1 + byte2 * 2**8 + byte3 * 2**16 + byte4 * 2**24
# length is the byte where the data stops
# so if we have zero bytes, we write 0x80
# to byte 0
def md5(bytes, length):
data = bytearray(64)
msg = bytearray(bytes, 'ascii')
# 56 bytes, 64 is the max
assert length < 56, "too long"
if length < 56:
data[length] = 0x80
data[56] = (length * 8).to_bytes(1, byteorder='little')[0]
for i in range(57,64):
data[i] = 0x00
for i in range(0, length):
data[i] = msg[i]
# data is a len 64 array of bytes. However, it will be much easier to work
# on if we turn it into a len 16 array of 32 bit words
data_32 = [0] * 16
for i in range(0, 16):
data_32[i] = To32BitWord(data[4*i], data[4*i + 1], data[4*i + 2], data[4*i + 3])
# algo runs for 64 iterations with 4 registers, each using 32 bits
# we allocate 65, because the 0th will be the default starting value
buffer = [[0]*4 for _ in range(65)]
buffer[0][0] = 0x67452301
buffer[0][1] = 0xefcdab89
buffer[0][2] = 0x98badcfe
buffer[0][3] = 0x10325476
A = 0
B = 1
C = 2
D = 3
for i in range(1, 65):
F = func(buffer[i - 1][B], buffer[i - 1][C], buffer[i - 1][D], i)
G = iter_to_index[i - 1]
to_rotate = buffer[i-1][A] + F + K[i - 1] + data_32[iter_to_index[i - 1]]
rotated = leftRotate(to_rotate, s[i - 1])
new_B = Overflow32(buffer[i-1][B] + rotated)
buffer[i][A] = buffer[i - 1][D]
buffer[i][B] = new_B
buffer[i][C] = buffer[i - 1][B]
buffer[i][D] = buffer[i - 1][C]
final = [0,0,0,0]
for i, b in enumerate(buffer[64]):
final[i] = Overflow32((b + buffer[0][i]))
digest = final[0] + final[1] * 2**32 + final[2] * 2**64 + final[3] * 2**96
raw = digest.to_bytes(16, byteorder='little')
return int.from_bytes(raw, byteorder='big')
print(hex(md5("RareSkills", 10)))
Componentes Prerrequisito
Overflow32
Overflow32 emula un desbordamiento de 32 bits en una VM que ocurre en :
template Overflow32() {
signal input in;
signal output out;
component n2b = Num2Bits(252);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
n2b.out[i] ==> b2n.in[i];
}
b2n.out ==> out;
}
LeftRotate
LeftRotate rota los bits como si estuvieran en un búfer circular:
template LeftRotate(s) {
signal input in;
signal output out;
component n2b = Num2Bits(32);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
b2n.in[(i + s) % 32] <== n2b.out[i];
}
out <== b2n.out;
}
Bitwise AND, OR, XOR y NOT
Las siguientes plantillas (templates) se construyeron en nuestro tutorial sobre emulación de 32 bits:
template BitwiseAnd32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ands[32];
for (var i = 0; i < 32; i++) {
Ands[i] = AND();
Ands[i].a <== n2ba.out[i];
Ands[i].b <== n2bb.out[i];
Ands[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseOr32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ors[32];
for (var i = 0; i < 32; i++) {
Ors[i] = OR();
Ors[i].a <== n2ba.out[i];
Ors[i].b <== n2bb.out[i];
Ors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseXor32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Xors[32];
for (var i = 0; i < 32; i++) {
Xors[i] = XOR();
Xors[i].a <== n2ba.out[i];
Xors[i].b <== n2bb.out[i];
Xors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseNot32() {
signal input in;
signal output out;
// range check
component n2ba = Num2Bits(32);
n2ba.in <== in;
component b2n = Bits2Num(32);
component Nots[32];
for (var i = 0; i < 32; i++) {
Nots[i] = NOT();
Nots[i].in <== n2ba.out[i];
Nots[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
Func
Func toma los registros B, C y D y los combina en una sola salida — y esa combinación depende de en qué iteración nos encontremos:
template Func(i) {
assert(i <= 64);
signal input b;
signal input c;
signal input d;
signal output out;
if (i <= 16) {
signal bAndc;
component a1 = BitwiseAnd32();
a1.in[0] <== b;
a1.in[1] <== c;
component a2 = BitwiseAnd32();
component n1 = BitwiseNot32();
n1.in <== b;
a2.in[0] <== n1.out;
a2.in[1] <== d;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i > 16 && i <= 32) {
component a1 = BitwiseAnd32();
a1.in[0] <== d;
a1.in[1] <== b;
component n1 = BitwiseNot32();
n1.in <== d;
component a2 = BitwiseAnd32();
a2.in[0] <== n1.out;
a2.in[1] <== c;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i > 32 && i <= 48) {
component x1 = BitwiseXor32();
component x2 = BitwiseXor32();
x1.in[0] <== b;
x1.in[1] <== c;
x2.in[0] <== x1.out;
x2.in[1] <== d;
out <== x2.out;
}
// i must be <= 64 by the assert
// statement above
else {
component o1 = BitwiseOr32();
component n1 = BitwiseNot32();
n1.in <== d;
o1.in[0] <== n1.out;
o1.in[1] <== b;
component x1 = BitwiseXor32();
x1.in[0] <== o1.out;
x1.in[1] <==c;
out <== x1.out;
}
Relleno de la entrada (Padding)
Para simplificar, nuestra función hash acepta un array de bytes como entrada, no un array de bits. Además, limitamos la longitud de entrada a 56 bytes para poder fijar en el código (hardcode) la inserción de la longitud en el índice de byte 56 de la entrada de 64 bytes (512 bits) que utiliza el hash.
Dado que la entrada tendrá como máximo 56 bytes, el número que debemos usar para la longitud no será superior a 448 bits, lo que requiere como máximo 2 bytes para almacenarse.
// n is the number of bytes
template Padding(n) {
// 56 bytes = 448 bits
assert(n < 56);
signal input in[n];
// 64 bytes = 512 bits
signal output out[64];
for (var i = 0; i < n; i++) {
out[i] <== in[i];
}
// add 128 = 0x80 to pad the 1 bit (0x80 = 10000000b)
out[n] <== 128;
// pad the rest with zeros
for (var i = n + 1; i < 56; i++) {
out[i] <== 0;
}
var lenBits = n * 8;
if (lenBits < 256) {
out[56] <== lenBits;
}
else {
var lowOrderBytes = lenBits % 256;
var highOrderBytes = lenBits \ 256;
out[56] <== lowOrderBytes;
out[57] <== highOrderBytes;
}
}
Num2Bytes
Para cambiar el orden de los bytes (endianness), necesitamos convertir una señal in en un array de bytes out:
// n is the number of bytes
template ToBytes(n) {
signal input in;
signal output out[n];
component n2b = Num2Bits(n * 8);
n2b.in <== in;
component b2ns[n];
for (var i = 0; i < n; i++) {
b2ns[i] = Bits2Num(8);
for (var j = 0; j < 8; j++) {
b2ns[i].in[j] <== n2b.out[8*i + j];
}
out[i] <== b2ns[i].out;
}
}
Solución Final
El siguiente código combina todos los componentes para realizar el hash MD5. También convierte el resultado al formato big-endian. El lector puede probar el código en zkrepl.
include "circomlib/bitify.circom";
include "circomlib/gates.circom";
template BitwiseAnd32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ands[32];
for (var i = 0; i < 32; i++) {
Ands[i] = AND();
Ands[i].a <== n2ba.out[i];
Ands[i].b <== n2bb.out[i];
Ands[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseOr32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Ors[32];
for (var i = 0; i < 32; i++) {
Ors[i] = OR();
Ors[i].a <== n2ba.out[i];
Ors[i].b <== n2bb.out[i];
Ors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseXor32() {
signal input in[2];
signal output out;
// range check
component n2ba = Num2Bits(32);
component n2bb = Num2Bits(32);
n2ba.in <== in[0];
n2bb.in <== in[1];
component b2n = Bits2Num(32);
component Xors[32];
for (var i = 0; i < 32; i++) {
Xors[i] = XOR();
Xors[i].a <== n2ba.out[i];
Xors[i].b <== n2bb.out[i];
Xors[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
template BitwiseNot32() {
signal input in;
signal output out;
// range check
component n2ba = Num2Bits(32);
n2ba.in <== in;
component b2n = Bits2Num(32);
component Nots[32];
for (var i = 0; i < 32; i++) {
Nots[i] = NOT();
Nots[i].in <== n2ba.out[i];
Nots[i].out ==> b2n.in[i];
}
b2n.out ==> out;
}
// n is the number of bytes
template ToBytes(n) {
signal input in;
signal output out[n];
component n2b = Num2Bits(n * 8);
n2b.in <== in;
component b2ns[n];
for (var i = 0; i < n; i++) {
b2ns[i] = Bits2Num(8);
for (var j = 0; j < 8; j++) {
b2ns[i].in[j] <== n2b.out[8*i + j];
}
out[i] <== b2ns[i].out;
}
}
// n is the number of bytes
template Padding(n) {
// 56 bytes = 448 bits
assert(n < 56);
signal input in[n];
// 64 bytes = 512 bits
signal output out[64];
for (var i = 0; i < n; i++) {
out[i] <== in[i];
}
// add 128 = 0x80 to pad the 1 bit (0x80 = 10000000b)
out[n] <== 128;
// pad the rest with zeros
for (var i = n + 1; i < 56; i++) {
out[i] <== 0;
}
var lenBits = n * 8;
if (lenBits < 256) {
out[56] <== lenBits;
}
else {
var lowOrderBytes = lenBits % 256;
var highOrderBytes = lenBits \ 256;
out[56] <== lowOrderBytes;
out[57] <== highOrderBytes;
}
}
template Overflow32() {
signal input in;
signal output out;
component n2b = Num2Bits(252);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
n2b.out[i] ==> b2n.in[i];
}
b2n.out ==> out;
}
template LeftRotate(s) {
signal input in;
signal output out;
component n2b = Num2Bits(32);
component b2n = Bits2Num(32);
n2b.in <== in;
for (var i = 0; i < 32; i++) {
b2n.in[(i + s) % 32] <== n2b.out[i];
}
out <== b2n.out;
}
template Func(i) {
assert(i <= 64);
signal input b;
signal input c;
signal input d;
signal output out;
if (i < 16) {
component a1 = BitwiseAnd32();
a1.in[0] <== b;
a1.in[1] <== c;
component a2 = BitwiseAnd32();
component n1 = BitwiseNot32();
n1.in <== b;
a2.in[0] <== n1.out;
a2.in[1] <== d;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i >= 16 && i < 32) {
// (D & B) | (~D & C)
component a1 = BitwiseAnd32();
a1.in[0] <== d;
a1.in[1] <== b;
component n1 = BitwiseNot32();
n1.in <== d;
component a2 = BitwiseAnd32();
a2.in[0] <== n1.out;
a2.in[1] <== c;
component o1 = BitwiseOr32();
o1.in[0] <== a1.out;
o1.in[1] <== a2.out;
out <== o1.out;
}
else if (i >= 32 && i < 48) {
component x1 = BitwiseXor32();
component x2 = BitwiseXor32();
x1.in[0] <== b;
x1.in[1] <== c;
x2.in[0] <== x1.out;
x2.in[1] <== d;
out <== x2.out;
}
// i must be < 64 by the assert statement above
else {
component o1 = BitwiseOr32();
component n1 = BitwiseNot32();
n1.in <== d;
o1.in[0] <== n1.out;
o1.in[1] <== b;
component x1 = BitwiseXor32();
x1.in[0] <== o1.out;
x1.in[1] <==c;
out <== x1.out;
}
}
// n is the number of bytes
template MD5(n) {
var s[64] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21];
var K[64] = [0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391];
var iter_to_index[64] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9];
signal input in[n];
signal inp[64];
component Pad = Padding(n);
for (var i = 0; i < n; i++) {
Pad.in[i] <== in[i];
}
for (var i = 0; i < 64; i++) {
Pad.out[i] ==> inp[i];
}
signal data32[16];
for (var i = 0; i < 16; i++) {
data32[i] <== inp[4 * i] + inp[4 * i + 1] * 2**8 + inp[4 * i + 2] * 2**16 + inp[4 * i + 3] * 2**24;
}
var A = 0;
var B = 1;
var C = 2;
var D = 3;
signal buffer[65][4];
buffer[0][A] <== 1732584193;
buffer[0][B] <== 4023233417;
buffer[0][C] <== 2562383102;
buffer[0][D] <== 271733878;
component Funcs[64];
signal toRotates[64];
component SelectInputWords[64];
component LeftRotates[64];
component Overflow32s[64];
component Overflow32s2[64];
for (var i = 0; i < 64; i++) {
Funcs[i] = Func(i);
Funcs[i].b <== buffer[i][B];
Funcs[i].c <== buffer[i][C];
Funcs[i].d <== buffer[i][D];
Overflow32s[i] = Overflow32();
Overflow32s[i].in <== buffer[i][A] + Funcs[i].out + K[i] + data32[iter_to_index[i]];
// rotated = rotate(to_rotate, s[i])
toRotates[i] <== Overflow32s[i].out;
LeftRotates[i] = LeftRotate(s[i]);
LeftRotates[i].in <== toRotates[i];
// new_B = rotated + B
Overflow32s2[i] = Overflow32();
Overflow32s2[i].in <== LeftRotates[i].out + buffer[i][B];
// store into the next state
buffer[i + 1][A] <== buffer[i][D];
buffer[i + 1][B] <== Overflow32s2[i].out;
buffer[i + 1][C] <== buffer[i][B];
buffer[i + 1][D] <== buffer[i][C];
}
component addA = Overflow32();
component addB = Overflow32();
component addC = Overflow32();
component addD = Overflow32();
// we hardcode initial state because we only
// process one 512 bit block
addA.in <== 1732584193 + buffer[64][A];
addB.in <== 4023233417 + buffer[64][B];
addC.in <== 2562383102 + buffer[64][C];
addD.in <== 271733878 + buffer[64][D];
signal littleEndianMd5;
littleEndianMd5 <== addA.out + addB.out * 2**32 + addC.out * 2**64 + addD.out * 2**96;
// convert the answer to bytes and reverse
// the bytes order to make it big endian
component Tb = ToBytes(16);
Tb.in <== littleEndianMd5;
// sum the bytes in reverse
var acc;
for (var i = 0; i < 16; i++) {
acc += Tb.out[15 - i] * 2**(i * 8);
}
signal output out;
out <== acc;
}
component main = MD5(10);
// The result out =
// "RareSkills" in ascii to decimal
/* INPUT = {"in": [82, 97, 114, 101, 83, 107, 105, 108, 108, 115]} */
// The result is 246193259845151292174181299259247598493
// The MD5 hash of "RareSkills" is 0xb93718dd21d2f5081239d7a16cf69b9d when converted to decimal is 246193259845151292174181299259247598493
Motivación para los hashes amigables con ZK (ZK-friendly)
El R1CS producido por el código anterior tiene más de cincuenta y dos mil filas de longitud, como se resalta en la figura a continuación. Hay muchas oportunidades para reducir el tamaño del circuito, especialmente al no convertir los elementos de campo a arrays de 32 bits cada vez que los usamos.
Sin embargo, cada palabra en un MD5 (y en otros hashes modernos) es de 32 bits, por lo que requerirá 32 veces más señales para representarse en comparación con el código regular.
En el siguiente capítulo, aprenderemos sobre hashes que operan en el campo finito nativo en lugar de palabras de 32 bits y evitan operaciones costosas como XOR, que requieren descomponer las señales en bits.