Polynomial commitments and Fiat–Shamir heuristic

In cryptographic schemes like PLONK, the prover needs to commit to certain polynomials to ensure that they do not change these polynomials later in the protocol.

Later in the protocol, the prover usually needs to prove that these polynomials evaluate at a certain point to the claimed values.

But this certain point must not be known ahead of time.

Let’s have a polynomial $p(x)$. The prover computes the commitment to this polynomial: $p_c$.

At some point in the protocol, the verifier chooses a random $\chi$, gives it to the prover, and the prover returns $\bar{p} = p(\chi)$.

The messages go like:

$\text{Prover} \rightarrow p_c \rightarrow \text{Verifier}$

$\text{Prover} \leftarrow \chi \leftarrow \text{Verifier}$

The prover then has to prove that it knows a polynomial that evaluates to $\bar{p}$ at $\chi$. We say the prover opens $p$ at $\chi$.

Remember, when using KZG commitments, the prover computes $g(x)$ such that:

$p(x) - \bar{p} = g(x) (x - \chi)$

The prover opens $p(x)$ at $\chi$ by sending $[g(s)]_1$ to the verifier:

$\text{Prover} \rightarrow [g(s)]_1 \rightarrow \text{Verifier}$

Usually, the prover needs to prove some relations between the polynomials. Let’s say there is another polynomial $q(x)$. And let’s say the prover would like to prove the relation:

$p(x) q(x) + 1 = 0$

Let’s denote $h(x) = p(x)q(x) + 1$.

The prover doesn’t want to reveal $p(x)$ and $q(x)$. Instead, it proves that it knows a polynomial that evaluates to $\bar{p}$ at $\chi$ and that it knows a polynomial that evaluates to $\bar{q}$ at $\chi$.

The prover computes the commitment to $h(x)$: $[h(s)]_1$. It then computes $h_1(x)$ such that:

$h(x) - h(\chi) = h_1(x) (x - \chi)$

The verifier is given $\bar p$, $\bar q$, $[h(s)]_1$, $[h_1(s)]_1$ and checks whether:

$e([h(s) - \bar p \bar q - 1]_1, [1]_2) = e([h_1(s)]_1, [(s - \chi)]_2)$

Note that $[h(s) - \bar p \bar q - 1]_1$ can be easily computed having $[h(s)]_1$, $\bar p$, and $\bar q$: $[h(s) - \bar p \bar q - 1]_1 = [h(s)]_1 - [\bar p \bar q + 1]_1$.

What if the challenge is known ahead of time?

So, what if the prover knows $\chi$ ahead of time?

Well, the prover could take an arbitrary polynomial (of the proper degree) that evaluates to $\bar p \bar q$ at $\chi$. Let’s denote such a polynomial by $r(x)$:

$r(\chi) = \bar p \bar q + 1$

It then computes $r_1(x)$ such that:

$r(x) - r(\chi) = r_1(x) (x - \chi)$

The prover sends $[r(s)]_1$ and $[r_1(s)]_1$ to the verifier (instead of $[h(s)]_1$ and $[h_1(s)]_1$).

The following check that verifier executes turns out to be true:

$e([r(s) - \bar p \bar q - 1]_1, [1]_2) = e([r_1(s)]_1, [(s - \chi)]_2)$

Note that the verifier doesn’t compute $[h(s)]_1$ out of $[p(s)]_1$ and $[q(s)]_1$ because that’s not possible—Kate commitments are not fully homomorphic; they are only additively homomorphic.

Fiat-Shamir

So, it’s crucial that the prover doesn’t know the challenge in advance. However, in real-world applications, it’s often beneficial to reduce communication between the involved parties. The Fiat–Shamir heuristic eliminates the need for the verifier to choose and send a challenge to the prover by computing the challenge using a cryptographic hash function."

However, how to guarantee that the challenge has been computed only after the prover committed to $h(x)$? Remember, otherwise the prover could choose some arbitrary $r(x)$ that evaluates to $\bar p \bar q + 1$ at $\chi$ and then commit to $r(x)$ instead of $h(x)$.

To prevent such a scenario, the challenge needs to be computed by taking into account the commitment to $h(x)$.

So, part of the input to hash function to compute the challenge needs to be the commitment to $h(x)$. Note that the inputs to hash function need to be known to both parties - prover and verifier. Obviously, they both need to compute the challenges.

So, part of the input to the hash function to compute the challenge needs to be the commitment to $h(x)$. Note that the inputs to the hash function need to be known to both parties—the prover and the verifier. Obviously, they both need to compute the challenge.