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

区块链技术 0 4 月 22, 2024 0 区块链315

上一篇文章我们讲解了如何用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 ![](https://img.learnblockchain.cn/attachments/2021/11/9jjy74dW619611dcc3ea3.jpg)

上一篇文章我们讲解了如何用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 &lt; 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