notes - April 17, 2023

Some ideas behind PLONK




PLONK stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. But do not mind the incomprehensible words – PLONK is an incredibly useful cryptographic protocol.

Let’s say we are in the field

and in it, we have the multiplicative subgroup
We also have the polynomial
for which it holds:

For example, we would like to prove that for each

That means:

Let’s denote:

The prover needs to prove:

To achieve this, the prover computes the polynomial

The prover then computes commitments

and
to the polynomials
respectively. The prover then proves that it knows the polynomials behind the commitments. It opens the polynomials at
(chosen by a verifier):

That means the prover proves that

evaluate to
at
respectively. The prover provides:

The verifier checks:

Note that the verifier computes

as follows:

Why is this secure?

This will be just a bit of hand-waving (I say this too many times).

Let’s say the attacker does not know

and
such that:

Note that the equation above ensures:

The attacker could easily take polynomials

and define
such that (considering
as a constant):

However, the prover needs to commit to

before knowing the challenge
That means that the prover cannot subsequently change the polynomial
When committing to
the value
could be any element of
and the probability of the prover guessing it is negligible.

Multi-opening

What if the prover needs to prove multiple relations?

Let’s say the prover would like to prove for

Could opening a polynomial for each relation be avoided? Could one opening suffice?

It could and the reason, again, is probability.

Another challenge is needed for this, let’s say

Our new polynomial of interest is:

The steps are then the same as for the single opening, but note that the verifier computes

as follows:

Zero-knowledge

We didn’t care about zero-knowledge above - about disclosing nothing about

and
to the verifier.

To achieve zero-knowledge we need to add random multiples of

to the witness based polynomials (
and
), such as:

where

are scalars chosen randomly from

Note that one very important PLONK idea is totally ignored here: the permutation argument.

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter