ZKP— PlonK Algorithm Introduction

Initial Parameters SRS

For those of you know about Groth16 should be somewhat familiar with CRS — Common Reference String. In a similar fashion, SRS only has Universal data, the Structured Reference String.

Polynomial Commitment

Batched Polynomial Commitment is based on a very simple theory, which happens to be the most important foundation of PlonK. Polynomial commitment is to prove multiple polynomials. The paper has explained single-type polynomial commiement and multi-type polynomial (batched) algorithms.

Single-Polynomial Commitment

On page 11, the paper breaks down in details principles of single polynomial commiement. There are three steps:

Multi-Polynomial Commitment

Basing on single-polynomial commitment, let’s move on to the mult-polynomial commitment. Multi-polynomial means that multiple polynomials are given, and we need to prove their value matches the commitment. In PlonK algorithm, we use two types of polynomial commitment. Unlike single polynomial commitment, this needs Vpc to provide two random messages.

Polynomial Permutation

PlonK algorithm relies on the proof of polynomial permutation. Here the polynomial permutation means that swapping the input of a specific polynomial, the output doesn’t change.

Li(X)

Li(X) refers to the Lagrange function value of the ith term in a polynomial. In a finite subgroup H, the generator is g, and the power is n. If a=g^i, then Li(a)=1; otherwise, Li(a) = 0.

ID and Permutation

Before we get into polynomial permutation, we need to define the ID for the input of polynomial. Because in a definite field, the input is g^i, the input can be represented indirectly with i. SID is an order index. Sigma(i) is permutation function.

Permutation protocol

Permutation could happen following situations:

Fiat-Shamir Heuristic Algorithm

Fiat-Shamir Heuristic Algorithm has two different types: interactive and non-interactive. You can check out the wiki if interested:

Interactive Type:

To prove Peggy knows one specific value x. and y=g^x, Peggy and Victor both choose a random number: v and c. Peggy provides g^v and r=v-cx, so that Victor can verify.

Non-interactive Type:

In interactive type algorithm, Victor has to provide a random number. In non-interactive type, this random number is substituted by public hash value.

Circuit Principle and Constraint System

Vitalik posted on his blog this article about PlonK, which covers the princicple of circuit.

PlonK protocol

Last chapter of the paper, chapter 8 gives an conclusion of the whole PlonK agreement. PlonK agreement is based on polynomial commitment andFiat-Shamir heuristic algorithm. Given 3n witness, and coefficient vector and permutation function of a polynomial, prove that the constraint exists for each gate:

Public Information

PlonK agreement public information, including gate coefficient, permutation function and public input.

Proving Process:

The proving process has 5 rounds.

Verification Process:

Verification process has some simple data check. Main steps listed below:

How to constrain?

For those of you paying attention, you might be curious how all these calculations guarantee to meet the circuit constraint? Even if multi-polynomial commitment matches the challenge, it only garantees the following function’s polynomial form:

  1. a/b/c 2. r 3. z 4. t 5. Permutation function

Performance Comparison

The paper also gives performance comparison in first chapter.

Performance

Verify Performance

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Trapdoor-Tech

Trapdoor-Tech

Trapdoor-Tech tries to connect the world with zero-knowledge proof technologies. zk-SNARK/STARK solution and proving acceleration are our first small steps :)