admin管理员组文章数量:1529460
1. 引言
本文重点关注基于inner product argument实现的polynomial commitment。
对polynomial
p
(
X
)
∈
F
p
[
X
]
p(X)\in\mathbb{F}_p[X]
p(X)∈Fp[X]进行commit,并需可provably evaluate the committed polynomial at arbitrary points。
最直观的解决方案是:
Prover将多项式的系数都发给Verifier,这需要
O
(
n
)
O(n)
O(n) communication。
而借助polynomial commitment scheme,可实现 O ( log n ) O(\log n) O(logn) communication。
2. Setup
根据参数
d
=
2
k
d=2^k
d=2k,生成common reference string
σ
=
(
G
,
G
⃗
,
H
,
F
p
)
\sigma=(\mathbb{G},\vec{G},H,\mathbb{F}_p)
σ=(G,G
- G \mathbb{G} G为a group of prime order p p p。
-
G
⃗
∈
G
d
\vec{G}\in\mathbb{G}^d
G
∈Gd为a vector of d d d random group elements。 - H ∈ G H\in\mathbb{G} H∈G为a random group element。
- F p \mathbb{F}_p Fp为the finite field of group p p p。
3. Commit
Pedersen vector commitment
C
o
m
m
i
t
Commit
Commit定义为:
C
o
m
m
i
t
(
σ
,
p
(
X
)
;
r
)
=
<
a
⃗
,
G
⃗
>
+
[
r
]
H
Commit(\sigma,p(X);r)=<\vec{a},\vec{G}>+[r]H
Commit(σ,p(X);r)=<a
其中,多项式
p
(
X
)
∈
F
p
[
X
]
p(X)\in\mathbb{F}_p[X]
p(X)∈Fp[X],blinding factor
r
∈
F
p
r\in\mathbb{F}_p
r∈Fp。每个vector元素
a
i
∈
F
p
a_i\in\mathbb{F}_p
ai∈Fp为
p
(
X
)
p(X)
p(X)第
i
i
i项的系数,
p
(
X
)
p(X)
p(X)的最大degree为
d
−
1
d-1
d−1。
4. Open (prover) and OpenVerify (verifier)
改进版的inner product argument用于证明以下关系:
{
(
(
P
,
x
,
v
)
;
(
a
⃗
,
r
)
)
:
P
=
<
a
⃗
,
G
⃗
>
+
[
r
]
H
,
v
=
<
a
⃗
,
b
⃗
>
}
\{((P,x,v);(\vec{a},r)):P=<\vec{a},\vec{G}>+[r]H, v=<\vec{a},\vec{b}>\}
{((P,x,v);(a
其中
b
⃗
=
(
1
,
x
,
x
2
,
⋯
,
x
d
−
1
)
\vec{b}=(1,x,x^2,\cdots,x^{d-1})
b
即,需要Prover向Verifier证明:
the polynomial contained “inside” the commitment
P
P
P evaluates to
v
v
v at
x
x
x,且该committed polynomial的最大degree为
d
−
1
d-1
d−1。
inner product argument需 k = log 2 d k=\log_2d k=log2d轮。仅需知道其最后一轮的输出即可,而不需要中间轮的结果,详细可参看Halo论文第3节内容。
在开始证明之前,Verifier需选择一个随机group element
U
U
U,并将
U
U
U发送给Prover。并从第
k
k
k轮开始,递减到
1
1
1,初始
a
⃗
(
k
)
=
a
⃗
,
G
⃗
(
k
)
=
G
⃗
.
b
⃗
(
k
)
=
b
⃗
\vec{a}^{(k)}=\vec{a},\vec{G}^{(k)}=\vec{G}.\vec{b}^{(k)}=\vec{b}
a
- Prover计算2个值
L
j
,
R
j
L_j,R_j
Lj,Rj:【其中
l
j
,
r
j
l_j,r_j
lj,rj为random blinding factors。
L
j
,
R
j
L_j,R_j
Lj,Rj以"cross-term"形式表达。】
L j = < a ⃗ l o ( j ) , G ⃗ h i ( j ) > + [ l j ] H + [ < a ⃗ l o ( j ) , b ⃗ h i ( j ) > ] U L_j=<\vec{a}_{lo}^{(j)},\vec{G}_{hi}^{(j)}>+[l_j]H+[<\vec{a}_{lo}^{(j)}, \vec{b}_{hi}^{(j)}>]U Lj=<alo(j),G hi(j)>+[lj]H+[<a lo(j),b hi(j)>]U
R j = < a ⃗ h i ( j ) , G ⃗ l o ( j ) > + [ r j ] H + [ < a ⃗ h i ( j ) , b ⃗ l o ( j ) > ] U R_j=<\vec{a}_{hi}^{(j)},\vec{G}_{lo}^{(j)}>+[r_j]H+[<\vec{a}_{hi}^{(j)}, \vec{b}_{lo}^{(j)}>]U Rj=<ahi(j),G lo(j)>+[rj]H+[<a hi(j),b lo(j)>]U - Verifier发送random challenge u j u_j uj。
- Prover使用
u
j
u_j
uj来压缩
a
⃗
(
j
)
\vec{a}^{(j)}
a
(j)的前半部分和后半部分,产生新的vector,其length为原来的一半:
a ⃗ ( j − 1 ) = a ⃗ h i ( j ) ⋅ u j − 1 + a ⃗ l o ( j ) ⋅ u j \vec{a}^{(j-1)}=\vec{a}_{hi}^{(j)}\cdot u_j^{-1}+\vec{a}_{lo}^{(j)}\cdot u_j a(j−1)=a hi(j)⋅uj−1+a lo(j)⋅uj
b ⃗ ( j − 1 ) = b ⃗ l o ( j ) ⋅ u j − 1 + b ⃗ h i ( j ) ⋅ u j \vec{b}^{(j-1)}=\vec{b}_{lo}^{(j)}\cdot u_j^{-1}+\vec{b}_{hi}^{(j)}\cdot u_j b(j−1)=b lo(j)⋅uj−1+b hi(j)⋅uj
G ⃗ ( j − 1 ) = G ⃗ l o ( j ) ⋅ u j − 1 + G ⃗ h i ( j ) ⋅ u j \vec{G}^{(j-1)}=\vec{G}_{lo}^{(j)}\cdot u_j^{-1}+\vec{G}_{hi}^{(j)}\cdot u_j G(j−1)=G lo(j)⋅uj−1+G hi(j)⋅uj -
a
⃗
(
j
−
1
)
,
G
⃗
(
j
−
1
)
,
b
⃗
(
j
−
1
)
\vec{a}^{(j-1)},\vec{G}^{(j-1)},\vec{b}^{(j-1)}
a
(j−1),G (j−1),b (j−1)作为下一轮 j − 1 j-1 j−1的输入,重复以上过程。
最后一轮为
j
=
1
j=1
j=1,剩余的结果为
a
=
a
⃗
(
0
)
,
G
=
G
⃗
(
0
)
,
b
=
b
⃗
(
0
)
a=\vec{a}^{(0)},G=\vec{G}^{(0)},b=\vec{b}^{(0)}
a=a
注意,最终的
G
,
b
G,b
G,b为rearrangements of the publicly known
G
⃗
,
b
⃗
\vec{G},\vec{b}
G
5. Recursion
根据第4节可知,计算
G
G
G需要a length-
2
k
2^k
2k multiexponentiation
<
G
⃗
,
s
⃗
>
<\vec{G},\vec{s}>
<G
G
=
C
o
m
m
i
t
(
σ
,
g
(
X
,
u
1
,
⋯
,
u
k
)
)
G=Commit(\sigma,g(X,u_1,\cdots,u_k))
G=Commit(σ,g(X,u1,⋯,uk))
其中
g
(
X
,
u
1
,
⋯
,
u
k
)
=
∏
i
=
1
k
(
u
i
+
u
i
−
1
X
2
i
−
1
)
g(X,u_1,\cdots,u_k)=\prod_{i=1}^{k}(u_i+u_i^{-1}X^{2^i-1})
g(X,u1,⋯,uk)=∏i=1k(ui+ui−1X2i−1)为a polynomial with degree
2
k
−
1
2^k-1
2k−1。
由于
G
G
G为a commitment,其可被checked in an inner product argument:Verifier circuit可将
G
,
u
1
,
⋯
,
u
k
G,u_1,\cdots,u_k
G,u1,⋯,uk作为public input,使用inner product argument来验证proof
π
\pi
π:即check that
G
=
C
o
m
m
i
t
(
g
(
X
,
u
1
,
⋯
,
u
k
)
)
G=Commit(g(X,u_1,\cdots,u_k))
G=Commit(g(X,u1,⋯,uk)) evaluates at some random point to the expected value for the given challenges
u
1
,
⋯
,
u
k
u_1,\cdots,u_k
u1,⋯,uk。 根据第4节可知,仅需 k = log 2 d k=\log_2d k=log2d轮。在验证完 π \pi π和 G G G之后,the circuit is left with a new G ′ G' G′, along with the u 1 ′ , ⋯ , u k ′ u_1',\cdots,u_k' u1′,⋯,uk′ challenges sampled for the check。为了完全接受 π \pi π为valid的,需perform a linear-time computation of G ′ = < G ⃗ , s ⃗ ′ > G'=<\vec{G},\vec{s}'> G′=<G 这样依次由one proof instance to the next,直到we are satisfied with the size of our batch of proofs。然后最终仅需运行依次linear-time computation,从而decide the validity of the whole batch。 |
根据Halo2中构建的Cycles of curves 可知,可将以上协议基于two-cycle curve来实例化:
- a proof produced by one curve is efficiently verified in the circuit of the other curve。
- 但是,some of these verifier checks can actually be efficiently performed in the native circuit,这些“deferred” to the next native circuit(具体如下图)instead of being immediately passed over to the other curve。
参考资料
[1] Halo2 背景资料之 Polynomial commitment using inner product argument
[2] Halo2 背景资料之 Recursion
本文标签: 学习笔记背景资料Polynomialcommitment
版权声明:本文标题:Halo2 学习笔记——背景资料之Polynomial commitment(6) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1726703576a1081404.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论