协议一：抽样验证：prover向验证证明它知道一个d阶多项式
-
verifier：选取随机数s，发送给prover -
prover：计算h(x) = P(x)/t(x) ，公开p(s) 、h(s)。 -
verifier：验证等式p(s) = t(s) h(s)是否成立
该证明了prover知道一个整除t(x)的多项式，但存在以下问题：
-
prover 知道s，可以计算出t(s), 随机选取h(s) ,并构造p(s) = t(s) h(s) -
prover 知道点(s, t? h?), 可以构造经过该点的任意多项式 -
prover 即使不知道多项式p(x) ,也可以构造多项式p’(x) = t(x) h’(x) 成立
协议二： 同态隐藏
-
verifier
- 选取随机数s，计算
E
(
s
i
)
=
g
s
i
i
=
0
,
.
.
.
,
d
{E(s^i) = g ^{s_i}}_{i=0,...,d}
E(si)=gsi?i=0,...,d? (d为多项式的阶)
- 将
E
(
s
i
)
=
g
s
i
i
=
0
,
.
.
.
,
d
{E(s^i) = g ^{s_i}}_{i=0,...,d}
E(si)=gsi?i=0,...,d?发送给prover
-
prover
- 计算h(x) = P(x)/t(x)
- 使用
E
(
s
i
)
E(s^i)
E(si)和多项式系数c0,…,cd计算
E
(
p
(
s
)
)
=
∏
i
=
0
d
(
g
s
i
)
c
i
E(p(s)) = \prod_{i=0}^{d}{{(g^{s_i})}^{c_i}}
E(p(s))=∏i=0d?(gsi?)ci?
- 同理计算
E
(
h
(
s
)
)
E(h(s))
E(h(s))
- 生成证明{
E
(
p
(
s
)
)
E(p(s))
E(p(s))，
E
(
h
(
s
)
)
E(h(s))
E(h(s)) }
-
verifier
- 验证等式
E
(
p
(
s
)
)
=
(
E
(
h
(
s
)
)
)
t
(
s
)
E(p(s)) = {(E(h(s)))}^{t(s)}
E(p(s))=(E(h(s)))t(s)
该协议解决了随机数s暴露的问题，同时限制了多项式的阶数为d，但无法验证 prover 是否是真的使用了 verifier 提供的值来构造证明
协议三： KCA
-
verifier
- 选取随机数s，
α
\alpha
α，
- 计算
E
(
s
i
)
=
g
s
i
i
=
0
,
.
.
.
,
d
{E(s^i) = g ^{s_i}}_{i=0,...,d}
E(si)=gsi?i=0,...,d? 以及
E
(
α
s
i
)
=
g
α
s
i
i
=
0
,
.
.
.
,
d
{E({\alpha}s^i) = g ^{{\alpha}s_i}}_{i=0,...,d}
E(αsi)=gαsi?i=0,...,d?
- 将
E
(
s
i
)
，
E
(
α
s
i
)
{E(s^i)，E({\alpha}s^i)}
E(si)，E(αsi)发送给prover
-
prover
- 计算h(x) = P(x)/t(x)
- 使用
E
(
s
i
)
，
E
(
α
s
i
)
{E(s^i)，E({\alpha}s^i)}
E(si)，E(αsi)和多项式系数c0,…,cd计算
E
(
p
(
s
)
)
=
∏
i
=
0
d
(
g
s
i
)
c
i
E(p(s)) = \prod_{i=0}^{d}{{(g^{s_i})}^{c_i}}
E(p(s))=∏i=0d?(gsi?)ci? 和
E
(
α
p
(
s
)
)
=
∏
i
=
0
d
(
g
α
s
i
)
c
i
E({\alpha}p(s)) = \prod_{i=0}^{d}{{(g^{{\alpha}s_i})}^{c_i}}
E(αp(s))=∏i=0d?(gαsi?)ci?
- 同理计算
E
(
h
(
s
)
)
E(h(s))
E(h(s))
- 生成证明{
E
(
p
(
s
)
)
E(p(s))
E(p(s))，
E
(
α
p
(
s
)
)
E({\alpha}p(s))
E(αp(s))，
E
(
h
(
s
)
)
E(h(s))
E(h(s)) }
-
verifier
该协议限制了 prover 必须使用verifier提供的值进行构造，但这个协议没有保护prover的知识
协议四： 零知识
-
verifier
- 选取随机数s，
α
\alpha
α，
- 计算
E
(
s
i
)
=
g
s
i
i
=
0
,
.
.
.
,
d
{E(s^i) = g ^{s_i}}_{i=0,...,d}
E(si)=gsi?i=0,...,d? 以及
E
(
α
s
i
)
=
g
α
s
i
i
=
0
,
.
.
.
,
d
{E({\alpha}s^i) = g ^{{\alpha}s_i}}_{i=0,...,d}
E(αsi)=gαsi?i=0,...,d?
- 将
E
(
s
i
)
，
E
(
α
s
i
)
{E(s^i)，E({\alpha}s^i)}
E(si)，E(αsi)发送给prover
-
prover
- 计算h(x) = P(x)/t(x), 选择随机数
δ
\delta
δ
- 使用
E
(
s
i
)
，
E
(
α
s
i
)
{E(s^i)，E({\alpha}s^i)}
E(si)，E(αsi)和多项式系数c0,…,cd计算
E
(
δ
p
(
s
)
)
=
∏
i
=
0
d
(
g
s
i
)
δ
c
i
E({\delta}p(s)) = \prod_{i=0}^{d}{{(g^{s_i})}^{{\delta}c_i}}
E(δp(s))=∏i=0d?(gsi?)δci? 和
E
(
δ
α
p
(
s
)
)
=
∏
i
=
0
d
(
g
α
s
i
)
δ
c
i
E({\delta}{\alpha}p(s)) = \prod_{i=0}^{d}{{(g^{{\alpha}s_i})}^{{\delta}c_i}}
E(δαp(s))=∏i=0d?(gαsi?)δci?
- 同理计算
E
(
δ
h
(
s
)
)
E({\delta}h(s))
E(δh(s))
- 生成证明{
E
(
δ
p
(
s
)
)
E({\delta}p(s))
E(δp(s))，
E
(
δ
α
p
(
s
)
)
E({\delta}{\alpha}p(s))
E(δαp(s))，
E
(
h
(
s
)
)
E(h(s))
E(h(s)) }
-
verifier
-
验证等式
E
(
δ
α
p
(
s
)
)
=
(
E
(
δ
p
(
s
)
)
)
α
E({\delta}{\alpha}p(s)) = {(E({\delta}p(s)))}^{\alpha}
E(δαp(s))=(E(δp(s)))α -
验证等式
E
(
δ
p
(
s
)
)
=
(
E
(
δ
h
(
s
)
)
)
t
(
s
)
E({\delta}p(s)) = {(E({\delta}h(s)))}^{t(s)}
E(δp(s))=(E(δh(s)))t(s)
该协议通过引入
δ
\delta
δ 变换 实现了prover的零知识，但该证明是一个交互式证明，即该证明只对此verifier有效，要想所有的 verifier 都相信该证明，需要构造一个可以被重复使用，公开，可信，又不会被滥用的秘密参数
协议五： 非交互式(多项式的零知识证明)
-
setup
- 选取随机数s，
α
\alpha
α，
- 计算
g
α
g ^{\alpha}
gα、
{
g
s
i
}
i
=
1...
d
\{g^{s^i}\}_{i=1...d}
{gsi}i=1...d?、
{
g
α
s
i
}
i
=
1...
d
\{g^{{\alpha}s^i}\}_{i=1...d}
{gαsi}i=1...d?
- 生成proving key {
{
g
s
i
}
i
=
1...
d
\{g^{s^i}\}_{i=1...d}
{gsi}i=1...d?，
{
g
α
s
i
}
i
=
1...
d
\{g^{{\alpha}s^i}\}_{i=1...d}
{gαsi}i=1...d? }
- 生成verification key {
g
α
g ^{\alpha}
gα，
g
t
(
s
)
g ^{t(s)}
gt(s)}
-
prover
- 计算h(x) = P(x)/t(x)，选择随机数
δ
\delta
δ
- 使用
E
(
s
i
)
，
E
(
α
s
i
)
{E(s^i)，E({\alpha}s^i)}
E(si)，E(αsi)和多项式系数c0,…,cd计算
E
(
δ
p
(
s
)
)
=
∏
i
=
0
d
(
g
s
i
)
δ
c
i
E({\delta}p(s)) = \prod_{i=0}^{d}{{(g^{s_i})}^{{\delta}c_i}}
E(δp(s))=∏i=0d?(gsi?)δci? 和
E
(
δ
α
p
(
s
)
)
=
∏
i
=
0
d
(
g
α
s
i
)
δ
c
i
E({\delta}{\alpha}p(s)) = \prod_{i=0}^{d}{{(g^{{\alpha}s_i})}^{{\delta}c_i}}
E(δαp(s))=∏i=0d?(gαsi?)δci?
- 同理计算
E
(
δ
h
(
s
)
)
E({\delta}h(s))
E(δh(s))
- 生成证明{
E
(
δ
p
(
s
)
)
E({\delta}p(s))
E(δp(s))，
E
(
δ
α
p
(
s
)
)
E({\delta}{\alpha}p(s))
E(δαp(s))，
E
(
h
(
s
)
)
E(h(s))
E(h(s)) }
-
verifier
-
证明简写为{
g
p
,
g
p
′
,
g
h
g^p,g^{p'}, g^h
gp,gp′,gh } -
验证等式
e
(
g
p
′
,
g
)
=
e
(
g
p
,
g
α
)
e(g^{p'}, g) = e(g^p, g^{\alpha})
e(gp′,g)=e(gp,gα) -
验证等式
e
(
g
p
,
g
)
=
e
(
g
t
(
s
)
,
g
h
)
e(g^{p}, g) = e(g^{t(s)}, g^h)
e(gp,g)=e(gt(s),gh)
该协议实现了一个交互式零知识证明，且该证明只对此verifier有效，要想所有的 verifier 都相信该证明，需要构造一个可以被重复使用，公开，可信，又不会被滥用的秘密参数
协议六： 扩展到一般运算(即QAP上的零知识证明)
∑
i
=
0
n
{
(
v
i
?
l
i
(
x
)
)
(
v
i
?
r
i
(
x
)
)
?
(
v
i
?
o
i
(
x
)
)
}
=
t
(
x
)
h
(
x
)
\sum_{i=0}^{n}\{(v_i*l_i(x))(v_i*r_i(x))-(v_i*o_i(x))\}=t(x)h(x)
i=0∑n?{(vi??li?(x))(vi??ri?(x))?(vi??oi?(x))}=t(x)h(x)
-
setup
- 选取随机数s，
α
\alpha
α，
- 计算
g
α
g ^{\alpha}
gα、
{
g
s
k
}
k
=
1...
d
\{g^{s^k}\}_{k=1...d}
{gsk}k=1...d?
- 计算
{
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
i
(
s
)
,
g
α
r
i
(
s
)
,
g
α
o
i
(
s
)
}
i
=
1...
n
\{{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}l_i(s)},g^{{\alpha}r_i(s)},g^{{\alpha}o_i(s)}}\}_{i=1...n}
{gli?(s),gri?(s),goi?(s),gαli?(s),gαri?(s),gαoi?(s)}i=1...n?
- 生成proving key
{
g
s
k
,
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
i
(
s
)
,
g
α
r
i
(
s
)
,
g
α
o
i
(
s
)
}
\{g^{s^k},{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}l_i(s)},g^{{\alpha}r_i(s)},g^{{\alpha}o_i(s)}}\}
{gsk,gli?(s),gri?(s),goi?(s),gαli?(s),gαri?(s),gαoi?(s)}
- 生成verification key {
g
α
g ^{\alpha}
gα，
g
t
(
s
)
g ^{t(s)}
gt(s)}
-
prover
- 计算h(x) = {L(x)*R(x) -O(x)}/t(x)
- 计算
g
L
(
s
)
=
∏
i
=
0
n
(
g
l
i
(
s
)
)
v
i
g^{L(s)} = \prod_{i=0}^{n}{{(g^{l_i(s)})}^{v_i}}
gL(s)=∏i=0n?(gli?(s))vi?,
g
α
L
(
s
)
=
∏
i
=
0
n
(
g
α
l
i
(
s
)
)
v
i
g^{{\alpha}L(s)} = \prod_{i=0}^{n}{{(g^{{\alpha}l_i(s)})}^{v_i}}
gαL(s)=∏i=0n?(gαli?(s))vi? 其中vi为线性组合的解
- 同理计算
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
R
(
s
)
g^{{\alpha}R(s)}
gαR(s),
g
α
O
(
s
)
g^{{\alpha}O(s)}
gαO(s)
- 利用
g
s
k
g^{s^k}
gsk, 计算
g
h
(
s
)
g^{h(s)}
gh(s)
- 生成证明 {
g
h
(
s
)
g^{h(s)}
gh(s),
g
L
(
s
)
g^{L(s)}
gL(s),
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
L
(
s
)
g^{{\alpha}L(s)}
gαL(s),
g
α
R
(
s
)
g^{{\alpha}R(s)}
gαR(s),
g
α
O
(
s
)
g^{{\alpha}O(s)}
gαO(s) }
-
verifier
-
证明简写为 {
g
h
g^{h}
gh,
g
L
g^{L}
gL,
g
R
g^{R}
gR,
g
O
g^{O}
gO,
g
α
L
g^{{\alpha}L}
gαL,
g
α
R
g^{{\alpha}R}
gαR,
g
α
O
g^{{\alpha}O}
gαO } -
验证等式
e
(
g
L
,
g
α
)
=
e
(
g
α
L
,
g
)
e(g^L,g^{\alpha})=e(g^{{\alpha}L},g)
e(gL,gα)=e(gαL,g),
e
(
g
R
,
g
α
)
=
e
(
g
α
R
,
g
)
e(g^R,g^{\alpha})=e(g^{{\alpha}R},g)
e(gR,gα)=e(gαR,g),
e
(
g
O
,
g
α
)
=
e
(
g
α
O
,
g
)
e(g^O,g^{\alpha})=e(g^{{\alpha}O},g)
e(gO,gα)=e(gαO,g) -
验证等式
e
(
g
L
,
g
R
)
=
e
(
g
t
,
g
h
)
e
(
g
O
,
g
)
e(g^L,g^R)=e(g^t,g^h)e(g^O,g)
e(gL,gR)=e(gt,gh)e(gO,g)
该协议实现了一个简单的QAP证明，存在以下两个问题：
协议七： 不可交换性
- setup
- 选取随机数s，
α
l
{\alpha}_l
αl?，
α
r
{\alpha}_r
αr?，
α
o
{\alpha}_o
αo?
- 计算
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?、
{
g
s
k
}
k
=
1...
d
\{g^{s^k}\}_{k=1...d}
{gsk}k=1...d?
- 计算
{
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
}
i
=
1...
n
\{{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)}}\}_{i=1...n}
{gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s)}i=1...n?
- 生成proving key
{
g
s
k
,
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
}
\{g^{s^k},{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)}}\}
{gsk,gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s)}
- 生成verification key {
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?，
g
t
(
s
)
g ^{t(s)}
gt(s)}
- prover
- 计算h(x) = (L(x) · R(x) -O(x))/t(x)
- 计算
g
L
(
s
)
=
∏
i
=
0
n
(
g
l
i
(
s
)
)
v
i
g^{L(s)} = \prod_{i=0}^{n}{{(g^{l_i(s)})}^{v_i}}
gL(s)=∏i=0n?(gli?(s))vi?,
g
α
l
L
(
s
)
=
∏
i
=
0
n
(
g
α
l
l
i
(
s
)
)
v
i
g^{{\alpha}_lL(s)} = \prod_{i=0}^{n}{{(g^{{\alpha}_ll_i(s)})}^{v_i}}
gαl?L(s)=∏i=0n?(gαl?li?(s))vi? 其中vi为线性组合的解
- 同理计算
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s)
- 利用
g
s
k
g^{s^k}
gsk, 计算
g
h
(
s
)
g^{h(s)}
gh(s)
- 生成证明 {
g
h
(
s
)
g^{h(s)}
gh(s),
g
L
(
s
)
g^{L(s)}
gL(s),
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
l
L
(
s
)
g^{{\alpha}_lL(s)}
gαl?L(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s) }
- verifier
- 证明简写为 {
g
h
g^{h}
gh,
g
L
g^{L}
gL,
g
R
g^{R}
gR,
g
O
g^{O}
gO,
g
α
l
L
g^{{\alpha}_lL}
gαl?L,
g
α
r
R
g^{{\alpha}_rR}
gαr?R,
g
α
o
O
g^{{\alpha}_oO}
gαo?O }
- 验证等式
e
(
g
L
,
g
α
l
)
=
e
(
g
α
l
L
,
g
)
e(g^L,g^{{\alpha}_l})=e(g^{{\alpha}_lL},g)
e(gL,gαl?)=e(gαl?L,g),
e
(
g
R
,
g
α
r
)
=
e
(
g
α
r
R
,
g
)
e(g^R,g^{{\alpha}_r})=e(g^{{\alpha}_rR},g)
e(gR,gαr?)=e(gαr?R,g),
e
(
g
O
,
g
α
o
)
=
e
(
g
α
o
O
,
g
)
e(g^O,g^{{\alpha}_o})=e(g^{{\alpha}_oO},g)
e(gO,gαo?)=e(gαo?O,g)
- 验证等式
e
(
g
L
,
g
R
)
=
e
(
g
t
,
g
h
)
e
(
g
O
,
g
)
e(g^L,g^R)=e(g^t,g^h)e(g^O,g)
e(gL,gR)=e(gt,gh)e(gO,g)
该协议对li(s),ri(s),oi(s)使用不同的
α
{\alpha}
α保证了操作数和输出的不可交换性
协议八： 变量一致性
- setup
- 选取随机数s，
α
l
{\alpha}_l
αl?，
α
r
{\alpha}_r
αr?，
α
o
{\alpha}_o
αo?，
β
l
{\beta}_l
βl?，
β
r
{\beta}_r
βr?，
β
o
{\beta}_o
βo?
- 计算
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?、
g
β
l
g ^{{\beta}_l}
gβl?、
g
β
r
g ^{{\beta}_r}
gβr?、
g
β
o
g ^{{\beta}_o}
gβo?、
{
g
s
k
}
k
=
1...
d
\{g^{s^k}\}_{k=1...d}
{gsk}k=1...d?
- 计算
{
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
}
i
=
1...
n
\{{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)}}\}_{i=1...n}
{gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s)}i=1...n?
- 计算
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)}
gβl?li?(s)+βr?ri?(s)+βo?oi?(s)
- 生成proving key
{
g
s
k
,
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
,
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
}
\{g^{s^k},{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)},g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)}}\}
{gsk,gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s),gβl?li?(s)+βr?ri?(s)+βo?oi?(s)}
- 生成verification key {
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?，
g
t
(
s
)
g ^{t(s)}
gt(s),
g
β
l
g ^{{\beta}_l}
gβl?,
g
β
r
g ^{{\beta}_r}
gβr?,
g
β
o
g ^{{\beta}_o}
gβo?}
- prover
- 计算h(x) = (L(x) · R(x) -O(x))/t(x)
- 计算
g
L
(
s
)
=
∏
i
=
0
n
(
g
l
i
(
s
)
)
v
i
g^{L(s)} = \prod_{i=0}^{n}{{(g^{l_i(s)})}^{v_i}}
gL(s)=∏i=0n?(gli?(s))vi?,
g
α
l
L
(
s
)
=
∏
i
=
0
n
(
g
α
l
l
i
(
s
)
)
v
i
g^{{\alpha}_lL(s)} = \prod_{i=0}^{n}{{(g^{{\alpha}_ll_i(s)})}^{v_i}}
gαl?L(s)=∏i=0n?(gαl?li?(s))vi? 其中vi为线性组合的解
- 同理计算
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s)
- 利用
g
s
k
g^{s^k}
gsk, 计算
g
h
(
s
)
g^{h(s)}
gh(s)
- 计算
g
Z
(
s
)
=
∏
i
=
0
n
(
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
)
v
i
g^{Z_(s)} = \prod_{i=0}^{n}{(g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)})^{v_i}}
gZ(?s)=∏i=0n?(gβl?li?(s)+βr?ri?(s)+βo?oi?(s))vi?
- 生成证明 {
g
h
(
s
)
g^{h(s)}
gh(s),
g
L
(
s
)
g^{L(s)}
gL(s),
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
l
L
(
s
)
g^{{\alpha}_lL(s)}
gαl?L(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s), $g^{Z_(s)} $ }
- verifier
- 证明简写为 {
g
h
g^{h}
gh,
g
L
g^{L}
gL,
g
R
g^{R}
gR,
g
O
g^{O}
gO,
g
α
l
L
g^{{\alpha}_lL}
gαl?L,
g
α
r
R
g^{{\alpha}_rR}
gαr?R,
g
α
o
O
g^{{\alpha}_oO}
gαo?O,$g^{Z} $ }
- 验证等式
e
(
g
L
,
g
α
l
)
=
e
(
g
α
l
L
,
g
)
e(g^L,g^{{\alpha}_l})=e(g^{{\alpha}_lL},g)
e(gL,gαl?)=e(gαl?L,g),
e
(
g
R
,
g
α
r
)
=
e
(
g
α
r
R
,
g
)
e(g^R,g^{{\alpha}_r})=e(g^{{\alpha}_rR},g)
e(gR,gαr?)=e(gαr?R,g),
e
(
g
O
,
g
α
o
)
=
e
(
g
α
o
O
,
g
)
e(g^O,g^{{\alpha}_o})=e(g^{{\alpha}_oO},g)
e(gO,gαo?)=e(gαo?O,g)
- 验证等式
e
(
g
L
,
g
β
l
)
?
e
(
g
R
,
g
β
r
)
?
e
(
g
O
,
g
β
o
)
=
e
(
g
Z
,
g
)
e(g^L,g^{{\beta}_l}) ·e(g^R,g^{{\beta}_r}) ·e(g^O,g^{{\beta}_o})=e(g^Z,g)
e(gL,gβl?)?e(gR,gβr?)?e(gO,gβo?)=e(gZ,g)
- 验证等式
e
(
g
L
,
g
R
)
=
e
(
g
t
,
g
h
)
e
(
g
O
,
g
)
e(g^L,g^R)=e(g^t,g^h)e(g^O,g)
e(gL,gR)=e(gt,gh)e(gO,g)
该协议对li(s),ri(s),oi(s)使用不同的
β
{\beta}
β保证了变量的一致性；
通过协议七和协议八分别解决了不可交换性和变量的一致性，但仍然以下问题：
- 多项式的延展性：对于证明中的
g
L
g^{L}
gL ，可以计算
g
L
?
g
5
=
g
L
+
5
g^{L}·g^{5} = g^{L+5}
gL?g5=gL+5，由于知道
g
α
l
g ^{{\alpha}_l}
gαl?,可以计算
g
α
l
L
?
g
α
l
5
=
g
α
l
(
L
+
5
)
g^{{\alpha}_lL}·g^{{\alpha}_l5} = g^{{\alpha}_l(L+5)}
gαl?L?gαl?5=gαl?(L+5),从而
e
(
g
L
+
5
,
g
α
l
)
=
e
(
g
α
l
(
L
+
5
)
,
g
)
e(g^{L+5},g^{{\alpha}_l})=e(g^{{\alpha}_l(L+5)},g)
e(gL+5,gαl?)=e(gαl?(L+5),g) 验证通过
- 变量的延展性： 同理
e
(
g
L
+
5
,
g
β
l
)
?
e
(
g
R
,
g
β
r
)
?
e
(
g
O
,
g
β
o
)
=
e
(
g
Z
?
g
β
l
5
,
g
)
e(g^{L+5},g^{{\beta}_l}) ·e(g^R,g^{{\beta}_r}) ·e(g^O,g^{{\beta}_o})=e(g^Z ·g^{{\beta}_l5},g)
e(gL+5,gβl?)?e(gR,gβr?)?e(gO,gβo?)=e(gZ?gβl?5,g) 可验证通过
协议九： 非延展性
-
setup
- 选取随机数s，
α
l
{\alpha}_l
αl?，
α
r
{\alpha}_r
αr?，
α
o
{\alpha}_o
αo?，
β
l
{\beta}_l
βl?，
β
r
{\beta}_r
βr?，
β
o
{\beta}_o
βo?，
γ
{\gamma}
γ
- 计算
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?、
g
β
l
g ^{{\beta}_l}
gβl?、
g
β
r
g ^{{\beta}_r}
gβr?、
g
β
o
g ^{{\beta}_o}
gβo?、
{
g
s
k
}
k
=
1...
d
\{g^{s^k}\}_{k=1...d}
{gsk}k=1...d?
- 计算
{
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
}
i
=
1...
n
\{{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)}}\}_{i=1...n}
{gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s)}i=1...n?
- 计算
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)}
gβl?li?(s)+βr?ri?(s)+βo?oi?(s)
- 生成proving key
{
g
s
k
,
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
,
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
}
\{g^{s^k},{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)},g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)}}\}
{gsk,gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s),gβl?li?(s)+βr?ri?(s)+βo?oi?(s)}
- 生成verification key {
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?，
g
t
(
s
)
g ^{t(s)}
gt(s),
g
β
l
γ
g ^{{\beta}_l{\gamma}}
gβl?γ,
g
β
r
γ
g ^{{\beta}_r{\gamma}}
gβr?γ,
g
β
o
γ
g ^{{\beta}_o{\gamma}}
gβo?γ，
g
γ
g ^{{\gamma}}
gγ}
-
prover
- 计算h(x) = (L(x) · R(x) -O(x))/t(x)
- 计算
g
L
(
s
)
=
∏
i
=
0
n
(
g
l
i
(
s
)
)
v
i
g^{L(s)} = \prod_{i=0}^{n}{{(g^{l_i(s)})}^{v_i}}
gL(s)=∏i=0n?(gli?(s))vi?,
g
α
l
L
(
s
)
=
∏
i
=
0
n
(
g
α
l
l
i
(
s
)
)
v
i
g^{{\alpha}_lL(s)} = \prod_{i=0}^{n}{{(g^{{\alpha}_ll_i(s)})}^{v_i}}
gαl?L(s)=∏i=0n?(gαl?li?(s))vi? 其中vi为线性组合的解
- 同理计算
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s)
- 利用
g
s
k
g^{s^k}
gsk, 计算
g
h
(
s
)
g^{h(s)}
gh(s)
- 计算
g
Z
(
s
)
=
∏
i
=
0
n
(
g
β
l
l
i
(
s
)
+
β
r
r
i
(
s
)
+
β
o
o
i
(
s
)
)
v
i
g^{Z_(s)} = \prod_{i=0}^{n}{(g^{{\beta}_ll_i(s)+{\beta}_rr_i(s)+{\beta}_oo_i(s)})^{v_i}}
gZ(?s)=∏i=0n?(gβl?li?(s)+βr?ri?(s)+βo?oi?(s))vi?
- 生成证明 {
g
h
(
s
)
g^{h(s)}
gh(s),
g
L
(
s
)
g^{L(s)}
gL(s),
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
l
L
(
s
)
g^{{\alpha}_lL(s)}
gαl?L(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s), $g^{Z_(s)} $ }
-
verifier
-
证明简写为 {
g
h
g^{h}
gh,
g
L
g^{L}
gL,
g
R
g^{R}
gR,
g
O
g^{O}
gO,
g
α
l
L
g^{{\alpha}_lL}
gαl?L,
g
α
r
R
g^{{\alpha}_rR}
gαr?R,
g
α
o
O
g^{{\alpha}_oO}
gαo?O,$g^{Z} $ } -
验证等式
e
(
g
L
,
g
α
l
)
=
e
(
g
α
l
L
,
g
)
e(g^L,g^{{\alpha}_l})=e(g^{{\alpha}_lL},g)
e(gL,gαl?)=e(gαl?L,g),
e
(
g
R
,
g
α
r
)
=
e
(
g
α
r
R
,
g
)
e(g^R,g^{{\alpha}_r})=e(g^{{\alpha}_rR},g)
e(gR,gαr?)=e(gαr?R,g),
e
(
g
O
,
g
α
o
)
=
e
(
g
α
o
O
,
g
)
e(g^O,g^{{\alpha}_o})=e(g^{{\alpha}_oO},g)
e(gO,gαo?)=e(gαo?O,g) -
验证等式
e
(
g
L
,
g
β
l
γ
)
?
e
(
g
R
,
g
β
r
γ
)
?
e
(
g
O
,
g
β
o
γ
)
=
e
(
g
Z
,
g
γ
)
e(g^L,g^{{\beta}_l{\gamma}}) ·e(g^R,g^{{\beta}_r{\gamma}}) ·e(g^O,g^{{\beta}_o{\gamma}})=e(g^Z,g^{\gamma})
e(gL,gβl?γ)?e(gR,gβr?γ)?e(gO,gβo?γ)=e(gZ,gγ) -
验证等式
e
(
g
L
,
g
R
)
=
e
(
g
t
,
g
h
)
e
(
g
O
,
g
)
e(g^L,g^R)=e(g^t,g^h)e(g^O,g)
e(gL,gR)=e(gt,gh)e(gO,g)
协议十： 变量一致性的优化（双线性对运算 和verification key的优化）
- setup
- 选取随机数s，
α
l
{\alpha}_l
αl?，
α
r
{\alpha}_r
αr?，
α
o
{\alpha}_o
αo?，
β
{\beta}
β，
γ
{\gamma}
γ ，
p
l
,
p
r
,
p
o
=
p
l
?
p
r
p_l,p_r, p_o =p_l·p_r
pl?,pr?,po?=pl??pr?
- 设置生成元
g
l
=
g
p
l
g_l= g^{p_l}
gl?=gpl?,
g
r
=
g
p
r
g_r= g^{p_r}
gr?=gpr?,
g
0
=
g
p
o
g_0= g^{p_o}
g0?=gpo?
- 计算
g
l
β
l
i
(
s
)
g_l^{{\beta}l_i(s)}
glβli?(s)?,
g
r
β
r
i
(
s
)
g_r^{{\beta}r_i(s)}
grβri?(s)?,
g
o
β
o
i
(
s
)
g_o^{{\beta}o_i(s)}
goβoi?(s)?
- 计算
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?、
{
g
s
k
}
k
=
1...
d
\{g^{s^k}\}_{k=1...d}
{gsk}k=1...d?
- 计算
{
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
}
i
=
1...
n
\{{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)}}\}_{i=1...n}
{gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s)}i=1...n?
- 生成proving key
{
g
s
k
,
g
l
i
(
s
)
,
g
r
i
(
s
)
,
g
o
i
(
s
)
,
g
α
l
l
i
(
s
)
,
g
α
r
r
i
(
s
)
,
g
α
o
o
i
(
s
)
,
g
l
β
l
i
(
s
)
,
g
r
β
r
i
(
s
)
,
g
o
β
o
i
(
s
)
}
\{g^{s^k},{g^{l_i(s)},g^{r_i(s)},g^{o_i(s)},g^{{\alpha}_ll_i(s)},g^{{\alpha}_rr_i(s)},g^{{\alpha}_oo_i(s)},g_l^{{\beta}l_i(s)}, g_r^{{\beta}r_i(s)},g_o^{{\beta}o_i(s)}}\}
{gsk,gli?(s),gri?(s),goi?(s),gαl?li?(s),gαr?ri?(s),gαo?oi?(s),glβli?(s)?,grβri?(s)?,goβoi?(s)?}
- 生成verification key {
g
α
l
g ^{{\alpha}_l}
gαl?、
g
α
r
g ^{{\alpha}_r}
gαr?、
g
α
o
g ^{{\alpha}_o}
gαo?，
g
o
t
(
s
)
g_o ^{t(s)}
got(s)?,
g
β
γ
g ^{{\beta}{\gamma}}
gβγ，
g
γ
g ^{{\gamma}}
gγ}
- prover
- 计算h(x) = (L(x) · R(x) -O(x))/t(x)
- 计算
g
L
(
s
)
=
∏
i
=
0
n
(
g
l
i
(
s
)
)
v
i
g^{L(s)} = \prod_{i=0}^{n}{{(g^{l_i(s)})}^{v_i}}
gL(s)=∏i=0n?(gli?(s))vi?,
g
α
l
L
(
s
)
=
∏
i
=
0
n
(
g
α
l
l
i
(
s
)
)
v
i
g^{{\alpha}_lL(s)} = \prod_{i=0}^{n}{{(g^{{\alpha}_ll_i(s)})}^{v_i}}
gαl?L(s)=∏i=0n?(gαl?li?(s))vi? 其中vi为线性组合的解
- 同理计算
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s)
- 利用
g
s
k
g^{s^k}
gsk, 计算
g
h
(
s
)
g^{h(s)}
gh(s)
- 计算
g
Z
(
s
)
=
∏
i
=
0
n
(
g
l
β
l
i
(
s
)
?
g
r
β
r
i
(
s
)
?
g
o
β
o
i
(
s
)
)
v
i
g^{Z_(s)} = \prod_{i=0}^{n}{(g_l^{{\beta}l_i(s)}·g_r^{{\beta}r_i(s)}·g_o^{{\beta}o_i(s)})^{v_i}}
gZ(?s)=∏i=0n?(glβli?(s)??grβri?(s)??goβoi?(s)?)vi?
- 生成证明 {
g
h
(
s
)
g^{h(s)}
gh(s),
g
L
(
s
)
g^{L(s)}
gL(s),
g
R
(
s
)
g^{R(s)}
gR(s),
g
O
(
s
)
g^{O(s)}
gO(s),
g
α
l
L
(
s
)
g^{{\alpha}_lL(s)}
gαl?L(s),
g
α
r
R
(
s
)
g^{{\alpha}_rR(s)}
gαr?R(s),
g
α
o
O
(
s
)
g^{{\alpha}_oO(s)}
gαo?O(s), $g^{Z_(s)} $ }
- verifier
- 证明简写为 {
g
h
g^{h}
gh,
g
L
g^{L}
gL,
g
R
g^{R}
gR,
g
O
g^{O}
gO,
g
α
l
L
g^{{\alpha}_lL}
gαl?L,
g
α
r
R
g^{{\alpha}_rR}
gαr?R,
g
α
o
O
g^{{\alpha}_oO}
gαo?O,$g^{Z} $ }
- 多项式的不可变换检查：
e
(
g
L
,
g
α
l
)
=
e
(
g
α
l
L
,
g
)
e(g^L,g^{{\alpha}_l})=e(g^{{\alpha}_lL},g)
e(gL,gαl?)=e(gαl?L,g),
e
(
g
R
,
g
α
r
)
=
e
(
g
α
r
R
,
g
)
e(g^R,g^{{\alpha}_r})=e(g^{{\alpha}_rR},g)
e(gR,gαr?)=e(gαr?R,g),
e
(
g
O
,
g
α
o
)
=
e
(
g
α
o
O
,
g
)
e(g^O,g^{{\alpha}_o})=e(g^{{\alpha}_oO},g)
e(gO,gαo?)=e(gαo?O,g)
- 变量一致性检查
e
(
g
l
L
?
g
r
R
?
g
o
O
,
g
β
γ
)
=
e
(
g
Z
,
g
γ
)
e(g_l^L·g_r^R·g_o^O,g^{{\beta}{\gamma}}) =e(g^Z,g^{\gamma})
e(glL??grR??goO?,gβγ)=e(gZ,gγ)
- 计算有效性检查
e
(
g
l
L
,
g
r
R
)
=
e
(
g
o
t
,
g
h
)
?
e
(
g
o
O
,
g
)
e(g_l^L,g_r^R) =e(g_o^t,g^h)·e(g_o^O,g)
e(glL?,grR?)=e(got?,gh)?e(goO?,g)
|