#1 — Kimchi & Proto-Danksharding

In the world of cryptography, polynomial commitment schemes and zero-knowledge proofs are vital for maintaining data integrity, privacy, and efficiency.

This is the first article in a series of articles where we will dive deeper into Mina’s Kimchi proof system and compare it to the Ethereum Proto-Danksharding design as an example.

KZG Commitments (Kate Commitments), SNARKs, and the PLONK Protocol each play a crucial role in enabling these properties, especially within blockchain and privacy-preserving applications.

This article will cover the terms and mathematical operations you need to know at a basic level. I will cover the math in my X account, which you can access at the end of the article. Enjoy your reading.

KZG Commitments

KZG commitments, introduced by Kate, Zaverucha, and Goldberg in 2010. This scheme is a polynomial commitment scheme that allows a prover to commit to a polynomial in such a way that they can later reveal its evaluation at specific points, along with succinct proofs of correctness, without revealing the entire polynomial.

One of the standout features of KZG commitments is their constant-sized commitments and proofs, irrespective of the degree of the polynomial.

The KZG scheme relies on pairing-friendly elliptic curves and a trusted setup known as a Structured Reference String (SRS). The SRS involves precomputed elliptic curve points for a secret value and a generator of the elliptic curve group.

The security of KZG commitments depends on the hardness of the Discrete Logarithm Problem (DLP) in elliptic curve groups and the secrecy secret value.

To generate a commitment to a polynomial of degree , the prover must perform field and elliptic curve operations. The commitment is calculated by combining the polynomial coefficients with the SRS elements.

To prove that the polynomial evaluates to a certain value at a point , the prover computes a witness polynomial and commits to it. Polynomial division can be optimized using Fast Fourier Transforms (FFTs), resulting in a proof generation time complexity of O( n.log(n) ). The verifier can then check pairing equations, and since the commitment and proof sizes are constant, verification is done in constant time.

In the context of blockchain technologies, KZG commitments are instrumental. For example, in Ethereum’s proto-danksharding (EIP-4844), KZG commitments are used to commit to large data blobs efficiently, which is essential for data availability in rollups. By using KZG commitments, Ethereum can ensure that data required by a rollup is accessible and verifiable without imposing significant overhead on the network.

To illustrate, imagine a scenario where Ethereum is processing a large number of transactions using rollups. Instead of storing all the transaction data on-chain, which would be costly and inefficient, KZG commitments allow Ethereum to store a succinct commitment to the data, ensuring it is available and verifiable by anyone who needs it.

This is akin to having a digital “receipt” that proves the correctness of all the data without needing to carry the entire dataset.

SNARKs: Succinct Non-Interactive Arguments of Knowledge

SNARKs (Succinct Non-Interactive Arguments of Knowledge) are proof systems that enable a prover to convince a verifier that a specific computational statement is true without revealing any additional information.

SNARKs are characterized by their succinctness, which means that the proofs are short and verification times are fast, regardless of the complexity of the original computation.

This makes SNARKs highly efficient for use in blockchain applications, where many participants need to verify proofs quickly.

In SNARK systems, the computation is represented as an arithmetic circuit or a set of polynomial equations over a finite field. The prover constructs a proof that they know a valid witness (i.e., input values that satisfy the circuit) without revealing the witness itself.

Proof generation involves complex operations like polynomial arithmetic, cryptographic hashing, and group exponentiations. The time complexity for proof generation is typically O( n.log(n) ), where represents the number of gates or constraints in the circuit.

A real world example of SNARKs is their use in Zcash, a privacy-focused cryptocurrency. In Zcash, SNARKs are used to enable shielded transactions, where the details of the sender, receiver, and transaction amount are hidden from the public.

This is similar to proving you have enough money to buy something without actually showing your bank account balance.

The verifier, on the other hand, can validate the proof using a small number of cryptographic operations, often involving pairings on elliptic curves.

Verification time is typically constant or logarithmic in “n”, significantly faster than verifying the entire computation directly.

This efficiency is a key advantage of SNARKs, making them highly suitable for practical applications where computational integrity must be maintained without high overhead.

PLONK Protocol

PLONK, which stands for “Permutation Argument over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge” is a zk-SNARK protocol that improves upon previous constructions by introducing a universal and updatable trusted setup. This setup can be used for any circuit or computation up to a certain size and can be contributed to by multiple parties, enhancing its security.

PLONK optimizes both prover and verifier time complexities while simplifying the process of representing computations in a form suitable for SNARKs.

In PLONK, computations are represented using polynomials in the Lagrange basis, allowing for efficient evaluation and manipulation of polynomials at specific points, particularly roots of unity.

The protocol includes a permutation argument that ensures that variables (or “wires” in the circuit) are correctly connected across different gates or constraints, enforcing consistency through permutation checks on certain polynomials that represent the wiring of the circuit.

The proof generation time complexity in PLONK is O( n.log(n) ) , where “n” is the number of constraints in the circuit.

This efficiency is due to the use of FFTs for polynomial arithmetic, which speeds up essential operations such as polynomial multiplication and division. The prover commits to several polynomials that encode the circuit’s constraints and applies zero-knowledge blinding factors to maintain privacy. These polynomials are then committed using a polynomial commitment scheme, such as KZG commitments.

Verification in PLONK is also efficient. The verifier checks a small number of pairing equations and evaluates polynomials at randomly chosen challenge points, ensuring that the committed polynomials satisfy the circuit’s constraints and that the permutation argument holds.

The use of KZG commitments, with their constant-size commitments and proofs, further enhances PLONK’s efficiency and scalability, making it suitable for blockchain systems that require secure and private verification without high verification overhead.

The Mina blockchain utilizes a variant of PLONK called the Kimchi proof system.

Kimchi introduces optimizations for recursive proof composition, allowing Mina to maintain a constant-sized blockchain.

Each new block in Mina contains a proof that attests to the validity of all previous blocks, achieved through recursive zk-SNARKs. While this recursive nature increases the complexity of proof generation (since each proof depends on the previous ones), the verification remains efficient, enabling participants to verify the entire blockchain state quickly and with minimal computational resources.

Imagine a scenario where you want to store all the previous states of a system in a very compact way.

Mina’s approach is like having a single, continually updated document that proves every change ever made to the system, without needing to keep all the individual documents.

This makes Mina one of the lightest blockchains, allowing even fridges to fully verify the network.

Conclusion

KZG commitments, SNARKs, and the PLONK protocol together form a powerful toolkit for building secure, scalable, and efficient cryptographic systems. KZG commitments provide succinct and constant-sized proofs for polynomial evaluations, while SNARKs enable efficient verification of complex computations. PLONK, building on both of these, offers a versatile and efficient protocol with a universal setup, making it highly practical for real-world applications such as blockchain and privacy-preserving computations.

The interplay of these cryptographic techniques ensures that complex operations can be performed securely, with minimal overhead, and verified efficiently, key requirements for the modern digital age.

Thanks for reading.

X : blockofchain