在内积证明（inner product arguments）的语境下，范围证明是指证明标量 v v v V V V n n n v v v 2 n 2^n 2 n
本文将展示 Bulletproofs 论文是如何构建这种证明的。其高层理念是，如果我们能证明向量 a L \mathbf{a}_L a L a L \mathbf{a}_L a L v v v v v v 2 n 2^n 2 n
使用 Bulletproofs 进行范围证明的优势在于，可以直接构建范围证明，而无需使用算术电路 。
Monero 使用了 Bulletproofs 范围证明 （即本文介绍的算法）来确保交易金额之和不为负数（在有限域 中，负数是指大于 p / 2 p/2 p /2 p / 2 p/2 p /2 p p p
本文是 ZK Bulletproofs 系列文章的一部分。
符号说明
0 n \mathbf{0}^n 0 n n n n
1 n \mathbf{1}^n 1 n n n n
2 n \mathbf{2}^n 2 n n n n [ 1 , 2 , 4 , 8 , . . . , 2 n − 1 ] [1,2,4,8,...,2^{n-1}] [ 1 , 2 , 4 , 8 , ... , 2 n − 1 ]
y n \mathbf{y}^n y n n n n [ 1 , y , y 2 , y 3 , . . . , y n − 1 ] [1, y, y^2, y^3, ..., y^{n-1}] [ 1 , y , y 2 , y 3 , ... , y n − 1 ]
y − n \mathbf{y}^{-n} y − n n n n [ 1 , y − 1 , y − 2 , . . . , y − ( n − 1 ) ] [1, y^{-1}, y^{-2}, ..., y^{-(n-1)}] [ 1 , y − 1 , y − 2 , ... , y − ( n − 1 ) ]
注意 y n ∘ y − n = 1 n \mathbf{y}^n\circ\mathbf{y}^{-n}=\mathbf{1}^n y n ∘ y − n = 1 n
范围证明概述
要证明 V V V 2 n 2^n 2 n
a L \mathbf{a}_L a L 0 0 0 1 1 1 内积 ⟨ a L , 2 n ⟩ = v \langle \mathbf{a}_L,\mathbf{2}^n\rangle=v ⟨ a L , 2 n ⟩ = v
第二点很容易证明，我们进行常规的内积证明，然后揭示 2 n \mathbf{2}^n 2 n 2 n \mathbf{2}^n 2 n a L \mathbf{a}_L a L
四个实用的技巧
Bulletproofs 论文隐式地使用了四个代数技巧，在直接查看范围证明算法之前，最好先显式地讲解它们。
1. 证明 a L \mathbf{a}_L a L
声明 a L \mathbf{a}_L a L
a R = a L − 1 n \mathbf{a}_R = \mathbf{a}_L-\mathbf{1}^n a R = a L − 1 n a L ∘ a R = 0 n \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n a L ∘ a R = 0 n
例如，如果 a L = [ 1 , 0 , 0 , 1 ] \mathbf{a}_L = [1,0,0,1] a L = [ 1 , 0 , 0 , 1 ] a R = [ 0 , − 1 , − 1 , 0 ] \mathbf{a}_R=[0,-1,-1,0] a R = [ 0 , − 1 , − 1 , 0 ]
在这种情况下，a L ∘ a R = 0 n \mathbf{a}_L \circ\mathbf{a}_R=\mathbf{0}^n a L ∘ a R = 0 n
[ 1 , 0 , 0 , 1 ] ∘ [ 0 , − 1 , − 1 , 0 ] = [ 0 , 0 , 0 , 0 ] = 0 n [1,0,0,1] \circ [0,-1,-1,0] = [0,0,0,0] = \mathbf{0}^n [ 1 , 0 , 0 , 1 ] ∘ [ 0 , − 1 , − 1 , 0 ] = [ 0 , 0 , 0 , 0 ] = 0 n
现在考虑 a L \mathbf{a}_L a L [ 2 , 1 , 0 , 0 ] [2, 1, 0, 0] [ 2 , 1 , 0 , 0 ] a R \mathbf{a}_R a R [ 1 , 0 , − 1 , − 1 ] [1,0,-1,-1] [ 1 , 0 , − 1 , − 1 ] a L \mathbf{a}_L a L a R \mathbf{a}_R a R [ 2 , 0 , 0 , 0 ] ≠ 0 n [2,0,0,0] \neq \mathbf{0}^n [ 2 , 0 , 0 , 0 ] = 0 n
更一般地说，如果 a L \mathbf{a}_L a L 1 1 1 a R \mathbf{a}_R a R a L \mathbf{a}_L a L a R \mathbf{a}_R a R a L ∘ a R ≠ 0 n \mathbf{a}_L \circ \mathbf{a}_R \neq \mathbf{0}^n a L ∘ a R = 0 n
然而，如果 a L \mathbf{a}_L a L 1 1 1 a R \mathbf{a}_R a R 0 0 0
最后，如果 a L \mathbf{a}_L a L 0 0 0 a R \mathbf{a}_R a R − 1 -1 − 1
因此，如果 a L \mathbf{a}_L a L a R \mathbf{a}_R a R a R = a L − 1 \mathbf{a}_R = \mathbf{a}_L-\mathbf{1} a R = a L − 1 a L ∘ a R = 0 n \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n a L ∘ a R = 0 n
2. 证明一个向量为全零
假设我们希望证明 Pedersen 承诺 A A A A = ⟨ a , G ⟩ + α B A = \langle\mathbf{a},\mathbf{G}\rangle + \alpha B A = ⟨ a , G ⟩ + α B a = 0 n \mathbf{a}=\mathbf{0}^n a = 0 n
看起来仅仅发送盲化因子 α \alpha α
相反，证明者将 A A A r \mathbf{r} r
⟨ a , r ⟩ = 0 \langle\mathbf{a},\mathbf{r}\rangle = 0 ⟨ a , r ⟩ = 0
请注意，这是一个概率测试。在 a ≠ 0 n \mathbf{a}\neq\mathbf{0}^n a = 0 n ⟨ a , r ⟩ = 0 \langle\mathbf{a},\mathbf{r}\rangle=0 ⟨ a , r ⟩ = 0 a \mathbf{a} a r \mathbf{r} r
然而，传输 r \mathbf{r} r O ( n ) \mathcal{O}(n) O ( n ) y y y y n \mathbf{y}^n y n y n \mathbf{y}^n y n
然后，证明者证明 ⟨ a , y n ⟩ = 0 \langle\mathbf{a},\mathbf{y}^n\rangle=0 ⟨ a , y n ⟩ = 0
3. 证明内积具有 ⟨ a L , a R ∘ y n ⟩ \langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle ⟨ a L , a R ∘ y n ⟩ y y y y n \mathbf{y}^n y n
我们还没有机制来证明 a L ∘ a R = 0 n \mathbf{a}_L\circ\mathbf{a}_R=\mathbf{0}^n a L ∘ a R = 0 n a L ∘ a R \mathbf{a}_L\circ\mathbf{a}_R a L ∘ a R 0 n \mathbf{0}^n 0 n ⟨ a L ∘ a R , y n ⟩ = 0 \langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=0 ⟨ a L ∘ a R , y n ⟩ = 0 a R \mathbf{a}_R a R ⟨ a L , a R ∘ y n ⟩ = 0 \langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=0 ⟨ a L , a R ∘ y n ⟩ = 0
验证者将收到对 a L \mathbf{a}_L a L a R \mathbf{a}_R a R a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n
我们所依赖的关键技巧是，证明者使用基向量 G \mathbf{G} G H \mathbf{H} H G \mathbf{G} G H ∘ y − n \mathbf{H}\circ\mathbf{y}^{-n} H ∘ y − n
当证明者发送求值结果 r u \mathbf{r}_u r u y n \mathbf{y}^n y n y − n ∘ H \mathbf{y}^{-n}\circ\mathbf{H} y − n ∘ H y − n \mathbf{y}^{-n} y − n
具体来说，证明者构建承诺
A = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B S = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B \begin{align*}
A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B\\
S &= \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B
\end{align*} A S = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB
并将 ( A , S ) (A, S) ( A , S ) V V V V V V
证明者的多项式将是
l ( x ) = a L + s L x r ( x ) = a R ∘ y n + s R ∘ y n x \begin{align*}
\mathbf{l}(x)&=\mathbf{a}_L + \mathbf{s}_Lx\\
\mathbf{r}(x)&=\mathbf{a}_R\circ\mathbf{y}^n + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x
\end{align*} l ( x ) r ( x ) = a L + s L x = a R ∘ y n + s R ∘ y n x
关键在于，证明者将 s R \mathbf{s}_R s R y n \mathbf{y}^n y n r ( x ) \mathbf{r}(x) r ( x ) r ( x ) = a R ∘ y n + s R x \mathbf{r}(x)=\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{s}_Rx r ( x ) = a R ∘ y n + s R x y n ∘ s R \mathbf{y}^n\circ\mathbf{s}_R y n ∘ s R ⟨ r u , y − n ∘ H ⟩ \langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle ⟨ r u , y − n ∘ H ⟩ y n \mathbf{y}^n y n r u \mathbf{r}_u r u ( a R + s R u ) ∘ y n (\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n ( a R + s R u ) ∘ y n ⟨ ( a R + s R u ) ∘ y n , y − n ∘ H ⟩ \langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle ⟨( a R + s R u ) ∘ y n , y − n ∘ H ⟩ y n \mathbf{y}^n y n
⟨ ( a R + s R u ) ∘ y n , y − n ∘ H ⟩ = ⟨ ( a R + s R u ) , y n ∘ y − n ∘ H ⟩ = ⟨ ( a R + s R u ) , 1 n ∘ H ⟩ = ⟨ ( a R + s R u ) , H ⟩ \begin{align*}
&\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\
&=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{y}^n\circ\mathbf{y}^{-n}\circ\mathbf{H}\rangle\\
&=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{1}^n\circ\mathbf{H}\rangle\\
&=\langle(\mathbf{a}_R+\mathbf{s}_Ru),\mathbf{H}\rangle
\end{align*} ⟨( a R + s R u ) ∘ y n , y − n ∘ H ⟩ = ⟨( a R + s R u ) , y n ∘ y − n ∘ H ⟩ = ⟨( a R + s R u ) , 1 n ∘ H ⟩ = ⟨( a R + s R u ) , H ⟩
然而，证明者现在还不能计算 l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) y y y ( A , S ) (A, S) ( A , S ) y y y y n \mathbf{y}^n y n t ( x ) t(x) t ( x )
t ( x ) = ⟨ l ( x ) , r ( x ) ⟩ = ⟨ a L , a R ∘ y n ⟩ + t 1 x + t 2 x 2 t(x)=\langle\mathbf{l}(x),\mathbf{r}(x)\rangle=\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle+t_1x+t_2x^2 t ( x ) = ⟨ l ( x ) , r ( x )⟩ = ⟨ a L , a R ∘ y n ⟩ + t 1 x + t 2 x 2
其中
t 1 = ⟨ a L , s R ∘ y n ⟩ + ⟨ s L , a R ∘ y n ⟩ t 2 = ⟨ s L , s R ∘ y n ⟩ \begin{align*}
t_1&=\langle\mathbf{a}_L,\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle\\
t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y}
^n\rangle
\end{align*} t 1 t 2 = ⟨ a L , s R ∘ y n ⟩ + ⟨ s L , a R ∘ y n ⟩ = ⟨ s L , s R ∘ y n ⟩
证明者将系数 t 1 t_1 t 1 t 2 t_2 t 2
T 1 = t 1 G + τ 1 B T 2 = t 2 G + τ 2 B \begin{align*}
T_1&=t_1G+\tau_1B\\
T_2&=t_2G+\tau_2B
\end{align*} T 1 T 2 = t 1 G + τ 1 B = t 2 G + τ 2 B
并将 ( T 1 , T 2 ) (T_1, T_2) ( T 1 , T 2 ) u u u l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x )
l u = a L + s L u r u = a R ∘ y n + ( s R ∘ y n ) u t u = ⟨ l u , r u ⟩ π l r = α + β u π t = τ 1 u + τ 2 u 2 \begin{align*}
\mathbf{l}_u&= \mathbf{a}_L+\mathbf{s}_Lu\\
\mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+(\mathbf{s}_R\circ\mathbf{y}^n)u\\
t_u&=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\
\pi_{lr}&=\alpha + \beta u\\
\pi_t&=\tau_1u+\tau_2u^2
\end{align*} l u r u t u π l r π t = a L + s L u = a R ∘ y n + ( s R ∘ y n ) u = ⟨ l u , r u ⟩ = α + β u = τ 1 u + τ 2 u 2
注意，π t \pi_t π t t 1 t_1 t 1 t 2 t_2 t 2 π t \pi_t π t γ + τ 1 u + τ 2 u 2 \gamma + \tau_1u+\tau_2u^2 γ + τ 1 u + τ 2 u 2 γ \gamma γ V V V t ( x ) t(x) t ( x )
这里没有盲化因子 γ \gamma γ V V V v v v 0 0 0 ( l u , r u , t u , π l r , π t ) (\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t) ( l u , r u , t u , π l r , π t )
t u = ? ⟨ l u , r u ⟩ A + S u = ? ⟨ l u , G ⟩ + ⟨ r u , y − n ∘ H ⟩ + π l r B t u G = ? T 1 u + T 2 u 2 − π t B \begin{align*}
t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\
A+Su&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\
t_uG&\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B\\
\end{align*} t u A + S u t u G = ? ⟨ l u , r u ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , y − n ∘ H ⟩ + π l r B = ? T 1 u + T 2 u 2 − π t B
第一个关键区别是，由于之前讨论的原因，对 r u \mathbf{r}_u r u y − n ∘ H \mathbf{y}^{-n}\circ\mathbf{H} y − n ∘ H H \mathbf{H} H
其次，t u G = ? T 1 u + T 2 u 2 − π t B t_uG\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B t u G = ? T 1 u + T 2 u 2 − π t B t u G = ? V + T 1 u + T 2 u 2 − π t B t_uG\stackrel{?}{=} \boxed{V}+T_1 u + T_2 u^2 - \pi_t B t u G = ? V + T 1 u + T 2 u 2 − π t B V V V 0 0 0
一般来说，如果 V V V V V V
4. 在涉及加法公开常数的情况下证明内积
正如上一节所暗示的，如果验证者知道底层向量，验证者就可以重构承诺。
例如，假设我们要证明
⟨ a L + j , a R ∘ y n + k ⟩ = v z \langle\mathbf{a}_L + \mathbf{j},\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}\rangle=vz ⟨ a L + j , a R ∘ y n + k ⟩ = v z
其中 j \mathbf{j} j k \mathbf{k} k z z z y n \mathbf{y}^n y n k \mathbf{k} k y n \mathbf{y}^n y n
证明者仍然像往常一样只对秘密值 a L \mathbf{a}_L a L a R \mathbf{a}_R a R v v v
A = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B S = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B V = v G + γ B \begin{align*}
A &= \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B\\
S &= \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B\\
V &= vG + \gamma B
\end{align*} A S V = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB = v G + γ B
像往常一样，多项式 l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) s L \mathbf{s}_L s L s R \mathbf{s}_R s R y y y y n \mathbf{y}^n y n l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x )
l ( x ) = a L + j ⏟ left vector + s L x r ( x ) = a R ∘ y n + k ⏟ right vector + s R ∘ y n x \begin{align*}
\mathbf{l}(x)&=\underbrace{\mathbf{a}_L + \mathbf{j}}_\text{left vector} + \mathbf{s}_Lx\\
\mathbf{r}(x)&=\underbrace{\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}}_\text{right vector} + \boxed{\mathbf{s}_R\circ\mathbf{y}^n}x
\end{align*} l ( x ) r ( x ) = left vector a L + j + s L x = right vector a R ∘ y n + k + s R ∘ y n x
请注意，k \mathbf{k} k y n \mathbf{y}^n y n s R \mathbf{s}_R s R
目前，我们将 t ( x ) t(x) t ( x )
t ( x ) = v z + t 1 x + t 2 x 2 t(x)=vz+t_1x+t_2x^2 t ( x ) = v z + t 1 x + t 2 x 2
其中
t 1 = ⟨ a L + j , s R ∘ y n ⟩ + ⟨ s L , a R ∘ y n + k ⟩ t 2 = ⟨ s L , s R ∘ y n ⟩ \begin{align*}
t_1&=\langle\mathbf{a}_L+\mathbf{j},\mathbf{s}_R\circ\mathbf{y}^n\rangle + \langle\mathbf{s}_L,\mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}\rangle\\
t_2&=\langle\mathbf{s}_L,\mathbf{s}_R\circ\mathbf{y}
^n\rangle
\end{align*} t 1 t 2 = ⟨ a L + j , s R ∘ y n ⟩ + ⟨ s L , a R ∘ y n + k ⟩ = ⟨ s L , s R ∘ y n ⟩
注意 t ( x ) t(x) t ( x ) v z vz v z v v v
T 1 = t 1 G + τ 1 B T 2 = t 2 G + τ 2 B \begin{align*}
T_1 &= t_1G+\tau_1B\\
T_2 &= t_2G+\tau_2B\\
\end{align*} T 1 T 2 = t 1 G + τ 1 B = t 2 G + τ 2 B
并发送给验证者，然后验证者发送随机值 u u u
证明者计算：
l u = a L ∘ y n + j + ( s L ∘ y n ) u r u = a R ∘ y n + k + s R u t u = ⟨ l u , r u ⟩ π l r = α + β u π t = v z + τ 1 u + τ 2 u 2 \begin{align*}
\mathbf{l}_u&= \mathbf{a}_L\circ\mathbf{y}^n+\mathbf{j}+(\mathbf{s}_L\circ\mathbf{y}^n)u\\
\mathbf{r}_u&= \mathbf{a}_R\circ\mathbf{y}^n+\mathbf{k}+\mathbf{s}_Ru\\
t_u&=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\
\pi_{lr}&=\alpha + \beta u\\
\pi_t&=vz+\tau_1u+\tau_2u^2
\end{align*} l u r u t u π l r π t = a L ∘ y n + j + ( s L ∘ y n ) u = a R ∘ y n + k + s R u = ⟨ l u , r u ⟩ = α + β u = v z + τ 1 u + τ 2 u 2
注意 π t \pi_t π t γ z \gamma z γ z ( l u , r u , t u , π l r , π t ) (\mathbf{l}_u,\mathbf{r}_u,t_u,\pi_{lr},\pi_t) ( l u , r u , t u , π l r , π t )
t u = ? ⟨ l u , r u ⟩ A + S u + ⟨ j , G ⟩ ⏟ commitment to j in l ( x ) + ⟨ k , y − n ∘ H ⟩ ⏟ commitment to k in r ( x ) = ? ⟨ l u , G ⟩ + ⟨ r u , y − n ∘ H ⟩ + π l r B t u G = ? V z + T 1 u + T 2 u 2 − π t B \begin{align*}
t_u&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle\\
A+Su+\underbrace{\langle\mathbf{j,\mathbf{G}}\rangle}_{\text{commitment to } \mathbf{j} \text{ in } \mathbf{l}(x)}+\underbrace{\langle\mathbf{k},\mathbf{y}^{-n}\circ\mathbf{H}\rangle}_{\text{commitment to } \mathbf{k} \text{ in } \mathbf{r}(x)}&\stackrel{?}=\langle\mathbf{l}_u,\mathbf{G}\rangle+\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle+\pi_{lr}B\\
t_uG&\stackrel{?}{=} Vz+ T_1 u + T_2 u^2 - \pi_t B\\
\end{align*} t u A + S u + commitment to j in l ( x ) ⟨ j , G ⟩ + commitment to k in r ( x ) ⟨ k , y − n ∘ H ⟩ t u G = ? ⟨ l u , r u ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , y − n ∘ H ⟩ + π l r B = ? V z + T 1 u + T 2 u 2 − π t B
l u \mathbf{l}_u l u r u \mathbf{r}_u r u j \mathbf{j} j k \mathbf{k} k A A A S S S A A A S S S k \mathbf{k} k y − n ∘ H \mathbf{y}^{-n}\circ\mathbf{H} y − n ∘ H k \mathbf{k} k k ∘ y − n \mathbf{k}\circ\mathbf{y}^{-n} k ∘ y − n y − n ∘ H \mathbf{y}^{-n}\circ\mathbf{H} y − n ∘ H π t \pi_t π t v z vz v z V V V z z z V V V z z z
通过计算 ⟨ j , G ⟩ \langle\mathbf{j},\mathbf{G}\rangle ⟨ j , G ⟩ ⟨ k , y n ∘ H ⟩ \langle\mathbf{k},\mathbf{y}^n\circ\mathbf{H}\rangle ⟨ k , y n ∘ H ⟩ V z Vz V z
范围证明
为了证明 V V V 2 n 2^n 2 n
内积 ⟨ a L , 2 n ⟩ = V \langle \mathbf{a}_L,\mathbf{2}^n\rangle = V ⟨ a L , 2 n ⟩ = V a L \mathbf{a}_L a L v v v
a R = a L − 1 \mathbf{a}_R=\mathbf{a}_L-\mathbf{1} a R = a L − 1 a L ∘ a R = 0 \mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0} a L ∘ a R = 0
最后两个声明并不直接采用内积的形式。然而，我们可以稍微修改它们以实现这一目标。我们实际上要表达的是，向量
a R − a L + 1 \mathbf{a}_R - \mathbf{a}_L+\mathbf{1} a R − a L + 1 a L ∘ a R \mathbf{a}_L\circ\mathbf{a}_R a L ∘ a R
都是 0 n \mathbf{0}^n 0 n
⟨ a L ∘ a R , y n ⟩ = 0 \langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0} ⟨ a L ∘ a R , y n ⟩ = 0
和
⟨ a R − a L + 1 , y n ⟩ = 0 \langle \mathbf{a}_R - \mathbf{a}_L+\mathbf{1},\mathbf{y}^n\rangle=\mathbf{0} ⟨ a R − a L + 1 , y n ⟩ = 0
其中 y n \mathbf{y}^n y n y y y
原始的 Bulletproofs 论文对第一个声明进行了如下微调，以便我们可以使用上一节中的第三个技巧：
⟨ a L , a R ∘ y n ⟩ = 0 \langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0} ⟨ a L , a R ∘ y n ⟩ = 0
因此，证明者需要建立三个内积：
⟨ a L , 2 n ⟩ = v \langle \mathbf{a}_L,\mathbf{2}^n\rangle = v ⟨ a L , 2 n ⟩ = v ⟨ a L , a R ∘ y n ⟩ = 0 n \langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}^n ⟨ a L , a R ∘ y n ⟩ = 0 n ⟨ a L − 1 n − a R , y n ⟩ = 0 n \langle\mathbf{a}_L -\mathbf{1}^n- \mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}^n ⟨ a L − 1 n − a R , y n ⟩ = 0 n
将三个内积合并为一个
使用由验证者提供的随机数 z z z
z 2 ⋅ ⟨ a L , 2 n ⟩ + z 1 ⋅ ⟨ a L − 1 n − a R , y n ⟩ + z 0 ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v + z 1 ⋅ 0 n + z 0 ⋅ 0 n z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z^1 \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + z^0\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v + z^1\cdot\mathbf{0}^n+z^0\cdot\mathbf{0}^n z 2 ⋅ ⟨ a L , 2 n ⟩ + z 1 ⋅ ⟨ a L − 1 n − a R , y n ⟩ + z 0 ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v + z 1 ⋅ 0 n + z 0 ⋅ 0 n
z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v z^2 \cdot \langle \mathbf{a_L}, 2^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
通过一些非常繁琐的内积代数运算，我们可以如下合并所有的内积。我们将在附录中展示推导过程。
⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩ \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + (z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩
下面方框中的项包含验证者已知的值，因此我们将构建验证算法来显式检查这些值。也就是说，由验证者（而不是证明者）计算对框内各项值的承诺：
⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩ \left\langle \mathbf{a_L} - \boxed{z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle} ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩
为了节省篇幅，Bulletproofs 论文将项 ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩ (z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ 1 n , 2 n ⟩ δ ( y , z ) \delta(y,z) δ ( y , z )
⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z ) \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z) ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z )
注意 δ ( y , z ) \delta(y,z) δ ( y , z )
范围证明算法
证明者选择 v v v a L \mathbf{a}_L a L a R = a L − 1 \mathbf{a}_R = \mathbf{a}_L - \mathbf{1} a R = a L − 1
证明者然后随机选择盲化因子 α \alpha α G \mathbf{G} G H \mathbf{H} H a L \mathbf{a}_L a L a R \mathbf{a}_R a R
A = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B A = \langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B A = ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B
证明者随后选择即将创建的向量多项式 l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) s L \mathbf{s}_L s L s R \mathbf{s}_R s R
S = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B S = \langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B S = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB
证明者将内积承诺为 V V V G G G G \mathbf{G} G
V = v G + γ B V = vG+\gamma B V = v G + γ B
证明者将 ( A , S , V ) (A, S, V) ( A , S , V )
验证者回复随机值 ( y , z ) (y, z) ( y , z )
⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z ) \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle = z^2 \cdot v + \delta(y,z) ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z )
内积的左半部分 a L − z ⋅ 1 \mathbf{a}_L-z\cdot\mathbf{1} a L − z ⋅ 1 l ( x ) \mathbf{l}(x) l ( x ) y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n \mathbf{y}^n \circ\mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n r ( x ) \mathbf{r}(x) r ( x )
因此，我们将 l ( x ) \mathbf{l}(x) l ( x )
l ( x ) = a L − z ⋅ 1 ⏟ constant term + s L x \mathbf{l}(x)=\underbrace{\mathbf{a}_L-z\cdot\mathbf{1}}_\text{constant term}+\mathbf{s}_Lx l ( x ) = constant term a L − z ⋅ 1 + s L x
并将 r ( x ) \mathbf{r}(x) r ( x )
r ( x ) = y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n ⏟ constant term + y n ∘ s R x \mathbf{r}(x)=\underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n}_\text{constant term}+\mathbf{y}^n\circ\mathbf{s}_Rx r ( x ) = constant term y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x
注意，出于上面前置条件部分第 3 点所讨论的原因，我们将 s R x \mathbf{s}_Rx s R x y n \mathbf{y}^n y n
证明者现在可以构造 t ( x ) = ⟨ l ( x ) , r ( x ) ⟩ t(x) = \langle\mathbf{l}(x),\mathbf{r}(x)\rangle t ( x ) = ⟨ l ( x ) , r ( x )⟩ t 0 t_0 t 0 t 1 t_1 t 1 t 2 t_2 t 2
t 0 = ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ t 1 = ⟨ ( a L − z ⋅ 1 ) , y n ∘ s R ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n , s L ⟩ t 2 = ⟨ s L , y n ∘ s R ⟩ \begin{align*}
t_0 &= \left\langle \mathbf{a_L} - z \cdot \mathbf{1}^n, \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n \right\rangle\\
t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\
t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle
\end{align*} t 0 t 1 t 2 = ⟨ a L − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = ⟨( a L − z ⋅ 1 ) , y n ∘ s R ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n , s L ⟩ = ⟨ s L , y n ∘ s R ⟩
其中 t ( x ) = t 0 + t 1 x + t 2 x 2 t(x) = t_0 + t_1x + t_2x^2 t ( x ) = t 0 + t 1 x + t 2 x 2
证明者发送对 t 1 t_1 t 1 t 2 t_2 t 2
T 1 = t 1 G + τ 1 B T 2 = t 2 G + τ 2 B \begin{align*}
T_1 &= t_1G+\tau_1B\\
T_2 &= t_2G+\tau_2B
\end{align*} T 1 T 2 = t 1 G + τ 1 B = t 2 G + τ 2 B
不需要对 t 0 t_0 t 0 V V V
验证者发送随机数 u u u
l u = l ( u ) r u = r ( u ) t u = t ( u ) π l r = α + β u π t = z 2 γ + τ 1 u + τ 2 u 2 \begin{align*}
\mathbf{l}_u &= \mathbf{l}(u) \\
\mathbf{r}_u &= \mathbf{r}(u) \\
t_u &= \mathbf{t}(u)\\
\pi_{lr} &=\alpha+\beta u\\
\pi_t &= z^2\gamma + \tau_1u + \tau_2u^2\\
\end{align*} l u r u t u π l r π t = l ( u ) = r ( u ) = t ( u ) = α + β u = z 2 γ + τ 1 u + τ 2 u 2
注意，π t \pi_t π t z 2 z^2 z 2 z 2 ⋅ v z^2\cdot v z 2 ⋅ v
验证者随后计算新的基向量 H y − 1 = y − n ∘ H \mathbf{H}_{\mathbf{y}^{-1}}=\mathbf{y}^{-n}\circ\mathbf{H} H y − 1 = y − n ∘ H
t u = ? ⟨ l u , r u ⟩ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle t u = ? ⟨ l u , r u ⟩
A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , H y − 1 ⟩ + π l r B A + Su + \boxed{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \boxed{\langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , H y − 1 ⟩ + π l r B
t u G + π t B = V z 2 + δ ( y , z ) ⋅ G + T 1 u + T 2 u 2 t_uG+\pi_tB=V\boxed{z^2}+\boxed{\delta(y,z)}\cdot G+T_1u+T_2u^2 t u G + π t B = V z 2 + δ ( y , z ) ⋅ G + T 1 u + T 2 u 2
回顾一下，证明者并没有对用于内积左右两侧的完整向量进行承诺，而只承诺了 a L \mathbf{a}_L a L b L \mathbf{b}_L b L
作为提醒，以下是原始内积，验证者已知的值已加框标出：
⟨ a L + − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z ) \left\langle \mathbf{a_L} + \boxed{-z \cdot \mathbf{1}^n}, \mathbf{y}^n \circ \mathbf{a_R} + \boxed{\mathbf{y}^n\cdot z + z^2 \cdot 2^n }\right\rangle = \boxed{z^2} \cdot v + \boxed{\delta(y,z)} ⟨ a L + − z ⋅ 1 n , y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z )
建议读者验证：在原始内积中加框的项（验证者已知的值）已经在上述的一组等式检查中，由验证者在框内各项里进行了重构。
通过复制证明者的部分计算，验证者可以断言证明者确实如其所称的那样执行了计算。
验证算法的正确性
我们现在展示，如果证明者是诚实的，那么最终的验证检查是完全正确的。
下面我们将展示精确的代数运算，但从直觉上看，验证者是在“重构”内积的左向量 a L − z ⋅ 1 n \mathbf{a_L} - z \cdot \mathbf{1}^n a L − z ⋅ 1 n y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n z 2 v + δ ( y , z ) z^2v+\delta(y,z) z 2 v + δ ( y , z )
验证者并没有被给出对 a L − z ⋅ 1 n \mathbf{a_L} - z \cdot \mathbf{1}^n a L − z ⋅ 1 n y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n a L \mathbf{a}_L a L a R \mathbf{a}_R a R z 2 v + δ ( y , z ) z^2v + \delta(y,z) z 2 v + δ ( y , z ) v v v
加法项以及被 y n \mathbf{y}^n y n
t u = t ( u ) t_u = \mathbf{t}(u) t u = t ( u ) 对于 t u = ? ⟨ l u , r u ⟩ t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle t u = ? ⟨ l u , r u ⟩ t u t_u t u
关于 A A A S S S l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x )
对于A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , H y − 1 ⟩ + π l r B A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ l u , G ⟩ + ⟨ r u , H y − 1 ⟩ + π l r B
我们做以下替换：
⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B ⏟ A + ( ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B ) ⏟ S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a L − z ⋅ 1 + s L u ⏟ l u , G ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x ⏟ r u , H y − 1 ⟩ + ( α + β u ) ⏟ π l r B \underbrace{\langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B}_A + \underbrace{(\langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)}_Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \underbrace{\mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_Lu}_{\mathbf{l}_u}, \mathbf{G} \rangle + \langle \underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_Rx}_{\mathbf{r}_u}, \mathbf{H}_{y^{-1}} \rangle + \underbrace{(\alpha+\beta u)}_{\pi_{lr}} B A ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B + S (⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB ) u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ l u a L − z ⋅ 1 + s L u , G ⟩ + ⟨ r u y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + π l r ( α + β u ) B
所有 G \mathbf{G} G
⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B + ( ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B ) u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a L − z ⋅ 1 + s L u , G ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B \cancel{\langle\mathbf{a}_L,\mathbf{G}\rangle}+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\cancel{\langle\mathbf{s}_L,\mathbf{G}\rangle}+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \cancel{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_L u, \mathbf{G} \rangle} + \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B ⟨ a L , G ⟩ + ⟨ a R , H ⟩ + α B + ( ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB ) u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a L − z ⋅ 1 + s L u , G ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B
⟨ a R , H ⟩ + α B + ( ⟨ s R , H ⟩ + β B ) u + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B \langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B ⟨ a R , H ⟩ + α B + (⟨ s R , H ⟩ + βB ) u + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B
与 B B B
⟨ a R , H ⟩ + α B + ( ⟨ s R , H ⟩ + β B ) u + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B \langle\mathbf{a}_R,\mathbf{H}\rangle+\cancel{\alpha B} + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\cancel{\beta B)u} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + \cancel{(\alpha+\beta u) B} ⟨ a R , H ⟩ + α B + (⟨ s R , H ⟩ + βB ) u + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R x , H y − 1 ⟩ + ( α + β u ) B
⟨ a R , H ⟩ + ( ⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R u , H y − 1 ⟩ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R u, \mathbf{H}_{y^{-1}} \rangle ⟨ a R , H ⟩ + (⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n + y n ∘ s R u , H y − 1 ⟩
H y − 1 \mathbf{H}_{y^{-1}} H y − 1 y n \mathbf{y}^n y n
⟨ a R , H ⟩ + ( ⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R + z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R+z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle ⟨ a R , H ⟩ + (⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R + z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩
拆分内积：
⟨ a R , H ⟩ + ( ⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R , H ⟩ + ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩ \langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R,\mathbf{H}\rangle+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle ⟨ a R , H ⟩ + (⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R , H ⟩ + ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩
抵消等式两侧都出现的项：
⟨ a R , H ⟩ + ( ⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R , H ⟩ + ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩ \cancel{\langle\mathbf{a}_R,\mathbf{H}\rangle} + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_R,\mathbf{H}\rangle}+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle ⟨ a R , H ⟩ + (⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ a R , H ⟩ + ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩
( ⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩ \cancel{(\langle\mathbf{s}_R,\mathbf{H}\rangle u)} + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle\mathbf{s}_R u, \mathbf{H} \rangle} (⟨ s R , H ⟩ u ) + ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 2 n , H y − 1 ⟩ + ⟨ s R u , H ⟩
⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle} \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\cancel{\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle} ⟨ z ⋅ y n , H y − 1 ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩ + ⟨ z 2 ⋅ 2 n , H y − 1 ⟩
⟨ z ⋅ y n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩ \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle ⟨ z ⋅ y n , H y − 1 ⟩ = ? ⟨ z ⋅ 1 , H ⟩
将 y n \mathbf{y}^n y n
⟨ z ⋅ 1 , H ⟩ = ? ⟨ z ⋅ 1 , H ⟩ \langle z\cdot\mathbf{1},\mathbf{H}\rangle \stackrel{?}{=}\langle z\cdot\mathbf{1},\mathbf{H}\rangle ⟨ z ⋅ 1 , H ⟩ = ? ⟨ z ⋅ 1 , H ⟩
⟨ z ⋅ 1 , H ⟩ = ? ⟨ z ⋅ 1 , H ⟩ \cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} \stackrel{?}{=}\cancel{\langle z\cdot\mathbf{1},\mathbf{H}\rangle} ⟨ z ⋅ 1 , H ⟩ = ? ⟨ z ⋅ 1 , H ⟩
t ( u ) t(u) t ( u ) 要看出
t u G + π t B = V z 2 + δ ( y , z ) G + T 1 u + T 2 u 2 t_uG+\pi_tB=Vz^2+\delta(y,z)G+T_1u+T_2u^2 t u G + π t B = V z 2 + δ ( y , z ) G + T 1 u + T 2 u 2
是正确的，我们可以如下代入各项：
⟨ l u , r u ⟩ ⏟ t u G + ( z 2 γ + τ 1 u + τ 2 u 2 ) ⏟ π t B = ( v G + γ B ) ⏟ V z 2 + δ ( y , z ) G + ( t 1 G + τ 1 B ⏟ T 1 ) u + ( t 2 G + τ 2 B ) ⏟ T 2 u 2 \underbrace{\langle \mathbf{l}_u, \mathbf{r}_u \rangle}_{t_u}G+\underbrace{(z^2\gamma + \tau_1u + \tau_2u^2)}_{\pi_t}B=\underbrace{(vG+\gamma B)}_{V}z^2+\delta(y,z)G+\underbrace{(t_1G+\tau_1B}_{T_1})u+\underbrace{(t_2G+\tau_2B)}_{T_2}u^2 t u ⟨ l u , r u ⟩ G + π t ( z 2 γ + τ 1 u + τ 2 u 2 ) B = V ( v G + γ B ) z 2 + δ ( y , z ) G + T 1 ( t 1 G + τ 1 B ) u + T 2 ( t 2 G + τ 2 B ) u 2
其中 l u \mathbf{l}_u l u r u \mathbf{r}_u r u t 1 t_1 t 1 t 2 t_2 t 2
l u = a L − z ⋅ 1 n r u = y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n t 1 = ⟨ ( a L − z ⋅ 1 ) , y n ∘ s R ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n , s L ⟩ t 2 = ⟨ s L , y n ∘ s R ⟩ \begin{align*}
\mathbf{l}_u &= \mathbf{a_L} - z \cdot \mathbf{1}^n\\
\mathbf{r}_u &= \mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n\\
t_1 &= \langle(\mathbf{a}_L-z\cdot\mathbf{1}),\mathbf{y}^n\circ\mathbf{s}_R\rangle+\langle\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n,\mathbf{s_L}\rangle\\
t_2 &= \langle\mathbf{s}_L,\mathbf{y}^n\circ\mathbf{s}_R\rangle
\end{align*} l u r u t 1 t 2 = a L − z ⋅ 1 n = y n ∘ a R + y n ⋅ z + z 2 ⋅ 2 n = ⟨( a L − z ⋅ 1 ) , y n ∘ s R ⟩ + ⟨ y n ∘ ( a R + z ⋅ 1 ) + z 2 2 n , s L ⟩ = ⟨ s L , y n ∘ s R ⟩ 然而，这样的代数运算将极其混乱。相反，我们观察到 z 2 v + δ ( y , z ) G z^2v+\delta(y,z)G z 2 v + δ ( y , z ) G ⟨ l ( x ) , r ( x ) ⟩ \langle\mathbf{l}(x),\mathbf{r}(x)\rangle ⟨ l ( x ) , r ( x )⟩ V V V γ B \gamma B γ B π t \pi_t π t z 2 γ z^2\gamma z 2 γ V z 2 = ( v G + γ B ) z 2 Vz^2 = (vG + \gamma B)z^2 V z 2 = ( v G + γ B ) z 2
因为 Pedersen 承诺是加法同态的，验证者可以简单地计算 δ ( y , z ) G \delta(y,z)G δ ( y , z ) G V z 2 Vz^2 V z 2 t ( x ) t(x) t ( x )
对数级大小的范围证明
我们可以通过发送一个对 l u \mathbf{l}_u l u r u \mathbf{r}_u r u C C C t u t_u t u
A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ − π l r B = ? C A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle-\pi_{lr}B\stackrel{?}{=} C A + S u + ⟨ − z ⋅ 1 n , G ⟩ + ⟨ z ⋅ y n + z 2 ⋅ 2 n , H y − 1 ⟩ − π l r B = ? C
以及
t u = ? ⟨ l u , r u ⟩ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle t u = ? ⟨ l u , r u ⟩
是相对于基向量 G \mathbf{G} G H y − 1 \mathbf{H}_{\mathbf{y}^{-1}} H y − 1
将范围证明算法应用于子集和问题
子集和问题 提出这样的问题：“给定一组数字，是否存在一个子集（可能包括整个集合）的总和为 k k k k = 16 k = 16 k = 16 { 3 , 5 , 7 , 11 } \set{3,5,7,11} { 3 , 5 , 7 , 11 } 5 + 11 = 16 5 + 11 = 16 5 + 11 = 16 k = 13 k=13 k = 13
子集和问题是一个 NP-Complete（NP完全）问题，这意味着，类似于布尔电路或算术电路，它可以表示NP 中的任何问题。也就是说，NP中的任何问题都可以重写（技术术语为“归约（reduced） ”）为一个子集和问题实例。
通过将 2 n \mathbf{2}^n 2 n [ 3 , 5 , 7 , 11 ] [3,5,7,11] [ 3 , 5 , 7 , 11 ] k = 16 k=16 k = 16 a L = [ 0 , 1 , 0 , 1 ] \mathbf{a}_L= [0,1,0,1] a L = [ 0 , 1 , 0 , 1 ] a L \mathbf{a}_L a L
因此，Bulletproofs 能够为 NP 中的任何问题证明对任何见证（witness）的知识。
附录：将三个内积合并为一个的推导
从三个内积开始
z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
我们将展示如何使用之前学过的内积代数来推导最终结果
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩
中间项可以被拆分为独立的内积：
z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle + \boxed{z \cdot \langle \mathbf{a_L} - \mathbf{1}^n - \mathbf{a_R}, \mathbf{y}^n \rangle} + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 \cdot v z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L − 1 n − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L , y n ⟩ + z ⋅ ⟨ − 1 n , y n ⟩ + z ⋅ ⟨ − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v z^2 \cdot \langle \mathbf{a_L}, \mathbf{2}^n \rangle+\boxed{z\cdot\langle\mathbf{a}_L,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{1}^n,\mathbf{y}^n\rangle+z\cdot\langle-\mathbf{a}_R,\mathbf{y}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle=z^2\cdot v z 2 ⋅ ⟨ a L , 2 n ⟩ + z ⋅ ⟨ a L , y n ⟩ + z ⋅ ⟨ − 1 n , y n ⟩ + z ⋅ ⟨ − a R , y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
我们可以把常数 z z z
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
把验证者已知的值移到右边：
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle-\mathbf{a}_R,z\cdot\mathbf{y}^n\rangle+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\boxed{\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle} ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − a R , z ⋅ y n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
将所有的 a R \mathbf{a}_R a R a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − a R ∘ y n , z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle-\mathbf{a}_R\circ\mathbf{y}^n,z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ − a R ∘ y n , z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle}+\boxed{\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a L , a R ∘ y n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a R ∘ y n , a L ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a R ∘ y n , a L ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
把 a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a R ∘ y n , a L ⟩ ⏟ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\underbrace{\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle+\langle \mathbf{a_R} \circ \mathbf{y}^n,\mathbf{a_L} \rangle} = z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ + ⟨ a R ∘ y n , a L ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_L,z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
合并左边的两个 a L \mathbf{a}_L a L
⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \boxed{\mathbf{a_L}}, z^2\cdot\mathbf{2}^n \rangle+\langle\boxed{\mathbf{a}_L},z\cdot\mathbf{y}^n\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z 2 ⋅ 2 n ⟩ + ⟨ a L , z ⋅ y n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
把左边最后一项拆分为两个内积：⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\boxed{\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L-z\cdot\mathbf{1}^n\rangle}= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,\mathbf{a}_L\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
合并 a L \mathbf{a}_L a L ⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \boxed{\mathbf{a_L}}, z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,
\boxed{\mathbf{a}_L}\rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , a L ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ \langle \mathbf{a_L}, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle+\langle\mathbf{a}_R\circ\mathbf{y}^n,-z\cdot\mathbf{1}^n\rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ a L , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ a R ∘ y n , − z ⋅ 1 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
我们可以利用规则 ⟨ x , b + c ⟩ + ⟨ b , y ⟩ = v → ⟨ x + y , b + c ⟩ = v + ⟨ y , c ⟩ \langle \mathbf{x}, \mathbf{b} + \mathbf{c}\rangle + \langle \mathbf{b}, \mathbf{y}\rangle = v \rightarrow \langle \mathbf{x} + \mathbf{y}, \mathbf{b} + \mathbf{c}\rangle = v + \langle\mathbf{y},\mathbf{c}\rangle ⟨ x , b + c ⟩ + ⟨ b , y ⟩ = v → ⟨ x + y , b + c ⟩ = v + ⟨ y , c ⟩ a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n b \mathbf{b} b a R ∘ y n \mathbf{a}_R\circ\mathbf{y}^n a R ∘ y n c \mathbf{c} c z ⋅ y n + z 2 ⋅ 2 n z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n z ⋅ y n + z 2 ⋅ 2 n y \mathbf{y} y − z ⋅ 1 n -z\cdot\mathbf{1}^n − z ⋅ 1 n
⟨ a L ⏟ x , a R ∘ y n ⏟ b + z ⋅ y n + z 2 ⋅ 2 n ⏟ c ⟩ + ⟨ a R ∘ y n ⏟ b , − z ⋅ 1 n ⏟ y ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ ⏟ v \langle \underbrace{\mathbf{a_L}}_\mathbf{x}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle+\langle\underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b},\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y}\rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v ⟨ x a L , b a R ∘ y n + c z ⋅ y n + z 2 ⋅ 2 n ⟩ + ⟨ b a R ∘ y n , y − z ⋅ 1 n ⟩ = v z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩
⟨ a L ⏟ x − z ⋅ 1 n ⏟ y , a R ∘ y n ⏟ b + z ⋅ y n + z 2 ⋅ 2 n ⏟ c ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ ⏟ v + ⟨ − z ⋅ 1 n ⏟ y , z ⋅ y n + z 2 ⋅ 2 n ⏟ c ⟩ \langle \underbrace{\mathbf{a_L}}_\mathbf{x}-\underbrace{z\cdot\mathbf{1}^n}_\mathbf{y}, \underbrace{\mathbf{a}_R\circ\mathbf{y}^n}_\mathbf{b}+\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c} \rangle= \underbrace{z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle}_v+\langle\underbrace{-z\cdot\mathbf{1}^n}_\mathbf{y},\underbrace{z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n}_\mathbf{c}\rangle ⟨ x a L − y z ⋅ 1 n , b a R ∘ y n + c z ⋅ y n + z 2 ⋅ 2 n ⟩ = v z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ y − z ⋅ 1 n , c z ⋅ y n + z 2 ⋅ 2 n ⟩
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − z ⋅ 1 n , z ⋅ y n + z 2 ⋅ 2 n ⟩ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n\rangle ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − z ⋅ 1 n , z ⋅ y n + z 2 ⋅ 2 n ⟩
我们现在拆分右边的项：
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − z ⋅ 1 n , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , z 2 ⋅ 2 n ⟩ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v-\langle-z\cdot\mathbf{1}^n,\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z\cdot\mathbf{y}^n\rangle+\langle-z\cdot\mathbf{1}^n,z^2\cdot\mathbf{2}^n\rangle ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v − ⟨ − z ⋅ 1 n , y n ⟩ + ⟨ − z ⋅ 1 n , z ⋅ y n ⟩ + ⟨ − z ⋅ 1 n , z 2 ⋅ 2 n ⟩
将右边内积中的标量提取出来：
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + z ⋅ ⟨ 1 n , y n ⟩ − z 2 ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+z\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^2\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + z ⋅ ⟨ 1 n , y n ⟩ − z 2 ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩
提取出公因子 ⟨ 1 n , y n ⟩ \langle\mathbf{1}^n,\mathbf{y}^n\rangle ⟨ 1 n , y n ⟩
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩ \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩
因为 δ ( y , z ) = ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩ \delta(y,z)=(z-z^2)\cdot\langle\mathbf{1}^n,\mathbf{y}^n\rangle-z^3\langle\cdot\mathbf{1}^n,\mathbf{2}^n\rangle δ ( y , z ) = ( z − z 2 ) ⋅ ⟨ 1 n , y n ⟩ − z 3 ⟨ ⋅ 1 n , 2 n ⟩
⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z ) \langle \mathbf{a_L}-z\cdot\mathbf{1}^n, \mathbf{a}_R\circ\mathbf{y}^n+z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n \rangle= z^2 \cdot v+\delta(y,z) ⟨ a L − z ⋅ 1 n , a R ∘ y n + z ⋅ y n + z 2 ⋅ 2 n ⟩ = z 2 ⋅ v + δ ( y , z )
推导完毕。■ \blacksquare ■