zkSNARK实践（三）—— 哈希函数的证明

哈希是一种常用的密码学工具，它可以把一个无限大的数据空间映射到另一个有限的数值空间。由于它的不可逆性，常用来隐藏一些信息。现在我们来分析一下怎么证明这类问题。

有这样一个哈希函数 Y=hash(X)，X是未知数，Y是已知数，prover要向verifier证明他知道X的值，但不能让verifier知道X是多少。

我们知道哈希算法有很多种，并不是所有的哈希算法都适合SNARK。我们把适合SNARK的哈希算法叫 SFH (SNARK-friendly hash)。SFH是专门为SNARK而设计的哈希算法，比传统哈希算法拥有更低的乘法复杂度，常见的SFH有 MiMC/Poseidon等。这里我们来证明一下MIMC哈希函数。

我们先写一个mimc哈希函数

func mimcHash(data []byte) string {
  f := bn254.NewMiMC("seed")
  f.Write(data)
  hash := f.Sum(nil)
  hashInt := big.NewInt(0).SetBytes(hash)
  return hashInt.String()
}

然后定义我们的电路，gnark库已经封装了mimc的电路实现，直接使用即可

type Circuit struct {
  PreImage frontend.Variable
  Hash     frontend.Variable `gnark:",public"`
}

func (circuit *Circuit) Define(curveID ecc.ID, api frontend.API) error {
  mimc, _ := mimc.NewMiMC("seed", curveID, api)
  mimc.Write(circuit.PreImage)
  api.AssertIsEqual(circuit.Hash, mimc.Sum())
  return nil
}

电路定义之后，基本就是套模板了，参考第一篇文章。

完整的代码

https://github.com/liyue201/gnark-examples