In Merkle Tree we have a way to trade time for space when it comes to opening commitments, prover can be very efficient by storing part of the tree.
What are the equivalent possibilities in constant-size vector commitments? Let’s look at LVC construction we recently published here.
Muppets: New Maintainable VC from LVC
Tree-based VC: High-level description
We have 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 flexible form of maintainability: our schemes allow to arbitrary tune the memory used to save on the opening time.
One construction is based on multivariate polynomials, the other on univariate polynomials:
- The multivariate case is a generalisation of Hyperproofs that uses binary trees:
- we allow for any arity for the trees,
- therefore proofs are shorter
- the leaves can be commitments from any LVC scheme
- the aggregation/subvector openings are made via IPA
- only for binary trees
- reusable setup: powers of tau
- additional feature: setup is independent of the trade-off tuning
- the memory/time used can be decided by the prover on the fly
- different provers might have different tradeoffs in the same application
- to save online verifier work one can preprocess n elements (Lagrange polynomials)
- each node in the tree can be computed independent of parents and children nodes
- computing one level of the tree: for vectors of size
- aggregation/subvector openings are also made via IPA
Univariate Muppets: Construction
How it works:
We divide the vector (size ) in small chunks of size . We have
We then arrange these chunks in a tree as follows:
- each chunk corresponds to a leaf of the tree
- each node is a succinct representation of its children (because we have structured keys)
- the root of the tree is the committed value.
More of how to compute each level:
As we know the opening (a subvector of ), the node computation are independent of one another:
- each node is of the form where
- is the opening containing all the leaves below node
- is the Lagrange interpolation of some coset
- we don’t even need the parent nodes, just the position in the tree to pick the correct coset
An opening proof only involves the elements in the path from the root to the leaf containing the position to be opened. That is, if we want to open value in position of , we prove that:
- is the leaf that contains the commitment to the chunk containing —> storage cost linear in ,
- opens to in the position corresponding to —> time cost operations linear in .
The former part can be pre-computed and efficiently maintained, with a storage cost linear in , while the latter involves operations that are linear in .
Reusable setup and Parameters for trade-off:
Muppets for univariate polynomials is an optimized construction that achieves memory-time tradeoffs from Powers of tau setup.
This scheme 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.
For vectors of size , we offer the following trade-off:
- for any , such that , one can derive openings of size group elements.
- The prover can pre-compute and store proofs, and then compute proofs by performing group operations and field operations.
- We show also how to compute all proofs with group operations ( + field operations).
- The proofs are maintainable: an update in a position requires recomputing nodes.
- The trusted setup depends only on (the number of powers of ) and not on , so the tradeoff can be decided on the fly.
Relations with Verkle and Hyperproofs
Verkle trees: The tree-based construction 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 difference with Verkle trees is that the “commitment” does not satisfy a binding notion; indeed there are efficient ways to express each node in more than one way by manipulating group elements. This allow us to get around the recursivity problem of committing to commitments when building the tree, that Verkle trees have.
Hyperproofs: In this work, pre-computing all proofs of opening (for one position) can be done in quasi-linear time in the dimension n of the vector, instead of the trivial quadratic time n^2. Furthermore, the homomorphic properties allow to efficiently, in logarithmic time update all proofs after a position update. Hyperproofs use a binary interpolating set for their polynomials: . We extend these techniques to construct a multi-variate vector commitment scheme with the same properties while reducing proof size. Specifically, we observe that evaluating all openings in any set of the form for small N has lower amortized cost than computing the evaluations individually. Using of size (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 results in proof size instead of , reducing the proof size by a constant factor.
Our Univariate construction, generalises further Hyperproofs, by getting rid of multiple variables in the polynomial representation for each node.
Univariate Muppets - Detailed Description
Bilinear groups notation:
- A bilinear group is given by a description
- are additive groups of order prime, so is a field
- We use notation for elements in and respectively
- The bilinear map or pairing is such that
- We implicitly have that generates
- We use to refer to 2 group elements
Building a tree of commitments to a vector of size :
- The root of the tree is a commitment , where , computed from the powers of τ setup:
- Let be the set of -th roots of unity .
- The polynomials are the Lagrange basis interpolation polynomials for set
- The two children will be and which are commitments to and with keys and of half the size.
- The two children of c_0 will be and so on.
- The leaves are commitments , vectors of size .
- For a leaf index , we denote the suffix of size j.
- Notethat for denotes all the commitments from the root to the leaf .
- The division into vectors of half the size is done according to the least significant bit of the binary representation of the index, .
- At the first level, there will be two vectors of size containing all positions of with suffix .
- At the next level, there will be four vectors of size
- indicates all the positions of (in the natural order) that have as suffix and so on.
- The division into commitment keys of half the size will follow a similar pattern:
- At level 1, roots of unity will be split into and , according to the least significant bit of the binary representation of the index of the root,
- consists of all even and all odd powers of .
- In particular, are the roots of unity of size , and
- At level 2, the commitment keys will be associated to
- By the same reasoning, are the roots of unity of size .
- More generally, we note that for any and any string ,
- The Lagrange basis polynomials associated to the interpolation set with the natural order is
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 verifier work.
More in detail, because of the way subsets are chosen, there is a simple relation between the parent and the children nodes.
- observe that if then for and
- where and are vanishing polynomials for and
- observe that evaluating at , the second term in the right hand side disappears,
- while for any
- so both sides take the same value at , and similarly for
Towards an MVP for Univariate Muppets
An implementation would roughly consist of three components:
- the Lagrange basis construction from the LVC paper
- (as presented above, our maintainable construction relies on an underlying ”non maintainable” subvector commitment construction for Lagrange basis from the LVC paper (Section 5.2))
Hyperproofs, Verkle Trees (and here) and our mVC
|Operation||Hyperproofs cost||Verkle trees cost (KZG, arity = B)||Our cost|
~ n 𝔾1
Compute all proofs
n log(n) 𝔾1
Update all proofs (”state”)
log n 𝔾1
Verify 1 proof
log n ℙ
Aggregate m proofs
m log n (𝔾1+𝔾2+ℙ)
Verify aggr. of m proofs
m log n (𝔾2+𝔾T+ℙ)
Size of one proof
log n 𝔾1
+1 ) 𝔾1
Size of aggregated proof
log(m log n) 𝔾T
via IPA (costly)
Maintainability (update all)
Compute/Update a fraction ⁍ of the tree
Total # of proofs in Verkle Trees
d is depth of VT; B is branching factor. It holds that , i.e.,