Circom 中的 MD5 哈希

在本教程中，我们将使用 Circom 实现 MD5 哈希，既可以计算哈希值，也可以在 Circom 中约束其正确计算。

尽管 MD5 哈希函数在密码学上并不安全（因为已经发现了冲突），但其机制与密码学上安全的哈希函数类似。

重要的是，MD5 哈希函数可以快速学习。以下 14 分钟的视频解释了 MD5 哈希的工作原理。我们建议先观看它：

<https://www.youtube.com/watch?v=5MiMK45gkTY>

为了创建一个证明，证明我们知道 MD5 哈希的 preimage 但不泄露它，我们需要证明我们正确执行了哈希的每一步并产生了一定的结果。本教程展示了如何为每个状态转换设计约束。

具体来说，MD5 哈希具有以下子程序：

• 按位 AND、OR、NOT 和 XOR
• LeftRotate
• 加 32 位数字并在 $2^{32}$ 处溢出
• 函数 Func，它使用按位运算符将寄存器 B、C 和 D 组合在一起
• 开始时的填充步骤，在输入后添加 1 位并放入输入的长度（以位为单位）

此外，MD5 的输出通常以 big-endian 形式的 128 位数字书写。假设我们有一个 128 位的值 0x1234567890ABCDEF1122334455667788

在 big-endian 中，它将被写成：

0x12   0x34   0x56   0x78   0x90   0xAB   0xCD   0xEF   0x11   0x22   0x33   0x44   0x55   0x66   0x77   0x88

在 little-endian 中，它将被写成：

0x88   0x77   0x66   0x55   0x44   0x33   0x22   0x11   0xEF   0xCD   0xAB   0x90   0x78   0x56   0x34   0x12

我们将需要一个单独的例程来反转字节的顺序，从 little endian 到 big endian。大多数哈希实现都输出 big endian，因此为了轻松地将我们的结果与已建立的库进行比较，我们希望我们的实现以 big endian 格式输出。我们稍后将为此创建一个 ToBytes 组件。

虽然有大量的数组索引，但我们使用的索引是基于哈希的迭代确定的，因此哈希约束中不需要任何 Quin 选择器——我们可以硬编码数组索引。

在 Python 中构建 MD5 原型

在构建像哈希函数这样复杂的东西时，最好用一种更熟悉且更易于调试的语言（如 Python）构建参考实现，然后将 Python 代码转换为 Circom。

这是 MD5 的 Python 实现（为简单起见，仅支持 448 位的输入）。这在很大程度上受到了 Utkarsh87 的另一个实现 的启发。我们试图使函数的行为“像组件一样”，因此转换为 Circom 更加简单。

一些实现说明：

• 加法模 $2^{32}$ 通过添加数字然后调用函数 Overflow32() 来完成。
• 我们接受输入作为字节数组，而不是作为位数组。
• 字节 0x80 在二进制中看起来像 10000000。这允许我们在输入的末尾用单个位填充输入。
• 输出为 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
    # 请注意，i 将是 1..64（含）
    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
# 连接四个字节以变为 32 位
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
# length 是数据停止的字节
## so if we have zero bytes, we write 0x80
# 因此，如果我们有零字节，我们写入 0x80
## to byte 0
# 到字节 0
def md5(bytes, length):
    data = bytearray(64)
    msg = bytearray(bytes, 'ascii')

    # 56 bytes, 64 is the max
    # 56 字节，64 是最大值
    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
    # data 是一个长度为 64 的字节数组。但是，如果我们将其转换为长度为 16 的 32 位单词数组，则更容易处理
    # 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
    # 算法运行 64 次迭代，使用 4 个寄存器，每个寄存器使用 32 位
    # we allocate 65, because the 0th will be the default starting value
    # 我们分配 65，因为第 0 个将是默认起始值
    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)))

先决条件组件

Overflow32

Overflow32 模拟 VM 中在 $2^{32}$ 发生的 32 位溢出：

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 旋转位，就好像它们在一个循环缓冲区中一样：

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;
}

按位 AND、OR、XOR 和 NOT

以下模板是在我们的 32 位仿真教程中构建的：

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 接受寄存器 B、C 和 D 并将它们组合成一个输出——并且该组合取决于我们正在进行的迭代：

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
    // 上面的 assert 语句必须为 <= 64
    // 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;
    }

输入填充

为了简化，我们的哈希函数接受一个字节数组作为输入，而不是一个位数组。此外，我们将输入长度限制为 56 字节，以便我们可以硬编码在哈希使用的 64 字节（512 位）输入的字节索引 56 处插入长度。

由于输入最多为 56 字节，因此我们必须用于长度的数字不会超过 448 位，这最多需要 2 字节来存储。

// n is the number of bytes
// n 是字节数
template Padding(n) {
    // 56 bytes = 448 bits
    // 56 字节 = 448 位
    assert(n < 56);

    signal input in[n];

    // 64 bytes = 512 bits
    // 64 字节 = 512 位
    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)
    // 添加 128 = 0x80 以填充 1 位 (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

要更改 endianness，我们需要将信号 in 转换为字节数组 out：

// n is the number of bytes
// n 是字节数
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;
    }
}

最终解决方案

下面的代码将所有组件组合在一起以执行 MD5 哈希。它还将结果转换为 big-endian 形式。读者可以在 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
// n 是字节数
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
// n 是字节数
template Padding(n) {
    // 56 bytes = 448 bits
    // 56 字节 = 448 位
    assert(n < 56);

    signal input in[n];

    // 64 bytes = 512 bits
    // 64 字节 = 512 位
    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)
    // 添加 128 = 0x80 以填充 1 位 (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
    // i 必须 < 64 通过上面的断言语句
    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
// n 是字节数
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```markdown
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

ZK友好哈希的动机

上面代码生成的 R1CS 超过五万两千行，如下图所示。有很多机会可以减少电路的大小，特别是不要每次使用字段元素时都将其转换为 32 位数组。

但是，MD5（以及其他现代哈希）中的每个字都是 32 位的，因此与常规代码相比，它需要 32 倍的信号来表示。

在下一章中，我们将学习在原生有限域上运算而不是在 32 位字上运算的哈希，并避免像 XOR 这样代价高昂的操作，XOR 需要将信号分解为位。

• 原文链接： rareskills.io/post/md5-c...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～