零知识证明友好的哈希函数

ZK-friendly 哈希函数是相比传统密码学哈希函数，需要更少的约束来证明和验证的哈希函数。

像 SHA256 或 keccak256 这样的哈希函数大量使用按位运算符，例如 XOR 或位旋转。证明 XOR 或位旋转的正确执行需要将数字表示为 32 位，这需要 32 个单独的信号。由于传统哈希函数的默认字大小为 32 位，因此对此数据类型的操作需要 32 个信号。

ZK-friendly 哈希函数使用本地字段元素作为默认数据类型，并避免将字段元素分解为位的操作。字段元素的本地操作只有加法和乘法，因此 ZK-friendly 哈希函数操作必须仅使用模加和模乘。

我们关心的哈希函数的属性是：

1. 原像抵抗性（Preimage resistance） —— 给定哈希的输出，计算输入应该是不可行的。
2. 碰撞抵抗性（Collision resistance） —— 给定一个输入-输出对，找到另一个导致相同输出的输入在计算上应该是不可行的。
3. 伪随机性（Pseudorandomness） —— 输出应该看起来是随机的 —— 输入和输出之间不应该存在统计关系。

我们将从高层次描述两种最流行的 ZK-friendly 哈希函数，最小乘法复杂度（Minimal Multiplicative Complexity, MiMC）和 Poseidon 的工作原理。然而，分析它们为何安全不在本文的讨论范围内。事实上，这些哈希函数的安全性——尽管经过了最多的实战检验——在某种程度上仍然是一个悬而未决的问题。

MiMC

此哈希函数的输入是单个字段元素，输出也是单个字段元素。

MiMC 初始化 91 个随机常量并将它们存储在数组 C 中。这些可以以确定性和透明的方式计算，例如取字符串 “MiMC” 并使用 SHA256 对其进行哈希 91 次，并且每个哈希都用作随机数。这些常量是固定的、公开的，并且所有参与者都知道。按照惯例，C[0] = 0。然后，MiMC 接受一个字段元素 t0 作为其输入并迭代计算： $$ let u=k+t_i+Ci \ t{i+1} = i <90 ? u^e: u^e+k $$

其中 e 是某个固定的指数，通常是 3 或 7。k 是一个设置为 0 的常量（稍后将讨论为什么我们提供一个输入 k 只是将其设置为零）。

为了使 MiMC 安全，gcd(e, p - 1) == 1 必须成立，其中 gcd 是最大公约数（greatest common divisor）。对于 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...