ZK 友好型哈希函数是指在证明和验证过程中，所需约束数量比传统密码学哈希函数少得多的哈希函数。
像 SHA256 或 keccak256 这样的哈希函数大量使用按位运算符，例如 XOR 或位旋转。证明 XOR 或位旋转的正确执行需要将数字表示为 32 位，这就需要 32 个独立的信号。由于传统哈希函数的默认字长是 32 位，对该数据类型的运算就需要 32 个信号。
ZK 友好型哈希函数使用原生域元素（field element）作为默认数据类型，并避免将域元素分解为位的操作。域元素上的原生运算只有加法和乘法，因此 ZK 友好型哈希函数的操作必须仅使用模加和模乘。
我们关心的哈希函数属性包括：
- 抗原像性（Preimage resistance） — 给定哈希输出，计算出输入在计算上应该是不可行的。
- 抗碰撞性（Collision resistance） — 给定一对输入和输出，寻找另一个能产生相同输出的输入在计算上应该是不可行的。
- 伪随机性（Pseudorandomness） — 输出看起来应该是随机的，即输入和输出之间不应存在统计学上的关联。
我们将从高层次上描述目前最流行的两种 ZK 友好型哈希函数：Minimal Multiplicative Complexity (MiMC) 和 Poseidon 的工作原理。然而，对它们为何安全的分析超出了本文的范围。事实上，这些哈希函数的安全性——尽管经过了极其严格的实战检验——在某种程度上仍然是一个未解之谜（open question）。
MiMC
该哈希函数的输入是一个单一的域元素，输出也是一个单一的域元素。
MiMC 会初始化 91 个随机常量，并将它们存储在一个数组 C 中。这些常量可以通过确定且透明的方式计算得出，例如取字符串 “MiMC” 并使用 SHA256 对其进行 91 次哈希计算，每次得到的哈希值作为一个随机数。这些常量是固定的、公开的，并且为所有参与方所知。按照惯例，C[0] = 0。然后，MiMC 接受一个域元素 作为输入并进行迭代计算：
其中 是一些固定的指数，通常是 3 或 7。 是一个被设置为 0 的常量（为什么我们提供一个输入 却只将其设置为 0，稍后会进行讨论）。
为了保证 MiMC 的安全性，必须满足 gcd(e, p - 1) == 1，其中 gcd 是最大公约数。对于 Circom 的默认域大小，gcd(3, p - 1) ≠ 1，但 gcd(7, p - 1) = 1。
from math import gcd
p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
gcd(3, p - 1)
# 3
gcd(7, p - 1)
# 1
因此，Circomlib 提供了 MiMC7 作为哈希算法（其中 7 为指数）。话虽如此，使用其他域大小的库可能会使用 e = 3（要了解为什么会这样，请参阅文章末尾链接的资源）。
以下是使用单个输入的 MiMC7 的最小化示例：
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;
}
如果我们希望将多个域元素传递给哈希并输出单个域元素，我们可以使用以下方法：
- 我们对第一个输入元素进行哈希处理。
- 该哈希的输出将成为下一个哈希的
k值。 - 下一个哈希的输入是原输入的下一部分。
这可以通过以下图示来直观理解：
MultiMiMC7 模板为我们实现了这一点：
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 与 MiMC 类似，不同之处在于它增加了一步矩阵乘法。也就是说，如果输入是单个元素，它会被扩展为 [0, input]，并且该向量会乘以一系列经过精心调整的 2 x 2 矩阵。这里的“精心调整”是指它具有某种密码学特性，我们在此不作深入探讨。
因此，与单元素经历一系列加法和求幂（如在 MiMC 中）不同，在 Poseidon 中，是一个向量经历一系列逐元素加法、矩阵乘法（这会产生相同维度的向量）和求幂。
虽然矩阵乘法增加了更多的约束，但它在哈希中产生了更多的“分散性（dispersion）”，因此 Poseidon 不需要像 MiMC 那样进行那么多轮的计算。
以下是使用单个输入的 Poseidon 的最小化示例：
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]
} */
要使用多个输入信号（signal），我们可以将 Poseidon 的模板参数 n 更改为所需的值，并提供大小正确的数组。
Poseidon vs MiMC Performance
对于单输入的哈希，MiMC 的底层 R1CS 具有 364 个约束：
而 Poseidon 有 213 个：
现在，我们来比较一下有两个输入时所生成的约束数量。
对于 MiMC7，有两个输入时约束数量会翻倍：
但对于 Poseidon 来说，约束数量几乎没有增加：
这种卓越性能的主要原因是：与 MiMC 不同，Poseidon 不会对输入中的每个域元素重新进行哈希计算。相反，为了对更大的输入进行哈希，它会使用一个更大的矩阵来与输入向量相乘。Circomlib 的 Poseidon 不支持大于 17 个域元素的输入。如果我们需要对大型数据集进行哈希处理，这可能会成为一个问题。然而，如果我们正在构建 Merkle 树，我们只需要对两个输入进行哈希计算即可。
Seeking even more security
如前所述，Poseidon 和 MiMC 的安全性尚不如 SHA-256 等经过高度实战检验的哈希函数那样被透彻理解。
目前存在一种基于椭圆曲线、安全假设比 Poseidon 和 MiMC 更强的 ZK 友好型哈希函数。人们普遍认为，在没有量子计算机的情况下，计算椭圆曲线点的离散对数是不可行的。Pedersen 哈希是一种 ZK 友好型哈希函数，它使用椭圆曲线运算作为计算哈希的核心子程序。在电路中进行椭圆曲线算术运算不如 Poseidon 或 MiMC 高效，但它仍比传统的密码学哈希函数更高效。
Bounties on MiMC and Poseidon Bugs
目前，Ethereum Foundation 提供了一项 $20,000 的赏金，用于寻找本文所述 MiMC 哈希变体的哈希碰撞。
Ethereum Foundation 目前也正在通过 Poseidon Cryptanalysis Initiative 资助针对 Poseidon 安全性的研究。Ethereum 的创始人已表示，Ethereum 可能会转而使用 Poseidon 作为 Ethereum 的首选哈希函数，以使得使用 ZK 证明网络状态变得更加容易。
Acknowledgement
在撰写本文时，参考了来自 Risc Zero 的以下资源：