# Aggregatable Subvector Commitment with Efficient Updates
## 3 The Proposed Scheme
```
1:\(Poly_{I}[0,|I|]=\{(x-p_{i})\}_{i\in I}\)
2:\(A_{I}(x)\)
3:if\(|I|=1\)then
4: Output: \(A_{I}(x)=Poly_{I}[0]\)
5:else
6: mid =\(\lfloor|I|/2\rfloor\)
7: left_result = MultiplyAll (\(Poly_{I}[0:\text{mid})\))
8: right_result = MultiplyAll (\(Poly_{I}[\text{mid}:|I|)\))
9:endif
10:return\(A_{I}(x)=\text{KA(left\_result, right\_result)}{=\prod_{i\in I}(x-p_{i})}\)
```  
**Algorithm 2** MultiplyAll  
Similar to aSVC [3], the specific form of \(q_{I}(x)\) is  
\[q_{I}(x)=\frac{N(x)-R(x)}{A_{I}(x)}=\sum_{i\in I}\frac{q_{i}(x)}{A_{I}^{\prime} (p_{i})}. \tag{25}\]where the derivative \(A^{\prime}_{I}(x)\) of \(A_{I}(x)\) can be expressed as \(A^{\prime}_{I}(x)=\sum_{i\in I}(A_{I}(x)/(x-p_{i}))\). Let \(c_{i}=\frac{1}{A^{\prime}_{I}(p_{i})}\); then, our aggregate proof \(\pi_{I}=\prod_{i\in I}\pi_{i}^{c_{i}}\), and the polynomial \(A_{I}(x)\) can be computed with the help of \(KA\) in time complexity \(O(1.39(\frac{|I|}{2}+1)^{\log 3})\), while its derivative \(A^{\prime}_{I}(x)\) has computational complexity \(O(I)\). Therefore, it is possible to obtain all \(c_{i}\) in \(O(1.39(\frac{|I|}{2}+1)^{\log 3})\). * Verify(\(\text{pp},C,I,\{v_{i}\}_{i\in I},\pi_{I})\rightarrow\{0,1\}\): Upon inputting the index set \(I\) at which the proofs are to be aggregated, the set of messages \(\{v_{i}\}_{i\in I}\), the batch proof \(\pi_{I}\) and commitment value \(C\), it outputs \(1\) iff: \[e(C/g^{R_{I}(\tau)},g)=e(\pi_{I},g^{A_{I}(\tau)}),\] (26) where \(A_{I}(x)=\prod_{i\in I}(x-p_{i})\), and \(R(x)\) satisfies \(R(p_{i})=v_{i}\) for \(i\in I\). When \(i\in I\) and \(|I|=1\), we can verify that \(\pi_{i}\) passes the following equation: \[e(C/g^{v_{i}},g)=e(\pi_{i},g^{\tau-p_{i}})\] (27)
* UpdateCom(\(\text{pp},C,i,\delta)\to C^{\prime}\): Upon inputting the original commitment value \(C\), the updated index \(i\), and the difference \(\delta\) at the updated index, it calculates the new interpolation polynomial \(F(x)=\varepsilon_{i}x^{i}\), where \(\varepsilon_{i}\) is the interpolation polynomial coefficient, and outputs the new commitment value \(C^{\prime}=\prod_{i\in[0,n)}(g^{x^{i}})^{\varepsilon_{i}}\). * UpdateAllProofs(\(\text{pp},i,\delta,\{\pi_{j}\}_{j\in[0,n)})\rightarrow\{\pi^{\prime}_{j} \}_{j\in[0,n)}\): Upon inputting the index \(i\) at the update and difference between message update \(\delta\), it can calculate the updated Newton interpolation polynomial, and output all proofs by calling it OpenAll. * UpdateProof(\(\text{pp},i,\delta,j,\pi_{j})\rightarrow\pi^{\prime}_{j}\): Upon inputting the index \(i\) of the update location, the message update difference \(\delta\), the index \(j\) and the proof \(\pi_{j}\), calculate the updated Newton interpolation polynomial, call the algorithm Open, and output the updated proof \(\pi^{\prime}_{j}\) to reflect the message at position \(i\) changing by \(\delta\). * AddCom(\(\text{pp},C,\mathbf{v}^{\prime}\)) \(\to C^{\prime}\): Input the original commitment value \(C\) and the vector \(\mathbf{v}^{\prime}=\{\mathbf{v},v_{n},v_{n+1},\ldots,v_{n+l-1}\}\) after adding the node, where \(l\) represents the number of nodes we want to add. Call \(\text{Gen}(1^{\lambda},n+l)_{\{l\in\mathbb{N}_{l}<n\}}\rightarrow\text{pp}^{\prime}\) to obtain the new public parameter \(\text{pp}^{\prime}\). \[\text{pp}^{\prime}= \begin{cases}(g,g^{\tau},g^{\tau^{2}},\ldots,g^{\tau^{n+l} })_{i\in[0,n+l]}\\ (u_{i,l})_{(i\in[n,n+l],j\in[0,n))}=g^{\frac{\omega_{j}(\tau)}{\tau-p_{j}}}\\ \text{PrimeGen}\end{cases} \] where \(\text{PrimeGen}(i)=p_{i}\). Compute the new difference quotient values \((a_{i})_{i\in[n,n+l]}\), and we can obtain a new polynomial \(f(x)=\sum_{i\in[n,n+l)}a_{i}(\prod_{j=0}^{i-1}(x-p_{j}))=\sum_{i\in[0,n+l)}s_{ i}x^{i}\). Output \[C^{\prime}=C\cdot\prod_{i\in[0,n+l)}(g^{x^{i}})^{s_{i}}.\] (28)
* AddProof(\(\text{pp}^{\prime},(i,a_{i})_{i\in[n,n+l]},\pi_{j})\rightarrow\pi^{ \prime}_{j}\): Whenever we add a new vector node, the original proof changes.