Introduction to the PLONK protocol and 'KZG Universal Trusted setup

The PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge) protocol is a groundbreaking zero-knowledge proving system designed for scalability and efficiency in blockchain and cryptographic applications. Its modularity, simplicity, and reduced proving times make it a favored choice for developers and researchers working on zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge).

Introduced in 2019, PLONK revolutionized the proving system landscape by addressing key limitations in previous protocols, such as the dependency on trusted setups for each application. PLONK employs universal trusted setups and leverages powerful cryptographic primitives, including polynomial commitment schemes, to achieve succinct, efficient, and highly verifiable proofs.

This blog aims to provide a deep technical dive into the mechanics of the PLONK protocol, breaking down its components, theoretical underpinnings, and practical implementations. Whether you’re a researcher, a developer, or just someone passionate about cryptographic proving systems, this article will serve as a comprehensive guide to understanding and implementing PLONK.

Similar to a good number of zkSNARK protocols, this protocol life-cycle could be described as follows;

1. Computation

2. Algebraic circuit

3. Intermediate Representation. example R1CS

4. Polynomials structure. QAP in the groth16 protocol

5. linear interactive oracle protocol. birthed from information theory

6. SNARK

Protocol Overview

This is just a trailer showing what would be explored in this protocol. An overview of the PLONK protocol can be viewed in this light;

• Universal Trusted Setup

• Computation Expression as Circuit and Circuit compilation

• Witness Generation and Proof generation

• Verification

Notation

• $\mathbb{F}$: Denotes a finite field.
• $\omega$: represents the roots of Unity in $\mathbb{F}$, that is $\omega^n = 1$ and $\omega^k \neq 1$ for $0 < k < n$
• All polynomials have coefficients $\mathbb{F}$, and the variable is usually denoted by $X$
• we denote this set as $F[X]$
• We represent polynomials by single letters like $p,a,b,z$
• $L_i$: This indicates Lagrange basis
• $M$: this indicates a Matrix
• $G$: Group generator
• $[x]_1$: An Element in group $1$
• $[x]_2$: An Element in group $2$

PLONK: Universal Trusted Setup

The reason why a Trusted Setup is important is due to the nature of the polynomial commitment scheme which in this case is the KZG polynomial commitment scheme which needs a One-time Universal Trusted setup to carryout its polynomial commitment duties, the reason why this trusted setup is called Universal is that, the same Trusted Setup can be used across various circuits hereby reducing the security concerns as regarding Trust, knowing fully well that, should the trusted setup be compromised, invalid proofs can be generated. Let's explore how this universal trusted setup can be carried out and tailored to the PLONK protocol.

A polynomial commitment scheme is a cryptographic protocol that allows someone to commit to a polynomial while keeping its coefficients hidden, yet still be able to prove evaluations of the polynomial at specific points. It's like making a secure promise about a polynomial without revealing it entirely.

Here are the steps involved in KZG PCS;

1. Setup

2. Commit to polynomial

3. Prove an Evaluation

4. Verify an evaluation proof

We would only be looking into the setup stage of this polynomial commitment scheme. This is the same setup needed in the PLONK protocol.

Setup

• The first step is a one-time trusted setup. Once this step is completed, the other steps can be repeated to commit to and reveal various polynomials.

• Let $g$ be a generator of some pairing-friendly elliptic curve group $G$
• Let $l$ be the maximum degree of the polynomials we want to commit to
• Pick some random field element $τ \in F_p$
• Compute $(g,g^τ,g^{τ^2},…,g^{τ^l})$, and release it publicly

Note that $\tau$ should not be revealed - it is a secret parameter of the setup, and should be discarded after the setup ceremony such that nobody can figure out its value.

The obtained exponents is regarded as the Structured Referenced String (SRS), which would be used at other stages of the PCS.

This is all that is needed for the setup phase of the protocol.