Commitment Schemes

Commitment schemes are essential for many cryptographic protocols, especially in zero-knowledge proofs where a prover needs to commit to certain values without revealing them immediately. They provide a way to “lock” a value in a way that can be verified later.

💡 Key Properties:

• 🔒 Binding: The committer cannot change the committed value after the commitment is made.
• 🔍 Hiding: The commitment does not reveal information about the committed value.

A commitment scheme $\Gamma$ is 🔒 binding if for all $\mathrm{PPT}$ adversaries $\mathcal{A}$ :

Informally, this states that a valid commitment $C$ to a message $m_{0}$ is binding if no adversary can produce a valid opening to some different message $m_{1}$.

A commitment scheme $\Gamma$ is 🔍 hiding if for any polynomial-time adversary $\mathcal{A}$ :

Informally, this states that if a commitment is hiding if an adversary cannot “reverse-engineer” which of their messages was committed to.

Vector Pedersen commitment. The Pedersen commitment [9] is a binding and hiding commitment scheme for the message space $\mathbb{F}_{q}$. For a secret message $m \in \mathbb{Z}_{q}$ :

• $\operatorname{Pedersen.Setup} \left(1^{\lambda}, q\right) \rightarrow \mathrm{pp}: \mathrm{pp}=G, H \in \mathbb{G}$, where $\mathbb{G}$ is a cryptographic group of order $q$.

• $\operatorname{Pedersen.Commit} (\mathrm{pp} ; m) \rightarrow(C ; r): C=[m] G+[r] H$, where $r \in \mathbb{Z}_{q}$ is a random secret.

• $\operatorname{Pedersen.Open} (\mathrm{pp}, C ; m, r) \rightarrow\{0,1\}:$ the prover $\mathcal{P}$ reveals $m$ and $r$, and the verifier $\mathcal{V}$ checks $C \stackrel{?}{=}[m] G+[r] H$

Note that the Pedersen commitment is additively homomorphic:

Vector commitments allow committing to a vector of values while being able to open the commitment at specific positions. They are particularly useful in applications where you need to commit to multiple values at once.

🔢 Mathematical Definition:

Where:

• $\vec{m} = (m_1, m_2, \ldots, m_n)$ is the vector to commit to
• $r$ is a random value (blinding factor)
• $g_1, g_2, \ldots, g_n$ are independent group generators
• $h$ is another independent group generator

🔍 Applications: Vector commitments are used in:

• Verifiable databases where you need to prove membership of elements
• Zero-knowledge proofs for multiple values
• Blockchain systems for committing to multiple transactions

⚡ Efficiency Considerations: The main challenge with vector commitments is efficiency, especially as the vector size grows. Various optimizations exist to make vector commitments more practical:

• Merkle trees for logarithmic-sized proofs
• Polynomial commitments for batch openings
• Specialized constructions like KZG for vectors

A univariate polynomial commitment scheme (PCS) is a commitment scheme for the message space $\mathbb{F}^{\leq d}[X]$, the ring of univariate polynomials with maximum degree $d \in \mathbb{N}$ and coefficients in the field $\mathbb{F}=\mathbb{Z}_{p}$

It supports an argument of knowledge for proving the correct evaluation of a committed polynomial at a given point. A lot of information can be encoded in a polynomial: an arbitrary relation can be represented as a polynomial.

KZG (Kate-Zaverucha-Goldberg) polynomial commitments allow committing to a polynomial and later proving evaluations of that polynomial at specific points. They are widely used in modern zero-knowledge proof systems due to their efficiency and succinctness.

Its core idea is:

• The prover can commit to a polynomial.
• Later, they can prove to the verifier the value of that polynomial at a specific point without revealing the underlying polynomial.

This method is so useful because any content that can be encoded as a polynomial can now be easily disclosed selectively.

We will use the shorthand notation $[x]_{1}:=[x] G_{1},[x]_{2}:=[x] G_{2}$, for any $x \in \mathbb{F}_{p}$.

• $\operatorname{KZG.Setup} \left(1^{\lambda}, d\right) \rightarrow srs$:

  set $srs =(\mathrm{ck}, \mathrm{vk})=\left(\left\{\left[\alpha^{i}\right]_{1}\right\}_{i=0}^{d-1},[\alpha]_{2}\right)$. $\alpha$ here is a secret element and must be discarded after the Setup.

• $\operatorname{KZG.Commit} (\mathrm{ck} ; f(X)) \rightarrow C$:

  for $f(X)=\sum_{i=0}^{n-1} f_{i} X^{i}, C=\sum_{i=0}^{n-1}\left[f_{i}\right]\left[\alpha^{i}\right]_{1}=[f(\alpha)]_{1}$.

• $\operatorname{KZG.Open}(srs, C, x, y ; f(X)) \rightarrow\{0,1\}$:

  To “open” the commitment at evaluation point $x$ to a claimed value $y$

  1. the prover $\mathcal{P}$ computes the quotient polynomial $q(X)=\frac{f(X)-y}{X-x}$ and sends the verifier $\pi=\operatorname{KZG.Commit} (ck; q(X))=[q(\alpha)]_{1}$

  2. the verifier $\mathcal{V}$ checks $e\left(C-[y]_{1}, H\right) \stackrel{?}{=} e\left(\pi,[\alpha]_{2}-[x]_{2}\right)$.

  The 1 and 2 steps in $\operatorname{KZG.Open}$ are often written as two separate algorithms:

  • $\operatorname{Open} (\mathrm{ck}, C, x, y ; f(X)) \rightarrow \pi$ returns an opening proof for the relation
  $$\mathcal{R}:=\left\{(\mathrm{ck}, C, x, y ; f(X)): \begin{array}{rl} & C \operatorname{deg}(f(X)) \leq d \\ & \wedge y=f(x) \end{array}\right\} ;$$
  • $\operatorname{Verify} (\mathrm{vk}, C, x, y, \pi) \rightarrow\{0,1\}$ verifies the opening proof’s correctness.