# Aggregatable Subvector Commitment with Efficient Updates
## 2 Preliminaries
### Vector Commitment  
Informally, VC allows the submission of an ordered sequence of values that can be subsequently verified against a specific position. We recall a formal definition of vector commitment in Hyperproofs [5]. Definition 1 (Vc): A VC scheme is a set of the following nine PPT algorithms:  
* \(Gen(1^{\lambda},n)\to pp\): Inputting vector size \(n\) and security parameter \(\lambda\) outputs the public parameters. * Commit(pp,\(\mathbf{v}\)) \(\rightarrow\) (\(C\),aux): Inputting vector \(\mathbf{v}=\{v_{0},v_{1},\ldots,v_{n-1}\}\) outputs commitment \(C\) and auxiliary information \(\mathsf{aux}\). * Open(pp, \(i\),\(\mathbf{v}\), aux) \(\rightarrow\)\(\pi_{i}\): Inputting the position index \(i\), the vectors \(\mathbf{v}\) and aux outputs proof \(\pi_{i}\) at index \(i\). * OpenAll(pp, \(\mathbf{v}\)) \(\rightarrow\)\(\{\pi_{0},\pi_{1},\pi_{2},\ldots,\pi_{n-1}\}\): Inputting vector \(\mathbf{v}\) outputs proofs at all positions \(\pi_{0},\pi_{1},\ldots,\pi_{n-1}\). * Agg(pp,I, \((\pi_{i},v_{i})_{i\in I})\rightarrow\pi_{I}\): For the aggregate set \(I\subseteq[0,n)\), inputting the proofs \(\{\pi_{i}\}_{i\in I}\) and the values \(\{v_{i}\}_{i\in I}\) outputs \(\pi_{I}\), which is an aggregated proof of constant size. * Verify(pp, \(C\), \(I\), \(\{v_{i}\}_{i\in I},\pi_{I}):=\{0,1\}\): Inputting values \(\{v_{i}\}_{i\in I}\), commitment \(C\) and aggregate proof \(\pi_{I}\) outputs either \(0\) or \(1\). * UpdateCom(pp, \(C\), \(i,\delta\)) \(\rightarrow\)\(C^{\prime}\): Inputting update index \(i\), update value \(\delta\) and commitment \(C\) outputs the update commitment \(C^{\prime}\) after changing \(\delta\) at position \(i\). * UpdateProof(pp,\(i,\delta,j,\pi_{j})\rightarrow\pi_{j}^{\prime}\): Inputting update index \(i\), update value \(\delta\), index \(j\) and proof \(\pi_{j}\) outputs updated proof \(\pi_{j}^{\prime}\) after changing \(\delta\) at position \(i\). * UpdateAllProofs(pp, \(i,\delta,\{\pi_{j}\}_{j\in[0,n)},\mathsf{aux}\)\(\rightarrow\)\((\{\pi_{j}^{\prime}\}),\mathsf{aux}^{\prime}\)): Inputting update index \(i\), update value \(\delta\), all proofs \(\{\pi_{j}\}_{j\in[0,n)}\) and auxiliary information aux outputs all updated proofs \(\{\pi_{j}^{\prime}\}_{j\in[0,n)}\) and updated auxiliary information aux\({}^{\prime}\) after changing \(\delta\) at position \(i\). Definition 2 (Vc Correctness): For any security parameter \(\lambda\) and \(\forall i\in[0,n)\),  
\[P_{r} \begin{bmatrix}\mathsf{pp}\leftarrow\mathsf{Gen}(1^{\lambda},n),\\ C\leftarrow\mathsf{Commit}(\mathsf{pp},\mathbf{v})\\ \pi_{i}\leftarrow\mathsf{Open}(\mathsf{pp},i,\mathbf{v},\mathsf{aux}):\\ \mathsf{Ver}(\mathsf{pp},C,i,v_{i},\pi_{i})=1\end{bmatrix} =1 \tag{6}\]  
Definition 3 (Position Binding): For any PPT adversary \(\mathcal{A}\),  
\[P_{r} \begin{bmatrix}\mathsf{pp}\leftarrow\mathsf{Gen}(1^{\lambda},n),\\ (C,i,v_{i},v_{i}^{\prime},\pi_{i}^{\prime},\pi_{i}^{\prime})\leftarrow\mathcal{ A}(1^{\lambda},\mathsf{pp}):\\ 1\leftarrow\mathsf{Ver}(\mathsf{pp},C,i,v_{i},\pi_{i})\wedge\\ 1\leftarrow\mathsf{Ver}(\mathsf{pp},C,i,v_{i}^{\prime},\pi_{i}^{\prime}) \wedge\\ v_{i}\
eq v_{i}^{\prime}\end{bmatrix} \leq negl(\lambda) \tag{7}\]  
**Definition 4** (Correctness of Proof Aggregation). : _For the security parameter \(\lambda\), vector size \(n\), vector \(\mathbf{v}\) and any set of positions \(I\subseteq[0,n)\),_  
\[P_{r}\left[ \begin{array}{c}\text{\small pp}\leftarrow\mathsf{Gen}(1^{ \lambda},n),\\ C\leftarrow\mathsf{Com}(\text{\small pp},\mathbf{v}),\\ \pi_{i}\leftarrow\mathsf{Open}(\text{\small pp},i,v_{i}),\\ \pi_{I}\leftarrow\mathsf{Agg}(\text{\small pp},I,\{v_{i},\pi_{i}\}_{i\in I }),\\ 1\leftarrow\mathsf{Ver}(\text{\small pp},C,I,\{v_{i}\}_{i\in I},\pi_{I}) \end{array} \right]=1 \tag{8}\]  
**Definition 5** (Correctness of Commitment Update). : _For the security parameter \(\lambda\), vector size \(n\) and vector \(\mathbf{v}\), the update occurs at the \(i\)-th position, where \(v_{i}^{\prime}=v_{i}+\delta\), and the updated vector is \(\mathbf{v}^{\prime}\):_  
\[P_{r}\left[