PLONK: Reducing the number of Field Elements Trick

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.

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.