Aggregatable Subvector Commitments for Stateless Cryptocurrencies

Abstract

An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs and give a construction from constant-sized polynomial commitments. Our construction is unique in that it has linear-sized public parameters, it can compute all constant-sized proofs in quasilinear time, it updates proofs in constant time and it can aggregate multiple proofs into a constant-sized subvector proof. Furthermore, our concrete proof sizes are small due to our use of pairing-friendly groups. We use our aSVC to obtain a payments-only stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block’s proof overhead to a single group element, which is optimal. Furthermore, our subvector proofs speed up block verification and our smaller public parameters further reduce block size.

An errata for this paper can be found at https://github.com/alinush/asvc-paper.

1 Introduction

In a stateless cryptocurrency, neither miners nor cryptocurrency users need to store the full ledger state. Instead, this state consisting of users’ account balances is split among all users using an authenticated data structure. This way, miners only store a succinct digest of the ledger state and each user stores their account balance. Nonetheless, miners can still validate transactions sent by users, who now include proofs that they have sufficient balance. Furthermore, miners can still propose new blocks of transactions and users can easily synchronize or update their proofs as new blocks get published.

Stateless cryptocurrencies have received increased attention  [Dry19, RMCI17, CPZ18, BBF19, GRWZ20] due to several advantages. First, stateless cryptocurrencies eliminate hundreds of gigabytes of miner storage needed to validate blocks. Second, statelessness makes scaling consensus via sharding much easier, by allowing miners to efficiently switch from one shard to another [KJG+18]. Third, statelessness lowers the barrier to entry for full nodes, resulting in a much more resilient, distributed cryptocurrency.

Stateless Cryptocurrencies from VCs. At a high level, a VC scheme allows a prover to compute a succinct commitment c to a vector ${\mathbf {v}}=[v_0, v_1, \dots , v_{n-1}]$ of n elements where $v_i\in \mathbb {Z}_p$. Importantly, the prover can generate a proof $\pi _i$ that $v_i$ is the element at position i in ${\mathbf {v}}$, and any verifier can check it against the commitment c. The prover needs a proving key $\mathsf {prk}$ to commit to vectors and to compute proofs, while the verifier needs a verification key $\mathsf {vrk}$ to verify proofs. (Usually $|\mathsf {vrk} | \ll |\mathsf {prk} |$.) Some VC schemes support updates: if one or more elements in the vector change, the commitment and proofs can be updated efficiently. For this, a static update key $\mathsf {upk} _j$ tied only to the updated position j is necessary. Alternatively, some schemes require dynamic update hints $\mathsf {uph} _j$, typically consisting of the actual proof $\pi _j$. The proving, verification and update keys comprise the VC’s public parameters. Lastly, subvector commitment (SVC) schemes  [LM19] support computing succinct proofs for I-subvectors $(v_i)_{i\in I}$ where $I\subset [0,n)$. Furthermore, some schemes are aggregatable: multiple proofs $\pi _i$ for $v_i, \forall i \in I$ can be aggregated into a single, succinct I-subvector proof.

Chepurnoy, Papamanthou and Zhang pioneered the idea of building account-based  [Woo], stateless cryptocurrencies on top of any vector commitment (VC) scheme  [CPZ18]. Ideally, such a VC would have (1) sublinear-sized, updatable proofs with sublinear-time verification, (2) updatable commitments and (3) sublinear-sized update keys. In particular, static update keys (rather than dynamic update hints) help reduce interaction and thus simplify the design (see Sect. 4.1). We say such a VC has “scalable updates.” Unfortunately, most VCs do not have scalable updates (see Sect. 1.1) or, if they do  [CPZ18, Tom20], they are not optimal in their proof and update key sizes. Lastly, while some schemes in hidden-order groups have scalable updates  [CFG+20], they suffer from larger concrete proof sizes and are likely to require more computation in practice.

Our Contributions. In this paper, we formalize a new aggregatable subvector commitment (aSVC) notion that supports commitment updates, proof updates and aggregation of proofs into subvector proofs. Then, we construct an aSVC with scalable updates over pairing-friendly groups. Compared to other pairing-based VCs, our aSVC has constant-sized, aggregatable proofs that can be updated with constant-sized update keys (see Table 2). Furthermore, our aSVC supports computing all proofs in quasilinear time. We prove our aSVC secure under q-SBDH  [Goy07] in the extended version of our paper  [TAB+20].

Table 1. Asymptotic comparison of our work with other stateless cryptocurrencies. n is the number of users, $\lambda$ is the security parameter, and b is the number of transactions in a block. $\ \mathbb {G}$ is an exponentiation in a known-order group. $\mathbb {G}_?$ is a (slower) exponentiation (of size $2\lambda$ bits) in a hidden-order group. $\mathbb {P}$ is a pairing computation. $|\pi _i|$ is the size of a proof for a user’s account balance. $|\mathsf {upk} _i|$ is the size of user i’s update key. $|\pi _I|$ is the size of a proof aggregated from all $\pi _i$’s in a block. We give each Miner’s storage in terms of VC public parameters (e.g., update keys). A miner takes: (1) Check digest time, to check that, by “applying” the transactions from block $t+1$ to block t’s digest, he obtains the correct digest for block $t+1$, (2) Aggr. proofs time, to aggregate b transaction proofs, and (3) Vrfy. $|\pi _I|$ time, to verify the aggregated proof. A user takes Proof synchr. time to “synchronize” or update her proof by “applying” all the transactions in a new block. We treat [GRWZ20] and [CFG+20] as a payments-only stateless cryptocurrency without smart contracts. Our aggregation and verification times have an extra $b\log ^2{b}\ \mathbb {F}$ term, consisting of very fast field operations.

A Highly-Efficient Stateless Cryptocurrency. We use our aSVC to construct a stateless cryptocurrency based on the elegant design of Edrax [CPZ18]. Our stateless cryptocurrency has very low storage, communication and computation overheads (see Table 1). First, our constant-sized update keys have a smaller impact on block size and help users update their proofs faster. Second, our proof aggregation drastically reduces block size and speeds up block validation. Third, our verifiable update keys removes the need for miners to either (1) store all O(n) update keys or (2) interact during transaction validation to check update keys.

1.1 Related Work

Vector Commitments (VCs). The notion of VCs appears early in  [CFM08, LY10, KZG10] but Catalano and Fiore  [CF13] are the first to formalize it. They introduce schemes based on the Computational Diffie-Hellman (CDH), with $O(n^2)$-sized public parameters, and on the RSA problem, with O(1)-sized public parameters, which can be specialized into O(n)-sized ones when needed. Lai and Malavolta  [LM19] formalize subvector commitments (SVCs) and extend both constructions from  [CF13] with constant-sized I-subvector proofs. Camenisch et al.  [CDHK15] build VCs from KZG commitments  [KZG10] to Lagrange polynomials that are not only binding but also hiding. However, their scheme intentionally prevents aggregation of proofs as a security feature. Feist and Khovratovich  [FK20] introduce a technique for precomputing all constant-sized evaluation proofs in KZG commitments when the evaluation points are all roots of unity. We use their technique to compute VC proofs fast. Chepurnoy et al.  [CPZ18] instantiate VCs using multivariate polynomial commitments  [PST13] but with logarithmic rather than constant-sized proofs. Then, they build the first efficient, account-based, stateless cryptocurrency on top of their scheme. Later on, Tomescu  [Tom20] presents a very similar scheme but from univariate polynomial commitments  [KZG10] which supports subvector proofs.

Boneh et al. [BBF19] instantiate VCs using hidden-order groups. They are the first to support aggregating multiple proofs (under certain conditions). They are also the first to have constant-sized public parameters, without the need to specialize them into O(n)-sized ones. However, their VC uses update hints (rather than keys), which is less suitable for stateless cryptocurrencies. Campanelli et al.  [CFG+20] also formalize SVCs with a more powerful notion of infinite (dis)aggregation of proofs. In contrast, our aSVC only supports “one hop” aggregation and does not support disaggregation. They also formalize a notion of updatable, distributed VCs as Verified Decentralized Storage (VDS). However, their use of hidden-order groups leads to larger concrete proof sizes.

Concurrent with our work, Gorbunov et al.  [GRWZ20] also formalize aSVCs with a stronger notion of cross-commitment aggregation. However, their formalization lacks (verifiable) update keys, which hides many complexities that arise in stateless cryptocurrencies (see Sect. 4.2.2). Their VC scheme extends  [LY10] with (1) aggregating proofs into I-subvector proofs and (2) aggregating multiple I-subvector proofs with respect to different VCs into a single, constant-sized proof. However, this versatility comes at the cost of (1) losing the ability to precompute all proofs fast, (2) O(n)-sized update keys for updating proofs, and (3) O(n)-sized verification key. This makes it difficult to apply their scheme in a stateless cryptocurrency for payments such as Edrax  [CPZ18]. Furthermore, Gorbunov et al. also enhance KZG-based VCs with proof aggregation, but they do not consider proof updates. Lastly, they show it is possible to aggregate I-subvector proofs across different commitments for KZG-based VCs.

Kohlweiss and Rial  [KR13] extend VCs with zero-knowledge protocols for proving correct computation of a new commitment, for opening elements at secret positions, and for proving secret updates of elements at secret positions.

Stateless Cryptocurrencies. The concept of stateless validation appeared early in the cryptocurrency community  [Mil12, Tod16, But17] and later on in the academic community  [RMCI17, Dry19, CPZ18, BBF19, GRWZ20]. Initial proposals for UTXO-based cryptocurrencies used Merkle hash trees  [Mil12, Tod16, Dry19, CPZ18]. In particular, Dryja  [Dry19] gives a beautiful Merkle forest construction that significantly reduces communication. Boneh et al.  [BBF19] further reduce communication by using RSA accumulators.

Reyzin et al.  [RMCI17] introduce a Merkle-based construction for account-based stateless cryptocurrencies. Unfortunately, their construction relies on proof-serving nodes: every user sending coins has to fetch the recipient’s Merkle proof from a node and include it with her own proof in the transaction. Edrax  [CPZ18] obviates the need for proof-serving nodes by using a vector commitment (VC) with update keys (rather than update hints like Merkle trees). Nonetheless, proof-serving nodes can still be used to assist users who do not want to manually update their proofs (which is otherwise very fast). Unfortunately, Edrax’s (non-aggregatable) proofs are logarithmic-sized and thus sub-optimal.

Gorbunov et al.  [GRWZ20] introduce Pointproofs, a versatile VC scheme which can aggregate proofs across different commitments. They use this power to solve a slightly different problem: stateless block validation for smart contract executions (rather than for payments as in Edrax). Unfortunately, their approach requires miners to store a different commitment for each smart contract, or around 4.5 GBs of (dynamic) state in a system with $10^8$ smart contracts. This could be problematic in applications such as sharded cryptocurrencies, where miners would have to download part of this large state from one another when switching shards. Lastly, the verification key in Pointproofs is O(n)-sized, which imposes additional storage requirements on miners. Furthermore, Gorbunov et al. do not discuss how to update nor precompute proofs efficiently. Instead they assume that all contracts have $n\le 10^3$ memory locations and users can compute all proofs in $O(n^2)$ time. In contrast, our aSVC can compute all proofs in $O(n\log {n})$ time  [FK20]. Nonetheless, their approach is a very promising direction for supporting smart contracts in stateless cryptocurrencies.

Bonneau et al.  [BMRS20] use recursively-composable, succinct non-interactive arguments of knowledge (SNARKs)  [BSCTV14] for stateless validation. However, while block validators do not have to store the full state in their system, miners who propose blocks still have to.

2 Preliminaries

Notation. $\lambda$ is our security parameter. $\mathbb {G}_1,\mathbb {G}_2$ are groups of prime order p endowed with a pairing $e : \mathbb {G}_1 \times \mathbb {G}_2 \rightarrow \mathbb {G}_T$. (We assume symmetric pairings where $\mathbb {G}_1=\mathbb {G}_2$ for simplicity of exposition.) $\mathbb {G}_{?}$ is a hidden-order group. We use multiplicative notation for all groups. $\omega$ is a primitive nth root of unity in $\mathbb {Z}_p$  [vzGG13a]. $\mathsf {poly}(\cdot )$ is any function upper-bounded by some univariate polynomial. $\mathsf {negl}(\cdot )$ is any negligible function. $\log {x}$ and $\lg {x}$ are shorthand for $\log _2{x}$. $[i,j] = \{i,i+1,\dots ,j-1,j\}$, $[0,n) =[0,n-1]$ and $[n]=[1,n]$. ${\mathbf {v}}=(v_i)_{i\in [0,n)}$ is a vector of size n with elements $v_i\in \mathbb {Z}_p$.

Lagrange Interpolation. Given n pairs $(x_i, y_i)_{i\in [0,n)}$, we can find or interpolate the unique polynomial $\phi (X)$ of degree $<n$ such that $\phi (x_i) = y_i, \forall i\in [0,n)$ using Lagrange interpolation in $O(n\log ^2{n})$ time  [vzGG13b] as $\phi (X) = \sum _{i\in [0,n)} \mathcal {L}_i(X) y_i$, where $\mathcal {L}_i(X) = \prod _{\begin{array}{c} j\in [0,n),j\ne i \end{array}}\frac{X-x_j}{x_i-x_j}$. Recall that a Lagrange polynomial $\mathcal {L}_i(X)$ has the property that $\mathcal {L}_i(x_i) = 1$ and $\mathcal {L}_i(x_j)=0, \forall i,j\in [0,n)$ with $j \ne i$. Note that $\mathcal {L}_i(X)$ is defined in terms of the $x_i$’s which, throughout this paper, will be either $(\omega ^i)_{i\in [0,n)}$ or $(\omega ^i)_{i\in I}, I\subset [0,n)$.

2.1 KZG Polynomial Commitments

Kate, Zaverucha and Goldberg (KZG) proposed a constant-sized commitment scheme for degree n polynomials $\phi (X)$. Importantly, an evaluation proof for any $\phi (a)$ is constant-sized and constant-time to verify; it does not depend in any way on the degree of the committed polynomial. KZG requires public parameters $(g^{\tau ^i})_{i\in [0,n]}$, which can be computed via a decentralized MPC protocol  [BGM17] that hides the trapdoor $\tau$. KZG is computationally-hiding under the discrete log assumption and computationally-binding under n-SDH  [BB08].

Committing. Let $\phi (X)$ denote a polynomial of degree $d\le n$ with coefficients $c_0, c_1, \dots , c_d$ in $\mathbb {Z}_p$. A KZG commitment to $\phi (X)$ is a single group element $C = \prod _{i=0}^d {\left( g^{\tau ^i}\right) ^{c_i}} = g^{\sum _{i=0}^d c_i \tau ^i} = g^{\phi (\tau )}$. Committing to $\phi (X)$ takes $\varTheta (d)$ time.

Proving One Evaluation. To compute an evaluation proof that $\phi (a) = y$, KZG leverages the polynomial remainder theorem, which says $\phi (a) = y \Leftrightarrow \exists q(X)\ \text {such that}\ \phi (X) - y = q(X)(X-a)$. The proof is just a KZG commitment to q(X): a single group element $\pi =g^{q(\tau )}$. Computing the proof takes $\varTheta (d)$ time. To verify $\pi$, one checks (in constant time) if $e(C / g^y, g) = e(\pi , g^{\tau }/g^a) \Leftrightarrow e(g^{\phi (\tau ) - y}, g) = e(g^{q(\tau )},g^{\tau -a})\Leftrightarrow {\phi (\tau )-y} = q(\tau )(\tau -a)$.

Proving Multiple Evaluations. Given a set of points I and their evaluations $\{\phi (i)\}_{i\in I}$, KZG can prove all evaluations with a constant-sized batch proof rather than |I| individual proofs. The prover computes an accumulator polynomial $a(X)=\prod _{i\in I} (X-i)$ in $\varTheta (|I|\log ^2{|I|})$ time and computes $\phi (X)/a(X)$ in $\varTheta (d\log {d})$ time, obtaining a quotient q(X) and remainder r(X). The batch proof is $\pi _I=g^{q(\tau )}$. To verify $\pi _I$ and $\{\phi (i)\}_{i\in I}$ against C, the verifier first computes a(X) from I and interpolates r(X) such that $r(i)=\phi (i), \forall i \in I$ in $\varTheta (|I|\log ^2{|I|})$ time. Next, she computes $g^{a(\tau )}$ and $g^{r(\tau )}$. Finally, she checks if $e(C / g^{r(\tau )}, g) = e(g^{q(\tau )}, g^{a(\tau )})$. We stress that batch proofs are only useful when $|I| \le d$. Otherwise, if $|I| > d$, the verifier can interpolate $\phi (X)$ directly from the evaluations, which makes verifying any $\phi (i)$ trivial.

2.2 Account-Based Stateless Cryptocurrencies

In a stateless cryptocurrency based on VCs  [CPZ18], there are miners running a permissionless consensus algorithm  [Nak08] and users, numbered from 0 to $n-1$ who have accounts with a balance of coins. (n can be $\infty$ if the VC is unbounded.) For simplicity of exposition, we do not give details on the consensus algorithm, on transaction signature verification nor on monetary policy.

The (Authenticated) State. The state is an authenticated data structure (ADS) mapping each user i’s public key to their account balance $\mathsf {bal} _i$. (In practice, the mapping is also to a transaction counter $c_i$, which is necessary to avoid transaction replay attacks. We address this in Sect. 4.3.1.) Importantly, miners and users are stateless: they do not store the state, just its digest $d_t$ at the latest block t they are aware of. Additionally, each user i stores a proof $\pi _{i,t}$ for their account balance that verifies against $d_t$.

Miners. Despite miners being stateless, they can still validate transactions, assemble them into a new block, and propose that block. Specifically, a miner can verify every new transaction spends valid coins by checking the sending user’s balance against the latest digest $d_t$. This requires each user i who sends coins to j to include her proof $\pi _{i,t}$ in her transaction. Importantly, user i should not have to include the recipient’s proof $\pi _{j,t}$ in the transaction, since that would require interacting with proof-serving nodes (see Sect. 4.3.2)

Once the miner has a set V of valid transactions, he can use them to create the next block ${t+1}$ and propose it. The miner obtains this new block’s digest $d_{t+1}$ by “applying” all transactions in V to $d_t$. When other miners receive this new block ${t+1}$, they can validate its transactions from V against $d_t$ and check that the new digest $d_{t+1}$ was produced correctly from $d_t$ by “reapplying” all the transactions from V.

Users. When creating a transaction $\mathsf {tx}$ for block $t+1$, user i includes her proof $\pi _{i,t}$ for miners to verify she has sufficient balance. When she sees a new block ${t+1}$, she can update her proof $\pi _{i,t}$ to a new proof $\pi _{i,t+1}$, which verifies against the new digest $d_{t+1}$. For this, she will look at all changes in balances $(j, \varDelta \mathsf {bal} _j)_{j\in J}$, where J is the set of users with transactions in block ${t+1}$, and “apply” those changes to her proof. Similarly, miners can also update proofs of pending transactions which did not make it in block t and now need a proof w.r.t. $d_{t+1}$

Users assume that the consensus mechanism produces correct blocks. As a result, they do not need to verify transactions in the block; they only need to update their own proof. Nonetheless, since block verification is stateless and fast, users could easily participate as block validators, should they choose to.

3 Aggregatable Subvector Commitment (aSVC) Schemes

In this section, we introduce the notion of aggregatable subvector commitments (aSVCs) as a natural extension to subvector commitments (SVCs)  [LM19] where anybody can aggregate b proofs for individual positions into a single constant-sized subvector proof for those positions. Our formalization differs from previous work  [BBF19, GRWZ20] in that it accounts for (static) update keys as the verifiable auxiliary information needed to update commitments and proofs. This is useful in distributed settings where the public parameters of the scheme are split amongst many participants, such as in stateless cryptocurrencies.

3.1 aSVC API

Our API resembles the VC API by Chepurnoy et al.  [CPZ18] and the SVC API by Lai and Malavolta  [LM19], extended with an API for verifying update keys (see Section 4.2.2) and an API for aggregating proofs. Unlike [CPZ18], our $\mathsf {VC}$.$\mathsf {UpdateProof}$ API receives both $\mathsf {upk} _i$ and $\mathsf {upk} _j$ as input. This is reasonable in the stateless setting, since each user has to store their $\mathsf {upk} _i$ anyway and they extract $\mathsf {upk} _j$ from the transactions (see Sect. 4).

• $\mathsf {VC}.\mathsf {KeyGen} (1^\lambda , n)\rightarrow \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _j)_{j\in [0,n)}$. Randomized algorithm that, given a security parameter $\lambda$ and an upper-bound n on vector size, returns a proving key $\mathsf {prk}$, a verification key $\mathsf {vrk}$ and update keys $(\mathsf {upk} _j)_{j\in [0,n)}$.

• $\mathsf {VC}.\mathsf {Commit} (\mathsf {prk}, {\mathbf {v}}) \rightarrow c$. Deterministic algorithm that returns a commitment c to any vector ${\mathbf {v}}$ of size $\le n$.

• $\mathsf {VC}.\mathsf {ProvePos} (\mathsf {prk}, I, {\mathbf {v}}) \rightarrow \pi _I$. Deterministic algorithm that returns a proof $\pi _I$ that ${\mathbf {v}}_I = (v_i)_{i\in I}$ is the I-subvector of ${\mathbf {v}}$. For notational convenience, I can be either an index set $I\subseteq [0,n)$ or an individual index $I = i\in [0,n)$.

• $\mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, c, {\mathbf {v}}_I, I, \pi _I) \rightarrow T/F$. Deterministic algorithm that verifies the proof $\pi _I$ that ${\mathbf {v}}_I$ is the I-subvector of the vector committed in c. As before, I can be either an index set $I\subseteq [0,n)$ or an individual index $I = i\in [0,n)$.

• $\mathsf {VC}.\mathsf {VerifyUPK} (\mathsf {vrk}, i, \mathsf {upk} _i) \rightarrow T/F$. Deterministic algorithm that verifies that $\mathsf {upk} _i$ is indeed the ith update key.

• $\mathsf {VC}.\mathsf {UpdateComm} (c, \delta , j,\mathsf {upk} _j)\rightarrow c'$. Deterministic algorithm that returns a new commitment $c'$ to ${\mathbf {v'}}$ obtained by updating $v_j$ to $v_j+\delta$ in the vector ${\mathbf {v}}$ committed in c. Needs $\mathsf {upk} _j$ associated with the updated position j.

• $\mathsf {VC}.\mathsf {UpdateProof} (\pi _i, \delta , i, j, \mathsf {upk} _i, \mathsf {upk} _j)\rightarrow \pi '_i$. Deterministic algorithm that updates an old proof $\pi _i$ for the ith element $v_i$, given that the jth element was updated to $v_j + \delta$. Note that i can be equal to j.

• $\mathsf {VC}.\mathsf {AggregateProofs} (I, (\pi _i)_{i\in I})\rightarrow \pi _I$ Deterministic algorithm that, given proofs $\pi _i$ for $v_i,\forall i\in I$, aggregates them into a succinct I-subvector proof $\pi _I$.

3.2 aSVC Correctness and Security Definitions

Definition 1 (Aggregatable SVC Scheme)

$(\mathsf {VC}.\mathsf {KeyGen}$, $\mathsf {VC}.\mathsf {Commit}$, $\mathsf {VC}.\mathsf {ProvePos}$, $\mathsf {VC}.\mathsf {VerifyPos}$, $\mathsf {VC}.\mathsf {VerifyUPK}$, $\mathsf {VC}.\mathsf {UpdateComm}$, $\mathsf {VC}.\mathsf {UpdateProof}$, $\mathsf {VC}.\mathsf {AggregateProofs})$ is a secure aggregatable subvector commitment scheme if $\forall$ upper-bounds $n=\mathsf {poly}(\lambda )$ it satisfies the following properties:

Definition 2 (Correctness)

$\forall$ honestly generated $\mathsf {prk},\mathsf {vrk},(\mathsf {upk} _j)_{j\in [0,n)}$ via $\mathsf {VC}$.$\mathsf {KeyGen}$, $\forall$ vectors ${\mathbf {v}}=(v_j)_{j\in [0,n)}$ with commitment c obtained via $\mathsf {VC}$.$\mathsf {Commit}$ and, optionally, $\mathsf {VC}$.$\mathsf {UpdateComm}$ calls, $\forall I\subseteq [0,n)$, if $\pi _I$ is a (sub)vector proof for $\mathbf {v}_I=(v_i)_{i\in I}$ obtained via any valid interleaving of $\mathsf {VC}$.$\mathsf {ProvePos}$, $\mathsf {VC}$.$\mathsf {AggregateProofs}$ and $\mathsf {VC}$.$\mathsf {UpdateProof}$, then $\mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, c, \mathbf {v}_I, I, \pi _I)$ returns true. Furthermore, $\mathsf {VC}.\mathsf {VerifyUPK} (\mathsf {vrk}, i, \mathsf {upk} _i) = T,\forall i\in [0,n)$.

Definition 3 (Update Key Uniqueness)

$\forall$ adversaries $\mathcal {A}$ running in time $\mathsf {poly}(\lambda )$:

$$\begin{aligned} \Pr \left[ \begin{array}{c} \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _j)_{j\in [0,n)} \leftarrow \mathsf {VC}.\mathsf {KeyGen} (1^\lambda , n),\\ i, \mathsf {upk},\mathsf {upk} ' \leftarrow \mathcal {A} (1^\lambda , \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _j)_{j\in [0,n)}):\\ \mathsf {VC}.\mathsf {VerifyUPK} (\mathsf {vrk}, i, \mathsf {upk}) = T\ \wedge \\ \mathsf {VC}.\mathsf {VerifyUPK} (\mathsf {vrk}, i, \mathsf {upk} ') = T \wedge \\ \mathsf {upk} \ne \mathsf {upk} ' \end{array} \right] \le \mathsf {negl}(\lambda ) \end{aligned}$$

Observation: Definitions that allow for dynamic update hints rather than unique update keys are possible too, but would be less simple to state and less useful for stateless cryptocurrencies (see Sect. 4).

Definition 4 (Position Binding Security)

$\forall$ adversaries $\mathcal {A}$ running in time $\mathsf {poly}(\lambda )$, if ${\mathbf {v}}_I=(v_i)_{i\in I}$ and ${\mathbf {v}}'_J=(v'_j)_{j\in J}$, then:

$$\begin{aligned} \Pr \left[ \begin{array}{c} \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _i)_{i\in [0,n)} \leftarrow \mathsf {VC}.\mathsf {KeyGen} (1^\lambda , n), \\ (c,I,J,{\mathbf {v}}_I,{\mathbf {v}}'_J, \pi _I,\pi _J) \leftarrow \mathcal {A} (1^\lambda , \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _i)_{i\in [0,n)}): \\ \mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, c, {\mathbf {v}}_I, I, \pi _I) = T\ \wedge \\ \mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, c, {\mathbf {v}}'_J, J, \pi _J) = T\ \wedge \\ \exists k \in I\cap J,\ \text {such that}\ v_k \ne v'_k \end{array} \right] \le \mathsf {negl}(\lambda ) \end{aligned}$$

Table 2. Asymptotic comparison of our aSVC with other (aS)VCs based on prime-order groups. n is the vector size and b is the subvector size. See our extended paper  [TAB+20] for a more detailed analysis. All schemes have O(n)-sized parameters (except   [LM19] has $O(n^2)$ and   [CFG+20] has O(1)); can update commitments in O(1) time (except for [KZG10]); have O(1)-sized proofs that verify in O(1) time (except [CPZ18] and [Tom20] proofs are $O(\lg {n})$). Com. is the time to commit to a size-n vector. Proof upd. is the time to update one individual proof $\pi _i$ after a change to one vector element $v_j$. Prove one, Prove subv. and Prove each are the times to compute a proof $\pi _i$ for one $v_i$, a size-b subvector proof $\pi _I$ and proofs for all $(v_i)_{i\in [0,n)}$, respectively.

3.3 aSVC from KZG Commitments to Lagrange Polynomials

In this subsection, we present our aSVC from KZG commitments to Lagrange polynomials. Similar to previous work, we represent a vector ${\mathbf {v}} = [v_0, v_1, \dots , v_{n-1}]$ as a polynomial $\phi (X)=\sum _{i\in [0,n)} \mathcal {L}_i(X)v_i$ in Lagrange basis  [KZG10, CDHK15, Tom20, GRWZ20]. However, unlike previous work, we add support for efficiently updating and aggregating proofs. For aggregation, we use known techniques for aggregating KZG proofs via partial fraction decomposition  [But20]. For updating proofs, we introduce a new mechanism to reduce the update key size from linear to constant. We use roots of unity and “store” $v_i$ as $\phi (\omega ^i)=v_i$, which means our Lagrange polynomials are $\mathcal {L}_i(X)=\prod _{j\in [0,n),j\ne i} \frac{X-\omega ^j}{\omega ^i - \omega ^j}$. For this to work efficiently, we assume without loss of generality that n is a power of two.

Committing. A commitment to ${\mathbf {v}}$ is just a KZG commitment $c=g^{\phi (\tau )}$ to $\phi (X)$, where $\tau$ is the trapdoor of the KZG scheme (see Sect. 2.1). Similar to previous work  [CDHK15], the proving key includes commitments to all Lagrange polynomials $\ell _i = g^{\mathcal {L}_i(\tau )}$. Thus, we can compute $c=\prod _{i=1}^n (\ell _i)^{v_i}$ in O(n) time without interpolating $\phi (X)$ and update it as $c' = c\cdot (\ell _i)^{\delta }$ after adding $\delta$ to $v_i$. Note that $c'$ is just a commitment to an updated $\phi '(X)=\phi (X)+\delta \cdot \mathcal {L}_i(X)$.

Proving. A proof $\pi _i$ for a single element $v_i$ is just a KZG evaluation proof for $\phi (\omega ^i)$. A subvector proof $\pi _I$ for for $v_I,I\subseteq [0,n)$ is just a KZG batch proof for all $\phi (\omega ^i)_{i\in I}$ evaluations. Importantly, we use the Feist-Khovratovich (FK)  [FK20] technique to compute all proofs $(\pi _i)_{i\in [0,n)}$ in $O(n\log {n})$ time. This allows us to aggregate I-subvector proofs faster in $O(\vert I \vert \log ^2{|I|})$ time (see Table 2).

3.4 Partial Fraction Decomposition

A key ingredient in our aSVC scheme is partial fraction decomposition, which we re-explain from the perspective of Lagrange interpolation. First, let us rewrite the Lagrange polynomial for interpolating $\phi (X)$ given all $\left( \phi (\omega ^i)\right) _{i\in I}$:

$$\begin{aligned} \mathcal {L}_i(X)=\prod _{j\in I, j\ne i} \frac{X-\omega ^j}{\omega ^i - \omega ^j}=\frac{A_I(X)}{A'_I(\omega ^i) (X-\omega ^i)},\ \text {where}\ A_I(X)=\prod _{i\in I} (X-\omega ^i) \end{aligned}$$

(1)

Here, $A'_I(X)=\sum _{j\in [0,n)} A_I(X)/(X-\omega ^j)$ is the derivative of $A_I(X)$  [vzGG13b]. Next, for any $\phi (X)$, we can rewrite the Lagrange interpolation formula as $\phi (X) = A_I(X)\sum _{i\in [0,n)} \frac{y_i}{A'_I(\omega ^i)(X-\omega ^i)}$. In particular, for $\phi (X)=1$, this implies $\frac{1}{A_I(X)} = \sum _{i\in [0,n)} \frac{1}{A'_I(\omega ^i)(X-\omega ^i)}$. In other words, we can decompose $A_I(X)$ as:

$$\begin{aligned} \frac{1}{A_I(X)} = \frac{1}{\prod _{i \in I} (X-\omega ^i)}&= \sum _{i\in [0,n)} c_i\cdot \frac{1}{X-\omega ^i},\ \text {where}\ c_i=\frac{1}{A'_I(\omega ^i)} \end{aligned}$$

(2)

$A_I(X)$ can be computed in $O(|I|\log ^2{|I|})$ time  [vzGG13b]. Its derivative, $A'_I(X)$, can be computed in O(|I|) time and evaluated at all $\omega ^i$’s in $O(|I|\log ^2{|I|})$ time  [vzGG13b]. Thus, all $c_i$’s can be computed in $O(|I|\log ^2{|I|})$ time. For the special case of $I=[0,n)$, we have $A_I(X)=A(X)=\prod _{i\in [0,n)} (X-\omega ^i)=X^n - 1$ and $A'(\omega ^i)=n\omega ^{-i}$  [TAB+20, Appendix A]. In this case, any $c_i$ can be computed in O(1) time.

3.4.1 Aggregating Proofs

We build upon Drake and Buterin’s observation  [But20] that partial fraction decomposition (see Sect. 3.4) can be used to aggregate KZG evaluation proofs. Since our VC proofs are KZG proofs, we show how to aggregate a set of proofs $(\pi _i)_{i\in I}$ for elements $v_i$ of ${\mathbf {v}}$ into a constant-sized I-subvector proof $\pi _I$ for $(v_i)_{i\in I}$.

Recall that $\pi _i$ is a commitment to $q_i(X)=\frac{\phi (X)-v_i}{X-\omega ^i}$ and $\pi _I$ is a commitment to $q(X) = \frac{\phi (X)-R(X)}{A_I(X)}$, where $A_I(X)=\prod _{i\in I} (X-\omega ^i)$ and R(X) is interpolated such that $R(\omega ^i)=v_i,\forall i\in I$. Our goal is to find coefficients $c_i\in \mathbb {Z}_p$ such that $q(X)=\sum _{i\in I} c_i q_i(X)$ and thus aggregate $\pi _I=\prod _{i\in I} \pi _i^{c_i}$. We observe that:

$$\begin{aligned} q(X)&= \phi (X)\frac{1}{A_I(X)}- R(X)\frac{1}{A_I(X)}\end{aligned}$$

(3)

$$\begin{aligned}&= \phi (X)\sum _{i\in I} \frac{1}{A_I'(\omega ^i)(X-\omega ^i)} - \left( A_I(X)\sum _{i\in I} \frac{v_i}{A_I'(\omega ^i)(X-\omega ^i)}\right) \cdot \frac{1}{A_I(X)} \end{aligned}$$

(4)

$$\begin{aligned}&= \sum _{i\in I} \frac{\phi (X)}{A_I'(\omega ^i)(X-\omega ^i)} - \sum _{i\in I} \frac{v_i}{A_I'(\omega ^i)(X-\omega ^i)} = \sum _{i\in I} \frac{1}{A_I'(\omega ^i)}\cdot \frac{\phi (X) - v_i}{X-\omega ^i}\end{aligned}$$

(5)

$$\begin{aligned}&= \sum _{i\in I} \frac{1}{A_I'(\omega ^i)}\cdot q_i(X) \end{aligned}$$

(6)

Thus, we can compute all $c_i={1}/{A_I'(\omega ^i)}$ using $O(\vert I\vert \log ^2{\vert I \vert })$ field operations (see Sect. 3.4) and compute $\pi _I=\prod _{i\in I} \pi _i^{c_i}$ with an O(|I|)-sized multi-exponentiation.

3.4.2 Updating Proofs

When updating $\pi _i$ after a change to $v_j$, it could be that either $i=j$ or $i\ne j$. First, recall that $\pi _i$ is a KZG commitment to $q_i(X)=\frac{\phi (X)-v_i}{X-\omega ^i}$. Second, recall that, after a change $\delta$ to $v_j$, the polynomial $\phi (X)$ is updated to $\phi '(X)=\phi (X)+\delta \cdot \mathcal {L}_j(X)$. We refer to the party updating their proof $\pi _i$ as the proof updater.

The $\varvec{i=j}$ Case. Consider the quotient polynomial $q_i'(X)$ in the updated proof $\pi _i'$ after $v_i$ changed to $v_i+\delta$:

$$\begin{aligned} q_i'(X)&=\frac{\phi '(X)-(v_i+\delta )}{X-\omega ^i}=\frac{\left( \phi (X) + \delta \mathcal {L}_i(X)\right) - v_i -\delta }{X-\omega ^i}\end{aligned}$$

(7)

$$\begin{aligned}&=\frac{\phi (X) - v_i}{X-\omega ^i}+\frac{\delta (\mathcal {L}_i(X)-1)}{X-\omega ^i} = q_i(X) + \delta \left( \frac{\mathcal {L}_i(X)-1}{X-\omega ^i}\right) \end{aligned}$$

(8)

This means the proof updater needs a KZG commitment to $\frac{\mathcal {L}_i(X)-1}{X-\omega ^i}$, which is just a KZG evaluation proof that $\mathcal {L}_i(\omega ^i)=1$. This can be addressed very easily by making this commitment part of $\mathsf {upk} _i$. To conclude, to update $\pi _i$, the proof updater obtains $u_i=g^{\frac{\mathcal {L}_i(\tau )-1}{\tau - \omega ^i}}$ from $\mathsf {upk} _i$ and computes $\pi _i'=\pi _i \cdot \left( u_i\right) ^\delta$. (Remember that the proof updater, who calls $\mathsf {VC}.\mathsf {UpdateProof} (\pi _i, \delta ,i,i,\mathsf {upk} _i,\mathsf {upk} _i)$, has $\mathsf {upk} _i$.)

The $\varvec{i\ne j}$ Case. Now, consider the quotient polynomial $q_i'(X)$ after $v_j$ changed to $v_j+\delta$:

$$\begin{aligned} q_i'(X)&= \frac{\phi '(X)-v_i}{X-\omega ^i}=\frac{\left( \phi (X) + \delta \mathcal {L}_j(X)\right) - v_i}{X-\omega ^i}\end{aligned}$$

(9)

$$\begin{aligned}&= \frac{\phi (X) - v_i}{X-\omega ^i}+\frac{\delta \mathcal {L}_j(X)}{X-\omega ^i} = q_i(X) + \delta \left( \frac{\mathcal {L}_j(X)}{X-\omega ^i}\right) \end{aligned}$$

(10)

In this case, the proof updater will need to construct a KZG commitment to $\frac{\mathcal {L}_j(X)}{X-\omega ^i}$. For this, we put enough information in $\mathsf {upk} _i$ and $\mathsf {upk} _j$, which the proof updater has (see Sect. 3.1), to help her do so.

Since $U_{i,j}(X)=\frac{A(X)}{A'(\omega ^j)(X-\omega ^j)(X-\omega ^i)}$ and $A'(\omega ^j) = n\omega ^{-j}$, it is sufficient to reconstruct a KZG commitment to $W_{i,j}(X)=\frac{A(X)}{(X-\omega ^j)(X-\omega ^i)}$, which can be decomposed as $W_{i,j}(X)=A(X) \left( c_i \frac{1}{X-\omega ^i} + c_j \frac{1}{X-\omega _j}\right) = c_i \frac{A(X)}{X-\omega ^i} + c_j \frac{A(X)}{X-\omega ^j}$, where $c_i = 1/(\omega ^i-\omega ^j)$ and $c_j=1/(\omega ^j-\omega ^i)$ (see Sect. 3.4). Thus, if we include $a_j=g^{{A(\tau )}/(\tau -\omega ^j)}$ in each $\mathsf {upk} _j$, the proof updater can first compute $w_{i,j} = a_i^{c_i} a_j^{c_j}$, then compute $u_{i,j}=\left( w_{i,j}\right) ^{\frac{1}{A'(\omega ^j)}}$ and finally update the proof as $\pi _i' = \pi _i \cdot (u_{i,j})^\delta$.

3.4.3 aSVC Algorithms

Having established the intuition for our aSVC, we can now describe it in detail using the aSVC API from Sect. 3.1.

• $\mathsf {VC}.\mathsf {KeyGen} (1^\lambda , n) \rightarrow \mathsf {prk},\mathsf {vrk},(\mathsf {upk} _j)_{j\in [0,n)}$. Generates n-SDH public parameters $g,g^\tau ,g^{\tau ^2},\dots ,g^{\tau ^n}$. Computes $a=g^{A(\tau )}$, where $A(X)=X^n - 1$. Computes $a_i=g^{A(\tau )/(X-\omega ^i)}$ and $\ell _i = g^{\mathcal {L}_i(\tau )}, \forall i\in [0,n)$. Computes KZG proofs $u_i=g^{\frac{\mathcal {L}_i(\tau )-1}{X-\omega ^i}}$ for $\mathcal {L}_i(\omega ^i) = 1$. Sets $\mathsf {upk} _i = (a_i, u_i)$, $\mathsf {prk} = \bigl ((g^{\tau ^i})_{i\in [0,n]},(\ell _i)_{i\in [0,n)}$, $(\mathsf {upk} _i)_{i\in [0,n)}\bigr )$ and $\mathsf {vrk} = ((g^{\tau ^i})_{i\in [0,|I|]},a)$.

• $\mathsf {VC}.\mathsf {Commit} (\mathsf {prk}, {\mathbf {v}}) \rightarrow c$. Returns $c=\prod _{i\in [0,n)} (\ell _i)^{v_i}$.

• $\mathsf {VC}.\mathsf {ProvePos} (\mathsf {prk}, I, {\mathbf {v}}) \rightarrow \pi _I$. Computes $A_I(X)=\prod _{i\in I} (X-\omega ^i)$ in $O(\vert I\vert \log ^2{\vert I \vert })$ time. Divides $\phi (X)$ by $A_I(X)$ in $O(n\log {n})$ time, obtaining a quotient q(X) and a remainder r(X). Returns $\pi _I = g^{q(\tau )}$. (We give an O(n) time algorithm in  [TAB+20, Appendix D.7] for the $\vert I\vert = 1$ case.)

• $\mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, c, {\mathbf {v}}_I, I, \pi _I) \rightarrow T/F$. Computes $A_I(X)=\prod _{i\in I} (X-\omega ^i)$ in $O(\vert I\vert \log ^2{\vert I \vert })$ time and commits to it as $g^{A_I(\tau )}$ in $O(\vert I \vert )$ time. Interpolates $R_I(X)$ such that $R_I(i) = v_i,\forall i \in I$ in $O(\vert I\vert \log ^2{\vert I \vert })$ time and commits to it as $g^{R_I(\tau )}$ in $O(\vert I \vert )$ time. Returns T iff. $e(c/g^{R_I(\tau )},g)=e(\pi _I, g^{A_I(\tau )})$. (When $I=\{i\}$, we have $A_I(X)=X-\omega ^i$ and $R_I(X)=v_i$.)

• $\mathsf {VC}.\mathsf {VerifyUPK} (\mathsf {vrk},i, \mathsf {upk} _i) \rightarrow T/F$. Checks that $\omega ^i$ is a root of $X^n-1$ (which is committed in a) via $e(a_i, g^\tau /g^{(\omega ^i)}) = e(a,g)$. Checks that $\mathcal {L}_i(\omega ^i) = 1$ via $e(\ell _i/g^1, g) =e(u_i,g^\tau /g^{(\omega ^i)})$, where $\ell _i=a_i^{1/A'(\omega ^i)}=g^{\mathcal {L}_i(\tau )}$.

• $\mathsf {VC}.\mathsf {UpdateComm} (c, \delta , j,\mathsf {upk} _j)\rightarrow c'$. Returns $c'=c\cdot (\ell _j)^\delta$, where $\ell _j=a_j^{1/A'(\omega ^j)}$.

• $\mathsf {VC}.\mathsf {UpdateProof} (\pi _i, \delta , i,j, \mathsf {upk} _i, \mathsf {upk} _j)\rightarrow \pi '_i$. If $i=j$, returns $\pi _i'=\pi _i \cdot (u_i)^\delta$. If $i\ne j$, computes $w_{i,j}=a_i^{1/(\omega ^i - \omega ^j)}\cdot a_j^{1/(\omega ^j - \omega ^i)}$ and $u_{i,j}=w_{i,j}^{1/A'(\omega ^j)}$ (see Sect. 3.4.2) and returns $\pi _i'=\pi _i \cdot (u_{i,j})^\delta$.

• $\mathsf {VC}.\mathsf {AggregateProofs} (I, (\pi _i)_{i\in I})\rightarrow \pi _I$. Computes $A_I(X)=\prod _{i\in I} (X-\omega ^i)$, its derivative $A'_I(X)$ and all $c_i = (A'_I(\omega ^i))_{i\in I}$ in $O(\vert I\vert \log ^2{\vert I \vert })$ time. Returns $\pi _I = \prod _{i\in I} \pi _i^{c_i}$.

3.4.4 Distributing the Trusted Setup

Our aSVC requires a centralized, trusted setup phase that computes its public parameters. We can decentralize this phase using highly-efficient MPC protocols that generate $(g^{\tau ^i})$’s in a distributed fashion  [BGM17]. Then, we can derive the remaining parameters from the $(g^{\tau ^i})$’s, which has the advantage of keeping our parameters updatable. First, the commitment $a=g^{A(\tau )}$ to $A(X)=X^{n} - 1$ can be computed in O(1) time via an exponentiation. Second, the commitments $\ell _i=g^{\mathcal {L}_i(\tau )}$ to Lagrange polynomials can be computed via a single DFT on the $(g^{\tau ^i})$’s  [Vir17, Sec 3.12.3, pg. 97]. Third, each $a_i = g^{A(\tau )/(\tau -\omega ^i)}$ is a bilinear accumulator membership proof for $\omega ^i$ w.r.t. A(X) and can all be computed in $O(n\log {n})$ time using FK  [FK20]. But what about computing each $u_i = g^{\frac{\mathcal {L}_i(\tau )-1}{X-\omega ^i}}$?

Computing All $\varvec{u_i}$’s Fast. Inspired by the FK technique  [FK20], we show how to compute all n $u_i$’s in $O(n\log {n})$ time using a single DFT on group elements. First, note that $u_i=g^{\frac{\mathcal {L}_i(\tau )-1}{X-\omega ^i}}$ is a KZG evaluation proof for $\mathcal {L}_i(\omega ^i)=1$. Thus, $u_i = g^{Q_i(\tau )}$ where $Q_i(X) = \frac{\mathcal {L}_i(X)-1}{X-\omega ^i}$. Second, let $\psi _i(X)=A'(\omega ^i)\mathcal {L}_i(X)=\frac{X^n - 1}{X-\omega ^i}$. Then, let $\pi _i=g^{q_i(\tau )}$ be an evaluation proof for $\psi _i(\omega ^i)=A'(\omega ^i)$ where $q_i(X) = \frac{\psi _i(X)-A'(\omega ^i)}{X-\omega ^i}$ and note that $Q_i(X)=\frac{1}{A'(\omega ^i)}q_i(X)$. Thus, computing all $u_i$’s reduces to computing all $\pi _i$’s. However, since each proof $\pi _i$ is for a different polynomial $\psi _i(X)$, directly applying FK does not work. Instead, we give a new algorithm that leverages the structure of $\psi _i(X)$ when divided by $X-\omega ^i$. Specifically, in  [TAB+20, Appendix B], we show that:

$$\begin{aligned} q_i(X)&= \sum _{j\in [0,n-2]} H_j(X) \omega ^{ij},\forall i \in [0,n),\ \text {where}\ H_j(X) = (j+1) X^{(n-2)-j} \end{aligned}$$

(11)

If we let $h_j$ be a KZG commitment to $H_j(X)$, then we have $\pi _i = \prod _{j\in [0,n-2]} h_j^{(\omega ^{ij})}$, $\forall i \in [0,n)$. Next, recall that the Discrete Fourier Transform (DFT) on a vector of group elements ${\mathbf {a}}=[a_0, a_1, \dots , a_{n-1}]\in \mathbb {G}^n$ is:

$$\begin{aligned} \mathsf {DFT}_n({\mathbf {a}}) = {\mathbf {\hat{a}}}=[\hat{a}_0, \hat{a}_1, \dots , \hat{a}_{n-1}]\in \mathbb {G}^n,\ \text {where}\ \hat{a}_i= \prod _{j\in [0,n)} a_j^{(\omega ^{ij})} \end{aligned}$$

(12)

If we let ${\mathbf {\pi }}=[\pi _0, \pi _1, \dots , \pi _{n-1}]$ and ${\mathbf {h}} = [h_0, h_1, \dots , h_{n-2}, 1_\mathbb {G}, 1_\mathbb {G}]$, then ${\mathbf {\pi }} = \mathsf {DFT_n}({\mathbf {h}})$. Thus, computing all n $h_i$’s takes O(n) time and computing all n $\pi _i$’s takes an $O(n\log {n})$ time DFT. As a result, computing all $u_i$’s from the $(g^{\tau ^i})$’s takes $O(n\log {n})$ time overall.

3.4.5 Correctness and Security

The correctness of our aSVC scheme follows naturally from Lagrange interpolation. Aggregation and proof updates are correct by the arguments laid out in Sects. 3.4.1 and 3.4.2, respectively. Subvector proofs are correct by the correctness of KZG batch proofs  [KZG10]. We prove our aSVC is position binding and has update key uniqueness in the extended version   [TAB+20, Appendix C].

4 A Highly-Efficient Stateless Cryptocurrency

In this section, we enhance Edrax’s elegant design by replacing their VC with our secure aggregatable subvector commitment (aSVC) scheme from Sect. 3.3. As a result, our stateless cryptocurrency has smaller, aggregatable proofs and smaller update keys. This leads to smaller, faster-to-verify blocks for miners and faster proof synchronization for users (see Table 1). Furthermore, our verifiable update keys reduce the storage overhead of miners from O(n) update keys to O(1). We also address a denial of service (DoS) attack in Edrax’s design.

4.1 From VCs to Stateless Cryptocurrencies

Edrax pioneered the idea of building account-based, stateless cryptocurrencies on top of any VC scheme  [CPZ18]. In contrast, previous approaches were based on authenticated dictionaries (ADs)  [RMCI17, But17], for which efficient constructions with static update keys are not known. In other words, these AD-based approaches used dynamic update hints $\mathsf {uph} _j$ consisting of the proof for position j. This complicated their design, requiring user i to ask a proof-serving node for user j’s proof in order to create a transaction sending money to j.

Trusted Setup. To support up to n users, public parameters $(\mathsf {prk},\mathsf {vrk}, (\mathsf {upk} _i)_{i\in [0,n)})\leftarrow \mathsf {VC}.\mathsf {KeyGen} (1^{\lambda }, n)$ are generated via a trusted setup, which can be decentralized using MPC protocols  [BGM17]. Miners need to store all O(n) update keys to propose blocks and to validate blocks (which we fix in Sect. 4.2.2). The $\mathsf {prk}$ is only needed for proof-serving nodes (see Sect. 4.3.2).

The (Authenticated) State. The state is a vector ${\mathbf {v}}=(v_i)_{i\in [0,n)}$ of size n that maps user i to $v_i=(\mathsf {addr} _i|\mathsf {bal} _i)\in \mathbb {Z}_p$, where $\mathsf {bal} _i$ is her balance and $\mathsf {addr} _i$ is her address, which we define later. (We discuss including transaction counters for preventing replay attacks in Sect. 4.3.1.) Importantly, since $p \approx 2^{256}$, the first 224 bits of $v_i$ are used for $\mathsf {addr} _i$ and the last 32 bits for $\mathsf {bal} _i$. The genesis block’s state is the all zeros vector with digest $d_0$ (e.g., in our aSVC, $d_0=g^0$). Initially, each user i is unregistered and starts with a proof $\pi _{i,0}$ that their $v_i = 0$.

“Full” vs. “Traditional” Public Keys. User i’s address is computed as $\mathsf {addr} _i=H(\mathbf {\mathsf {FPK}} _i)$, where $\mathbf {\mathsf {FPK}} _i=(i,\mathsf {upk} _i,\mathsf {tpk} _i)$ is her full public key. Here, $\mathsf {tpk} _i$ denotes a “traditional” public key for a digital signature scheme, with corresponding secret key $\mathsf {tsk} _i$ used to authorize user i’s transactions. To avoid confusion, we will clearly refer to public keys as either “full” or “traditional.”

Registering via INIT  Transactions. INIT transactions are used to register new users and assign them a unique, ever-increasing number from 1 to n. For this, each block t stores a count of users registered so far $\mathsf {cnt} _t$. To register, a user generates a traditional secret key $\mathsf {tsk}$ with a corresponding traditional public key $\mathsf {tpk}$. Then, she broadcasts an INIT transaction:

$$\mathsf {tx} =[\texttt {INIT}, \mathsf {tpk} ]$$

A miner working on block ${t+1}$ who receives $\mathsf {tx}$, proceeds as follows.

• 1. He sets $i=\mathsf {cnt} _{t+1}$ and increments the count $\mathsf {cnt} _{t+1}$ of registered users,

• 2. He updates the VC via $d_{t+1}=\mathsf {VC}.\mathsf {UpdateComm} (d_{t+1}, (\mathsf {addr} _i\vert 0), i, \mathsf {upk} _i)$,

• 3. He incorporates $\mathsf {tx}$ in block $t+1$ as $\mathsf {tx} ' = [\texttt {INIT}, (i, \mathsf {upk} _i,\mathsf {tpk} _i)]=[\texttt {INIT}, \mathbf {\mathsf {FPK}} _i]$.

The full public key with $\mathsf {upk} _i$ is included so other users can correctly update their VC when they process $\mathsf {tx} '$. Note that to compute $\mathsf {addr} _i=H(\mathbf {\mathsf {FPK}} _i)$, the miner needs to have the correct $\mathsf {upk} _i$ which requires O(n) storage. We discuss how to avoid this in Sect. 4.2.2.

Transferring Coins via SPEND  Transactions. When transferring v coins to user j, user i (who has $v'\ge v$ coins) must first obtain $\mathbf {\mathsf {FPK}} _j=(j, \mathsf {upk} _j,\mathsf {tpk} _j)$. This is similar to existing cryptocurrencies, except the (full) public key is now slightly larger. Then, user i broadcasts a SPEND transaction, signed with her $\mathsf {tsk} _i$:

$$\mathsf {tx} =[\texttt {{SPEND}}, t, \mathbf {\mathsf {FPK}} _i, j, \mathsf {upk} _j, v,\pi _{i,t}, v']$$

A miner working on block ${t+1}$ processes this SPEND transaction as follows:

• 1. He checks that $v\le v'$ and verifies the proof $\pi _{i,t}$ that user i has $v'$ coins via $\mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, d_t, (\mathsf {addr} _i|v'), i, \pi _{i,t})$. (If the miner receives another transaction from user i, it needs to carefully account for i’s new $v'-v$ balance.)

• 2. He updates i’s balance in block $t+1$ with $d_{t+1}=\mathsf {VC}.\mathsf {UpdateComm} (d_{t+1}, -v, i$, $\mathsf {upk} _i)$, which only sets the lower order bits of $v_i$ corresponding to $\mathsf {bal} _i$, without touching the higher order bits for $\mathsf {addr} _i$.

• 3. He does the same for j with $d_{t+1}=\mathsf {VC}.\mathsf {UpdateComm} (d_{t+1}$, $+v, j, \mathsf {upk} _j)$.

Validating Blocks. Suppose a miner receives a new block $t+1$ with digest $d_{t+1}$ that has b SPEND transactions:

$$\mathsf {tx} =[\texttt {{SPEND}}, t, \mathbf {\mathsf {FPK}} _{i}, {j}, \mathsf {upk} _{j}, v, \pi _{i,t}, v']$$

To validate this block, the miner (who has $d_t$) proceeds in three steps (INIT transactions can be handled analogously):

Step 1: Check Balances. First, for each $\mathsf {tx}$, he checks that $v \le v'$ and that user i has balance $v'$ via $\mathsf {VC}.\mathsf {VerifyPos} (\mathsf {vrk}, d_t$, $(\mathsf {addr} _{i}|v'), i, \pi _{i,t})=T$. Since the sending user i might have multiple transactions in the block, the miner has to carefully keep track of each sending user’s balance to ensure it never goes below zero.

Step 2: Check Digest. Second, he checks $d_{t+1}$ has been computed correctly from $d_t$ and from the new transactions in block $t+1$. Specifically, he sets $d'=d_t$ and for each $\mathsf {tx}$, he computes $d' = \mathsf {VC}.\mathsf {UpdateComm} (d', -v, i, \mathsf {upk} _{i})$ and $d'=\mathsf {VC}.\mathsf {UpdateComm} (d',+v$, $j,\mathsf {upk} _{j})$. Then, he checks that $d'=d_{t+1}$.

Step 3: Update Proofs, If Any. If the miner lost the race to build block $t+1$, he can start mining block $t+2$ by “moving over” the SPEND transactions from his unmined block. For this, he updates all proofs in those SPEND transactions, so they are valid against the new digest $d_{t+1}$. Similarly, the miner must also “move over” all INIT transactions, since block $t+1$ might have registered new users.

User Proof Synchronization. Consider a user i who has processed the ledger up to time t and has digest $d_t$ and proof $\pi _{i,t}$. Eventually, she receives a new block $t+1$ with digest $d_{t+1}$ and needs to update her proof so it verifies against $d_{t+1}$. Initially, she sets $\pi _{i,t+1} = \pi _{i,t}$. For each $[\texttt {INIT},\mathbf {\mathsf {FPK}} _j]$ transaction, she updates her proof $\pi _{i,t+1} = \mathsf {VC}.\mathsf {UpdateProof} (\pi _{i,t+1}, (H(\mathbf {\mathsf {FPK}} _j)|0), i,j, \mathsf {upk} _i, \mathsf {upk} _j)$. For each $[\texttt {{SPEND}}, t, \mathbf {\mathsf {FPK}} _j, k, \mathsf {upk} _k, v,\pi _{j,t}, v']$, she updates her proof twice: $\pi _{i,t+1} =\mathsf {VC}.\mathsf {UpdateProof} (\pi _{i,t+1}, -v, i,j, \mathsf {upk} _i,\mathsf {upk} _j)$ and $\pi _{i,t+1} =\mathsf {VC}.\mathsf {UpdateProof} (\pi _{i,t+1}$, $+v, i, k, \mathsf {upk} _i,\mathsf {upk} _k)$. We stress that users can safely be offline and miss new blocks. Eventually, when a user comes back online, she downloads the missed blocks, updates her proof and is ready to transact.

4.2 Efficient Stateless Cryptocurrencies from aSVCs

In this subsection, we explain how replacing the Edrax VC with our aSVC from Sect. 3.3 results in a more efficient stateless cryptocurrency (see Table 1). Then, we address a denial of service attack on user registrations in Edrax.

4.2.1 Smaller, Faster, Aggregatable Proofs

Our aSVC enables miners to aggregate all b proofs in a block of b transactions into a single, constant-sized proof. This drastically reduces Edrax’s per-block proof overhead from $O(b\log {n})$ group elements to just one group element. Unfortunately, the b update keys cannot be aggregated, but we still reduce their overhead from $O(b\log {n})$ to b group elements per block (see Sect. 4.2.3). Our smaller proofs are also faster to update, taking O(1) time rather than $O(\log {n})$. While verifying an aggregated proof in our aSVC is $O(b\log ^2{b})$ time, which is asymptotically slower than the O(b) time for verifying b individual ones, it is still concretely faster as it only requires two, rather than O(b), cryptographic pairings. This makes validating new blocks much faster in practice.

4.2.2 Reducing Miner Storage Using Verifiable Update Keys

We stress that miners must validate update keys before using them to update a digest. Otherwise, they risk corrupting that digest, which results in a denial of service. Edrax miners sidestep this problem by simply storing all O(n) update keys. Alternatively, Edrax proposes outsourcing update keys to an untrusted third party via a static Merkle tree. Unfortunately, this would either require interaction during block proposal and block validation or would double the update key size. Our implicitly-verifiable update keys avoid these pitfalls, since miners can directly verify the update keys in a SPEND transaction via $\mathsf {VC}$.$\mathsf {VerifyUPK}$. Furthermore, for INIT transactions, miners can fetch (in the background) a running window of the update keys needed for the next k registrations. By carefully upper-bounding the number of registrations expected in the near future, we can avoid interaction during the block proposal. This background fetching could be implemented in Edrax too, either with a small overhead via Merkle proofs or by making their update keys verifiable (which seems possible).

4.2.3 Smaller Update Keys

Although, in our aSVC, $\mathsf {upk} _i$ contains $a_i=g^{A(\tau )/(X-\omega ^i)}$ and $u_i=g^{\frac{\mathcal {L}_i(\tau )-1}{X-\omega ^i}}$, miners only need to include $a_i$ in the block. This is because of two reasons. First, user i already has $u_i$ to update her own proof after changes to her own balance. Second, no other user $j\ne i$ will need $u_i$ to update her proof $\pi _j$. However, as hinted in Sect. 4.1, miners actually need $u_i$ when only a subset of i’s pending transactions get included in block t. In this case, the excluded transactions must have their proofs updated using $u_i$ so they can be included in block $t+1$. Fortunately, this is not a problem, since miners always receive $u_i$ with user i’s transactions. The key observation is that they do not have to include $u_i$ in the mined block, since users do not need it.

4.2.4 Addressing DoS Attacks on User Registrations.

Unfortunately, the registration process based on INIT transactions is susceptible to Denial of Service (DoS) attacks: an attacker can simply send a large number of INIT transactions and quickly exhaust the free space in the vector ${\mathbf {v}}$. There are several ways to address this. First, one can use an aSVC from hidden-order groups, which supports an unbounded number of elements  [CFG+20]. However, that would negatively impact performance. Second, as future work, one could develop and use unbounded, authenticated dictionaries with scalable updates. Third, one could simply use multiple bounded aSVCs together with cross-commitment proof aggregation, which our aSVC supports  [GRWZ20]. Lastly, one can add a cost to user registrations via a new INITSPEND transaction that registers a user j by having user i send her some coins:

$$[\texttt {INITSPEND}, t, \mathbf {\mathsf {FPK}} _i, \mathsf {tpk},v,\pi _{i,t}, v'],\ \text {where}\ 0 < v \le v'$$

Miners processing this transaction would first register a new user j with traditional public key $\mathsf {tpk}$ and then transfer her v coins. We stress that this is how existing cryptocurrencies operate anyway: in order to join, one has to be transferred some coins from existing users. Lastly, we can ensure that each $\mathsf {tpk}$ is only registered once by including in each INIT/INITSPEND transaction a non-membership proof for $\mathsf {tpk}$ in a Merkle prefix tree of all TPKs. We leave a careful exploration of this to future work.

Finally, miners (and only miners) will be allowed to create a single $[\texttt {INIT}, \mathbf {\mathsf {FPK}} _i]$ transaction per block to register themselves. This has the advantage of letting new miners join, without “permission” from other miners or users, while severely limiting DoS attacks, since malicious miners can only register a new user per block. Furthermore, transaction fees and/or additional proof-of-work can also severely limit the frequency of INITSPEND transactions.

4.2.5 Minting Coins and Transaction Fees

Support for minting new coins can be added with a new MINT transaction type:

$$\mathsf {tx} = [\texttt {MINT}, i, \mathsf {upk} _i, v]$$

Here, i is the miner’s user account and v is the amount of newly minted coins. (Note that miners must register as users using $\texttt {INIT}$ transactions if they are to receive block rewards.) To support transaction fees, we can extend the SPEND transaction format to include a fee, which is then added to the miner’s block reward specified in the MINT transaction.

4.3 Discussion

4.3.1 Making Room for Transaction Counters

As mentioned in Sect. 2.2, to prevent transaction replay attacks, account-based stateless cryptocurrencies such as Edrax should actually map a user i to $v_i = (\mathsf {addr} _i\vert c_i\vert \mathsf {bal} _i)$, where $c_i$ is her transaction counter. This change is trivial, but does leave less space in $v_i$ for $\mathsf {addr} _i$, depending on how many bits are needed for $c_i$ and $\mathsf {bal} _i$. (Recall that $v_i\in \mathbb {Z}_p$ typically has $\approx$ 256 bits.) To address this, we propose using one aSVC for mapping i to $\mathsf {addr} _i$ and another aSVC for mapping i to $(c_i\vert \mathsf {bal} _i)$. Our key observation is that if the two aSVCs use different n-SDH parameters (e.g., $(g^{\tau ^i})$’s and $(h^{\tau ^i})$’s, such that $\log _g{h}$ is unknown), then we could aggregate commitments, proofs and update keys so as to introduce zero computational and communication overhead in our stateless cryptocurrency. Security of this scheme could be argued similar to security of perfectly hiding KZG commitments  [KZG10], which commit to $\phi (X)$ as $g^{\phi (\tau )}h^{r(\tau )}$ in an analogous fashion. We leave investigating the details of this scheme to future work.

4.3.2 Overhead of Synchronizing Proofs

In a stateless cryptocurrency, users need to keep their proofs updated w.r.t. the latest block. For example, in our scheme, each user spends $O(b\cdot \varDelta {t})$ time updating her proof, if there are $\varDelta {t}$ new blocks of b transactions each. Fortunately, when the underlying VC scheme supports precomputing all n proofs fast  [Tom20], this overhead can be shifted to untrusted third parties called proof-serving nodes  [CPZ18]. Specifically, a proof-serving node would have access to the proving key $\mathsf {prk}$ and periodically compute all proofs for all n users. Then, any user with an out-of-sync proof could ask a node for their proof and then manually update it, should it be slightly out of date with the latest block. Proof-serving nodes save users a significant amount of proof update work, which is important for users running on constrained devices such as mobile phones.

5 Conclusion

In this paper, we formalized a new cryptographic primitive called an aggregatable subvector commitment (aSVC) that supports aggregating and updating proofs (and commitments) using only constant-sized, static auxiliary information referred to as an “update key.” We constructed an efficient aSVC from KZG commitments to Lagrange polynomials which, compared to other pairing-based schemes, can precompute, aggregate and update proofs efficiently and, compared to schemes from hidden-order groups, has smaller proofs and should perform better in practice. Lastly, we continued the study of stateless validation initiated by Chepurnoy et al., improving block validation time and block size, while addressing attacks and limitations. We hope our work will ignite further research into stateless validation for payments and smart contracts and lead to improvements both at the theoretical and practical level.