这篇文章简要介绍 Hyrax-PCS 的原理，其安全假设为 Discrete Log。它的主要思想是证明一个 Inner Product，并且采用了递归折叠的思路逐步把长度为 n n n n / 2 n/2 n /2 O ( n ) O(n) O ( n ) n × n \sqrt{n}\times\sqrt{n} n × n n \sqrt{n} n O ( n ) O(\sqrt{n}) O ( n ) O ( log n ) O(\log{n}) O ( log n )
1. MLE 多项式的求值证明 ¶ 不管 MLE 多项式是 Coefficients 形式还是 Evaluation 形式，我们都可以通过「内积证明」 Inner Product Argument 来证明多项式在某些点上的求值。
f ( X 0 , X 1 , . . . , X n − 1 ) = ∑ i = 0 2 n − 1 a i ⋅ e q ~ ( b i t s ( i ) , X 0 , X 1 , . . . , X n − 1 ) f(X_0, X_1, ..., X_{n-1}) = \sum_{i=0}^{2^n-1} a_i \cdot \tilde{eq}(\mathsf{bits}(i), X_0, X_1, ..., X_{n-1}) f ( X 0 , X 1 , ... , X n − 1 ) = i = 0 ∑ 2 n − 1 a i ⋅ e q ~ ( bits ( i ) , X 0 , X 1 , ... , X n − 1 ) f ( X 0 , X 1 , . . . , X n − 1 ) = ∑ i = 0 2 n − 1 c i ⋅ X 0 i 0 ⋅ X 1 i 1 ⋅ . . . ⋅ X n − 1 i n − 1 , where b i t s ( i ) = ( i 0 , i 1 , . . . , i n − 1 ) f(X_0, X_1, ..., X_{n-1}) = \sum_{i=0}^{2^n-1} c_i \cdot X_0^{i_0} \cdot X_1^{i_1} \cdot ... \cdot X_{n-1}^{i_{n-1}}, \quad \text{where } \mathsf{bits}(i) = (i_0, i_1, ..., i_{n-1}) f ( X 0 , X 1 , ... , X n − 1 ) = i = 0 ∑ 2 n − 1 c i ⋅ X 0 i 0 ⋅ X 1 i 1 ⋅ ... ⋅ X n − 1 i n − 1 , where bits ( i ) = ( i 0 , i 1 , ... , i n − 1 ) 如果我们有一个内积证明协议，那么我们可以轻松构造一个 MLE 多项式的求值证明
公共输入 ¶ a ⃗ \vec{a} a C a = c m ( a 0 , a 1 , . . . , a 2 n − 1 ) C_a=\mathsf{cm}(a_0, a_1, ..., a_{2^n-1}) C a = cm ( a 0 , a 1 , ... , a 2 n − 1 ) u ⃗ = ( u 0 , u 1 , . . . , u n − 1 ) \vec{u}=(u_0, u_1, ..., u_{n-1}) u = ( u 0 , u 1 , ... , u n − 1 ) v = f ~ ( u 0 , u 1 , . . . , u n − 1 ) v=\tilde{f}(u_0, u_1, ..., u_{n-1}) v = f ~ ( u 0 , u 1 , ... , u n − 1 ) Witness ¶ a ⃗ \vec{a} a 内积协议 ¶ Prover 计算向量 e ⃗ \vec{e} e 2 n 2^n 2 n
e 0 = e q ~ ( b i t s ( 0 ) , u 0 , u 1 , . . . , u n − 1 ) e 1 = e q ~ ( b i t s ( 1 ) , u 0 , u 1 , . . . , u n − 1 ) ⋯ e 2 n − 1 = e q ~ ( b i t s ( 2 n − 1 ) , u 0 , u 1 , . . . , u n − 1 ) \begin{aligned}
e_0 &= \tilde{eq}(\mathsf{bits}(0), u_0, u_1, ..., u_{n-1}) \\
e_1 &= \tilde{eq}(\mathsf{bits}(1), u_0, u_1, ..., u_{n-1}) \\
\cdots \\
e_{2^n-1} &= \tilde{eq}(\mathsf{bits}(2^n-1), u_0, u_1, ..., u_{n-1}) \\
\end{aligned} e 0 e 1 ⋯ e 2 n − 1 = e q ~ ( bits ( 0 ) , u 0 , u 1 , ... , u n − 1 ) = e q ~ ( bits ( 1 ) , u 0 , u 1 , ... , u n − 1 ) = e q ~ ( bits ( 2 n − 1 ) , u 0 , u 1 , ... , u n − 1 ) Prover 与 Verifier 通过一个 Inner Product Argument 协议来证明 a ⃗ \vec{a} a e ⃗ \vec{e} e v v v
2. Mini-IPA ¶ 我们先从最简单的情况入手，假如 Prover 拥有两个向量 a ⃗ \vec{a} a b ⃗ \vec{b} b ⟨ a ⃗ , b ⃗ ⟩ = c \langle \vec{a}, \vec{b} \rangle = c ⟨ a , b ⟩ = c c c c 公开值 ）。
证明目标 ¶ Prover 拥有知识 ( a ⃗ , b ⃗ ) (\vec{a},\vec{b}) ( a , b ) m m m 2 m 2m 2 m ⟨ a ⃗ , b ⃗ ⟩ = c \langle \vec{a}, \vec{b} \rangle = c ⟨ a , b ⟩ = c
公开参数 ¶ 我们计算向量的 Pedersen Commitment，需要选取一组随机的群元素 g 1 , g 2 , g 3 , … , g m , h ∈ G g_1, g_2, g_3, \ldots, g_m, h \in \mathbb{G} g 1 , g 2 , g 3 , … , g m , h ∈ G
公共输入 ¶ 内积计算结果 c c c 向量 a ⃗ \vec{a} a C a = c m ( a ⃗ ; ρ a ) C_a=\mathsf{cm}(\vec{a};\rho_a) C a = cm ( a ; ρ a ) 向量 b ⃗ \vec{b} b C b = c m ( b ⃗ ; ρ b ) C_b=\mathsf{cm}(\vec{b};\rho_b) C b = cm ( b ; ρ b ) Witnesses ¶ ( a ⃗ , ρ a ) (\vec{a}, \rho_a) ( a , ρ a ) ( b ⃗ , ρ b ) (\vec{b}, \rho_b) ( b , ρ b ) 协议基本思路 ¶ Prover 引入两个「致盲向量」Blinder factors， r ⃗ \vec{r} r s ⃗ \vec{s} s μ \mu μ
a ⃗ ′ = r ⃗ + μ ⋅ a ⃗ b ⃗ ′ = s ⃗ + μ ⋅ b ⃗ \vec{a}' = \vec{r}+ \mu\cdot \vec{a} \qquad \vec{b}' = \vec{s}+ \mu\cdot \vec{b} a ′ = r + μ ⋅ a b ′ = s + μ ⋅ b 然后计算a ⃗ ′ ⋅ b ⃗ ′ \vec{a}'\cdot \vec{b}' a ′ ⋅ b ′
⟨ a ⃗ ′ , b ⃗ ′ ⟩ = ( r ⃗ + μ ⋅ a ⃗ ) ( s ⃗ + μ ⋅ b ⃗ ) = μ 2 ( ⟨ a ⃗ , b ⃗ ⟩ ) + μ ( ⟨ a ⃗ , s ⃗ ⟩ + ⟨ b ⃗ , r ⃗ ⟩ ) + ⟨ r ⃗ , s ⃗ ⟩ \langle \vec{a}', \vec{b}' \rangle = (\vec{r}+ \mu\cdot \vec{a})(\vec{s}+ \mu\cdot \vec{b}) =\mu^2(\langle \vec{a}, \vec{b} \rangle) + \mu(\langle \vec{a}, \vec{s} \rangle + \langle \vec{b}, \vec{r} \rangle) + \langle \vec{r}, \vec{s} \rangle ⟨ a ′ , b ′ ⟩ = ( r + μ ⋅ a ) ( s + μ ⋅ b ) = μ 2 (⟨ a , b ⟩) + μ (⟨ a , s ⟩ + ⟨ b , r ⟩) + ⟨ r , s ⟩ 观察下 a ⃗ ′ \vec{a}' a ′ b ⃗ ′ \vec{b}' b ′ μ \mu μ μ \mu μ 二次多项式 ，其中 μ 2 \mu^2 μ 2 a ⃗ \vec{a} a b ⃗ \vec{b} b c c c r ⃗ ⋅ s ⃗ \vec{r}\cdot\vec{s} r ⋅ s μ \mu μ 混乱 。 我们可以先不管混乱的 μ \mu μ μ 2 \mu^2 μ 2
我们让 Prover 在协议第一步中不仅需要对「致盲向量」承诺，同时还要对内积展开后的（关于 μ \mu μ a ⃗ ′ \vec{a}' a ′ b ⃗ ′ \vec{b}' b ′ a ′ a' a ′ A ′ A' A ′ b ′ b' b ′ B ′ B' B ′ a ⃗ ′ ⋅ b ⃗ ′ \vec{a}'\cdot\vec{b}' a ′ ⋅ b ′ C ′ C' C ′
Round 1 ¶ Prover 发送两个「致盲向量」 r ⃗ \vec{r} r s ⃗ \vec{s} s C r C_r C r C s C_s C s C 0 C_0 C 0 C 1 C_1 C 1
C r = c m ( r ⃗ ; ρ r ) C s = c m ( s ⃗ ; ρ s ) C 0 = c m ( ⟨ r ⃗ , s ⃗ ⟩ ; ρ 0 ) C 1 = c m ( ⟨ a ⃗ , s ⃗ ⟩ + ⟨ b ⃗ , r ⃗ ⟩ ; ρ 1 ) \begin{aligned}
C_r&=\mathsf{cm}(\vec{r};\rho_{r}) \\
C_s&=\mathsf{cm}(\vec{s} ;\rho_{s}) \\
C_0&=\mathsf{cm}(\langle \vec{r}, \vec{s} \rangle; \rho_0) \\
C_1&=\mathsf{cm}(\langle \vec{a}, \vec{s} \rangle + \langle \vec{b}, \vec{r} \rangle; \rho_1) \\
\end{aligned} C r C s C 0 C 1 = cm ( r ; ρ r ) = cm ( s ; ρ s ) = cm (⟨ r , s ⟩ ; ρ 0 ) = cm (⟨ a , s ⟩ + ⟨ b , r ⟩ ; ρ 1 ) Round 2 ¶ Verifier 回复一个挑战数 μ \mu μ
Prover 发送两个拍扁向量 a ⃗ ′ \vec{a}' a ′ b ⃗ ′ \vec{b}' b ′ μ \mu μ ρ a ′ \rho'_a ρ a ′ ρ b ′ \rho'_b ρ b ′ ρ a b ′ \rho'_{ab} ρ ab ′
a ⃗ ′ = r ⃗ + μ ⋅ a ⃗ b ⃗ ′ = s ⃗ + μ ⋅ b ⃗ \begin{aligned}
\vec{a}'&=\vec{r} + \mu \cdot \vec{a}\\
\vec{b}'&=\vec{s} + \mu \cdot \vec{b}\\
\end{aligned} a ′ b ′ = r + μ ⋅ a = s + μ ⋅ b ρ a ′ = ρ r + μ ⋅ ρ a ρ b ′ = ρ s + μ ⋅ ρ b ρ a b ′ = ρ 0 + μ ⋅ ρ 1 \begin{aligned}
\rho'_a&=\rho_{r} + \mu \cdot \rho_a \\
\rho'_b&=\rho_{s} + \mu \cdot \rho_b \\
\rho'_{ab}&=\rho_0 + \mu \cdot \rho_1 \\
\end{aligned} ρ a ′ ρ b ′ ρ ab ′ = ρ r + μ ⋅ ρ a = ρ s + μ ⋅ ρ b = ρ 0 + μ ⋅ ρ 1 Verifier 在群 G \mathbb{G} G a ⃗ ′ \vec{a}' a ′ b ⃗ ′ \vec{b}' b ′
c m ( a ⃗ ′ ; ρ a ′ ) = ? C r + μ ⋅ C a c m ( b ⃗ ′ ; ρ b ′ ) = ? C s + μ ⋅ C b \begin{aligned}
\mathsf{cm}(\vec{a}'; \rho'_a)&\overset{?}{=} C_r + \mu\cdot C_a \\
\mathsf{cm}(\vec{b}'; \rho'_b)&\overset{?}{=} C_s + \mu \cdot C_b \\
\end{aligned} cm ( a ′ ; ρ a ′ ) cm ( b ′ ; ρ b ′ ) = ? C r + μ ⋅ C a = ? C s + μ ⋅ C b c m ( ⟨ a ⃗ ′ , b ⃗ ′ ⟩ ; ρ a b ′ ) = ? μ 2 ⋅ c m ( c ; 0 ) + μ ⋅ C 1 + C 0 \mathsf{cm}(\langle \vec{a}', \vec{b}' \rangle; \rho'_{ab})\overset{?}{=} \mu^2\cdot\mathsf{cm}(c;0) + \mu\cdot C_1 + C_0 cm (⟨ a ′ , b ′ ⟩ ; ρ ab ′ ) = ? μ 2 ⋅ cm ( c ; 0 ) + μ ⋅ C 1 + C 0 这个协议的最大问题是 Verifier 的计算复杂度为 O ( n ) O(n) O ( n ) ⟨ a ⃗ ′ , b ⃗ ′ ⟩ \langle \vec{a}', \vec{b}' \rangle ⟨ a ′ , b ′ ⟩ b ⃗ \vec{b} b e ⃗ \vec{e} e u ⃗ \vec{u} u
3. Square-root inner product argument ¶ Hyrax 论文提出了一个简单直接的思路，将 Verifier 的计算复杂度降到 O ( n ) O(\sqrt{n}) O ( n ) f ~ \tilde{f} f ~ c ⃗ \vec{c} c f ~ \tilde{f} f ~
我们假设 n = 4 n=4 n = 4 c ⃗ \vec{c} c
[ c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15 ] \begin{bmatrix}
c_0 & c_1 & c_2 & c_3 \\
c_4 & c_5 & c_6 & c_7 \\
c_8 & c_9 & c_{10} & c_{11} \\
c_{12} & c_{13} & c_{14} & c_{15}
\end{bmatrix} ⎣ ⎡ c 0 c 4 c 8 c 12 c 1 c 5 c 9 c 13 c 2 c 6 c 10 c 14 c 3 c 7 c 11 c 15 ⎦ ⎤ 以 c ⃗ \vec{c} c
f ~ ( X 0 , X 1 , X 2 , X 3 ) = [ 1 X 2 X 3 X 2 X 3 ] [ c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15 ] [ 1 X 0 X 1 X 0 X 1 ] \tilde{f}(X_0, X_1, X_2, X_3) =
\begin{bmatrix}
1 & X_2 & X_3 & X_2X_3 \\
\end{bmatrix}
\begin{bmatrix}
c_0 & c_1 & c_2 & c_3 \\
c_4 & c_5 & c_6 & c_7 \\
c_8 & c_9 & c_{10} & c_{11} \\
c_{12} & c_{13} & c_{14} & c_{15}
\end{bmatrix}
\begin{bmatrix}
1 \\
X_0 \\
X_1 \\
X_0X_1 \\
\end{bmatrix} f ~ ( X 0 , X 1 , X 2 , X 3 ) = [ 1 X 2 X 3 X 2 X 3 ] ⎣ ⎡ c 0 c 4 c 8 c 12 c 1 c 5 c 9 c 13 c 2 c 6 c 10 c 14 c 3 c 7 c 11 c 15 ⎦ ⎤ ⎣ ⎡ 1 X 0 X 1 X 0 X 1 ⎦ ⎤ 这个矩阵的计算结果如下：
f ~ ( X 0 , X 1 , X 2 , X 3 ) = c 0 + c 1 X 0 + c 2 X 1 + c 3 X 0 X 1 + c 4 X 2 + ⋯ + c 14 X 1 X 2 X 3 + c 15 X 0 X 1 X 2 X 3 \tilde{f}(X_0, X_1, X_2, X_3) = c_0 + c_1X_0 + c_2X_1 + c_3X_0X_1 + c_4X_2 + \cdots + c_{14}X_1X_2X_3 + c_{15}X_0X_1X_2X_3 f ~ ( X 0 , X 1 , X 2 , X 3 ) = c 0 + c 1 X 0 + c 2 X 1 + c 3 X 0 X 1 + c 4 X 2 + ⋯ + c 14 X 1 X 2 X 3 + c 15 X 0 X 1 X 2 X 3 我们先把 u ⃗ \vec{u} u
u ⃗ = ( u 0 , u 1 , u 2 , u 3 ) = ( u 0 , u 1 ) ∥ ( u 2 , u 3 ) \vec{u} = (u_0, u_1, u_2, u_3) = (u_0, u_1) \parallel (u_2, u_3) u = ( u 0 , u 1 , u 2 , u 3 ) = ( u 0 , u 1 ) ∥ ( u 2 , u 3 ) 那么 f ~ ( u 0 , u 1 , u 2 , u 3 ) \tilde{f}(u_0, u_1, u_2, u_3) f ~ ( u 0 , u 1 , u 2 , u 3 )
f ~ ( u 0 , u 1 , u 2 , u 3 ) = [ 1 u 2 u 3 u 2 u 3 ] [ c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 c 9 c 10 c 11 c 12 c 13 c 14 c 15 ] [ 1 u 0 u 1 u 0 u 1 ] \tilde{f}(u_0, u_1, u_2, u_3) = \begin{bmatrix}
1 & u_2 & u_3 & u_2u_3 \\
\end{bmatrix}
\begin{bmatrix}
c_0 & c_1 & c_2 & c_3 \\
c_4 & c_5 & c_6 & c_7 \\
c_8 & c_9 & c_{10} & c_{11} \\
c_{12} & c_{13} & c_{14} & c_{15}
\end{bmatrix}
\begin{bmatrix}
1 \\
u_0 \\
u_1 \\
u_0u_1 \\
\end{bmatrix} f ~ ( u 0 , u 1 , u 2 , u 3 ) = [ 1 u 2 u 3 u 2 u 3 ] ⎣ ⎡ c 0 c 4 c 8 c 12 c 1 c 5 c 9 c 13 c 2 c 6 c 10 c 14 c 3 c 7 c 11 c 15 ⎦ ⎤ ⎣ ⎡ 1 u 0 u 1 u 0 u 1 ⎦ ⎤ 然后，我们把 c ⃗ \vec{c} c C 0 , C 1 , C 2 , C 3 C_0, C_1, C_2, C_3 C 0 , C 1 , C 2 , C 3
C 0 = c m ( c 0 , c 1 , c 2 , c 3 ; ρ 0 ) C 1 = c m ( c 4 , c 5 , c 6 , c 7 ; ρ 1 ) C 2 = c m ( c 8 , c 9 , c 10 , c 11 ; ρ 2 ) C 3 = c m ( c 12 , c 13 , c 14 , c 15 ; ρ 3 ) \begin{aligned}
C_0 &= \mathsf{cm}(c_0, c_1, c_2, c_3; \rho_0) \\
C_1 &= \mathsf{cm}(c_4, c_5, c_6, c_7; \rho_1) \\
C_2 &= \mathsf{cm}(c_8, c_9, c_{10}, c_{11}; \rho_2) \\
C_3 &= \mathsf{cm}(c_{12}, c_{13}, c_{14}, c_{15}; \rho_3)
\end{aligned} C 0 C 1 C 2 C 3 = cm ( c 0 , c 1 , c 2 , c 3 ; ρ 0 ) = cm ( c 4 , c 5 , c 6 , c 7 ; ρ 1 ) = cm ( c 8 , c 9 , c 10 , c 11 ; ρ 2 ) = cm ( c 12 , c 13 , c 14 , c 15 ; ρ 3 ) 然后我们可以使用 ( 1 , u 2 , u 3 , u 2 u 3 ) (1, u_2, u_3, u_2u_3) ( 1 , u 2 , u 3 , u 2 u 3 ) ( C 0 , C 1 , C 2 , C 3 ) (C_0, C_1, C_2, C_3) ( C 0 , C 1 , C 2 , C 3 ) C ∗ C^* C ∗
C ∗ = C 0 + u 2 C 1 + u 3 C 2 + u 2 u 3 C 3 C^* = C_0 + u_2C_1 + u_3C_2 + u_2u_3C_3 C ∗ = C 0 + u 2 C 1 + u 3 C 2 + u 2 u 3 C 3 那么 C ∗ C^* C ∗ M c M_c M c ( 1 , u 2 , u 3 , u 2 u 3 ) (1, u_2, u_3, u_2u_3) ( 1 , u 2 , u 3 , u 2 u 3 ) d ⃗ = ( d 0 , d 1 , d 2 , d 3 ) \vec{d}=(d_0, d_1, d_2, d_3) d = ( d 0 , d 1 , d 2 , d 3 )
d 0 = c 0 + c 4 ⋅ u 2 + c 8 ⋅ u 3 + c 12 ⋅ u 2 u 3 d 1 = c 1 + c 5 ⋅ u 2 + c 9 ⋅ u 3 + c 13 ⋅ u 2 u 3 d 2 = c 2 + c 6 ⋅ u 2 + c 10 ⋅ u 3 + c 14 ⋅ u 2 u 3 d 3 = c 3 + c 7 ⋅ u 2 + c 11 ⋅ u 3 + c 15 ⋅ u 2 u 3 \begin{split}
d_0 &= c_0 + c_4\cdot u_2 + c_8\cdot u_3 + c_{12}\cdot u_2u_3 \\
d_1 &= c_1 + c_5\cdot u_2 + c_9\cdot u_3 + c_{13}\cdot u_2u_3 \\
d_2 &= c_2 + c_6\cdot u_2 + c_{10}\cdot u_3 + c_{14}\cdot u_2u_3 \\
d_3 &= c_3 + c_7\cdot u_2 + c_{11}\cdot u_3 + c_{15}\cdot u_2u_3 \\
\end{split} d 0 d 1 d 2 d 3 = c 0 + c 4 ⋅ u 2 + c 8 ⋅ u 3 + c 12 ⋅ u 2 u 3 = c 1 + c 5 ⋅ u 2 + c 9 ⋅ u 3 + c 13 ⋅ u 2 u 3 = c 2 + c 6 ⋅ u 2 + c 10 ⋅ u 3 + c 14 ⋅ u 2 u 3 = c 3 + c 7 ⋅ u 2 + c 11 ⋅ u 3 + c 15 ⋅ u 2 u 3 可以轻易验证：
C ∗ = c m ( d 0 , d 1 , d 2 , d 3 ; ρ ∗ ) C^* = \mathsf{cm}(d_0, d_1, d_2, d_3; \rho^*) C ∗ = cm ( d 0 , d 1 , d 2 , d 3 ; ρ ∗ ) 这里 ρ ∗ = ρ 0 + ρ 1 u 2 + ρ 2 u 3 + ρ 3 u 2 u 3 \rho^*=\rho_0 + \rho_1u_2 + \rho_2u_3 + \rho_3u_2u_3 ρ ∗ = ρ 0 + ρ 1 u 2 + ρ 2 u 3 + ρ 3 u 2 u 3
采用这个思路，我们构造一个简单的 MLE 多项式承诺方案。
公共输入 ¶ a ⃗ \vec{a} a C a = c m ( a 0 , a 1 , . . . , a 2 n − 1 ) C_a=\mathsf{cm}(a_0, a_1, ..., a_{2^n-1}) C a = cm ( a 0 , a 1 , ... , a 2 n − 1 ) u ⃗ = ( u 0 , u 1 , . . . , u n − 1 ) \vec{u}=(u_0, u_1, ..., u_{n-1}) u = ( u 0 , u 1 , ... , u n − 1 ) v = f ~ ( u 0 , u 1 , . . . , u n − 1 ) v=\tilde{f}(u_0, u_1, ..., u_{n-1}) v = f ~ ( u 0 , u 1 , ... , u n − 1 ) Witness ¶ a ⃗ \vec{a} a Prover 把 a ⃗ \vec{a} a M a ∈ F p h × l M_a\in\mathbb{F}_p^{h\times l} M a ∈ F p h × l M a = [ a 0 a 1 a 2 ⋯ a l − 1 a l a l + 1 a l + 2 ⋯ a 2 l − 1 a 2 l a 2 l + 1 a 2 l + 2 ⋯ a 3 l − 1 a ( h − 1 ) l a ( h − 1 ) l + 1 a ( h − 1 ) l + 2 ⋯ a h l − 1 ] M_a =
\begin{bmatrix}
a_0 & a_1 & a_2 & \cdots & a_{l-1} \\
a_l & a_{l+1} & a_{l+2} & \cdots & a_{2l-1} \\
a_{2l} & a_{2l+1} & a_{2l+2} & \cdots & a_{3l-1} \\
a_{(h-1)l} & a_{(h-1)l+1} & a_{(h-1)l+2} & \cdots & a_{hl-1} \\
\end{bmatrix} M a = ⎣ ⎡ a 0 a l a 2 l a ( h − 1 ) l a 1 a l + 1 a 2 l + 1 a ( h − 1 ) l + 1 a 2 a l + 2 a 2 l + 2 a ( h − 1 ) l + 2 ⋯ ⋯ ⋯ ⋯ a l − 1 a 2 l − 1 a 3 l − 1 a h l − 1 ⎦ ⎤ Prover 按行计算承诺 C 0 , C 1 , . . . , C h − 1 C_0, C_1, ..., C_{h-1} C 0 , C 1 , ... , C h − 1 C 0 = c m ( a 0 , a 1 , . . . , a l − 1 ; ρ 0 ) C 1 = c m ( a l , a l + 1 , . . . , a 2 l − 1 ; ρ 1 ) C 2 = c m ( a 2 l , a 2 l + 1 , . . . , a 3 l − 1 ; ρ 2 ) ⋯ = ⋯ C h − 1 = c m ( a ( h − 1 ) l , a ( h − 1 ) l + 1 , . . . , a h l − 1 ; ρ h − 1 ) \begin{aligned}
C_0 &= \mathsf{cm}(a_0, a_1, ..., a_{l-1}; \rho_0) \\
C_1 &= \mathsf{cm}(a_l, a_{l+1}, ..., a_{2l-1}; \rho_1) \\
C_2 &= \mathsf{cm}(a_{2l}, a_{2l+1}, ..., a_{3l-1}; \rho_2) \\
\cdots\ &=\quad \cdots \\
C_{h-1} &= \mathsf{cm}(a_{(h-1)l}, a_{(h-1)l+1}, ..., a_{hl-1}; \rho_{h-1}) \\
\end{aligned} C 0 C 1 C 2 ⋯ C h − 1 = cm ( a 0 , a 1 , ... , a l − 1 ; ρ 0 ) = cm ( a l , a l + 1 , ... , a 2 l − 1 ; ρ 1 ) = cm ( a 2 l , a 2 l + 1 , ... , a 3 l − 1 ; ρ 2 ) = ⋯ = cm ( a ( h − 1 ) l , a ( h − 1 ) l + 1 , ... , a h l − 1 ; ρ h − 1 ) Evaluation证明协议 ¶ Prover 与 Verifier 把 u ⃗ \vec{u} u u ⃗ L \vec{u}_L u L u ⃗ R \vec{u}_R u R u ⃗ L = ( u 0 , u 1 , . . . , u log ( l ) − 1 ) u ⃗ R = ( u log ( l ) , u log ( l ) + 1 , . . . , u n − 1 ) \begin{aligned}
\vec{u}_L &= (u_0, u_1, ..., u_{\log(l)-1}) \\
\vec{u}_R &= (u_{\log(l)}, u_{\log(l)+1}, ..., u_{n-1}) \\
\end{aligned} u L u R = ( u 0 , u 1 , ... , u l o g ( l ) − 1 ) = ( u l o g ( l ) , u l o g ( l ) + 1 , ... , u n − 1 ) 显然
u ⃗ = u ⃗ L ∥ u ⃗ R \vec{u} = \vec{u}_L \parallel \vec{u}_R u = u L ∥ u R Round 1 ¶ Prover 计算 e ⃗ = ( e 0 , e 1 , . . . , e h − 1 ) \vec{e}=(e_0, e_1, ..., e_{h-1}) e = ( e 0 , e 1 , ... , e h − 1 ) h h h e 0 = e q ~ ( b i t s ( 0 ) , u ⃗ R ) e 1 = e q ~ ( b i t s ( 1 ) , u ⃗ R ) ⋯ = ⋯ e h − 1 = e q ~ ( b i t s ( h − 1 ) , u ⃗ R ) \begin{split}
e_0 &= \tilde{eq}(\mathsf{bits}(0), \vec{u}_R) \\
e_1 &= \tilde{eq}(\mathsf{bits}(1), \vec{u}_R) \\
\cdots\ &=\quad \cdots \\
e_{h-1} &= \tilde{eq}(\mathsf{bits}(h-1), \vec{u}_R) \\
\end{split} e 0 e 1 ⋯ e h − 1 = e q ~ ( bits ( 0 ) , u R ) = e q ~ ( bits ( 1 ) , u R ) = ⋯ = e q ~ ( bits ( h − 1 ) , u R ) Prover 计算 e ⃗ \vec{e} e M a M_a M a b ⃗ \vec{b} b l l l b 0 = ⟨ e ⃗ , ( a 0 , a l , . . . , a ( h − 1 ) l ) ⟩ b 1 = ⟨ e ⃗ , ( a 1 , a l + 1 , . . . , a ( h − 1 ) l + 1 ) ⟩ ⋯ = ⋯ b l − 1 = ⟨ e ⃗ , ( a l − 1 , a l + l − 1 , . . . , a ( h − 1 ) l + l − 1 ) ⟩ \begin{split}
b_0 &= \langle \vec{e}, (a_0, a_l, ..., a_{(h-1)l}) \rangle \\
b_1 &= \langle \vec{e}, (a_1, a_{l+1}, ..., a_{(h-1)l+1}) \rangle \\
\cdots\ &=\quad \cdots \\
b_{l-1} &= \langle \vec{e}, (a_{l-1}, a_{l+l-1}, ..., a_{(h-1)l+l-1}) \rangle \\
\end{split} b 0 b 1 ⋯ b l − 1 = ⟨ e , ( a 0 , a l , ... , a ( h − 1 ) l )⟩ = ⟨ e , ( a 1 , a l + 1 , ... , a ( h − 1 ) l + 1 )⟩ = ⋯ = ⟨ e , ( a l − 1 , a l + l − 1 , ... , a ( h − 1 ) l + l − 1 )⟩ Prover 计算 b ⃗ \vec{b} b C ∗ C^* C ∗ C ∗ = c m ( b ⃗ ; ρ ∗ ) C^* = \mathsf{cm}(\vec{b}; \rho^*) C ∗ = cm ( b ; ρ ∗ ) 这里 ρ ∗ = ⟨ e ⃗ , ( ρ 0 , ρ 1 , . . . , ρ h − 1 ) ⟩ \rho^* = \langle \vec{e}, (\rho_0, \rho_1, ..., \rho_{h-1}) \rangle ρ ∗ = ⟨ e , ( ρ 0 , ρ 1 , ... , ρ h − 1 )⟩
Round 2. ¶ Prover 和 Verifier 进行一个 Inner Product Argument 协议，完成 b ⃗ \vec{b} b d ⃗ \vec{d} d
d 0 = e q ~ ( b i t s ( 0 ) , u ⃗ L ) d 1 = e q ~ ( b i t s ( 1 ) , u ⃗ L ) ⋯ = ⋯ d h − 1 = e q ~ ( b i t s ( h − 1 ) , u ⃗ L ) \begin{split}
d_0 &= \tilde{eq}(\mathsf{bits}(0), \vec{u}_L) \\
d_1 &= \tilde{eq}(\mathsf{bits}(1), \vec{u}_L) \\
\cdots\ &=\quad \cdots \\
d_{h-1} &= \tilde{eq}(\mathsf{bits}(h-1), \vec{u}_L) \\
\end{split} d 0 d 1 ⋯ d h − 1 = e q ~ ( bits ( 0 ) , u L ) = e q ~ ( bits ( 1 ) , u L ) = ⋯ = e q ~ ( bits ( h − 1 ) , u L ) Prover 先抽样一个随机数向量 r ⃗ \vec{r} r b ⃗ \vec{b} b C r = c m ( r ⃗ ; ρ r ) C_{r} = \mathsf{cm}(\vec{r}; \rho_{r}) C r = cm ( r ; ρ r ) Prover 计算 r ⃗ \vec{r} r b ⃗ \vec{b} b v v v s = r ⃗ ⋅ d ⃗ s = \vec{r}\cdot\vec{d} s = r ⋅ d C 0 = c m ( s ; ρ s ) C_0 = \mathsf{cm}(s; \rho_s) C 0 = cm ( s ; ρ s ) C 1 = c m ( 0 ; ρ t ) C_1 = \mathsf{cm}(0; \rho_t) C 1 = cm ( 0 ; ρ t ) Round 3. ¶ Verifier 发送一个随机数 μ \mu μ
Prover 计算并发送下面的值：
z b ⃗ = r ⃗ + μ ⋅ b ⃗ \vec{z_b} = \vec{r} + \mu\cdot\vec{b} z b = r + μ ⋅ b z ρ = ρ r + μ ⋅ ρ ∗ z_\rho = \rho_r + \mu\cdot\rho^* z ρ = ρ r + μ ⋅ ρ ∗ z t = ρ s + μ − 1 ⋅ ρ t z_t = \rho_s + \mu^{-1}\cdot\rho_t z t = ρ s + μ − 1 ⋅ ρ t Verification ¶ Verifier 计算 C ∗ C^* C ∗
Verifier 验证：
C r + μ ⋅ C ∗ = ? c m ( z b ⃗ ; z ρ ) C_r + \mu\cdot{}C^*\overset{?}{=} \mathsf{cm}(\vec{z_b}; z_\rho) C r + μ ⋅ C ∗ = ? cm ( z b ; z ρ ) C 0 + μ − 1 ⋅ C 1 + μ ⋅ c m ( v ; 0 ) = ? c m ( ⟨ z ⃗ b , d ⃗ ⟩ ; z t ) C_0 + \mu^{-1}\cdot{}C_1 + \mu\cdot\mathsf{cm}(v; 0)\overset{?}{=} \mathsf{cm}(\langle\vec{z}_b, \vec{d}\rangle; z_t) C 0 + μ − 1 ⋅ C 1 + μ ⋅ cm ( v ; 0 ) = ? cm (⟨ z b , d ⟩ ; z t ) 4. Bulletproofs 的优化 ¶ 在上文中的「内积证明」协议（Mini-IPA）的 Round-2，由于 Prover 要发送长度为 l l l z ⃗ b \vec{z}_b z b O ( l ) O(l) O ( l ) 证明尺寸的压缩 。
假设有一个长度为 4 的向量 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 ) a ⃗ 1 = ( a 1 , a 2 ) \vec{a}_1 = (a_1, a_2) a 1 = ( a 1 , a 2 ) a ⃗ 2 = ( a 3 , a 4 ) \vec{a}_2 = (a_3, a_4) a 2 = ( a 3 , a 4 )
[ a 1 a 2 a 3 a 4 ] \begin{bmatrix}
a_1 & a_2\\
a_3 & a_4 \\
\end{bmatrix} [ a 1 a 3 a 2 a 4 ] 然后我们对这个 2 × 2 2\times 2 2 × 2
( x , x − 1 ) [ a 1 a 2 a 3 a 4 ] = ( a 1 x + a 3 x − 1 , a 2 x + a 4 x − 1 ) = a ⃗ ′ (x, x^{-1})
\left[
\begin{array}{ll}
a_1 &a_2\\
a_3 &a_4
\end{array}
\right]
= (a_1x + a_3x^{-1},\quad a_2x + a_4x^{-1})
= \vec{a}' ( x , x − 1 ) [ a 1 a 3 a 2 a 4 ] = ( a 1 x + a 3 x − 1 , a 2 x + a 4 x − 1 ) = a ′ 方法如上式，我们把矩阵左乘上一个随机数向量 ( x , x − 1 ) (x, x^{-1}) ( x , x − 1 ) a ⃗ ′ \vec{a}' a ′ ( x 0 , x 1 ) (x^0, x^1) ( x 0 , x 1 )
我们能注意到，折叠后的向量 a ⃗ ′ \vec{a}' a ′ a ⃗ \vec{a} a 2 k 2^k 2 k k k k 横向拍扁 。
这个初步思路面临第一个问题 ，就是当向量切成两半之后，原始向量 a ⃗ \vec{a} a A A A
c m G ⃗ ( a ⃗ ) = a 1 G 1 + a 2 G 2 + ⋯ + a m G m \mathsf{cm}_{\vec{G}}(\vec{a}) = a_1G_1 + a_2G_2 + \cdots + a_mG_m cm G ( a ) = a 1 G 1 + a 2 G 2 + ⋯ + a m G m 接下来的技巧很关键，我们把基向量 G ⃗ \vec{G} G 不同的 「挑战向量」：
( x − 1 , x ) [ G 1 G 2 G 3 G 4 ] = ( G 1 x − 1 + G 3 x , G 2 x − 1 + G 4 x ) = G ⃗ ′ (x^{-1}, x)
\left[
\begin{array}{ll}
G_1 &G_2\\
G_3 &G_4
\end{array}
\right]
= (G_1x^{-1} + G_3x, \quad G_2x^{-1} + G_4x) = \vec{G}' ( x − 1 , x ) [ G 1 G 3 G 2 G 4 ] = ( G 1 x − 1 + G 3 x , G 2 x − 1 + G 4 x ) = G ′ 请注意上面两个挑战向量 ( x , x − 1 ) (x, x^{-1}) ( x , x − 1 ) ( x − 1 , x ) (x^{-1}, x) ( x − 1 , x ) 对称的 。这么做的目的，是为了凑一个特殊的常数项。当把新的向量 a ⃗ ′ \vec{a}' a ′ G ⃗ ′ \vec{G}' G ′ a ⃗ \vec{a} a G ⃗ \vec{G} G x 2 x^2 x 2 x − 2 x^{-2} x − 2 比较混乱的值 。
我们展开计算下，首先把 a ⃗ \vec{a} a a ⃗ = ( a ⃗ 1 , a ⃗ 2 ) \vec{a}=(\vec{a}_1, \vec{a}_2) a = ( a 1 , a 2 ) G ⃗ = ( G ⃗ 1 , G ⃗ 2 ) \vec{G}=(\vec{G}_1, \vec{G}_2) G = ( G 1 , G 2 ) a ⃗ ′ = a ⃗ 1 x + a ⃗ 2 x − 1 \vec{a}'=\vec{a}_1x + \vec{a}_2x^{-1} a ′ = a 1 x + a 2 x − 1 G ⃗ ′ = G ⃗ 1 x − 1 + G ⃗ 2 x \vec{G}'=\vec{G}_1x^{-1} + \vec{G}_2x G ′ = G 1 x − 1 + G 2 x
a ⃗ ′ ⋅ G ⃗ ′ = ( 1 , 1 ) ( [ a ⃗ 1 ⋅ G ⃗ 1 a ⃗ 1 ⋅ G ⃗ 2 a ⃗ 2 ⋅ G ⃗ 1 a ⃗ 2 ⋅ G ⃗ 2 ] ∘ [ 1 x 2 x − 2 1 ] ) ( 1 1 ) \vec{a}'\cdot\vec{G}'=
(1,1)\left(\left[
\begin{array}{cc}
\vec{a}_1\cdot\vec{G}_1 & \vec{a}_1\cdot\vec{G}_2 \\
\vec{a}_2\cdot\vec{G}_1 & \vec{a}_2\cdot\vec{G}_2
\end{array}
\right]
\circ
\left[
\begin{array}{cc}
1 & x^2 \\
x^{-2} & 1
\end{array}
\right]\right)
\left(
\begin{array}{c}
1\\
1
\end{array}
\right) a ′ ⋅ G ′ = ( 1 , 1 ) ( [ a 1 ⋅ G 1 a 2 ⋅ G 1 a 1 ⋅ G 2 a 2 ⋅ G 2 ] ∘ [ 1 x − 2 x 2 1 ] ) ( 1 1 ) 上面式子右边是一个关于 x x x x 2 x^2 x 2 x − 2 x^{-2} x − 2
接下来我们来解决上面提出的问题：如何让 Verifier 能算出折叠后向量 a ⃗ ′ \vec{a}' a ′
A ′ = A + ( a ⃗ 1 ⋅ G ⃗ 2 ) x 2 + ( a ⃗ 2 ⋅ G ⃗ 1 ) x − 2 A'=A + (\vec{a}_1\cdot\vec{G}_2)~x^2 + (\vec{a}_2\cdot\vec{G}_1)~x^{-2} A ′ = A + ( a 1 ⋅ G 2 ) x 2 + ( a 2 ⋅ G 1 ) x − 2 我们让 Verifier 计算 A ′ = a ⃗ ′ ⋅ G ⃗ ′ A'=\vec{a}'\cdot \vec{G}' A ′ = a ′ ⋅ G ′ G ⃗ ′ \vec{G}' G ′ a ⃗ ′ \vec{a}' a ′ A ′ A' A ′
承诺 A ′ A' A ′ x x x A A A x 2 x^2 x 2 x − 2 x^{-2} x − 2 x 1 x^1 x 1 x − 1 x^{-1} x − 1 零 。因为我们巧妙采用了两个对称的挑战向量分别对 a ⃗ \vec{a} a G ⃗ \vec{G} G x x x x − 1 x^{-1} x − 1
新的承诺 A ′ A' A ′ A ′ = A + L x 2 + R x − 2 A'=A + Lx^2 + Rx^{-2} A ′ = A + L x 2 + R x − 2 L = ( a ⃗ 1 ⋅ G ⃗ 2 ) L=(\vec{a}_1\cdot \vec{G}_2) L = ( a 1 ⋅ G 2 ) R = ( a ⃗ 2 ⋅ G ⃗ 1 ) R=(\vec{a}_2\cdot \vec{G}_1) R = ( a 2 ⋅ G 1 ) L L L R R R m m m v ⃗ \vec{v} v 对折并拍扁后的向量 v ⃗ ′ \vec{v}' v ′ m / 2 m/2 m /2
递归折叠也有相应的代价，除了Verifier 要额外计算 G ⃗ ′ \vec{G}' G ′ L L L R R R
公开参数 ¶ G ⃗ , H ⃗ ∈ G n \vec{G}, \vec{H}\in\mathbb{G}^n G , H ∈ G n U , T ∈ G U, T\in\mathbb{G} U , T ∈ G
公共输入 ¶ P = a ⃗ G ⃗ + b ⃗ H ⃗ + c U + ρ T P = \vec{a}\vec{G} + \vec{b}\vec{H} + cU + \rho T P = a G + b H + c U + ρT
Witnesses ：a ⃗ , b ⃗ ∈ Z p n \vec{a}, \vec{b}\in\mathbb{Z}^n_p a , b ∈ Z p n c ∈ Z p c\in \mathbb{Z}_p c ∈ Z p
第一步（承诺步） ：Prover 发送两个遮罩向量的承诺 P 0 P_0 P 0 C 1 C_1 C 1 C 2 C_2 C 2
P 0 = a ⃗ 0 G ⃗ + b ⃗ 0 H ⃗ + ρ 0 T P_0=\vec{a}_0\vec{G} + \vec{b}_0\vec{H} + \rho_{0}T P 0 = a 0 G + b 0 H + ρ 0 T C 1 = a ⃗ 0 ⋅ b ⃗ 0 ⋅ U + ρ 1 T C_1=\vec{a}_0\cdot\vec{b}_0\cdot{}U + \rho_{1}T C 1 = a 0 ⋅ b 0 ⋅ U + ρ 1 T C 2 = ( a ⃗ ⋅ b ⃗ 0 + a ⃗ 0 ⋅ b ⃗ ) ⋅ U + ρ 2 T C_2 = (\vec{a}\cdot\vec{b}_0 + \vec{a}_0\cdot\vec{b})\cdot U + \rho_{2}T C 2 = ( a ⋅ b 0 + a 0 ⋅ b ) ⋅ U + ρ 2 T 第二步（挑战） ：Verifier 回复一个挑战数 z z z
第三步 ：Prover 计算 z z z a ⃗ ′ \vec{a}' a ′ b ⃗ ′ \vec{b}' b ′ ρ ′ \rho' ρ ′ ρ c \rho_c ρ c
a ⃗ ′ = a ⃗ + z a ⃗ 0 \vec{a}' = \vec{a} + z\vec{a}_0 a ′ = a + z a 0 b ⃗ ′ = b ⃗ + z b ⃗ 0 \vec{b}' = \vec{b} + z\vec{b}_0 b ′ = b + z b 0 ρ ′ = ρ + z ρ 0 \rho' = \rho + z\rho_0 ρ ′ = ρ + z ρ 0 ρ c = z 2 ρ 1 + z ρ 2 \rho_c = z^2\rho_1 + z\rho_2 ρ c = z 2 ρ 1 + z ρ 2 Verifier 可以计算得到 P ′ P' P ′
P ′ = P + z P 0 + z C 2 + z 2 C 1 − ρ c T P' = P + zP_0 + zC_2 + z^2C_1 - \rho_cT P ′ = P + z P 0 + z C 2 + z 2 C 1 − ρ c T 于是，Prover 和 Verifier 可以接着运行 rIPA 协议，证明 a ⃗ ′ ⋅ b ⃗ ′ = ? c ′ \vec{a}'\cdot\vec{b}'\overset{?}{=}c' a ′ ⋅ b ′ = ? c ′ P ′ = a ⃗ ′ G ⃗ + b ⃗ ′ H ⃗ + ( a ⃗ ′ ⋅ b ⃗ ′ ) U + ρ ′ T P' = \vec{a}'\vec{G} + \vec{b}'\vec{H} + (\vec{a}'\cdot\vec{b}')U + \rho'T P ′ = a ′ G + b ′ H + ( a ′ ⋅ b ′ ) U + ρ ′ T
5. 完整协议 ¶ 下面是结合了递归折叠与 Square-root IPA 的完整协议，这个协议支持 Zero-Knowledge 性质。如果不需要的 ZK 性质，直接去除 H H H ρ \rho ρ
公开参数 ¶ G 0 , G 1 , G 2 , … , G 2 n − 1 , H , U ∈ G G_0, G_1, G_2, \ldots, G_{2^n-1}, H, U \in \mathbb{G} G 0 , G 1 , G 2 , … , G 2 n − 1 , H , U ∈ G 计算承诺 ¶ Prover 把 a ⃗ \vec{a} a M a ∈ F p h × l M_a\in\mathbb{F}_p^{h\times l} M a ∈ F p h × l M a = [ a 0 a 1 a 2 ⋯ a l − 1 a l a l + 1 a l + 2 ⋯ a 2 l − 1 a 2 l a 2 l + 1 a 2 l + 2 ⋯ a 3 l − 1 a ( h − 1 ) l a ( h − 1 ) l + 1 a ( h − 1 ) l + 2 ⋯ a h l − 1 ] M_a =
\begin{bmatrix}
a_0 & a_1 & a_2 & \cdots & a_{l-1} \\
a_l & a_{l+1} & a_{l+2} & \cdots & a_{2l-1} \\
a_{2l} & a_{2l+1} & a_{2l+2} & \cdots & a_{3l-1} \\
a_{(h-1)l} & a_{(h-1)l+1} & a_{(h-1)l+2} & \cdots & a_{hl-1} \\
\end{bmatrix} M a = ⎣ ⎡ a 0 a l a 2 l a ( h − 1 ) l a 1 a l + 1 a 2 l + 1 a ( h − 1 ) l + 1 a 2 a l + 2 a 2 l + 2 a ( h − 1 ) l + 2 ⋯ ⋯ ⋯ ⋯ a l − 1 a 2 l − 1 a 3 l − 1 a h l − 1 ⎦ ⎤ Prover 按行计算承诺 C 0 , C 1 , . . . , C h − 1 C_0, C_1, ..., C_{h-1} C 0 , C 1 , ... , C h − 1 C 0 = c m ( a 0 , a 1 , . . . , a l − 1 ; ρ 0 ) C 1 = c m ( a l , a l + 1 , . . . , a 2 l − 1 ; ρ 1 ) C 2 = c m ( a 2 l , a 2 l + 1 , . . . , a 3 l − 1 ; ρ 2 ) ⋯ = ⋯ C h − 1 = c m ( a ( h − 1 ) l , a ( h − 1 ) l + 1 , . . . , a h l − 1 ; ρ h − 1 ) \begin{aligned}
C_0 &= \mathsf{cm}(a_0, a_1, ..., a_{l-1}; \rho_0) \\
C_1 &= \mathsf{cm}(a_l, a_{l+1}, ..., a_{2l-1}; \rho_1) \\
C_2 &= \mathsf{cm}(a_{2l}, a_{2l+1}, ..., a_{3l-1}; \rho_2) \\
\cdots\ &=\quad \cdots \\
C_{h-1} &= \mathsf{cm}(a_{(h-1)l}, a_{(h-1)l+1}, ..., a_{hl-1}; \rho_{h-1}) \\
\end{aligned} C 0 C 1 C 2 ⋯ C h − 1 = cm ( a 0 , a 1 , ... , a l − 1 ; ρ 0 ) = cm ( a l , a l + 1 , ... , a 2 l − 1 ; ρ 1 ) = cm ( a 2 l , a 2 l + 1 , ... , a 3 l − 1 ; ρ 2 ) = ⋯ = cm ( a ( h − 1 ) l , a ( h − 1 ) l + 1 , ... , a h l − 1 ; ρ h − 1 ) 这里的 c m ( a ⃗ ; ρ ) \mathsf{cm}(\vec{a};\rho) cm ( a ; ρ )
c m ( a ⃗ ; ρ ) = ∑ i = 0 l − 1 a i G i + ρ H \mathsf{cm}(\vec{a};\rho) = \sum_{i=0}^{l-1} a_iG_i + \rho H cm ( a ; ρ ) = i = 0 ∑ l − 1 a i G i + ρ H Evaluation证明协议 ¶ 公共输入 ¶ a ⃗ \vec{a} a ( C 0 , C 1 , . . . , C h − 1 ) (C_0, C_1, ..., C_{h-1}) ( C 0 , C 1 , ... , C h − 1 ) u ⃗ = ( u 0 , u 1 , . . . , u n − 1 ) = u ⃗ L ∥ u ⃗ R \vec{u}=(u_0, u_1, ..., u_{n-1})=\vec{u}_L \parallel \vec{u}_R u = ( u 0 , u 1 , ... , u n − 1 ) = u L ∥ u R ∣ u ⃗ L ∣ = log ( l ) |\vec{u}_L|=\log(l) ∣ u L ∣ = log ( l ) ∣ u ⃗ R ∣ = log ( h ) |\vec{u}_R|=\log(h) ∣ u R ∣ = log ( h ) v = f ~ ( u 0 , u 1 , . . . , u n − 1 ) v=\tilde{f}(u_0, u_1, ..., u_{n-1}) v = f ~ ( u 0 , u 1 , ... , u n − 1 ) Witness ¶ a ⃗ \vec{a} a ( ρ 0 , ρ 1 , . . . , ρ h − 1 ) (\rho_0, \rho_1, ..., \rho_{h-1}) ( ρ 0 , ρ 1 , ... , ρ h − 1 ) 证明协议 ¶ Round 1 ¶ Prover 计算 e ⃗ \vec{e} e e 0 = e q ~ ( b i t s ( 0 ) , u ⃗ R ) e 1 = e q ~ ( b i t s ( 1 ) , u ⃗ R ) ⋯ = ⋯ e h − 1 = e q ~ ( b i t s ( h − 1 ) , u ⃗ R ) \begin{split}
e_0 &= \tilde{eq}(\mathsf{bits}(0), \vec{u}_R) \\
e_1 &= \tilde{eq}(\mathsf{bits}(1), \vec{u}_R) \\
\cdots\ &=\quad \cdots \\
e_{h-1} &= \tilde{eq}(\mathsf{bits}(h-1), \vec{u}_R) \\
\end{split} e 0 e 1 ⋯ e h − 1 = e q ~ ( bits ( 0 ) , u R ) = e q ~ ( bits ( 1 ) , u R ) = ⋯ = e q ~ ( bits ( h − 1 ) , u R ) Prover 计算 e ⃗ \vec{e} e M a M_a M a b ⃗ \vec{b} b l l l b 0 = ⟨ e ⃗ , ( a 0 , a l , . . . , a ( h − 1 ) l ) ⟩ b 1 = ⟨ e ⃗ , ( a 1 , a l + 1 , . . . , a ( h − 1 ) l + 1 ) ⟩ ⋯ = ⋯ b l − 1 = ⟨ e ⃗ , ( a l − 1 , a l + l − 1 , . . . , a ( h − 1 ) l + l − 1 ) ⟩ \begin{split}
b_0 &= \langle \vec{e}, (a_0, a_l, ..., a_{(h-1)l}) \rangle \\
b_1 &= \langle \vec{e}, (a_1, a_{l+1}, ..., a_{(h-1)l+1}) \rangle \\
\cdots\ &=\quad \cdots \\
b_{l-1} &= \langle \vec{e}, (a_{l-1}, a_{l+l-1}, ..., a_{(h-1)l+l-1}) \rangle \\
\end{split} b 0 b 1 ⋯ b l − 1 = ⟨ e , ( a 0 , a l , ... , a ( h − 1 ) l )⟩ = ⟨ e , ( a 1 , a l + 1 , ... , a ( h − 1 ) l + 1 )⟩ = ⋯ = ⟨ e , ( a l − 1 , a l + l − 1 , ... , a ( h − 1 ) l + l − 1 )⟩ Prover 计算 b ⃗ \vec{b} b C ∗ C^* C ∗ C ∗ = c m ( b ⃗ ; ρ ∗ ) C^* = \mathsf{cm}(\vec{b}; \rho^*) C ∗ = cm ( b ; ρ ∗ ) Round 2. ¶ Prover 和 Verifier 进行一个 IPA 协议，完成 b ⃗ \vec{b} b d ⃗ \vec{d} d d ⃗ \vec{d} d
d 0 = e q ~ ( b i t s ( 0 ) , u ⃗ L ) d 1 = e q ~ ( b i t s ( 1 ) , u ⃗ L ) ⋯ = ⋯ d h − 1 = e q ~ ( b i t s ( h − 1 ) , u ⃗ L ) \begin{split}
d_0 &= \tilde{eq}(\mathsf{bits}(0), \vec{u}_L) \\
d_1 &= \tilde{eq}(\mathsf{bits}(1), \vec{u}_L) \\
\cdots\ &=\quad \cdots \\
d_{h-1} &= \tilde{eq}(\mathsf{bits}(h-1), \vec{u}_L) \\
\end{split} d 0 d 1 ⋯ d h − 1 = e q ~ ( bits ( 0 ) , u L ) = e q ~ ( bits ( 1 ) , u L ) = ⋯ = e q ~ ( bits ( h − 1 ) , u L ) Verifier 发送一个随机数 γ \gamma γ
Prover 和 Verifier 计算 U ′ ∈ G U'\in\mathbb{G} U ′ ∈ G
U ′ = γ ⋅ U U' = \gamma\cdot U U ′ = γ ⋅ U Round 3 (Repeated i = 0 , 1 , . . . , n − 1 i=0, 1, ..., n-1 i = 0 , 1 , ... , n − 1 ¶ 先引入下面的符号，比如 b ⃗ L \vec{b}_L b L b ⃗ \vec{b} b b ⃗ R \vec{b}_R b R b ⃗ \vec{b} b
b ⃗ L ( i ) = ( b 0 ( i ) , b 1 ( i ) , . . . , b 2 n − 1 − 1 ( i ) ) b ⃗ R ( i ) = ( b 2 n − 1 ( i ) , b 2 n − 1 + 1 ( i ) , . . . , b 2 n − 1 ( i ) ) d ⃗ L ( i ) = ( d 0 ( i ) , d 1 ( i ) , . . . , d 2 n − 1 − 1 ( i ) ) d ⃗ R ( i ) = ( d 2 n − 1 ( i ) , d 2 n − 1 + 1 ( i ) , . . . , d 2 n − 1 ( i ) ) G ⃗ L ( i ) = ( G 0 ( i ) , G 1 ( i ) , . . . , G 2 n − 1 − 1 ( i ) ) G ⃗ R ( i ) = ( G 2 n − 1 ( i ) , G 2 n − 1 + 1 ( i ) , . . . , G 2 n − 1 ( i ) ) \begin{aligned}
\vec{b}^{(i)}_L &= (b^{(i)}_0, b^{(i)}_1, ..., b^{(i)}_{2^{n-1}-1}) \\
\vec{b}^{(i)}_R &= (b^{(i)}_{2^{n-1}}, b^{(i)}_{2^{n-1}+1}, ..., b^{(i)}_{2^n-1}) \\
\vec{d}^{(i)}_L &= (d^{(i)}_0, d^{(i)}_1, ..., d^{(i)}_{2^{n-1}-1}) \\
\vec{d}^{(i)}_R &= (d^{(i)}_{2^{n-1}}, d^{(i)}_{2^{n-1}+1}, ..., d^{(i)}_{2^n-1}) \\
\vec{G}^{(i)}_L &= (G^{(i)}_0, G^{(i)}_1, ..., G^{(i)}_{2^{n-1}-1}) \\
\vec{G}^{(i)}_R &= (G^{(i)}_{2^{n-1}}, G^{(i)}_{2^{n-1}+1}, ..., G^{(i)}_{2^n-1}) \\
\end{aligned} b L ( i ) b R ( i ) d L ( i ) d R ( i ) G L ( i ) G R ( i ) = ( b 0 ( i ) , b 1 ( i ) , ... , b 2 n − 1 − 1 ( i ) ) = ( b 2 n − 1 ( i ) , b 2 n − 1 + 1 ( i ) , ... , b 2 n − 1 ( i ) ) = ( d 0 ( i ) , d 1 ( i ) , ... , d 2 n − 1 − 1 ( i ) ) = ( d 2 n − 1 ( i ) , d 2 n − 1 + 1 ( i ) , ... , d 2 n − 1 ( i ) ) = ( G 0 ( i ) , G 1 ( i ) , ... , G 2 n − 1 − 1 ( i ) ) = ( G 2 n − 1 ( i ) , G 2 n − 1 + 1 ( i ) , ... , G 2 n − 1 ( i ) ) 注意这里的初始值， b ⃗ ( 0 ) = b ⃗ \vec{b}^{(0)} = \vec{b} b ( 0 ) = b d ⃗ ( 0 ) = d ⃗ \vec{d}^{(0)} = \vec{d} d ( 0 ) = d G ⃗ L ( 0 ) = G ⃗ L \vec{G}^{(0)}_L=\vec{G}_L G L ( 0 ) = G L G ⃗ R ( 0 ) = G ⃗ R \vec{G}^{(0)}_R=\vec{G}_R G R ( 0 ) = G R
Prover 发送 L ( i ) L^{(i)} L ( i ) R ( i ) R^{(i)} R ( i ) L ( i ) = c m G ⃗ L ( i ) ( b ⃗ R ( i ) ; ρ L ( i ) ) + ⟨ b ⃗ R ( i ) , d ⃗ L ( i ) ⟩ ⋅ U ′ R ( i ) = c m G ⃗ R ( i ) ( b ⃗ L ( i ) ; ρ R ( i ) ) + ⟨ b ⃗ L ( i ) , d ⃗ R ( i ) ⟩ ⋅ U ′ \begin{aligned}
L^{(i)} &= \mathsf{cm}_{\vec{G}^{(i)}_L}(\vec{b}_R^{(i)}; \rho^{(i)}_L) + \langle\vec{b}^{(i)}_R, \vec{d}^{(i)}_L\rangle\cdot{}U' \\
R^{(i)} &= \mathsf{cm}_{\vec{G}^{(i)}_R}(\vec{b}_L^{(i)}; \rho^{(i)}_R) + \langle\vec{b}^{(i)}_L, \vec{d}^{(i)}_R\rangle\cdot{}U' \\
\end{aligned} L ( i ) R ( i ) = cm G L ( i ) ( b R ( i ) ; ρ L ( i ) ) + ⟨ b R ( i ) , d L ( i ) ⟩ ⋅ U ′ = cm G R ( i ) ( b L ( i ) ; ρ R ( i ) ) + ⟨ b L ( i ) , d R ( i ) ⟩ ⋅ U ′ Verifier 发送一个随机数 μ ( i ) \mu^{(i)} μ ( i )
Prover 计算并发送下面的值：
b ⃗ ( i + 1 ) = b ⃗ L ( i ) + μ ( i ) ⋅ b ⃗ R ( i ) d ⃗ ( i + 1 ) = d ⃗ L ( i ) + μ ( i ) − 1 ⋅ d ⃗ R ( i ) \begin{aligned}
\vec{b}^{(i+1)} &= \vec{b}^{(i)}_L + \mu^{(i)}\cdot\vec{b}^{(i)}_R \\
\vec{d}^{(i+1)} &= \vec{d}^{(i)}_L + {\mu^{(i)}}^{-1}\cdot\vec{d}^{(i)}_R \\
\end{aligned} b ( i + 1 ) d ( i + 1 ) = b L ( i ) + μ ( i ) ⋅ b R ( i ) = d L ( i ) + μ ( i ) − 1 ⋅ d R ( i ) Prover 和 Verifier 计算 G ⃗ ( i + 1 ) \vec{G}^{(i+1)} G ( i + 1 ) G ⃗ ( i + 1 ) = G ⃗ L ( i ) + μ ( i ) − 1 ⋅ G ⃗ R ( i ) \begin{aligned}
\vec{G}^{(i+1)} &= \vec{G}^{(i)}_L + {\mu^{(i)}}^{-1}\cdot\vec{G}^{(i)}_R \\
\end{aligned} G ( i + 1 ) = G L ( i ) + μ ( i ) − 1 ⋅ G R ( i ) Prover 和 Verifier 递归地进行 Round 3，直到 i = n − 1 i=n-1 i = n − 1
Prover 计算
ρ ^ = ρ ∗ + ∑ i = 0 n − 1 μ ( i ) ⋅ ρ L ( i ) + μ ( i ) − 1 ⋅ ρ R ( i ) \hat{\rho} = \rho^* + \sum_{i=0}^{n-1}\mu^{(i)}\cdot\rho^{(i)}_L + {\mu^{(i)}}^{-1}\cdot\rho^{(i)}_R ρ ^ = ρ ∗ + i = 0 ∑ n − 1 μ ( i ) ⋅ ρ L ( i ) + μ ( i ) − 1 ⋅ ρ R ( i ) Round 4. ¶ Prover 计算并发送 R R R r , ρ r ∈ F p r, \rho_r\in\mathbb{F}_p r , ρ r ∈ F p R = r ⋅ ( G ( n − 1 ) + b ( n − 1 ) ⋅ U ′ ) + ρ r ⋅ H R = r\cdot(G^{(n-1)} + b^{(n-1)}\cdot{U'}) + \rho_r\cdot{}H R = r ⋅ ( G ( n − 1 ) + b ( n − 1 ) ⋅ U ′ ) + ρ r ⋅ H Round 5. ¶ Verifier 发送一个随机数 ζ ∈ F p \zeta\in\mathbb{F}_p ζ ∈ F p
Prover 计算 z z z z r z_r z r
z = r + ζ ⋅ b ( n − 1 ) z = r + \zeta\cdot b^{(n-1)} z = r + ζ ⋅ b ( n − 1 ) z r = ρ r + ζ ⋅ ρ ^ z_r = \rho_r + \zeta\cdot\hat{\rho} z r = ρ r + ζ ⋅ ρ ^ Verification ¶ Verifier 计算 C ∗ C^* C ∗ P P P C ∗ = d 0 C 0 + d 1 C 1 + . . . + d h − 1 C h − 1 C^* = d_0C_0 + d_1C_1 + ... + d_{h-1}C_{h-1} C ∗ = d 0 C 0 + d 1 C 1 + ... + d h − 1 C h − 1 P = C ∗ + ∑ i = 0 n − 1 μ ( i ) L ( i ) + μ ( i ) − 1 R ( i ) P = C^* + \sum_{i=0}^{n-1}\mu^{(i)}L^{(i)} + {\mu^{(i)}}^{-1}R^{(i)} P = C ∗ + i = 0 ∑ n − 1 μ ( i ) L ( i ) + μ ( i ) − 1 R ( i ) Verifier 验证下面的等式是否成立 R + ζ ⋅ P = ? z ⋅ ( G ( n − 1 ) + b ( n − 1 ) ⋅ U ′ ) + z r ⋅ H R + \zeta\cdot P \overset{?}{=} z\cdot (G^{(n-1)} + b^{(n-1)}\cdot{U'}) + z_r\cdot{}H R + ζ ⋅ P = ? z ⋅ ( G ( n − 1 ) + b ( n − 1 ) ⋅ U ′ ) + z r ⋅ H References ¶ [WTSTW16] Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish. “Doubly-efficient zkSNARKs without trusted setup.” In 2018 IEEE Symposium on Security and Privacy (SP), pp. 926-943. IEEE, 2018. https:// [BBB+18] Bünz, Benedikt, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. “Bulletproofs: Short proofs for confidential transactions and more.” In 2018 IEEE symposium on security and privacy (SP), pp. 315-334. IEEE, 2018. https:// [BCC+16] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting.” In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, pp. 327-357. Springer Berlin Heidelberg, 2016. https://