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
}
电路定义之后,基本就是套模板了,参考上一篇文章。
完整的代码
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!