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

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.

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}$

More of how to compute each level:

As we know the opening (a subvector of $v$), the node computation are independent of one another:

• each node is of the form $C(v_i) = \Lambda^h w$ where
• $w$ is the opening containing all the leaves below node $C(v_i)$
• $\Lambda^h$ 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

The former part can be pre-computed and efficiently maintained, with a storage cost linear in $m$, while the latter involves operations that are linear in $2^k$.

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 $N=2^n$, we offer the following trade-off:

• for any $m, k$, such that $N=2^{m+k+1}=2MK$, one can derive openings of size $m+4$ group elements.
• The prover can pre-compute and store $2^m-1$ proofs, and then compute proofs by performing $O(2^k)$ group operations and $O(k2^k)$ field operations.
• We show also how to compute all proofs with $O(m N)=O(log(M)N)$ group operations ( + $O(n(m+k))$ field operations).
• The proofs are maintainable: an update in a position requires recomputing $O(m)$ nodes.
• The trusted setup depends only on $N$ (the number of powers of $\tau$) and not on $m, k$, 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: $\{0,1\}^N$. 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 $Σ^N =\{0,1\}^N$ for small N has lower amortized cost than computing the evaluations individually. Using $Σ$ of size $l>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 $l= O(1)$ results in proof size $log_l n$ instead of $log_2 n$, 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 $gk = (p, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T , e)$
• $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ are additive groups of order $p$ prime, so $\mathbb{F} = \mathbb{F}_p$ is a field
• We use notation $[a]_1, [b]_2, [c]_t$ for elements in $\mathbb{G}_1, \mathbb{G}_2$ and $\mathbb{G}_T$ respectively
• The bilinear map or pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is such that

$\forall a, b ∈ \mathbb{F}_p, \quad e([a]_1, [b]_2) = [ab]_t$

• We implicitly have that $[1]_t= e([1]_1, [1]_2)$ generates $\mathbb{G}_T$
• We use $[a]_{1,2}$ to refer to 2 group elements $[a]_1 \in \mathbb{G}_1, ~ [a]_2 \in \mathbb{G}_2$

Building a tree of commitments to a vector $v$ of size $N=2^n$:

• The root of the tree is a commitment $C = [λ]_1v$, where $λ = ([λ_1(τ )]_1, . . . , [λ_N(τ )]_1)$, computed from the powers of τ setup:
• Let $H=\{ω^j\}_{j=0, N-1}$ be the set of $N$-th roots of unity $ω^j$.
• The polynomials $\{λ_j (X)\}_{j=1,N}$ are the Lagrange basis interpolation polynomials for set $H$
• The two children will be $c_0 = [λ_0]_1v_0$ and $c_1 = [λ_1]_1v_1,$ which are commitments to $v_0$ and $v_1$ with keys $λ_0$ and $λ_1$ of half the size.
• The two children of c_0 will be $c_{00} = [λ_{10}]_1v_{10}, C_{10} = [λ_{10}]_1v_{10}$ and so on.
• The leaves are commitments $c_b$, $b = (b_ν, . . . , b_0) ∈ \{0, 1\}^{ν+1}$ vectors of size $2^k$.
• For a leaf index $b = (b_ν, . . . , b_0) ∈ \{0, 1\}^{ν+1}$, we denote $b_{|j} = (b_j . . . b_0)$ the suffix of size j.
• Notethat $c_{b_{|j}}$ for $j = 0, . . . , ν − 1$ denotes all the commitments from the root to the leaf $c_b$.
• The division into vectors of half the size is done according to the least significant bit of the binary representation of the index, $b_0$.
• At the first level, there will be two vectors $v_0, v_1$ of size $N/2=2^{n-1}$ containing all positions of $v$ with suffix $b_0$.
• At the next level, there will be four vectors $v_{00}, v_{01}, v_{10}, v_{11}$ of size $N/4$
• $v_{b_1b_0}$ indicates all the positions of $v$ (in the natural order) that have as suffix ${b_1b_0}$ 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 $H_0$ and $H_1$, according to the least significant bit of the binary representation of the index of the root,
• $H_0$ consists of all even and $H_1$ all odd powers of $ω$.
• In particular, $H_0$ are the roots of unity of size $N/2$, and $H_0 = ωH_1$
• At level 2, the commitment keys will be associated to $H_{00}, H_{01}, H_{10}, H_{11}$
• By the same reasoning, $H_{00}$ are the roots of unity of size $N/4$.
• $H_{10} = ω^2H_{00}, H_{01} = ωH_{00}$ and $H_{11} = ω^3H_{00}$
• More generally, we note that for any $0 ≤ j ≤ ν$ and any string $(b_j, . . . , b_0) ∈ \{0, 1\}^{j+1}$,
• $H_{b|j} = ω^sH_r,$ for
• $s =\sum_{i=0}^j b_i 2^ij, \quad r =N/2^{j+1}= 2^{n-j-1}$
• The Lagrange basis polynomials associated to the interpolation set $H_{b|j}$ with the natural order is
• $λ_{b|j}(X) = (λ_{b|j}^1 (X), . . . , λ_{b|j}^r(X))$

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 $c(X) = λ(X)v,$ then $c_b(X) = λ_b(X)v$ for $b=0,1$ and
• $c(X) = \frac{1}{2} (c_0(X)t_1(X) − c_1(X)t_0(X))$
• where $t_0$ and $t_1$ are vanishing polynomials for $H_0$ and $H_1$
• observe that evaluating at $H_0$, the second term in the right hand side disappears,
• while $t_1(η) = 2$ for any $η ∈ H_0$
• so both sides take the same value at $H_0$, and similarly for $H_1$

Towards an MVP for Univariate Muppets

An implementation would roughly consist of three components:

1. 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))
2. integration of (1) with the “tree-based” maintainability parts above
3. integrating (1) and (2) with Inner Product Arguments for subvector opening