# Commitment Scheme

###### tags: `ingo`

### What is a commitment?

A cryptographic commitment allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. It has two important properties:
1. **Hiding**: a commitment does not reveal anything about the original value
2. **Binding**: once you commit to a value, later you cannot change the committed value

We can think of a commitment scheme as a locker which has two phases:
1. **Commit**: lock a certain secret in the locker
2. **Open**: the secret is revealed by the sender, then the receiver verifies its authenticity

### Kate Commitment Scheme

Lets say I know a polynomial $f(X)$ of degree $d$. I wish to prove to you that I indeed know the coefficients of $f$ without revealing them. Suppose $f(X) = c_0 + c_1X + \dots + c_{d}X^d$ and we have a *secret* scalar $\beta \in \mathbb{F}_p$. The commit phase of KZG is simply computing the evaluation of $f$ at $\beta$.
$$
\textsf{com}(f) := f(\beta) = c_0 + c_1\beta + \dots + c_d\beta^d
$$

Now, the interesting thing about $\beta$ is that it is assumed to be a universal secret, i.e. no one in the world knows what $\beta$ is. Well, in that case, how can I compute the evaluation of $f$ on $\beta$? We will answer this a bit later. For now, lets see what I do in the open phase of KZG. I compute a polynomial $w(X)$ such that
$$
w(X) := \frac{f(X) - f(z)}{X - z} = (f(X) - f(z))(X-z)^{-1}
$$

where $z \in \mathbb{F}_p$ was sent by the verifier as a challenge. A natural question we can ask: is the polynomial $(f(X) - f(z))$ even divisible by $(X-z)$? The answer is: yes, it is!
$$
\begin{aligned}
(f(X) - f(z)) &= (c_0 + c_1X + \dots + c_{d}X^d) - (c_0 + c_1z + \dots + c_{d}z^d) \\
&= c_1(X-z) + c_2(X^2 - z^2) + \dots + c_d(X^d - z^d) \\
&= (X-z)\left[c_1 + c_2(X+z) + \dots + c_d(X^{d-1} + zX^{d-2} + \dots + z^{d-1})\right]
\end{aligned}
$$

Therefore, $w(X)$ is a degree-$(d-1)$ polynomial with integer coefficients. Let $w(X) = w_0 + w_1X + \dots + w_{d-1}X^{d-1}$. We commit to $w$ as:
$$
\textsf{com}(w) := w(\beta) = w_0 + w_1\beta + \dots + w_{d-1}\beta^{d-1}
$$
As a part of the open phase, I send the verifier a proof $\pi_{pc} = (\textsf{com}(f), \textsf{com}(w), v)$ where $v := f(z)$.

The verifier will *authenticate* the proof by checking:
$$
\textsf{com}(w)(\beta - z) = (\textsf{com}(f) - v)
\tag{1}
$$
In other words, if the above equation holds true, it implies that the verifier checked if the expression of $w$ holds at the secret point $\beta$. The verifier is convinced about my knowledge of $f$ because otherwise, it would have been impossible for me to compute $w(X)$.

### Structured Reference String (SRS)

In the above discussion, we assumed that the scalar $\beta$ is not known to anybody in the world. But still the prover and verifier end up using it some way or other, how is that possible? This is made possible by elliptic curve cryptography! Suppose we have a group $\mathbb{G}_1$ with generator $g$. We embed the secret $\beta$ using powers of the generator $g_1 \in \mathbb{G}_1$.
$$
\textsf{srs}_1 = \left\{g_1, g_1^\beta, g_1^{\beta^2}, \dots, g_1^{\beta^D}\right\} \in \mathbb{G}_1^{D}
$$

Given $\textsf{srs}_1$ and the fact that the discrete log relation is unknown in $\mathbb{G}_1$, there is no way any$^\dagger$ adversary could figure out what $\beta$ is. Now, the commitment to $f$ can be computed easily (of course only if $d < D$):
$$
\begin{aligned}
\textsf{com}(f) := g_1^{f(\beta)} &= g_1^{(c_0 + c_1\beta + \dots c_d\beta^d)} \\
&= g_1^{c_0} \cdot \big(g_1^{\beta}\big)^{c_1} \cdot \big(g_1^{\beta^2}\big)^{c_2} \dots \big(g_1^{\beta^d}\big)^{c_d}
\end{aligned}
$$

Given $(\textsf{com}(f), \textsf{com}(w))$ and $\textsf{srs}_1$, how can we verify equation $(1)$? We essentially wish to check multiplication of evaluations of some polynomials on the secret $\beta$. Using $\textsf{srs}_1$, we can only add up terms in $\beta$ in the exponent of $g_1$. To enable multiplication of terms in $\beta$, we need another fascinating cryptographic primitive: *pairings*.

:::info
A pairing is a map $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ where we have group generators $g_1 \in \mathbb{G}_1, g_2 \in \mathbb{G}_2$ and $g_t \in \mathbb{G}_T$ in the target group $\mathbb{G}_T$, such that $\forall a, b \in \mathbb{F}_p$
$$
e(g_1^a, g_2^b) = g_t^{ab}.
$$
:::

Therefore, a pairing allows us to multiply scalars in the exponent of the generators $g_1$ and $g_2$. For verification in $(1)$, we need a second part of our structured reference string:
$$
\textsf{srs}_2 = \left\{g_2, g_2^{\beta}\right\} \in \mathbb{G}_2^2.
$$

Now, the verification in equation $(1)$ boils down to an equality of two pairing computations:
$$
\begin{aligned}
g_t^{w(\beta) (\beta - z)} &\stackrel{?}{=} g_t^{(f(\beta) - v)\cdot 1} \\[6pt]
\implies e\left(g_1^{w(\beta)}, g_2^{(\beta - z)}\right) &\stackrel{?}{=} e\left(g_1^{(f(\beta) - v)}, g_2\right) \\[6pt]
\implies e\left(\textsf{com}(w), \ g_2^{\beta} \cdot g_2^{-z}\right) &\stackrel{?}{=} e\left(\textsf{com}(f) \cdot g_1^{-v}, \ g_2\right)
\end{aligned}
$$

:::success
The set $\textsf{srs} = \textsf{srs}_1 \cup \textsf{srs}_2$ is called as the structured reference string. This SRS is computed using MPC among several participants of which only one party needs to be honest.
:::

:::info
Notation: We will denote the commitment to a polynomial $f$ as $[f(\beta)]_1$. Further, the SRS can be written as
$$
\begin{aligned}
\textsf{srs}_1 &= \left\{\right [1]_1, [\beta]_1, \dots, [\beta^D]_1\} \\
\textsf{srs}_2 &= \left\{\right [1]_2, [\beta]_2\}.
\end{aligned}
$$
:::

### Overview of Batched Kate PCS (Optional)

The Kate commitment scheme can be used prove the knowledge of a bunch of polynomials by "opening" all of them at a single scalar. Suppose we have the following polynomials to be opened at respective points (we're considering a fairly general case here):

| Polynomials | Opening points |
| -------- | :--------: |
| $f_{1,1}, f_{1,2}, \dots, f_{1,m}$ | $z_1$ |
| $f_{2,1}, f_{2,2}, \dots, f_{2,m}$ | $z_2$ |
| $\vdots$ | $\vdots$ |
| $f_{n,1}, f_{n,2}, \dots, f_{n,m}$ | $z_n$ |

Here, we'll have to compute $n$ opening polynomials $\{W_i(X)\}_{i \in [n]}$ such that

$$
W_i(X) = \frac{F_i(X) - F_i(z_i)}{X - z_i}
$$

where $F_i(X) = \sum_{j=1}^{m} \gamma_i^{j-1} f_{i,j}$. The opening proof would be $\left\{ [W_1]_1, [W_2]_1, \dots, [W_n]_1, \{[f_{i,j}]_1, v_{i,j}\}_{i \in [n], j \in [m] } \right\}$ where $v_{i,j} = f_{i,j}(z_i) \in \mathbb{F}_p$. Clearly, the number of opening polynomial commitments needed to be computed by the prover is $n$ (i.e. the number of opening points). Finally, the verification needs the pairing check:

$$
e(W, Y) = e(F - Q, [1]_2)
$$

where

$$
\begin{aligned}
W &= \sum_{i \in [n]} u^{i-1} [W_i]_1 \\
F &= \sum_{i \in [n]}\sum_{j \in [m]} u^{i-1} \gamma_i^{j-1} [f_{i,j}]_1 \\
Q &= \left[ \sum_{i \in [n]}\sum_{j \in [m]} u^{i-1} \gamma_i^{j-1} v_{i,j} \right]_1 \\
Y &= \left[\sum_{i \in [n]}u^{i-1}(X - z_i) \right]_2
\end{aligned}
$$

### Marlin PCS

The structure of the SRS is slightly different for the KZG-style PCS used in Marlin.
$$
\textsf{srs} =
\begin{pmatrix}
G & \beta G & \beta^2 G & \dots & \beta^D G \\
\gamma G & \gamma \beta G & \gamma \beta^2 G & \dots & \gamma \beta^D G
\end{pmatrix}
\in \mathbb{G}_1^{2D+2}
$$

The terms which include $\gamma$ are necessary to commit to the *hiding* polynomials. Hiding polynomials are randomly generated polynomials that are added to the original polynomials to ensure that no information about the original polynomials is not revealed (i.e to make it zero-knowledge).

#### Commit Phase

Suppose we have polynomials $\{p_i(X)\}_{i \in [n]}$ each with a degree bound[^1] $\{d_i\}_{i \in [n]}$. In this case, we also need to commit to the polynomial $p'_i(X) = X^{D-d_i}p_i(X)$ to prove the correct degree bound $\text{deg}(p_i) < d_i$ holds. Define $d := \text{max}(\{d_i\}_{i \in [n]})$. To commit to these polynomial, we need to trim the SRS to get a committer's key:

$$
\textsf{srs}_{ck} =
\begin{pmatrix}
G & \beta G & \beta^2 G & \dots & \beta^d G & \beta^{D-d}G & \beta^{D-d-1}G & \dots & \beta^{D}G \\
\gamma G & \gamma \beta G & \gamma \beta^2 G & \dots & \gamma \beta^d G
\end{pmatrix}
\in \mathbb{G}_1^{3d+3}
$$

Hereafter, the commit phase proceeds as follows:

1. We are given randomness $\{r_i, r'_i\}_{i \in [n]}$ which is to be added to the polynomials $p_i, p'_i$ respectively.
2. Compute polynomials $\bar{p}_i(X)$ and $\bar{p}'_i(X)$ from the randomness $\{r_i, r'_i\}_{i \in [n]}$. Note the degrees of these polynomials should be equal to $\text{deg}(p_i)$.
3. Compute the commitments as:
$$
\begin{aligned}
{[}p_i] &:= p_i(\beta)G + \color{blue}{\gamma \bar{p}_i(\beta)G} \\[4pt]
[p'_i] &:= \beta^{D-d_i}p_i(\beta)G + \color{blue}{\gamma \bar{p}'_i(\beta)G}
\end{aligned}
$$

#### Open Phase

Given the evaluation point $z \in \mathbb{F}_p$ and the verifier challenge $\xi \in \mathbb{F}_p$, the opening phase proceeds as:
1. We compute the opening polynomials as
$$
\begin{aligned}
w(X) &= \sum_{i \in [n]} \left( \xi^i \frac{p_i(X) - p_i(z)}{X-z} + \xi^{n+i} X^{D-d_i} \frac{p_i(X) - p_i(z)}{X-z} \right) \\
&= \sum_{i \in [n]} \xi^i \left( 1 + \xi^n X^{D-d_i} \right) \left( \frac{p_i(X) - p_i(z)}{X-z}\right) \\
\bar{w}(X) &= \frac{\bar{p}(X) - \bar{p}(z) + \bar{p}'(X) - \bar{p}'(z)}{X-z}
\end{aligned}
$$
where $\bar{p}(X) = \sum_{i}\xi^i \bar{p}_i(X)$ and $\bar{p}'(X) = \sum_{i}\xi^{n+i} \bar{p}'_i(X)$.
2. Compute commitment to the opening polynomials:
$$
\textsf{w} = [w(\beta)] + [\gamma \bar{w}(\beta)]
$$
3. Compute the randomness polynomials' evaluation:
$$
\bar{v} := \bar{p}(z) + \bar{p}'(z).
$$

Thus, the opening proof is $\pi = (\textsf{w}, \bar{v})$.

#### Verification

The verification involves checking the equality
$$
e(C - vG - \gamma \bar{v}G, H) = e(\textsf{w}, \beta H - zH)
$$
where $v = \sum_{i}\xi^i v_i$ and $C = \sum_{i}\xi^i [p_i] + \sum_{i}\xi^{n+i}([p'_i] - v_i\beta^{D-d_i}G)$. Note that the verifier now requires the following SRS:
$$
\textsf{srs}_{vk} = \left\{H, \beta H, \ \beta^{D-d_1}G, \ \beta^{D-d_2}G, \dots, \ \beta^{D-d_n}G \right\} \in \mathbb{G}_1^{n} \times \mathbb{G}_2^2.
$$
Also note, the evaluations $v_i = p_i(z)$ and the commitments $\{[p_i], [p'_i]\}_{i \in [n]}$ are sent to the verifier by the prover.

[^1]: In the previous sections, we didn't need to prove any degree-bounds on a polynomial $f(X)$ other than the obvious bound $\text{deg}(f) < D$.