Zero-Knowledge Proof，ZKP
零知识证明（Zero-Knowledge Proof，ZKP）是密码学中的一个概念，它允许一方（证明者 Prover）向另一方（验证者 Verifier）证明自己拥有某个信息，但在整个过程中，**证明者并不会暴露任何有关该信息的具体内容。**零知识证明要具备下列三种性质：
完备性（Completeness）
如果一个命题是真的，那么诚实的验证者就能被诚实的证明者说服，相信他们掌握了关于正确输入的知识。
健全性（Soundness）
如果命题是假的，那么任何不诚实的证明者都无法单方面说服诚实的验证者相信他们掌握了关于正确输入的知识。仅有极小机会能说服诚实验证者该事为真。
零知识（zero-knowledge）
若命题为真，那么验证者从证明者那里除了知道命题为真之外，就再也学不到其他东西了。
你可以通过下面的2个小故事来了解基本概念：
How to explain zero-knowledge protocols to your children (wisc.edu)
The Incredible Machine. How Alice Bob and Charlie used the… | by Aviv Zohar | QEDIT | Medium
零知识证明（包括知识证明）的另一种分类方法是交互性即有交互性和非交互性之分。
交互式零知识证明需要证明者和验证者之间进行轮次直接通信
非交互式零知识证明则可以在双方没有任何直接交互的情况下进行验证。
注：非零知识证明的非交互式变体有时也被称为签名方案。
下面为将用Go写一个交互式的零知识证明故事流水
package zkp
import (
"fmt"
"math/rand"
)
var caveMap = `
xxxxxxxxxxxxxxx
xxxxx xxx
xxxx xx
xxx 上 通 道 xx
xx x
xxxxxxxxxxxx xxxxxxxxxx xx
xxxx xx x
洞 口 x xx──门 ──xx xxxxxxxxxxxxxxx
xxxxxxxxxxx x xx
x xx x──门───xxxxxxxxxxxx xxxx
xx xx xxx xx
xx xx xxxxxxx x
xx xxxx x
xxx x
xxx 下 通 道 xxx
xx xxxxxxxxx
xxxxxxxxxxxxxx
`
// 洞穴的两个出口
var exits = []string{"[上]通道", "[下]通道"}
type Role struct {
name string // 名字
exit int // 当前要求或者所在的出口
belief float32 // 相信指数 无限趋近100%
}
func NewRole(name string) *Role {
return &Role{name: name, belief: 0}
}
func (r *Role) ReqExit() (int, string) {
exit := rand.Intn(2)
event := fmt.Sprintf("%s走到洞口大喊:\"你给我从%s出来\"\n", r.name, exits[exit])
fmt.Printf(event)
return exit, event
}
func (r *Role) Hide() string {
enter := rand.Intn(2)
fmt.Printf("%s进入了洞口，偷偷藏进了%s\n", r.name, exits[enter])
r.exit = enter
return fmt.Sprintf("%s进入了洞口\n", r.name)
}
func (r *Role) Leave() string {
event := fmt.Sprintf("%s倒退离开了洞口\n", r.name)
fmt.Printf(event)
return event
}
func (r *Role) Exit(e int) string {
if e != r.exit {
fmt.Printf("%s确认了没人其他人看到和听到他，悄悄的说：\"芝麻开门\"。\n 两个通道中间的门打开了...\n", r.name)
}
event := fmt.Sprintf("%s从%s出来了\n", r.name, exits[e])
fmt.Print(event)
return event
}
func (r *Role) Reaction() {
r.belief = 1 - (1-r.belief)/1.25
fmt.Printf("%s认为对方可以打开门的信任程度达到了%v\n", r.name, r.belief)
}
func ZKP() {
fmt.Println(caveMap)
prover := NewRole(" 精神小伙-张三 ")
verifier := NewRole(" 强盗-李四 ")
fmt.Println(verifier.name + "的团队，想要付费请人打开山洞中的一扇门 ")
fmt.Println(verifier.name + "找到了" + prover.name + "，因为" + prover.name + "说他可以打开门 但是怕强盗们翻脸不认人 要三天后他的好兄弟们到齐后再帮他们打开")
fmt.Println(prover.name + "还保证 不会有第二个强盗团队相信他可以打开这道门")
fmt.Println(verifier.name + "说他的同伙们 明天就要回老家寻找可以打开门的人 等不了那么久")
fmt.Println(prover.name + "表示现在就可以证明自己可以打开山洞中的门")
fmt.Println(" 现在 " + prover.name + "需要在不透露任何知识的情况下 向" + verifier.name + "证明自己可以打开这个门")
fmt.Println(" 与此同时" + verifier.name + "偷偷开起了藏在裤裆大门的GoPro....")
gopro := []string{}
for i := 0; i < 15; i++ {
fmt.Printf("====新的%v次证明===\n", i+1)
gopro = append(gopro, verifier.Leave())
gopro = append(gopro, prover.Hide())
exit, event := verifier.ReqExit()
gopro = append(gopro, event)
gopro = append(gopro, prover.Exit(exit))
verifier.Reaction()
}
fmt.Println("\n\n\n因为" + verifier.name + "明天想回老家的网吧通宵,所以他选择把" + prover.name + "可以开门的消息卖给另一个强盗团伙")
fmt.Printf("====%s以下GoPro拍到的事实====\n", verifier.name)
for _, event := range gopro {
fmt.Printf(event)
}
fmt.Println("============")
fmt.Println(" 另一个强盗团伙A认为" + verifier.name + "和" + prover.name + "串通好了，在演他..")
fmt.Println(" 另一个强盗团伙B说他可以找个人 拍出和录像一模一样的流程 再卖给" + verifier.name + "的老大，然后B就把" + verifier.name + "暴打了一顿...")
fmt.Println(verifier.name + "躺在地上委屈的哭了起来，心想" + prover.name + "真狗啊，他确实做到了 不会有第二个强盗团队相信他可以打开这道门")
fmt.Println(" 也只有" + verifier.name + "相信" + prover.name + "真的可以打开门，因为只有他知道每一次要求的出口确实是随机的")
}
=== RUN TestZKP
xxxxxxxxxxxxxxx
xxxxx xxx
xxxx xx
xxx 上 通 道 xx
xx x
xxxxxxxxxxxx xxxxxxxxxx xx
xxxx xx x
洞 口 x xx──门 ──xx xxxxxxxxxxxxxxx
xxxxxxxxxxx x xx
x xx x──门───xxxxxxxxxxxx xxxx
xx xx xxx xx
xx xx xxxxxxx x
xx xxxx x
xxx x
xxx 下 通 道 xxx
xx xxxxxxxxx
xxxxxxxxxxxxxx
强盗-李四 的团队，想要付费请人打开山洞中的一扇门
强盗-李四 找到了 精神小伙-张三 ，因为 精神小伙-张三 说他可以打开门 但是怕强盗们翻脸不认人 要三天后他的好兄弟们到齐后再帮他们打开
精神小伙-张三 还保证 不会有第二个强盗团队相信他可以打开这道门
强盗-李四 说他的同伙们 明天就要回老家寻找可以打开门的人 等不了那么久
精神小伙-张三 表示现在就可以证明自己可以打开山洞中的门
现在 精神小伙-张三 需要在不透露任何知识的情况下 向 强盗-李四 证明自己可以打开这个门
与此同时 强盗-李四 偷偷开起了藏在裤裆大门的GoPro....
====新的1次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.19999999
====新的2次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.36
====新的3次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.48800004
====新的4次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.59040004
====新的5次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.67232
====新的6次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.73785603
====新的7次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.7902848
====新的8次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.8322278
====新的9次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.86578226
====新的10次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.8926258
====新的11次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.91410065
====新的12次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.9312805
====新的13次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.9450244
====新的14次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[下]通道
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[上]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.9560195
====新的15次证明===
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口，偷偷藏进了[上]通道
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 确认了没人其他人看到和听到他，悄悄的说："芝麻开门"。
两个通道中间的门打开了...
精神小伙-张三 从[下]通道出来了
强盗-李四 认为对方可以打开门的信任程度达到了0.9648156
因为 强盗-李四 明天想回老家的网吧通宵,所以他选择把 精神小伙-张三 可以开门的消息卖给另一个强盗团伙
==== 强盗-李四 以下GoPro拍到的事实====
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[上]通道出来"
精神小伙-张三 从[上]通道出来了
强盗-李四 倒退离开了洞口
精神小伙-张三 进入了洞口
强盗-李四 走到洞口大喊:"你给我从[下]通道出来"
精神小伙-张三 从[下]通道出来了
============
另一个强盗团伙A认为 强盗-李四 和 精神小伙-张三 串通好了，在演他..
另一个强盗团伙B说他可以找个人 拍出和录像一模一样的流程 再卖给 强盗-李四 的老大，然后B就把 强盗-李四 暴打了一顿...
强盗-李四 躺在地上委屈的哭了起来，心想 精神小伙-张三 真狗啊，他确实做到了 不会有第二个强盗团队相信他可以打开这道门
也只有 强盗-李四 相信 精神小伙-张三 真的可以打开门，因为只有他知道每一次要求的出口确实是随机的
--- PASS: TestZKP (0.00s)
PASS
Process finished with the exit code 0
Zero Knowledge Succinct Non-interactive Argument of Knowledge， zk-SNARK
2012 年，亚历山德罗-基耶萨（Alessandro Chiesa）等人开发了 zk-SNARK 协议，它是
Zero Knowledge 零知识的
Succinct 简洁的
Non-interactive 无交互的
Argument of Knowledge 知识证明
zk-SNARKs的首次广泛应用是在Zerocash区块链协议中，零知识密码学提供了计算骨干，通过数学证明一方拥有某些信息，而不透露该信息是什么。 Zcash 利用 zk-SNARKs 来促进四种不同的交易类型：私有交易、屏蔽交易、去屏蔽交易和公开交易。该协议允许用户决定每次交易与公共分类账共享多少数据。 以太坊 zk-Rollups 也利用 zk-SNARKs 来提高可扩展性。
一个 非交互论证系统 由3个算法组成（S,P,V）
• S（C） - 公共参数（Sp, Sv）发送给证明者和验证者
• P使用（Sp,x,w）生成 证明 π （简洁定义 ： 要求π要小）
• V使用（Sv,x,π） 决定 接受或拒绝 。（简洁定义 ： 要求验证过程要快）
| P | Prover 证明者 负责生成证明 |
| V | Verifier 验证者 负责验证提供的证明 |
| w | witness 证明中使用的秘密信息 |
| x | instance 即需要证明的问题实例 |
| π | proof 证明，即由 Prover 生成的证明 |
| Sp | proving key |
| Sv | verification key |
| S | setup 阶段，即非交互式证明系统的初始化过程，生成公共参数。 |
| C | common parameters 通常指整个系统在 setup 阶段生成的可以公开访问的参数，这些参数可能会被 Prover 和 Verifier 同时使用。 |
zk-SNARK不是一个具体算法，如果（S. P.V）是简洁且零知识的，那么我们称它为 zk-SNARK。
生成和验证proof过程背后的大概解释
Trigger warning: math.
Trigger warning: math.
Trigger warning: math.
注意，对于这个过程，我从来没有完全理解的打算，只想建立一种类似程序员思维的理解，比如：
非对称加密很牛 我可以用私钥、公钥加解密 因为离散对数问题是陷门函数性质 只要保存好私钥 就基本无法被逆向
我只需要理解椭圆形加密产生的现象就足以， 然后我可以放心的使用非对称加密技术来构建我的逻辑。
接下来我将带着这种心态来解释 zk-SNARK是如何生成和验证proof，所以内容可能会有误导甚至错误的情况。
首先我们需要将一个验证函数“扁平化” 转化为数学形式，这个数学形式可以表达在w和x的参与下：
验证了w和x的关系
验证的运行过程
现在通过r1cs来理解“数学形式”的转换过程（这里引用并且改写了V神的示例代码）：
（图片引用自：Quadratic Arithmetic Programs: from Zero to Hero）
import ast
from _ast import stmt
import astor
if 'arg' not in dir(ast):
ast.arg = type(None)
def parse(code):
return ast.parse(code).body
# 接受以下形式的代码
# def foo(arg1, arg2 ...):
# x = arg1 + arg2
# y = ...
# return x + y
# 并提取输入和主体，期望主体为一系列
# 变量赋值（变量为不可变；只能设置一次）
# 以及最后的返回语句
def extract_inputs_and_body(code):
o = []
if len(code) != 1 or not isinstance(code[0], ast.FunctionDef):
raise Exception("期待函数声明")
# 收集输入变量列表
inputs = []
for arg in code[0].args.args:
if isinstance(arg, ast.arg):
assert isinstance(arg.arg, str)
inputs.append(arg.arg)
elif isinstance(arg, ast.Name):
inputs.append(arg.id)
else:
raise Exception("无效的参数: %r" % ast.dump(arg))
# 收集主体
body = []
returned = False
for c in code[0].body:
if not isinstance(c, (ast.Assign, ast.Return)):
raise Exception("期待变量赋值或返回")
if returned:
raise Exception("返回语句之后不能执行操作")
if isinstance(c, ast.Return):
returned = True
body.append(c)
return inputs, body
# 将可能包含复杂表达式的主体转换为
# 简单表达式形式，例如 x = y 或 x = y * z
def flatten_body(body):
o = []
for c in body:
o.extend(flatten_stmt(c))
return o
# 生成临时变量
next_symbol = [0]
def mksymbol():
next_symbol[0] += 1
return 'sym_' + str(next_symbol[0])
# “展平”单个语句到一系列简单语句。
# 首先提取目标变量，然后展平表达式
def flatten_stmt(stmt):
# 获取目标变量
if isinstance(stmt, ast.Assign):
assert len(stmt.targets) == 1 and isinstance(stmt.targets[0], ast.Name)
target = stmt.targets[0].id
elif isinstance(stmt, ast.Return):
target = '~out'
# 获取内部内容
return flatten_expr(target, stmt.value)
# 展平表达式的主要方法
def flatten_expr(target, expr):
# x = y
if isinstance(expr, ast.Name):
return [['set', target, expr.id]]
# x = 5
elif isinstance(expr, ast.Num):
return [['set', target, expr.n]]
# x = y (op) z
# 或者，x = y (op) 5
elif isinstance(expr, ast.BinOp):
if isinstance(expr.op, ast.Add):
op = '+'
elif isinstance(expr.op, ast.Mult):
op = '*'
elif isinstance(expr.op, ast.Sub):
op = '-'
elif isinstance(expr.op, ast.Div):
op = '/'
# 幂运算编译为重复乘法，
# 需要常数指数
elif isinstance(expr.op, ast.Pow):
assert isinstance(expr.right, ast.Num)
if expr.right.n == 0:
return [['set', target, 1]]
elif expr.right.n == 1:
return flatten_expr(target, expr.left)
else: # 这可以通过平方乘算法提高效率，尽管这样
if isinstance(expr.left, (ast.Name, ast.Num)):
nxt = base = expr.left.id if isinstance(expr.left, ast.Name) else expr.left.n
o = []
else:
nxt = base = mksymbol()
o = flatten_expr(base, expr.left)
for i in range(1, expr.right.n):
latest = nxt
nxt = target if i == expr.right.n - 1 else mksymbol()
o.append(['*', nxt, latest, base])
return o
else:
raise Exception("错误的操作: " % ast.dump(stmt.op))
# 如果子表达式是变量或数字，则直接包含
if isinstance(expr.left, (ast.Name, ast.Num)):
var1 = expr.left.id if isinstance(expr.left, ast.Name) else expr.left.n
sub1 = []
# 如果子表达式本身是复合表达式，递归
# 应用这种方法到它使用中间变量
else:
var1 = mksymbol()
sub1 = flatten_expr(var1, expr.left)
# 右子表达式同左子表达式处理
if isinstance(expr.right, (ast.Name, ast.Num)):
var2 = expr.right.id if isinstance(expr.right, ast.Name) else expr.right.n
sub2 = []
else:
var2 = mksymbol()
sub2 = flatten_expr(var2, expr.right)
# 最后表达式代表赋值；sub1 和 sub2 代表
# 对子表达式的处理，如果有的话
return sub1 + sub2 + [[op, target, var1, var2]]
else:
raise Exception("意外的语句值: %r" % stmt.value)
# 添加变量或数字到向量之一；如果是变量
# 则与该变量相关的槽设为1，如果是数字
# 则与1相关的槽设为该数字
def insert_var(arr, varz, var, used, reverse=False):
if isinstance(var, str):
if var not in used:
raise Exception("使用未设置的变量！")
arr[varz.index(var)] += (-1 if reverse else 1)
elif isinstance(var, int):
arr[0] += var * (-1 if reverse else 1)
# 映射输入、输出及中间变量到索引
def get_var_placement(inputs, flatcode):
return ['~one'] + [x for x in inputs] + ['~out'] + [c[1] for c in flatcode if c[1] not in inputs and c[1] != '~out']
# 将上面生成的展平代码转换为一阶约束系统
def flatcode_to_r1cs(inputs, flatcode):
varz = get_var_placement(inputs, flatcode)
A, B, C = [], [], []
used = {i: True for i in inputs}
for x in flatcode:
a, b, c = [0] * len(varz), [0] * len(varz), [0] * len(varz)
if x[1] in used:
raise Exception("变量已经使用过了: %r" % x[1])
used[x[1]] = True
if x[0] == 'set':
a[varz.index(x[1])] += 1
insert_var(a, varz, x[2], used, reverse=True)
b[0] = 1
elif x[0] == '+' or x[0] == '-':
c[varz.index(x[1])] = 1
insert_var(a, varz, x[2], used)
insert_var(a, varz, x[3], used, reverse=(x[0] == '-'))
b[0] = 1
elif x[0] == '*':
c[varz.index(x[1])] = 1
insert_var(a, varz, x[2], used)
insert_var(b, varz, x[3], used)
elif x[0] == '/':
insert_var(c, varz, x[2], used)
a[varz.index(x[1])] = 1
insert_var(b, varz, x[3], used)
A.append(a)
B.append(b)
C.append(c)
return A, B, C
# 给定现有输入向量获取变量或数字
def grab_var(varz, assignment, var):
if isinstance(var, str):
return assignment[varz.index(var)]
elif isinstance(var, int):
return var
else:
raise Exception("这是什么表达式? %r" % var)
# 遍历展平代码并完成输入向量
def assign_variables(inputs, input_vars, flatcode):
varz = get_var_placement(inputs, flatcode)
assignment = [0] * len(varz)
assignment[0] = 1
for i, inp in enumerate(input_vars):
assignment[i + 1] = inp
for x in flatcode:
if x[0] == 'set':
assignment[varz.index(x[1])] = grab_var(varz, assignment, x[2])
elif x[0] == '+':
assignment[varz.index(x[1])] = grab_var(varz, assignment, x[2]) + grab_var(varz, assignment, x[3])
elif x[0] == '-':
assignment[varz.index(x[1])] = grab_var(varz, assignment, x[2]) - grab_var(varz, assignment, x[3])
elif x[0] == '*':
assignment[varz.index(x[1])] = grab_var(varz, assignment, x[2]) * grab_var(varz, assignment, x[3])
elif x[0] == '/':
assignment[varz.index(x[1])] = grab_var(varz, assignment, x[2]) / grab_var(varz, assignment, x[3])
return assignment
def code_to_r1cs_with_inputs(code, input_vars):
print('需要扁平化的函数代码：\n', code)
print('\n=====\n')
inputs, body = extract_inputs_and_body(parse(code))
print('函数代码的输入是：\n', inputs)
print('\n=====\n')
# 使用 astor 来还原代码字符串
print("函数代码的body是:")
for node in body:
print(astor.to_source(node).strip())
print('\n=====\n')
flatcode = flatten_body(body)
print('将可能包含复杂表达式的主体转换为简单表达式形式，例如 x = y 或 x = y * z')
print(flatcode)
print('''
sym_1 = x * x
y = sym_1 * x //相当于实现了幂函数y = x**3
sym_2 = y + x
~out = sym_2 + 5
这里的表达式 和 原始代码是等价的
''')
print('\n=====\n')
print('''
R1CS 是由三个向量组成的序列 (a, b, c) ，R1CS 的解是一个向量 s ，其中 s 必须满足等式 s . a * s . b - s . c = 0 ，其中 . 代表点乘
--简单地说，如果我们把 a 和 s "拉在一起"，将两个值乘以相同的位置，
然后求出这些乘积之和，再对 b 和 s 以及 c 和 s 做同样的运算，那么第三个结果就等于前两个结果的乘积。
''')
print('现在我们将数学公式 转为r1cs的形式')
print(get_var_placement(inputs, flatcode))
A, B, C = flatcode_to_r1cs(inputs, flatcode)
print('A')
for x in A: print(x)
print('B')
for x in B: print(x)
print('C')
for x in C: print(x)
print('现在我们带入x的值 求出公式的解 r')
r = assign_variables(inputs, input_vars, flatcode)
print('r')
print(r)
return r, A, B, C
code = """
def qeval(x):
y = x**3
return y + x + 5
"""
r, A, B, C = code_to_r1cs_with_inputs(code, [3])
print('===========')
print("第一个门")
print('a:', A[0])
print('b:', B[0])
print('c:', C[0])
print('''
sym_1 = x * x，即 x*x - sym_1 = 0
那么r1cs的形式是
a: [0, 1, 0, 0, 0, 0]
r: [1, 3, 35, 9, 27, 30]
A = r . a = 3
b: [0, 1, 0, 0, 0, 0]
r: [1, 3, 35, 9, 27, 30]
B = r . b = 3
c: [0, 0, 0, 1, 0, 0]
r: [1, 3, 35, 9, 27, 30]
C = r . c = 9
带入等式 r . a * r . b - r . c = 0
A*B-C=0
3*3-9=0
第一次检查仅仅是为了验证第一个门的输入和输出的一致性。
''')
print('===========')
print("第二个门")
print('a:', A[1])
print('b:', B[1])
print('c:', C[1])
print('''
与第一次点积检验的风格类似，这里我们要检验的是 sym_1 * x = y .
''')
print('===========')
print("第三个门")
print('a:', A[2])
print('b:', B[2])
print('c:', C[2])
print('''
这里我们要检验的是 sym_2 = y + x
因为是加法，这里的模式有些不同：它是将解算向量中的第一个元素乘以第二个元素，再乘以第五个元素，将两个结果相加然后检查总和是否等于第六个元素。
因为解法向量中的第一个元素总是 1，所以这只是一个加法检查，检查输出是否等于两个输入之和。
r: [1, 3, 35, 9, 27, 30]
(1*3)=3
(1*27)=27
27+3 = 30
r[5]=30
30=30
''')
print('===========')
print("第四个门")
print('a:', A[3])
print('b:', B[3])
print('c:', C[3])
print('''
在这里，我们正在评估最后一项校验，即 ~out = sym_2 + 5 。
点乘检查的工作原理是：取解算向量中的第六个元素，与第一个元素相加 5 倍（提醒：第一个元素是 1，因此这实际上意味着相加 5），
然后与第三个元素进行检查，也就是我们存储输出变量的地方。
r: [1, 3, 35, 9, 27, 30]
30+（1*5） = 35
r[2] = 35
35 = 35
''')
print(code)
print('''
r = [1, 3, 35, 9, 27, 30]
这样，我们的 R1CS 就有了四个约束条件。见证是对所有变量的赋值，包括
输入 r[1] = 3
内部变量：r[4] = "y=x**3" = 3*3*3 = 27
输出 r[2] = 35 = "y + x + 5" = 27+3+5 = 35
您只需 "执行 "上面的扁平化代码，从输入变量赋值 x=3 开始，然后输入所有中间变量的值和计算后的输出结果，就可以自己计算出结果。
note：
r[0] 通常代表常量 1，在 R1CS 中，这个常量用于帮助实现和处理不依赖于输入变量的常数项，或当需要在方程中加入常数时使用。
r[3] = 9 是该示例中某个计算过程产生的中间变量。根据前面的描述，r[3] 代表 sym_1 计算结果，即 x * x 的结果。这里 x
''')
这段程序的输出
需要扁平化的函数代码：
def qeval(x):
y = x**3
return y + x + 5
=====
函数代码的输入是：
['x']
=====
函数代码的body是:
y = x ** 3
return y + x + 5
=====
将可能包含复杂表达式的主体转换为简单表达式形式，例如 x = y 或 x = y * z
[['*', 'sym_1', 'x', 'x'], ['*', 'y', 'sym_1', 'x'], ['+', 'sym_2', 'y', 'x'], ['+', '~out', 'sym_2', 5]]
sym_1 = x * x
y = sym_1 * x //相当于实现了幂函数y = x**3
sym_2 = y + x
~out = sym_2 + 5
这里的表达式 和 原始代码是等价的
=====
R1CS 是由三个向量组成的序列 (a, b, c) ，R1CS 的解是一个向量 s ，其中 s 必须满足等式 s . a * s . b - s . c = 0 ，其中 . 代表点乘
--简单地说，如果我们把 a 和 s "拉在一起"，将两个值乘以相同的位置，
然后求出这些乘积之和，再对 b 和 s 以及 c 和 s 做同样的运算，那么第三个结果就等于前两个结果的乘积。
现在我们将数学公式 转为r1cs的形式
['~one', 'x', '~out', 'sym_1', 'y', 'sym_2']
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]
现在我们带入x的值 求出公式的解 r
r
[1, 3, 35, 9, 27, 30]
===========
第一个门
a: [0, 1, 0, 0, 0, 0]
b: [0, 1, 0, 0, 0, 0]
c: [0, 0, 0, 1, 0, 0]
sym_1 = x * x，即 x*x - sym_1 = 0
那么r1cs的形式是
a: [0, 1, 0, 0, 0, 0]
r: [1, 3, 35, 9, 27, 30]
A = r . a = 3
b: [0, 1, 0, 0, 0, 0]
r: [1, 3, 35, 9, 27, 30]
B = r . b = 3
c: [0, 0, 0, 1, 0, 0]
r: [1, 3, 35, 9, 27, 30]
C = r . c = 9
带入等式 r . a * r . b - r . c = 0
A*B-C=0
3*3-9=0
第一次检查仅仅是为了验证第一个门的输入和输出的一致性。
===========
第二个门
a: [0, 0, 0, 1, 0, 0]
b: [0, 1, 0, 0, 0, 0]
c: [0, 0, 0, 0, 1, 0]
与第一次点积检验的风格类似，这里我们要检验的是 sym_1 * x = y .
===========
第三个门
a: [0, 1, 0, 0, 1, 0]
b: [1, 0, 0, 0, 0, 0]
c: [0, 0, 0, 0, 0, 1]
这里我们要检验的是 sym_2 = y + x
因为是加法，这里的模式有些不同：它是将解算向量中的第一个元素乘以第二个元素，再乘以第五个元素，将两个结果相加然后检查总和是否等于第六个元素。
因为解法向量中的第一个元素总是 1，所以这只是一个加法检查，检查输出是否等于两个输入之和。
r: [1, 3, 35, 9, 27, 30]
(1*3)=3
(1*27)=27
27+3 = 30
r[5]=30
30=30
===========
第四个门
a: [5, 0, 0, 0, 0, 1]
b: [1, 0, 0, 0, 0, 0]
c: [0, 0, 1, 0, 0, 0]
在这里，我们正在评估最后一项校验，即 ~out = sym_2 + 5 。
点乘检查的工作原理是：取解算向量中的第六个元素，与第一个元素相加 5 倍（提醒：第一个元素是 1，因此这实际上意味着相加 5），
然后与第三个元素进行检查，也就是我们存储输出变量的地方。
r: [1, 3, 35, 9, 27, 30]
30+（1*5） = 35
r[2] = 35
35 = 35
def qeval(x):
y = x**3
return y + x + 5
r = [1, 3, 35, 9, 27, 30]
这样，我们的 R1CS 就有了四个约束条件。见证是对所有变量的赋值，包括
输入 r[1] = 3
内部变量：r[4] = "y=x**3" = 3*3*3 = 27
输出 r[2] = 35 = "y + x + 5" = 27+3+5 = 35
您只需 "执行 "上面的扁平化代码，从输入变量赋值 x=3 开始，然后输入所有中间变量的值和计算后的输出结果，就可以自己计算出结果。
note：
r[0] 通常代表常量 1，在 R1CS 中，这个常量用于帮助实现和处理不依赖于输入变量的常数项，或当需要在方程中加入常数时使用。
r[3] = 9 是该示例中某个计算过程产生的中间变量。根据前面的描述，r[3] 代表 sym_1 计算结果，即 x * x 的结果。这里 x
假设一个场景，A知道一个数w，B知道一个结果x。A要证明 w**3+w+5 = x，并且不透露w，那么函数的内容就是：
def qeval(w,x):
y = w**3
y2 = y + w + 5
return x - y2
这样在函数过程固定、返回值固定的不变情况下，只要验证return的结果是否为0 就能证明w和x的关系
因为一个一个门的验证太慢了，现实情况中的验证计算量和示例中的计算量差的不止一点点。所以还会将r1cs通过QAP转换为可以加快验证过程的数学形式。
同时还会加入随机数、同态隐藏（加密后还可以进行基础的运算）等方法将w的信息剔除，在实现零知识的同时，还可以完成验证。
结束语
这篇文章只是一个入门人员为了解概念而写的，过程中忽略了非常多关键内容。
数学家简直就是这个世界的魔法师，作为一名“麻瓜”在跳进零知识等兔子洞之前，我无法想象出 “阿里巴巴的山洞故事” 是如何变为一种技术方案来应用。
最后再补充：
区块链其实并不那么匿名，因为公开记账的机制，导致所有人的资金都可以被追踪 然后与现实世界的信息关联并且定位，ZKP非常神奇的解决了“混币器”的中心化信任问题。
其实ZKP最主要的并不是“零知识”，而是它可以减少数据大小和加快验证时间，减少链上的运算负担。