A vector commitment is scheme that allows one to commit to a sequence of values while keeping them hidden. The committer is also able to reveal the values later by providing a proof.
Merkle tree is a form of vector commitment. The sequence of values are the leave nodes. The commitment is the root hash. The revealing strategy is by way of a Merkle proof. One of the limitation of a Merkle proof is the proof size is \(O(k \log_k n)\).
A polynomial commitment is a strictly more expressive scheme than a vector commitment. A polynomial scheme could be used as a vector commitment.
Let’s make the setup more concrete. We have a sequence of values that we want to commit, \(\{x_i\}_{i=0}^n\). We want a construction where we have a constant size \(C\) to represent these values, and we also want a constant size \(\pi\) as a proof to the authenticity of a value \(y=x_i\). The following scheme is the KZG polynomial commitment.
Preliminary
The construction depends on pairing based cryptography primitives. I am not going into the technical details. You can find some a simple introduction to one such construction in my BLS post. The basics is that there are three groups, \(\mathbb{G}_1\), \(\mathbb{G}_2\), and \(\mathbb{G}_T\) constructed on the prime field \(\mathcal{F}_r\). \(r\) is the prime field order. Let \(G_1\) and \(G_2\) be the group generator of \(\mathbb{G}_1\) and \(\mathbb{G}_2\) respectively. There is a bilinear map \(e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{G}_T\). There are also arbitrary many of these values known by everyone, \(t^k G_1\) and \(t^k G_2\), where \(k= 1, 2, ...\) The trapdoor value \(t\in \mathcal{F}_r\) is discarded and not known by anyone. We just need as many of these parameters as the size of the sequence we want to commit to.
Commitment
- Create a polynomial from the value sequence \(\{x_i\}\). This is straight forward, and could be accomplished by lagrange polynomial. The idea is simple. The polynomial could be just set to be as high degree as possible so all the values could be encoded in the polynomial. The polynomial \(p\) is such that \(p(i) = x_i\). We write this polynomial in terms of its coefficients,
- The commitment is
\begin{equation} C = \sum_{i=0}^{n-1} p_i t^k G_1 \end{equation}
Note that the commitment \(C\) is a curve point in \(\mathbb{G}_1\). It is a curve point regardless of the size of the original sequence.
Proof
We want to construct a proof of a single value, \(y=x_i\). Because we convert the value sequence into a polynomial \(p\), we want to prove \(p(i) = y\). Let’s define another polynomial,
Again, we re-write this polynomial in its coefficient form, where
The proof is
Note that the proof \(\pi\) is a curve point in \(\mathbb{G}_1\).
Verification
We only need to verify the following relation.
The commitment is \(C\). The claim is \(y = x_i\). The proof is \(\pi\). All of these are public information. \(tG_2\) are public as well.
Notes
- The single point proof could be extended to a multiproof. The proof size remains to be a single curve point, hence constant size.
- We could use the polynomial commitment scheme instead of the Merkle tree vector commitment scheme to represent a trie. The proof of a k-ary Merkle tree requires each path to contain \(k-1\) many hash values, the number of hash values of the interested node’s siblings. The proof size is \(k \log_k n\). However, the polynomial commitment proof would allow us to use a single curve point to represent the proof at each level. It reduce the needs to list out sibling’s hash values. Hence the overall proof size is \( \log_k n\).
- This could actually be one better. Because the revelation proofs are curve points, they are additive. We could use a single curve point to prove all parent-child relationship for each of the level. The overall proof size could be reduce to constant size.
References:
- Vitalik’s description of Verkle tree
- Dankrad Feist’s description of Verkle trie
- Polynomial and Ethereum state root