Linear-map Vector Commitments and their Practical Applications

? Matteo Campanelli¹, Anca Nitulescu¹, Carla Rafols², Alexandros Zacharakis², and Arantxa Zapico².

¹ Protocol Labs fmatteo, ancag@protocol.ai

² Universitat Pompeu Fabra fcarla.rafols, alexandros.zacharakis, arantxa.zapicog@upf.edu

Abstract.

Vector commitments (VC) are a cryptographic primitive that allow one to commit to a vector and then \open" some of its positions eciently. Vector commitments are increasingly recognized as a central tool to scale highly decentralized networks of large size and whose content is dynamic. In this work, we examine the demands on the properties that an ideal vector commitment should satisfy in the light of the emerging plethora of practical applications and propose new constructions that improve the state-of-the-art in several dimensions and oer new tradeos. We also propose a unifying framework that captures several constructions and show how to generically achieve some properties from more basic ones. On the practical side, we focus on building ecient schemes that do not require new trusted setup (we can reuse existing ceremonies for pairing-based \powers of tau" run by realworld systems such as ZCash or Filecoin). Our (in-progress) implementation demonstrates that our work over-performs in eciency prior schemes with same properties.

Our contributions can be resumed as follows:

{ Theoretical Formalisation: We formally dene the notion of Linear Map Vector Commitments (LVC) inspired by the work of Lai and Malavolta [CRYPTO19]. Our denition aims at recovering all previous notions of VC and include properties such as updatability, aggregation and homomorphism. We introduce a stronger new unbounded aggregation concept that allows to aggregate multiple times without a disaggregation procedure. This relaxes incremental aggregation which is hard to achieve in general.

{ Black-box Frameworks for LVC: We show how to lift the homomorphic properties of a simple LVC in order to obtain an LVC with unbounded aggregation and/or updatability. We also show that we m n can construct generic LVC (i.e. for any f : F*!* F) fro^m homomorphic LVC for a more restricted class of openings, inner-products IP (for n = 1).

$$ f:\mathbb{F}^{m}\rightarrow\mathbb{F}^{n}) $$

{ VC Constructions: We show two pairing-based LVC constructions for inner products IP based on the properties of monomial and Lagrange polynomial basis. We prove that the two satisfy all the relevant homomorphic properties to obtain unbounded aggregation and transformation to LVC. We also extend such schemes to support subvector openings SVC in a native way for special subsets or via aggregation for generic subsets.

{ Adding Maintainability: We present two novel maintainable VC constructions that can be instantiated from any underlying VC scheme with homomorphic proofs. We show how to achieve a stronger, more exible form of maintainability: our schemes allow to arbitrary tune the memory used to save on the opening time to obtain the desired trade-o. Both constructions are based on the tensor structure of multivariate and univariate polynomials:

1.The multivariate case is a generalisation of a recent work, Hyperproofs that uses binary trees: we allow for any arity for the trees, so proofs are shorter and the leaves can be commitments for any LVC scheme, to allow more expressivity.

2.The univariate construction is inspired by this generalization and it has the additional feature that the setup is independent of the trade-o, so the memory used can be decided by the prover on the y.

^? Arantxa Zapico has been funded by a Protocol Labs PhD Fellowship PL-RGP1-2021-062. Alexandros Zacharakis has been partially funded by Protocol Labs Research Grant PL-RGP1-2021-048

Table of Contents

Linear-map Vector Commitments and their Practical Applications ..... 1 Matteo Campanelli$^1$, Anca Nitulescu$^1$, Carla Ràfols$^2$, Alexandros Zacharakis$^2$, and Arantxa Zapico$^{23}$.

1 Introduction ..... 3 1.1 Motivation for Better Vector Commitments ..... 3 1.2 Desired Properties and Limitations ..... 4 1.3 Our Contributions ..... 5 1.4 Related Work ..... 6

2 Preliminaries ..... 7

3 Definitions: Linear-map Vector Commitments ..... 8 3.1 Homomorphic Properties for LVC ..... 9

4 Generic Constructions from Homomorphic Proofs ..... 10 4.1 New Notion: Unbounded Aggregation ..... 10 4.2 Unbounded Aggregation for LVC ..... 11 4.3 From Inner-Products to Arbitrary Linear-Maps ..... 13 4.4 Updability for LVC ..... 13

5 Constructions for Inner-Pairing VC ..... 14 5.1 Monomial Basis ..... 14 5.2 Lagrange Basis ..... 17

6 Subvector Openings ..... 19 6.1 Special Subset Native Openings for the Monomial Basis ..... 20 6.2 Any Subset Non-native Openings for the Monomial Basis ..... 20 6.3 Any Subset Openings from Lagrange Basis ..... 20

7 Implementation and Experimental Evaluation for LVC ..... 21 7.1 Comparison with SNARKs over Merkle Trees ..... 21 7.2 Proving time for Range Queries ..... 22 7.3 Verification for Any Subsets ..... 22

8 Maintainable Vector Commitment Schemes ..... 24 8.1 Multivariate Case ..... 24 8.2 Efficiency of the Multivariate Construction ..... 29 8.3 Univariate Maintainable Vector Commitments ..... 29

A Vector Commitment Definitions ..... 34

B Vector Commitment Applications ..... 35 B.1 Verifiable Databases ..... 36 B.2 Stateless Cryptocurrency ..... 36 B.3 Proof of Space ..... 37 B.4 Compiling SNARKs from Vector Commitments ..... 38 B.5 Applications of Range Openings ..... 38

C Native SVC in [29] ..... 38

D Complementary material of section 8 ..... 39 D.1 PST polynomial commitment ..... 39 D.2 Completeness of UVTree construction ..... 40 D.3 Lagrange basis IP for Cosets of Roots of Unity ..... 42

1 Introduction

Vector commitment schemes [22, 7] (or VC) allow a party to commit to a vector v through a short digest and then open some of its elements guaranteeing position binding⁴ (one should not be able to open a commitment at position i to two dierent values vⁱ6= vⁱ⁰). For this primitive to be interesting the proof of opening|or just \opening"|should be of size sublinear in m, the size of the committed vector. A vector commitment with subvector opening also supports a short opening for arbitrary subsets of positions I (rather than individual ones only). More specically this opening should be of size independent, not only of m, but of jIj. We denote commitment schemes with such property as SVC [20](also called VC with batch opening in [4]).

$$ v_{i}\neq v_{i}^{\prime}) $$

Functional Vector Commitments, rst introduced by Libert, Ramanna and Yung in [21], capture the ability to compute commitments to vectors and later perform openings of linear functions (inner-products) ^m n f : F*!* F of these vectors, for some eld F.

$$ f:\mathbb{F}^{m}\rightarrow\mathbb{F}^{n} $$

Both vector commitments with subvector openings and functional commitments for inner-products can be captured as vector commitments with openings for a more general class of function families, linear-maps. Lai and Malavolta [20] were the rst to introduce Linear Map Commitments (LMC). In such a scheme, the prover is able to open the commitment to some vector v to the output of multiple linear functions or, m n equivalently, to the output of one linear-^map f : F*!* F, by producing a single short proof. In this work, we revisit Lai and Malavolta [20] LMC notion and augment it to a full-featured vector commitment generic denition that recovers all previously-dened schemes and more. We call our primitive Linear Map Vector Commitment and use LVC for short⁵.

$$ f:\mathbb{F}^{m}\rightarrow\mathbb{F}^{n} $$

1.1 Motivation for Better Vector Commitments

Vector commitments are very useful to scale highly decentralized networks of large size and whose content is dynamic [8, 4, 6, 15](such dynamic content can be the state of a blockchain, amount stored on a wallet, the value of a le in a decentralized storage network, etc.). Beyond the basic requirement that openings should be ecient, in this work we also discuss how to achieve some additional properties of LVC. We discuss some of the most prominent applications of LVC to motivate and justify the importance of these properties in practice.

Veriable Databases. One of the applications that can be signicantly improved by Vector Commitments is Veriable Databases (VDB). In this setting, a client outsources the storage of a database to a server while keeping the ability to access and change some of its records, i.e. query functions of the data and update some of the data and ensure the server does not tamper with the data. Solutions using (binding) commitment schemes provide security but not eciency in such a setting. A popular instantiation that achieves both of them are Merkle trees [23], but these are clearly not expressive enough to allow for functional openings.

For a VC scheme to be the ideal solution for VDB application, we require to additionally support ecient updates and expressive openings. For example, a LVC scheme that allow the client to update records of the database in sublinear time and to verify linear-map queries at almost the same cost as simple position openings is a great improvement over current solutions.

Stateless Cryptocurrency. A recent application that motivated more ecient constructions of VC schemes is stateless cryptocurrency, i.e. a payment system based on a distributed ledger where neither validators of transactions nor system users need to store the full ledger state.

The ideal vector commitment scheme that provides the best trade-o between storage, bandwidth, and computation in this setting should have all of the following properties: it must have small commitment size, short proofs, ecient computation for openings and it should allow for proof updates and for aggregation to minimise communication in the transactions and maintainability for the proofs, that allows to update all pre-stored proofs in sublinear time.

⁴ For the applications considered in this work, hiding properties are not necessary. In particular our commitments are deterministic.

⁵ We prefer LVC rather than initially proposed LMC in order to emphasise the Vector Commitment aspect of our notion.

Proof of Space. Proof of Space (PoS) is a protocol that allows miners (storage providers) to convince the network that they are dedicating physical storage over time in an ecient way. In a nutshell, a miner commits to a le (data) that uses a specied amount of disk space and then the miner proves that it continues to store the data by answering to recurring audits that consist of random spot-checks.

A PoS construction based on vector commitments, as described in [12], requires short opening proofs for subvectors to be stored in a blockchain, cross-commitments aggregation techniques and the possibility to implement space-time tradeos to reduce the proving time for the miner (ideally sublinear in the size of the vector).

\Caching" Optimizations. In some applications, e.g. when performing HTTP queries, clients use the so-called prefetching⁶ and receive from a server not only the values of interest but other related values that could potentially be queried in the near future (e.g., values in a neighboring range of the queried values). Vector commitments with ecient proofs for special (\caching") subset openings allow to add veriability to such queries in a way that does not aect the speed of the server since the proving procedure for a bigger subset is close or the same as for individual positions.

1.2 Desired Properties and Limitations

At the very least basic a LVC should be ecient (small proof size and low opening/verifying computational needs). Obviously, the same design goals as with other cryptographic protocols apply, i.e. ideally one would like to prove security under as standard assumptions as possible.

Reusable setup refers to the structured reference string (SRS) that many pairing-based schemes use as public parameters. Ideally, one would like to have a transparent setup that does not rely on any trusted parameter generation. It is common to sacrice this goal for eciency and settle for a trusted setup that can be generated in a ceremony. But such ceremonies are complicated to implement⁷, so it is interesting to design LVC that can reuse existing setups for other primitives and do not have special SRS distributions.

Expressivity refers to the opening possibilities. One would like VC to be as expressive as possible, meaning that it should be possible to open to functions of the vector as general as possible (subvector openings, linear or arbitrary functions).

Proof Aggregation captures the ability to \pack" two or more proofs together obtaining a new proof for their combined claims (e.g. f (v) = y and f⁰(v) = y⁰). This should be done without knowledge of the opening of the vector and aggregation cost should be sublinear in the vector length. Importantly, the resulting proof should not signicantly grow each time we perform an aggregation. One-hop aggregation allows only to aggregate fresh proofs. Ideally, one would also want to aggregate already aggregated proofs.

$$ \mathbf{f}(\mathbf{v})=y $$

$$ \mathbf{f}^{\prime}(\mathbf{v})=y^{\prime}) $$

Updatability allows to eciently update opening proofs: if C is a commitment to v and a position needs to be updated resulting in a new commitment C⁰, an updatable VC must provide a method to update an opening_ffor a function f that is valid for C into a new opening for the same function that is valid for the new commitment C⁰. The new opening should be computed by only knowing the portion of the vector that is supposed to change and in time faster than recomputing the opening from scratch.

$$ \pi_{f} $$

Maintainability aims in amortizing the proving costs in systems where committed values have a long life span and evolve over time. This is achieved by means of dedicated memory to reduce the computation time needed to open proofs. Concretely, the property requires that (1) one can eciently store some values to reduce the cost of computing any individual openings (2) after updating a single position of the committed vector, it should be possible to update all proofs in time sublinear in the size of the vector (less than computing a single proof from scratch in some cases).

Homomorphic properties apply to commitments as well as to proofs. An LVC has homomorphic commitments if it is possible to meaningfully combine commitments without knowing their openings: that is, from

⁶ https://developer.mozilla.org/en-US/docs/Web/HTTP/Link_prefetching_FAQ

⁷ This remains true even if many setups are updatable [18] and they can be generated and updated non-interactively in a secure way as long as one party is honest. There might be issues if not enough parties participate in generating the SRS or updates are not properly validated.

commitments C₁ and C₂ to v₁ and v₂, any party must be able to compute a commitment to v₁+ v₂ for any ; 2 F. The scheme has homomorphic openings if it is possible to derive a proof that f(v₁ + v₂) = y₁ + y₂ from proofs for the claims f(v₁) = y₁ and f(v₂) = y₂. Finally, a vector commitment scheme has homomorphic proofs when it is possible to combine proofs of statements for dierent functions but same vector. As we will see, this property is interesting for its implications.

$$ C_{1} $$

$$ C_{2} $$

$$ \alpha\mathbf{v}{1}!+!\beta\mathbf{v}{2} $$

$$ \mathbf{v}{}_{2} $$

$$ \mathbf{v}_{1} $$

$$ \alpha,\beta\in\mathbb{F} $$

$$ f(\mathbf{v}{1}!+!\mathbf{v}{2})=\mathbf{y}{1}!+!\mathbf{y}{2} $$

$$ f(\mathbf{v}{1})=\mathbf{y}{1} $$

$$ f(\mathbf{v}{2})=\mathbf{y}{2} $$

1.3 Our Contributions

Theoretical Advances. On the theoretical frontier, we unify previous denitions and augment them with additional properties. The basic notion we use is Linear Map Vector Commitments (LVC) and is inspired by the work of Lai and Malavolta [20]. We then dene additional properties on top of this denition and explore their relations. Specically, we augment this notion with updatability and aggregation properties, including a novel notion -unbounded aggregation- capturing the ability to aggregate already aggregated proofs but relaxing incremental aggregation [6] in the sense that the verier is allowed to do work linear in the number of aggregation hops (i.e. aggregation is \history" dependent), also, disaggregation is not possible. We show that having additional homomorphic properties is highly desirable, by arguing that any LVC that satises them: (1) can be augmented with unbounded aggregation as well as updatability; (2) can support general m n linear map openings (i.e. for any f : F*!* F) as loⁿg as it supports inner product openings (i.e. for ^m f⁰ : F*!* F). This allows us to focus on ecient constructions for inner products with homomorphic properties.

$$ f,:,\mathbb{F}^{m},\rightarrow,\mathbb{F}^{n}) $$

$$ f^{\prime},:,\mathbb{F}^{m},\rightarrow,\mathbb{F} $$

VC Constructions. First, we present two pairing-based LVC constructions for inner products based on the properties of monomial and Lagrange polynomial basis and prove that they satisfy all the relevant homomorphic properties to obtain unbounded aggregation and support general linear maps. In terms of expressivity, these constructions generalize previous work [28, 29] by supporting linear functions instead of position or subvector openings. Vector commitments for this class of functions are core components of important primitives such as arguments of knowledge for Inner Product (IP) relations or aggregation arguments [9].

Second, we present two novel maintainable constructions by exploiting the tensor structure of multivariate and univariate polynomials. These constructions allow a stronger, more exible form of maintainability: they support an arbitrary memory/time trade-o for openings, meaning that one can decide how much memory it wants to use to reduce the opening time.

The multivariate case is a generalization of Hyperproofs [28] in several dimensions. Roughly speaking maintanability is achieved in Hyperproofs by constructing a binary tree of proofs where at the leaves there are the values of individual positions. We present a single construction that can be instantiated in several ways (recovering Hyperproofs as a special case) with these features: (i) the tree can be of any arity, so proofs are shorter⁸; (ii) the leaves can be commitments for any LVC and not only individual openings, to achieve a fully exible trade-o. As a result of (ii), the scheme is more expressive (as it can support openings to linear functions/subvector openins at leaf level if the underlying commitment supports it).

The univariate construction is inspired by this generalization and it has the additional feature that the setup is independent of the trade-o, and can be decided by the prover on the y.

Practical Improvements. As in some applications like Proof of Space, the subset of opened positions is not very meaningful and its distribution is expected to be known in advance, we study how to improve verication eciency for certain special subsets I openings in our inner-product constructions. For some structured sets I, we achieve a verier that performs half of the work it does for arbitrary sets J of the same size in the Lagrange construction, and only a constant number of group operations in the one that uses the monomial basis.

$$ I, $$

⁸ If one uses the Inner Pairing Product argument of Bunz et al. [5] on top of PST commitments as suggested in Hyperproofs the dierence in proof size is not so relevant, but IPP will be much cheaper to run.

$$ O(n) $$

Table 1: Comparison of our LVCs with other aggregatable VC schemes (aggSVC) designed for Stateless Cryptocurrencies and Proof of Space applications. All schemes have O(1)-sized proofs that verify in O(1) time and can update commitments in O(1) time.

| VC Scheme | Setup | Homomorphic Aggregation | | $|\pi|$ | Prove | OpenAll | UpdateAll | | --- | --- | --- | --- | --- | --- | --- | --- | | Merkle Trees | Transparent | × | SNARK | log m | O(k) | O(m) | O(k+logm') | | Hyperproofs[28] | Trusted | √ | IPP | log m | O(k) | O(m logm') | O(logm') | | Our Multivariate LVC | Trusted | √ | IPP | log$\ell$m' | O(k) | O(m logm') | O(logm') | | Our Univariate LVC | Reusable | √ | IPP | logm' | O(k) | O(m logm') | O(logm') |

$$ |\pi| $$

$$ \overline{{O(k+\log m^{\prime})}} $$

$$ O(\log m^{\prime}) $$

$$ \checkmark $$

$$ \log_{\ell}m^{\prime}\ O(k)\ O(m\log m^{\prime}) $$

$$ \overline{{O(\ g m^{\prime})}} $$

$$ \checkmark $$

$$ \overline{{{\log},,m^{\prime},O(k),O(m\log m^{\prime})}} $$

$$ \ (\log m^{\prime}) $$

Table 2: Comparison of our schemes with other maintainable VC. We consider vectors of dimension m = k m⁰ where m⁰ is the amount of memory dedicated for storing proofs. All schemes are aggregatable using generic techniques, SNARKs or Inner Pairing Products [5]. All times/sizes omit the dependence on the security parameter. We omit constant additive terms from proof sizes. In the multivariate construction, ‘ refers to a constant parameter.

$$ m=k\cdot m^{\prime} $$

$$ m^{\prime} $$

Second, we mitigate the challenges of deploying these constructions due to their need of a trusted setup. With the exception of the multivariate variant of the maintainable construction, all our constructions can reuse trusted setups such as \powers of tau" that were run for pairing-based SNARK schemes used in real- 9 world applications., as opposed to for example [15], in which a certain middle power of needs to be missing in the SRS. In Appendix 7 we demonstrate the practical benets of our special subset construction by providing an implementation and comparisons with current solutions.

1.4 Related Work

Vector commitments were fully formalized in [7] and two rst constructions were proposed under standard, constant-size, assumptions: CDH in bilinear groups and RSA respectively. Many following works built on these constructions to obtain better eciency and more properties such as subvector openings, functional openings, aggregation, updates and variants of these. A number of constructions [6, 4] use the properties of hidden order groups to achieve constructions with attractive features such as constant size parameters or incremental aggregation but are concretely less ecient than pairing-based constructions.

The VC schemes based on bilinear groups made their way into oering an alternative to Merkle trees which are widely used in practice nowadays. Merkle trees are quite ecient and only need a transparent setup. They also oer natural time-memory tradeos due to their tree structure. Nevertheless, new vector commitments schemes with linear-size parameters are more expressive in terms of openings, have homomorphic properties, allow for ecient updates for the proofs and aggregation mechanisms.

Expressivity. VC were generalized by Libert et al. [21], who formalize the notion of functional commitments (FC). They construct vector commitments with openings to linear-forms of the vector based on the Die-Hellman exponent assumption over pairing groups. Later, Lai and Malavolta [20] introduce subvector openings and show applications to building succinct-arguments of knowledge (similar applications were shown by [4]) in the bilinear group setting. They also generalize the notion of SVCs to allow the prover to reveal arbitrary linear maps computed over the committed vector. Previously, only Functional VC for

9 E.g., the one used by ZCash. https://z.cash or and Filecoin [11]

single-output linear functions were proposed which did not account for provers that want to reveal multiple locations or function outputs of the committed vector in a concise way.

Updatability. Vector commitments that allow for updates are useful in applications such as stateless cryptocurrencies. A weak variant of updatability requires the algorithms that update the commitment and the opening to take as input an opening for the position in which the vector update occurs called hints. Recent RSA-based constructions are hint-updatable [4, 6]. Compared to hint updates, key-updates only need xed update keys corresponding to the updated positions. Schemes based on bilinear groups require such xed keys, and no extra information about the change made in the vector in order to update.

Aggregation. Vector Commitments with an additional aggregation property are very appealing for blockchain applications for their even shorter proofs of opening. Campanelli et al. [6] showed two constructions of incrementally aggregatable SVCs, that have constant-size parameters and work over groups of unknown order. Unfortunately, the practical eciency of these constructions is still not suecient for their deployment in real-world systems.

Gorbunov et al. [15] show how to extend the VC scheme of [22] to allow for cross-commitment aggregation. Like our constructions, they assume the Algebraic Group Model (AGM) [14] in bilinear groups and a random oracle. Their nal SVC requires public parameters whose size is linear in the size of the committed vector, while cross-commitment aggregation allow for splitting up a long vector into shorter ones and simply aggregate the proofs. However, this approach allows only for one-hop aggregation, meaning that already aggregated proofs cannot be reused in further aggregations by external nodes.

Tomescu et al.[29] showed how to realize an updatable SVC with one-hop aggregation from bilinear groups. Their scheme has linear-sized public parameters, and it supports commitment updates, proof updates from a static linear-sized update key tied only to the updated position, in contrast with the dynamic update hints required by related works.

Maintainability. Apart from Merkle tree based Vector Commitments which are known to be maintainable, Srinivasan et. al. [28] show that the multilinear PST polynomial commitment [25] can be turned to a maintainable VC construction. Pre-computing all (single-position) opening proofs is done in quasilinear time (contrary to the trivial quadratic time) and updating all proofs after a (single position) vector update needs only logarithmic time. Contrary to Merkle tree based approaches, the scheme has homomorphic properties. Furthermore, due to its algebraic structure, it supports one-hop aggregation through generic means, namely, Inner Pairing Product Arguments [5], albeit with a concretely expensive proving computation.

2 Preliminaries

We denote the set of natural numbers by N and let 2 N be the computational security parameter. We denote the list of integer numbers between 1 and n as [n]. All the algorithms dened throughout this work are assumed to be probabilistic Turing machines that run in polynomial time (abbreviated as PPT). We say c that a function is negligible (in), and we denote it by negl(), if negl() = () for any xed constant c > 1.

$$ \lambda\in\mathbb{N} $$

$$ {\mathsf{n e g l}}(\lambda)=\varOmega(\lambda^{-c}) $$

$$ c>1 $$

m m Vectors. For m-dimensional vectors a 2 F, we denote the i-th entry by a_i2 F. We use e_i2 F to denote the vectors of the canonical basis, more concretely e_iis the vector with a 1 in the i-th coordinate and 0’s m n m n elsewhere. For vectors a 2 F*;* b 2 F, we deⁿote a b 2 F = (a₁b*;:::;a*_nb) the tensor product of the vectors.

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ a_{i}\in\mathbb{F} $$

$$ \mathbf{e}_{i}\in\mathbb{F}^{m} $$

$$ {\bf e}_{i} $$

$$ \mathbf{a}\in\mathbb{F}^{m},\mathbf{b}\in\mathbb{F}^{n} $$

$$ \ {mathsf a\otimes\mathsf b\in\mathbb{F}^{m\cdot n}=\left(a_{1}\ \mathsf{b},\ldots,a_{n}\ \mathsf{b}\right)} $$

Lagrange basis. Let H = fh₁*;:::;*h_mg be a multiplicative group of size m in F. We consider the set of m Lagrange interpolation polynomials f_j(X)g_j=1associated with H, namely, Y

$$ \mathbb{H},=,{\mathsf{h}{1},\ldots,\mathsf{h}{m}} $$

$$ {\lambda_{j}(X)}_{j=1}^{m} $$

$$ \mathbb{H} $$

$$ \lambda_{j}(X)=\prod_{i\neq j}\frac{X-\mathsf{h}{i}}{\mathsf{h}{j}-\mathsf{h}_{i}}. $$

PmQm Recall thatj=1 j(X) = 1. Moreover, we dene t(X) =j=1(X hj) the vanishing polynomial. We will Q also consider tk(X) = (X hj), the vanishing polynomial of a subset fhjgj2JH and tk_c (X) = Qj2Jk k j=2J(X h_j). kQ

$$ \textstyle{\sum_{i=1}^{m}\lambda_{j}(X)=1} $$

$$ \textstyle{t\bigl(X\bigr)=\prod_{i=1}^{m}\bigl(X-\mathsf{h}_{j}\bigr)} $$

$$ \textstyle\check{t_{k}(X)}=\prod_{j\in J_{k}}\bigl(X-\mathsf{h}_{j}\bigr) $$

$$ {\mathsf{h}{j}}{j\in J_{k}}\subset\mathbb{H} $$

$$ t_{k^{c}}(X)= $$

$$ \textstyle\prod_{j\notin J_{k}}(X-\mathsf{h}_{j}, $$

For the multivariate case, recall that (X ;:::;X₁) =_{j=1 j}(X^j). Using these, we can write the vector of multivariate Lagrange as the tensor product (X) (X₁), where (X) is the univariate Lagrange basis.

$$ \lambda_{\sigma}(X_{\nu},\ldots,X_{1})=\prod_{i=1}^{\nu}\lambda_{\sigma_{i}}(X_{j}) $$

$$ \lambda(X_{\nu})\mathbin{\otimes}\cdots\mathbin{\otimes}\lambda(X_{1}) $$

Bilinear Groups. A bilinear group is given by a description gk = (p; G₁*;G₂;* G_T;e) with additive notation such that p is prime, so F = F_pis a eld. G₁*;G₂ are cyclic (additive) groups of prime order p. We use the notation [a]₁;* [b]₂; [c]_tfor elements in G₁*;G₂ and G_Trespectively. e : G₁ G₂!* G_Tis a bilinear asymmetric map (pairing), which means that 8a;b 2 Z_p; e([a]₁; [b]₂) := [ab]_t: We implicitly have that [1]_t:= e([1]₁;[1]₂) generates G_T. We use [a]_1;2to refer to 2 group elements [a]₁2 G₁*;* [a]22 G₂. In our constructions, we denote by G(p) the algorithm that, given as input the prime value p, outputs a description gk = (p; G₁*;G₂;* G_T;e).

$$ {\mathfrak{g k}}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T},e) $$

$$ \mathbb{F}=\mathbb{F}_{p} $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ [a]{1},[b]{2},[c]_{l} $$

$$ \mathbb{G}_{T} $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ e:\mathbb{G}{1}\times\mathbb{G}{2}\to\mathbb{G}_{T} $$

$$ \forall a,b\in\mathbb{Z}{p},,e([a]{1},[b]{2}):=[a b]{i} $$

$$ [1]{t}:=e([1]{1},[1]_{2}) $$

$$ \mathbb{G}_{T} $$

$$ [a]{1}\in\mathbb{G}{1},[a]{2}\in\mathbb{G}{2} $$

$$ [a]_{1,2} $$

$$ \ \mathfrak{g}\ \ {\sf k}=\left(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T},e\right) $$

$$ p, $$

$$ \mathcal{G}(p) $$

Algebraic Group Model (AGM). The algebraic group model [14] lies between the standard model and the stronger generic group model. In AGM, we consider only so-called algebraic adversaries. Such adversaries have direct access to group elements and, in particular, can use their bit representation, like in the standard model. However, these adversaries are assumed to output new group elements only by applying the group operation to received group elements (like in the generic group model). This requirement is formalized as follows: Suppose an adversary A is given some group elements [x₁]1*:::[xm]12* G₁. Then, for every new group Pm element [z]₁2 G₁ that the adversary outputs, it must also output z₁ :::z_m2 F such that [z]₁=_i=1[z_ix_i]₁.

$$ [x_{1}]{1}\dots[x{m}]{1}\in\mathbb{G}{1} $$

$$ [z]{1}=\textstyle\sum{i=1}^{m}[\tilde{z_{i}}x_{i}]_{1} $$

$$ [z]{1}\in\mathbb{G}{1} $$

$$ z_{1}\ldots z_{m}\in\mathbb{F} $$

Bilinear Strong Die Hellman Assumption. In the tree-based construction we rely on a q-type assumption, the Bilinear Strong Die Hellman assumption ((q₁;q₂)-BSDH) [3]. When q₁ = q₂, we simply call it q-BSDH Assumption. We present it next.

$$ ((q_{1},q_{2})\mathsf{-B S D H}) $$

$$ q_{1}=q_{2} $$

Denition 1. The (q₁;q₂)*-*BSDH assumption holds relative to G(1) if for all PPT adversaries A, the fol- lowing probability is negligible in. h i

$$ (q_{1},q_{2})\ {sf-B B D H} $$

$$ {\mathcal A}, $$

$$ \mathcal{G}(1^{\lambda}) $$

$$ \operatorname{P r}[(c,\textstyle{\frac{1}{(\tau-c)}}e([1]{1},[1]{2}))\leftarrow\mathcal{A}(\mathsf{g k},{[\tau^{i}]{1}}{i=0}^{q_{1}},{[\tau^{i}]{2}}{i=0}^{q_{2}})|\mathsf{g k}\leftarrow\mathcal{G}(1^{\lambda});:\tau\leftarrow\mathbb{F}_{p}]. $$

3 Denitions: Linear-map Vector Commitments

In the following, we dene what we call Linear-map Vector Commitments (LVC) schemes. Notably, this denition has been introduced by Lai and Malavolta in [20] (except that there the name is Linear Map Com- mitments) to capture further functionalities of vector commitments, whose denition before only account for proofs of position openings (Vector Commitments) or more generally subvector openings (Sub-vector commitments) (See Appendix A for the formal denitions). We introduce the denition and security properties of LVC. Importantly, we do not consider the hiding property as for our applications all vectors are public.

Linear-map Vector Commitment A linear-map vector commitment scheme for function families F m n ff : M!M g is a tuple of PPT algorithms LVC*:* KeyGen*;LVC:* Commit*;LVC:* Open*;LVC;*Vf that work as follows:

$$ \left{f:\mathcal{M}^{m}\to\mathcal{M}^{n}\right} $$

$$ \mathcal{F}\subset $$

LVC*:* KeyGen(1*; F*)! (prk*;vrk): The setup algorithm takes the security parameter, a family of functions F implicitly dening the message space M, and the maximum vector length m = poly(), and outputs a pair of keys (prk;*vrk).

$$ \lambda, $$

$$ m=\ \mathsf{p o l y}(\lambda) $$

$$ {\mathcal M}. $$

m LVC*:* Commit(prk*;v)!* (C*;*aux): On input the proving key prk, and a vector v = (v₁;v₂ :::;v_m) 2 M, returns a commitment C and auxiliary information aux. This algorithm is deterministic.

$$ (\mathsf{p r k},\mathbf{v})\to(\mathsf{C}, $$

$$ \mathtt{v}=\left(v_{1},v_{2}\ldots,v_{m}\right),\in,\mathcal{M}^{m} $$

LVC*:* Open(prk*;aux;f;* y)!_f:Takes as input prk, the auxiliary information aux, a function f 2F, and a n claimed result y 2M. It outputs a proof_fthat f(v) = y.

$$ \ C.\angle D e n(\mathsf{p r k},\mathsf{a U X},f\mathsf y)\to\pi_{f} $$

$$ f\in{\mathcal{F}} $$

$$ \mathbf{y}\in{\mathcal{M}}^{n} $$

$$ \pi_{f} $$

$$ f(\mathbf{v})=\mathbf{y} $$ n LVC*:* Vf(vrk*;* C*;f;y;_f)!* 0*=*1 :Takes as input the verication key vrk, C, function f, y 2M, aⁿd proof f. It accepts or rejects.

$$ \ \ \ {\mathsf{V}}(\mathsf{v r k},\mathsf{C},f,\mathsf{y},\pi_{f})\to0/1 $$

$$ f,,\mathbf{y}\in\mathcal{M}^{n} $$

$$ \pi f $$

A LVC scheme must satisfy the following properties:

Denition 2(LVC correctness). An LVC scheme is perfectly correct if for all 2 N*, for any family of* m n m functions Fff : M!M g and any v 2M,

$$ \mathbf{v}\in\mathcal{M}^{m} $$

$$ \mathcal{F}\subset{f:\mathcal{M}^{m}\to\mathcal{M}^{n}} $$

$$ \lambda\in\mathbb{N} $$

$$ \operatorname*{P r}\left[\mathsf{L V C.V f}(\mathsf{v r k},\mathsf{C},f,\mathbf{y},\pi_{f})=1\left|\begin{matrix}{(mathsf{p r k},\mathsf{v r k})\leftarrow\mathsf{L V C.K e y G e n}(1^{\lambda},\mathcal{F})}\ {(C,\mathsf{a r k})\leftarrow\mathsf{L V C.C o m m i t}(\mathsf{p r k},\mathbf{v})}\ {\pi_{f}\leftarrow\mathsf{L V C.O p e n}(\mathsf{p r k},\mathsf{a u u},f,\mathbf{y})}\ \end{matrix}\right.\right]=1. $$

Denition 3(LVC (strong) function binding.). A linear map commitment LVC satises strong function binding if, for any PPT adversary A, for all 2 N*, for all integers K 2* poly(), and for any family of functions F, the following probability is negligible in :

$$ \lambda\in\mathbb{N} $$

$$ K\in{\mathsf{p o l y}}(\lambda) $$

$$ \operatorname*{P r}\left[\begin{matrix}{\forall k\in[K]:\ \mathsf{U V C}\ \mathsf{U f}(\mathsf{v r k},\mathsf{C},f_{k},\mathbf{y}{k},\pi{f_{k}})=1}&{\ ((\mathsf{p r t},\mathsf{v r k})\leftarrow\mathsf{U V C}\mathsf{K e y C e n}(1^{\lambda},\mathcal{F})}\ {\wedge\ \exists\ \mathsf\ v{\in\mathcal{M}^{m}}\ \mathrm{}{s.t.}\forall k\in[K]:\ f_{k}(\mathbf{v})=\mathbf{y}{k}}\ {\wedge\ \exists\ \mathsf{v\in\mathcal{M}^{m}}\ \mathrm{}{s.t.}\forall k\in[K]:\ f\ f{k}(\mathsf{v r t},\pi_{f_{k}})\leftarrow\mathcal{A}(\mathsf{v r k},\mathsf{v r k})}\ \end{matrix}\right]\leftarrow\mathcal{A}(\mathsf{p r k},\mathsf{v r k})\notag $$

The denition above can be relaxed to hold only for honestly-generated commitments C, raising to the weak function binding notion. In the weak denition, the adversary A returns a vector v while the commitment C is computed via LVC*:* Commit. In this work, constructions are proven strong function binding.

3.1 Homomorphic Properties for LVC

Homomorphic Commitments. Linear-map vector commitment schemes that satisfy homomorphic commitments allow to combine commitments of two vectors into a single one of their sum (or any linear combination). Namely, for all, and (vrk*;prk) LVC:* KeyGen(1*; F*), if (C₁*;aux₁) LVC:* Commit(prk*;v₁) and (C₂;aux₂) LVC:* Commit(prk*;*v₂), then C~ = ( C₁ + C₂) is a valid commitment to v~ = ( v₁ + v₂) for any ; 2M.

$$ \lambda, $$

$$ \lambda , \text {a n d} (\mathrm {v r k}, \mathrm {p r k}) \leftarrow \mathrm {L V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {F}\right), \text {i f} \left(\mathrm {C} _ {1}, \mathrm {a u x} _ {1}\right) \leftarrow \mathrm {L V C}. \mathrm {C o m m i t} (\mathrm {p r k}, \mathbf {v} _ {1}) $$

$$ ({C_{2},\ 2u u_{2}}) $$

$$ \check{\mathsf{C}}=\left(\alpha\mathsf{C}{1}+\beta\mathsf{C}{2}\right) $$

$$ \tilde{\mathbf{v}}=\left(\alpha\mathbf{v}{1}+\beta\mathbf{v}{2}\right) $$

$$ \alpha,\beta\in{\mathcal{M}} $$

In this work, we are particularly interested in LVC that also have homomorphic proofs for dierent functions applied to a committed vector and homomorphic openings for the same function applied to dierent initial vectors.

Homomorphic Proofs. An LVC scheme has homomorphic proofs if it allows recombine two proofs₁,₂ corresponding to linear maps f₁, f₂ into a new proof ~ that opens to a linear combination of f₁ and f₂ m n m applied to the same committed vector. Namely, for all, F f f : M!M g aⁿd all vectors v 2M, and (vrk*;prk) LVC:* KeyGen(1*; F*), (C*;aux) LVC:* Commit(prk*;v), if₁LVC:* Open(prk*;aux;f₁;y₁) and 2LVC:* Open(prk*;aux;f₂;y₂), then for all; 2M*: ~ = ( +) veries LVC: Vf(vrk; C; f~ = (f₁ + f₂); y~ = ( y₁ + y₂); ~ = 1:

$$ \pi_{1} $$

$$ f_{1},\ f_{2} $$

$$ f_{1} $$

$$ f_{2} $$

$$ \lambda,\mathcal{F}\subset{f:\mathcal{M}^{m}\to\mathcal{M}^{n}} $$

$$ \mathbf{v}\in\mathcal{M}^{m} $$

$$ (N1,,,,,1)-\angle1C.\angle(3,\angle)\
$$

$$ \pi_{1}\gets\mathsf N C.\mathsf p e n(\mathsf p k,\mathsf u v,\mathsf u_{1},\mathsf y_{1}) $$

$$ \pi_{2}\leftarrow L C C.O p e n(p k,k)times x_{2},y_{2}, $$

$$ \alpha,\beta\in{\mathcal{M}} $$

$$ \tilde{\pi}=(\alpha\pi_{1}+\beta\pi_{2})\mathrm{}{v e r i f i e s}\mathsf{I V C.V f}(\mathsf{v r k}\mathsf{{k}}}{,\bar{f}}=(\alpha f_{1}+\beta f_{2}),\tilde{\mathbf{y}}=(\alpha\mathbf{y}{1}+\beta\mathbf{y}{2}),\tilde{\pi})=1. $$

Homomorphic Openings. An LVC scheme has homomorphic openings if we can combine opening proofs for the same linear-map f applied to two dierent vectors v₁ and v₂ to obtain a new proof of opening ~ that veries with respect to the linear combination C~ of the two initial commitments C₁*;*C₂ and show the result of f applied to the linear combination of the vectors v₁ and v₂.

$$ \mathbf{v}{}_{2} $$

$$ \tilde{C} $$

$$ \mathbf{v}{_1} $$

$$ \tilde{\pi} $$

$$ \mathsf{C}{1},\mathsf{C}{2} $$

$$ \mathbf{v}_{1} $$

$$ \mathbf{v}_{2} $$

m n m More formally, for all, Fff : M!M g, vectors v₁*;v₂ 2M, and (vrk;prk) LVC:* KeyGen(1*; F*), if₁LVC*:* Open(prk*;aux₁;f;* y₁) and₂LVC*:* Open(prk*;aux₂;f;* y₂), where (C₁*;aux₂) LVC:* Commit(prk*;v₁) and (C₂;aux₂) LVC:* Commit(prk*;v₂), then for all; 2M*:

$$ \lambda,\mathcal{F}\subset\left{f:\mathcal{M}^{m}\to\mathcal{M}^{n}\right} $$

$$ \mathbf{v}{1},\mathbf{v}{2}\in\mathcal{M}^{m} $$

$$ (N1k,D r k)-\ N C.\sin(1)^{\lambda},F) $$

$$ \pi_{1}\leftarrow\angle N C.0up p e n(p r k,a lup x_{1},f,y_{1}) $$

$$ \pi_{2}\leftarrow L C C.O p e n(D m,2timestimes_,2,f,y_{2}) $$

$$ (C_{1},\ \ u u_{2})\leftarrow C.C\ m\min\pm(\ \ u_{1},v_{1}) $$

$$ \left(\mathrm {C} _ {2}, \operatorname {a u x} _ {2}\right) \leftarrow \mathrm {L V C}. \operatorname {C o m m i t} (\mathrm {p r k}, \mathbf {v} _ {2}) $$

$$ \alpha,\beta\in{\mathcal{M}}: $$

$$ \tilde{\pi}=(\alpha\pi_{1}+\beta\pi_{2})\mathrm{}{v e r i f i e s}\mathsf{L V C}.\mathsf{V f}(\mathsf{v r k},\bar{\mathsf{C}}=(\alpha\mathsf{C}{1}+\beta\mathsf{C}{2}),f,\tilde{\mathbf{y}}=(\alpha\mathsf{y}{1}+\beta\mathsf{y}{2}),\bar{\pi})=1. $$

4 Generic Constructions from Homomorphic Proofs

Many natural schemes (such as [29, 15], PST commitments or our constructions in Section 5) have homomorphic proofs or openings. This motivates us to consider generic constructions that enhance any LVC scheme with homomorphic properties. We start by dening the notions of unbounded aggregation for same and cross-commitments and then we show how to add such properties to LVC schemes that have homomorphic proofs for the former and, additionally, homomorphic commitments for the latter.

4.1 New Notion: Unbounded Aggregation

The intuition for our denition is that, given t proofs, commitments or openings, we can aggregate them by performing a linear combination with random coecients. Importantly, these coecients have to be chosen after the claims are xed and for that we rely on the RO model, as it is often the case for aggregation in the literature.

In our work, we go a step further and show how this procedure can be done over already aggregated proofs. Actually, aggregating already aggregated proofs consist on just sampling new coecients and using them for fresh linear combinations. Importantly, the verier needs to have access to the aggregation history: it has to recompute the coecient corresponding to each initial proof, which is the product of all the coecients used in the aggregations it was involved in. Note that this also adds a small overhead to the verier: it makes a linear (in the number of aggregation \hops") number of hash computations.

Example for same-commitment aggregation: Consider vector v committed in C, functions f₁;f₂ and f₃; let 1*;2and3be proofs that f₁(v) = y₁, f₂(v) = y₂ and f₃(v) = y₃. An aggregated proof for f₂(v) = y₂, f₃(v) = y₃, would be₁=₂+_{1 3}, for₁= H(C; f*(f₂;y₂); (f₃;y₃)g). In a second step, we can aggregate a proof that f₁(v) = y₁, by performing₂=₁+_{2 1}, for₂= H(C; (f₁;y₁);₁). At the verication step, the verier would reconstruct the coecients of each initial proof in₂. For instance,₁= 1,₂=_{1 2},₃=₂. Then, the verier can run the LVC*:* Vf algorithm to check whether₂=₁+_{2 1}=₁+_{1 2 2}+_{2 3} is a valid proof that function f = f₁ +_{1 2}f₂ +₂f₃ evaluated at the vector committed in C opens to y = y₁ +_{1 2}y₂ +₂y₃. For this last step to work we need the homomorphic proof property and the verier to have access to the aggregation \history".

$$ C, $$

$$ f_{1},f_{2} $$

$$ \pi_{1},\pi_{2} $$

$$ \pi_{3} $$

$$ f_{1}(\mathbf{v})=\mathbf{y}{1},,f{2}(\mathbf{v})=\mathbf{y}_{2} $$

$$ f: $$

$$ f_{3}(\mathbf{v})=\mathbf{y}_{3} $$

$$ f_{3}(\mathbf{v})=\mathbf{y}_{3} $$

$$ \pi_{1}^{*}=\pi_{2}+\gamma_{1}\pi_{3} $$

$$ f_{2}(\mathbf{v})=\mathbf{y}_{2} $$

$$ \gamma_{1}=\mathsf{H}(\mathsf{C},{(f_{2},\mathtt{y}{2}),(f{3},\mathtt{y}_{3})}) $$

$$ f_{1}(\mathbf{v})=\mathbf{y}_{1} $$

$$ \pi_{2}^{}=\pi_{1}+\gamma_{2}\pi_{1}^{} $$

$$ \gamma_{2}=\mathsf{H}(\mathsf{C},(f_{1},_{\ } $$

$$ \delta_{1}=1,\delta_{2}=\gamma_{1}\gamma_{2},\delta_{3}=\gamma_{2} $$

$$ \pi_{2}^{*} $$

$$ \pi_{2}^{},=,\pi_{1}+\gamma_{2}\pi_{1}^{},=,\pi_{1}+\gamma_{1}\gamma_{2}\pi_{2}+\gamma_{2}\pi_{3} $$

$$ f=f_{1}+\gamma_{1}\gamma_{2}f_{2}+\gamma_{2}f_{3} $$

$$ y=y_{1}+\gamma_{1}\gamma_{2}y_{2}+\gamma_{2}y_{3} $$

tj To describe our history of claims we move to trees of statements ff^j; y^jg⁼¹. In these trees, leaves are pairs of function{output (f; y). As in the usual case internal nodes are dened as an ordered list of subtrees. An empty history/tree is referred to as null. We denote trees using the syntax T_f;yand the operation that \merges" two subtrees in order adding a new root as )". The following denition formalizes the above and will be useful in our construction. We remark that we include the commitment in each of the leaves of the trees T_f;y. This does not increase the input size for cross-commitment aggregation where this information is necessary (for same-commitment aggregation the commitment is not necessary). This also allows to model more closely the \claims" for the cross-commitment case where each proof is for a statement (C*;f;* y).

$$ {f_{j},\mathbf{y}{j}}{j=1}^{t} $$

$$ T_{f,\mathbf{y}} $$

$$ ^{66\cdot99}_{\cdot\cdot} $$

$$ T_{f,\mathbf{y}} $$

Denition 4. Given a tree T we associate to each of its internal nodes a hash label h dened so that h(L) R) := H(C;L;R). We then associate to each of the leaves in the tree a label Y

$$ h(L\colon R):={\mathsf{H}}(C,L,R) $$

$$ \delta(\mathsf{l e a f}):=\prod_{i=1,\ldots,t}h(x_{i})^{r(x_{i},\mathsf{l e a f})} $$

where the x_i-s are the internal nodes along the path from leaf to the root (root included and starting from the bottom), the predicate r(x; leaf) is 1 if leaf is a right child of x and 0 otherwise.

$$ x_{i}–s $$

Remark 1(Unbounded vs One-hop vs Incremental). Previous works have dened other types of aggregation. In one-hop aggregation (or batching) [4] aggregated proofs cannot be aggregated further. Incremental aggregation [6] does not have this limitation. The dierence between the latter and our notion is that incremental aggregation does not require to keep track of the order in which the aggregation has been applied

(for verication or further aggregation). On the other hand, we do require to track order, but we argue that this is not an overhead in many settings. In particular, even incremental aggregators and veriers need to know the claims related to the proofs being aggregated, albeit in no order. Adding a structure to the claims roughly adds a number of bits linear in the length of the opening for additional separators (see also examples on tree histories above).

When we consider unbounded-aggregatable LVC, we assume KeyGen outputs additional parameters for aggregations in pp. The aggregation algorithm will follow this syntax¹⁰:

$$ \mathsf{L V C.A g g}(\mathsf{p p},\mathtt{T}{f,\mathbf{y}},\pi,\mathtt{T}{f^{\prime},\mathbf{y}^{\prime}},\pi^{\prime})\to\pi^{*} $$

We subsequently modify the syntax for the verication algorithm in an (unbounded) aggregatable LVC as follows: 0 LVC*:* Vf(vrk*;* C*;T*) T;)! b 2f⁰; 1g

$$ \mathsf{L V C.V f}(\mathsf{v r k},\mathsf{C},T_{f,\mathbf{y}}\ \ \therefore T_{f,\mathbf{y}}^{\prime},\pi^{*})\ \to{}\ b\in{0,1} $$

with T_f;yreplacing f; y.

$$ T_{f,\mathbf{y}} $$

$$ f,\mathbf{y}. $$

We require the following correctness property and that function binding still holds.

0 Denition 5(Unbounded Aggregation Correctness). For any T_f;y;T_f0_;y0 and any, : 2 3

$$ T_{f,\mathbf{y}},T_{f^{\prime},\mathbf{y}^{\prime}} $$

$$ \pi,;\pi^{\prime}. $$

$$ \Pr \left[ \begin{array}{c c} (\mathrm {L V C}. \mathrm {V f} (\mathrm {v r k}, \mathrm {C}, T _ {f, \mathbf {y}}, \pi) = 1 \wedge \ \mathrm {L V C}. \mathrm {V f} (\mathrm {v r k}, \mathrm {C}, T _ {f, \mathbf {y}} ^ {\prime}, \pi^ {\prime}) = 1) \Rightarrow \ \mathrm {L V C}. \mathrm {V f} (\mathrm {v r k}, \mathrm {C}, T _ {f, \mathbf {y}} \therefore T _ {f, \mathbf {y}} ^ {\prime}, \pi^ {}) = 1 \end{array} \right] \left| \begin{array}{c} (\mathrm {p r k}, \mathrm {v r k}, \mathrm {p p}) \leftarrow \mathrm {L V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {F}\right) \ (\mathrm {C}, \mathrm {a u x}) \leftarrow \mathrm {L V C}. \mathrm {C o m m i t} (\mathrm {p r k}, \mathbf {v}) \ \pi^ {} \leftarrow \mathrm {L V C}. \mathrm {A g g} (\mathrm {p p}, T _ {f, \mathbf {y}}, \pi , T _ {f ^ {\prime}, \mathbf {y} ^ {\prime}}, \pi^ {\prime}) \end{array} \right] = 1 $$

Denition 6(Unbounded Aggregation Function Binding). For any T_f;y;T_f0_;y0 the following prob- ability is negligible in :

$$ T_{f,\mathbf{y}},T_{f^{\prime},\mathbf{y}^{\prime}} $$

$$ \operatorname*{P r}\left[\begin{matrix}{\mathsf{I V C}f(\mathsf{v r k},\mathsf{C},T_{f,\mathbf{y}}\cdot\cdot T_{f,\mathbf{y}}^{\prime},\pi^{})\mathrm{}{=}\mathtt{I}\left[\mathsf{p r k},\mathsf{v r k},\mathsf{p p}\right)\leftarrow\mathsf{L V C}\ \mathsf{K e y G e n}(1^{\lambda},\mathcal{F}),}\ {\wedge\mathrm{}{\ nexistsa.s.t.~}f(\mathbf{a})=\mathbf{y}\wedge f^{\prime}(\mathbf{a})=\mathbf{y}^{\prime}\left|\left(\mathsf{C},\pi^{},T_{f,\mathbf{y}},T_{f,\mathbf{y}}^{\prime}\right)\leftarrow\mathcal{A}(\mathsf{p p},\mathsf{p r k},\mathsf{v r k})\right|}\ \end{matrix}\right] $$

Denition: Cross-Commitment Aggregation. Unbounded aggregation can be performed across dierent commitments as well. This property is called Cross-commitment Aggregation and makes sense when we 0t have a set of commitments C⁰₁*;:::;*C that we want to open at one or more maps f, as it allows to compute a succinct proof of opening for linear-maps from dierent vectors committed separately. Below we show our syntax which directly expands on our same-commitment aggregation described above. Function binding and correctness are also straightforward to expand. We let T_f;yinclude our commitments in the leaves (see also next section).

$$ \mathsf{C}{1}^{\prime},\ldots,\mathsf{C}{t}^{\prime} $$

$$ f_{f} $$

$$ T_{f,\mathbf{y}} $$

Cross-commitment aggregation:

$$ \mathsf{L V C.C r o s s}\mathsf{A g g}(\mathsf{p p},{{T,\mathbf{y}}},\pi,\ \ {T}{{f^{\prime}},\mathbf{y}{'}},\pi^{\prime})\to\pi^{*} $$

Cross-commitment verication:

$$ \mathrm {L V C}. \operatorname {C r o s s} V f y (\mathrm {v r k}, \left(\mathrm {C} _ {j} ^ {\prime}\right) _ {j}, T _ {f, \mathbf {y}}, \pi^ {*}) \rightarrow 0 / 1 $$

4.2 Unbounded Aggregation for LVC

We now describe unbounded aggregation algorithms for any LVC scheme that satises the homomorphic properties of Section 3.1.

m LVC*:* KeyGen(1*; F*)! (prk*;vrk;pp; f*upk_jg_j=1): Additionally generate the description of a hash function H( ) and set it as pp.

$$ \mathsf{L V C}.\mathsf{K e y G e n}(1^{\lambda},\mathcal{F})\to(\mathsf{p r k},\mathsf{v r k},\mathsf{p p},{\mathsf{u p k}{j}}{i=1}^{m})! $$

$$ \mathsf{H}(\cdot) $$

¹⁰ The algorithms can be generalized for more proofs. Proof size remains the same, also for cross-commitment aggregation.

$$ \mathsf{A g g}(\mathsf{p p},T_{f,\mathrm{y}},\pi,T_{f^{\prime},\mathrm{y}^{\prime}},\pi^{\prime})\to\pi^{*} $$

0 LVC*:* Agg(pp*;T*_f;y;;T_f0_;y0;)! : Compute = H(C*;T*_f;y;T_f0_;y0) 0 Output = + LVC*:* Vf(vrk*;* C*;T*_f;y) T_f0_;y0;)! b Return b LVC*:* Vf vrk*;* C*;f;y ;* where: { let leaf₁*;:::;* leaf_‘be all the leaves in T_f;y) T_f0_;y0. { recall each leaf_iis of the form (C*;f*_i; y_i) { For each i let_i:= (leaf_i) be the value dened as in Denition 4.

$$ \gamma=\mathsf{H}(\mathsf{C},T_{f,\mathbf{y}},T_{f^{\prime},\mathbf{y}^{\prime}}) $$

$$ \pi^{*}=\pi+\gamma\pi $$

$$ \mathsf{C},T_{f,\mathbf{y}}\ :\ T T_{f^{\prime},\mathbf{y}^{\prime}},\pi^{*})\to b $$

$$ \mathsf{l e a f}{1},\ldots,\mathsf{l e a f}{\ell} $$

$$ T_{f,\mathbf{y}}\therefore T_{f^{\prime},\mathbf{y}^{\prime}}. $$

$$ \left(\mathsf{C},f_{i},\mathbf{y}_{i}\right) $$

$$ \delta_{i}:=\delta({mathsf l e a f}_{i}) $$

$$ f^{}:=\sum_{i}\delta_{i}f_{i}\qquad y^{}:=\sum_{i}\delta_{i}\mathbf{y}_{i} $$

Theorem 1. When applied to a function binding LVC scheme with homomorphic proofs, LVC*:* Agg*;LVC:* Vf satises Unbounded Aggregation Correctness (as in Def. 5) and Function Binding (Def. 6) in the ROM.

Proof. Correctness follows by inspection, using the fact that the LVC satises homomorphic proof, so we omit it.

For function binding, let C*; ;Tf;y;Tf⁰;y⁰ be an output of A such that LVC:* Vf(vrk*;* C*;Tf;y) Tf⁰;^y0;)=1. P P B^y construction this implies IP:* Vf vrk*;* C*;i ifi;i iyi;* = 1. Because IPPis function binding, except P with negligible probability, there exists a vector a such that f(a) = y, for y =_{i i}y_i, f(X) =_{i i}f_i(X) P_tP_t then there exists a such that_if_i(a) =_iy_i. i=1 i=1

$$ \left(\mathsf{C},\pi^{*},T_{f,\mathbf{y}},T_{f^{\prime},\mathbf{y}^{\prime}}\right) $$

$$ \textstyle\mathsf{I P.V f}\left(\mathsf{v r k},\mathsf{C},\sum_{i}\delta_{i}f_{i},\sum_{i}\delta_{i}\mathbf{y}_{i},\pi^{*}\right):=:1 $$

$$ f(\mathbf{a})=\mathbf{y} $$

$$ \mathbf{y}=\sum_{i}\delta_{i}\mathbf{y}{i},,f(\mathbf{X})=\sum{i}\delta_{i}f_{i}(\mathbf{X}) $$

$$ \sum_{i=1}^{t}\delta_{i}f_{i}(\mathbf{a})=\sum_{i=1}^{t}\delta_{i}\mathbf{y}_{i} $$

Since H is a random oracle, the coecients_ido not depend on y_i;f_i. And by the Schwartz-Zippel lemma, except with probability *r=*F, f_i(a) = y_ifor all i, which concludes the proof. ut

$$ \delta_{i} $$

$$ \mathbf{y}{i},f{i} $$

$$ r/\mathbb{F},,f_{i}(\mathbf{a})=\mathbf{y}_{i} $$

$$ i, $$

Cross-Commitment Aggregation for LVC. For the case of cross-commitment aggregation, we proceed similarly but we also need to homomorphically operate on the commitments (recall that hashing on trees implicitly hashes the commitments too since we include them there).

0 LVC*:* CrossAgg(pp*;T*_f;y;;T_f0_;y0;)! : Compute = H(T;T)

$$ T_{f,\mathbf{y}},\pi,T_{f^{\prime},\mathbf{y}^{\prime}},\pi^{\prime}\ )\to\pi^{*} $$

$$ \gamma=\mathsf{H}(T_{f,\mathbf{y}},T_{f^{\prime},\mathbf{y}^{\prime}}) $$

$$ \pi^{*}=\pi+\gamma\pi^{\prime} $$

$$ \left(\mathsf{C},\mathsf{C}^{\prime},T_{f,\mathsf{y}}:,T_{f^{\prime},\mathsf{y}^{\prime}},\pi^{*}\right)\to b $$

f;y f;y { let leaf₁*;:::;* leaf_‘be all the leaves in T_f;y) T_f0_;y0. We add to each leaf leaf_iand additional subindex j that refers to which commitment the proof in leaf_ijcorresponds to. Note that we still consider ‘ leaves.

$$ \mathsf{l e a f}{1},\ldots,\mathsf{l e a f}{\ell} $$

$$ T_{f,\mathbf{y}}\therefore T_{f^{\prime},\mathbf{y}^{\prime}} $$

$$ \exists{\sf f_{i}} $$

$$ {\mathrm{|f a f}}_{i j} $$

{ each leaf_ijis of the form (C_j;f_i; y_i)

$$ \ {mathsf i f}_{i j} $$

$$ (C_{j},f_{i},\mathbf{y}_{i}) $$

{ For each i let_ij:= (leaf_ij) be the value dened as in Denition 4.

$$ \delta_{i j}:=\delta(\mathsf{l e a f}_{i j}) $$

{ Compute

$$ f_{j}^{}:=\sum_{i}\delta_{i j}f_{i}\qquad y_{j}^{}:=\sum_{i}\delta_{i j}\mathbf{y}i $$

{ Return 1 i b_j= 1 for all b_jLVC*:* Vf vrk*;* C_j;f_j;y_j;.

$$ b_{j}\gets\mathsf{L V C.V f}(\mathsf{v r k},\mathsf{C}{j},f{j}^{},y_{j}^{},\pi^{*}) $$

$$ b_{j}=1 $$

Eciency. For our constructions, the verication equations for computing b_i= IP*:* Vf vrk*;* C*;f;y ;* are two pairing equations where the elements in the right side can be aggregated, and thus the verier performs only ‘ + 1 pairings.

$$ b_{i}=\mathsf{I}\mathsf{P}.\mathsf{V}\mathsf{f}\big(\mathsf{v r k},\mathsf{C}^{},f^{},y^{},\pi^{}\big) $$

Security. The security of this augmented construction follows analogously to that for same-commitment aggregation, with the additional requirement for the LVC scheme to have homomorphic commitments and openings.

4.3 From Inner-Products to Arbitrary Linear-Maps

$$ \mathcal{F}\subset\left{f:\mathbb{F}^{m}\to\mathbb{F}^{n}\right} $$

m n In this section we show we can obtain LVC schemes for any family of functions Fff : F*!* F g starting from simpler constructions that have homomorphic proofs and openings.

$$ \mathcal{F}_{\mathsf{I P}}={f:\mathbb{F}^{m}\to\mathbb{F}} $$

m Our starting point are LVC schemes for F_IP= ff : F*!* Fg, or inner-product VC schemes, that we will denote as IP = (IP*:* KeyGen*;IP:* Commit*;IP:* Open*;IP:* Vf). All this algorithms work as the ones for LVC, except m that instead of f 2F_IPm;p, they use the vector f 2 F_pso that f(v) = f v.

$$ \mathsf{I P}=\bar{\mathsf{I P P}K e y G e n} $$

$$ f(\mathbf{v})=\mathbf{f}\cdot\mathbf{v}. $$

$$ f\in\mathcal{F}{\mathsf{I P}{m,p}}. $$

$$ \mathbf{f}\in\mathbb{F}_{p}^{m} $$

m n We can write the linear-^map f : F*!* F as f = (f₁;f₂;:::f_n), where each f_iis an inner product function. If the IP scheme has homomorphic proofs, and we set_ito be the proof that f_i(v) = f_iv = y_i, n an aggregation of fⁱg_i⁼¹is a proof of the statement f(v) = y. Later, in the following section, we show two possible constructions of IP vector commitments schemes that can be used to instantiate the framework in this section.

$$ f,:,\mathbb{F}^{m},\rightarrow,\mathbb{F}^{n} $$

$$ \ {pm\ f=\ (f_{1},f_{2},\dots f_{n})} $$

$$ f_{i} $$

$$ \pi_{i} $$

$$ f_{i}(\mathbf{v})=\mathbf{f}{i}\cdot\mathbf{v}=y{i} $$

$$ f(\mathbf{v})=\mathbf{y} $$

$$ {\pi_{i}}_{i=1}^{n} $$

An IP aggregation algorithm for one-hop aggregation¹¹ of proofs works as follows: n n 0 IP*:* Agg(pp*; ff;y g;* = ())! :

$$ \mathsf{I P.A g g}(\mathsf{p p},{\mathbf{f}{i},y{i}}{i=1}^{n},\pi=(\pi{i})_{i=1}^{n})\to\pi^{\prime} $$

i i i=1 i i=1 n Parse pp = HP, where H is a hash function, compute = H(C*; ff_i;y*_ig_i=1)

$$ {\mathfrak{p p}}={\mathsf{H}} $$

$$ \gamma=\mathsf{H}(\mathsf{C},{\mathbf{f}{i},y{i}}_{i=1}^{n}) $$

0 n i 1 Output =^{i=1 i}

$$ \pi^{\prime}=\sum_{i=1}^{n}\gamma^{i-1}\pi_{i} $$

$$ \mathsf{C},{\mathsf{f}{i},y{i}}_{i-1}^{n},\pi^{\prime})\to b $$

n 0 IP*:* VfAgg(vrk*;* C*; ffⁱ;y*ⁱgⁱ⁼¹;)! b : n Compute = H(C*; ff;y g*);

$$ \mathrm {r t e} \gamma = \mathrm {H} (\mathrm {C}, \left{\mathbf {f} _ {i}, y _ {i} \right} _ {i=1} ^ {n}), \quad \mathbf {f} ^ {\prime} = \sum_ {i=1} ^ {n} \gamma^ {i-1} \mathbf {f} _ {i}, \quad y ^ {\prime} = \sum_ {i=1} ^ {n} \gamma^ {i-1} y _ {i} $$

i i i=1 0 Output b IP*:* Vf(vrk*;* C*;f⁰;y⁰;):*

$$ b\gets\mathsf{P P.V f(v r k,C,f^{\prime},y^{\prime},\pi^{\prime})}. $$

Using IP*:* Agg, we present an alternative way of computing concise proofs of LVC for more general functions ^m n f : F*!* F, based on aggregation. LVC: KeyGen(1; F)! (prk;vrk;pp):

$$ f:\mathbb{F}^{m}\to\mathbb{F}^{n} $$

$$ \cdot\mathbf{\dot{\ \ \ {}u R R\ }}(\mathsf{p r k},\dot{\mathsf{v r v}})\xleftarrow{\ \ }{\sf P.K.y G y n n}(\mathbf{1^{\lambda}},\mathcal{F}_{\mathsf{I P}}) $$

IP 2.Generate aggregation parameters pp = H (a hash function).

3.Output (prk*;vrk;*pp).

$$ \operatorname{u t p u t};(\mathsf{p r k},\mathsf{v r k},\mathsf{p p}) $$

LVC*:* Commit(prk*;v)!* (C*;aux) : 1.Run (C;aux) IP:* Commit(prk

$$ \ {mathsf i t t}p\ \ \mathsf{r k},\mathsf{v})\to\ \ \bigl({\mathsf{,,a u x}}\bigr) $$

$$ \sin(\mathsf{C},\mathsf{a}U)\leftarrow\vert mathsf P cdot mathsf\ C o m m\pm(p\mathsf k,\mathsf{V}) $$

2.Output (C*;*aux)

$$ (\mathsf{C},\mathsf{a u x}) $$

LVC*:* Open(prk*;pp;aux;f;* y)! :

$$ \mathsf{I1}k\ \mathsf{I1k},\mathsf{p p},\mathsf{a u x},f,\mathtt{y})\to\pi $$

1.Parse f = (f₁;f₂;:::f_n) and y = (y₁;:::y_n). Consider f_ias the vector representing inner-product function f_i.

$$ \ \ f\ (\ f_{1},f_{2},\ldots f_{n}) $$

$$ \mathbf{y}=(y_{1},\ldots y_{n}) $$

$$ \mathbf{f}_{i} $$

2.RunⁱIP*:* Open(prk*;aux;* f_i;yⁱ) for i 2 [n]

$$ \pi_{i}\gets\mathsf{P.P D e n}p k\ \mathsf{p r k,{x}}\ \mathsf{f{}}{i},y{i} $$

$$ i\in[n] $$

n 3.Output IP*:* Agg(pp*; f*ⁱg_i=1)

LVC*:* VfAgg(vrk*;pp;* C*;f;y;)! b* :

$$ \pi\gets|\mathsf{P}.\mathsf{A g g}(\mathsf{p p},{\pi_{i}}_{i=1}^{n}) $$

$$ (mathsf v H,\mathsf{p p},\mathsf{\hat{C}},\mathsf{\hat{C}},\mathsf{\hat{f}},\mathsf{y},\pi{})\to b: $$

$$ f=(f_{1},f_{2},\ldots f_{n}) $$

$$ \mathbf {y} = \left(y _ {1}, \dots y _ {n}\right) $$

$$ \mathbf{f}_{i} $$

$$ f_{i}. $$

n 2.Output b IP*:* VfAgg(vrk*;* C*; ff_i;y*_ig_i=1;)

$$ b\gets\mathsf{I P}.\mathsf{V A g g}(\mathsf{v r k},\mathsf{C},{\mathsf{f}{i},y{i}}_{i=1}^{n},\pi) $$

4.4 Updability for LVC

We consider updatability as an extra property of the LVC scheme. The KeyGen algorithm additionally computes the update keys, while two extra algorithms are dened as follows:

LVC*:* UpdCom(upk*;* C*;j;)!* C⁰: takes as input C, a position j 2 [m], update key upk, and a constant 2M. 12 It outputs C⁰ as a commitment for v⁰ = v + e^j.

$$ j\in[m] $$

$$ \mathsf{C},j,\delta)\to\mathsf{C}^{\prime}; $$

$$ \delta\in\mathcal{M} $$

$$ \mathbf{v}^{\prime}=\mathbf{v}+\delta\mathbf{e}_{j}{}^{12} $$

$$ C^{\prime} $$

0 LVC*:* UpdOpen(upk*;j;;f;y;)!* :Takes as input upk, j,, a function f, a valid opening pair (y*;*) for 0 f and outputs a proof for the new opening y⁰ = f(v + e_j).

$$ \mathsf{L V C.U p d O p e n}(\mathsf{u p k},j,\delta,f,\mathbf{y},\pi)\to\pi^{\prime} $$

$$ f, $$

$$ j,,\delta, $$

$$ \mathbf{y}^{\prime}=f(\mathbf{v}+\delta\mathbf{e}_{j}) $$

$$ (\mathbf{y},\pi) $$

$$ \pi^{\prime} $$

$$ f $$

Update correctness. Let prk*;vrk;upk LVC:* KeyGen(1*; F*), and let (C*;j;f;y;) be a tuple such that LVC:* Vf(vrk*;* C*;f;y;*) = 1. Then LVC satises update correctness if for any 2M,

$$ (\mathsf{C},j,f,\mathbf{y},\pi) $$

$$ \ \ (\mathsf{p r k},\mathsf{v r k},\mathsf{u p k})\ \leftarrow\ \mathsf{L V C.K e y G e n}(\ ^{\lambda},\mathcal{F}) $$

$$ \ {sf L C.4}\ {\sf f}(\sf r k,\ \sf C f y\pi)=1 $$

$$ \delta\in\mathcal{M} $$

$$ \Pr \left[ \begin{array}{c c} \mathrm {L V C . V f} (\mathrm {v r k}, \mathrm {C} ^ {\prime}, f, \mathbf {y} ^ {\prime}, \pi^ {\prime}) = 1 \ \wedge \mathbf {y} ^ {\prime} = \mathbf {y} + \delta f (\mathbf {e} _ {j}) \end{array} \right| \begin{array}{c} \mathrm {C} ^ {\prime} \leftarrow \mathrm {L V C . U p d C o m} (\mathrm {u p k} _ {j}, \mathrm {C}, j, \delta) \ \pi^ {\prime} \leftarrow \mathrm {L V C . U p d O p e n} (\mathrm {u p k} _ {j}, j, \delta , f, \mathbf {y}, \pi) \end{array} ] = 1. $$

¹¹ Naturally, this can be seen as a particular case of unbounded aggregation.

¹² This notion can be generalized to more than one position.

Updates for IP. We present a generic construction of the updatability algorithms for inner-product schemes. We state that even though algorithms can be generalized to LVC for arbitrary functions, for ease of exposition we only present it for inner-product openings, rather than generic linear-maps.

It is easy to see that commitments can be updated when one value of the vector changes by simply applying the linear-homomorphic property of the underlying IP scheme. Given C such that (C*;aux) LVC:* Commit(prk*;v), when position t of the vector changes, i.e. v⁰ = v + e^twe can compute a commitment to the new vector v⁰ as C⁰ = (C + C^) where (C^;aux^ ) LVC:* Commi_t(prk*;* e) is given as an update key. t

$$ \mathbf{v}^{\prime}=\mathbf{v}+\delta\mathbf{e}_{t} $$

$$ \mathbf{v}^{\prime} $$

$$ \ \mathsf{C}^{\prime}=(\mathsf{C}+{\hat{\mathsf{C}}}) $$

$$ \ {\cdot}(\mathsf{p r k},\mathbf{e}_{t}) $$

$$ (\hat {C}, a \hat {u} x) \leftarrow L V C $$

Moreover, it is possible to update existing proofs using the homomorphic openings property of the IP scheme: when position t of the vector changes as above, to update a prior proof we simply add to a proof 0 ^ corresponding to the opening of f( e^t). The resulting = + ^ corresponds to the opening of the sum f(v⁰) = f(v) + f(e) wi_th respect to the updated commitment C⁰ =C+C^. t

$$ \hat{\pi} $$

$$ \pi^{\prime}=\pi+\hat{\pi} $$

$$ f(\delta\mathbf{e}_{t}) $$

$$ f(\mathbf{v}^{\prime})=f(\mathbf{v})+\delta f(\mathbf{e}_{t}) $$

$$ \mathsf{C}^{\prime}=\mathsf{C}+\hat{\mathsf{C}}. $$

$$ \mathsf{I P}K.\mathsf{K e y G e n}(\ {{\ 1}}^{\lambda},\mathcal{F}{\mathsf{I P}})\to(\mathsf{p r k},\mathsf{v r k},{\mathsf{u p k}{j}}_{j=1}^{m}): $$

We extend IP arguments to satisfy updatability by asking the IP*:* KeyGen algorithm to additionally generate updatable keys and introduce IP*:* UpdCom and IP*:* UpdOpen that work the following way; m IP*:* KeyGen(1*; F*_IP)! (prk*;vrk; fupk_jg_j=1): 1.Additionally generate public update keys upk: 2.Set^uijIP:* Open(prk*;aux^j;* eⁱ;u^ij= e_ie_j); 8i;j 2 [m] m 3.Dene upk^j= f_uijg_i=1for all j 2 [m] m 4.Output (prk*;vrk; fupk_ig_i=1). IP:* UpdCom(prk*;* C*;t;)!* C⁰ : 1.Set C^ IP*:* Commit(prk*;* e). _t 2.Output C⁰ =C+ C^. 0 IP*:* UpdOpen(upk_t;t;;C; f*;y;)!* : m 1.Parse upkt= fuitgi=1 P^m 2.Compute ^ =ⁱ₌₁f^{i uit} ₀ 3.Set = + ^ as proof for y⁰ = y + f e_t 0 4.Output.

$$ \pi_{u_{i j}}\leftarrow\mathsf{I P.O p e n}(\mathsf{p r k},\mathsf{a u x}{j},\mathbf{e}{i},u_{i j}=\mathbf{e}{i}\cdot\mathbf{e}{j}),\ \forall i,j\in[m] $$

$$ \mathsf{I p k}{j}={\pi{u_{i j}}}_{i=1}^{m} $$

$$ j\in[m] $$

$$ \mathsf{I}(\mathsf{p r k},\mathsf{C},t,\delta)\to\mathsf{C}^{\prime} $$

$$ \hat{\mathsf{C}}\leftarrow\mathsf{I P.C o m m i t(r k k,e_{t})}. $$

$$ \mathsf{C}^{\prime}=\mathsf{C}+\delta\hat{\mathsf{C}}. $$

$$ \mathsf{I P.U p d O p e n}(\mathsf{u p k}_{t},t,\delta,\mathsf{C},\mathbf{f},y,\pi)\to\pi^{\prime}: $$

$$ \mathsf{u p k}{t}={\pi{u_{i t}}}_{i=1}^{m} $$

$$ \hat{\pi}=\sum_{i=1}^{m}f_{i}\pi_{u_{i t}} $$

$$ \pi^{\prime}=\pi+\delta\hat{\pi} $$

$$ y^{\prime}=y+\mathbf{f}\cdot\delta\mathbf{e}_{t} $$

$$ \pi^{\prime} $$

Theorem 2. If IP satises function binding and has homomorphic commitments and openings, the extension above satises update correctness.

Proof. The proof follows directly by the denition of homomorphic proof and IP*:* UpdCom*;IP:* UpdOpen.

5 Constructions for Inner-Pairing VC

In this section, we present two constructions of LVC for inner products, that is, for functions f F_IP= ^m ff : F*!* Fg. We denote as IP = (IP*:* KeyGen*;IP:* Commit*;IP:* Open*;IP:* Vf) a vector commitment scheme with inner product openings. All the algorithms work as the ones for LVC, except that they take as inputs the m vector of coecients of the linear function f 2F_IP, f(v) = f v, i.e. use the vector f 2 F_p.

$$ f,\subset,\mathcal{F}_{\mathsf{I P}},= $$

$$ {f:\mathbb{F}^{m}\to\mathbb{F}} $$

$$ \mathsf{I P=(I P.K e y G e n,P P)} $$

$$ f\in\mathcal{F}_{\mathsf{I P P}},,f(\mathbf{v})=\mathbf{f}\cdot\mathbf{v}. $$

$$ \mathbf{f}\in\mathbb{F}_{p}^{m} $$

The rst one is in the monomial basis and the other based on the univariate sumcheck of [2, 26] that considers vectors encoded as polynomials in the Lagrange basis. We prove they are indeed linear vector commitment arguments with homomorphic proofs and openings. Therefore, they can be used as a starting point to obtain further aggregation properties as shown in Section 4.1 and, in particular, lead to two dierent more generic linear-map vector commitment schemes.

5.1 Monomial Basis

m For the rst scheme, we consider vectors a 2 F encoded as a polynomial in the monomial basis, that is as Pm i 1 a(X) =_i=1a_iX :

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ a(X)=\sum_{i=1}^{m}a_{i}X^{i-1} $$

IP*:* KeyGen(1*; F*_IP)! (prk*;*vrk):

Generate group description gk = (p; G₁*;G₂;* G_T;e) G (p)

Sample F

$$ \operatorname{c r i p t i o n\ g k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T},e)\leftarrow\mathcal{G}(p $$

$$ \tau\gets\mathbb{F} $$

i m m 1 i m Output prk = f[]1;2gⁱ=01*;* vrk = []¹; []². Pⁱ=0

$$ \mathrm {p r k} = \left(\left{\left[ \tau^ {i} \right] _ {1, 2} \right} _ {i = 0} ^ {m - 1}\right), \mathrm {v r k} = \left(\left[ \tau^ {m - 1} \right] _ {1}, \left{\left[ \tau^ {i} \right] _ {2} \right} _ {i = 0} ^ {m}\right) $$

m i 1 IP*:* Co_mm_it(prk*;a)!* (C^a*;aux): Compute C_a=i₌₁a_i[]¹and output (C_a;*a).

$$ P.o m m i n(p r,))\rightarrow(C_{a},d l x) $$

$$ (\mathsf{C}_{a},\mathbf{a}) $$

$$ \mathsf{C}{a}=\sum{i=1}^{m}a_{i}[\tau^{i-1}]_{1} $$

IP*:* Open(prk*;aux;* b*;y*)! :

Find R(X);H(X) such that deg(R) < m 1 and ! !

$$ R(X),H(X) $$

$$ \deg(R)<m-1 $$

$$ \left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}b_{i}X^{m-i}\right)-y X^{m-1}=R(X)+X^{m}H(X). $$

Dene R^(X) = XR(X)

$$ {\hat{R}}(X)=X R(X) $$

Output = ([R()]; [H()]; [R^()]). ₁ 1 1

$$ \pi=\left([R(\tau)]{1},[H(\tau)]{1},[\hat{R}(\tau)]_{1}\right) $$

Pm m i^] IP: Vf(vrk*;* C^a; b*;y;)!* 0*=1 :Compute C_b=_i=1b_i[]₁, parse = ([R]¹;* [H]¹; [R¹) and output 1 if and only if m 1 m e C*;* C e y[];[¹] = e [R];[1] + e [H]; [] and

$$ \mathsf{I P.V f}(\mathsf{v r k},\mathsf{C}{a},\mathbf{b},\hat{y},\pi)\overset{\cdot}{\to}\mathbf{0//1}\ \ {{\tilde{\mathrm{}{\ C}i m p n i t e}}^{\cdot}}\hat{\mathsf{C}}{b};=;\sum_{i=1}^{m}b_{i}[\tau^{m-i}]_{1} $$

$$ \pi = \left([ R ] _ {1}, [ H ] _ {1}, [ \hat {R} ] _ {1}\right) $$

$$ e \left(\mathrm {C} _ {a}, \mathrm {C} _ {b}\right) - e \left(y \left[ \tau^ {m - 1} \right] _ {1}, [ 1 ] _ {2}\right) = e \left([ R ] _ {1}, [ 1 ] _ {2}\right) + e \left([ H ] _ {1}, [ \tau^ {m} ] _ {2}\right) \text {a n} $$

$$ e([R]{1},[\tau]{2})=e([\hat{R}]{1},[1]{2}). $$

Remark 2. The second verication equation is meant to ensure that [R]₁is the evaluation at of a polynomial of degree at most m 2. Note that it is important for security that only m 1 powers of are available to the adversary in G₁, otherwise the second equation does not guarantee that the degree is at most m 2. Importantly, even though we present our construction using a srs with powers of up to m 1 in G₁ and m in G₂, it can easily be adapted for a bigger srs and, in particular, existing trusted setups where the same powers of are available in both groups are enough. For the second check, if m + k powers of are given in ^(k+2 G₁, R X) should be dened as X R(X).

$$ [R]_{1} $$

$$ m-2 $$

$$ \tau $$

$$ m-1 $$

$$ \mathbb{G}_{1} $$

$$ m-2 $$

$$ m-1 $$

$$ \mathbb{G}_{2} $$

$$ \mathbb{G}_{1} $$

$$ m+k $$

$$ \mathbb{G}_{1},,\hat{R}(X) $$

$$ X^{k+2}R(X) $$

We implement this construction for single positions and compare it with individual position openings in Merkle tree-based vector commitments in Appendix 7.1.

Theorem 3. The construction above satises Completeness, Homomorphic Proofs and Homomorphic Open- ings.

Proof. Completeness follows from simple inspection.

Homomorphic Proofs. Let y^b= a b, y^c= a c,^bIP*:* Prove(srs*;* a*;* b*;y*^b) and^cIP*:* Prove(srs*;* a*;* c*;y*_c), where = ([R ()]; [H ()]; [R^ ()]), = ([R ()]; [H ()]; [R^ ()]) are such that b b 1 b 1 b 1 c c 1 c 1 c 1 ! !

$$ y_{b}=\mathbf{a}\cdot\mathbf{b},:y_{c}=\mathbf{a}\cdot\mathbf{c},:\pi_{b}\leftarrow\mathsf{I P.P r o v e}(\mathsf{s r s},\mathbf{a},\mathbf{b},y_{b}) $$

$$ \pi_{c}\leftarrow|\sf P o p r o e(s r s,a,c,y_{c}) $$

$$ \pi_{b}=([R_{b}(\tau)]{1},[H{b}(\tau)]{1},[\hat{R}{b}(\tau)]{1}),:\pi{c}=([R_{c}(\tau)]{1},[H{c}(\tau)]{1},[\hat{R}{c}(\tau)]_{1}) $$

$$ \left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}b_{i}X^{m-i}\right)-y_{b}X^{m-1}=R_{b}(X)+X^{m}H_{b}(X), $$

$$ \left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}c_{i}X^{m-i}\right)-y_{c}X^{m-1}=R_{c}(X)+X^{m}H_{c}(X), $$

$$ \operatorname{a n d};\hat{{R}}{b}(X)={X}{R}{b}(X),\hat{{R}}{c}(X)={X}{R}{c}(X). $$

In order to compute a proof that a ( b + c) = y_b+ y_c, the prover proceeds as follows:

$$ \mathbf{a}\cdot(\mathbf{a}\mathbf{b}+\beta\mathbf{\hat{c}})=\alpha y_{b}+\beta y_{c} $$

$$ \begin{aligned}{(\sum_{i=1}^{m}a_{i}X^{i-1})}&{{}(\alpha\sum_{i=0}^{m}b_{i}X^{m-i}+\beta\sum_{i=1^{m}}c_{i}X^{m-i})=}\ {}&{{}=\alpha(\sum_{i=1}^{m}a_{i}X^{i-1})(\sum_{i=1}^{m}b_{i}X^{m-i})+\beta(\sum_{i=1}^{m}a_{i}X^{i-1})(\sum_{i=1}^{m}c_{i}X^{m-i})}\ {}&{{}=\alpha(y y^{m-1}+R_{i}(X)+X^{m}H_{i}(X))+\beta(y_{}^X m m+i X right()+X^{m}H{c}(X)\ )}\ {}&{{}=(\alpha y_{b}+\beta y_{b})X^{m-1}+(\alpha b_{b}(X)+\beta R_{c}(X))+X^{m}(\alpha H_{b}(X)+\beta H_{c}(X)),}\ \end{aligned} $$ and therefore for y = y + y it outputs = ([R()]; [H()]; [R^()]) where R(X) = R (X) +R (X), b ^c 1 1 1 b c H(X) = H (X) + H (X) and R^(X) = XR(X) = XR (X) + XR (X) = R^ (X) + R^ (X), i.e., b c b c b c =_b+_c.

$$ y=\alpha y_{b}+\beta y_{c} $$

$$ R(X)=\alpha R_{b}(X)+\beta R_{c}(X) $$

$$ \pi=\left([R(\tau)]{1},[H(\tau)]{1},[\hat{R}(\tau)]_{1}\right) $$

$$ H(X),=,\alpha H_{b}(X),+,\beta H_{c}(X),,\mathrm{a n d},,\dot{R}(X),=,X R(X),=,\alpha X R_{b}(X),+,\beta X R_{c}(X),=,\alpha\dot{R}{b}(X)+\beta\dot{R}{c}(X),,,\mathrm{..c.},, $$

Homomorphic Openings. The proof for homomorphic openings work analogous as the previous case. Indeed, for y^a= a c, y_b= b c and^aIP*:* Prove(srs*;* a*;* b*;y*^a),^cIP*:* Prove(srs*;* c*;* b*;y*_c),_a= ([R ()]; [H ()]; [R^ ()]), = ([R ()]; [H ()]; [R^ ()]), it is enough to see that: a 1 a 1 a 1 c c 1 c 1 c 1

$$ \pi=\alpha\pi_{b}+\beta\pi_{c} $$

$$ y_{a};=;\mathbf{a}\ :\mathbf{c},\ y y_{b};=;\mathbf{b}\cdot\mathbf{c};;{\sf a n d};;\pi_{a};\leftarrow;{\sf I P}.{\sf P r o w e}(\mathbf{s r s},\mathbf{a},\mathbf{b},y_{a}),\ \pi_{c};\leftarrow;{\sf I P}.{\sf P r o w e}(\mathbf{s s s},\mathbf{c},\mathbf{b},y_{c}),\ \pi_{a};= $$

$$ ([R_{a}(\tau)]{1},:[H{a}(\tau)]{1},:[\hat{R}{a}(\tau)]{1}),:\pi{c}=([R_{c}(\tau)]{1},[H{c}(\tau)]{1},[\hat{R}{c}(\tau)]_{1}) $$

$$ \begin{array}{l}{\left(\alpha\sum_{i=1}^{m}a_{i}X^{i-1}+\beta\sum_{i=1}^{m}c_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}b_{i}X^{m-i}\right)}\ {=\alpha\left(y_{a}X^{m-1}+R_{a}(X)+X^{m}H_{a}(X)\right)+\beta\left(y_{c}X^{m-1}+R_{c}(X)+X^{m}H_{c}(X)\right)}\ {=(\alpha y_{a}+\beta y_{c})X^{m-1}+(\alpha R_{a}(X)+\beta R_{c}(X))+X^{m}(\alpha H_{a}(X)+\beta H_{c}(X)),}\ \end{array} $$

and the rest of the proof is the same as the one for homomorphic openings.

Theorem 4. The construction above satises Strong Function Binding in the AGM under the (m 1*;m*)- BSDH Assumption.

$$ (m-1,m). $$

Proof. Consider an adversary A that given (prk*;vrk) IP:* KeyGen(1*; F*) is able to generate a commitment and K proofs C_a; fb_k;y_k;_bkg A (prk*;vrk) such that 8k 2 [K] : IP:* Vf(vrk*;* C_a; b_k;y_k;_bk) = 1 and k2[K] m there is no a 2 F s. t. 8k 2 [K] : a b_k= y_k. Without loss of generality, we can consider K = 2: adversary A outputs ((b*;y*^b;^b);(c*;y*^c;^c)) A (prk*;*vrk).

$$ (P1K,W K K)\leftarrow1P.K e y G e n(1^{\lambda},\mathcal{F}) $$

$$ \left(\mathrm {C} _ {a}, \left{\mathbf {b} _ {k}, y _ {k}, \pi_ {b _ {k}} \right} _ {k \in [ K ]}\right) \leftarrow \mathcal {A} (\mathrm {p r k}, \mathrm {v r k}) $$

$$ \forall k\in[K]:\ \ \mathsf{I P.V f}(\mathsf{v r k},\mathsf{C}{a},\mathsf{b}{k},y_{k},\pi_{b_{k}})=\mathbf{1} $$

$$ \mathfrak{l}}\in\mathbb{F}^{m},\mathfrak{s.,t},\forall k\in\left[K\right]:\mathfrak{a}^{'}\cdot\mathfrak{b}{k}=y{k} $$

$$ ((\mathfrak{b},y_{b},\pi_{b}),(\mathfrak{c},y_{c},\pi_{c}))\leftarrow A(\mathfrak{p},\mathfrak{k},\mathfrak{k}) $$

$$ K=2: $$

For commitment C ^and proofs = ([R]; [H]; [R^]) and = ([R]; [H]; [R^]) we have that in a b b 1 b 1 b 1 c c 1 c 1 c 1 the AGM there exists polynomials a(X);H (X);R (X); R^ (X) and H (X);R (X); R^ (X) of degree up to b b b c c c m 1 such that C = [a()], [R] = [R ()], [H] = [H ()]; [R^] = [R^ ()] and [R] = [R ()], a ₁ b 1 b 1 b 1 b 1 b 1 b 1 c 1 _{c 1} [H] = [H ()]; [R^] = [R^ ()]. _{c 1} c 1 c 1 c 1

$$ \pi_{b}=\big([R_{b}]{1},[H{b}]{1},[\hat{R}{b}]_{1}\big) $$

$$ C_{a} $$

$$ \pi_{c}=([R_{c}]{1},[H{c}]{1},[\dot{R}{c}]_{1}) $$

$$ a(X),H_{b}(X),R_{b}(X),\hat{R}_{b}(X) $$

$$ H_{c}(X),R_{c}(X),\hat{R}_{c}(X) $$

$$ m-1 $$

$$ \mathsf{C}{a}:=:[a(\tau)]{1},;[R_{b}]{1}:=:[R{b}(\tau)]{1},;[H{b}]{1}:=:[H{b}(\tau)]{1},[\hat{R{b}}]{1}:=:[\hat{R{b}}(\tau)] $$

$$ [R_{c}]{1}=[R{c}(\tau)]_{1} $$

$$ [H_{c}]{1}=[H{c}(\tau)]{1},[\mathring{R}{c}]{1}=[\mathring{R}{c}(\tau)]_{1} $$

The second verication equation in our IP scheme assures that, except in the case where is a root for the polynomial R(X)X R^(X) which happens with probability m=jFj, R(X)X = R^(X). We can then assume the latter is the case and since deg(R^)*;deg(R^) m 1, we have deg(R);*deg(R) m 2. b c b c P

$$ \tau $$

$$ m/|\mathbb{F}|,,R(X)X=\hat{R}(X) $$

$$ R(X)X-{hat{R}}(X) $$

$$ ^{\prime}\hat{R}{b}),\deg(\hat{R}{c})\leq m-1 $$

$$ (R_{b}),\deg(R_{c})\leq m-2 $$

m m i 1 Note also that as deg(a) m 1, there exists a vector a 2 F such that a(X) =ⁱ⁼¹aⁱX. Then, from the rst vericatⁱon equation in both of the proofs_band_cwe have that the following two polynomials have a common root in :

$$ \deg(a)\leq m-1 $$

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ a(X)=\sum_{i=1}^{m}a_{i}X^{i-1} $$

$$ \pi_{b} $$

$$ \pi_{C} $$

$$ \tau: $$

$$ P_{b}(X)=\left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}b_{i}X^{m-i}\right)-y_{b}X^{m-1}-R_{b}(X)+X^{m}H_{b}(X). $$

$$ P_{c}(X)=\left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}c_{i}X^{m-i}\right)-y_{c}X^{m-1}-R_{c}(X)+X^{m}H_{c}(X). $$

We rst argue that at least one of the polynomials P_b(X) or P_c(X) is not the zero polynomial. Let us m suppose both Pb(X) and Pc(X) are zero polynomials. Because deg(Rb);deg(Rc) < m 1 and deg(X Hb(X)); Pm m m 1 deg(X H*c(X)) > m 1, we have that the coecient for X in polyno_mial Pb(X) isi=1aibiyb= 0. Pm m 1 Same holds for the coecient of X in polynomial P_c(X):_i=1a_ic_iy_c= 0. This means that there exists a vector a such that a b = y_b^* a c = y_c, contradicting the initial assumption that the adversary A breaks the strong functional binding.

$$ P_{b}(X) $$

$$ P_{c}(X) $$

$$ P_{b}(X) $$

$$ P_{c}(X) $$

$$ (R_{b}),\mathrm{d e g}(R_{c})<m{-1} $$

$$ \operatorname{d e g}(X^{m}H_{b}(X)) $$

$$ \deg(X^{m}H_{c}(X))>m-1 $$

$$ X^{m-1} $$

$$ P_{b}(X) $$

$$ X^{m-1} $$

$$ \textstyle{\sum_{i=1}^{m}a_{i}b_{i}-y_{b}=0} $$

$$ P_{c}(X):\sum_{i=1}^{m}a_{i}c_{i}-y_{c}=0 $$

$$ \mathbf{a}\cdot\mathbf{b}=y_{b}\ \wedge\ \mathbf{a}\cdot\mathbf{c}=y_{c} $$

Consider now that the non-zero polynomial is P_b(X). Then, since is one of the roots of this polynomial, we can solve the discrete logarithm problem and extract from the exponent of [P_b()]₁.

$$ P_{b}(X) $$

$$ \big[P_{b}(\tau)\big]. $$

To extend the proof to the case where we give m + k powers of in G₁ in the prk: We will have a degree check that insures that polynomials R(X) are still of maximum degree m 2 and instead of extracting a Pm+k+1 m m+k+1 i 1 vector a 2 F, we get a 2 F and thus a(X) =_i=1a_iX. St_ill, the coecient for the power m _{1 m} X is ~a b, for ~a = (a_i)_i=1, so the proof follows in the same way. ut

$$ \tau $$

$$ m+k $$

$$ \mathbb{G}_{1} $$

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ R(X) $$

$$ m-2 $$

$$ \mathbf{a}\in\mathbb{F}^{m+k+1} $$

$$ a(X)=\sum_{i=1}^{m+k+1}a_{i}X^{i-1} $$

$$ X^{m-1} $$

$$ \tilde{\mathbf{a}}=(a_{i})_{i=1}^{m} $$

Updates Without Keys. In the case of our rst construction in 5.1, we remark that we do not need any additional update keys added to the setup. Indeed, the update key is made by proofs of inner products between cannonic vectors e_ie_i= 1 or e_ie_j= 0. In our construction for encodings in the monomial basis, a proof that e_ie_i= 1 consists on R(X) = H(X) = 0. On the other hand, to prove that e_ie_j= 0 for i 6= j m+i j i j the proof is (the evaluation in the group of) either R(X) = X ⁱf j > i, or H(X) = X ⁱf i > j. As such powers of are already included in prk, upk =;.

$$ \mathbf{e}{i}\cdot\mathbf{e}{i}=0 $$

$$ \mathbf{e}{i}\cdot\mathbf{e}{i}=1 $$

$$ \mathbf{e}{i}\cdot\mathbf{e}{i}=1 $$

$$ R(X)=H(X)=0 $$

$$ \mathbf{e}{i}\cdot\mathbf{e}{j}=0 $$

$$ i\neq j $$

$$ R(X)=X^{m+i-j}{\mathrm{i f}}j>i. $$

$$ H(X)=X^{{\ddot{i-j}}}{\mathrm{i f}}i>j $$

5.2 Lagrange Basis

m In this second scheme, for a Lagrange basis fi(X)gi=1over a multiplicative group H = fh₁*;:::;hmg* of size Pm m m in F we encode a vector a 2 F as a polynomial a(X) =_i=1a_{i i}(X).

$$ {\lambda_{i}(X)}_{i=1}^{m} $$

$$ \mathbb{F} $$

$$ \mathbb{H}={\mathsf{h}{1},\ldots,\mathsf{h}{m}} $$

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ \textstyle{\bar{a({X})}=\sum_{i=1}^{m}a_{i}\lambda_{i}({)}X)} $$

The construction uses few properties of Lagrange basis over multiplicative groups that we would like to 1 remind before formally presenting our scheme. When H is a multiplicative subgroup,_i(0) = m for all m i 2 [m]. Moreover, if H = fhigi=1consists oof the roots of unity of order m, theni(hi) = 1 andi(hj) = 0 Qm for i 6= j and for the vanishing polynomial t(X) =_i=1(X h_i) we have that

$$ \lambda_{i}(0)=m^{-1} $$

$$ i\in[m] $$

$$ \mathbb{H}={\mathsf{h}{i}}{i=1}^{m} $$

$$ m. $$

$$ t (X) = \prod_ {i = 1} ^ {m} \left(X - \mathrm {h} _ {i}\right) $$

$$ \lambda_{i}(\mathsf{h}_{i})=1 $$

$$ \lambda_{i}({\mathfrak{h}}_{j})=0 $$

$$ i\neq j $$

$$ \lambda_{i}(X)\lambda_{j}(X)\equiv0\ \mod{t(X)},\qquad\lambda_{i}(X)^{2}\equiv\lambda_{i}(X)\ \mod{t(X)}. $$

The construction below, presented in [26], exploits these properties in the proof of openings for innerproducts:

$$ 1P.\mathsf{K e y G e n}(1^{\lambda},\mathcal{F}{1\mathsf{P}{m}})\to(\mathsf{p r k},\mathsf{v r k}): $$

IPm Generate group description gk = (p; G₁*;G₂;* G_T;e) G (p)

$$ \mathfrak{g}\mathsf{k}=(p,\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{T},e)\gets\mathcal{G}(p) $$

Dene multiplicative group H = fh₁*;:::;*h^mg in F

$$ \mathbb{H}=\left{\mathsf{h}{1},\ldots,\mathsf{h}{m}\right}\operatorname{i n}] $$

m Compute Lagrange polynomials f_j(X)g_j=1over H.

$$ {\lambda_{j}(X)}_{j=1}^{m}{\mathrm{o v e r}}\mathbb{H}. $$

Sample F

$$ \tau\gets\mathbb{F} $$

i m m i m Output prk = f[]^1;2gⁱ⁼¹; f[ⁱ()]1g_i⁼¹m 1*;* []²and vrk = [¹]1*;²; []2;* [ⁱ()]². P_i=1 ^m IP: Commit(prk*;a)!* (C_a*;aux): Compute C_a=_i=1a_i[_i()]₁and output (C_a;*a).

$$ \operatorname {o r k} = \left(\left{\left[ \tau^ {i} \right] _ {1, 2} \right} _ {i=1} ^ {m}, \left{\left[ \lambda_ {i} (\tau) \right] _ {1} \right} _ {i=1} m - 1, \left[ \tau^ {m} \right] _ {2}\right) $$

$$ \mathsf{w k}=\left([1]{1,2},\left{[\tau^{i}]{2},[\lambda_{i}(\tau)]{2}\right}{i=1}^{m}\right) $$

$$ \textstyle(\mathsf{p r k},\mathbf{a})\stackrel{\cdot}{\to}(\mathsf{C}{a},\mathsf{a u x})\mathrm{}{:~}\operatorname{C o m p u t e~~}\mathsf{C}{a}=\sum_{i=1}^{m}a_{i}[\lambda_{i}(\tau)]_{1} $$

IP*:* Open(prk*;aux;* b*;y*)! :

$$ (\mathsf{C}_{a},\mathbf{a}) $$

Find R(X);H(X) such that deg(R) < m 1 and ! !

$$ R(X),H(X) $$

$$ \deg(R)<m-1 $$

$$ \left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)-m^{-1}y=X R(X)+t(X)H(X) $$

Dene R^(X) = XR(X) and output = ([PR()]; [H()]; [R^()]). ₁ 1 1 m IP*:* Vf(vrk*;* C_a; b*;y;)!* 0*=*1 :Calculate C_b=_i=1b_i[_i()]₂

$$ {\hat{R}}(X)=X R(X) $$

$$ \pi=\big([R(\tau)]{1},[H(\tau)]{1},[\hat{R}(\tau)]_{1}\big). $$

$$ \ {sf P P}V({\sf v r k},{\sf C}_{a},{\sf b},y,\pi)\to0/1 $$

$$ \mathsf{C}{b}=\sum{i=1}^{m}b_{i}[\lambda_{i}(\tau)]_{2} $$

Parse = ([R]; [H]; [R^]) and output 1 if and only if 1 1 1

$$ \pi=([R]{1},[H]{1},[\dot{R}]_{1}) $$

$$ {}{e}({mathsf C}{a},{\mathsf{C}}{b})-{}{e}(m^{-1}{}{}{y}[1]{1},{}{[}1]{2}){{}}{=}{{e}}([R]{1},{}[1]{2}){{}}{+}{{e}}([H]{1},{}[t(\tau)]{2}), $$

$$ e\big([R]{1},[\tau]{2}\big)=e\big([\hat{R}]{1},[1]{2}\big). $$

We omit the proof of completeness as it can be found in [26]. Still, since there it is presented as an NIZK argument for inner-product relations as opposite to LVC scheme as considered in this paper, we prove Strong Function Binding and homomorphic proofs and openings below.

Theorem 5. The construction above has Homomorphic Proofs and Openings.

Proof. Completeness follows from simple inspection.

$$ \text {P r o o f s}. \text {L e t} y _ {b} = \mathbf {a} \cdot \mathbf {b}, y _ {c} = \mathbf {a} \cdot \mathbf {c}, \pi_ {b} \leftarrow \mathrm {I P}. \operatorname {P r o v e} (\mathrm {s r s}, \mathbf {a}, \mathbf {b}, y _ {b}) \text {a n d} \pi_ {c} \leftarrow \mathrm {I P}. \operatorname {P r o v e} (\mathrm {s r s}, \mathbf {a}, \mathbf {c}, y _ {c}), $$

$$ \pi_{b}=([R_{b}(\tau)]{1},[H{b}(\tau)]{1},[\hat{R}{b}(\tau)]{1}),:\pi{c}=([R_{c}(\tau)]{1},[H{c}(\tau)]{1},[\hat{R}{c}(\tau)]_{1}) $$

$$ \left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)-m^{-1}y_{b}=X R_{b}(X)+t(X)H_{b}(X), $$

$$ \left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}c_{i}\lambda_{i}(X)\right)-m^{-1}y_{c}=X R_{c}(X)+t(X)H_{c}(X), $$

$$ \operatorname{a n d};\hat{\ }{hat R_{{b}}}(X)={\ }X R_{b}(X),;\hat{R R_{{c}}}(X)=X R_{{c}}(X). $$

In order to compute a proof that a ( b + c) = y_b+ y_c, the prover proceeds as follows:

$$ \mathbf{a}\cdot(\alpha\mathbf{b}+\beta\mathbf{}\mathbf{c})=\alpha y_{b}+\beta y_{c} $$

$$ \begin{array}{l} \left(\sum_ {i = 1} ^ {m} a _ {i} \lambda_ {i} (X)\right) \left(\alpha \sum_ {i = 1} ^ {m} b _ {i} \lambda_ {i} (X) + \beta \sum_ {i = 1} ^ {m} c _ {i} \lambda_ {i} (X)\right) \ = \alpha \left(\sum_ {i = 1} ^ {m} a _ {i} \lambda_ {i} (X)\right) \left(\sum_ {i = 1} ^ {m} b _ {i} \lambda_ {i} (X)\right) + \beta \left(\sum_ {i = 1} ^ {m} a _ {i} \lambda_ {i} (X)\right) \left(\sum_ {i = 1} ^ {m} c _ {i} \lambda_ {i} (X)\right) \ = \alpha \left(m ^ {- 1} y _ {b} + X R _ {b} (X) + t (X) H _ {b} (X)\right) + \beta \left(m ^ {- 1} y _ {c} + X R _ {c} (X) + t (X) H _ {c} (X)\right) \ = m ^ {- 1} \left(\alpha y _ {b} + \beta y _ {c}\right) + X \left(\alpha R _ {b} (X) + \beta R _ {c} (X)\right) + t (X) \left(\alpha H _ {b} (X) + \beta H _ {c} (X)\right), \ \end{array} $$

and therefore for y = y + y it outputs = ([R()]; [H()]; [R^()]) where R(X) = R (X) +R (X), b ^c 1 1 1 b c H(X) = H (X) + H (X) and R^(X) = XR(X) = XR (X) + XR (X) = R^ (X) + R^ (X), i.e., b c b c b c =_b+_c.

$$ y=\alpha y_{b}+\beta y_{c} $$

$$ \pi=\left([R(\tau)]{1},[H(\tau)]{1},[\hat{R}(\tau)]_{1}\right) $$

$$ R(X)=\alpha R_{b}(X)+\beta R_{c}(X) $$

$$ \bar{R}(X),=,X R(X),=,\alpha X R_{b}(X),+,\beta X R_{c}(X),=,\alpha\bar{R}{b}(X),+,\beta\bar{R}{c}(X) $$

$$ H(X)=\alpha H_{b}(X)+\beta H_{c}(X) $$

Homomorphic Openings. The proof for homomorphic openings work analogous as the previous case. Indeed, for y_a= a c, y_b= b c and_aIP*:* Prove(srs*;* a*;* b*;y*_a),_cIP*:* Prove(srs*;* c*;* b*;y*_c), it is enough to see that:

$$ \pi=\alpha\pi_{b}+\beta\pi_{c} $$

$$ y_{a}=\mathbf{a}\cdot\mathbf{c},,y_{b}=\mathbf{b}\cdot\mathbf{c}} $$

$$ \pi_{a}\gets\mathsf{I P.P r o v e}(\mathsf{s r s},\mathbf{a},\mathbf{b},y_{a}),:\pi_{c}\gets\mathsf{I P.P r o v e}(\mathsf{s r s},\mathbf{c},\mathbf{b},y_{c}) $$

$$ \begin{array}{l}{\left(\alpha\sum_{i=1}^{m}a_{i}\lambda_{i}(X)+\beta\sum_{i=1}^{m}c_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)}\ {=\alpha\left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)+\beta\left(\sum_{i=1}^{m}c_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)}\ {=\alpha(\sum_{i=1}^{m-y_{a}}+X R_{m}(X)+t(X)H_{a}(X))+\beta\left(m^{-1}y_{e}+\lambda R_{e}(X)+t(X)H_{c}(X)\right)}\ {=alpha^{-1}(\alpha y_{a}+\beta y_{e})+X(\alpha H_{a}(X)+\beta R_{e}(X))+t(X)(\alpha H_{a}(X)+\beta H_{e}(X)),}\ \end{array} $$

and the rest of the proof is the same as the one for homomorphic openings.

Theorem 6. The construction above satises Strong Function Binding in the AGM under the (m 1*;m*)- BSDH Assumption.

$$ (m-1,m)\cdot $$

Proof. Consider an adversary A that given (prk*;vrk) IP:* KeyGen(1*; F*_IP) is able to generate a commitment and K proofs C_a; fb_k;y_k;_bkg A (prk*;vrk) such that 8k 2 [K] : IP:* Vf(vrk*;* C_a; b_k;y_k;_bk) = 1 and k2[K] m there is no a 2 F s. t. 8k 2 [K] : a b_k= y_k. Without loss of generality, we can consider K = 2: adversary A outputs ((b*;y*^b;^b);(c*;y*^c;^c)) A (prk*;*vrk).

$$ (p r k,v r k)\leftarrow P y X e q(1^{\lambda},F_{P P}) $$

$$ \forall k\in[K]:\ \mathsf{I P.V f}(\mathsf{v r k},\mathsf{C}{a},\mathsf{b}{k},y_{k},\pi_{b_{k}})=1 $$

$$ \mathsf{a}\in\mathbb{F}^{m},\mathsf{s}.,\mathsf{t}.,\forall k\in\left[K\right]:\mathsf{a}\cdot\mathsf{b}{k}=y{k} $$

$$ K=2. $$

$$ ((\mathfrak{b},y_{b},\pi_{b}),(\mathfrak{c},y_{c},\pi_{c}))\leftarrow A(\mathfrak{p}m,v/k) $$

For commitment C ^and proofs = ([R]; [H]; [R^]) and = ([R]; [H]; [R^]) we have that the a b b 1 b 1 b 1 c c 1 c 1 c 1 AGM extractor outputs polynomials a(X);H (X);R (X); R^ (X) and H (X);R (X); R^ (X) of degree up to b b b c c c m 1 such that C = [a()], [R] = [R ()], [H] = [H ()]; [R^] = [R^ ()] and [R] = [R ()], a ₁ b 1 b 1 b 1 b 1 b 1 b 1 c 1 _{c 1} [H] = [H ()]; [R^] = [R^ ()]. _{c 1} c 1 c 1 c 1

$$ \pi_{b}=\big([R_{b}]{1},[H{b}]{1},[\hat{R}{b}]_{1}\big) $$

$$ C_{a} $$

$$ \pi_{c}=([R_{c}]{1},[H{c}]{1},[\hat{R}{c}]_{1}) $$

$$ a(X),H_{b}(X),R_{b}(X),\dot{R}_{b}(X) $$

$$ H_{c}(X),R_{c}(X),\dot{R}_{c}(X) $$

$$ m-1 $$

$$ \mathsf{C}{a}:=:[a(\tau)]{1},;[R_{b}]{1}:=:[R{b}(\tau)]{1},;[H{b}]{1}:=:[H{b}(\tau)]{1},[\hat{R{b}}]{1}:=:[\hat{R{b}}(\tau)] $$

$$ [R_{c}]{1}=[R{c}(\tau)]. $$

$$ [H_{c}]{1}=[H{c}(\tau)]{1},[\hat{R}{c}]{1}=[\hat{R}{c}(\tau)]_{1} $$

As in the proof of Thm. 4, the second verication equation in our IP scheme assures that, except with probability m=jFj, we have that deg(R^)*;deg(R^) m 1, so deg(R);*deg(R) m 2. b c b c P

$$ \mathrm{d e g}(\hat{R}{b}),\mathrm{d e g}(\hat{R}{c})\leq m-1 $$

$$ m/|\mathbb{F}| $$

$$ |\mathrm{e g}(R_{b}),\mathrm{d e g}(R_{c})\leq m-2 $$

m m i 1 Note also that as deg(a) m 1, there exists a vector a 2 F such that a(X) =ⁱ⁼¹aⁱX. Then, from the rst vericatⁱon equation in both of the proofs_band_cwe have that the following two polynomials have a common root in : ! !

$$ \operatorname{d e g}(a)\leq m-1 $$

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ a(X)=\sum_{i=1}^{m}a_{i}X^{i-1} $$

$$ \pi_{b} $$

$$ \tau $$

$$ \pi_{c} $$

$$ P_{b}(X)=\left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}b_{i}X^{m-i}\right)-m^{-1}y_{b}-X R_{b}(X)+t(X)H_{b}(X). $$

$$ P_{c}(X)=\left(\sum_{i=1}^{m}a_{i}X^{i-1}\right)\left(\sum_{i=1}^{m}c_{i}X^{m-i}\right)-m^{-1}y_{c}-X R_{c}(X)+t(X)H_{c}(X). $$

We rst argue that at least one of the polynomials P_b(X) or P_c(X) is not the zero polynomial. Let us suppose both P_b(X) and P_c(X) are zero polynomials. Because deg(Rb);deg(Rc) < m 1 and ! !

$$ P_{c}(X) $$

$$ P_{b}(X) $$

$$ P_{b}(X) $$

$$ P_{c}(X) $$

$$ \deg({R_{b}}),\deg(R R_{c})<m-1 $$

$$ \left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\right)\equiv\sum_{i=1}^{m}a_{i}b_{i}\lambda_{i}(X)\ \mod t{t(X)}, $$

$$ \left(\sum_{i=1}^{m}a_{i}\lambda_{i}(X)\right)\left(\sum_{i=1}^{m}c_{i}\lambda_{i}(X)\right)\equiv\sum_{i=1}^{m}a_{i}c_{i}\lambda_{i}(X)\ \mod t{t(X)}, $$

PmPm 1 1 i=1aibi i(X) m yb= XRb(X), which i^mpliesi=1aibi i(0) m yb= 0. Same reasoning leads to P^m 1 1 i=1aici i(0) m y = 0. As H is a multiplicative subgroup,i(0) = m for all i 2 [m] and thus PmP^mc ⁱ⁼¹aⁱbⁱ= y_bandⁱ₌₁a_ic_i= y_c. Namely, there exists a such that a b = y_band a c = y_ccontradicting the initial claim that adversary A is successful.

$$ \textstyle\sum_{i=1}^{m}a_{i}b_{i}\lambda_{i}(X)-m^{-1}y_{b}\ =\ X X_{b}(X) $$

$$ \sum_{i=1}^{m}a_{i}b_{i}\lambda_{i}(0)-m^{-1}y_{b}=0 $$

$$ \sum_{i=1}^{m}a_{i}c_{i}\lambda_{i}(0)-m^{-1}y_{c}=0 $$

$$ \lambda_{i}(0),=,m^{-1} $$

$$ i,\in,[m] $$

$$ \textstyle{\sum_{i=1}^{m}a_{i}b_{i}=y_{b}} $$

$$ \textstyle{\sum_{i=1}^{m}a_{i}c_{i}=y_{c}} $$

$$ \mathbf{a}\cdot\mathbf{b}=y_{b} $$

$$ \mathbf{a}\cdot\mathbf{c}=y_{c} $$

$$ P_{b}(X) $$

$$ \tau $$

$$ [P_{b}(\tau)]_{1} $$

To extend the proof to the case where we give m + k powers of in G₁ in the prk PmP: we can extract a vectorm m+k+1 m 0 0 m 0 a 2 F and set a(X) =_i=1a_{i i}(X) + X a (X) for deg(a) = k. Then,_i=1b_{i i}(X) X a (X), if not zero, is contained in H(X). Indeed, as its degree is 2m + k+ 1 even when taking modulus t(X), it cannot m m be contained in R(X). Then, even when a 2 F, the inner product is proven as a~ b for a~ = (a_i)_i=1. ut

$$ \mathbb{G}_{1} $$

$$ \mathbf{a}\in\mathbb{F}^{m+k+1} $$

$$ a(X)=\sum_{i=1}^{m}a_{i}\lambda_{i}(X)+X^{m}a^{\prime}(X) $$

$$ \deg(a^{\prime})=k $$

$$ \textstyle\big(\sum_{i=1}^{m}b_{i}\lambda_{i}(X)\big)X^{m}a^{\prime}(X) $$

$$ H(X) $$

$$ t(X) $$

$$ \tilde{\mathbf{a}}\cdot\mathbf{b} $$

$$ \mathbf{a}\in\mathbb{F}^{m} $$

$$ \tilde{\mathbf{a}}=(a_{i})_{i=1}^{m} $$

Updatability with Short Keys In this construction, a proof that e_ie_i= 1 is the encoding in a group of the polynomial R_i(), for R_i(X) = (_i(X) 1)=X. On the other hand, the proof that e_ie_j= 0 for i 6= j is [H()]₁, for H(X) = ((_i(X)_j(X))=t(X). Including the evaluation of all these polynomials in upk would require a srs of quadratic size. Still, as noted in [29],

$$ \mathbf{e}{i}\cdot\mathbf{e}{i}=1 $$

$$ R_{i}(X)=(\lambda_{i}(X)-1)/X $$

$$ R_{i}(\tau) $$

$$ \mathsf{e}{i}\cdot\mathsf{e}{j}=0 $$

$$ i\neq j $$

$$ [H(\tau)]_{1} $$

$$ H(X)=((\lambda_{i}(X)\lambda_{j}(X))/t(X) $$

$$ \frac{\lambda_{i}(X)\lambda_{j}(X)}{t(X)}=\frac{t(X)}{(X-\mathsf{h}{i})(X-\mathsf{h}{j})}, $$

and can be computed as

$$ \frac{1}{\mathsf{h}{i}-\mathsf{h}{j}}\left(\frac{t(X)}{X-\mathsf{h}{i}}+\frac{t(X)}{X-\mathsf{h}{j}}\right). $$

Therefore, it is enough to include in upk the evaluations of (_i(X) 1)=X for the proofs of same position m and then the evaluations of ft(X)=(X hⁱ)gⁱ⁼¹, so the verier can reconstruct the one of_i(X)_j(X)=t(X) from there, requiring only 2m elements instead of m².

$$ (\lambda_{i}(X)-1)/X $$

$$ {t(X)/(X-\mathsf{h}{i})}{i=1}^{m} $$

$$ \lambda_{i}(X)\lambda_{j}(X)/t(X) $$

$$ m^{2} $$

6 Subvector Openings

In this section, we present schemes for VC with Subvector Openings (SVC), starting from the constructions of Section 5. Instead of using Def. 8, we will consider SVC as a special case of LVC. The class of functions m that open a set of positions I = fi₁;:::;i_ng of a committed vector v 2 F is given by the linear-map f_I with m n f : F! F; f (v) = (e v;::: e v)

$$ I={i_{1},\ldots,i_{n}} $$

$$ \mathbf{v}\in\mathbb{F}^{m} $$

$$ f_{I} $$

$$ f _ {I}: \mathbb {F} ^ {m} \rightarrow \mathbb {F} ^ {n}, \quad f _ {I} (\mathbf {v}) = \left(\mathbf {e} _ {i _ {1}} \cdot \mathbf {v}, \dots \mathbf {e} _ {i _ {n}} \cdot \mathbf {v}\right) $$

$$ k\in[n],,e_{i_{k}} $$

m where for each k 2 [n], e^ikis the i^kth vector of the canonical basis F.

m Naturally, for a vector v 2 F, we can construct proofs of openings of subvectors v_I= (v_i)_i2Iby aggregating dierent inner product proofs for vectors e^ikfor i^k2 I using the techniques in Section 4.1. We refer to these aggregated proofs as non-native subvector openings, given that they require a random oracle and in particular, are no longer algebraic and homomorphic. As opposed to them, we call native subvector opening, a scheme that is algebraic and homomorphic.

$$ \mathbb{F}^{m} $$

$$ \mathbf{v}\in\mathbb{F}^{m} $$

$$ \mathbf{v}{I},=,(v{i})_{i\in I} $$

$$ \mathbf{e}{i{k}} $$

$$ i_{k}\in I $$

In what follows, we improve on Subvector Openings in some special scenarios, achieving native aggregation for new schemes and reducing the verier complexity in existing ones.

6.1 Special Subset Native Openings for the Monomial Basis

For the construction of Section 5.1, we introduce native subvector openings for subsets with consecutive position I = fi;i + 1*;:::;i* + kg. That is, for c = (ci)i2Isuch that there exist u₁*;u₂ with c = Pi 1 m i+s 1 (Pu₁;*c*;u₂). To prove an opening of c, we only need commitments to R(X) =_s=1c_iX and H(X) = m s 1 i=i+k+1cm i+s+1X, which are shifted-encodings of u₁, u₂. The verier checks that deg(R) < m 1, P_i+k ~(_{s i} ~ = [ ~( ~ _{m i} computes C X) =_s=ic_sX and C C)]₁and checks whether e(C C;* []₁) = e([R]₁;[1]₂) + m+k e([H]₁; []₂).

$$ \mathbf{\tilde{c}}\ =\ (c_{i})_{i\in I} $$

$$ I,=,\left{i,i+1,\ldots,i+k\right} $$

$$ \mathbf{u}{1},\mathbf{u}{2} $$

$$ {{\bf{c}}}\ = $$

$$ (\mathfrak{u}{1},\tilde{\mathfrak{c}},\mathfrak{u}{2}) $$

$$ {tilde{\bf{c}}}_{\ } $$

$$ R(X)=\sum_{s=1}^{i-1}c_{i}X^{m-i+s-1} $$

$$ H(X)= $$

$$ \textstyle\sum_{i=i+k+1}^{m}c_{m-i+s+1}X^{s-1} $$

$$ \mathbf{u}{1},,\mathbf{u}{2} $$

$$ \deg(R)<m-1 $$

$$ \tilde{C}(X),=,\sum_{s=i}^{i+k}\tilde{c}_{s}X^{s-i} $$

$$ \tilde{\mathsf{C}}=[\tilde{\mathsf{C}}(\tau)]. $$

$$ e \left(\mathrm {C} - \tilde {\mathrm {C}}, [ \tau^ {m - i} ] _ {1}\right) = e \left([ R ] _ {1}, [ 1 ] _ {2}\right) + $$

$$ e(\bar{[H]{1}},[\tau^{m+\dot{k}}]{2}) $$

Note that, given individual proofs of openings as in Section 5.1, that is, [R_s()]₁; [H_s()]₁such that m s m 1 ^m C(X)X csX = Rs(X) + X Hs(X) and deg(Rs) < m 1, for the commitments dened above we have [R]₁= [R_i()]₁and [H]₁= [H_i+k()]₁, that is, proofs can be aggregated at no cost for the prover.

$$ [R_{s}(\tau)]{1},[H{s}(\tau)]_{1} $$

$$ C(X)X^{m-s}-c_{s}X^{m-1}=R_{s}(X)+X^{m}H_{s}(X) $$

$$ {R_{s}})<m-1 $$

$$ [R]{1}=[R{i}(\tau)]_{1} $$

$$ [H]{1}=[H{i+k}(\tau)]. $$

We implement this scheme and compare it with opening consecutive positions, or ranges, using Merkle trees in Section 7.2.

6.2 Any Subset Non-native Openings for the Monomial Basis

For the LVC scheme of Section 5.1, the techniques of Section 4.1 allow us to redene the Open and Vf algorithms to work for an arbitrary subset of positions I [m]. More specically, the prover will simply run IP*:* Open(prk*;aux;* eik*;v) for k = 1;:::;n* to obtain (vik*;*ik) andika proof of correct computation of vik. Pn k 1 Then, use the random oracle to sample a randomness 2 F and outputI=_k=₁ ik. P

$$ I\subset[m] $$

$$ \mathsf{I P.O p e n}p(\mathsf{p r k},\mathsf{a t x},\mathsf{e}{i{k}},\mathsf{v}) $$

$$ \left(v_{i_{k}},\pi_{i_{k}}\right) $$

$$ k=1,\ldots,n $$

$$ \pi_{i_{k}} $$

$$ v_{i_{k}} $$

$$ \gamma\in\mathbb{F} $$

$$ \pi_{I}=\sum_{k=1}^{n}\gamma^{k-1}\pi_{i_{k}} $$

^]n k ₁ The verier will receive_I= ([R]₁; [H]₁; [R1), compute y =_k=1v_ik, and check as before e([R]₁; []₂) = e([R^];[₁]) and 1 ₂ !

$$ \pi_{I}=\ [[R]{1},[H]{1},[\hat{R}]_{1}) $$

$$ \textstyle{y=\sum_{k=1}^{n}\gamma^{k-1}v_{i_{k}}} $$

$$ e([R]{1},[\tau]{2})= $$

$$ e([\hat{R}]{1},[1]{2}) $$

$$ e\left(\mathsf{C},\sum_{k=1}^{n}\gamma^{k-1}[\tau^{m-i_{k}}]{2}\right)-e\left(y[\tau^{m-1}]{1},[1]{2}\right)=e\left([R]{1},[1]{2}\right)+e\left([H]{1},[\tau^{m}]_{2}\right). $$

P^{n k} 1 m ik Note that verier’s work is dominated by the computation of^k=1[]², so we analyze for which sets I [m] this computation can be cheaper than jIj G₂-exponentiations. Without loss of generality, we can PnP k 1 m ikm ikm i re-ass_ign*!*, and thus our verier now needs to compute_k=1[(X)]2=_i2I[(X)]₂.

$$ I\subset[m] $$

$$ \textstyle\sum_{k=1}^{n}\gamma^{k-1}[\tau^{m-i_{k}}]_{2} $$

$$ |I|;{\mathbb{G}}_{2}. $$

$$ \gamma^{k-1}\to\gamma^{m-i_{k}} $$

$$ \textstyle\sum_{k=1}^{n}[(\gamma X)^{m-i_{k}}]{2}=\mathring\sum{i\in I}[(\mathring{\gamma X})^{m-i}]_{2} $$

Now, note that if I_k;s;n[m] is an arithmetic progression, i.e. it is such that for a given ratio s; a starting power k and a number n of desired elements, I_k;s;n= fk;s + k;:::;(n 1)s + kg, then

$$ s, $$

$$ I_{k,s,n}\subset[m] $$

$$ I_{k,s,n}=\left{k,s{mathfrak}s+k,\ldots,\left(n-1\right)s+k\right} $$

$$ \sum_{i\in I_{k,s,n}}(\gamma X)^{m-i}=(\gamma X)^{k}\frac{1-(\gamma X)^{n}}{1-(\gamma X)^{s}}. $$

P m i This reduces the work of the verier to compute^i2I(X) to constant. Note that the verier k;s;n s 1 s cannot compute (₁ (X)), so we multiply all the terms of the equation by 1 (X). I.e, the verier P m i computes y =_i2Iy_iand checks whether k;s;n

$$ \sum_ {i \in I _ {k, s, n}} (\gamma X) ^ {m - i} $$

$$ (1-(\gamma X)^{s})^{-1} $$

$$ 1-(\gamma X)^{s}.{\mathrm{I.e}} $$

$$ \textstyle{y=\sum_{i\in I_{k,s,n}}\gamma^{m-i}y_{i}} $$

$$ \begin{aligned}{e\big([C]{1},\gamma^{k}[\tau^{k}]{2}-\gamma^{k+n}[\tau^{k+n}]{2}\big)-e\big([\tau^{m-1}]{1}y-[\tau^{n+s-1}]{1}\gamma^{s}y,[1]{2}\big)}\ {}&{{}=e\big([R]{1},1-\gamma^{s}[\tau^{s}]{2}\big)+e\big([H]{1},[\tau^{n}]{2}-\gamma^{s}[\tau^{n+s}]_{2}\big).}\ \end{aligned} $$

6.3 Any Subset Openings from Lagrange Basis

Native. In the Lagrange Basis, one can use the native subset openings of [29]. There, the verier needs Q to compute computation the vanishing polynomial t_I(X) =_i2I(X h_i) (we recall SVC*:* Open and SVC*:* Vf algorithms in Appendix C). To reduce verifer’s work we focus on those subsets I [m] such that t_I(X) can be calculated in less than jIj computations. One answer to this question comes from cosets. That is, given 2 m 1 n k H = f1*;!;!;:::;! g* group of roots of unity where m = 2, let H_kbe the subgroup of order 2 of H, n=k s where k goes from 0 to n. Then, for each 0 s < 2 we can construct the coset I =! Hk, whose vanishing k k k k 2 s 2 ~ 2 s2 polynomial is t_I(X) = X (!) : Verier accepts if and only if e C C*;[1]₂= e [H]₁;* [x]₂!.

$$ t _ {I} (X) = \prod_ {i \in I} \left(X - \mathrm {h} _ {i}\right) $$

$$ t_{I}(X) $$

$$ I\subset[m] $$

$$ |I| $$

$$ \mathbb{H}=\left{1,\omega,\omega^{2},\ldots,\omega^{m-1}\right} $$

$$ m=2^{n} $$

$$ \mathbb{H}_{k} $$

$$ 2^{k} $$

$$ 0\leq s<2^{n/k} $$

$$ \ =\omega^{s}\mathbb{H}_{k} $$

$$ t_{I}(X)=X^{2^{k}}-(\omega^{s})^{2^{k}} $$

$$ e \left(\mathrm {C} - \tilde {\mathrm {C}}, [ 1 ] _ {2}\right) = e \left([ H ] _ {1}, \left[ x ^ {2 k} \right] _ {2} - \omega^ {s 2 k}\right) $$

Non-native. Given that the native subvector opening procedure above works for arbitrary subsets I [m], we don’t consider aggregation of individual positions. The latter makes sense only when applying a linear function to the new subset. That is, when the verier is given C_f;I, claimed to be a commitment to f c_I, for some linear function f applied to the vector c_I= (c_i)_i2I.

$$ I\subset[m] $$

$$ \mathsf{C}_{f,I} $$

$$ \mathbf{f}\cdot\mathbf{c}_{I} $$

$$ \mathbf{c}{I}=(c{i})_{i\in I} $$

7 Implementation and Experimental Evaluation for LVC

We implement our monomial basis construction in Rust on top of the paired library¹³ and is available on Github¹⁴. In this section we experimentally evaluate dierent features of our monomial-basis construction. In particular we investigate and provide estimates for the following questions:

{ For which set sizes can we expect proving time in our construction to be more ecient than that in SNARKs over Merkle Trees?

{ How benecial is for proving time our range opening?

{ How much can verication time benet from special subset opening?

Log of vector size

Fig. 1: Proving time in our scheme with monomial basis vs SNARKs for Merkle trees opening. Plot is in log-scale.

7.1 Comparison with SNARKs over Merkle Trees

We show our comparison in Fig. 1. We compare to Merkle trees instantiated with both Poseidon hash [16] and with SHA256. The underlying proof system used here is Groth16 [17] in its libsnark implementation¹⁵.

18 We estimate our construction to have more ecient proving time for vectors up to approximately 2, where SNARKs over Poseidon are of similar eciency. Our construction is more ecient than SNARKs for SHA-based Merkle trees for larger vectors. We point out that while Poseidon is a highly SNARK-friendly hash function it is slower than SHA when executed \natively" and it has received little cryptanalytic scrutiny so far.

$$ 2^{18} $$

¹³ https://github.com/filecoin-project/paired

14 Our code is available at https://github.com/matteocam/lvc-mon-rust.

¹⁵ https://github.com/scipr-lab/libsnark

Our proving time has a steeper growth than that of the SNARKs. This is a direct consequence of the following: our proving consists of multiexponentiations roughly linear in the size of the vector; SNARKs over Merkle trees, on the other hand, are still Merkle tree openings and thus logarithmic in the vector size despite their larger hidden constants.

The diagram shows proving time for a single opening only. Our scheme performs better than MT+Poseidon 18 hashes for vectors of size up to 2, while we do better than Merkle Trees with SHA256 for vector of size up ²⁵ to 2.

$$ 2^{18} $$

$$ 2^{25} $$

7.2 Proving Time for Special Subsets

The results of this comparison are in Fig. 2. We compare the proving time of our subvector opening for a range of positions of Section 6.1 to range position opening through a SNARK (again Groth16) over Merkle trees with the Poseidon hash function. For the latter, we make use of the fact that a range opening in a Merkle tree can often be signicantly optimized by opening an \upper path" only once and then opening a whole subtree stemming from that upper path and corresponding to the whole range¹⁶.

Except for very small ranges, Merkle trees perform worse. The savings are of a few order of magnitudes even for moderately sized ranges. The reason for this is the virtually constant proving time in our range subset compared to the one for SNARKs which roughly grows linearly with it (our proving time actually decreases with the range size, but in the diagram we just consider the proving time for the most expensive case). We performed similar evaluations for dierent set sizes and nd little dierence in the patterns.

Fig. 2: Proving time for range queries in our scheme with monomial basis vs SNARKs for Merkle trees with Poseidon 20 in a vector of size 2. Plot is in log-scale.

$$ 2^{20} $$

7.3 Verication for Any Subsets

The results of this comparison are summarized in Fig. 3. We compare our verier for an aggregated subset opening in Section 6.2 with that in Pointproofs [15]. Our estimates indicate that our verier can be twice as fast as that in Pointproofs for appropriately large opening subsets. See Fig. 3. We describe the costs of

¹⁶ 8 20 Consider for example the opening of range 1*;:::;* 256 = 2 in a tree with 2 leaves. We can rst open the leftmost path of depth 12 (20 8) and then open the whole subtree of depth 8 stemming from there.

$$ 1,\ldots,256=2^{8} $$

$$ 2^{20} $$

Fig. 3: Verication cost for subset opening. Costs are independent of original vector size. Plot is in log-scale.

these verier reducing all other operations to their corresponding costs in jG₁j. For this we use the thorough conversions documented in [?, Table 2]. All our costs refer to an instantiation with BLS12-381. Cost of the Pointproofs verier opening a subset jIj:

$$ |G_{1}| $$

$$ 2\vert\mathsf{M L}\vert+\ 1\vert\mathsf{F E}\vert+\ 1\vert\mathsf{G_{1}}\vert+\vert I\vert\vert\left(\vert\mathbb{F}\vert+\ \vert\mathbb{G_{2}}\vert\right)+c\left(\vert\mathbb{G_{1}}\vert+\ \vert\mathbb{G_{T}}\vert\right)\vert $$

Cost of our verier in Section 6.2:

$$ 6|\mathsf{M L}|+2|\mathsf{F E}|+|I||\mathbb{F}|+c^{\prime}\left(|\mathbb{G}{1}|+|\mathbb{G}{2}|\right)| $$

Above ML and FE correspond respectively to Miller Loop and Final Exponentiation for the pairing. Field operations refer to multiplications. The constants c;c⁰ are small enough to be ignored in our gure. We 1 estimate the cost of a eld operation as approximately of a G₁ operation¹⁷. 8

$$ c,c^{\prime} $$

$$ \frac{1}{8} $$

$$ \mathbb{G}_{1} $$

Our construction has an initially higher cost which is soon compensated as the subset size increases. This is due to the more expensive G₂ operation that dominate in Pointproofs. Our verication achieves a speedup of approximately 16 in this cost model. The maximum subset size we show in the plot is also roughly the parameter at which the ratio between the two verication times converges, i.e., the multiplicative speedup of our construction does not increase for larger subsets.

$$ \mathbb{G}_{2} $$

We stress that our goal here is to give an indication of the fact that our approach can be useful. Concrete speedups would be highly dependent on the implementation of algebraic primitives and on the curve as well as other optimizations we have not considered in the analysis above.

Further Details on Evaluation

All the curve operations are instantiated over curve BLS12-381 [?]. Our timings for SNARKs over Merkle trees are (generous) lower bounds extrapolated from[?, Figure 5]. All our benchmarks refer to executions run single-threaded on Amazon EC2 using r5.8xlarge instances (248GB of memory).

¹⁷ A point addition in G₁ costs at least 4 eld multiplications and 5 squarings (cost of point doubling for Jacobian coordinates in short Weierstrass). With a squaring at 0*:* 8 eld multiplication we can approximate 8jFj 1jG₁j. https://www.hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html

$$ \mathbb{G}_{11} $$

$$ 8|\mathbb{F}|,\approx,1|\mathbb{G}_{1}| $$

8 Maintainable Vector Commitment Schemes

8.1 Multivariate Case

One of the key points of vector commitment schemes that allow to speedup subvector openings is the ability to pre-compute and store individual openings and later aggregate them to create subvector openings without incurring linear amount of computations each time.

In constructions such as the ones presented in Section 5, the proof of opening of one position involves all other elements in the vector. That is, the polynomials committed to create the proof have coecients that m involve all the values of the committed vector v 2 F. As a consequence, prover work is linear in the size of v (as it has to evaluate polynomials of degree m).

$$ \mathbf{v}\in\mathbb{F}^{m} $$

In this section, we present a solution for more ecient openings for individual positions that is maink tainable. The intuition is the following: we divide the vector v in small chunks fv_jg2 F. We then arrange these chunks in a tree as follows: each chunk corresponds to a leaf of the tree and each node is a succinct representation of its children. The root of the tree is the committed value. An opening proof only involves the elements in the path of the root to the leaf containing the position to be opened. That is, if we want to k m⁰ open value a in position i of v 2 F, we prove that (1) c_jis the leaf that contains the commitment to the j chunk containing i and (2) c_jopens to a in the position corresponding to i. The former part can be pre-computed and eciently maintained, with a storage cost linear in m⁰, while the latter involves operations that are linear in k.

$$ \big{\mathbf{v}_{j}\big}\in\mathbb{F}^{k} $$

$$ \mathbf{v}\in\mathbb{F}^{k\cdot m^{\prime}} $$

$$ c_{j} $$

$$ j $$

$$ c_{j} $$

$$ m^{\prime}, $$

This results in a construction with the following memory/time trade-o: for any k;m⁰ 2 N with m = k m⁰, any opening can be computed in time independent of m⁰ after pre-computing and storing O (m⁰) values (independent of k). Furthermore, a relaxed maintainability notion is satised: all stored values can be precomputed eciently (in quasi linear time in m) and updated in log m⁰ time.

$$ k,m^{\prime}\in\mathbb{N} $$

$$ m={\boldsymbol{k}}{\cdot}{!}{}m^{\prime}} $$

$$ m^{\prime} $$

$$ O_{\lambda}(m^{\prime}) $$

Our starting point is the PST polynomial commitment [5]. We rst show how to directly use its low degree variant (instead of the multilinear one used in [28]) to reduce proof size by a constant factor. Second, we modify this construction by composing it with any other algebraic¹⁸ vector commitment scheme to achieve maximum exibility in time/memory trade-os. We review the PST polynomial commitment and describe the core techniques to use it as a maintainable vector commitment in App. D.

Tree structure. We can directly exploit the tree structure of the PST commitment scheme to pre-compute all proofs in quasi-linear time and simply hand them when needed. While this can be benecial in some cases, it is an \extreme" approach. One might be willing to store some values and do some computation during opening of a position.

To achieve the exible memory/time trade-o, we exploit the same tree-like structure, but instead of having the vector values in the leaves of the tree, we replace them with vector commitments using an arbitrary k algebraic vector commitment scheme LVC. Concretely, the leaves contain elements [r]₁v_j, where [r]₁2 G₁ is the commitment key of LVC. To open a position of v, we use the PST approach to reach corresponding leaf j, and then the opening algorithm of VC on v_j. The tree part can be eciently pre-computed (memory resources) while the leaf part is opened on-demand (time resources).

$$ [\mathbf{r}]{1}\cdot\mathbf{v}{j} $$

$$ [\mathbf{r}]{1}\in\mathbb{G}{1}^{k} $$

$$ \mathbf{v}_{j} $$

We demonstrate the tree structure of our construction in app. D. For simplicity, we consider = f0*;* 1g as the interpolating set. Each node can be consider as a succinct representation of the vectors encoded in the leafs of the sub-tree having the node as a root.

$$ \Sigma = {0, 1 } $$

The tree has a similar structure to Verkle trees. Each node can be considered as a succinct \commitment" to its children and proving involves (in some sense) sending this \commitments" and evidence they are well formed. The dierence with Verkle trees is that the \commitment" does not satisfy a binding notion; indeed there are ecient ways to express each node in more than one ways by manipulating group elements.

Note that the root of the tree depends on the elements*;r. Viewing both = (;:::;₁) and r = (r_k;:::;r₁*) as formal variables X*;*R, we can treat the root node (the commitment) as an evaluation of a

$$ \boldsymbol{\tau}=,(\tau_{\nu},\ldots,\tau_{1}) $$

$$ (r_{k},\ldots,r_{1}) $$

$$ \tau,\mathbf{r}. $$

$$ \mathbf {r} = $$

¹⁸ We call algebraic, any (vector) commitment scheme where the commit algorithm works by simply setting [c]1 = [r]1 v, where [r]1 is the commitment key and v is the message to be committed.

$$ [\mathbf{r}]_{1}\cdot\mathbf{v}, $$

$$ [c]_{1}=,\, $$ polynomial. Now, note that this polynomial corresponds to the interpolation of the elements of the leaves in . Thus, the aforementioned polynomial is

$$ \Sigma^{\nu} $$

$$ p(\mathbf{X},\mathbf{R})=\mathbf{}(\mathbf{X})\cdot(\mathbf{R}\cdot\mathbf{v}{1},\ldots,\mathbf{R}\cdot\mathbf{v}{\ell^{\nu}})=(\mathbf{\lambda}(\mathbf{X})\otimes\mathbf{R})\cdot\mathbf{v}} $$

The prover can still evaluate one by one the variables X ;:::;X₁ at*;:::;₁-as it would do in the simple PST case- and end up with a polynomial q(R) = p(;*R) = R v_j. To ensure that q does not contain any X_jvariable, we also include a low degree test in the proof. The evaluation of the latter polynomial at [r]₁ corresponds to the leaf commitment at position and can be opened by employing the Open algorithm of the leaf commitment scheme with key [r]₁.

$$ X_{\nu},\ldots,X_{1} $$

$$ \sigma_{\nu},\ldots,\sigma_{1} $$

$$ q(\mathbf{R})=p(\boldsymbol{\sigma},\mathbf{R})=\mathbf{R}\cdot\mathbf{v}_{j} $$

$$ \sigma $$

$$ X_{j} $$

$$ [\mathbf{r}]_{1} $$

Construction. First, we introduce some notation. Let F denote the interpolating set. Given = i+1 k i (;:::;₁) 2, we denote_ji= (;:::;_i) 2. For v = (v)₂with v 2 F and₁2 we denote with v^{k; 1}the vector (v^{1; 2})²²ⁱ, that is, the concatenation of vectors v^jwhose m-ary representation of the index j is prexed with₁. Finally, we denote with_;‘the-variate monomial basis of individual degree less than evaluated at*;:::;*₁. In all cases, we omit the subscript when it is clear from the context.

$$ \Sigma\ \subseteq\ \mathbb{F} $$

$$ \sigma\ = $$

$$ \left(\sigma_{\nu},\ldots,\sigma_{1}\right)\in\varSigma^{\nu} $$

$$ \boldsymbol {\sigma} _ {| i} = \left(\sigma_ {\nu}, \dots , \sigma_ {i}\right) \in \Sigma^ {\nu - i + 1} $$

$$ \mathbf{v}=(\mathbf{v}{\sigma}){\mathbf\sigma\in\varSigma^{\nu}} $$

$$ \mathbf{v}_{\sigma}\in\mathbb{F}^{k} $$

$$ \boldsymbol {\sigma} _ {1} \in \Sigma^ {i} $$

$$ \mathbf{v}{k,\sigma{1}} $$

$$ \ \big(\mathbf{v}{\sigma{1},\sigma_{2}}\big){\sigma{2}\in\varSigma^{\nu-i}} $$

$$ \mathbf{v}_{j} $$

$$ j $$

$$ \sigma_{1} $$

$$ \tau_{\nu,\ell} $$

$$ \tau_{\nu},\ldots,\tau_{1} $$

We present the construction next. While our aim is individual position openings, the construction supports a bigger family of functions: linear forms¹⁹ applied to one of the k-sized chunks of the vector. Concretely, k let F_p;kf : F*!* F be the family of linear forms supported by the leaf commitment scheme. We dene the ‘;-extended family as

$$ \mathcal{F}_{p,k}\subseteq\left{f:\mathbb{F}^{k}\to\mathbb{F}\right} $$

$$ \begin{aligned}{{\sf E x t}{\ell,\nu^{\nu}}{\cal F}{p,k}={f:{\mathbb F}^{k\cdot\ell^{\nu}}}&{{}\to{\mathbb F}\mid\exists f^{\prime}\in{\cal F}{p,k},i\in{1,\ldots,\ell^{\nu}}\ \mathrm{}{s.t.}}\ {}&{{}\forall\mathbf{v}{1},\ldots,\mathbf{v}{\ell^{\nu}}\in{\mathbb F}^{k}:;f(\mathbf{v}{1},\ldots,\mathbf{v}{\ell^{\nu}})=f^{\prime}(\mathbf{v}{i})}}\ \end{aligned} $$

Our construction is a linear vector commitment MVTree for the family Ext_‘-F_p;k, that uses as a black box an algebraic linear vector commitment scheme LVC⁰ for the family F_p;k.

$$ \mathsf{E}{\times}\mathsf{t}{\ell^{\nu}}mathcal F{{}}{p,k} $$

$$ \mathcal{F}_{p,k} $$

MVTree*:* KeyGen(1*;Ext_‘-F_p;k)!* (prk*;vrk): 1.(prk⁰ = [r];vrk⁰) LVC⁰:* KeyGen(1*; F*

$$ \operatorname {K e y G e n} \left(1 ^ {\lambda}, \operatorname {E x t} _ {\ell^ {\nu}} - \mathcal {F} _ {p, k}\right) \rightarrow (\mathrm {p r k}, \mathrm {v r k}); $$

$$ \ .\ \ (\mathsf{p r k}^{\prime}=[\mathbf{r}]{1},\mathsf{v r k}^{\prime})\xleftarrow{}\mathsf{L V C}^{\prime}.\mathsf{K e y G e n}(1^{\lambda},\mathcal{F}{p,k}) $$

1 p;k 2.Let (X) be the vector of Lagrange polynomials associated to.

$$ \Sigma. $$

3.;:::;₁F

$$ \tau_{\nu},\ldots,\tau_{1}\leftarrow\mathbb{F} $$

4. Output prk = (prk'， $ [\boldsymbol{\lambda}]{1}=[\boldsymbol{\lambda}(\tau{\nu})\otimes \dots \otimes \boldsymbol{\lambda}(\tau_{1})\otimes \mathbf{r}]{1},[ \boldsymbol{\tau}\otimes \mathbf{r}]{1}),$ vrk = (vrk'， $ [\tau_{\nu}]{2},\ldots ,[ \tau{1}]{2},[ \tau{\nu}^{\ell-1}\cdots \tau_{1}^{\ell-1}]_{2}) $

$$ \operatorname{O u t p u t}\ \mathsf{p r k}=(\mathsf{p r k}^{\prime},[\mathbf{\lambda}]{1}=[\mathbf{\lambda}(\tau{\nu})\otimes\cdots\otimes\mathbf{\lambda}(\tau_{1})\otimes\mathbf{r}]{1},[\mathbf{\tau}\otimes\mathbf{r}]{1}), $$

$$ \mathsf{v r k}={\bf(}\mathsf{v r k}^{\prime},[\tau_{\nu}]{2},\ldots,[\tau{1}]{2},[\tau{\nu}^{\ell-1}\cdots\tau_{1}^{\ell-1}]_{2}) $$

$$ \mathsf{u p k}=({[\mathtt{\lambda}(\tau_{j})\otimes\cdots\otimes\mathtt{\lambda}(\tau_{1})\otimes\mathbf{r}]{1}}{j=\nu-1}^{1}), $$

MVTree*:* Commit(prk*;v)!* (C*;*aux):

$$ \mathrm {t} (\mathrm {p r k}, \mathbf {v}) \rightarrow (\mathrm {C}, \mathrm {a u x}) $$

1.For all 2 : compute (C;aux) LVC⁰: Commit(prk⁰*;* v)

$$ \sigma\in\Sigma^{\nu} $$

$$ (C_{\sigma},\mathsf{a u x}{\sigma})\leftarrow\mathsf{L V C}^{\prime}.\mathsf{C o m m i t}(\mathsf{p r k}^{\prime},\mathbf{v}{\sigma}) $$

2.Compute C = [p(*;*r)]₁= []₁v

$$ {\hat{\mathsf{C}}}=[p(\mathbf{\tau},\mathbf{r})]{1}=[\mathbf{\lambda}]{1}\cdot\mathbf{v} $$

3.Output C*;aux = faux g²;* v

$$ \mathrm {C}, \operatorname {a u x} = \left(\left{\operatorname {a u x} _ {\sigma} \right} _ {\sigma \in \Sigma^ {\nu}}, \mathbf {v}\right) $$

MVTree*:* Open(prk*;aux;f;* y)! :

$$ O p e n(p r k,a l X,f,y)\rightarrow\pi\vdots $$

1.Let f (v₁ ;:::; v ‘ ) = f⁰ (v i ) for f⁰ 2F p;k and i = ( ) ‘ in ‘ -ary.

1.Let f(v₁*;:::;*v_‘) = f⁰(v_i) for f⁰ 2F_p;kand i = ()_‘in ‘-ary.

$$ f^{\prime}\in\mathcal{F}_{p,k} $$

$$ \textstyle\ \ \ \ \ \ \ \ \ \ \\ \\ \ \ \ \ \ \ (\mathtt{v}{1},\ldots,\mathbf{v}{\ell})=\int^{\ 1} $$

$$ i=(\sigma)_{\ell} $$

2.Consider*;r as formal variables X = (X ;:::;X₁);R = (R_k;:::;R₁*).

$$ \mathbf{X}=(X_{\nu},\ldots,X_{1}),\mathbf{R}=(R_{k},\ldots,R_{1}) $$

3.Denote p₊₁(X*;R) = p(X;*R) = ( (X) R) v

$$ p_{\nu+1}(\mathbf{X},\mathbf{R})=p(\mathbf{X},\mathbf{R})=(\mathbf{\lambda}(\mathbf{X})\otimes\mathbf{R})\cdot\mathbf{v} $$

4.For all j 1:

$$ \nu\geq j\geq1; $$

$$ p_{j}(X_{j-1},\ldots,X_{1},\mathbf{R})=\lambda(X_{j-1},\ldots,X_{1},\mathbf{R})\cdot\mathbf{v}{\sigma{|j}} $$

Compute p^j(X^{j 1}*;:::;X₁;R) = (X_{j 1};:::;X₁;*R) v_jj

$$ H_{j}(X_{j},\ldots,X_{1},\ \ {bf R R}) $$

$$ H_{j}(X_{j},\ldots,X_{1},\mathbf{R})=\frac{p_{j+1}(X_{j},\ldots,X_{1},\mathbf{R})-p_{j}(X_{j-1},\ldots,X_{1},\mathbf{R})}{(X_{j}-\sigma_{j})} $$

Compute H_j(X_j*;:::;X₁;*R) as

Compute group element [H_j]₁= [H_j(_j;:::;₁*;*r)]₁

$$ [H_{j}]{1}=[H{j}(\tau_{j},\dots,\tau_{1},\mathbf{r})]_{1} $$

¹⁹ We use linear forms for simplicity, one could also consider general linear functions.

^ ‘ 1 ‘ 1 5.Compute C = [¹r]¹v 0 6.Compute LVC⁰*:* Open(prk⁰*;aux;f⁰*

$$ {\hat{\mathsf{C}}}{\sigma}=[\tau{\nu}^{\ell-1}\cdots\tau_{1}^{\ell-1}\cdot\mathbf{r}]{1}\cdot\mathbf{v}{\sigma} $$

$$ \operatorname{C o m p u t e}\ \pi^{\prime}\leftarrow\mathsf{L V C^{\prime}}.\mathsf{O p e n}(\mathsf{p r k^{\prime}},\mathsf{a u x}_{\sigma},f^{\prime},\mathbf{y}) $$

$$ \operatorname{O u t p u t}\ \pi=([H_{\nu}]{1},\ldots,[H{1}]{1},\mathsf{C}{\sigma},\mathsf{\hat{C}}_{\sigma},\pi^{\prime}) $$

MVTree*:* Vf(vrk*;* C*;f;y;)!* 0*=*1:

$$ \sf f(v r k,C,f,y,\pi)\rightarrow\ 0/1! $$

1.Let f(v₁*;:::;v‘) = f⁰(vi) for f⁰ 2Fp;kand i = ()‘in ‘-ary. P 2. b e(C C;[1]) = e([H];* [])

$$ f(\mathbf{v}{1},\ldots,\mathbf{v}{\ell^{\nu}})=f^{\prime}(\mathbf{v}{i})\ {}\ mathrm{{f o r}}\ f^{\prime}\in\mathcal{F}{p,k} $$

$$ i=(\sigma)_{\ell} $$

$$ btextstyle{{{\mathsf{P a t h}}}\ \leftarrow\ e(\mathsf{C}-\mathsf{C}{\sigma},[1]{2})=\sum{j=1}^{\nu}e([H_{j}]{1},[\tau{j}-\sigma_{j}]_{2}) $$

$$ bquad b_{\mathsf{L D-T e s t}}\leftarrow e(\mathsf{C}{\sigma},[\tau{\nu}^{\ell-1}\cdots\tau_{1}^{\ell-1}]{2})=e(\mathsf{\hat{C}}{\sigma},[1]_{2}) $$

$$ b _ {\mathrm {L e a f}} \leftarrow \mathrm {L V C} ^ {\prime}. \mathrm {V f} \left(\mathrm {v r k} ^ {\prime}, \mathrm {C} _ {\sigma}, f ^ {\prime}, \mathbf {y}, \pi^ {\prime}\right) $$

5.Output b_Path^ b_LD-Test^ b_Leaf

$$ \mathsf{p u t}\ b_{\mathsf{P a t h}}\wedge b_{\mathsf{L D-T e s t}}\wedge b_{\mathsf{L e a f}} $$

We omit explicitly describing the update algorithm. Instead, we demonstrate in Thm. 8 how to eciently update all proofs after modifying a position in the committed vector.

We summarize the properties of the construction in the following theorems.

Theorem 7. Let LVC⁰ be an algebraic vector commitment scheme that satises completeness, homomorphic openings and weak function binding for a function family F_p;k. Then, MVTree satises (1) completeness, (2) Homomorphic Openings and (3) strong function binding for Ext_‘-F_p;kin the AGM under the (‘ 1)*-*BSDH assumption.

$$ \mathcal{F}_{p,k} $$

$$ E\times t\ell\nu\ \mathcal{F}_{p,k} $$

Proof.

Completeness. Consider an honest execution of MVTree*:* Open. Let y = f(v) = f⁰(v_i) for some i = ()_‘. Also, by construction, the low degree test always succeeds. It remains to show that the rst test outputs 1.

Let p₊₁(*X ;:::;X₁;*R) = p(*X ;:::;X₁;*R) be the polynomial ( (X) R) v. Next, consider the polynomial equations that the polynomials H_jare constructed to satisfy:

$$ y = f (\mathbf {v}) = f ^ {\prime} \left(\mathbf {v} _ {i}\right) $$

$$ i=(\pm\sigma)_{\ell} $$

$$ p_{\nu+1}(X_{\nu},\ldots,X_{1},\mathbf{R})=p(X_{\nu},\ldots,X_{1},\mathbf{R}) $$

$$ (\lambda (\mathbf {X}) \otimes \mathbf {R}) ^ {\top} \mathbf {v} $$

$$ H_{j} $$

$$ p_{j+1}(X_{j},\ldots,X_{1},\mathbf{R})-p_{j}(X_{j-1},\ldots,X_{1},\mathbf{R})=H_{j}(X_{j},\ldots,X_{1},\mathbf{R})(X_{j}-h_{j}) $$

Summing all these equation for 1 j gives

$$ 1\leq j\leq\nu $$

$$ p_{\nu+1}(X_{\nu},\ldots,X_{1},\mathbf{R})-p_{1}=\sum_{j=1}^{\nu}H_{j}(X_{j},\ldots,X_{1},\mathbf{R})(X_{j}-h_{j}) $$

and note that this corresponds to the verication equation. Thus, the rst test passes. Finally, note that all the monomials involved these polynomials are included in the commitment key (;:::;₁) r, so the prover can encode these in G₁.

$$ \lambda(\tau_{\nu},\ldots,\tau_{1})\otimes\mathbf{r}. $$

$$ \mathbb{G}_{1} $$

Function Binding. First, we prove a claim stating that we can extract an opening of a leaf commitment in the AGM.

^ 0 Claim. Let = ([H]₁;:::;[H₁]₁; C*;* C*;*) be an accepting proof. Then, for all algebraic adversaries A outputting accepting proofs, there exists an extractor that outputs opening of C w.r.t. key r in the AGM.

$$ \pi=\left([H_{\nu}]{1},\ldots,[H{1}]{1},\mathsf{\hat{C}}{\sigma},\mathsf{\hat{C}}_{\sigma},\pi^{\prime}\right) $$

$$ \mathsf{C}_{\sigma}\mathrm{~w.r.t} $$

Proof. Since we work in the AGM, we can extract coecients a^;a of polynomials C^(X;R);C(X*;R) with degree less that ‘ 1 in X ;:::;X₁ such that [C^(;r)] = C^ and [C(;r)] = C. By the low degree 1 1 ^(X‘ 1 ‘ 1 ‘ 1 ‘ 1 test, either C;R) = C(X;R) X X₁ holds or a^ (;r) = a(;r)₁. holds and we nd a non-trivial discrete logarithm relations of the elements of the commitment key. Assume the latter event did not happen. For this polynomial relation to hold with polynomial of degree less that ‘ 1 in X ;:::;X₁, only the coecients involving R are non-zero, in which case we extract a leaf commitment opening. Now, either this holds or the adversary successfully computed a non-zero polynomial p(R;*X) = ^(X‘ 1 ‘ 1 *C;R) C(X;R) X X₁ that has a root in (;*r) which happens with negligible probability.

$$ \hat{C}(\mathbf{X},\mathbf{R}),C(\mathbf{X},\mathbf{R}) $$

$$ X_{\nu},\ldots,X_{1} $$

$$ [\hat{C}(\ \tau{,}\mathbf{r})]_{1};=;\hat{\mathsf{C}} $$

$$ [C(\tau{\bf},{\bf r})]_{1},=,{\sf C}} $$

$$ \hat{C}({\bf X},{\bf R}):=:C({\bf X},{\bf R}):\cdot:X_{\nu}^{\ell-1}\cdots X_{1}^{\ell-1} $$

$$ {\hat{\mathsf{a}}}\cdot\ \ (\tau{\ ,\mathrm{r}})={\mathsf{a}}(\tau,{\mathrm{r}})\cdot\tau_{\nu}^{\ell-1}\cdots\tau_{1}^{\ell-1} $$

$$ X_{\nu},\ldots,X_{1}. $$

$$ \ell-1 $$

$$ p(\mathbf{R},\mathbf{X}),= $$

$$ \hat{\mathcal{C}}(\mathtt{X},\mathtt{R})-\mathcal{C}(\mathtt{X},\mathtt{R})\cdot X_{\nu}^{\ell-1}\cdots X_{1}^{\ell-1} $$

Now, consider two opening/proof pairs C*;f*_d; y_d;_dfor d 2f1*;* 2g. Note the only way that the functions 0 0 are inconsistent is if f₁(v) = f₁(v_i) and f²(v) = f₂(v_i) for the same index i.

$$ \mathsf{C}{\sigma};,f{d},\mathbf{y}{d},\pi{d} $$

$$ d\in{1,2} $$

$$ f_{1}(\mathbf{v})=f_{1}^{\prime}(\mathbf{v}_{i}) $$

$$ f^{2}(\mathbf{v})=f_{2}^{\prime}(\mathbf{v}_{i}) $$

0 0 Let f₁(v) = f₁(v_i) and f₂(v) = f₂(v_i) for the same i = ()_‘. We consider two cases. First, assume that C₁_;= C₂_;= C. By the fact that the low-degree test passes, we can extract an opening v for this commitment except with negligible probability. Then, by the last verication test we have

$$ f_{1}(\mathbf{v}),=,f_{1}^{\prime}(\mathbf{v}_{i}) $$

$$ f_{2}(\mathbf{v}),=,f_{2}^{\prime}(\mathbf{v}_{i}) $$

$$ i=(\sigma)_{t} $$

$$ \mathcal{C}{1,\sigma}=\mathcal{C}{2,\sigma}=\mathcal{C}_{\sigma} $$

$$ \mathbf{v}_{\sigma} $$

$$ \mathsf{L V C}^{\prime}.\mathsf{V f}(\mathsf{v k}^{\prime},C_{\sigma},{f^{\prime}}{1},\mathbf{y}{1},\pi_{1}^{\prime}){\ =\ }v\mathsf{C}^{\prime}.\mathsf{V f}(\mathsf{v k}^{\prime},C_{\sigma},{f^{\prime}}{2},\mathbf{y}{2},\pi_{2}^{\prime}){\ =\ }1 $$

Noting that the openings for f⁰₁;f⁰₂are inconsistent if the openings for f₁;f₂ are inconsistent, we conclude that we have solved a strong function binding challenge for LVC⁰ Indeed, we have a commitment C with 1 2 a valid opening v that f⁰-opens to y¹ and f⁰-opens to y² for some inconsistent values since *f¹;*y₁ and *f²;*y₂ are inconsistent.

$$ f^{\prime}{}{1},f^{\prime}{}{2} $$

$$ f_{1},f_{2} $$

$$ \mathbf{y}^{1} $$

$$ C_{\sigma} $$

$$ f^{\prime2} $$

$$ \mathbf{v}_{\sigma} $$

$$ \mathbf{y}^{2} $$

$$ f^{2},\mathbf{y}_{2} $$

$$ f^{1},\mathbf{y}_{1} $$

Next, consider the case where C₁_;6= C₂_;. We show that, in this case, an winning adversary can be used (‘ 1) to break BSDH assumption. The reduction works as follows: on input [1]₁;₂; []_1;2;:::;[]_1;2, sample a key for MVTree in the following way:

$$ C_{1,\sigma}\neq C_{2,\sigma} $$

$$ [1]{1,2},[\tau]{1,2},\ldots,[\tau^{(\ell-1)\cdot\nu}]_{1,2} $$

$$ i=(\sigma)_{\ell} $$

{ Guess index i = ()_‘.

{ Sample (pk⁰ = [r]₁;vk⁰) LVC⁰: KeyGen(1*; F*_p;k) along with the discrete logarithms of [r]₁₂₀

$$ (\mathsf{p k}^{\prime}=[\mathbf{r}]{1},\mathsf{v k}^{\prime})\leftarrow\mathsf{L V C}^{\prime}.\mathsf{K e y G e n}(\ ^{\lambda},\mathcal{F}{p,k}) $$

$$ [ \mathbf {r} ] _ {1} ^ {2 0} $$

{ for all 1 j set [_j]₁= [_j+_j]₁for random_j.

$$ 1\leq j\leq\nu;\sec\ \big[\tau_{j}\big]{1}=\big[\rho{j}\tau+\sigma_{j}\big]_{1} $$

$$ \rho_{j} $$

{ Compute the encodings of the multivariate Lagrange and monomial polynomials [ (;:::;₁)]₁; []₁ ‘ 1 ‘ 1 and []₂;:::;[₁]₂; []₂. Note that this step is ecient since any element (₁;:::;) and in is a polynomial of total degree at most (‘ 1) on variablesj=jso it can be computed using the powers of.

$$ [\lambda(\tau_{\nu},\dots,\tau_{1})]{1},[\tau]{1} $$

$$ [\tau_{\nu}]{2},\dots,[\tau{1}]{2},[\tau{\nu}^{\ell-1}\cdot\tau_{\nu}^{\ell-1}]_{2} $$

$$ \lambda_{\sigma}(\tau_{1},\ldots,\tau_{\nu}) $$

$$ \tau $$

$$ (\ell-1)\cdot\nu $$

$$ \tau_{j}=\rho_{j}\tau $$

$$ \tau $$

{ Compute the proving commitment key by computing r [ (;:::;₁)]₁.

$$ \mathbf{r}\otimes[\lambda(\tau_{\nu},\ldots,\tau_{1})]_{1} $$

First, we argue that the commitment key is correctly distributed. Indeed, we evaluate the multivariate Lagrange and monomial polynomials on a random point since*; ;:::;*₁are uniformly distributed, and we compute r honestly.

$$ \tau,\rho_{\nu},\ldots,\rho_{1} $$

Next, assume that the guess of index i was correct (which happens with 1*=‘* = m=k probability) and that the verifying proofs contain C₁_;6= C₂_;. By the fact that the low-degree test passes, we get two valid openings v₁*;*;v₂_;for these commitments w.r.t. the key [r]₁. Since we know r in the eld, we can compute the discrete logarithms of these elements: specically,

$$ 1/\ell^{\nu}=m/k $$

$$ C_{1,\sigma}\neq C_{2,\sigma} $$

$$ \mathbf{v}{1,\sigma},\mathbf{v}{2,\sigma} $$

$$ [\mathbf{r}]_{1} $$

$$ \left(\mathcal{C}{1,\sigma},\mathcal{C}{2,\sigma}\right)=\left\langle\mathbf{\check{r}}^{\top}\mathbf{check{v}}{1,\sigma},\mathbf{\check{r}}^{\top}\mathbf{\check{v}}{2,\sigma}\right\rangle $$

To simplify notation, denote these values v;v⁰ 2 F respectively and note that v 6= v⁰.

$$ v,v^{\prime}\in\mathbb{F} $$

$$ v\neq v^{\prime}. $$

By the rst vericatioon test, the following equations holds:

$$ e([C-v]{1},[1]{2})=\sum_{j=1}^{\nu}e([H_{j}]{1},[\tau{j}-\sigma_{j}]{2}),e([C-v^{\prime}]{1},[1]{2})=\sum{j=1}^{\nu}e([H_{j}^{\prime}]{1},[\tau{j}-\sigma_{j}]_{2}) $$

Subtracting and setting z_j= H_iH_i0gives

$$ z_{j}=H_{i}-H_{i}^{\prime} $$

$$ e([v^{\prime}-v]{1},[1]{2})=\sum_{j=1}^{\nu}e([z_{j}]{1},[\tau{j}-\sigma_{j}]{2})\Leftrightarrow e([v^{\prime}-v]{1},[1]{2})=\sum{j=1}^{\nu}e([z_{j}]{1},\rho{j}[\tau]_{2})\Leftrightarrow $$

$$ (v^{\prime}-v)\cdot e([1]{1},[1]{2})=\tau\cdot e\left(\sum_{j=1}^{\nu}\rho_{j}[z_{j}]{1},[1]{2}\right)\Leftrightarrow $$

$$ \tau^{-1}\cdot e([1]{1},[1]{2})=(v^{\prime}-v)^{-1}\cdot e\left(\sum_{j=1}^{\nu}\rho_{j}[z_{j}]{1},[1]{2}\right)\Leftrightarrow $$

$$ e([\tau^{-1}]{1},[1]{2})=\cdot e\left((v^{\prime}-v)^{-1}\sum_{j=1}^{\nu}\rho_{j}[z_{j}]{1},[1]{2}\right) $$

²⁰ We implicitly assume here that the distribution of the key generation algorithm is witness samplable. This is always the case for all distribution of interest.

so by the nal equation

$$ \frac{1}{\tau^{-1}}e([1]{1},[1]{1})=(v^{\prime}-v)^{-1}\sum_{j=1}^{\nu}\rho_{j}[z_{j}]_{1} $$

P 0 1 Therefore, ⁰; (v v) e(j_{=1 j}[z_j]₁;[1]₂) is a solution to the BSDH challenge.

$$ \Big(0,(v^{\prime}-v)^{-1}e(\textstyle\sum_{j=1}^{\nu}\rho_{j}[z_{j}]{1},[1]{2})\Big) $$

Homomorphic Proofs. Let (C₁*;f;* y₁*;₁), (C₂;f;* y₂*;₂) be accepting statement-proof pairs with respect to some key vk. We show that for all; 2* F, the statement-proof pair (C*;f;y;) = ( C₁ + C₂;f;y₁ + y₂;*₁+₂) is also accepting. Let

$$ \alpha,\beta\in\mathbb{F} $$

$$ \beta\mathbf{y}{2},\alpha\pi{1}+\beta\pi_{2}) $$

$$ \begin{aligned}{{\pi}=({\alpha}[H_{\nu,1}]{1}+{\beta}[H{\nu,2}]{1},}&{{}\dots,{\alpha}[H{1,1}]{1}+{\beta}[H{1,2}]{1},}\ {}&{{}{\alpha}\mathsf{C}{1,\sigma}+{\beta}\mathsf{C}{2,\sigma},{\alpha}\mathsf{\hat{C}}{1,\sigma}+{\beta}\mathsf{\hat{C}}{2,\sigma},{\alpha}{\pi}{1}^{\prime}+{\beta}{\pi}_{2}^{\prime})}\ \end{aligned} $$

be the combined proof. First, note that for the function f⁰ and 2 corresponding to f, the second 0 0 verication test LVC⁰*:* Vf(vk⁰*;C₁_;+ C₂_;;f⁰;y₁+ y₂;*₁+₂) outputs 1 by the homomorphic openings property of LVC⁰. For the rst test, we have

$$ \sigma,\in,\Sigma^{\nu} $$

$$ f, $$

$$ \mathsf{L V C}^{\prime}.\mathsf{V f}(\mathsf{v k}^{\prime},\alpha\mathsf{C}{1,\sigma}{+}\beta\mathsf{C}{2,\sigma},f^{\prime},\alpha\mathbf{y}{1}+\beta\mathbf{y}{2},\alpha\pi_{1}^{\prime}{+}\beta\pi_{2}^{\prime}) $$

$$ \begin{aligned}{e(\mathsf{C}-\mathsf{C}{\sigma},[1]{2})}&{{}=e(\alpha\mathsf{C}{1}+\beta\mathsf{C}{2}-\alpha\mathsf{C}{1,\sigma}-\beta\mathsf{C}{2,\sigma},[1]{2})}\ {}&{{}=\alpha\cdot e(\mathsf{C}{1}-\mathsf{C}{1,\sigma},[1]{2})+\beta\cdot e(\mathsf{C}{2}-\mathsf{C}{2,\sigma},[1]{2})}\ {}&{{}=\alpha\sum{j=1}^{\nu}e([H_{j,1}]{1},[\tau{j}-\sigma_{j}]{2})+\beta\sum{j=1}^{\nu}e([H_{j,2}]{1},[\tau{j}-\sigma_{j}]{2})}\ {}&{{}=\sum{j=1}^{\nu}e(\alpha[H_{j,1}]{1}+\beta[H{j,2}]{1},[\tau{j}-\sigma_{j}]{2})=\sum{j=1}^{\nu}e([H_{j}]{1},[\tau{j}-\sigma_{j}]_{2})}\ \end{aligned} $$

Similarly, for the low degree test we have

$$ \begin{array}{l} e \left(\hat {\mathrm {C}} _ {\sigma}, [ 1 ] _ {2}\right) = e \left(\alpha \hat {\mathrm {C}} _ {1, \sigma} + \beta \hat {\mathrm {C}} _ {2, \sigma}, [ 1 ] _ {2}\right) = \alpha \cdot e \left(\hat {\mathrm {C}} _ {1, \sigma}, [ 1 ] _ {2}\right) + \beta \cdot e \left(\hat {\mathrm {C}} _ {2, \sigma}, [ 1 ] _ {2}\right) \ = \alpha \cdot e \left(\mathrm {C} _ {1, \sigma}, \left[ \tau_ {\nu} ^ {\ell - 1} \dots \tau_ {1} ^ {\ell - 1} \right] _ {2}\right) + \beta \cdot e \left(\mathrm {C} _ {2, \sigma}, \left[ \tau_ {\nu} ^ {\ell - 1} \dots \tau_ {1} ^ {\ell - 1} \right] _ {2}\right) \ = e \left(\alpha C _ {1, \sigma} + \beta C _ {2, \sigma}, \left[ \tau_ {\nu} ^ {\ell - 1} \dots \tau_ {1} ^ {\ell - 1} \right] _ {2}\right) = e \left(C _ {\sigma}, \left[ \tau_ {\nu} ^ {\ell - 1} \dots \tau_ {1} ^ {\ell - 1} \right] _ {2}\right) \ \end{array} $$

Thus, the new statement/proof pair passes all verication tests.

Remark 3. Note that in the function binding proof, we only use the AGM to extract openings for the leaf commitments but not for the tree part of the construction. The latter is sound under falsiable assumptions.

^ 0 Theorem 8. Consider construction MVTree and let = ([H]₁;:::;[H₁]₁; C*;* C;) be some proof of opening for a leaf commitment in position written in ‘-ary. n o Then, computing all partial proofs ([H];:::;[H₁]; C*;* C^) can be done in O (k ‘) = O ( m) 2 1 2 time and storing them needs O (‘) = O (m=k) space. Furthermore, if we update C by adding in some position i , we can update all partial proofs in time O ().

$$ \pi^{\sigma}{\ =\ }([H_{\nu}^{\sigma}]{1},\ldots,[H{1}^{\sigma}]{1},\mathsf{C}{\sigma},\dot{\mathsf{C}}{\sigma},\pi{\sigma}^{\prime}) $$

$$ \sigma $$

$$ \Big{([H_{\nu}^{\sigma}]{2},\dots,[H{1}^{\sigma}]{1},\mathsf{C}{\sigma},\hat{\mathsf{C}}{\sigma})\Big}{\sigma\in\varSigma^{\nu}} $$

$$ \ {mathcal O_{{lambdalambda}}}\ k{\cdot}\nu{\cdot}\ell^{{\nu}}\big)={\mathcal{O}_{{\lambda}}}\big(\nu{\cdot}m\big) $$

$$ O_{\lambda}(\ell^{\nu})=O_{\lambda}(m/k) $$

$$ i^{*} $$

$$ \delta $$

$$ i f $$

$$ O_{\lambda}(\nu) $$

Proof.

Pre-computing partial proofs. Let p(X ;:::;X₁;R) be the polynomial encoding of v w.r.t. and consider the evaluation of polynomials p₁(X;R) = p(₁; X*;R) arranged in a tree: the root is the polynomial p(X ;:::;X₁;R) and the children of a node in level j are p^;:::;j(;X^{j 2};:::;X₁;*R). Computing all 2 proofs corresponds to computing a divisor polynomial for each node that asserts that the node is consistent with its parent node, plus some constant work for computing each leaf commitment along with its low degree proof. Assuming ‘ = O(1), each divisor polynomial proof can be computed in time linear in the total degree of p_;:::;j. A simple counting argument is enough to conclude the proof. In level j of the tree, we need to

$$ p(X_{\nu},\ldots,X_{1},\mathbf{R}) $$

$$ \mathbf {v} \mathrm {w . r . t .} \Sigma^ {\nu} $$

$$ p(X_{\nu},\ldots,X_{1},\mathbf{R}) $$

$$ p_{\sigma_{1}}(\mathtt{X}\mathttmathtt{,}mathttmathtt R R),=,p(\sigma_{1},\mathtt{X},\mathtt{R}) $$

$$ \left{p_{\sigma_{\nu},\ldots,\sigma_{j}}(\sigma,X_{j-2},\ldots,X_{1},\mathrm{R})\right}_{\sigma\in\mathrm{Y}} $$

$$ \ell=O(1) $$

$$ p_{\sigma_{\nu},...,\sigma_{j}} $$

$$ j $$ j j compute ‘ proofs, each for a polynomial of total degree k ‘. Thus, for each level of the tree, we need time linear in k ‘ = m. Having levels, the total time is O (m). For the space requirements, it is enough to note that the tree is has O(m) nodes, and we associate one group element to each.

$$ \ell^{\nu-j} $$

$$ \ell^{j} $$

$$ k\cdot\ell^{\nu}=m $$

$$ O_{\lambda}(m!\cdot!\nu!) $$

$$ O(m) $$

Updating all partial proofs. The updatability property follows directly by the homomorphic opening property of the construction. We focus on the computation needed for updating all stored proofs. The strategy is to consider the new commitment as C⁰ = C + C^ where C^ is a commitment to the vector e, where denotes i leaf corresponding to i. We claim that (1) we can compute all proofs for C^ in logarithmic time and (2) all but O() proof elements are 0. By this two facts the claim follows since we can combine all the non-zero proof elements of C^ with the corresponding elements of C.

$$ C ^ {\prime} = C + \hat {C} $$

$$ \sigma $$

$$ \delta\cdot\mathbf{e}_{i^{*}} $$

$$ i^{*} $$

$$ \hat{C} $$

$$ O(\nu) $$

$$ \hat{C} $$

The commitment C^ corresponds to a polynomial of the form p(X*;*R) = (X) R. All polynomials j labeling nodes in the tree are 0 apart from the ones being in the path from the root to the leaf containing i. Such a node always has the zero polynomial nodes as descendants, and the proof corresponding to each is 0 since 0 = 0 (X_{j j}). The proof polynomials for the rest ‘ nodes can be computed in constant time each and each can be encoded to the group in constant time since each involves a unique commitment key element. ut

$$ p(\mathbb{X},\mathbb{R})=\delta\cdot\lambda_{\sigma}(\mathbb{X})\cdot R_{}} $$

$$ i^{*} $$

$$ 0=0\cdot\left(X_{j}-\sigma_{j}\right) $$

8.2 Eciency of the Multivariate Construction

Eciency. We only consider the case where ‘ = O(1). First, let’s focus on the time needed to compute 1 [H^j]¹. One can simply write the polynomial p^jp^{j 1}as a polynomial in 1*;X*^j;:::;X^j‘with polynomial coecients in the other variables. Then, we can use standard (univariate) polynomial division to divide each term with X_{j j}in constant time. To encode it in the group, it is enough to note that the total degree of j 1 j each term is k ‘, so we need to perform ‘ multi-exponentiations of this size totaling in O(k ‘) operations.

$$ \ell=O(1) $$

$$ [H_{j}]. $$

$$ p_{j}-p_{j-1} $$

$$ 1,X_{j},\ldots,X_{j}^{\ell-1} $$

$$ X_{j}-\sigma_{j} $$

$$ k\cdot\ell^{j-1} $$

$$ O!(k!\cdot!\ell^{j}) $$

That said, we demonstrate the eciency of the construction. The commitment key consists of linear j in m group elements. Opening needs O(k ‘) operations for each iteration, totaling in O(k ‘) time. By 0 0 inspection of the construction, proofs size is log_‘(m=k) + 2 + j j, where is the size of an opening of the leaf commitment. Finally, verication consists of (1) a log_‘(m=k)-size pairing product equation, (2) a low degree test involving constant operations and (3) a verication of an opening of a leaf commitment.

$$ O(k\cdot\ell^{j}) $$

$$ O(k\cdot\ell^{\nu}) $$

$$ \log_{\ell}(m/k)+2+|\pi^{\prime}| $$

$$ \pi^{\prime} $$

$$ \ \mathrm{g}_{\ell}(m/k) $$

Remark 4(On aggregation). The rst two verication tests are pairing product equations. Assuming the leaf commitment verication is also a pairing product equation, one can use inner pairing products [5] to aggregate many such equations as done in [28] and, thus, achieve one-hop cross commitment aggregation. While the aggregated proof size decreases exponentially, this comes at the cost of a signicant overhead for the prover due to the need to work in the target group. Reducing the proof size from log₂ m to roughly log_‘(m=k) (assuming constant size/verication for leaf commitment opening) can make aggregation signicantly cheaper for the prover.

$$ \log_{\ell}(m/k) $$

8.3 Univariate Maintainable Vector Commitments

In this section, we give an optimized construction that achieves the same memory-time tradeos for the prover that the scheme in Section 8.1, but for univariate polynomials with the same variable at each level. For that, we rely on the q-BSDH assumption for q = m 1, while we only needed q = O(logm) for the multivariate case. On the other hand, this construction is limited to binary trees since it leverages the fact that the cardinal of the set of roots of unity is a power of 2.

$$ q=m-1 $$

$$ q\mathrm{B S D H} $$

$$ q={(}O(\log m) $$

• +1 For vectors of size m, we oer the following trade-o: for any*;, such that m = 2, one can derive openings of size +4 group elements. The prover can pre-compute and store 2 1 proofs, and then compute proofs by performing O( 2) group operations. We show also how to compute all proofs with O(m) group operations (plus O(m( +)) eld operations). The proofs are maintainable, as an update in a position requires recomputing O() proofs. One interesting feature is that the trusted setup depends only on m (the powers of) and not of;*, so rhe right tradeo can be decided on the y.

$$ m=2^{\nu+\kappa+1} $$

$$ \nu,\kappa, $$

$$ O(\kappa2^{\kappa}) $$

$$ 2^{\nu}-1 $$

$$ O(\nu m) $$

$$ O(m(\nu+\kappa), $$

$$ O(\nu) $$

$$ \tau) $$

$$ \nu,\kappa, $$

Notation and some facts about roots of unity. Before we explain how to arrange the proofs in a tree, we

• +1 recall some preliminaries about roots of unity. Throughout this section, m = 2 and H F is a set of roots of unity of size m. Elements of H will be indexed as powers of some xed primitive mth root of unity !.

$$ m=2^{\nu+\kappa+1} $$

$$ \mathbb{H}\subset\mathbb{F} $$

$$ m $$

mi i 2 2 2 It will be convenient to remember that the set of roots of unity of size r =ⁱis H_r= f1*;!;* (!);:::; ^{2 i} 2 r _{1 r} (!) g and the associated vanishing polynomial is X 1. Fu_rther, for any i, 0 i + + 1, H can i i s s s+2 s+(r 1)2 i be divided into cosets of Hrof the form! Hr= f!;!;:::;! g, for 0 s < 2. The vanishing s r s r polynomial associated to*!* H_ri^s X (!).

$$ r=\frac{m}{2^{i}} $$

$$ \mathbb{H}_{r}={1,\omega^{2^{i}},(\omega^{2^{i}})^{2},\ldots $$

$$ (\omega^{2^{i}})^{r-1}) $$

$$ X^{r}-1 $$

$$ i,\ 0\leq i\leq\nu+\kappa+1 $$

$$ \mathbb{H}_{r} $$

$$ \boldsymbol{\omega}^{s}\mathbb{H}_{r}=\left{\boldsymbol{\omega}^{s},\boldsymbol{\omega}^{s+2^{i}},\ldots,\boldsymbol{\omega}^{s+(r-1)2^{i}}\right} $$

$$ \omega^{s}\mathbb{H}_{}} $$

$$ 0\leq s<2^{i} $$

$$ X^{r}-(\omega^{s})^{r} $$

m High Level Description. Consider a tree of commitments to a vector v 2 F build as follows. The root of the tree is a commitment C = []₁v, where = ([₁()]₁;:::;[_m()]₁), and the polynomials f_j(X)g are the Lagrange basis interpolation polynomials for H. The two children will be C₀ = [₀]₁v₀ and C₁ = [₁]₁v₁, which are commitments to v₀ and v₁ with keys₀and₁of half the size. The two children of C₀ will be +1 C₀₀ = [₁₀]₁v₁₀*;C₁₀ = [₁₀]₁v₁₀ and so on. The leaves are commitments C_b, b = (b ;:::;b₀) 2f0;* 1g to vectors of size 2. For any leaf index b = (b ;:::;b₀), we denote b_jj= (b_j:::b₀) the sux²¹ of size j. Note that C_bjjfor j = 0*;:::;* 1 denotes all the commitments from the root to the leaf C_b.

$$ \mathbf{v}\in\mathbb{F}^{m} $$

$$ \mathsf{C}=[\lambda]_{1}\mathbf{v}. $$

$$ \lambda=\big([\lambda_{1}(\tau)]{1},\ldots,[\lambda{m}(\tau)]_{1}\big) $$

$$ {\lambda_{j}(X)} $$

$$ \mathbf{v}_{0} $$

$$ \mathsf{C}{0}=[\lambda{0}]{1}\mathbf{v}{0} $$

$$ \mathsf{C}{1}=[\lambda{1}]{1}\mathbf{v}{1} $$

$$ \mathbf{v}_{1} $$

$$ \lambda_{0} $$

$$ C_{0} $$

$$ \lambda_{1} $$

$$ {\mathsf{\hat{G}}}{\mathsf{b}},{\mathsf{b}}=\left(b{\nu},\ldots,b_{0}\right)\in{0,1}^{\nu+1} $$

$$ 2^{\kappa} $$

$$ \mathbf{b}=(left\ b_{\nu},\ldots,b_{0}) $$

$$ \mathbf{b}{|mid j}=(b{j}\ldots b_{0}) $$

$$ C_{\mathbf{b}} $$

$$ \mathbb{C}{\mathbf{b}{|mid j}} $$

$$ \mathrm{h r x}^{21} $$

$$ j=0,\ldots,\nu-1 $$

The division into vectors of half the size is done according to the least signicant bit of the binary representation of the index, b₀. At the rst level, there will be two vectors v₀*;*v₁ of size *m=2 containing all positions of v with sux b₀. At the next level, there will be four vectors v₀₀;v₀₁;v₁₀;*v₁₁ of size *m=*4, and v_{b1 b0}indicates all the positions of v (in the natural order) that have as sux b₁b₀ and so on.

$$ b_{0} $$

$$ \mathbf{v}{0},\mathbf{v}{1} $$

$$ m/2 $$

$$ b_{0} $$

$$ \mathbf{v}{01},\mathbf{v}{10},\mathbf{v}_{11} $$

$$ m/4 $$

$$ \mathbf{v}{b{1}b_{0}} $$

$$ b_{1}b_{0} $$

The division into commitment keys of half the size will follow a similar pattern. At level 1, roots of unity will be split into H⁰ and H¹, according to the least signicant bit of the binary representation of the index of the root, i.e. H⁰ consists of all even and H¹ all odd powers of*!. In particular, H⁰ are the roots of unity of size m=2, and H⁰ =!H¹. At level 2, the commitment keys will be associated to H⁰⁰; H⁰¹;* H¹⁰*;H¹¹ and 2 3 by the same reasoning, H⁰⁰ are the roots of unity of size m=4, H¹⁰ =! H⁰⁰;* H⁰¹ =!H⁰⁰ and H¹¹ =! H⁰⁰. j+1 bjjs More generally, we note that for any 0 j and any string (b_j;:::;b₀) 2f0*;* 1g, H =! H_r, for Pj i m s =_i=0b_i2 and r =_j+1. ₂

$$ \mathbb{H}^{0} $$

$$ \mathbb{H}^{0} $$

$$ \mathbb{H}^{1} $$

$$ \omega,, $$

$$ \mathbb{H}^{1} $$

$$ \mathbb{H}^{0} $$

$$ m/2 $$

$$ \mathbb{H}^{0}=\omega\mathbb{H}^{1} $$

$$ \mathbb{H}^{00},,\mathbb{H}^{01},,\mathbb{H}^{10},\mathbb{H}^{11} $$

$$ \mathbb{H}^{00} $$

$$ m\mathord/4,\mathbb{H}^{10}=\omega^{2}\mathbb{H}^{00},\mathbb{H}^{11}=\omega\mathbb{H}^{10} $$

$$ \mathbb{H}^{11}=\omega^{3}\mathbb{H}^{00} $$

$$ 0,\leq j\,\ \leq\nu $$

$$ (b_{j},\ldots,b_{0})\in{0,1}^{j+1} $$

$$ \mathbb{H}^{\mathbf{b}{|mid}!j},=,\omega^{s}\mathbb{H}{r} $$

$$ s=\sum_{i=0}^{j}b_{i}2^{i} $$

$$ r=\frac{m}{2^{j+1}} $$

bjj The Lagrange basis polynomials associated to the interpolation set H with the natural order is b bjjbjjb ^{b jj}(X) = ( (X);:::; (X)) and the commitment key for node ^b is^jj= [^jj()] . The vanishing 1 r jj 1 bjj polynomial associated to H will ^be denoted t_bjj(X).

$$ \mathbb{H}^{\mathbf{b}_{|mid j}} $$

$$ \lambda^{\mathsf{b}{|j}}(X)=(big(\lambda{1}^{\mathsf{b}{|j}}(X),\ldots,\lambda{r}^{\mathsf{b}_{|j}}(X)\big) $$

$$ \mathbf{b}_{|j} $$

$$ \lambda^{\mathbf{b}{|j}}=[\lambda^{\mathbf{b}{|j}}(\tau)] $$

$$ t_{\mathbf{b}_{|j}}(X) $$

$$ \mathbb{H}^{\mathbf{b}_{|mid j}} $$

As in the multivariate case, the idea is to open the root commitment to a leaf, and then open the commitment to the leaf using the IP argument for the Lagrange basis of Section 5 or the construction of b H Tomescu et al. [29]. Since at the leaf level the commitment is w.r.t to the key for some b, we need to argue that these constructions work for cosets of roots of unity (and with the same eciency). We prove this in App. D.3.

$$ \mathrm{I P} $$

The construction leverages the fact that vanishing and Lagrange polynomials corresponding to cosets of roots of unity are sparse, so we minimize precomputation, storage and verier work. More in detail, because of the way subsets are chosen, there is a simple relation between the parent and the children nodes. As an b illustration, observe that if c(X) = (X)v, c_b(X) = (X)v^b,

$$ c(X)=\frac{1}{2}\left(c_{0}(X)t_{1}(X)-c_{1}(X)t_{0}(X)\right). $$

(1)

Indeed, observe that evaluating at H⁰, the second term in the right hand side disappears, while t₁() = 2 for any 2 H⁰, so both sides take the same value at H₀, and similarly for H₁. Given that the polynomials

$$ \mathbb{H}^{0} $$

$$ \eta\in\mathbb{H}^{0} $$

$$ t_{1}(\eta),=,2 $$

$$ \mathbb{H}_{0} $$

$$ \mathbb{H}_{1} $$

²¹ Note that this notation is dierent than the one we used in the multivariate case. In the latter case, this notation denoted prexes while here it denotes suxes. We do this because in each case the corresponding notation makes presentation easier.

in both sides have the same degree, they are equal. Further, we can rewrite equation (1) as:

$$ \begin{aligned}{c(X)=}&{{}\frac{c_{0}(X)-c_{1}(X)}{2}X^{\frac{m}{2}}+\frac{c_{0}(X)+c_{1}(X)}{2}=}\ {=}&{{}\frac{c_{0}(X)-c_{1}(X)}{2}t_{0}(X)+c_{0}(X)=\frac{c_{0}(X)-c_{1}(X)}{2}t_{1}(X)+c_{1}(X)}\ \end{aligned} $$

Pj i m (i=0bi2 )j+2 Evaluating at gives a relation between C*;C₀;C₁. More generally, if K_{b :::b}= 2!2, the following j 0 relations hold for any j = 0;:::;*:

$$ \mathsf{C},\mathsf{C}{0},\mathsf{C}{1} $$

$$ K_{b_{j}\ldots b_{0}}=2\omega^{(\sum_{i=0}^{j}b_{i}2^{i})\frac{m{}2{^j22}} $$

$$ \mathsf{C}{\mathbf{b}{|j}}=K_{\mathbf{b}{|j}}\left(\mathsf{C}{0\mathbf{b}{|j}}[t{1\mathbf{b}{|j}}(\tau)]{1}-\mathsf{C}{1\mathbf{b}{|j}}[t_{0\mathbf{b}{|j}}(\tau)]{1}\right) $$

$$ j=0,\ldots,\nu: $$

(2)

$$ =K_{{\ {\mathsf{b}}}{|j}}\big({\mathsf{C}}{0{\mathsf{b}}{|j}}-{\mathsf{C}}{1{\mathsf{b}}{|j}}\big)\tau^{\frac{m}{2^{j+1}}}+K{{\mathsf{b}}{|j}}\big({\mathsf{C}}{0{\mathsf{b}}{|j}}+{\mathsf{C}}{1{\mathsf{b}}_{|j}}\big) $$

$$ =K_{\mathbf{b}{|j}}(\mathsf{C}{\mathbf{0}\mathbf{b}{|j}}-\mathsf{C}{\mathbf{1}\mathbf{b}{|j}})[t{\mathbf{1}\mathbf{b}{|j}}(\tau)]{1}+\mathsf{C}{\mathbf{1}\mathbf{b}{|j}} $$

)(3)

(4)

$$ =K_{\mathbf{b}{|j}}(\mathsf{C}{0\mathbf{b}{|j}}-\mathsf{C}{1\mathbf{b}{|j}})[t{0\mathbf{b}{|j}}(\tau)]{\mathbf{1}}+\mathsf{C}{0\mathbf{b}{|j}}. $$

(5)

Equation (2) generalizes the previous examples and gives the basic relation between the parent and the children nodes. The other equations come from rearranging the expression. Expression (3) will be useful to argue how to compute all commitments in the tree eciently from bottom to top.

To open C to a certain leaf commitment C_b, the idea is to implicitly show from root to leaf that C_bjj bjj+1 C^bjj+1agree in H. This is proven by showing that their dierence is divisible by t^{(1 bj+1)b}(X). Equations jj (4,5) give the exact expression for the quotient, i.e. it shows that, dening H_bjj= K^bjj(C^0b_jjC_1bjj), one can write C_bjjC_bjj+1= [H_bjjt_bjj+1()]₁. If H = (C₀ C₁)=2, going iteratively from the root replacing the commitments in the path of the leaf one gets:

$$ C_{\mathbf{b}} $$

$$ \mathsf{C}{\mathbf{b}{|j}}- $$

$$ \mathbb{H}^{\mathbf{b}_{|j j+1}} $$

$$ \mathsf{C}{\mathbf{b}{|mid j+1}} $$

$$ t_{(1-b_{j+1})\mathbf{b}_{|j}}(X) $$

$$ (4,5) $$

$$ H _ {\mathbf {b} _ {| j}} = K _ {\mathbf {b} _ {| j}} \left(\mathrm {C} _ {0 \mathbf {b} _ {| j}} - \mathrm {C} _ {1 \mathbf {b} _ {| j}}\right) $$

$$ \mathsf{C}{\mathbf{b}{|j}}-\mathsf{C}{\mathbf{b}{|j+1}}=\left[H_{\mathbf{b}{|j}}t{\mathbf{b}_{|j+1}}(\tau)\right] $$

$$ H=(big mathsf{C}{0}-\mathsf{C}{1}\big)/2 $$

$$ C(X)=H t_{b_{0}}(X)+\mathsf{C}{b{0}}=H\cdot t_{b_{0}}(X)+H_{b_{0}}\cdot t_{b_{1}b_{0}}(X)+\mathsf{C}{b{0}b_{1}}=\ldots $$

(6)

$$ = H t _ {b _ {0}} (X) + \sum_ {i = 0} ^ {\nu} H _ {\mathbf {b} _ {| j}} \cdot t _ {\mathbf {b} _ {| j + 1}} (X) + C _ {\mathbf {b}}. $$

(7)

To open C = [C()]₁to C_b, the prover will send the verier commitments to the H(X)s polynomials in this expression. For soundness, the general idea is that if we think of C*;* C_bas polynomials evaluated at, they b must agree on the set H since all the other terms in the expression evaluate to 0 in this coset. Note that the \tree opening" does not guarantee that the prover can construct a single C_bthat veries the proof (in fact, it is easy to randomize the values). However, the proof together with the inner product opening (or a eld element opening for the leaf if = 0) is sucient: the\tree part" of the proof implies that C*;* C_bas b polynomials agree in H and the inner product that C_bhas the right degree.

$$ {\mathsf{C}}=[{(}{\boldsymbol{C}}(\tau)].} $$

$$ C_{\mathbf{b}}. $$

$$ H(X){\mathrm{s}} $$

$$ \mathsf{C},\mathsf{C}_{\mathrm{b}} $$

$$ {\boldsymbol{\tau}}, $$

$$ \mathbb{H}^{\mathbf{b}} $$

$$ C_{\mathbf{b}} $$

$$ \kappa=0) $$

$$ \mathsf{C},\mathsf{C}_{\mathrm{b}} $$

$$ \mathbb{H}^{\mathbf{b}} $$

$$ C_{\mathbf{b}} $$

Scheme Description. Formally, we present an LVC commitment scheme that works for the function family²²:

$$ \begin{aligned}{{\sf E x t}{\nu^{*}}\mathcal{F}{p,2^{n}}={f:\mathbb{F}^{m}\to\mathbb{F},m=2^{\kappa+\nu+1}\ |\ \exists\mathbf{f}\in\mathbb{F}^{2^{n}},\mathbf{b}\in{0,1}^{\nu+1}\ {\bf s.t.}}\ {\forall\mathbf{v}{0...0},\ldots,\mathbf{v}{1...1}\in\mathbb{R}^{2^{n}}:\ f(\mathbf{v}{0..0},\ldots,\mathbf{v}{1...1})=\mathbf{v}_{\mathbf{b}}\cdot\mathbf{f}}}\ \end{aligned}. $$

Algorithms UVTree*:* KeyGen and UVTree*:* Commit(pk*;v)!* (C*;aux) are the same as the Lagrange basis construction of Section 5 and are omitted. The commitment to v is C = []₁v together with the auxiliary input information aux. Note that step 4:* of the open algorith is IP*:* Open from Sec. 5.2.

$$ W N T e e.c m m m t(p k,v)\rightarrow(C,a U X $$

$$ C = \left[ \boldsymbol {\lambda} \right] _ {1} \mathbf {v} $$

UVTree*:* Open(pk*;* b*;aux;f;* y)! :

1.Let f(v₀_{::: 0};:::; v₁_{::: 1}) = v_bf for f 2 F² and some b = (b ;:::;b₀).

$$ f \left(\mathbf {v} _ {0 \dots 0}, \dots , \mathbf {v} _ {1 \dots 1}\right) = \mathbf {v} _ {b} \cdot \mathbf {f} $$

$$ \mathbf{f}\in\mathbb{F}^{2^{\kappa}} $$

$$ \mathbf{b}=\left(b_{\nu},\ldots,b_{0}\right) $$

bjj 2.For any 0 j, compute C_bjj= []₁v^bjj.

$$ 0\leq j\leq\nu. $$

$$ \mathsf{C}{\mathbf{b}{|j}}=[\lambda{^{\mathbf{b}{|j}}}]{1}\mathbf{v}{\mathbf{b}{|j}}. $$

Pj i m (i=0bi2 )j+2 3.Compute [H]¹= (C₀ C₁)*=2, and for any 0 j 1, compute K_b= 2!*2. Then ^jj dene [H_bjj]₁= K_bjj(C₀_bj:::b0C₁_bj:::b0).

$$ [H]{1}=(\mathsf{C}{0}-\mathsf{C}_{1})/2 $$

$$ 0\leq j\leq\nu-1 $$

$$ K_{b_{|j}}=2\omega^{(\sum_{i=0}^{j}b_{i}2^{i})\frac{m}{2^{j+2}}} $$

²² Similarly to the multivariate case, we can also consider general linear functions.

4.Find R(X);H (X); R^(X) such that if b

$$ R(X),H_{\mathbf{b}}(X),\hat{R}(X) $$

$$ \left(\lambda^{\mathbf{b}{|j+1}}(X)\ \mathbf{v{\mathbf{b}{|j}}}\right)\left(\sum{i=1}^{2^{n}}f_{i}\lambda_{i}^{\mathbf{b}}(X)\right)-y m^{-1}=X R(X)+H_{\mathbf{b}}(X)t_{\mathbf{b}}(X). $$

^(m 1 2 23 Dene R X) = X R(X).

$$ \hat{R}(X)=X^{m-1-2^{\kappa}}R(X).^{23} $$

5.Output ([H];:::;[H]; [H ()]; [R()]; [R^()];[C]). ^b0 ₁ bj 11 b 1 1 1 b 1 UVTree*:* Vf(vk*;* C*;f;y;)!* 0*=*1: P₂

$$ ([H_{b_{0}}]{1},\ldots,[H{\mathbf{b}{|\nu-1}}]{1},:[H_{\mathbf{b}}(\tau)]{1},:[R(\tau)]{1},:[\hat{R}(\tau)]{1},:[\hat{R}(\tau)]{1},:[\mathbf{C_{b}}]_{1}). $$

b 1.Use the vector representation f of f and compute Cf=_i=1fi[_i()]₂.

$$ \mathsf{C}{f}=\sum{i=1}^{2^{\kappa}}f_{i}[\lambda_{i}^{\mathbf{b}}(\tau)]_{2} $$

2.Check that

$$ e(\mathsf{C}-\mathsf{C_{b}},1)=e([H]{1},[t{b_{0}}(\tau)]{2})+\sum{i=0}^{\nu-1}e([H_{\mathbf{b}{|j}}]{1},[t_{\mathbf{b}{|j+1}}(\tau)]{2}) $$

(8)

$$ e\big(\mathsf{C}{\mathbf{b}},\mathsf{C}{f}\big)-e\big(m^{-1}y[1]{1},[1]{2}\big)=e\big([R]{1},[1]{2}\big)+e\big([H_{\mathbf{b}}]{1},[t{\mathbf{b}}(\tau)]_{2}\big) $$

(9)

(10)

$$ e\big([R]{1},[\tau^{m-1-2^{\kappa}}]{2}\big)=e\big([\hat{R}]{1},[1]{2}\big) $$

+1 Alternatively, if m = 2, the scheme supports individual openings only and the IP commitment is not used but instead c_b= y: To save online verier work one can preprocess*;* for any 2f0*;* 1g (m elements).

$$ m=2^{\nu+1} $$

$$ c_{\mathbf{b}}=y $$

$$ \ ^{\delta} $$

$$ \delta\in{0,1}^{\nu} $$

Completeness follows from the high level description of the sheme. For the simple case, where the tree is used to open individual position we prove soundness under standard assumptions in the following theorem.

+1 Theorem 9. When m = 2*, the scheme is secure under the* (m 1)*-*BSDH assumption.

$$ m=2^{\nu+1} $$

Proof. Given an instance of the (m 1)-BSDH Assumption, generate the parameters and give them to the adversary.

$$ (m-1) $$

0 When it comes up with two dierent y;y⁰ and accepting proofs (f[H]₁; [H_bjj]₁g_j=01), (f[H⁰]₁; [H_b]₁g_j=01), _jj the challenger can obtain by subtracting the verication equations:

$$ y,y^{\prime} $$

$$ e((y-y^{\prime})[1]{1},[1]{2})=e([H-H^{\prime}]{1},[t{b_{0}}(\tau)]{2})+\sum{i=0}^{\nu-1}e([H_{\mathbf{b}{j j}}-H{\mathbf{b}{j j}}^{\prime}]{1},[t_{\mathbf{b}{[j+1}}(\tau)]{2}). $$

(11)

Let p^j(X) = (t_bjj(X))=(X h^b). This is a polynomial of degree less than m 1 since h^bis a root of t^bjj(X) for any 0 j. [p_j]₁= [p_j()]₁can be constructed from the powers of in G₁. Substituting in Eq. 11 and rearranging terms, we can compute, !

$$ p_{j}(X)=(t_{\mathbf{b}{|i}}(X))/(X-\mathsf{h}{\mathbf{b}}) $$

$$ {\mathfrak h}_{\bf h} $$

$$ t_{\mathbf{b}_{|j}}(X) $$

$$ 0 \leq j \leq \nu . [ p _ {j} ] _ {1} = [ p _ {j} (\tau) ] _ {1} $$

$$ \tau $$

$$ \mathbb{G}_{1} $$

$$ \left[\frac{1}{\tau-\mathsf{h_{b}}}\right]{T}=(y-y^{\prime})^{-1}\left(e([H-H^{\prime}]{1},[p_{0}]{2})+\sum{i=0}^{\nu-1}e([H_{\mathbf{b_{i j}}}-H_{\mathbf{b_{i j}}}^{\prime}]{1},[p{j+1}]_{2})\right), $$

breaking the (m 1)-BSDH Assumption.

When > 0 and one uses the IP argument for the leaf commitments, the proof is in the AGM and is based on the intuition mentioned before that the \tree part" of the proof guarantees that C and C_bagree on ^b H, while the IP part guarantees that c_bis of the right degree, so it guarantees uniqueness of c_b. Finally, the IP soundness allows to complete the reasoning.

$$ \kappa>0 $$

$$ C_{\mathbf{b}} $$

$$ \mathbb{H}^{\mathbf{b}} $$

$$ \mathbf{c_{b}} $$

$$ \mathbf{c_{b}} $$

Maintainability. Naive computation of all partial proofs takes time O(mlog² m) but this can be reduced to time O(mlogm) computing some values at the leafs and traversing the tree from leaf to root to compute the rest of the values using expression (3).

$$ O(m\log^{2}m) $$

²³ We assume as in Section 5 that at most m 1 powers of are in the SRS in group G₁. The degree check is meant to ensure that R(X) is of degree at most 2 2.

$$ m-1 $$

$$ \tau $$

$$ \mathbb{G}_{1} $$

$$ R(X) $$

$$ 2^{\kappa}-2 $$

References

1.H. Abusalah, J. Alwen, B. Cohen, D. Khilko, K. Pietrzak, and L. Reyzin. Beyond hellman’s time-memory tradeos with applications to proofs of space. In T. Takagi and T. Peyrin, editors, ASIACRYPT 2017, Part II, volume 10625 of LNCS, pages 357{379. Springer, Heidelberg, Dec. 2017. 37 2.E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward. Aurora: Transparent succinct arguments for R1CS. In Y. Ishai and V. Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 103{128. Springer, Heidelberg, May 2019. 14 3.D. Boneh and X. Boyen. Ecient selective identity-based encryption without random oracles. Journal of Cryp- tology, 24(4):659{693, Oct. 2011. 8 4.D. Boneh, B. Bunz, and B. Fisch. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In A. Boldyreva and D. Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 561{586. Springer, Heidelberg, Aug. 2019. 3, 6, 7, 10, 34, 36, 38 5.B. Bunz, M. Maller, P. Mishra, N. Tyagi, and P. Vesely. Proofs for inner pairing products and applications. In M. Tibouchi and H. Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Pro- ceedings, Part III, volume 13092 of Lecture Notes in Computer Science, pages 65{97. Springer, 2021. 5, 6, 7, 24, 29, 38 6.M. Campanelli, D. Fiore, N. Greco, D. Kolonelos, and L. Nizzardo. Incrementally aggregatable vector commitments and applications to veriable decentralized storage. In S. Moriai and H. Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 3{35. Springer, Heidelberg, Dec. 2020. 3, 5, 6, 7, 10 7.D. Catalano and D. Fiore. Vector commitments and their applications. In K. Kurosawa and G. Hanaoka, editors, PKC 2013, volume 7778 of LNCS, pages 55{72. Springer, Heidelberg, Feb. / Mar. 2013. 3, 6, 34 8.A. Chepurnoy, C. Papamanthou, and Y. Zhang. Edrax: A cryptocurrency with stateless transaction validation. Cryptology ePrint Archive, Report 2018/968, 2018. https://eprint.iacr.org/2018/968. 3, 36 9.V. Daza, C. Rafols, and A. Zacharakis. Updateable inner product argument with logarithmic verier and applications. In A. Kiayias, M. Kohlweiss, P. Wallden, and V. Zikas, editors, PKC 2020, Part I, volume 12110 of LNCS, pages 527{557. Springer, Heidelberg, May 2020. 5 10.S. Dziembowski, S. Faust, V. Kolmogorov, and K. Pietrzak. Proofs of space. In R. Gennaro and M. J. B. Robshaw, editors, CRYPTO 2015, Part II, volume 9216 of LNCS, pages 585{605. Springer, Heidelberg, Aug. 2015. 37 11.Filecoin. Filecoin powers of tau ceremony attestations, 2020. https://github.com/arielgabizon/ perpetualpowersoftau. 6 12.B. Fisch. PoReps: Proofs of space on useful data. Cryptology ePrint Archive, Report 2018/678, 2018. https: //eprint.iacr.org/2018/678. 4 13.B. Fisch. Tight proofs of space and replication. In Y. Ishai and V. Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 324{348. Springer, Heidelberg, May 2019. 37 14.G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. In H. Shacham and A. Boldyreva, editors, CRYPTO 2018, Part II, volume 10992 of LNCS, pages 33{62. Springer, Heidelberg, Aug. 2018. 7, 8 15.S. Gorbunov, L. Reyzin, H. Wee, and Z. Zhang. Pointproofs: Aggregating proofs for multiple vector commitments. In J. Ligatti, X. Ou, J. Katz, and G. Vigna, editors, ACM CCS 2020, pages 2007{2023. ACM Press, Nov. 2020. 3, 6, 7, 10, 22, 23 16.L. Grassi, D. Khovratovich, C. Rechberger, A. Roy, and M. Schofnegger. Poseidon: A new hash function for fZero-Knowledgeg proof systems. In 30th USENIX Security Symposium (USENIX Security 21), pages 519{535, 2021. 21 17.J. Groth. On the size of pairing-based non-interactive arguments. In M. Fischlin and J.-S. Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 305{326. Springer, Heidelberg, May 2016. 21, 37 18.J. Groth, M. Kohlweiss, M. Maller, S. Meiklejohn, and I. Miers. Updatable and universal common reference strings with applications to zk-SNARKs. In H. Shacham and A. Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 698{728. Springer, Heidelberg, Aug. 2018. 4 19.J. Kilian. A note on ecient zero-knowledge proofs and arguments (extended abstract). In 24th ACM STOC, pages 723{732. ACM Press, May 1992. 38 20.R. W. F. Lai and G. Malavolta. Subvector commitments with application to succinct arguments. In A. Boldyreva and D. Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 530{560. Springer, Heidelberg, Aug. 2019. 3, 5, 6, 8, 34, 38

21.B. Libert, S. C. Ramanna, and M. Yung. Functional commitment schemes: From polynomial commitments to pairing-based accumulators from simple assumptions. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, and D. Sangiorgi, editors, ICALP 2016, volume 55 of LIPIcs, pages 30:1{30:14. Schloss Dagstuhl, July 2016. 3, 6 22.B. Libert and M. Yung. Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In D. Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 499{517. Springer, Heidelberg, Feb. 2010. 3, 7 23.R. C. Merkle. A digital signature based on a conventional encryption function. In C. Pomerance, editor, CRYPTO’87, volume 293 of LNCS, pages 369{378. Springer, Heidelberg, Aug. 1988. 3, 36 24.S. Micali. CS proofs (extended abstracts). In 35th FOCS, pages 436{453. IEEE Computer Society Press, Nov. 1994. 38 25.C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In A. Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 222{242. Springer, Heidelberg, Mar. 2013. 7 26.C. Rafols and A. Zapico. An algebraic framework for universal and updatable SNARKs. In T. Malkin and C. Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 774{804, Virtual Event, Aug. 2021. Springer, Heidelberg. 14, 17 27.L. Ren and S. Devadas. Proof of space from stacked expanders. In M. Hirt and A. D. Smith, editors, TCC 2016-B, Part I, volume 9985 of LNCS, pages 262{285. Springer, Heidelberg, Oct. / Nov. 2016. 37 28.S. Srinivasan, A. Chepurnoy, C. Papamanthou, A. Tomescu, and Y. Zhang. Hyperproofs: Aggregating and maintaining proofs in vector commitments. In 31st USENIX Security Symposium (USENIX Security 22), Boston, MA, Aug. 2022. USENIX Association. 5, 6, 7, 24, 29, 39 29.A. Tomescu, I. Abraham, V. Buterin, J. Drake, D. Feist, and D. Khovratovich. Aggregatable subvector commitments for stateless cryptocurrencies. In C. Galdi and V. Kolesnikov, editors, SCN 20, volume 12238 of LNCS, pages 45{64. Springer, Heidelberg, Sept. 2020. 2, 5, 6, 7, 10, 19, 20, 30, 38

A Vector Commitment Denitions

In this section we provide the classical denitions of vector commitments (VC), introduced by Catalano and Fiore [7], and subvector commitments (SVC), as in [4, 20], that are particular cases of Linear-map Vector Commitments (LVC).

Denition 7(Vector Commitment). A vector commitment for vectors from the message space M is a tuple of PPT algorithms KeyGen*;Commit;Open;*Vf that work as follows:

VC*:* KeyGen(1*; M;m*)! prk*;vrk: On input the security parameter, the message space M for the vectors and the maximum vector length m²⁴. It returns s proving key prk that includes M, and a verication key vrk.*

$$ (1^{\lambda},{\mathcal{M}},m)\to{\mathsf{p r k}} $$

$$ \lambda, $$

$$ m^{24} $$

m VC*:* Commit(prk*;v)!* (C*;aux): Takes prk and a vector v = (v₁;v₂ :::;v_m) 2M, and returns a commitment C and auxiliary information aux.*

$$ \mathsf{i t}(\mathsf{p r k},\mathbf{v})\to\ (mathsf C\mathsfmathsf{{x u x}}) $$

$$ \mathbf{\nabla}\mathbf{\nabla}v=\left(v_{1},v_{2}\ldots,v_{m}\right)\in\mathcal{M}^{m} $$

VC*:* Open(prk*;aux;i;v*_i)!_i: On input prk*,* aux*, an index i 2* [n], and a value v_i, it outputs a proof_ithat the value v_iis at position i.

$$ \cdot,i,v_{i})\rightarrow\pi_{i} $$

$$ i\in[n] $$

$$ v_{i}. $$

$$ \pi_{i} $$

$$ v_{i} $$

VC*:* Vf(vrk*;* C*;i;v;_i)! b 2f0;* 1g: On input vrk*,* C*, i 2* [m], a value v 2M and_i, it outputs 1 if the proof veries and 0 otherwise.

$$ C.N(v H N,C,i,v,\pi_{i})\rightarrow b\in\left{0,l1\right} $$

$$ {\mathsf{C}},,i\in[m] $$

$$ v\in\mathcal{M} $$

$$ \pi_{i}. $$

Perfect Correctness A VC scheme is perfectly correct if, for all 2 N, any vector length m = poly(), any m index i 2 [n], and any v 2M, we have:

$$ \lambda\in\mathbb{N} $$

$$ i\in\left|n\right| $$

$$ \ \mathrm{i}{\mathrm{f}}, $$

$$ m={\mathsf{p o l y}}(\lambda) $$

$$ \mathbf{v}\in\mathcal{M}^{m} $$

$$ \Pr \left[ \mathrm {V C}. \mathrm {V f} (\mathrm {v r k}, \mathrm {C}, i, v _ {i}, \pi_ {i}) = 1 \mid \begin{array}{c} (\mathrm {p r k}, \mathrm {v r k}) \leftarrow \mathrm {V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {M}, m\right) \ (\mathrm {C}, \mathrm {a u x}) \leftarrow \mathrm {V C}. \mathrm {C o m m i t} (\mathrm {p r k}, \mathbf {v}) \ \pi_ {i} \leftarrow \mathrm {V C}. \mathrm {O p e n} (\mathrm {p r k}, \mathrm {a u x}, i, v _ {i}) \end{array} \right] = 1. $$

²⁴ Some schemes are unbounded: they ignore m since they can commit to vectors of any length poly().

Strong Position Binding A VC scheme satises strong position binding if, for all PPT adversaries A, for all 2 N, any vector length m = poly(),:

$$ \lambda\in\mathbb{N} $$

$$ {\mathcal A}, $$

$$ m={\mathsf{p o l y}}(\lambda) $$

$$ \Pr \left[ \begin{array}{c c} \mathrm {V C . V f} (\mathrm {v r k}, \mathrm {C}, i, v, \pi) = 1 \ \wedge \mathrm {V C . V f} (\mathrm {v r k}, \mathrm {C}, i, v ^ {\prime}, \pi^ {\prime}) = 1 \ \wedge v \neq v ^ {\prime} \end{array} \right| \left| \begin{array}{l} (\mathrm {p r k}, \mathrm {v r k}) \leftarrow \mathrm {V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {M}, m\right) \ (\mathrm {C}, i, (v, \pi), \left(v ^ {\prime}, \pi^ {\prime}\right)) \leftarrow \mathcal {A} (\mathrm {p r k}, \mathrm {v r k}) \end{array} \right] = \operatorname {n e g l} (\lambda). $$

Weak Position Binding If we relax the denition above to hold only for honestly-generated commitments C, we obtain a weak position binding notion. In other words, for all PPT adversaries A, for all 2 N, any vector length m = poly(),

$$ {\mathcal A}. $$

$$ m=\ \mathsf{p o l y}(\lambda) $$

$$ \lambda\in\mathbb{N} $$

$$ \Pr \left[ \begin{array}{c c} \mathrm {V C . V f} (\mathrm {v r k}, \mathrm {C}, i, v, \pi) = 1 \ \wedge \mathrm {V C . V f} (\mathrm {v r k}, \mathrm {C}, i, v ^ {\prime}, \pi^ {\prime}) = 1 \ \wedge y \neq y ^ {\prime} \end{array} \right| \left( \mathrm {p r k}, \mathrm {v r k} \right) \leftarrow \mathrm {V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {M}\right) \left| \begin{array}{l} \left(\mathbf {v}, i, v, \pi , v ^ {\prime}, \pi^ {\prime}\right) \leftarrow \mathcal {A} (\mathrm {p r k}, \mathrm {v r k}) \ \left(\mathrm {C}, \mathrm {a u x}\right) \leftarrow \mathrm {V C}. \mathrm {C o m m i t} (\mathrm {p r k}, \mathbf {v}) \end{array} \right] = \mathrm {n e g l} (\lambda). $$

Denition 8(Sub-Vector Commitment). A Sub-Vector Commitment scheme is a VC scheme that opens subsets rather than positions. It consists on algorithms SVC*:* KeyGen*;SVC:* Commit*;SVC:* Open*;SVC:* Vf that work as follows:

SVC*:* KeyGen(1*; M;m*)! prk*;vrk: Takes the security parameter, the message space M for the vectors elements and the maximum vector length m. It outputs a proving key prk and verication key vrk.*

$$ .e y!!{\mathsf{G e n}}(1^{\lambda},{\mathcal{M}},m)\rightarrow $$

m SVC*:* Commit(prk*;v)!* (C*;aux): On prk and a vector v = (v₁;v₂ :::;v_m) 2M, returns a commitment C and auxiliary information aux.*

$$ \mathtt{v}=\left(v_{1},v_{2}\ldots,v_{m}\right)\in\mathcal{M}^{m} $$

SVC*:* Open(prk*;aux;I;v_I)!_I: Takes as input prk,* aux*, a set of index I* [m] and values v_I= fv_ig_i2Iand outputs a proof_Ithat v_iis the value in position i, for all i 2 I.

$$ I,\mathbf{v}{I})\rightarrow\pi{I} $$

$$ I\subset[m] $$

$$ \mathbf{v}{I}={v{i}}_{i\in I} $$

$$ \upsilon_{i} $$

$$ i\in I $$

SVC*:* Vf(vrk*;* C*;I;y;_I)! b 2f0;* 1g : Takes as input vrk*,* C*, I, a vector* y = fy_ig_i2Iand_I. It outputs 1 for accept or 0 for reject.

$$ \cdot\mathbb{f}(\mathbb{N}(\mathbb{N}\ \mathbb{N},\mathbb{C},I,\mathbb{y},\pi_{I})\to b\in\left{0,\mathbb{I}\right} $$

$$ c,I, $$

$$ \mathbf{y}={y_{i}}_{i\in I} $$

$$ \pi\ !I{} $$

SVC correctness An SVC scheme is perfectly correct if, for all 2 N, any vector length m = poly(), any m index set I [m], and any v 2M, 2 3

$$ \lambda\in\mathbb{N} $$

$$ m=\ \mathsf{p o l y}(\lambda) $$

$$ I\subset[m] $$

$$ \mathbf{v}\in\mathcal{M}^{m} $$

$$ \Pr \left[ \mathrm {S V C . V f} (\mathrm {v r k}, C, I, \mathbf {v} _ {I}, \pi_ {I}) = 1 \left| \begin{array}{c} (\mathrm {p r k}, \mathrm {v r k}) \leftarrow \mathrm {V C}. \mathrm {K e y G e n} \left(1 ^ {\lambda}, \mathcal {M}, m\right) \ (\mathrm {C}, \mathrm {a u x}) \leftarrow \mathrm {V C}. \mathrm {C o m m i t} (\mathrm {p r k}, \mathbf {v}) \ \pi_ {I} \leftarrow \mathrm {S V C}. \mathrm {O p e n} (\mathrm {p r k}, \mathrm {a u x}, I, \mathbf {v} _ {I}) \end{array} \right] = 1. \right. $$

SVC binding. Binding captures the impossibility of creating inconsistent openings for subvectors. An SVC scheme satises strong position binding if, for all PPT adversaries A, for all 2 N, any vector length m = poly(),

$$ \ \mathcal A $$

$$ m={\mathsf{p o l y}}(\lambda) $$

$$ \lambda\in\mathbb{N} $$

$$ \operatorname*{P r}\left[\begin{matrix}{\mathsf{S V C,\mathsf{V f}}(\mathsf{v r k},\mathsf{C},I,\mathbf{y},\pi_{I})=1\wedge\Big|\left(\mathsf{p r k},\mathsf{v r k}\right)\leftarrow\mathsf{V C,\mathsf{K e y f e e n}}(1^{\lambda},\mathcal{M},m)}\ {\mathsf{S V C,\mathsf{V f}}(\mathsf{v r k},\mathsf{C},J,\mathbf{y}^{\prime},\pi_{J})=1}\ {\wedge\exists i\in I\cap J\mathbf{s.t.}\ y_{i}\neq y{{{i}}}}\ \end{matrix}\right.\left(\begin{matrix}{\mathsf{C},I,J,}\ {\mathsf{v},\pi_{I},\mathbf{y}^{\prime},\pi_{J}}\ \end{matrix}\right)\leftarrow\mathsf{n e g l}(\lambda). $$

Weak Position Binding is considering the denition above to hold only for honestly-generated commitments C computed via SVC*:* Commit.

B Vector Commitment Applications

Here we describe in more detail some of the applications of our work and their specic requirements.

B.1 Veriable Databases

Vector commitments are a solution for the problem of outsourcing storage to untrusted parties. In the veriable database (VDB) setting, a client owns a database D and wishes to outsource the storage of D to a server while keeping the ability to query and update the database. The security goal is to prevent an untrusted server from tampering with the database and cheat on the query outcomes that it provides to the client. A good solution should enable the client to run eciently once the outsourcing has been performed. Furthermore, the communication and running time of the query and update protocols should not depend on the total size of the database.

The basic problem of integrity of outsourced data can be easily solved by using the celebrated Merkle tree construction [23]. It consists in hashing the data using a tree structure in which the leaves are the blocks of D and every internal node is the hash of its two child nodes; the root of this tree is the so-called Merkle hash (digest) of D. To use Merkle trees to solve the outsourced storage problem, the client can compute the Merkle tree and store only the root. When the client wants to retrieve the k-th record D_k, the server responds with the data and a logarithmic-size path consisting of the nodes from D_kuntil the root, and the client can then verify the authenticity of D_kin logarithmic time by recomputing a hashed value using the path and check it against the stored digest (Merkle root). The security of this construction can be reduced to the collision resistance of the hash function [23]. In terms of eciency, the communication complexity of this protocol is O(logn).

$$ \mathbb{D}_{k}, $$

$$ \mathrm{D}_{k} $$

$$ \mathrm{D}_{k} $$

While Merkle trees solution is asymptotically better than resending the entire database, Vector Commitments allow to improve the communication complexity beyond logarithmic and to add important properties such as updatability or functional openings.

B.2 Stateless Cryptocurrency

One of an important decentralised applications of vector commitments is in distributed ledger-based payment systems, known as cryptocurrencies. The best-known examples of cryptocurrency largely used today are Bitcoin, Ethereum, or Zcash to name a few. Such a system, utilises a blockchain in order to post and record peer-to-peer payment transactions. This translates into an ordered log of transactions, in other words an append-only public ledger, that is replicated across nodes in the network. We will call such nodes that store and check the transactions log validators, as opposed to simple cryptocurrency users who only store their account balances. The validators are essential to reach consensus on what is the current state of the public ledger.

Unfortunately, there is a bottleneck: verifying the validity of a transaction requires querying the entire ledger to obtain the latest state of the account balances. However, maintaining the entire ledger increases the memory requirements and reduces the number of possible validators.

To reduce the amount of storage required of validators, there have been solutions [4, 8] based on vector commitments. Instead of storing the entire ledger state, the validators can keep commitments to vectors representing the state. Using vector commitments properties, validators with a commitment to the ledger state can still validate transactions sent by users by checking opening proofs against the commitment. More concretely, the users will send their account balance values and a proof that this is consistent with respect to the commitments stored by the validators. After the transaction is accepted, the validators should be able to update the commitment to the old state to a commitment to the new state that includes the changes made by the transaction. If the vector commitment scheme has small commitment sizes, short proofs, ecient opening computation and allow for updates, then such a solution provides the best trade-o between storage, bandwidth, and computation.

We call such a solution a stateless cryptocurrency, i.e. a system where neither validators nor cryptocurrency users need to store the full ledger state. While the stateless cryptocurrencies overcome the storage overhead when performing transaction validation, they increase network communication because of extra opening proofs added to each transaction payload. To minimise communication in the transactions, an important feature of vector commitments is aggregation. Using aggregation to "pack" together multiple opening proofs for a batch of transactions into a single constant-size proof allows a signicant improvement in the communication.

Another important property for applications to stateless cryptocurrencies is maintainability. This guarantees that re-proving an opening about the new state requires less time than computing it from scratch, which would make all previous computations useless. Instead, the individual proofs are initially computed and stored and eciently updated after each state transition. Collective updates or maintainability saves computational resources since computing a single proof needs linear time while updating all proofs needs sublinear (e.g. logarithmic time).

To summarize, in order to provide the best trade-o between storage, bandwidth, and computation in stateless cryptocurrency application, the following properties are required from a VC scheme:

Short Commitment: validators store only a commitment to the ledger state.

Short Opening Proofs: to submit a transaction, users will send their account balance values and a proof that this is consistent with respect to the commitments stored by the validators.

Ecient Verication: to validate transactions, validators check opening proofs against the commitment. Updatability: after the transaction is accepted, the validators should be able to update the commitment

to the old state to a commitment to the new state that includes the changes made by the transaction.

Aggregation: to minimise communication in the transactions, some nodes can "pack" together multiple opening proofs for a batch of transactions into a single small proof.

Maintainability: to save proving time at each update, maintaining all the proofs up to date should be possible in sublinear time each time the state changes.

B.3 Proof of Space

Proof-of-Space (PoS) is an eco-friendly alternative to proof-of-work (PoW) in blockchain-based consensus mechanisms that does not consume its resource (space vs. energy), but rather reuses it. A PoS, was introduced in [10] and further studied in [27, 1, 13]. It is an interactive protocol between a prover and a verier that allows to check if the prover is storing intactly a le (data) that uses a specied amount of disk space. The protocol must have compact communication relative to the prover’s space requirements and ecient verication. A PoS is persistent if repeated audits force the prover to permanently store the le over a period of time.

Proof of Space protocols consist of two main steps:

{Initialization (Setup phase): On public input v, an advice a (e.g., vector of random data) of size m is created and committed to in C. The advice is stored by the prover, while the verier knows only the commitment C to the advice.

{Execution (Audit phase): The verier sends a challenge, for example asking the prover to open some positions in the advice and the prover responds. The verier outputs accept if they are convinced that the prover stores the advice. This phase can be repeated many times.

We require that the verier is highly ecient in both phases, whereas the prover is highly ecient in the execution phase if they are honest and had stored the data as expected. Otherwise, if the prover deleted parts of the le, regenerating the advice in order to pass the audit phase should be more costly (in time or computation cost) than just storing the le. A PoS can be run non-interactively using a public blockchain to perform the Setup and the Audit phase of the protocol described above. Provers and veriers will post their challenge-response in the blockchain and this should be publicly veriable.

Publicly Veriable Proof of Space. A classical publicly veriable PoS is based on Merkle trees and random spot-checks. A drawback of this construction is that proofs grow with the number of spotchecks (and the size of the tree) and become undesirably large to be stored in a blockchain. While these checks can be compressed through a SNARK (Succinct Non-interactive Argument of Knowledge) [17], this still require hundreds of GB of RAM and tens of minutes compared to our vector commitment solution.

For a construction of PoS based on vector commitments, the prover (miner) uses a VC to commit to a le (seen as a vector of blocks); then at every audit the verier chooses a challenge by picking a set of many randomly chosen positions, and the prover responds by sending the subvector and an opening proof. The soundness property of a PoS scheme requires that for any prover that convinces the verier that it is storing the le, there exists an algorithm called the extractor that interacts with the prover and extracts the le.

A vector commitment construction with openings for subvectors immediately implies a publicly-veriable proof of storage.

Finally, our tree-based constructions allows reduced proving costs in the audit phase of PoS by instead using some extra memory to store proofs. A prover can eciently pre-compute and store proofs and simply serve them on demand. Since memory is expensive, however, it is not optimal to store all the proofs. Our construction is exible: a prover only stores partial proofs to reduce computation. Importantly, the part of the proof that is computed on the y has constant size and therefore the proof size only depends on the amount of memory dedicated by the prover. Finally, our proofs can be aggregated using standard techniques [5]. The smaller proof size translates to a cheaper aggregation cost.

B.4 Compiling SNARKs from Vector Commitments

Our LVC schemes can be used to construct new ecient Succinct Non-interactive Arguments of Knowledge (SNARKs) with constant-size opening. Following up on the approach pioneered by Kilian [19] and Micali [24], recent works [4, 20] show that we can construct SNARKs based on probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) by plugging in vector commitments with subvector openings.

In an IOP the prover sends multiple proof oracles to a verier. The verier uses these oracles to query a small subsets of the proof in order to decide acceptance or rejection. Recent practical instantiations of proof systems from IOPs use Merkle trees as a vector commitment. While Merkle trees do not require a trusted setup, these schemes have two signicant drawbacks for the two above applications: rst, position openings are not constant size, and second, the openings of several positions cannot be compressed into a single constant size proof (i.e. it does not support aggregation or subvector openings). LVC with subvector openings are a perfect candidate to instantiate IOP-based SNARKs.

Replacing Merkle trees with a vector commitment, Lai and Malavolta [20] obtain a SNARK where the proof consists of 3 eld elements and 2 group elements. Using the same blueprint, we can use LVC to match the same proof size as theirs and improve the trusted setup by making it compatible with other widely deployed proof systems. On the other hand, the construction in [20] (last row in their Table 2) requires a trusted setup with a \gap" in the powers of exponent.

B.5 Applications of Range Openings

One of the features of our monomial-basis construction is to have ecient range openings. These arguably have several natural applications.

In several protocols involving queries, it is common to perform some type of \caching" optimizations. For example, an HTTP client can perform prefetching²⁵ and receive from a server not only the values of interest but other related values that could potentially be queried in the near future (e.g., values in a neighboring range of the queried values). Our range-based queries can be used in similar setting whenever we need to query a resource whose digest consists of a vector commitment.

C Native SVC in [29]

m For a vector v 2 F and a subset I [m], the subvector opening scheme of Tomescu et. al. ([29]) consists on algorithms (SVC*:* KeyGen*;SVC:* Commit*;SVC:* Open*;SVC:* Vf) such that SVC*:* KeyGen, SVC*:* Commit behave as IP*:* KeyGen, IP*:* Commit in the construction of Section 5.2 and the other two as follows:

$$ I\subset[m] $$

$$ \mathbf{v}\in\mathbb{F}^{m} $$

²⁵ https://developer.mozilla.org/en-US/docs/Web/HTTP/Link_prefetching_FAQ

$$ \tilde{C}(X)=\sum_{i\in I}\tilde{c}{i}\mu{i}(X) $$

P SVC: Open(prk*;aux;I;~c)!* : Compute C(X) = c (X), where f (X)Qg are the Lagrange interpo- I i2I i i i lation polynomials of the set fh_ig_i2I, and nd H(X) such that for t_I(X) =_i2I(X h_i);

$$ I,\mathbf{\tilde{c}})\rightarrow\pi_{I} $$

$$ \left{\mu_{i}(X)\right} $$

$$ {\mathsf{h}{i}}{i\in I} $$

$$ H({\bar{X}}) $$

$$ \textstyle t_{I}\bigl(X\bigr)=\prod_{i\in I}\bigl(X-\mathsf{h}_{i}\bigr) $$

$$ \mathcal{C}(X)-\tilde{C}}({\cal X})=t_{I}(X)H(X). $$

$$ \pi_{I}=\big(\tilde{\mathsf{C}}=\big[\tilde{\mathcal{C}}(\tau)|{1},|H|{1}!=!|H(\tau)|_{1}\big) $$

OutputI= C C)]1; [H]1= [H()]1: SVC*:* Vf(vrk*;* C*;I;~c;_I)! b 2f0;* 1g : Compute [t_I]₂= [t_I()]₂and output 1 if and only if

$$ S N..((u/k,C,I,\tilde{c},\pi_{I})\rightarrow\dot{b}\in\dot{0{},,1}) $$

$$ [t_{I}]{2}=[t{I}(\tau)]_{2} $$

$$ e\big(\mathsf{C}-\tilde{\mathsf{C}},[1]{2}\big)=e\big([H]{1},[t_{I}]_{2}\big). $$

D Complementary material of section 8.

D.1 PST polynomial commitment

The PST polynomial commitment allows to commit to-variate polynomials of individual degrees less than ‘. The core idea of the construction lies in the fact that for every p(X) 2 F[X ;:::;X₁] and x = (x ;:::;x₁) 2 F , p(x) = y if and only if there exist polynomials H (X);:::;H₁(X) such that

$$ p(\mathbf{X})\in\mathbb{F}[X_{\nu},\ldots,X_{1}] $$

$$ \mathbf{x}=\left(x_{\nu},\ldots,x_{1}\right)\in $$

$$ \mathbb{F}^{\nu},,p(\mathbf{x})=y $$

$$ H_{\nu}(\mathbf{X}),\ldots,H_{1}(\mathbf{X}) $$

$$ p(\mathbf{X})-y=\sum_{j=1}^{\nu}H_{j}(\mathbf{X})\cdot(X_{j}-x_{j}) $$

where the proof polynomials H_j(X) are eciently computable.

$$ H_{j}(\mathbf{X}) $$

Using standard techniques to encode monomials in a cryptographically secure bilinear group (encode setd d1 ting X = and publishing all the monomials [¹]¹an^d []₂) the exponents of results in a polynomial commitment with proof of size roughly group elements.

$$ \ =tautau $$

$$ [\tau_{\nu}^{d_{\nu}}\cdots\tau_{1}^{d_{1}}]] $$

$$ [\tau!_{2}) $$

Srinivasan et. al. [28] observe that computing all polynomial evaluations and proofs for a committed -variate multilinear polynomial in the hypercube f0*;* 1g can be done in quasi-linear time in the dimension of the vector, instead of the trivial quadratic time. By encoding a vector as the corresponding interpolating polynomial in f0*;* 1g, we get a vector commitment with quasi-linear time for pre-computing all proofs. Furthermore, the homomorphic properties along with the tensor structure of multivariate polynomials allow to eciently (in logarithmic time) update all proofs after a position update. Thus, the resulting construction is a maintainable vector commitment scheme.

$$ {0,1}^{\nu} $$

$$ {0,1}^{\nu} $$

We extend these techniques to construct a multi-variate vector commitment scheme with the same properties while reducing proof size. Specically, we observe that evaluating all openings in any set of the form for small has lower amortized cost than computing the evaluations individually. Using of size ‘ instead of 2 -or equivalently using a low degree instead of a multilinear encoding- results in smaller proof size. Concretely, the proof size depends on the dimension of the hypercube. Setting ‘ = O(1) to avoid a blowup in the prover’s computation results in proof size roughly log_‘m instead of log₂ m, reducing the proof size by a constant factor.

$$ \Sigma^{\nu} $$

$$ \ell=O(1) $$

$$ \log_{\ell}m $$

$$ m, $$

We next describe the high level idea of the construction. First, x an alphabet F of size ‘ and consider the hypercube. Assume (w.l.o.g.) = f0*;:::;‘* 1g so that we can encode indices of vectors in ‘-ary.

$$ \Sigma^{\nu} $$

$$ \Sigma\subseteq\mathbb{F} $$

$$ (\mathrm {w}. \mathrm {l}. \mathrm {o}. \mathrm {g}.) \Sigma = {0, \dots , \ell - 1 } $$

‘ Now, we can encode a vector v 2 F by considering the (unique) low degree interpolating polynomial p(X) of v, that is, the-variate polynomial of individual degree less than ‘ such that for all 2, p() = v. This corresponds to position i with ‘-ary representation ()_‘. Computing all opening proofs corresponds to evaluating and proving evaluations of p(X) in the hypercube. To compute these evaluations in quasi-linear (instead of quadratic) time we rely on the following lemma which is implicit in the computation of the H_j(X) polynomials of PST.

$$ \mathbf{v}\in\mathbb{F}^{\ell^{\nu}} $$

$$ p(\mathbf{X}) $$

$$ \sigma,\in,\Sigma^{\nu} $$

$$ p(\pmb{\sigma}),=,v_{\pmb{\sigma}} $$

$$ (\sigma)_{\ell} $$

$$ p(\mathbf{X}) $$

$$ \Sigma^{\nu} $$

$$ H_{j}(\mathbf{X}) $$

Lemma 1. Let F be a subset of F*. Also, let p*(X ;:::;X₁) 2 F[X ;:::;X₁] be a polynomial in variables and p (X₁;:::;X₁) 2 F[X₁;:::;X₁] be a polynomial in 1 variables. Then, for all 2, p(;X₁:::;X₁) = p (X₁:::;X₁) i there exist a polynomial H(X ;:::;X₁) such that

$$ \Sigma\ subseteq\ \mathbb{F} $$

$$ p!(X_{\nu},\ldots,X_{1}),\in,\mathbb{F}![X_{\nu},\ldots,X_{1}] $$

$$ p_{\sigma}(X_{\nu-1},\ldots,X_{1})\in\mathbb{F}[X_{\nu-1},\ldots,X_{1}] $$

$$ \nu-1 $$

$$ \sigma\in\Sigma $$

$$ p(\sigma,X_{\nu-1}\ldots,X_{1})=p_{\sigma}(X_{\nu-1}\ldots,X_{1}) $$

$$ H(X_{\nu},\ldots,X_{1}) $$

$$ p(X_{\nu},\ldots,X_{1})-p_{\sigma}(X_{\nu-1},\ldots,X_{1})=H(X_{\nu},\ldots,X_{1})(X_{\nu}-\sigma) $$

(12)

To open the polynomial at = (;:::;₁) 2, the prover can compute the polynomials p(;X₁; :::;X₁);:::;p(;:::;₁) and compute \proof" polynomials H (X);:::;H₁(X). That is, for 1 j the following equations hold:

$$ \pm\ \sigma $$

$$ p(\sigma_{\nu},X_{\nu-1} $$

$$ \ldots,X_{1}),\ldots,p(\sigma_{\nu},\ldots,\sigma_{1}) $$

$$ H_{\nu}(\mathbf{X}),\ldots,H_{1}(\mathbf{X}) $$

$$ 1\leq j\leq\nu $$

$$ p(\sigma_{\mid j+1},X_{j},\ldots,X_{1})-p(\sigma_{\mid j+1},\sigma_{j},X_{j-1},\ldots,X_{1})=H_{j}(\mathbf{X})(X_{j}-\sigma_{j}) $$

Summing all the claims, we derive the PST verication equation. Note that the polynomial H_j(X) is independent of the variables X ;:::;X_j+1. Hence, each iteration is cheaper than the previous one.

$$ H_{j}(\mathbf{X}) $$

$$ X_{\nu},\ldots,X_{j+1} $$

The interesting part is that proofs for dierent positions share elements. Consider a polynomial H(X) asserting p(;X ;:::;X₁) p (X₁;:::;X₁). This element will be part of the proof for all elements 2 whose rst component is =. We utilize this fact to get a smaller amortized cost for evaluating all \proof" polynomials in the hypercube.

$$ H(\mathbf{X}) $$

$$ \sigma\in\Sigma^{\nu} $$

$$ p(\sigma,X_{\nu},\ldots,X_{1})\ {-}p_{\sigma}(X_{\nu-1},\ldots,X_{1}) $$

$$ \sigma_{\nu}=\sigma $$

The tensor structure of the multivariate polynomial allows to express the openings in the hypercube as a tree. Each node of the tree corresponds to a partial evaluation of p. A proof polynomial H is associated with each of them. We demonstrate this in Fig. 4.

$$ p(1,2,0)=v_{1,2,0}\qquad p(1,2,1)=v_{1,2,1}\qquad p(1,2,2)=v_{1,2,2}\qquad p(1,2,3)=v_{1,2,3} $$

Fig. 4: Tree structure for polynomials in 3 variables with individual degree at most 3. The dimension of the committed 3 vectors with these parameters is 4 = 64. We follow the path until we reach the leafs prexed with (1*;*2). Note that each polynomial is an encoding of the leafs of the sub-tree it denes.

$$ 4^{3}=64 $$

Finally, when using the Lagrange basis to encode polynomials, the interpolating polynomial p(X) corresponding to v becomes (X ;:::;X₁) v. Furthermore, each node of the tree is of the form (X_i;:::;X₁) v⁰ where v⁰ is the subvector of v corresponding to the leaf descendants of the node.

$$ p(\mathbf{X}) $$

$$ \lambda(X_{\nu},\ldots,X_{1})\cdot\mathbf{v} $$

$$ \lambda(X_{i},\ldots,X_{1})\ \ \mathbf{v^{\prime}} $$

$$ \mathbf{v}^{\prime} $$

Finally, we demonstrate the new tree structure of the commitment after we modify the leaf elements with committed values.

D.2 Completeness of UVTree construction.

To prove completeness of the UVTree construction, we start by proving the fundamental relation between parent and children nodes.

Lemma 2. With the notation introduced in section 8.3,

$$ \mathsf{C}{\ {mathbf b{{|j}}}}=K_{{\mathbf{b}{{|j}}}}\left(\mathsf{C}{0{{\mathbf{b}{|j}}}}[t{1{{\mathbf{b}{|j}}}}(\tau)]{1}-\mathsf{C}{1{{\mathbf{b}{|j}}}}[t_{0{{\mathbf{b}{|j}}}}(\tau)]{1}\right) $$

(13)

$$ =K_{\mathbf{b}{|j}}(\mathsf{C}{\mathbf{0b}{|j}}-\mathsf{C}{\mathbf{1b}{|j}})\tau^{\frac{m}{2^{j+1}}}+K{\mathbf{b}{|j}}(\mathsf{C}{\mathbf{0b}{|j}}+\mathsf{C}{\mathbf{1b}_{|j}}) $$

)(14)

$$ =K_{\mathbf{b}{|j}}(\mathsf{C}{\ \ \mathbf{0}\mathbf{b}{|j}}-\mathsf{C}{\ \ \mathbf{1}\mathbf{b}{|j}})[t{\ \ \mathbf{1}\mathbf{b}{|j}}(\tau)]{1}+\mathsf{C}{\ \ \mathbf mathbf{1}\mathbf{b}{|j}} $$

(15)

$$ =K_{\ {bf\sf{b}}{|j}}({\sf{C}}{0{\bf{sf}b}{|j}}-{\sf{C}}{1{\bf{}}{b j}})[t{0{\bf{}{}}}{{\ \ {\bf{b}}{|j}}}(\tau)]{1}+{\sf{C}}{0{\bf{sf b}}_{|j j}}.}} $$

(16)

Fig. 5: Demonstration of the tree structure of a commitment. Leaf nodes are commitments to k-dimensional vectors for an arbitrary vector commitment scheme. Each node is a commitment to its children under a Lagrange based key. 3 The message space of the scheme is k 2.

$$ k\cdot2^{3} $$

Proof. Consider the relation as the evaluations of polynomials in formal variable X. We will show that the m above relation holds as a polynomial identity. The polynomial associated to C^bjjhas degree^j+11, and so 2 do the polynomials in the right hand side. Therefore, to show the identity holds we just need to see that the 0bjj1bjjm 0bjj two polynomials coincide in H [ H, which is a set of size_j+1. If we evaluate at 2 H, 2

$$ \mathbb{C}{\mathrm{b}{|mid}{j}} $$

$$ \ textstyle\frac{m}{2^{j+1}}-1 $$

$$ \mathbb{H}^{0\mathbf{b}{|j}}\cup\mathbb{H}^{1\mathbf{b}{|j}} $$

$$ \eta\in\mathbb{H}^{0\mathbf{b}_{|j}} $$

$$ t_{1b_{|j}}(\eta)=K_{\mathbf{b}_{|j}} $$

$$ \frac{m}{2j+1} $$

and

$$ t_{0b_{|j}}(\eta)=-K_{\mathbf{b}_{|j}} $$

which concludes the proof, as by denition, C_bjjand C_vbjjtake the same value in the proof.

$$ \mathbb{C}{\mathrm{b}{\mathrm j}} $$

$$ \mathsf{C}{v\mathbf{b}{\mid j}} $$

Next we show completeness of UVTree construction.

Theorem 10. Construction UVTree is complete.

Proof. Consider an honest execution of Open algorithm. The last two steps verify. Indeed, for the second test, it is enough to note that C_bis a commitment to a vector b such that v_bf = y and the verication equation equation is a test for asserting this inner product. The third equation follows by construction. It remains to show that the rst test passes as well.

$$ C_{\mathbf{b}} $$

$$ \mathbf{v_{b}}\cdot\mathbf{f}=y $$

By the above lemma we have that for all 0 j 1

$$ 0\leq j\leq\nu-1 $$

$$ \mathsf{G}{\mathbf{b}{|j}}=K_{\mathbf{b}{|j}}(\mathsf{C}{0\mathbf{b}{|j}}-\mathsf{C}{1\mathbf{b}{|j}})t{b_{j+1}\mathbf{b}{|j}}(\tau)+\mathsf{C}{b_{j+1}\mathbf{b}{|j}}=H{|\mathbf{b}{j}}t{b_{j+1}\mathbf{b}{|j}}(\tau)+\mathsf{C}{b_{j+1}\mathbf{b}_{|j}} $$

or equivalently

$$ \mathsf{C}{\mathbf{b}{|j}}-\mathsf{C}{b{j+1}\mathbf{b}{|j}}=H{\mathbf{b}{|j}}t{\mathbf{b}_{|j+1}}(\tau) $$

Also, by construction,

$$ \mathsf{C}-\mathsf{C}{b{0}}=H t_{b_{0}}(\tau) $$

Summing all these equation we get

$$ \mathsf{C}C-\mathsf{C_{b}}=H t_{0}(\tau)+\sum_{j=0}^{\nu-1}H_{\mathbf{b}{|j}}t{\mathbf{b}_{|j+1}}(\tau) $$

which corresponds to the rst verication test.

The (m 1*;m*)-discrete logarithm assumption states it is nd to compute the discrete logarithm of some element when m 1 powers are given in G₁ and m in G₂.

$$ \ m-1,m) $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

Theorem 11. In the AGM, the construction is sound under the (m 1*;m*)-discrete logarithm assumption and the (m 1*;m*)-strong BDH Assumption.

$$ (m-1,m) $$

m 1 Proof. (sketch) Since the adversary is algebraic, there exist coecients ai2 F that can be extracted Pm from the adversary and such that C_b=_i=1a_{i i}(). That is, C_bis a polynomial of degree at most m 1 (the powers in the SRS) evaluated at, and similarly for the other terms of the proof. For the reasons argued b H before, C and C_bmust correspond to the evaluation of two polynomials that agree on t. On the other hand, because of the degree check either C_bis the evaluation in of some polynomial of degree at most 2 ¹ or there is some non-trivial relation between powers of in the group that allows to recover the break the discrete logarithm assumption.

$$ a_{i},\in,\mathbb{F}^{m-1} $$

$$ \mathsf{C}{\mathbf{b}}=\sum{i=1}^{m}a_{i}\lambda_{i}(\tau) $$

$$ C_{\mathbf{b}} $$

$$ m-1 $$

$$ \tau $$

$$ C_{\mathbf{b}} $$

$$ t^{\mathbb{H}^{\mathbf{b}}} $$

$$ C_{\mathbf{b}} $$

$$ \tau $$

$$ 2^{\kappa}-1 $$

Maintanability As mentioned, naive computation of all partial proofs takes time O(mlog² m)

H However, one can do better: using FFT compute the 2 coecients of C_b(X) = (X)v_bin the monomial +1 basis (O(2 2) eld operations) and traverse the tree from leaf to root to compute the rest of the values. Using this basis, each level can be computed using O(m) operations. As an illustration, having C₀(X);C₁(X) 1m1 in the monomial basis, we can compute [H]¹;C by computing C(X) = (C₀(X) C₁(X))X²+ (C₀(X) ² 2 C₁(X)); encoding them in G₁ using roughly m operations. In total, we need O(mlogm) eld and group operations. Updating all proofs needs O() operations. It works as in the multivariate case, exploiting that a commitment to e_ihas only O() non-zero proof elements.

$$ O(m\log^{2}m) $$

$$ \mathrm{F F T} $$

$$ 2^{\kappa} $$

$$ \mathcal{C}{\mathbf{b}}(X)=\lambda^{\mathbb{H}}(X)\mathbf{v{b}} $$

$$ (O(2^{\nu+1}!\cdot!2^{\kappa}) $$

$$ O(m) $$

$$ C_{0}(X),C_{1}(X) $$

$$ [H]_{1},\mathsf{C} $$

$$ Ctextstyle C(X)=\frac{1}{2}(C_{0}(X)-C_{1}(X))X^{\frac{m}{2}}+\frac{1}{2}(C_{0}(X)-\frac{1}{2}) $$

$$ C_{1}(X)) $$

$$ \mathbb{G}_{1} $$

$$ O(\nu) $$

$$ \delta\mathbf{e}_{i} $$

$$ O(\nu) $$

D.3 Lagrange basis IP for Cosets of Roots of Unity

We argue the construction of Section 5.2 of IP vector commitments using the Lagrange basis can be implemi i s s s+2 s+(r 1)2 i mented when using a coset of size r =ithat we denote! Hr= f!;!;:::;! g, for 0 s < 2 2 as ⁱnterpolation set, instead of the group of roots of unity H.

$$ r=\frac{m}{2^{i}} $$

$$ \omega^{s}\mathbb{H}_{r}=\big{\omega^{s},\omega^{s+2^{i}},\dots,\omega^{s+\breve{(r-1)2}{}^{i}}\big} $$

$$ 0\leq s<2^{i} $$

k s Claim 1. For all i = 1*;:::;2,the jth Lagrange interpolation polynomial of set!* H_ri^s

$$ i=1,\ldots,2^{k} $$

$$ \omega^{s}\mathbb{H}_{r} $$

$$ \lambda_{j}^{s,r}(X)=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\frac{X^{r}-\omega^{s r}}{X-\omega^{s+(j-1)2^{i}}} $$

r sr s Proof. Note that X! is the vanishing polynomial of*!* H_r. Indeed, it has degree r and for every i s_{+(j 1)2} ! we have

$$ X^{r}\mathrm{-}\omega^{s r} $$

$$ \omega^{s}\mathbb{H}_{r} $$

$$ \omega^{s+(j-1)2^{i}} $$

$$ (\omega^{s+(j-1)2^{i}})^{r}-\omega^{s r}=(\omega^{s r}(\omega^{(j-1)2^{i}})^{r})-\omega^{s r}=\omega^{s r}-\omega^{s r}=0. $$

Thus,

$$ X^{r}-\omega^{s r}=\prod_{k=1}^{r}(X-\omega^{s+(k-1)2^{i}})\mathrm{a n d}\frac{X^{r}-\omega^{s r}}{X-\omega^{s+(j-1)2^{i}}}=\prod_{k\neq j}^{r}(X-\omega^{s+(k-1)2^{i}}). $$

Then,

$$ \lambda_{j}^{s,r}(X)=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\frac{X^{r}-\omega^{s r}}{X-\omega^{s+(j-1)2^{i}}}=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\prod_{k\neq j j}^{r}(X-\omega^{s+(k-1)2^{i}}). $$

$$ \lambda_{j}^{s,k}(\omega^{s+(k-1)2^{i}}) $$

$$ k\neq j $$

s;ki s+(k 1)2 It is clear from the above that_j(!) for all k 6= j, now

$$ \begin{aligned}{\lambda_{j}^{s,k}(\omega^{s+(j-1)2^{i}})}&{{}=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\prod_{k\neq j}^{r}(\omega^{s+(j-1)2^{i}}-\omega^{s+(k-1)2^{i}})}\ {}&{{}=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\omega^{s(r-1)}\prod_{k\neq j}^{r}(\omega^{(j-1)2^{i}}-\omega^{(k-1)2^{i}})}\ {}&{{}=\frac{\omega^{(j-1)2^{i}}}{r}\prod_{k\neq j}^{r}(\omega^{(j-1)2^{i}}-\omega^{(k-1)2^{i}})}\ \end{aligned} $$

(j 1)2iQ i i ! _r (_j 1)2 (k 1)2 Since H_ris a group of roots of unity,^k6=^j(!!) is the lagrange polynomial r is;k (j 1)2 correspondⁱng to*!, evaluated at the same point and thus the equation above equals 1. That is_j(X) i s s+(j 1)2 is a polynomial of degree r 1 such that vanishes at all element^s in!* H_rexcept for*!* where takes s value 1 and we conclude is the jth lagrange polynomial of*!* H_r. ut

$$ \mathbb{H}_{r} $$

$$ \frac{\omega^{(j-1)2^{i}}}{r}\textstyle\prod_{k\neq j}^{r}\bigl(\omega^{(j-1)2^{i}}\ {-}\ \omega^{(k-1)2^{i}}\bigr) $$

$$ \omega^{(j-1)2^{i}} $$

$$ \lambda_{j}^{s,k}(X) $$

$$ r-1 $$

$$ \omega^{s}\mathbb{H}_{r} $$

$$ \omega^{s+(j-1)2^{i}} $$

$$ \omega^{s}\mathbb{H}_{r} $$

s;k Claim 2._j(0) = r.

$$ \lambda_{j}^{s,k}(0)=-r $$

Proof. Recall that as H_ris a set of roots of unity of size r, all its the Lagrange polynomials take value r when evaluated in 0. Then,

$$ \mathbb{H}_{r} $$

$$ r $$

$$ -r $$

$$ \lambda_{j}^{s,r}(0)=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\prod_{k\neq j}^{r}(0-\omega^{s+(k-1)2^{i}})=\frac{\omega^{(j-1)2^{i}}}{r\omega^{s(r-1)}}\omega^{s(r-1)}\prod_{k\neq j}^{r}(0-\omega^{(k-1)2^{i}}). $$

equals the jth Lagrange polynomial of H_revaluated in zero.

$$ \mathbb{H}_{\tau} $$

Thus, we conclude that the inner product construction of Section 5.2 works when the Lagrange basis is s chosen using any coset*!* H_kof a ^subgroup of roots of unity H_rof size r.

$$ \omega^{s}\mathbb{H}_{k} $$

$$ \mathbb{H}_{r} $$