# Aggregatable Subvector Commitment with Efficient Updates
## 1 Introduction  
Vector commitment (VC) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] allows the committer to submit an ordered sequence of messages \(\mathbf{v}=(v_{0},v_{1},v_{2},\ldots,v_{n-1})\) of size \(n\), generate a commitment value \(C\) that contains all the messages for which we cannot tell whether the commitment value \(C\) is generated for \((v_{0},v_{1},v_{2},\ldots,v_{n-1})\) or for \((v_{0}^{\prime},v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{n-1}^{\prime})\), and also to generate its location proof \((\pi_{0},\pi_{1},\pi_{2},\ldots,\pi_{n-1})\) for each position of the message at the location. When a verifier wants to check if a specific message \(v_{i}\) is at the \(i\)-th position, the committer sends the proof \(\pi_{i}\), the commitment value \(C\), and the message \(v_{i}\). The verifier uses this information to validate the location proof \(\pi_{i}\). If the verification is successful, it confirms that \(v_{i}\) is indeed located at the \(i\)-th position.  
VC is an efficient cryptographic tool that protects the privacy and integrity of data, and thus, has a wide range of potential applications in several fields. For example, in the field of blockchain technology, VC can protect user privacy and verify the validity of transactions. In particular, in the VC [3]-based stateless cryptocurrency system, the verifier only needs to store the vector commitment of the user's account balance without maintaining the state of the entire ledger. When a user initiates a transfer, he/she only needs to submit the transaction and prove his/her account balance, and the validator will verify the correctness of the balance upon receiving the transaction, and if the validation passes, the transaction proceeds normally. Additionally, in the context of cloud storage, vector commitments [9] enable users to generate compact proofs for their uploaded data, allowing cloud service providers to verify data integrity efficiently. This approach significantly reduces storagerequirements and communication overhead compared to conventional methods. Vector commitments also exhibit substantial utility in the domains of zero-knowledge proofs. Specifically, within zero-knowledge proof [1; 15; 16; 17] protocols, they enable the prover to demonstrate the satisfaction of specific set conditions without disclosing additional information. This is particularly valuable in large-scale data analytics or machine learning applications, where vector commitments can validate the participation of individual data points or the accuracy of computational outcomes, thereby enhancing the overall credibility of data processing procedures.  
In order to improve the efficiency of verification, some commitment schemes [3; 8; 9; 10] introduce the concept of subvector, i.e., multiple proofs of transactions can be aggregated into a concise single proof, thus further reducing the verification overhead. After the verification passes, we need to update the account status and its proofs in a timely manner in order to improve the updating efficiency. Thus, some scholars have proposed new vector commitment schemes [5; 6; 7], aiming to improve the efficiency of such updating. However, the existing VC schemes mainly focus on vectors of fixed size. When a new value is appended to the vector, the client has to recompute the commitment and proofs for all positions, leading to significant computational overhead. In this work, we explore an efficient aggregatable subvector commitment scheme that supports the dynamic addition of new values.