Inner Product Commitment Schemes
\gdef\p#1{\left({#1}\right)} \gdef\Norm#1{\left\lVert{#1}\right\rVert} \gdef\range#1{\left[#1\right)} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}}
Definition 1. An \F_q-Inner Product Commitment Scheme is a tuple of algorithms (\mathsf{commit}, \mathsf{open}, \mathsf{verify}) such that.
- \mathsf{commit} algorithm takes a vector \vec v \in \F_q^n and outputs a commitment C to \vec v.
- The \mathsf{open} algorithm takes \vec v, C, a vector \vec w \in \F_q^n, and a value y \in \F_q and outputs a proof \pi that the inner product \vec v \cdot \vec w equals y.
- The \mathsf{verify} algorithm takes C, \vec w, y, \pi and outputs true if the proof is valid and false otherwise.
Let's look at how Ligerito and WHIR construct such a scheme.
Tree Occupancy Distributions
Lemma 2. The Occupancy Distribution \mathcal{D}(n, m) is the distribution by throwing n balls uniformly at random into m bins and counting the number of bins which contain at least one ball. Given X \sim \mathcal{D}(n, m), the probability that X takes the value k is
\Pr[X = k] = \frac{\binom{m}{k} \cdot S(n, k) \cdot k!}{m^n}
where S(n, k) is the Stirling number of the second kind.
Linear Codes
Definition 2. A Linear Code C over a field \F_q is a subspace of \F_q^n. The elements of C are called codewords. The dimension of the code is the dimension of C as a vector space over \F_q. The minimum distance d of the code is the minimum Hamming distance between any two distinct codewords in C. A linear code with parameters [n, k, d] has length n, dimension k, minimum distance d, rate \rho = k/n and expansion \rho^{-1} = n /k. The generator matrix G of a linear code is a k \times n matrix whose rows form a basis for the code.
Hamming Weight Take \Norm{\vec v}_0 to mean the number of non-zero entries in \vec v. Despite notation it is not a proper norm as it fails homogeneity.
We will work over vectors of size 2^k for some integer k. These can be reshaped into matrices of size 2^l \times 2^{k-l} for some integer l \in \range{0,k}. Denote this \mathsf{Mat}_{k\,l}(\vec v), where we can drop the k if it is clear from context.
Commitment
Given a vector \vec v \in \F_q^n, the commitment algorithm works as follows:
Parameters:
- Field \F_q.
- Vector size n = 2^k.
- Matrix dimensions l \in \range{0,k}.
- Vector commitment scheme \setn{VC} of size m.
- Code \setn C with parameters [m, 2^{k - l}, d] and generator matrix \mat G.
- Code \setn C' with parameters [m', 2^{k - l}, d'] and generator matrix \mat G'.
- Number of out-of-domain samples n_o.
Steps:
- Reshape \vec v into a matrix \mat V of size 2^l \times 2^{k -l}.
- Encode rows using the generator matrix: \mat V' = \mat V \cdot \mat G.
- Commit to the columns of \mat V' using \setn{VC}.
- Pick challenges \setn{S} \subseteq \range{0, n'} by uniformly drawing n_0 samples.
- Compute \mat V'' by encoding the rows of \mat V'' = \mat V \cdot \mat G'_{\setn S}.
- Send \mat V''.
Transcript size (ignoring dedpulication in \setn S):
\mathsf{hash} + n_0 \cdot 2^l \cdot \mathsf{field}
Opening
Parameters:
- Commitment parameters as above.
- Vector \vec w \in \F_q^n.
- Value y \in \F_q.
- Number of in-domain samples n_i.
- Number of folds f.
Steps:
- Reshape \vec w into a matrix \mat W of size 2^l \times 2^{k -l}.
- Pick challenges \setn{T} \subseteq \range{0, 2^{k-l}} by uniformly drawing n_i samples.
- Compute $\
Adding Zero-Knowledge
References
- ACFY24 Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev (2024). WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification.
- NA25 Andrija Novakovic, Guillermo Angeris (2025). Ligerito: A Small and Concretely Fast Polynomial Commitment Scheme.
k \cdot \p{\frac{n}{k} + \log \frac{n}{k}}
https://ethereum.github.io/consensus-specs/ssz/merkle-proofs/?utm_source=chatgpt.com#merkle-multiproofs
