多项式承诺是一种方案, 它允许你对一个多项式(即对其系数)做出承诺. 之后, 有人可以要求你在某个点上对多项式进行求值并给出结果, 你可以做到这一点, 同时还能提供正确求值的证明.
承诺应具有 hiding 和 binding 属性. 同时具有一定的同态属性(如基于 pairing 的承诺具有乘法同态属性; 基于 DLG 的承诺具有加法同态属性).
Binding: 不存在 m ′ ≠ m m' \not = m m ′ = m , 使得 Commit ( m , r ) = Commit ( m ′ , r ′ ) \text{Commit}(m, r) = \text{Commit}(m', r') Commit ( m , r ) = Commit ( m ′ , r ′ ) .
Hiding: 对于随机数集合 R \mathbb{R} R , Commit ( m , R ) ≡ Commit ( m ′ , R ) \text{Commit}(m, \mathbb{R}) \equiv \text{Commit}(m', \mathbb{R}) Commit ( m , R ) ≡ Commit ( m ′ , R ) . 即承诺 Commit ( m , r ) \text{Commit}(m, r) Commit ( m , r ) 也不会泄露 m m m 的任何信息.
多项式承诺中包含的3个主要算法为:
Commit
Open
Verify
Pedersen hashing and commitments
简单的非隐藏承诺: Pedersen hash. 要对单个值 x x x 进行承诺, 只需计算 x G xG x G , 其中 G G G 的离散对数是未知的. 要打开承诺, 只需揭示值 x.
使用 Pedersen hash 可以进行多重承诺. 对于一个值的向量 ( x 1 , ⋯ , x k ) (x_{1}, \cdots, x_{k}) ( x 1 , ⋯ , x k ) , 可以通过计算 x 1 G 1 + ⋯ + x k G k x_{1}G_{1} + \cdots + x_{k}G_{k} x 1 G 1 + ⋯ + x k G k 来实现多重承诺. 其中每个 G i G_{i} G i 都是不同的, 并且也具有未知的离散对数. 通常会将最后这个公式简化表示为内积 < x ⃗ , G ⃗ > <\vec{x}, \vec{G}> < x , G > , 这里 x ⃗ = ( x 1 , ⋯ , x k ) \vec{x} = (x_{1}, \cdots, x_{k}) x = ( x 1 , ⋯ , x k ) , G ⃗ = ( G 1 , ⋯ , G k ) \vec{G} = (G_{1}, \cdots, G_{k}) G = ( G 1 , ⋯ , G k ) . 要揭示这个承诺, 只需揭示出值 x i x_{i} x i .
Pedersen hash 承诺是非隐藏但具有绑定性的, 因为你不能将它们打开为与最初承诺不同的值. 同时将 x x x 和 y y y 的承诺相加会得到 x + y x + y x + y 的承诺: x G + y G = ( x + y ) G xG + yG = (x + y)G x G + y G = ( x + y ) G , 这在我们的 IPA 协议中会很有用.
给定域 F F F 上的两个长度为 n n n 的向量, 证明它们的内积 < a ⃗ , b ⃗ > = z < \vec{a}, \vec{b}> = z < a , b >= z .
对于多项式 f f f 的系数向量 f ⃗ = a 0 , ⋯ , a n \vec{f}={a_{0}, \cdots, a_{n}} f = a 0 , ⋯ , a n , 有 f ( x ) = a 0 + a 1 x + ⋯ + a n x n f(x) = a_{0} + a_{1}x + \cdots + a_{n}x^{n} f ( x ) = a 0 + a 1 x + ⋯ + a n x n .
注意 f ( s ) = < f ⃗ , ( 1 , s , ⋯ , s n ) > f(s) = <\vec{f}, (1, s, \cdots, s^{n})> f ( s ) =< f , ( 1 , s , ⋯ , s n ) > 即是内积表示.
Setup
仅证明者知道的秘密向量是 a ⃗ = ( a 1 , a 2 , a 3 , a 4 ) \vec{a} = (a_1,a_2,a_3,a_4) a = ( a 1 , a 2 , a 3 , a 4 ) .
所有参与者都知道的有:
G ⃗ = ( G 1 , G 2 , G 3 , G 4 ) \vec{G} = (G_1, G_2, G_3, G_4) G = ( G 1 , G 2 , G 3 , G 4 ) , Pedersen hash 的一个基
A = ⟨ a ⃗ , G ⃗ ⟩ A = \langle \vec{a}, \vec{G} \rangle A = ⟨ a , G ⟩ , a ⃗ \vec{a} a 的承诺
b ⃗ = ( b 1 , b 2 , b 3 , b 4 ) \vec{b} = (b_1, b_2, b_3, b_4) b = ( b 1 , b 2 , b 3 , b 4 ) , 某个值 s s s 的幂, 使得b ⃗ = ( 1 , s , s 2 , s 3 ) \vec{b} = (1, s, s^2, s^3) b = ( 1 , s , s 2 , s 3 )
内积的结果 z = ⟨ a ⃗ , b ⃗ ⟩ z = \langle \vec{a}, \vec{b} \rangle z = ⟨ a , b ⟩
Reduced problem
首先, 证明者将所有内容一分为二. 然后, 他们使用x x x 来构造这些分割的线性组合:
a ′ ⃗ = x − 1 ( a 1 a 2 ) + x ( a 3 a 4 ) \vec{a'} = x^{-1} \begin{pmatrix}a_1 \\ a_2\end{pmatrix} + x \begin{pmatrix}a_3 \\ a_4\end{pmatrix} a ′ = x − 1 ( a 1 a 2 ) + x ( a 3 a 4 )
b ′ ⃗ = x ( b 1 b 2 ) + x − 1 ( b 3 b 4 ) \vec{b'} = x \begin{pmatrix}b_1 \\ b_2\end{pmatrix} + x^{-1} \begin{pmatrix}b_3 \\ b_4\end{pmatrix} b ′ = x ( b 1 b 2 ) + x − 1 ( b 3 b 4 )
G ′ ⃗ = x ( G 1 G 2 ) + x − 1 ( G 3 G 4 ) \vec{G'} = x \begin{pmatrix}G_1 \\ G_2\end{pmatrix} + x^{-1} \begin{pmatrix}G_3 \\ G_4\end{pmatrix} G ′ = x ( G 1 G 2 ) + x − 1 ( G 3 G 4 )
问题被简化为 ⟨ a ′ ⃗ , b ′ ⃗ ⟩ = z ′ \langle \vec{a'}, \vec{b'} \rangle = z' ⟨ a ′ , b ′ ⟩ = z ′ .
The actual proof
A ′ ⃗ = ⟨ a ′ ⃗ , G ′ ⃗ ⟩ = ( x − 1 a 1 + x a 3 ) ( x G 1 + x − 1 G 3 ) + ( x − 1 a 2 + x a 4 ) ( x G 2 + x − 1 G 4 ) = A + x − 2 ( a 1 G 3 + a 2 G 4 ) + x 2 ( a 3 G 1 + a 4 G 2 ) = A + x − 2 L a + x 2 R a \begin{align*}
\vec{A'} =& \langle \vec{a'}, \vec{G'} \rangle \\
=& (x^{-1} a_1 + x a_3)(x G_1 + x^{-1} G_3) + (x^{-1} a_2 + x a_4)(x G_2 + x^{-1}G_4) \\
=& A + x^{-2} (a_1 G_3 + a_2 G_4) + x^2 (a_3 G_1 + a_4 G_2) \\
=& A + x^{-2} L_a + x^{2} R_a
\end{align*} A ′ = = = = ⟨ a ′ , G ′ ⟩ ( x − 1 a 1 + x a 3 ) ( x G 1 + x − 1 G 3 ) + ( x − 1 a 2 + x a 4 ) ( x G 2 + x − 1 G 4 ) A + x − 2 ( a 1 G 3 + a 2 G 4 ) + x 2 ( a 3 G 1 + a 4 G 2 ) A + x − 2 L a + x 2 R a
z ′ ⃗ = ⟨ a ′ ⃗ , b ′ ⃗ ⟩ = ⟨ ( x − 1 a 1 + x a 3 x − 1 a 2 + x a 4 ) , ( x b 1 + x − 1 b 3 x b 2 + x − 1 b 4 ) ⟩ = ( a 1 b 1 + a 2 b 2 + a 3 b 3 + a 4 b 4 ) + x − 2 ( a 1 b 3 + a 2 b 4 ) + x 2 ( a 3 b 1 + a 4 b 2 ) = z + x − 2 ( L z ) + x 2 ( R z ) \begin{align*}
\vec{z'} =& \langle \vec{a'}, \vec{b'} \rangle \\
=& \langle \begin{pmatrix}x^{-1} a_1 + x a_3 \\ x^{-1} a_2 + x a_4 \end{pmatrix}, \begin{pmatrix}x b_1 + x^{-1} b_3 \\ x b_2 + x^{-1} b_4 \end{pmatrix} \rangle \\
=& (a_1b_1 + a_2b_2 + a_3b_3 + a_4b_4) + x^{-2} (a_1b_3 + a_2b_4) + x^2 (a_3b_1 + a_4b_2) \\
=& z + x^{-2} (L_z) + x^2 (R_z)
\end{align*} z ′ = = = = ⟨ a ′ , b ′ ⟩ ⟨ ( x − 1 a 1 + x a 3 x − 1 a 2 + x a 4 ) , ( x b 1 + x − 1 b 3 x b 2 + x − 1 b 4 ) ⟩ ( a 1 b 1 + a 2 b 2 + a 3 b 3 + a 4 b 4 ) + x − 2 ( a 1 b 3 + a 2 b 4 ) + x 2 ( a 3 b 1 + a 4 b 2 ) z + x − 2 ( L z ) + x 2 ( R z )
验证者可以从先前的值 z z z 以及证明者需要提供的两个标量值 L z L_z L z 和 R z R_z R z 重新计算 z ′ z' z ′ .
所以最后, 证明变成了:
向量 a ′ ⃗ \vec{a'} a ′ , 其大小是 a ⃗ \vec{a} a 的一半;
L a , R a L_a, R_a L a , R a 曲线点(如果压缩, 则围绕两个域元素);
L z , R z L_z, R_z L z , R z 标量值.
我们可以更新我们之前的图表:
The HALO optimization
Halo 优化类似于 bulletproofs 优化, 可进一步较少 proof size.
Halo 优化中, 问题转换成 C = A + z U = ⟨ a ⃗ , G ⃗ ⟩ + ⟨ a ⃗ , b ⃗ ⟩ U C = A + z U = \langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b} \rangle U C = A + z U = ⟨ a , G ⟩ + ⟨ a , b ⟩ U .
可将其 half reduce 为
C ′ = A ′ + z ′ U = ⟨ a ′ ⃗ , G ′ ⃗ ⟩ + ⟨ a ′ ⃗ , b ′ ⃗ ⟩ U = [ A + x − 2 L a + x 2 R a ] + [ z + x − 2 L z + x 2 R z ] U = C + x − 2 ( L a + L z U ) + x 2 ( R a + R z U ) = C + x − 2 L + x 2 R , \begin{align*}
C' &= A' + z' U \\
&= \langle \vec{a'}, \vec{G'} \rangle + \langle \vec{a'}, \vec{b'} \rangle U \\
&= [A + x^{-2}L_{a} + x^{2}R_{a}] + [z + x^{-2}L_{z} + x^{2}R_{z}] U \\
&= C + x^{-2}(L_{a} + L_{z}U) + x^{2}(R_{a} + R_{z}U) \\
&= C + x^{-2}L + x^{2}R,
\end{align*} C ′ = A ′ + z ′ U = ⟨ a ′ , G ′ ⟩ + ⟨ a ′ , b ′ ⟩ U = [ A + x − 2 L a + x 2 R a ] + [ z + x − 2 L z + x 2 R z ] U = C + x − 2 ( L a + L z U ) + x 2 ( R a + R z U ) = C + x − 2 L + x 2 R ,
这里 L = L a + L z U L= L_{a} + L_{z}U L = L a + L z U , R = R a + R z U R = R_{a} + R_{z}U R = R a + R z U .
Halo 优化将 4 个 域元素(压缩后)优化成 2 个域元素.
下面来添加零知识(给 pedersen commitment 添加 hiding), 有
C = A + z U + r H = ⟨ a ⃗ , G ⃗ ⟩ + ⟨ a ⃗ , b ⃗ ⟩ U + r H = C + x − 2 L + x 2 R , \begin{align*}
C &= A + zU + rH \\
&= \langle \vec{a}, \vec{G} \rangle + \langle \vec{a}, \vec{b} \rangle U + rH \\
&= C + x^{-2}L + x^{2}R ,
\end{align*} C = A + z U + rH = ⟨ a , G ⟩ + ⟨ a , b ⟩ U + rH = C + x − 2 L + x 2 R ,
这里 L = L a + L z U + r L H L= L_{a} + L_{z}U + r_{L}H L = L a + L z U + r L H , R = R a + R z U + r R H R = R_{a} + R_{z}U + r_{R}H R = R a + R z U + r R H .
最后, 下图是协议在经过 log 2 ( n ) \log_{2}(n) log 2 ( n ) 轮归约后再进行承诺打开的结果:
Aggregation
Aggregating opening proofs for several polynomials
Insight:
⟨ f ⃗ + v ⋅ g ⃗ , x ⃗ ⟩ = f ( x ) + v ⋅ g ( x ) \langle \vec{f} + v \cdot \vec{g}, \vec{x}\rangle = f(x) + v \cdot g(x) ⟨ f + v ⋅ g , x ⟩ = f ( x ) + v ⋅ g ( x )
Aggregating opening proofs for several evaluations
Insight:
⟨ f ⃗ , x 1 ⃗ + u ⋅ x 2 ⃗ ⟩ = f ( x 1 ) + u ⋅ f ( x 2 ) \langle \vec{f}, \vec{x_1} + u \cdot \vec{x_2}\rangle = f(x_1) + u \cdot f(x_2) ⟨ f , x 1 + u ⋅ x 2 ⟩ = f ( x 1 ) + u ⋅ f ( x 2 )
Double aggregation
Insight:
⟨ f ⃗ + v ⋅ g ⃗ , x 1 ⃗ + u ⋅ x 2 ⃗ ⟩ = f ( x 1 ) + v ⋅ g ( x 1 ) + u ⋅ ( f ( x 2 ) + v ⋅ g ( x 2 ) ) \langle \vec{f} + v \cdot \vec{g}, \vec{x_1} + u \cdot \vec{x_2} \rangle = f(x_1) + v \cdot g(x_1) + u \cdot (f(x_2) + v \cdot g(x_2)) ⟨ f + v ⋅ g , x 1 + u ⋅ x 2 ⟩ = f ( x 1 ) + v ⋅ g ( x 1 ) + u ⋅ ( f ( x 2 ) + v ⋅ g ( x 2 ))
Note that this kind of aggregation forces us to provide all combinations of evaluations, some of which might not be needed (for example, f ( x 2 ) f(x_2) f ( x 2 ) ).
Splitting a polynomial
If a polynomial is too large to fit in one SRS, you can split it in chuncks of size at most n n n
URS 由以下部分组成:
Gs
: 一个任意顺序的曲线点列表, 可用于以非隐藏方式承诺一个多项式.
H
: 一个盲化曲线点, 可用于为多项式承诺方案添加隐藏性.
URS 是确定生成的, 可以由下面的代码生成:
fn create (depth: usize ) -> Self {
let m = G::Map::setup ();
let g : Vec <_> = (0 ..depth)
.map (|i| {
let mut h = Blake2b512::new ();
h.update ((i as u32 ).to_be_bytes ());
point_of_random_bytes (&m, &h.finalize ())
})
.collect ();
let h = {
let mut h = Blake2b512::new ();
h.update ("srs_misc" .as_bytes ());
h.update (0_u32 .to_be_bytes ());
point_of_random_bytes (&m, &h.finalize ())
};
Self {
g,
h,
lagrange_bases: HashMapCache::new (),
}
}
生成算法, 见 hash-to-curve .
KZG10
Setup ( 1 κ , t ) \textbf{Setup}(1^\kappa, t) Setup ( 1 κ , t ) 计算两个素数阶 p p p (提供 κ \kappa κ 位安全性)的群 G \mathbb{G} G 和 G T \mathbb{G}_{T} G T , 使得存在一个对称双线性配对 e : G × G → G T e:\mathbb{G}×\mathbb{G} \rightarrow \mathbb{G}_{T} e : G × G → G T 且 t t t -SDH \text{SDH} SDH 假设成立. 我们将生成的双线性配对群记为 G = ⟨ e , G , G T ⟩ \mathcal{G}=\langle e,\mathbb{G},\mathbb{G}_{T} \rangle G = ⟨ e , G , G T ⟩ . 选择一个生成元 g ∈ R G g \in_{R} \mathbb{G} g ∈ R G . 令 α ∈ R Z p ∗ \alpha \in_{R} \mathbb{Z}_{p}^{*} α ∈ R Z p ∗ 为 SK \text{SK} SK , 由一个(可能是分布式的)可信权威机构生成. Setup \text{Setup} Setup 还生成一个 ( t + 1 ) (t + 1) ( t + 1 ) 元组 ⟨ g , g α , ⋯ , g α t ⟩ ∈ G t + 1 \langle g,g^\alpha,\cdots,g^{\alpha^t}\rangle\in\mathbb{G}^{t + 1} ⟨ g , g α , ⋯ , g α t ⟩ ∈ G t + 1 并输出 PK = ⟨ G , g , g α , ⋯ , g α t ⟩ \text{PK}=\langle\mathbb{G},g,g^\alpha,\cdots,g^{\alpha^t}\rangle PK = ⟨ G , g , g α , ⋯ , g α t ⟩ . 在构造的其余部分不需要 SK \text{SK} SK .
Commit ( PK , ϕ ( x ) ) \textbf{Commit}(\textbf{PK},\phi(x)) Commit ( PK , ϕ ( x )) 计算对次数为 t t t 或更低的多项式 ϕ ( x ) ∈ Z p [ X ] \phi(x)\in \mathbb{Z}_{p}[X] ϕ ( x ) ∈ Z p [ X ] 的承诺 C = g ϕ ( α ) ∈ G \mathcal{C} = g^{\phi(\alpha)} \in \mathbb{G} C = g ϕ ( α ) ∈ G . 对于ϕ ( x ) = ∑ j = 0 d e g ( ϕ ) ϕ j x j \phi(x)=\sum_{j = 0}^{deg(\phi)}\phi_{j}x^{j} ϕ ( x ) = ∑ j = 0 d e g ( ϕ ) ϕ j x j , 它输出 C = ∏ j = 0 d e g ( ϕ ) ( g α j ) ϕ j \mathcal{C} = \prod_{j = 0}^{deg(\phi)}(g^{ \alpha^{j} })^{\phi_{j} } C = ∏ j = 0 d e g ( ϕ ) ( g α j ) ϕ j 作为对 ϕ ( x ) \phi(x) ϕ ( x ) 的承诺.
Open ( PK , C , ϕ ( x ) ) \textbf{Open}(\textbf{PK},\mathcal{C},\phi(x)) Open ( PK , C , ϕ ( x )) 输出所承诺的多项式 ϕ ( x ) \phi(x) ϕ ( x ) .
VerifyPoly ( PK , C , ϕ ( x ) ) \textbf{VerifyPoly}(\textbf{PK},\mathcal{C},\phi(x)) VerifyPoly ( PK , C , ϕ ( x )) 验证 C = ? g ϕ ( α ) \mathcal{C} \stackrel{?} {=} g^{\phi(\alpha)} C = ? g ϕ ( α ) . 如果对于 ϕ ( x ) = ∑ j = 0 d e g ( ϕ ) ϕ j x j \phi(x)=\sum_{j = 0}^{deg(\phi)}\phi_{j}x^{j} ϕ ( x ) = ∑ j = 0 d e g ( ϕ ) ϕ j x j 有 C = ∏ j = 0 d e g ( ϕ ) ( g α j ) ϕ j \mathcal{C}=\prod_{j = 0}^{deg(\phi)}(g^{\alpha^j})^{\phi_j} C = ∏ j = 0 d e g ( ϕ ) ( g α j ) ϕ j , 该算法输出 1 1 1 , 否则输出 0 0 0 . 注意, 这仅在 d e g ( ϕ ) ≤ t deg(\phi)\leq t d e g ( ϕ ) ≤ t 时有效.
CreateWitness ( PK , ϕ ( x ) , i ) \textbf{CreateWitness}(\textbf{PK},\phi(x),i) CreateWitness ( PK , ϕ ( x ) , i ) 计算 ψ i ( x ) = ϕ ( x ) − ϕ ( i ) x − i \psi_i(x)=\frac{\phi(x)-\phi(i)}{x - i} ψ i ( x ) = x − i ϕ ( x ) − ϕ ( i ) 并输出 ⟨ i , ϕ ( i ) , w i ⟩ \langle i,\phi(i),w_i\rangle ⟨ i , ϕ ( i ) , w i ⟩ , 其中见证 w i = g ψ i ( α ) w_i = g^{\psi_{i}(\alpha)} w i = g ψ i ( α ) 的计算方式与上述 C \mathcal{C} C 类似.
VerifyEval ( PK , C , i , ϕ ( i ) , w i ) \textbf{VerifyEval}(\textbf{PK},\mathcal{C},i,\phi(i),w_i) VerifyEval ( PK , C , i , ϕ ( i ) , w i ) 验证 ϕ ( i ) \phi(i) ϕ ( i ) 是否是由 C C C 所承诺的多项式在索引 i i i 处的求值. 如果 e ( C , g ) = ? e ( w i , g α / g i ) e ( g , g ) ϕ ( i ) e(\mathcal{C},g) \stackrel{?}{=} e(w_{i},g^{\alpha}/g^i)e(g,g)^{\phi(i)} e ( C , g ) = ? e ( w i , g α / g i ) e ( g , g ) ϕ ( i ) , 该算法输出 1 1 1 , 否则输出 0 0 0 . V e r i f y E v a l VerifyEval V er i f y E v a l 是正确的, 因为
e ( w i , g α / g i ) e ( g , g ) ϕ ( i ) = e ( g ψ i ( α ) , g ( α − i ) ) e ( g , g ) ϕ ( i ) = e ( g , g ) ψ i ( α ) ( α − i ) + ϕ ( i ) = e ( g , g ) ϕ ( α ) = e ( C , g ) \begin{align*}
e(w_i,g^{\alpha}/g^i)e(g,g)^{\phi(i)}
&= e(g^{\psi_i(\alpha)},g^{(\alpha - i)})e(g,g)^{\phi(i)} \\ &=e(g,g)^{\psi_i(\alpha)(\alpha - i)+\phi(i)} \\
&=e(g,g)^{\phi(\alpha)} \\
&=e(C,g)
\end{align*} e ( w i , g α / g i ) e ( g , g ) ϕ ( i ) = e ( g ψ i ( α ) , g ( α − i ) ) e ( g , g ) ϕ ( i ) = e ( g , g ) ψ i ( α ) ( α − i ) + ϕ ( i ) = e ( g , g ) ϕ ( α ) = e ( C , g )
因为ϕ ( x ) = ψ i ( x ) ( x − i ) + ϕ ( i ) \phi(x)=\psi_i(x)(x - i)+\phi(i) ϕ ( x ) = ψ i ( x ) ( x − i ) + ϕ ( i ) .
注意 : α \alpha α 是有毒的废物, 必须丢弃, 因为它可以用来破坏绑定性.
Trusted setup
更多内容, 见 How do trusted setups work?
最后生成 SRS ⟨ g , g ∏ i = 0 k s i , ⋯ , g ∏ i = 0 k s i n ⟩ \langle g, g^{\prod_{i=0}^{k} s_{i}}, \cdots, g^{\prod_{i=0}^{k} s_{i}^{n}} \rangle ⟨ g , g ∏ i = 0 k s i , ⋯ , g ∏ i = 0 k s i n ⟩ .
更新 SRS
对于 SRS < g , g s , ⋯ , g s n > <g, g^{s}, \cdots, g^{s^{n}} > < g , g s , ⋯ , g s n > , 随机生成 t t t , 更新 SRS 为
< g , g s t , ⋯ , g ( s t ) n > <g, g^{st}, \cdots, g^{(st)^{n}} > < g , g s t , ⋯ , g ( s t ) n > .
FRI
todo