# Linear-map Vector Commitments and their Practical Applications
?
Matteo Campanelli¹, Anca Nitulescu¹, Carla Rafols², Alexandros Zacharakis², and Arantxa Zapico².
1
Protocol Labs *f*matteo, anca*g*@protocol.ai
2
Universitat Pompeu Fabra *f*carla.rafols, alexandros.zacharakis, arantxa.zapico*g*@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) from 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*i6= *v*i0). 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.
4
For the applications considered in this work, hiding properties are not necessary. In particular our commitments
are deterministic.
5
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
openingffor 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
6
https://developer.mozilla.org/en-US/docs/Web/HTTP/Link_prefetching_FAQ
7
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 long 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,
$$
8
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.
---
| VC Scheme | Setup | Aggregation | Updates | | Functional Opening | Special Sets Opening(size n) |
| --- | --- | --- | --- | --- | --- | --- |
| PoS aggSVC[6] | Trusted | IncrementalSame-Com | hint | RSA | SVC | O(n) |
| Pointproofs[15] | Trusted | One-hopCross-Com | key | pairings | × | O(n) |
| StatelessaggSVC[29] | Trusted | One-hopSame-Com | key | pairings | SVC | O(1) |
| Our LagrangeLVC | Reusable | UnboundedCross-Com | key | AGM | LVC | O(1) |
| Our MonomialLVC | Reusable | UnboundedCross-Com | keyless | AGM | LVC | O(1) |
$$
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*i*2* F. We use ei*2* F to denote
the vectors of the canonical basis, more concretely eiis 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 denote 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 = *f*h₁*;:::;*hm*g* 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 *t*k(*X*) = (*X* hj), the vanishing polynomial of a subset *f*hjgj2JH and *t*kc (*X*) =
Qj2Jk k
j=2J(*X* hj).
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₂*;* GT*;e*) with additive notation
such that *p* is prime, so F = Fpis a eld. G₁*;*G₂ are cyclic (additive) groups of prime order *p*. We use the
notation [*a*]1*;* [*b*]2*;* [*c*]tfor elements in G₁*;*G₂ and GTrespectively. *e* : G₁ G₂*!* GTis a bilinear asymmetric
map (pairing), which means that *8a;b 2* Zp*; e*([*a*]1*;* [*b*]2) := [*ab*]t*:* We implicitly have that [1]t:= *e*([1]1*;*[1]2)
generates GT. We use [*a*]1;2to refer to 2 group elements [*a*]1*2* G₁*;* [*a*]*2*2 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₂*;* GT*;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*:::*[*x*m]1*2* G₁. Then, for every new group
Pm
element [*z*]1*2* G₁ that the adversary outputs, it must also output *z₁ :::z*m*2* F such that [*z*]1=i=1[*z*i*x*i]1.
$$
[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 prooffthat *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*, and 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 proofs1,2
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* and all vectors v *2M*,
and (vrk*;*prk) LVC*:* KeyGen(1*; F*), (C*;*aux) LVC*:* Commit(prk*;*v), if1LVC*:* 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*),
if1LVC*:* Open(prk*;*aux₁*;f;* y₁) and2LVC*:* 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 be1=2+1 3, for1= H(C*; f*(*f₂;*y₂)*;* (*f₃;*y₃)*g*). In a second step, we can aggregate a
proof that *f₁*(v) = y₁, by performing2=1+2 1, for2= H(C*;* (*f₁;*y₁)*;*1). At the verication step, the
verier would reconstruct the coecients of each initial proof in2. For instance,1= 1,2=1 2,3=2.
Then, the verier can run the LVC*:* Vf algorithm to check whether2=1+2 1=1+1 2 2+2 3
is a valid proof that function *f* = *f₁* +1 2*f₂* +2*f₃* evaluated at the vector committed in C opens to
*y* = *y₁* +1 2*y₂* +2*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*;* yj*g*=1. 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*0*;* 1*g*
$$
\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*f*0*;y*0 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*f*0*;y*0 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{}{~\ nexists~a.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⁰1*;:::;*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*upkj*g*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)
$$
10
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*f*0*;y*0;*)*!* :
Compute = H(C*;T*f;y*;T*f*0*;y*0*)
0
Output = +
LVC*:* Vf(vrk*;* C*;T*f;y) *T*f*0*;y*0;*)*! b*
Return *b* LVC*:* Vf vrk*;* C*;f;y ;* where:
{ let leaf₁*;:::;* leaf‘be all the leaves in *T*f;y) *T*f*0*;y*0*.
{ recall each leafiis of the form (C*;f*i*;* yi)
{ For each *i* leti:= (leafi) 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*; ;T*f;y*;T*f0;y0 be an output of *A* such that LVC*:* Vf(vrk*;* C*;T*f;y) *T*f0*;*y0;)=1.
P P
By construction this implies IP*:* Vf vrk*;* C*;*i i*f*i*;*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 iyi, *f*(X) =i i*f*i(X)
PtPt
then there exists a such thati*f*i(a) =iyi.
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 coecientsido not depend on yi*;f*i. And by the Schwartz-Zippel lemma,
except with probability *r=*F, *f*i(a) = yifor 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*f*0*;y*0;*)*!* :
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*f*0*;y*0*. We add to each leaf leafiand additional subindex
*j* that refers to which commitment the proof in leafijcorresponds 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 leafijis of the form (*C*j*;f*i*;* yi)
$$
\ {mathsf i f}_{i j}
$$
$$
(C_{j},f_{i},\mathbf{y}_{i})
$$
{ For each *i* letij:= (leafij) 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*;* Cj*;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*!* F*g*, 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* Fpso 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 setito be the proof that *f*i(v) = fiv = *y*i,
n
an aggregation of *f*i*g*i=1is 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*; f*f*;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*; f*fi*;y*i*g*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*; f*fi*;y*i*g*i=1*;*)*! b* :
n
Compute = H(C*; f*f*;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 fias 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.RuniIP*:* Open(prk*;*aux*;* fi*;y*i) 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*i*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*; f*fi*;y*i*g*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 + ej.
$$
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 + ej).
$$
\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.
$$
11
Naturally, this can be seen as a particular case of unbounded aggregation.
12
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 + etwe can compute a commitment
to the new vector v⁰ as C⁰ = (C + C^) where (C^*;*aux^ ) LVC*:* Commit(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*( et). The resulting = + ^ corresponds to the opening of the sum
*f*(v⁰) = *f*(v) + *f*(e) with 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*; f*upkj*g*j=1):
1.Additionally generate public update keys upk:
2.SetuijIP*:* Open(prk*;*auxj*;* ei*;u*ij= eiej)*; 8i;j 2* [*m*]
m
3.Dene upkj= *f*uij*g*i=1for all *j 2* [*m*]
m
4.Output (prk*;*vrk*; f*upki*g*i=1).
IP*:* UpdCom(prk*;* C*;t;*)*!* C⁰ :
1.Set C^ IP*:* Commit(prk*;* e).
t
2.Output C⁰ =C+ C^.
0
IP*:* UpdOpen(upkt*;t;;*C*;* f*;y;*)*!* :
m
1.Parse upkt= *f*uitgi=1
Pm
2.Compute ^ =i=1*f*i uit
0
3.Set = + ^ as proof for *y⁰* = *y* + f et
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*!* F*g*. 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* Fp.
$$
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=1*a*i*X :*
$$
\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₂*;* GT*;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;2*g*i=01*;* vrk = []1*;* []2.
Pi=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*:* Commit(prk*;*a)*!* (Ca*;*aux): Compute Ca=i=1*a*i[]1and output (Ca*;*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)1 1 1
$$
\pi=\left([R(\tau)]_{1},[H(\tau)]_{1},[\hat{R}(\tau)]_{1}\right)
$$
Pm
m i^]
IP: Vf(vrk*;* Ca*;* b*;y;*)*!* 0*=*1 :Compute Cb=i=1*b*i[]1, parse = ([*R*]1*;* [*H*]1*;* [*R*1) and output 1 if
and only if
m 1 m
*e* C*;* C *e y*[]*;*[1] = *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*]1is 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) andcIP*:* 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 andaIP*:* 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 Ca*; f*bk*;y*k*;*bk*g A* (prk*;*vrk) such that *8k 2* [*K*] : IP*:* Vf(vrk*;* Ca*;* bk*;y*k*;*bk) = 1 and
k2[K]
m
there is no a *2* F s. t. *8k 2* [*K*] : a bk= *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 1 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=j*F*j*, *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*) =i=1ai*X*. Then,
from the rst veric*a*tion equation in both of the proofsbandcwe 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 polynomial Pb(*X*) isi=1aibiyb= 0.
Pm
m 1
Same holds for the coecient of *X* in polynomial *P*c(*X*):i=1*a*i*c*i*y*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
$$
$$
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()]1.
$$
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=1ai*X*. Still, 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 eiei= 1 or eiej= 0. In our construction for encodings in the monomial basis,
a proof that eiei= 1 consists on *R*(*X*) = *H*(*X*) = 0. On the other hand, to prove that eiej= 0 for *i 6*= *j*
m+i j i j
the proof is (the evaluation in the group of) either *R*(*X*) = *X* if *j > i*, or *H*(*X*) = *X* if *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 *f*i(*X*)*g*i=1over a multiplicative group H = fh₁*;:::;*hm*g* of size
P*m*
m
m in F we encode a vector a *2* F as a polynomial *a*(*X*) =i=1*a*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 = *f*hi*g*i=1consists oof the roots of unity of order m, theni(hi) = 1 andi(hj) = 0
Q*m*
for *i 6*= *j* and for the vanishing polynomial *t*(*X*) =i=1(*X* hi) 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}):
$$
IP*m*
Generate group description gk = (*p;* G₁*;*G₂*;* GT*;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 = *f*h₁*;:::;*hm*g* 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;2*g*i=1*; f*[i()]1*g*i=1*m* 1*;* []2and vrk = [1]1*;*2; []2*;* [i()]2.
Pi=1
m
IP: Commit(prk*;*a)*!* (Ca*;*aux): Compute Ca=i=1*a*i[i()]1and output (Ca*;*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)1 1 1
m
IP*:* Vf(vrk*;* Ca*;* b*;y;*)*!* 0*=*1 :Calculate Cb=i=1*b*i[i()]2
$$
{\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 andaIP*:* 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 Ca*; f*bk*;y*k*;*bk*g A* (prk*;*vrk) such that *8k 2* [*K*] : IP*:* Vf(vrk*;* Ca*;* bk*;y*k*;*bk) = 1 and
k2[K]
m
there is no a *2* F s. t. *8k 2* [*K*] : a bk= *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 1 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=j*F*j*, 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*) =i=1ai*X*. Then,
from the rst veric*a*tion equation in both of the proofsbandcwe 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})mpliesi=1*a*i*b*i i(0) *m y*b= 0. Same reasoning leads to
Pm
1 1
i=1*a*i*c*i i(0) *m* y = 0. As H is a *m*ultiplicative subgroup,i(0) = m for all *i 2* [m] and thus
P*m*Pmc
i=1*a*i*b*i= *y*bandi=1*a*i*c*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
P*m*P: we can extract a vectorm
m+*k*+1 m 0 0 m 0
a *2* F and set *a*(*X*) =i=1*a*i i(*X*) + *X a* (*X*) for deg(*a*) = *k*. Then,i=1*b*i i(*X*) *X a* (*X*), if
not zero, is contained in *H*(*X*). Indeed, as its degree is 2*m* + *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 eiei= 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 eiej= 0 for *i 6*= *j*
is [*H*()]1, 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* hi)*g*i=1, so the verier can reconstruct the one ofi(*X*)j(*X*)*=t*(*X*)
from there, requiring only 2*m* 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*n*g* 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 vI= (*v*i)i2Iby
aggregating dierent inner product proofs for vectors eikfor *i*k*2 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 = (*c*i)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=1*c*i*X* 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,
Pi+k
~(s i ~ = [ ~( ~ m i
*c*omputes *C X*) =s=ic~s*X* and C *C*)]1and checks whether *e*(C C*;* []1) = *e*([*R*]1*;*[1]2) +
m+k
*e*([*H*]1*;* []2).
$$
\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)s()]1*;* [*H*s()]1such 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*]1= [*R*i()]1and [*H*]1= [*H*i+k()]1, 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}})k=1 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 1
The verier will receiveI= ([*R*]1*;* [*H*]1*;* [*R*1), compute *y* =k=1*v*ik, and check as before *e*([*R*]1*;* []2) =
*e*([*R*^]*;*[1]) and
1 2
!
$$
\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).
$$
Pn
k 1 m ik
Note that verier’s work is dominated by the computation ofk=1[]2, 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-assign*!*, and thus our verier now needs to computek=1[(*X*)]2=i2I[(*X*)]2.
$$
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 computei2I(*X*) to constant. Note that the verier
k;s;n
s 1 s
cannot compute (1 (X)), so we multiply all the terms of the equation by 1 (*X*). I.e, the verier
P
m i
computes *y* =i2I*y*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* hi) (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 = *f*1*;!;!;:::;! g* group of roots of unity where *m* = 2, let Hkbe 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]2= *e* [*H*]1*;* [*x*]2*!*.
$$
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 Cf;I, claimed to be a commitment to f cI,
for some linear function f applied to the vector cI= (*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}
$$
13
https://github.com/filecoin-project/paired
14
Our code is available at https://github.com/matteocam/lvc-mon-rust.
15
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
25
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
16 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).
17
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 8*j*F*j* 1*j*G₁*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 *f*vj*g2* 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]1vj, where [r]1*2* G1
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 vj. 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 = *f*0*;* 1*g*
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 = (*;:::;*1) 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} =
$$
18
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*;:::;*1-as it would do in the simple
PST case- and end up with a polynomial *q*(R) = *p*(*;*R) = R vj. 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]1
corresponds to the leaf commitment at position and can be opened by employing the Open algorithm of
the leaf commitment scheme with key [r]1.
$$
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
(*;:::;*1) *2*, we denoteji= (*;:::;*i) *2*. For v = (v)2with v *2* F and1*2*
we denote with vk; 1the vector (v1; 2)22i, that is, the concatenation of vectors vjwhose m-ary
representation of the index *j* is prexed with1. Finally, we denote with;‘the-variate *m*onomial basis
of individual degree less than evaluated at*;:::;*1. 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;k*f* : 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.*;:::;*1F
$$
\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)]1= []1v
$$
{\hat{\mathsf{C}}}=[p(\mathbf{\tau},\mathbf{r})]_{1}=[\mathbf{\lambda}]_{1}\cdot\mathbf{v}
$$
3.Output C*;*aux = *f*aux *g*2*;* 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⁰*(vi) 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*+1(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) vjj
$$
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]1= [*H*j(j*;:::;*1*;*r)]1
$$
[H_{j}]_{1}=[H_{j}(\tau_{j},\dots,\tau_{1},\mathbf{r})]_{1}
$$
19
We use linear forms for simplicity, one could also consider general linear functions.
---
^ ‘ 1 ‘ 1
5.Compute C = [1r]1v
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⁰ 2F*p;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;k*in 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⁰*(vi) for some *i* = ()‘.
Also, by construction, the low degree test always succeeds. It remains to show that the rst test outputs 1.
>
Let *p*+1(*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 (*;:::;*1) 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*]1*;:::;*[*H₁*]1*;* 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)1. 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*;* yd*;*dfor *d 2f*1*;* 2*g*. Note the only way that the functions
0 0
are inconsistent is if *f₁*(v) = *f₁*(vi) and *f²*(v) = *f₂*(vi) 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₁*(vi) and *f₂*(v) = *f₂*(vi) 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⁰*1*;f⁰*2are 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*;:::;*[]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]1*;*vk⁰) LVC⁰*:* KeyGen(1*; F*p;k) along with the discrete logarithms of [r]120
$$
(\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]1= [j+j]1for randomj.
$$
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*;* []1
‘ 1 ‘ 1
and []2*;:::;*[1]2*;* []2. Note that this step is ecient since any element (1*;:::;*) and in
is a polynomial of total degree at most (*‘* 1) on variables*j*=*j*so 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 [ (*;:::;*1)]1.
$$
\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*; ;:::;*1are 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]1. 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*i*H*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)
$$
20
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, 0*;* (*v v*) *e*(j=1 j[*z*j]1*;*[1]2) 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₁*;*1), (C₂*;f;* y₂*;*2) 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₂*;*1+2) 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₂*;*1+2) 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*]1*;:::;*[*H₁*]1*;* 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*1(X*;*R) = *p*(1*;* 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]1. One can simply write the polynomial *p*j*p*j 1as 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 jin 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*(log*m*) 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 *m*th 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* =iis Hr= *f*1*;!;* (*!*)*;:::;*
2
i
2 r 1 r
(*!*) *g* and the associated vanishing polynomial is *X* 1. Further, 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*!* Hris *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 = []1v, where = ([1()]1*;:::;*[m()]1), and the polynomials *f*j(*X*)*g* are the
Lagrange basis interpolation polynomials for H. The two children will be C₀ = [0]1v₀ and C₁ = [1]1v₁,
which are commitments to v₀ and v₁ with keys0and1of half the size. The two children of C₀ will be
+1
C₀₀ = [10]1v₁₀*;*C₁₀ = [10]1v₁₀ and so on. The leaves are commitments Cb, b = (*b ;:::;b₀*) *2f*0*;* 1*g* to
vectors of size 2. For any leaf index b = (*b ;:::;b₀*), we denote bjj= (*b*j*:::b₀*) the sux²¹ of size *j*. Note
that Cbjjfor *j* = 0*;:::;* 1 denotes all the commitments from the root to the leaf Cb.
$$
\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
vb1 b0indicates 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₀*) *2f*0*;* 1*g*, H =*!* Hr, for
Pj
i m
*s* =i=0*b*i2 and *r* =j+1.
2
$$
\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 fo*r* node b isjj= [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*)vb,
$$
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}
$$
21
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 Cb, the idea is to implicitly show from root to leaf that Cbjj
bjj+1
Cbjj+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(C0bjjC1bjj), one
can write CbjjCbjj+1= [Hbjjtbjj+1()]1. If H = (C₀ C₁)*=*2, going iteratively from the root replacing the
commi*t*ments 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*()]1to Cb, 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*;* Cbas 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 Cbthat 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*;* Cbas
b
polynomials agree in H and the inner product that Cbhas 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 = []1v 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) = vbf 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 Cbjj= []1vbjj.
$$
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*]1= (C₀ C₁)*=*2, and for any 0 *j* 1, compute *K*b= 2*!*2. Then
jj
dene [*H*bjj]1= *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}}}
$$
22
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 1 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 C*f*=i=1fi[i()]2.
$$
\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 *2f*0*;* 1*g* (*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*]1*;* [*H*bjj]1*g*j=01), (*f*[*H⁰*]1*;* [*H*b]1*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* hb). This is a polynomial of degree less than *m* 1 since hbis a root of *t*bjj(*X*)
for any 0 *j*. [*p*j]1= [*p*j()]1can 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 Cbagree on
b
H, while the IP part guarantees that cbis of the right degree, so it guarantees uniqueness of cb. 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*(*m*log² *m*) but this can be reduced to
time *O*(*m*log*m*) 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)
$$
23
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
*f*Zero-Knowledge*g* 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*i*that*
*the value v*i*is 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 2f*0*;* 1*g*: *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.
$$
24
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;*vI)*!*I: *Takes as input* prk*,* aux*, a set of index I* [*m*] *and values* vI= *fv*i*g*i2I*and*
*outputs a proof*I*that v*i*is 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 2f*0*;* 1*g* : *Takes as input* vrk*,* C*, I, a vector* y = *fy*i*g*i2I*and*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 Dk, the server
responds with the data and a logarithmic-size path consisting of the nodes from Dkuntil the root, and the
client can then verify the authenticity of Dkin 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*(log*n*).
$$
\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}
$$
25
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*)Q*g* are the Lagrange interpo-
I i2I i i i
lation polynomials of the set *f*hi*g*i2I, and nd *H*(*X*) such that for *t*I(*X*) =i2I(*X* hi)*;*
$$
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)
$$
Output*I*= C C)]1; [H]1= [H()]1:
SVC*:* Vf(vrk*;* C*;I;*~c*;*I)*! b 2f*0*;* 1*g* : Compute [*t*I]2= [*t*I()]2and 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 [1]1and []2) 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 *f*0*;* 1*g* 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 *f*0*;* 1*g*, 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.) = *f*0*;:::;‘* 1*g* 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*1*;:::;X₁*) *2* F[*X*1*;:::;X₁*] *be a polynomial in* 1 *variables. Then, for all 2,*
*p*(*;X*1*:::;X₁*) = *p* (*X*1*:::;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 = (*;:::;*1) *2*, the prover can compute the polynomials *p*(*;X*1*;*
*:::;X₁*)*;:::;p*(*;:::;*1) 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*1*;:::;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 Cbjjhas degreej+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 sizej+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, Cbjjand Cvbjjtake 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 Cbis a commitment to a vector b such that vbf = *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 *a*dversary and such that Cb=i=1*a*i i(). That is, Cbis 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 Cbmust correspond to the evaluation of two polynomials that agree on *t*. On the other
hand, because of the degree check either Cbis the evaluation in of some polynomial of degree at most
*2* 1 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*(*m*log² *m*)
H
However, one can do better: using FFT compute the 2 coecients of *C*b(*X*) = (*X*)vbin 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*]1*;*C by computing *C*(*X*) = (*C₀*(*X*) *C₁*(*X*))*X*2+ (*C₀*(*X*)
2 2
*C₁*(*X*)); encoding them in G₁ using roughly *m* operations. In total, we need *O*(*m*log*m*) eld and group
operations. Updating all proofs needs *O*() operations. It works as in the multivariate case, exploiting that
a commitment to eihas 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 interpolation 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 *j*th Lagrange interpolation polynomial of set*!* Hris
$$
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*!* Hr. 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 thatj(*!*) 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)2*i*Q i i
! r (j 1)2 (k 1)2
Since Hris a group of roots of unity,k6=j(*!!*) is the lagrange polynomial
r
is;k
(j 1)2
corresponding to*!*, evaluated at the same point and thus the equation above equals 1. That isj(*X*)
i
s s+(j 1)2
is a polynomial of degree *r* 1 such that vanishes at all elements in*!* Hrexcept for*!* where takes
s
value 1 and we conclude is the *j*th lagrange polynomial of*!* Hr. *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 Hris 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 *j*th Lagrange polynomial of Hrevaluated 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*!* Hkof a subgroup of roots of unity Hrof size *r*.
$$
\omega^{s}\mathbb{H}_{k}
$$
$$
\mathbb{H}_{r}
$$