Vector commitments (VCs)

tl;dr: Definition of vector commitment (VC) schemes (e.g., Merkle trees, KZG-based, Pointproofs¹, aSVC², etc. can all satisfy this definition.)

Preliminaries

A $B$-subvector of a vector $\mathbf{v}$ is defined as just the elements from $\mathbf{v}$ that are at the positions in $B$: i.e., $\mathbf{v}[B] \bydef (v_j)_{j\in B}$.

Definitions

All algorithms are deterministic.

Typically, the VC setting includes:

1. A prover, who computes a commitment to a vector.
2. A verifier, who is given such a commitment and is interested in verifying that an element $v_j$ is indeed at position $j$ in the committed vector.

Vanilla VCs

$\mathsf{VC.Commit}(\mathbf{v}\bydef [v_1, v_2,\ldots,v_n])\rightarrow (c, \ad)$
Given a vector $\mathbf{v}$, computes its commitment $c$ and authentication data $\ad$, which helps speed up the prover.

Depending on the VC scheme, $\ad$ can store the vector $\mathbf{v}$, the commitment $c$, and/or any pre-computed proofs. For Merke-based VCs, the $\ad$ would include the Merkle tree itself. This way, the prover, who has $\ad$, can prove $v_j$ is the $j$th element by giving a Merkle path to it. For KZG-based VCs with FK, the $\ad$ would include all $n$ precomputed (individual) proofs for each position $j\in[n]$.

$\mathsf{VC.Prove}(\ad, j) \rightarrow (\pi_j)$
Given authentication data $\ad$, fetch (or compute) an individual proof $\pi_j$ for element $v_j$ being at position $j$.

$\mathsf{VC.Verify}(c, j, v_j, \pi_j)\rightarrow {0,1}$
Verifies the individual proof $\pi_j$ that $v_j$ is the $j$th element of the vector committed in $c$.

SVCs

$\mathsf{VC.Aggregate}(c, (j,v_j,\pi_j)_{j\in B})\rightarrow \hat{\pi}$
Given a $B$-subvector and individual proofs $\pi_j$ for each position $j\in B$ in this subvector, aggregates them into a subvector proof $\hat{\pi}$.

$\mathsf{VC.AggVerify}(c, B, \mathbf{v}[B], \hat{\pi})\rightarrow {0,1}$
Verifies the subvector proof $\hat{\pi}$ that $\mathbf{v}[B]$ is indeed the $B$-subvector of the vector committed in $c$.

Cross-aggregatable SVCs

$\mathsf{VC.CrossAggregate}\left({c_i, B_i,\mathbf{v}_i[B_i],\hat{\pi}_i)}_{i\in[\ell]}\right)\rightarrow \pi$
Cross-aggregates a bunch of subvector proofs for different vectors into a cross-aggregated proof $\pi$.

$\mathsf{VC.CrossVerify}\left({c_i, B_i,\mathbf{v}_i[B_i]}_{i\in[\ell]},\pi\right)\rightarrow {0,1}$
Verifies a cross-aggregated proof for the given subvectors and their associated vectors’ commitments.

TODOs

• Proof updates for vanilla VCs and SVCs (and maybe cross-agg VCs[^TXN20]?)
  • hintless
  • with hints
  • with update keys
• Hiding VCs

References

For cited works, see below 👇👇