内积论证（inner product argument）是一种证明，用于证明证明者正确执行了内积计算。本章将展示如何为内积论证构造零知识证明。
在上一章中，我们展示了如何以零知识的方式将两个标量相乘：我们对两个一阶多项式进行承诺（commit），并证明我们正确计算了它们的乘积，然后证明一阶多项式的常数项是我们所乘的秘密因子的承诺。
如果我们多项式的系数是向量而不是标量，那么我们就可以证明我们正确计算了向量的内积。现在我们引入向量多项式 （vector polynomial）。
向量多项式：以向量为系数的多项式
以下是两个具有向量系数的多项式：
l ( x ) = [ 1 2 ] x + [ 3 4 ] r ( x ) = [ 2 3 ] x + [ 7 2 ] \begin{align*}
\mathbf{l}(x) &= \begin{bmatrix} 1 \\ 2 \end {bmatrix} x + \begin{bmatrix} 3 \\ 4 \end{bmatrix} \\
\mathbf{r}(x) &= \begin{bmatrix} 2 \\ 3 \end{bmatrix} x +\begin{bmatrix} 7 \\ 2 \end{bmatrix}
\end{align*} l ( x ) r ( x ) = [ 1 2 ] x + [ 3 4 ] = [ 2 3 ] x + [ 7 2 ]
对向量多项式进行求值会得到另一个向量。例如，l ( 2 ) \mathbf{l}(2) l ( 2 )
l ( 2 ) = [ 1 2 ] ( 2 ) + [ 3 4 ] = [ 2 4 ] + [ 3 4 ] = [ 5 8 ] \begin{align*}
\mathbf{l}(2) &= \begin{bmatrix} 1 \\ 2 \end{bmatrix} (2) + \begin{bmatrix} 3 \\ 4 \end{bmatrix}\\
&= \begin{bmatrix} 2 \\ 4 \end{bmatrix}+\begin{bmatrix} 3 \\ 4 \end{bmatrix}\\
&=\begin{bmatrix} 5 \\ 8 \end{bmatrix}
\end{align*} l ( 2 ) = [ 1 2 ] ( 2 ) + [ 3 4 ] = [ 2 4 ] + [ 3 4 ] = [ 5 8 ]
而对 r \mathbf{r} r
r ( 2 ) = [ 2 3 ] ( 2 ) + [ 7 2 ] = [ 4 6 ] + [ 7 2 ] = [ 11 8 ] \begin{align*}
\mathbf{r}(2) &= \begin{bmatrix} 2 \\ 3 \end{bmatrix} (2) + \begin{bmatrix} 7 \\ 2 \end{bmatrix}\\
&= \begin{bmatrix} 4 \\ 6 \end{bmatrix} + \begin{bmatrix} 7 \\ 2 \end{bmatrix}\\
&= \begin{bmatrix} 11 \\ 8 \end{bmatrix}
\end{align*} r ( 2 ) = [ 2 3 ] ( 2 ) + [ 7 2 ] = [ 4 6 ] + [ 7 2 ] = [ 11 8 ]
l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) x x x
向量多项式相乘
向量多项式可以像标量多项式一样相乘。例如，将 l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x )
l ( x ) r ( x ) = ( [ 1 2 ] x + [ 3 4 ] ) ( [ 2 3 ] x + [ 7 2 ] ) = [ 1 2 ] ∘ [ 2 3 ] x 2 + [ 1 2 ] ∘ [ 7 2 ] x + [ 3 4 ] ∘ [ 2 3 ] x + [ 3 4 ] ∘ [ 7 2 ] = [ 2 6 ] x 2 + [ 7 4 ] x + [ 6 12 ] x + [ 21 8 ] = [ 2 6 ] x 2 + [ 13 16 ] x + [ 21 8 ] \begin{align*}
\mathbf{l}(x)\mathbf{r}(x) &=
(\begin{bmatrix}
1\\2
\end{bmatrix}x+
\begin{bmatrix}
3\\4
\end{bmatrix})(
\begin{bmatrix}
2 \\ 3
\end{bmatrix}x +
\begin{bmatrix}
7\\2
\end{bmatrix}
)\\
&=\begin{bmatrix}
1\\2
\end{bmatrix}\circ
\begin{bmatrix}
2\\3
\end{bmatrix}x^2+
\begin{bmatrix}
1\\2
\end{bmatrix}\circ
\begin{bmatrix}
7\\2
\end{bmatrix}x+
\begin{bmatrix}
3\\4
\end{bmatrix}\circ
\begin{bmatrix}
2\\3
\end{bmatrix}x+
\begin{bmatrix}
3\\4
\end{bmatrix}\circ
\begin{bmatrix}
7\\2
\end{bmatrix}&&\\
&=\begin{bmatrix}
2\\6
\end{bmatrix}x^2+
\begin{bmatrix}
7\\4
\end{bmatrix}x+
\begin{bmatrix}
6\\12
\end{bmatrix}x+
\begin{bmatrix}
21\\8
\end{bmatrix}\\
&=\begin{bmatrix}
2\\6
\end{bmatrix}x^2+
\begin{bmatrix}
13\\16
\end{bmatrix}x+
\begin{bmatrix}
21\\8
\end{bmatrix}
\end{align*} l ( x ) r ( x ) = ( [ 1 2 ] x + [ 3 4 ] ) ( [ 2 3 ] x + [ 7 2 ] ) = [ 1 2 ] ∘ [ 2 3 ] x 2 + [ 1 2 ] ∘ [ 7 2 ] x + [ 3 4 ] ∘ [ 2 3 ] x + [ 3 4 ] ∘ [ 7 2 ] = [ 2 6 ] x 2 + [ 7 4 ] x + [ 6 12 ] x + [ 21 8 ] = [ 2 6 ] x 2 + [ 13 16 ] x + [ 21 8 ]
当我们将每个向量相乘时，我们采用阿达马乘积（Hadamard product，即逐元素乘积，用 ∘ \circ ∘
注意，如果我们将 x = 2 x = 2 x = 2
[ 2 6 ] ( 2 ) 2 + [ 13 16 ] ( 2 ) + [ 21 8 ] = [ 55 64 ] \begin{bmatrix}
2\\6
\end{bmatrix}(2)^2+
\begin{bmatrix}
13\\16
\end{bmatrix}(2)+
\begin{bmatrix}
21\\8
\end{bmatrix}=
\begin{bmatrix}
55\\64
\end{bmatrix} [ 2 6 ] ( 2 ) 2 + [ 13 16 ] ( 2 ) + [ 21 8 ] = [ 55 64 ]
这与我们计算以下等式的结果相同：
l ( 2 ) ∘ r ( 2 ) = [ 5 8 ] ∘ [ 11 8 ] = [ 55 64 ] \mathbf{l}(2)\circ\mathbf{r}(2) = \begin{bmatrix}5\\8\end{bmatrix}\circ\begin{bmatrix}11\\8\end{bmatrix}=\begin{bmatrix}55\\64\end{bmatrix} l ( 2 ) ∘ r ( 2 ) = [ 5 8 ] ∘ [ 11 8 ] = [ 55 64 ]
换句话说，将两个向量多项式相乘然后对乘积在某点求值，与分别对向量多项式求值然后对所得向量取阿达马乘积是等价的。
向量多项式的内积
为了计算两个向量多项式的内积，我们按照上述方法将它们相乘，然后将向量中的各项相加，使结果变为一个标量。我们将此操作表示为 ⟨ l ( x ) , r ( x ) ⟩ \langle \mathbf{l}(x), \mathbf{r}(x) \rangle ⟨ l ( x ) , r ( x )⟩
对于上面那两个例子中的多项式，计算过程将是：
⟨ l ( x ) , r ( x ) ⟩ = ⟨ [ 1 2 ] x + [ 3 4 ] , [ 2 3 ] x + [ 7 2 ] ⟩ \langle \mathbf{l}(x), \mathbf{r}(x) \rangle = \langle \begin{align*}\end{align*} \begin{bmatrix} 1 \\ 2 \end{bmatrix} x +\begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}2\\3\end{bmatrix}x+\begin{bmatrix}7\\2\end{bmatrix}\rangle ⟨ l ( x ) , r ( x )⟩ = ⟨ [ 1 2 ] x + [ 3 4 ] , [ 2 3 ] x + [ 7 2 ] ⟩
= ⟨ [ 1 2 ] , [ 2 3 ] ⟩ x 2 + ⟨ [ 3 4 ] , [ 2 3 ] ⟩ x + ⟨ [ 1 2 ] , [ 7 2 ] ⟩ x + ⟨ [ 3 4 ] , [ 7 2 ] ⟩ =\langle \begin{bmatrix} 1 \\ 2 \end{bmatrix},\begin{bmatrix}2 \\ 3 \end{bmatrix}\rangle x^2 + \langle \begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}2 \\ 3 \end{bmatrix}\rangle x + \langle \begin{bmatrix} 1 \\ 2 \end{bmatrix},\begin{bmatrix}7 \\ 2 \end{bmatrix}\rangle x+\langle \begin{bmatrix} 3 \\ 4 \end{bmatrix},\begin{bmatrix}7 \\ 2 \end{bmatrix}\rangle = ⟨ [ 1 2 ] , [ 2 3 ] ⟩ x 2 + ⟨ [ 3 4 ] , [ 2 3 ] ⟩ x + ⟨ [ 1 2 ] , [ 7 2 ] ⟩ x + ⟨ [ 3 4 ] , [ 7 2 ] ⟩
= ( 1 ⋅ 2 + 2 ⋅ 3 ) x 2 + ( 3 ⋅ 2 + 4 ⋅ 3 ) x + ( 1 ⋅ 7 + 2 ⋅ 2 ) x + ( 3 ⋅ 7 + 4 ⋅ 2 ) =(1\cdot2+2\cdot3)x^2+(3\cdot2+4\cdot3)x + (1\cdot7+2\cdot2) x + (3\cdot7+4\cdot2) = ( 1 ⋅ 2 + 2 ⋅ 3 ) x 2 + ( 3 ⋅ 2 + 4 ⋅ 3 ) x + ( 1 ⋅ 7 + 2 ⋅ 2 ) x + ( 3 ⋅ 7 + 4 ⋅ 2 )
= 8 x 2 + 18 x + 11 x + 29 =8x^2 + 18x + 11x + 29 = 8 x 2 + 18 x + 11 x + 29
= 8 x 2 + 29 x + 29 =8x^2 + 29x + 29 = 8 x 2 + 29 x + 29
观察可以发现，⟨ l ( 2 ) , r ( 2 ) ⟩ \langle\mathbf{l}(2), \mathbf{r}(2)\rangle ⟨ l ( 2 ) , r ( 2 )⟩ ⟨ l ( x ) , r ( x ) ⟩ \langle \mathbf{l}(x), \mathbf{r}(x)\rangle ⟨ l ( x ) , r ( x )⟩ x = 2 x = 2 x = 2 ⟨ [ 5 , 8 ] , [ 11 , 8 ] ⟩ = 119 \langle [5, 8], [11, 8]\rangle = 119 ⟨[ 5 , 8 ] , [ 11 , 8 ]⟩ = 119 8 ( 2 ) 2 + 29 ( 2 ) + 29 = 119 8(2)^2 + 29(2) + 29 = 119 8 ( 2 ) 2 + 29 ( 2 ) + 29 = 119
为什么这在通常情况下成立
假设我们以“常规”方式将向量多项式相乘——即对系数取逐元素乘积（阿达马乘积）而不是内积。每个系数的内积实际上就是每个系数的阿达马乘积各项的总和。
因此我们可以说，如果我们有两个向量多项式 l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) t ( x ) = l ( x ) r ( x ) \mathbf{t}(x)=\mathbf{l}(x)\mathbf{r}(x) t ( x ) = l ( x ) r ( x ) ⟨ l ( x ) , r ( x ) ⟩ \langle \mathbf{l}(x), \mathbf{r}(x) \rangle ⟨ l ( x ) , r ( x )⟩ t \mathbf{t} t
零知识内积证明
在上一章关于零知识乘法的内容中，我们通过证明两个线性多项式常数项的乘积等于多项式乘积中的常数项，来证明我们具有一个有效的乘法。
为了证明正确计算了内积，我们将普通多项式替换为向量多项式，并将标量多项式的乘法替换为向量多项式的内积。
其他所有内容保持不变。
算法
我们的目标是让证明者能够说服验证者，A A A a \mathbf{a} a b \mathbf{b} b V V V v v v ⟨ a , b ⟩ = v \langle \mathbf{a}, \mathbf{b} \rangle = v ⟨ a , b ⟩ = v a \mathbf{a} a b \mathbf{b} b v v v
设置
证明者和验证者就以下参数达成一致：
证明者用于承诺向量的基向量 （basis vectors）G \mathbf{G} G H \mathbf{H} H
椭圆曲线点 G G G G \mathbf{G} G t ( x ) t(x) t ( x ) V V V
用于盲化项（blinding terms）的椭圆曲线点 B B B
证明者
证明者生成盲化项 α \alpha α β \beta β γ \gamma γ τ 1 \tau_1 τ 1 τ 2 \tau_2 τ 2
A = ⟨ a , G ⟩ + ⟨ b , H ⟩ + α B S = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + β B V = v G + γ B T 1 = ( ⟨ a , s R ⟩ + ⟨ b , s L ⟩ ) G + τ 1 B T 2 = ⟨ s L , s R ⟩ G + τ 2 B \begin{align}
A &= \langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\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 \\
T_1 &= (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle )G + \tau_1B\\
T_2 &= \langle\mathbf{s}_L,\mathbf{s}_R\rangle G + \tau_2B
\end{align} A S V T 1 T 2 = ⟨ a , G ⟩ + ⟨ b , H ⟩ + α B = ⟨ s L , G ⟩ + ⟨ s R , H ⟩ + βB = v G + γ B = (⟨ a , s R ⟩ + ⟨ b , s L ⟩) G + τ 1 B = ⟨ s L , s R ⟩ G + τ 2 B
注意，这次线性系数 s L \mathbf{s}_L s L s R \mathbf{s}_R s R ( A , S , V , T 1 , T 2 ) (A, S, V, T_1, T_2) ( A , S , V , T 1 , T 2 ) u u u u u u l ( x ) \mathbf{l}(x) l ( x ) r ( x ) \mathbf{r}(x) r ( x ) t ( x ) \mathbf{t}(x) t ( x )
l u = l ( u ) = a + s L u r u = r ( u ) = b + s R u t u = v + ( ⟨ a , s R ⟩ + ⟨ b , s L ⟩ ) u + ⟨ s L , s R ⟩ u 2 π l r = α + β u π t = γ + τ 1 u + τ 2 u 2 \begin{align*}
\mathbf{l}_u &= \mathbf{l}(u)=\mathbf{a} + \mathbf{s}_Lu \\
\mathbf{r}_u &= \mathbf{r}(u)=\mathbf{b} + \mathbf{s}_Ru \\
t_u &= v + (\langle\mathbf{a},\mathbf{s}_R\rangle + \langle\mathbf{b},\mathbf{s}_L\rangle)u + \langle\mathbf{s}_L,\mathbf{s}_R\rangle u^2\\
\pi_{lr} &=\alpha+\beta u\\
\pi_t &= \gamma + \tau_1u + \tau_2u^2\\
\end{align*} l u r u t u π l r π t = l ( u ) = a + s L u = r ( u ) = b + s R u = v + (⟨ a , s R ⟩ + ⟨ b , s L ⟩) u + ⟨ s L , s R ⟩ u 2 = α + β u = γ + τ 1 u + τ 2 u 2
最终验证步骤
首先，验证者检查 t u t_u t u l u \mathbf{l}_u l u r u \mathbf{r}_u r u u u u
t u = ? ⟨ l u , r u ⟩ t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle t u = ? ⟨ l u , r u ⟩
如果证明者是诚实的，这个等式应该成立，因为多项式在 u u u l x \mathbf{l}_x l x r x \mathbf{r}_x r x x = u x = u x = u
其次，验证者检查 A A A S S S l \mathbf{l} l r \mathbf{r} r
A + S u = ? ⟨ l u , G ⟩ + ⟨ r u , H ⟩ + π l r B A + Su \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B A + S u = ? ⟨ l u , G ⟩ + ⟨ r u , H ⟩ + π l r B
回顾一下，A A A S S S l \mathbf{l} l r \mathbf{r} r π l r \pi_{lr} π l r A A A S S S α \alpha α β \beta β
最后，验证者检查 t u t_u t u V , T 1 , T 2 V, T_1, T_2 V , T 1 , T 2
t u G + π t B = ? V + T 1 u + T 2 u 2 t_uG + \pi_tB \stackrel{?}{=} V + T_1 u + T_2 u^2 t u G + π t B = ? V + T 1 u + T 2 u 2
优化证明大小
当证明者发送 ( l , r , t , T 1 , T 2 , π ) (\mathbf{l}, \mathbf{r}, t, T_1, T_2, \pi) ( l , r , t , T 1 , T 2 , π ) 2 n 2n 2 n l \mathbf{l} l r \mathbf{r} r
在接下来的章节中，我们将学习如何减小证明的大小。我们可以创建一个大小为 log n \log n log n n n n log n \log n log n
具体而言，我们将通过发送对 l u \mathbf{l}_u l u r u \mathbf{r}_u r u 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 ⟩ A + S u = ? ⟨ l u , G ⟩ + ⟨ r u , H ⟩ + π l r B A + Su \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle + \pi_{lr} B A + S u = ? ⟨ l u , G ⟩ + ⟨ r u , H ⟩ + π l r B
总结
我们描述了一个协议，该协议能够证明 A A A a \mathbf{a} a b \mathbf{b} b V V V v v v ⟨ a , b ⟩ = v \langle \mathbf{a}, \mathbf{b} \rangle = v ⟨ a , b ⟩ = v a \mathbf{a} a b \mathbf{b} b v v v ( l u , r u , t , T 1 , T 2 , π l r , π t ) (\mathbf{l}_u, \mathbf{r}_u, t, T_1, T_2, \pi_{lr},\pi_t) ( l u , r u , t , T 1 , T 2 , π l r , π t ) l u \mathbf{l}_u l u r u \mathbf{r}_u r u n n n
练习： 填写缺失的代码以实现在本节课中的算法。在不泄露 n = 4 n=4 n = 4
Copy import numpy as np a = np.array([ 1 , 2 , 3 , 4 ]) b = np.array([ 2 , 2 , 2 , 2 ]) print (a + b) # np.array([3,4,5,6]) print (a * b) # np.array([2,4,6,8]) print (numpy.inner(a, b)) # 20 # casting a numpy array to numpy doesn't do anything print (np.array(a) + b) # np.array([3,4,5,6]) 填写以下代码：
Copy from py_ecc.bn128 import G1, multiply, add, FQ , eq, Z1 from py_ecc.bn128 import curve_order as p import numpy as np from functools import reduce import random def random_element (): return random.randint( 0 , p) def add_points ( * points): return reduce (add, points, Z1) # if points = G1, G2, G3, G4 and scalars = a,b,c,d vector_commit returns # aG1 + bG2 + cG3 + dG4 def vector_commit (points, scalars): return reduce (add, [multiply(P, i) for P, i in zip (points, scalars)], Z1) # these EC points have unknown discrete logs: G = [(FQ( 6286155310766333871795042970372566906087502116590250812133967451320632869759 ), FQ( 2167390362195738854837661032213065766665495464946848931705307210578191331138 )), (FQ( 6981010364086016896956769942642952706715308592529989685498391604818592148727 ), FQ( 8391728260743032188974275148610213338920590040698592463908691408719331517047 )), (FQ( 15884001095869889564203381122824453959747209506336645297496580404216889561240 ), FQ( 14397810633193722880623034635043699457129665948506123809325193598213289127838 )), (FQ( 6756792584920245352684519836070422133746350830019496743562729072905353421352 ), FQ( 3439606165356845334365677247963536173939840949797525638557303009070611741415 ))] H = [(FQ( 13728162449721098615672844430261112538072166300311022796820929618959450231493 ), FQ( 12153831869428634344429877091952509453770659237731690203490954547715195222919 )), (FQ( 17471368056527239558513938898018115153923978020864896155502359766132274520000 ), FQ( 4119036649831316606545646423655922855925839689145200049841234351186746829602 )), (FQ( 8730867317615040501447514540731627986093652356953339319572790273814347116534 ), FQ( 14893717982647482203420298569283769907955720318948910457352917488298566832491 )), (FQ( 419294495583131907906527833396935901898733653748716080944177732964425683442 ), FQ( 14467906227467164575975695599962977164932514254303603096093942297417329342836 ))] B = (FQ( 12848606535045587128788889317230751518392478691112375569775390095112330602489 ), FQ( 18818936887558347291494629972517132071247847502517774285883500818572856935411 )) # scalar multiplication example: multiply(G, 42) # EC addition example: add(multiply(G, 42), multiply(G, 100)) # remember to do all arithmetic modulo p def commit (a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2): pass # return (A, S, V, T1, T2) def evaluate (f_0, f_1, f_2, u): return (f_0 + f_1 * u + f_2 * u ** 2 ) % p def prove (blinding_0, blinding_1, blinding_2, u): # fill this in # return pi pass ## step 0: Prover and verifier agree on G and B ## step 1: Prover creates the commitments a = np.array([ 89 , 15 , 90 , 22 ]) b = np.array([ 16 , 18 , 54 , 12 ]) sL = ... sR = ... t1 = ... t2 = ... ### blinding terms alpha = ... beta = ... gamma = ... tau_1 = ... tau_2 = ... A, S, V, T1, T2 = commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2) ## step 2: Verifier picks u u = ... ## step 3: Prover evaluates l(u), r(u), t(u) and creates evaluation proofs l_u = evaluate(a, sL, 0 , u) r_u = evaluate(b, sR, 0 , u) t_u = evaluate(np.inner(a, b), t1, t2, u) pi_lr = prove(alpha, beta, 0 , u) pi_t = prove(gamma, tau_1, tau_2, u) ## step 4: Verifier accepts or rejects assert t_u == np.mod(np.inner(np.array(l_u), np.array(r_u)), p), "tu !=〈lu, ru〉" assert eq(add(A, commit(S, u)), add_points(vector_commit(G, l_u), vector_commit(H, r_u), multiply(B, pi_lr))), "l_u or r_u not evaluated correctly" assert eq(add(multiply(G, t_u), multiply(B, pi_t)), add_points(V, multiply(T1, u), multiply(T2, u ** 2 % p))), "t_u not evaluated correctly" 本教程是 ZK Bulletproofs 系列的一部分。