# Aggregatable Subvector Commitment with Efficient Updates
## 3 The Proposed Scheme  
Vector commitment is a basic building block in cryptography and zero-knowledge proof systems. In previous schemes, we have investigated various construction methods of VC [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14], for instance, based on the accumulator, Lagrangian, tree structure, etc. ; however, all the above schemes follow the premise that the vector size remains unchanged. In this section, we explore a novel vector commitment scheme based on [PERSON]'s interpolation. Similar to the previous scheme, we can create concise commitments for a given vector while maintaining an efficient aggregation and validation process. In addition, the proposed scheme can efficiently update the commitment and proofs when new vector nodes are added. The model diagram of our scheme is shown in Figure 1. The model is broadly divided into four phases, i.e., the commitment phase, the opening and validation phase, the update phase, and the addition phase. Vector commitment based on Newton interpolation.The basic principle of our scheme is similar to that of KZG [1] and aSVC [3], which are all based on polynomial interpolation. However, the difference is that KZG [1] and aSVC [3] are based on Lagrange interpolation, whereas our scheme is constructed using Newtonian polynomials. The specific formalized algorithm is as follows:  
* \(\text{Gen}(1^{\lambda},n)\to\text{pp}\): It takes as input the size of the vector \(n\) and security parameter \(\lambda\), and outputs the public parameter pp. First, it computes two groups \(\mathbb{G}\) and \(\mathbb{G}_{T}\) of order prime p for which there exists a symmetric bilinear pairing \(e:\mathbb{G}\times\mathbb{G}\to\mathbb{G}_{T}\). Then, the generators \(g\xleftarrow{\mathbb{G}}\) and \(\tau\xleftarrow{\mathbb{G}}\mathbb{Z}_{p}^{*}\) are chosen at random and generate an \((n+1)\)-tuple\((g,g^{\tau},g^{\tau^{2}},\ldots,g^{\tau^{n}})\). Additionally, a mapping \(\mathsf{PrimeGen}\) is defined to map an integer to a prime, such that \(\mathsf{PrimeGen}(i)\to p_{i}\). Finally, it outputs \[\mathsf{pp}= \begin{cases}g,g^{\tau},g^{\tau^{2}},\ldots,g^{\tau^{n}}\\ \mathsf{PrimeGen}.\end{cases} \]
* \(\mathsf{Commit(pp,v)}\to C\): It takes as input a vector \(\mathbf{v}=\{v_{0},v_{1},v_{2},v_{3},\ldots,v_{n-1}\}\), and generates the number of \(n\) primes \(p_{i}\) by invoking \(\mathsf{PrimeGen}(i)\to p_{i}\) for \(0\leq i\leq n-1\). Given \(n\) interpolation points \((p_{0},v_{0}),(p_{1},v_{1}),\ldots,(p_{n-1},v_{n-1})\), it computes the Newton interpolating polynomial \(N(x)\) such that \(N(p_{i})=v_{i}\). We represent \(N(x)=\sum_{i\in[0,n)}a_{i}\cdot w_{i}(x)=\sum_{i\in[0,n)}s_{i}x^{i}\). The commitment for \(\mathbf{v}\) is \[C=\prod_{i\in[0,n)}(g^{\tau^{i}})^{s_{i}}.\] (22)
* \(\mathsf{Open(pp,i,v)}\to\pi_{i}\): Upon inputting position index \(i\), vector \(\mathbf{v}\), it outputs proof \(\pi_{i}\). In particular, it calculates the following polynomial: \[q_{i}(x)=\frac{N(x)-v_{i}}{x-p_{i}},\] (23) and then the proof is \(\pi_{i}=g^{\sharp_{i}(\tau)}\). That is, \(\pi_{i}\) for the value \(v_{i}\) at the \(i\)-th position of the vector \(\mathbf{v}\) is the commitment to the polynomial \(q_{i}(x)\). * \(\mathsf{OpenAll(pp,v)}\to\{\pi_{0},\pi_{1},\ldots,\pi_{n-1}\}\): Upon inputting the vector \(\mathbf{v}\), we can call the Open algorithm to output all proofs \(\pi_{0},\pi_{1},\ldots,\pi_{n-1}\) in sequence. * \(\mathsf{Agg(pp,I,(\pi_{i},v_{i})_{i\in I})}\to\pi_{I}\): Upon inputting the index set \(I\subseteq[0,n)\) at which the proofs are to be aggregated, the set of messages \(\{v_{i}\}_{i\in I}\) corresponding with proofs \(\{\pi_{i}\}_{i\in I}\), it aggregates multiple proofs into a proof \(\pi_{I}\) of constant size for the set \(I\). Specifically, \(\pi_{I}\) is a commitment to the following polynomial: \[q_{I}(x)=\frac{N(x)-R(x)}{A_{I}(x)}\] (24) where \(R(x)\) satisfies \(R(p_{i})=v_{i}\) for \(i\in I\), \(A_{I}(x)=\prod_{i\in I}(x-p_{i})\), and \(A_{I}(x)\) is calculated as shown in Algorithm 2.