PLONK: Reducing the number of Field Elements Trick

Question

From the PLONK paper.

Page 18

We describe an optimization by Mary Maller to reduce the number of $F$-elements in the proof from $M$. We begin with an illustrating example. Suppose $V$ wishes to check the identity $h1(X) \cdot h2(X) − h3(X) \equiv 0$. The compilation described above would have $P$ send the values of $h1$, $h2$, $h3$ at a random $x \in F$; and $V$ would check if $h1(x)h2(x)−h3(x) = 0$. Thus, $P$ sends three field elements. Note however, that we could instead have $P$ send only $c := h1(x)$, and then simply verify in the open protocol whether the polynomial $L(X) := c \cdot h2(X) − h3(X)$ is equal to zero at $x$. (Note that we can compute $com(L) = c \cdot com(h2) − com(h3)$.)

Why not just create a new polynomial $F(X) = h1(X) \cdot h2(X) − h3(X)$ & send a commitment to $F(X)$ & also evaluate $F$ at a random point & check if it evaluates to $0$. This will also check the identity needed to be checked. This also reduces number of field elements to be sent. So why a more complicated trick to achieve this?

Another question is about the first quoted line - "proof from $M$" - what or who is $M$ in this context? It's not clear.

Answer 1

Verifier doesn't calculate ℎ1(x), ℎ2(x), ℎ3(x), prover has to. Therefore, simply sending a F(x) is not enough, prover still has to send ℎ1(x), ℎ2(x), ℎ3(x).

The optimization in the paper works as follows:
With ℎ1 evaluated as c, a constant, verifier can computes 𝑐𝑜𝑚(𝐿) themselves, which utilizes the (additive) homomorphic nature of KZG commitment scheme. prover then calculate 𝐿(x) and proof π to prove 𝐿(x) = 0.

Here's the sketch of how homomorphism of KZG commitment scheme: \begin{align*} & \text{Com}(h_1) + \text{Com}(h_2)\\ &= G \cdot h_1(\tau) + G \cdot h_2(\tau) \\ &= G \cdot (h_{1,0} + h_{1,1}\tau + h_{1,2}\tau^2 + \ldots + h_{1,d}\tau^d) + G \cdot (h_{2,0} + h_{2,1}\tau + h_{2,2}\tau^2 + \ldots + h_{2,d}\tau^d) \\ &= G \cdot [(h_{1,0}+h_{2,0})\tau + \ldots + (h_{1,d}+h_{2,d})\tau^d] \end{align*}

How would the verifier verify that ℎ1(𝑟)=𝑐 is actually true without having a commitment to ℎ1 also which is opened at 𝑟 ? After the verifier sends a random value 𝑟 to the prover, the prover can calculate ℎ2(𝑟) & ℎ3(𝑟) & calculate a 𝑐 such that 𝑐⋅ℎ2(𝑟)−ℎ3(𝑟)=0?

Prover outputs commitments, $([a]_1, [b]_2, [c]_1)$ in round 1, that's why this opening can be verified. The commitment of round 4 opening evaluation have all been submitted in previous round or as common preprocessed input.

ref: https://cacr.uwaterloo.ca/techreports/2010/cacr2010-10.pdf

Answer 2

The optimization described by Mary Maller [Can be found here] 1 aims to reduce the number of field elements that need to be sent by the prover in a zero-knowledge proof scenario. Let's address your two questions raised:

1. Why not just create a new polynomial F(X) = h1(X)⋅h2(X) − h3(X) and send a commitment to F(X) and also evaluate F at a random point & check if it evaluates to 0?

You are correct that creating a new polynomial F(X) = h1(X)⋅h2(X) − h3(X) and sending a commitment to F(X) would also check the identity needed to be verified (h1(X)⋅h2(X) − h3(X) ≡ 0). However, this approach may not necessarily be more efficient or simpler than the optimization described in Mary Maller.

The key idea of the optimization is to take advantage of the homomorphic property of the commitments to simplify the proof. By sending only c = h1(x) instead of h1(x), h2(x), and h3(x) individually, the prover can efficiently compute com(L) = c⋅com(h2) − com(h3) using the commitments they already have. This reduces the number of field elements to be sent from three (h1(x), h2(x), and h3(x)) to one (c). The verification process remains the same, but the communication overhead is reduced.

While creating a new polynomial F(X) would also work, it would require sending the commitments of h1(X), h2(X), and h3(X), which would involve sending more field elements compared to the optimized approach. The optimization leverages the commitments already available, making it more efficient in terms of communication overhead.

2. Another question is about the first quoted line - "proof from M" - what or who is M in this context?

In the context provided, "proof from M" refers to the proof that would involve sending M field elements (in this case, M = 3 since the prover sends h1(x), h2(x), and h3(x)). It's a general way of referring to the proof before the optimization, where the prover would send M field elements to the verifier as part of the proof. The optimization reduces the number of field elements required for the proof.