Problem:

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.

DRI: Anca Nitulescu

Talk is available here.

Muppets: New Maintainable VC from LVC

https://docs.google.com/presentation/d/1c0bI_ZKe90Fi_HpUsPskGBPikfmxyG3RUHp6VrAdoCk/edit?usp=sharing

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:

1. 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
2. The univariate construction:
   • 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: $O(2^{n})$ for vectors of size $2^n$
   • aggregation/subvector openings are also made via IPA

Univariate Muppets: Construction

How it works:

We divide the vector $v$ (size $2^n$) in small chunks $v_j$ of size $2^k$. We have $2^n=2^{m+k+1}$

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: