PLONK: A Breakthrough in Efficient ZK-SNARK Technology

Table of Contents

In the world of cryptography, privacy and security are of paramount importance. Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (ZK-SNARKs) have emerged as a powerful cryptographic technology that enables individuals to prove the correctness of their statements without disclosing sensitive information. Among various ZK-SNARKs, PLONK has recently garnered significant attention due to its exceptional efficiency and novel approach. In this article, we delve into the fascinating world of PLONK, exploring its inner workings, benefits, efficiency, and potential future improvements.

I. What is PLONK?

PLONK is a general-purpose zero-knowledge proof scheme introduced by Ariel Gabizon, Zac Williamson, and Oana Ciobotaru. The name "PLONK" stands for "Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge," which is a somewhat playful and unwieldy quasi-backronym.

Zero-knowledge proofs are cryptographic protocols that allow one party (the prover) to demonstrate knowledge of a certain information to another party (the verifier) without revealing any details about the information itself. This property makes them useful in various applications, such as privacy-preserving transactions and secure data sharing.

PLONK builds upon previous advancements in general-purpose zero-knowledge proof protocols like SONIC and Marlin. It introduces several enhancements that aim to improve the usability and efficiency of zero-knowledge proofs.

Source: Understanding PLONK - Vitalik Buterin's website

The key improvements in PLONK are as follows:

Universal and Updateable Trusted Setup: Like many other zero-knowledge proof schemes, PLONK still requires a trusted setup procedure. In a trusted setup, a set of initial parameters is generated, and the security of the scheme depends on keeping these parameters secret. However, PLONK's trusted setup is universal and updateable. This means that instead of needing a separate trusted setup for each program to be proven, there is one single trusted setup that can be used with any program (up to a certain maximum size defined during setup). Additionally, the trusted setup can involve multiple parties, and it remains secure as long as at least one of the participants is honest. This multi-party procedure is sequential, allowing participants to be added over time, which increases the safety of the setup in practice.

Standardized Component - Polynomial Commitment: PLONK relies on a single standardized component called a "polynomial commitment." Polynomial commitments are cryptographic tools that enable efficient verification of polynomial equations. PLONK uses "Kate commitments," which are based on trusted setups and elliptic curve pairings. However, the scheme is flexible, allowing alternative schemes like FRI or DARK to be used instead. This means that different trade-offs between proof size and security assumptions can be achieved by swapping out the polynomial commitment scheme. The ability to choose different schemes caters to various use cases and developer preferences.

II. The concept behind PLONK that we should know

In PLONK, gate constraints and copy constraints are essential concepts used to convert a problem represented by a computer program into a set of polynomial equations that can be efficiently verified as zero-knowledge proofs. These constraints are crucial for creating a structured system of equations that can represent the problem in a compact and verifiable manner.

1. Gate Constraints:

Gate constraints are equations that relate the values of wires attached to the same gate in the circuit. In PLONK, a problem is converted into a circuit representation consisting of logic gates for addition and multiplication. Each gate takes input wires and produces an output wire based on specific operations.

For example, let's consider a multiplication gate with two input wires (A and B) and one output wire (C). The gate constraint for this multiplication gate would be an equation of the form:

C = A * B

Similarly, for an addition gate with input wires (X and Y) and output wire (Z), the gate constraint would be:

Z = X + Y

These gate constraints ensure that the operations performed in the circuit are accurately represented by the polynomial equations, allowing the verifier to confirm the correctness of the computation without knowing the specific inputs provided by the prover.

2. Copy Constraints:

Copy constraints are claims about the equality of different wires anywhere in the circuit. They enforce that the output of one gate is the same as the input of another gate, preserving the flow of data within the circuit. Copy constraints are crucial for maintaining consistency and coherence in the circuit representation.

For example, consider two wires, A and B, that must have the same value. The copy constraint for this scenario would be an equation:

A = B

Copy constraints ensure that data is correctly propagated through the circuit, and they are necessary to create a well-formed system of equations representing the entire problem.

In summary, PLONK relies on gate constraints and copy constraints to convert a problem represented by a computer program into a structured set of polynomial equations. These equations are then used as the basis for generating zero-knowledge proofs. By employing these constraints, PLONK achieves a compact and efficient representation of the problem, making it practical and scalable for various applications that require zero-knowledge proofs. To understand more about formulas and math. We recommend you to read this article from Vitalik.

III. PLONK benefits and features

1. Enhanced Prover Efficiency: PLONK's design dramatically reduces the computational burden on the prover. By requiring only five polynomial commitments and two opening proofs, the prover's workload is significantly diminished when compared to other ZK-SNARKs, such as Sonic. This improvement makes PLONK an appealing choice for applications where efficient computation is critical.

2. Compact SRS Size: PLONK boasts a smaller Structured Reference String (SRS) size, which plays a crucial role in generating ZK-SNARK proofs. In PLONK, the degree of the SRS aligns with the number of gates in a circuit, resulting in a substantial reduction in required storage compared to other ZK-SNARKs. This compact SRS size enhances efficiency and scalability in real-world use cases.

Table Source: PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

III. How efficient is PLONK?

Benchmarking experiments:

Table Source: PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

Benchmarking experiments have been conducted on consumer-grade hardware, revealing compelling results. Extensive benchmarks showcased PLONK's remarkable performance, with proofs constructed in under 23 seconds for circuits containing over a million gates. These results underscore PLONK's efficiency and its ability to handle complex computations with impressive speed.

Comparison to FFT and elliptic curve scalar multiplications:

In a comparison to FFT (Fast Fourier Transform) and elliptic curve scalar multiplications, PLONK demonstrates its prowess. The FFT costs associated with PLONK are on par with elliptic curve scalar multiplications, emphasizing the efficiency of PLONK's computational operations. This demonstrates the optimized execution of essential cryptographic operations within PLONK.

IV. What are the potential future improvements to PLONK?

1. Integration of sparse bi-variate evaluation:

Integration of sparse bi-variate evaluation, a technique employed by other ZK-SNARKs like Fractal and Marlin, is being considered. By incorporating this technique, PLONK can achieve efficient verification of linear constraints. This enhancement could further streamline the validation process, improving overall efficiency.

2. Enhanced efficiency and flexibility:

An exciting prospect for PLONK is the potential to combine permutation checking with sparse bi-variate evaluation, capitalizing on their individual strengths. This integration could lead to improved efficiency and flexibility, enabling PLONK to handle a broader range of gate types effectively.

3. Exploration of optimization opportunities:

The exploration of optimization opportunities is a continuous endeavor in PLONK's development. Researchers are actively investigating techniques and strategies to enhance PLONK's performance across various metrics, including prover and verifier run times, proof length, and SRS (Structured Reference String) size. This commitment to ongoing research and development ensures that PLONK remains at the forefront of efficient cryptographic protocols.

4. Adapting to emerging use cases:

As the cryptographic landscape evolves, PLONK strives to adapt to emerging use cases. Ongoing efforts are focused on aligning PLONK with emerging technologies and applications, ensuring its compatibility and effectiveness in addressing future cryptographic challenges.

By continually seeking improvements, exploring innovative techniques, and adapting to emerging needs, PLONK aims to maintain its position as a cutting-edge ZK-SNARK construction, offering enhanced efficiency, flexibility, and security for a wide range of cryptographic applications.

Conclusion

In summary, PLONK has introduced a new era of efficiency in the realm of ZK-SNARKs. Through its unique permutation argument and simplified representation of Lagrange polynomials, PLONK offers exceptional benefits, including enhanced prover efficiency and reduced SRS size. The benchmarking experiments conducted on consumer-grade hardware have validated PLONK's efficiency, making it an excellent choice for a multitude of real-world applications. With ongoing research focused on potential improvements, PLONK is set to further solidify its position as a groundbreaking ZK-SNARK construction, empowering individuals and organizations with secure and privacy-preserving cryptographic solutions.

About Orochi Network

Orochi Network is a cutting-edge zkOS (An operating system based on zero-knowledge proof) designed to tackle the challenges of computation limitation, data correctness, and data availability in the Web3 industry. With the well-rounded solutions for Web3 Applications, Orochi Network omits the current performance-related barriers and makes ways for more comprehensive dApps hence, becoming the backbone of Web3's infrastructure landscape.