Overview of Computation in Zero-Knowledge Proofs

surface exploration of the concept of zero-knowledge proofs and how it relates to computational integrity...

Overview of Computation in Zero-Knowledge Proofs

The category of cryptographic proof system this book will be focusing on is the Zero Knowledge proof system. A zero-knowledge proof system is a cryptographic protocol that allows one party, known as the prover, to convince another party, known as the verifier, that a particular statement is true without revealing any information beyond the validity of the statement itself. This remarkable concept ensures that the verifier gains no additional knowledge about the prover’s secret or the underlying data beyond the fact that the statement is correct.

Going into the protocol, the Prover most times has the Problem which it claims to have a solution to, and the Verifer is expecting a Proof that states that the Prover has a valid Solution to the Problem.

The process of most zero-knowledge proof systems goes this way;

problem to snark

This chapter will be focused on navigating from Problem -> Computation -> Algebraic Circuit -> Arithmetization -> Quadratic Arithemetic Program.

Problem

This is the computable problem that can be expressed mathematically, which the Prover can compute the solution to. An example of the Problem we would be playing is the IsZero problem.

The IsZero problem in the context of Zero-Knowledge Proofs (ZKP) and circuit-based proving systems like Circom refers to the challenge of checking whether a given value is zero within an arithmetic circuit. This operation is essential for many cryptographic protocols and constraints, but it is non-trivial to implement efficiently within the confines of ZKP-friendly arithmetic.

This problem can be expressed as a circom circuit this way;

template IsZero() {
    signal input in;
    signal output out;
    signal inv;
    // Constraint to ensure inv is the inverse of 'in' when 'in' is non-zero
    inv <== in != 0 ? 1/in : 0;
    // When 'in' is zero, inv will be zero
    out <== 1 - in * inv;
}

component isZero = IsZero();

isZero.in <== someValue;

now we've declared this problem in the form of a circom circuit, this next step is to represent this problem in the form of a Algebraic Curcuit.

Algebraic Circuit

An algebraic circuit is a mathematical representation used to perform computations over a field by composing basic arithmetic operations (addition and multiplication) and constants. These circuits are integral to the design and analysis of cryptographic proof systems, especially in the context of zero-knowledge proofs (ZKPs). Algebraic circuits help convert computational problems into polynomial forms, which are then used to construct proofs that verify the correctness of computations without revealing the inputs.

Components of an Algebraic Circuit

1. Inputs: The variables or elements from a finite field that serve as the starting values for the circuit.

2. Gates: • Addition Gates: Sum two inputs from the field. • Multiplication Gates: Multiply two inputs from the field.

3. Constants: Fixed elements from the field used in operations.

4. Outputs: The results of the computations, which are also elements of the field.

Structure of an Algebraic Circuit An algebraic circuit can be visualized as a directed acyclic graph (DAG) where: • Nodes represent inputs, gates, and outputs. • Edges represent the flow of data from one operation to another.

Recall the IsZero problem we are playing with, this is how it would be expressed as a Algebraic Circuit;

is zero algebraic

after obtaining the Algebraic Circuit, the next step in the process is to represent this algebraic circuit in an Intermidiate Representation like R1CS, Plonkish, AIR and so on. This can be done by Arithmetization

Arithmetization

Arithmetization is the process of taking a circuit description via a programming language and turning it into a system of mathematical constraints that enable fast verification. With this set of mathematical constraints, which we’ll dive further into below, a verifier can run a small number of algebraic checks to show with high probability that the prover is not lying.

got this definition from this blog.

Arithmetization Techniques Here are the Arithmetization techniques this book would be exploring;

1. R1CS

2. Plonkish

3. AIR

4. CCS

In summary, the journey from a computable problem to a verifiable proof in zero-knowledge proof systems involves several crucial steps: expressing the problem in an arithmetic circuit, converting it into an algebraic circuit, and then arithmetizing it into mathematical constraints suitable for efficient verification. By breaking down these steps and examining each one in detail, we gain a deeper understanding of how zero-knowledge proofs ensure privacy and integrity. This chapter has provided a foundational overview, setting the stage for further exploration of specific arithmetization techniques like R1CS, Plonkish, AIR, and CCS, which are essential for creating robust and efficient cryptographic proof systems.