zkSNARK实践（一）——多项式方程的证明

zkSNARK全称zero-knowledge Succinct Non-Interactive Arguments of Knowledge，翻译过来叫非交互式简洁零知识证明。网上关于zkSNARK的文章很多，几乎都只讲解它的数学原理。因为它实在太难了，对于大多数像本人一样的学渣来说，理解起来真的很困难。只能隐约的感觉到它是一种很牛逼的技术，具体怎么应用总是一头雾水。所以本系列文章主要通过代码实例阐述zkSNARK，进而理解和体会它的思想精髓。

Groth16

zkSNARK的工程实践有多种方案，比如Groth16，GGPR13、PLORY等，其中Groth16应用最为广泛，包括zcash、filecoin、coda等项目都用到了这个方案。它是由一个叫Groth的大神于2016提出的算法，所以叫Groth16，整个算法流程如图所示：

矩形方块代表实体，紫色圆形代表函数，箭头代表输入输出。

Groth16的步骤如下：

1. 将问题转换成电路描述。
2. 将电路编译 (complie) 成R1CS（一节约束系统）。
3. 任何一方使用Setup生成一些随机的参数，包括 PK (proving key)，VK(verifying key)。
4. 证明者使用函数 Prove 函数生成证明（Proof）。
5. 验证者使用 Verify 函数，验证proof的真假。

前三步是一些初始化的工作，用来生成后面两步需要的参数。

这里面涉及到了大量的数学定理公式，当然这不是我们关心的，这里我们只关心它怎么使用。还是以那个v神文章里的方程来举例。Prover要向Verfier证明他知道方程 x^3+x+5=35 的解，但不能告诉他解是多少。我们将使用go语言的一个开源库gnark，来分析这个问题。

定义电路

我们定义一个结构体，里面有两个变量X和Y，对应上面的方程中的x和35。为了一般化，我们把方程中的35也定义成变量。其中X是私有的，Y是共有的，也就是说X只对Prover可见，Verfier是看不到的。Define函数里面定义了变量的关系，也就是电路的描述。

type Circuit struct {
    X frontend.Variable `gnark:"x"`
    Y frontend.Variable `gnark:",public"`
}

func (circuit *Circuit) Define(curveID ecc.ID, api frontend.API) error {
    x3 := api.Mul(circuit.X, circuit.X, circuit.X)
    api.AssertIsEqual(circuit.Y, api.Add(x3, circuit.X, 5))
    return nil
}

Compile

Compile将电路编译成R1CS，前两个参数都是常数，可以先不管。complie 内部会调用上面的Define函数，将电路的描述转换成真正的电路，然后再转化成R1CS。

var cubicCircuit Circuit
r1cs, _:= frontend.Compile(ecc.BN254, backend.GROTH16, &cubicCircuit)

Setup

Setup就是对上面生成的r1cs生成随机的pk和vk。pk给Prover，vk给Verifier。

pk, vk, _  := groth16.Setup(r1cs)

Prove

Prover知道x和y的值，所以他使用它们作为见证（witness），结合上面的pk，计算出证据（proof）。这个witness包含了私有的输入X和共有的输入Y。

witness := &Circuit{
    X: frontend.Value(3),
    Y: frontend.Value(35),
}
proof, _ := groth16.Prove(r1cs, pk, witness)

Verify

Verifier根据Prover提供的证据(proof)和其他公开参数，验证证据的真实性。Verifier从始至终都不知道x是多少，但如果证验证通过，他就是知道Prover知道x是多少。

publicWitness := &Circuit{
    Y: frontend.Value(35),
}

err = groth16.Verify(proof, vk, publicWitness)
if err != nil {
    fmt.Printf("verification failed\n")
    return
}
fmt.Printf("verification succeded\n")

小结

从这个例子我们对zkSNARK的使用有了大概的印象，基本上就是这些固定的步骤。当然作为一个入门的例子，这个有点简单。而实际应用中，我们遇到的问题比这个要复杂得多。这时我们又该如何解决呢。下一篇文章我们再继续探讨。

完整的代码

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

更多内容请关注公众号