zkSNARK实践（四）—— merkle证明

merkle树在区块中应用非常广泛，比如比特币SPV节点，使用merkle树来验证一笔交易是否在区块中。比如图中，节点18是区块头的merkle树根哈希，节点5是比特币的一笔交易的哈希。要证明节点5在这棵树中，只需提供节点5、4、13、15、14的哈希值即可，不需要所有的叶子节点。我们把验证节点5需要的这几个节点叫做merkle路径。

<img src="https://img.learnblockchain.cn/attachments/2021/12/xwOjE4WY61a9dd6a7fc9f.webp" width = "50%" height = "50%" align=center />

传统的merkle证明有个缺点，即需要向验证者暴露merkle路径哈希。而有时我们希望这些数据是隐私的，这就需要引入零知识证明。gnark已经帮我们实现了merkle路径的验证逻辑电路，这里我们只需定义一下电路。

type merkleCircuit struct {
  RootHash     frontend.Variable `gnark:",public"`
  Path, Helper []frontend.Variable
}

func (circuit *merkleCircuit) Define(curveID ecc.ID, api frontend.API) error {
  hFunc, err := mimc.NewMiMC("seed", curveID, api)
  if err != nil {
    return err
  }
  merkle.VerifyProof(api, hFunc, circuit.RootHash, circuit.Path, circuit.Helper)
  return nil
}

电路的公开输入是merkle树的根即代码中的RootHash，隐私输入是merkle树路径，即Path（路径的哈希）和Helper（路径的描述）。计算merkle哈希这里采用的是MiMC算法，上文我们提到过这是一种SNARK-fiendly算法。

由于代码比较多，就不贴了，完整代码看文章末尾链接。

完整的代码

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