Problem:

DRI: Anca Nitulescu

Muppets: New Maintainable VC from LVC

Tree-based VC: High-level description

Univariate Muppets: Construction

How it works:

• 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

Reusable setup and Parameters for 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

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

• 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

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