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.

## Leave A Comment