zkSNARK实践（二）——指数方程的证明

上一篇文章我们讲解了如何用zkSNARK证明多项式方程，本文我们将介绍如何使用zkSNARK证明指数方程。

指数方程指的是指数中含有未知数的方程。考虑到这样的指数方程 Y=X^E， 其中X和Y是已知数，E是未知数。prover要向verifier证明他知道问题的解E。比如要证明方程为 59049 = 3^E 的解是10。

因为SANARK的电路只有加法和乘法门，所以对于复杂的运算gnark的api没有相应的实现方法，这就需要我们自己去转换成加法和乘法。我们知道幂运算可以转换成乘法运算，3^E 就是E个3相乘，也就是电路中有E个3输入。但是现在E是未知数，这样的电路没法构建，所以我们需要思考另一种算法。

我们还知道有一种快速求幂的算法叫倍增法。将E转换成二进制之后，迭代倍增。代码如下

package main

import "fmt"

func pow(x, e int) int {
  y := 1
  for p := x; e > 0; e = e >> 1 {
    if e & 1 > 0 {
      y = y * p
    }
    p = p * p
  }
  return y
}

func main()  {
  fmt.Printf("3 ^ 10 = %d\n", pow(3, 10))
}

运行结果

3 ^ 10 = 59049

我们用上面的算法，稍加变通一下。把E限制成固定的位数，这里取8。也就是E表示成电路有8个固定的输入，每个输入就是E的二进制位对应的值。于是可以这样定义电路，代码如下：

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

func (circuit *Circuit) Define(curveID ecc.ID, api frontend.API) error {

  const bitSize = 8
  output := api.Constant(1)
  bits := api.ToBinary(circuit.E, bitSize)
  multiply := circuit.X

  for i := 0; i < len(bits); i++ {
    output = api.Select(bits[i], api.Mul(output, multiply), output)
    multiply = api.Mul(multiply, multiply)
  }
  api.AssertIsEqual(circuit.Y, output)

  return nil
}

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

完整的代码

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