在博客 Pointproofs: Aggregating Proofs for Multiple Vector Commitments 学习笔记1 中，主要对 Alogrand团队Gorbunov等人2020年论文《Pointproofs: Aggregating Proofs for Multiple Vector Commitments 》做了一个总体的梳理。该论文在 Libert和Yung 2010年论文《Concise mercurial vector commitments and independent zero-knowledge sets with short proofs 》的基础上，做了以下改进：
采用了非对称bilinear pairing group，并针对G 1 \mathbb{G}_1 G 1 G 2 \mathbb{G}_2 G 2 G T \mathbb{G}_T G T r = ( ∑ i ∈ S m i t i ) − 1 m o d p r=(\sum_{i\in S}m_it_i)^{-1}\ mod\ p r = ( ∑ i ∈ S m i t i ) − 1 m o d p G T \mathbb{G}_T G T G 1 \mathbb{G}_1 G 1
采用Random Oracle Model，基于hash函数H H H t i = H ( i , C , S , m ⃗ [ S ] ) t_i=H(i,C,S,\vec{m}[S]) t i = H ( i , C , S , m [ S ] ) H H H H ′ H' H ′ t j , i = H ( i , C j , S j , m ⃗ j [ S j ] ) t_{j,i}=H(i,C_j,S_j,\vec{m}_j[S_j]) t j , i = H ( i , C j , S j , m j [ S j ] ) t j ′ = H ′ ( j , { C j , S j , m ⃗ j [ S j ] } j ∈ [ l ] ) t_j'=H'(j,\{C_j,S_j,\vec{m}_j[S_j]\}_{j\in[l]}) t j ′ = H ′ ( j , { C j , S j , m j [ S j ] } j ∈ [ l ] )
本博客将重点关注：
proof of correctness/binding for same-commitment aggregation
proof of correctness/binding for cross-commitment aggregation
same-commitment aggregation from CDH-like assumption
weak binding and realization
cross-commitment aggregation from polynomial commitments
https://github.com/algorand/pointproofs 代码解析
该论文实现的binding属性是基于AGW+ROM model under the l l l Pointproofs: Aggregating Proofs for Multiple Vector Commitments 学习笔记1 1.1节内容）
具体的实现为：
Setup(1 λ , 1 N 1^{\lambda},1^N 1 λ , 1 N α ← Z p \alpha\leftarrow \mathbb{Z}_p α ← Z p a ⃗ = ( α , α 2 , ⋯ , α N ) \vec{a}=(\alpha,\alpha^2,\cdots,\alpha^N) a = ( α , α 2 , ⋯ , α N ) g 1 a ⃗ = ( g 1 α , ⋯ , g 1 α N ) g_1^{\vec{a}}=(g_1^\alpha,\cdots,g_1^{\alpha^N}) g 1 a = ( g 1 α , ⋯ , g 1 α N ) g 1 α N a ⃗ [ − 1 ] = ( g 1 α N + 2 , ⋯ , g 1 α 2 N ) g_1^{\alpha^N\vec{a}[-1]}=(g_1^{\alpha^{N+2}},\cdots,g_1^{\alpha^{2N}}) g 1 α N a [ − 1 ] = ( g 1 α N + 2 , ⋯ , g 1 α 2 N ) g 2 a ⃗ = ( g 2 α , ⋯ , g 2 α N ) g_2^{\vec{a}}=(g_2^\alpha,\cdots,g_2^{\alpha^N}) g 2 a = ( g 2 α , ⋯ , g 2 α N ) g T α N + 1 = e ( g 1 α , g 2 α N ) g_T^{\alpha^{N+1}}=e(g_1^{\alpha},g_2^{\alpha^N}) g T α N + 1 = e ( g 1 α , g 2 α N ) g 1 a ⃗ ， g 1 α N a ⃗ [ − 1 ] g_1^{\vec{a}}，g_1^{\alpha^N\vec{a}[-1]} g 1 a ， g 1 α N a [ − 1 ] g 2 a ⃗ , g T α N + 1 g_2^{\vec{a}},g_T^{\alpha^{N+1}} g 2 a , g T α N + 1 α \alpha α
Commit(m ⃗ \vec{m} m m ⃗ ∈ Z p N \vec{m}\in \mathbb{Z}_p^N m ∈ Z p N C = g 1 m ⃗ T a ⃗ = g 1 ∑ i ∈ S m i α i C=g_1^{\vec{m}^T\vec{a}}=g_1^{\sum_{i\in S}m_i\alpha^i} C = g 1 m T a = g 1 ∑ i ∈ S m i α i
UpdateCommit(C , S , m ⃗ [ S ] , m ⃗ ′ [ S ] C,S,\vec{m}[S],\vec{m}'[S] C , S , m [ S ] , m ′ [ S ] C ′ = C ⋅ g 1 ( m ⃗ ′ [ S ] − m ⃗ [ S ] ) T a ⃗ [ S ] = C ⋅ g 1 ∑ i ∈ S ( m i ′ − m i ) α i C'=C\cdot g_1^{(\vec{m}'[S]-\vec{m}[S])^T\vec{a}[S]}=C\cdot g_1^{\sum_{i\in S}(m_i'-m_i)\alpha^i} C ′ = C ⋅ g 1 ( m ′ [ S ] − m [ S ] ) T a [ S ] = C ⋅ g 1 ∑ i ∈ S ( m i ′ − m i ) α i
Prove(i , m ⃗ i,\vec{m} i , m i i i π i = g 1 α N + 1 − i m ⃗ [ − i ] T a ⃗ [ − i ] = g 1 ∑ j ∈ [ N ] − { i } m j α N + 1 − i + j \pi_i=g_1^{\alpha^{N+1-i}\vec{m}[-i]^T\vec{a}[-i]}=g_1^{\sum_{j\in [N]-\{i\}}m_j\alpha^{N+1-i+j}} π i = g 1 α N + 1 − i m [ − i ] T a [ − i ] = g 1 ∑ j ∈ [ N ] − { i } m j α N + 1 − i + j g 1 α N + 1 − i a ⃗ [ − i ] g_1^{\alpha^{N+1-i}\vec{a}[-i]} g 1 α N + 1 − i a [ − i ] m j m_j m j j ≠ i j\neq i j = i m j ′ m_j' m j ′ π i ′ = π ⋅ g 1 ( m j ′ − m j ) α N + 1 − i + j \pi_i'=\pi\cdot g_1^{(m_j'-m_j)\alpha^{N+1-i+j}} π i ′ = π ⋅ g 1 ( m j ′ − m j ) α N + 1 − i + j m i m_i m i m i ′ m_i' m i ′ π i ′ = π i \pi_i'=\pi_i π i ′ = π i C C C C ′ C' C ′
Aggregate(C , S , m ⃗ [ S ] , { π i : i ∈ S } C,S,\vec{m}[S],\{\pi_i:i\in S\} C , S , m [ S ] , { π i : i ∈ S } π ^ = ∏ i ∈ S π i t i \hat{\pi}=\prod_{i\in S}\pi_i^{t_i} π ^ = ∏ i ∈ S π i t i t i = H ( i , C , S , m ⃗ [ S ] ) t_i=H(i,C,S,\vec{m}[S]) t i = H ( i , C , S , m [ S ] )
Verify(C , S , m ⃗ [ S ] , π ^ C,S,\vec{m}[S],\hat{\pi} C , S , m [ S ] , π ^ e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i e(C,g_2^{\sum_{i\in S}\alpha^{N+1-i}t_i})=e(\hat{\pi},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}m_it_i} e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i t i = H ( i , C , S , m ⃗ [ S ] ) t_i=H(i,C,S,\vec{m}[S]) t i = H ( i , C , S , m [ S ] )
对于任意的i ∈ [ N ] , π i = P r o v e ( i , m ⃗ ) = g 1 α N + 1 − i m ⃗ [ − i ] T a ⃗ [ − i ] i\in [N],\pi_i=Prove(i,\vec{m})=g_1^{\alpha^{N+1-i}\vec{m}[-i]^T\vec{a}[-i]} i ∈ [ N ] , π i = P r o v e ( i , m ) = g 1 α N + 1 − i m [ − i ] T a [ − i ] Commit/Prove/Aggregate/Verify整个流程，可分两步证明：
1）证明e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i e(C,g_2^{\alpha^{N+1-i}})=e(\pi_i,g_2)\cdot g_T^{\alpha^{N+1}m_i} e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i
2）证明e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i e(C,g_2^{\sum_{i\in S}\alpha^{N+1-i}t_i})=e(\hat{\pi},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}m_it_i} e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i
具体为：m ⃗ T a ⃗ = m ⃗ [ − i ] T a ⃗ [ − i ] + α i m i \vec{m}^T\vec{a}=\vec{m}[-i]^T\vec{a}[-i]+\alpha^im_i m T a = m [ − i ] T a [ − i ] + α i m i α N + 1 − i \alpha^{N+1-i} α N + 1 − i ( m ⃗ T a ⃗ ) α N + 1 − i = α N + 1 − i m ⃗ [ − i ] T a ⃗ [ − i ] + α N + 1 m i (\vec{m}^T\vec{a})\alpha^{N+1-i}=\alpha^{N+1-i}\vec{m}[-i]^T\vec{a}[-i]+\alpha^{N+1}m_i ( m T a ) α N + 1 − i = α N + 1 − i m [ − i ] T a [ − i ] + α N + 1 m i e ( g 1 m ⃗ T a ⃗ , g 2 α N + 1 − i ) = e ( g 1 α N + 1 − i m ⃗ [ − i ] T a ⃗ [ − i ] , g 2 ) ⋅ g T α N + 1 m i e(g_1^{\vec{m}^T\vec{a}},g_2^{\alpha^{N+1-i}})=e(g_1^{\alpha^{N+1-i}\vec{m}[-i]^T\vec{a}[-i]},g_2)\cdot g_T^{\alpha^{N+1}m_i} e ( g 1 m T a , g 2 α N + 1 − i ) = e ( g 1 α N + 1 − i m [ − i ] T a [ − i ] , g 2 ) ⋅ g T α N + 1 m i e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i e(C,g_2^{\alpha^{N+1-i}})=e(\pi_i,g_2)\cdot g_T^{\alpha^{N+1}m_i} e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i
2）在e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i e(C,g_2^{\alpha^{N+1-i}})=e(\pi_i,g_2)\cdot g_T^{\alpha^{N+1}m_i} e ( C , g 2 α N + 1 − i ) = e ( π i , g 2 ) ⋅ g T α N + 1 m i t i t_i t i e ( C , g 2 α N + 1 − i t i ) = e ( π i t i , g 2 ) ⋅ g T α N + 1 m i t i e(C,g_2^{\alpha^{N+1-i}t_i})=e(\pi_i^{t_i},g_2)\cdot g_T^{\alpha^{N+1}m_it_i} e ( C , g 2 α N + 1 − i t i ) = e ( π i t i , g 2 ) ⋅ g T α N + 1 m i t i S S S i ∈ S i\in S i ∈ S e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( ∏ i ∈ S π i t i , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i e(C,g_2^{\sum_{i\in S}\alpha^{N+1-i}t_i})=e(\prod_{i\in S}\pi_i^{t_i},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}m_it_i}=e(\hat{\pi},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}m_it_i} e ( C , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( ∏ i ∈ S π i t i , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i
证明UpdateCommit算法正确性的思路为：m ⃗ ′ T a ⃗ = ( m ⃗ ′ [ S ] − m ⃗ [ S ] ) T a ⃗ [ S ] + m ⃗ T a ⃗ \vec{m}'^T\vec{a}=(\vec{m}'[S]-\vec{m}[S])^T\vec{a}[S]+\vec{m}^T\vec{a} m ′ T a = ( m ′ [ S ] − m [ S ] ) T a [ S ] + m T a
采用归谬法来证明，假设adversary 可计算C = g 1 z ⃗ T a ⃗ C=g_1^{\vec{z}^T\vec{a}} C = g 1 z T a ( S , m ⃗ [ S ] ) (S,\vec{m}[S]) ( S , m [ S ] ) π ^ \hat{\pi} π ^ m ⃗ [ S ] ≠ z ⃗ [ S ] \vec{m}[S]\neq \vec{z}[S] m [ S ] = z [ S ] π ^ \hat{\pi} π ^ e ( g 1 z ⃗ T a ⃗ , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S z i t i e(g_1^{\vec{z}^T\vec{a}},g_2^{\sum_{i\in S}\alpha^{N+1-i}t_i})=e(\hat{\pi},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}m_it_i}=e(\hat{\pi},g_2)\cdot g_T^{\alpha^{N+1}\sum_{i\in S}z_it_i} e ( g 1 z T a , g 2 ∑ i ∈ S α N + 1 − i t i ) = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S m i t i = e ( π ^ , g 2 ) ⋅ g T α N + 1 ∑ i ∈ S z i t i
注意adversary也不知道g 1 α N + 1 g_1^{\alpha^{N+1}} g 1 α N + 1 log g 1 π ^ \log_{g_1}\hat{\pi} log g 1 π ^ α N + 1 \alpha^{N+1} α N + 1 0 0 0 g T α N + 1 g_T^{\alpha^{N+1}} g T α N + 1 ∑ i ∈ S m i t i ≡ p ∑ i ∈ S z i t i \sum_{i\in S}m_it_i\equiv_p \sum_{i \in S}z_it_i ∑ i ∈ S m i t i ≡ p ∑ i ∈ S z i t i z ⃗ [ S ] T t ⃗ ≡ p m ⃗ [ S ] T t ⃗ \vec{z}[S]^T\vec{t}\equiv_p \vec{m}[S]^T\vec{t} z [ S ] T t ≡ p m [ S ] T t t ⃗ = ( H ( i , C , S , m ⃗ [ S ] ) , i ∈ S ) \vec{t}=(H(i,C,S,\vec{m}[S]),i\in S) t = ( H ( i , C , S , m [ S ] ) , i ∈ S )
假设当( S , z ⃗ [ S ] , m ⃗ [ S ] ) (S,\vec{z}[S],\vec{m}[S]) ( S , z [ S ] , m [ S ] ) t ⃗ ← Z p ∣ S ∣ \vec{t}\leftarrow \mathbb{Z}_p^{|S|} t ← Z p ∣ S ∣ Pr t ⃗ [ z ⃗ [ S ] ̸ ≡ p m ⃗ [ S ] a n d z ⃗ [ S ] T t ⃗ ≡ p m ⃗ [ S ] T t ⃗ ] = 1 / p \Pr_{\vec{t}}[\vec{z}[S]\not\equiv_p \vec{m}[S]\ and\ \vec{z}[S]^T\vec{t}\equiv_p \vec{m}[S]^T\vec{t}]=1/p Pr t [ z [ S ] ≡ p m [ S ] a n d z [ S ] T t ≡ p m [ S ] T t ] = 1 / p
因此问题的关键在于：ensure the uniform choice of t ⃗ \vec{t} t ( S , z ⃗ [ S ] , m ⃗ [ S ] ) (S,\vec{z}[S],\vec{m}[S]) ( S , z [ S ] , m [ S ] )
C C C z ⃗ \vec{z} z
C , S , m ⃗ [ S ] C,S,\vec{m}[S] C , S , m [ S ] H ( i , ⋅ , ⋅ , ⋅ ) H(i,\cdot,\cdot,\cdot) H ( i , ⋅ , ⋅ , ⋅ ) t i t_i t i
若adversary可以找到相应的m i ≠ z i m_i\neq z_i m i = z i ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i \sum_{i\in S}z_it_i\equiv_p \sum_{i \in S}m_it_i ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i
t i = H ( i , ⋅ , ⋅ , ⋅ ) t_i=H(i,\cdot,\cdot,\cdot) t i = H ( i , ⋅ , ⋅ , ⋅ ) S , m ⃗ [ S ] S,\vec{m}[S] S , m [ S ] H H H
若t i t_i t i m i m_i m i ∣ S ∣ − 1 |S|-1 ∣ S ∣ − 1 m i m_i m i ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i \sum_{i\in S}z_it_i\equiv_p \sum_{i \in S}m_it_i ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i m i m_i m i
若t i = H ( i , C ) t_i=H(i,C) t i = H ( i , C ) 2 log p 2^{\sqrt{\log p}} 2 log p { z i t i , m i t i } i ∈ [ N ] \{z_it_i,m_it_i\}_{i \in [N]} { z i t i , m i t i } i ∈ [ N ] S S S 2 log p 2^{\sqrt{\log p}} 2 log p ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i \sum_{i\in S}z_it_i\equiv_p \sum_{i \in S}m_it_i ∑ i ∈ S z i t i ≡ p ∑ i ∈ S m i t i log p ≈ 256 \log p\approx 256 log p ≈ 2 5 6 2 log p ≈ 2 16 2^{\sqrt{\log p}}\approx 2^{16} 2 log p ≈ 2 1 6
若t i = H ( i , C , S ) t_i=H(i,C,S) t i = H ( i , C , S ) t i = H ( i , C ) t_i=H(i,C) t i = H ( i , C ) t i = H ( i , C , S ) t_i = H(i, C, S) t i = H ( i , C , S ) ∑ i ∈ S z i t i \sum_{i\in S} z_it_i ∑ i ∈ S z i t i m i m_i m i i ∈ S i \in S i ∈ S
