zkSNARK实践(二)——指数方程的证明

  • stirlingx
  • 更新于 2021-11-19 15:40
  • 阅读 3359

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

点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
stirlingx
stirlingx
0x7690...f836
江湖只有他的大名,没有他的介绍。