1
$\begingroup$

This is Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=vxyoPM2m7Yg

I went through the video multiple times & also tried to go through the original PLONK paper - https://eprint.iacr.org/2019/953.pdf

Boneh's explanation of PLONK involves the steps

1) Boneh consider's the trace of the equation as the inputs (public & private) & the gates. Let's say there are 3 gates & 3 inputs, each gate can be considered as

$Left$ $o$ $Right$ = $Output$

So 3 gates become 9 points. Adding to this, the 3 points from the 3 inputs. We get a total of 12 points.

So he interpolates a polynomial $P(X)$ of degree 11 using the 12 points.

PLONK Paper:. I don't see the PLONK paper doing this step at all.

2) Boneh proves that this polynomial is the input correctly by interpolating a polynomial $v(X)$ for the 3 inputs & verifies if $P = v$ at the 3 points.

PLONK Paper: Since the PLONK Paper never creates $P(X)$, it doesn't do this step either.

3) Boneh proves that every gate is evaluated correctly

He creates a selector Polynomial $S(x)$ which represents whether a gate is an addition or a multiplication gate & then checks whether the below is true

$S(y)\cdot [P(y) + P(\omega Y)] + (1-S(y))\cdot P(y)\cdot P(\omega Y) = P(\omega^2 Y)$

PLONK Paper: The PLONK Paper does do this though they expresses this polynomial in a slightly different way

$q_L \cdot f_L + q_R \cdot f_R + q_O \cdot f_O + q_M \cdot f_L \cdot f_R + q_C = 0$

Here $q_L$, $q_R$ & $q_O$ act like the selector polynomials & I believe do the same thing which Boneh does with his $S(x)$ selector polynomial.

So I believe this step would match in both cases.

4) Boneh proves that the wiring has been done correctly using a prescribed permuation check.

PLONK Paper: This is also done in the PLONK Paper, they call it "copy constraints" checking using a permutation done by grand product argument.

So this also matches.

So I am confused as to why the first 2 steps aren't covered in the PLONK Paper. And I am just unable to recognize them in the paper? The PAPER covers 10x as much as Boneh's video - in terms of details, proofs, optimisations etc so I may be not recognising it in the paper - which is what i want to find out.

I am looking to find out if those steps get implicitly performed in some other step in the paper - if so, which steps are those?

Or if the same check/purpose is done in a different way (like for e.g. the selector polynomial looks quite different between the two) - if so, I want to know which step is it in the paper?

$\endgroup$
0

2 Answers 2

0
$\begingroup$

It is very common for a talk/presentation to not match all the details of a paper. There can be many valid reasons for this.

  1. Illustrating crucial concepts without too much detail that won't fit into a regular length talk/lecture
  2. There may be multiple versions of the same paper, especially in applied fields, as details get updated/improved

Maybe try to see if an earlier preprint version of the paper is available. If anyone else here has noticed this they may respond.

$\endgroup$
6
  • $\begingroup$ It's not that the talk doesn't cover everything in the paper. It's the opposite - it's that the paper doesn't cover 2 seemingly non trivial steps in the talk. The paper is far more detailed as I mentioned in the question but 2 of the proofs in Boneh's video aren't there in the Paper. $\endgroup$
    – user93353
    Commented Apr 27, 2023 at 11:23
  • $\begingroup$ Are you sure there are no other journal versions of the paper? Another reason may be that some aspects are in patent applications so they may not be written down in full detail in a paper but can informally be covered in a talk $\endgroup$
    – kodlu
    Commented Apr 27, 2023 at 11:24
  • $\begingroup$ I checked everywhere. I also checked Multiple PLONK tutorials & PLONK Blogs. None of them cover the 2 extra steps Boneh has in the video - other tutorials & blogs have less than the paper but they don't have anything which the paper doesn't have. $\endgroup$
    – user93353
    Commented Apr 27, 2023 at 11:26
  • $\begingroup$ OK, maybe someone has some knowledge, but in general answering why questions is pretty hard. $\endgroup$
    – kodlu
    Commented Apr 27, 2023 at 11:27
  • $\begingroup$ I am looking to see if it is included in the paper in another way which I am missing or if it's implicitly done in some other step. I will update the question the reflect it. $\endgroup$
    – user93353
    Commented Apr 27, 2023 at 11:29
0
$\begingroup$

In the talk, Boneh shows how to obtain an "arithmetization" from an arithmetic circuit, which represents a specific computation. In the paper, Gabizon does provide a proof system, given a specific arithmetization (also called "Plonkish", the equivalent traditional arithmetization is a "Rank 1 Constraint System", which other proof systems were already based on in the past.)

The transformation from:

source code (describing the arithmetic circuit) -> arithmetization

is not given in the paper, as it is not relevant to describe how the system works over an arithmetized circuit. The paper only introduces a proof system on top of a set of polynomials, which encode a specific relation.

You can see this e.g. in Section 8.1 - "Polynomials that define a specific circuit", which generalizes the arithmetization over a circuit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.