Definition and properties:
Zero-knowledge proofs (ZKPs) are an important privacy-enhancing tool from cryptography. They allow proving the validity of a statement related to confidential data without revealing any information beyond the validity of the statement.
In any zero-knowledge proof system, there is a prover who wants to convince a verifier that some statement is true without revealing any other information, e.g., the verifier learns that the prover has more than X in his bank account but nothing else (i.e., the actual amount is not disclosed). Another example is to suppose that a prover holds a birthdate certificate digitally signed by an authority. The prover may have to prove to be at least 18 years old to access some services. A ZKP allows this without the prover revealing the birthdate or any other information.
The ZKP proof system must have three properties:
Completeness: If the statement is true and both prover and verifier follow the protocol, the verifier will accept.
Soundness: If the statement is false(cheating prover), and the verifier follows the protocol, the verifier will not be convinced.
Zero-knowledge: If the statement is true and the prover follows the protocol, the verifier will not learn any confidential information from the interaction with the prover but the fact the statement is true.
ZKPs provide cryptographic proof of computational integrity (CI). Much of today's cryptographic primitives offer security services for data. For example, encryption schemes provide confidentiality, authenticity, integrity, etc for data. What about security services for computation?
Computation integrity(CI): It allows people to compute correctly and securely without revealing secret information. It is based on cryptographic proofs.
Cryptographic proofs: is a mathematical proof that proves computation integrity. They are super short and super fast to verify.
Blockchain application
In the first zero-knowledge protocols, the prover and verifier had to communicate back and forth for multiple rounds, but in “non-interactive” constructions, the proof consists of a single message sent from the prover to the verifier. In the context of Blockchain, we need a “non-interactive” version of zero-knowledge proof.
Non-interactive zero-knowledge (NIZK) proof system, in which the protocol involves a single message from the prover to the verifier.
A powerful technique for converting interactive proof systems into non-interactive ones is the Fiat-Shamir transform.
ZKP is used to enhance blockchain capabilities around two different aspects: scalability and privacy.
In public blockchains, computational integrity refers to the correctness of transactions executed on a network. Most blockchains achieve it by making other computers (nodes) rerun each transaction: re-execution.
A ZKP-proof system can also prove the correctness of computation performed off-chain without nodes replaying every computation step. This is where ZKP becomes useful for scaling blockchains. They are cryptographic proofs for computation integrity(correctness of computation) that are super short and fast to verify by Blockchain nodes.
With the L2 ecosystem, we have ZK-Rollups systems based on ZKP to solve the scalability problem. There are multiple projects: Polygon Hermez, zkSync, Aztec, etc. Those projects leads to different types of ZK-EVMs.
Computational integrity-proof systems can help solve a fundamental problem in decentralized blockchains: Privacy. They provide privacy by shielding some inputs of a computation without compromising integrity.
Cryptographic proofs offer privacy-preserving integrity for computation.
Cryptographic proofs generated using ZKP can prove the validity of a transaction without revealing the private inputs.
Private transactions on public Blockchain: Tornado cash, IronFish, private Dapps(Aleo).
ZKP system construction paradigm
There are multiple paradigms for constructing zero-knowledge proofs for general statements.
In the last years, we have a modern perspective on building a ZKP system based on the composition of an information-theoretic (IT) system, based on ideal components, a cryptographic compiler (CC), and an arithmetization system to encode the actual public data (statement and instance) and private data (witness) that determine the specific proof taking place.
Arithmetization
We can’t apply a proof system directly to a computer program. So, we need to transfer that computer program into another representation equivalent to a probabilistic proofs system.
Every IT-proof system has some native representation in which it accepts the statement to be proven. Common ones include polynomial equations, Boolean circuits, and arithmetic circuits.
We can reduce a computational statement to arithmetic circuits which are then converted to a set of constraints (typically, A rank-1 constraint system (R1CS)).
Proof systems include some internal conversion from some natural format to their lower-level native (e.g., polynomial equations).
Example: You might start with a conceptual statement like this: “I have more than X in my bank account”. Arithmetization translates it into an algebraic statement involving a set of bounded-degree polynomials, like: I know three polynomials F(X), H(X), G(X), each of degree less than 3,000, such that this equality holds: F(X)*-H(X) = (X²⁰⁰⁰–1)*G(X)
Information-theoretic (IT) system
An Information-theoretic proof system provides soundness and zero-knowledge guarantees even when the prover and the verifier are computationally unbounded. They use an idealized model of interaction.
Probabilistic Proofs is a variety of information-theoretic models that differ in what kinds of powers and capabilities we grant to the verifier.
There are multiple information-theoretically secure protocols, such as interactive proof (IPs), multi-prover interactive proof (MIPs), probabilistically checkable proof (PCPs), interactive oracle proofs (IOPs), or polynomial IOP (PIOP) is a generalization of a standard IOP.
Cryptographic compiler (CC)
The cryptographic compiler removes the idealized assumptions underlying the information-theoretic proof system by transforming it into a protocol involving direct interaction between the prover and the verifier.
To achieve a proof that is useful in the real world, the IT proof system then needs to be instantiated by a CC that removes the ideal components.
The concrete ZKP schemes emerge from combining an Information-theoretic proof system and a crypto compiler. IPs, MIPs, PCPs/IOPs, and PIOPs can all be transformed into succinct interactive arguments by combining them with a cryptographic primitive called a polynomial commitment scheme(PCS). The most used combination:
Information-theoretic (IT): Polynomial interactive oracle proof(Polynomial IOP) for R1CS or circuit satisfiability. There are different Polynomial IOP approaches.
Cryptographic compiler (CC): polynomial commitment scheme(PCS).There are several different PCS approaches like:
- FRI(Low-level tech: Hash function)
- KZG10(Low-level tech: pairing group )
- Bulletproof(Low-level tech: discrete log group)
- etc
There are different implementations of a proof system: Groth16, Sonic, Marlin, Plonk, etc.
Proof system implementation
The implementation of a proof system can be divided into two parts: Frontend and Backend.
Frontend: It is the arithmetization step, which converts a high-level representation of the statement to the native representation. In most cases, it is the transformation from a turning complete computer program into a circuit.
The front end ensures the circuit is equivalent to the original computer program. A circuit is like a kind of low-level language. A frontend consists of:
The specification of a high-level language for expressing statements.
A compiler that converts relations expressed in a high-level language into low-level relations suitable for some backend(s). For example, this may produce an R1CS constraint system.
In the front end, some people write a low-level language like Bellman or Circom to generate the circuit gate by gate.
There are libraries in different languages like Rust(bellman: has circuit traits and primitive structures to build circuits). There are also various domain-specific language (DSLs) implementations like ZoKrates which allows writing pseudocode to generate circuit, witness, and generate/verify proof. They target different kinds of circuits like:
R1CS: Bellman, Circom, ZoKrates, Leo.
Plonk: Noir, upa
AIR: Cairo, Air assembly
The front end of a ZK proof system implementation provides means to express statements in a convenient language and to prove such statements in zero-knowledge by compiling them into a low-level representation and invoking a suitable ZK backend.
Backends: Cryptographic proof System Implementations
The backend of a ZK proof implementation is the portion of the software that contains an implementation of the low-level cryptographic protocol. It proves statements where the instance and witness are expressed as variable assignments, and relations are expressed via low-level languages (such as arithmetic circuits, Boolean circuits, R1CS/QAP constraint systems, or arithmetic constraint satisfaction problems).
The backend typically consists of a concrete implementation of a proposed ZK proof system(s) (often specified by the pseudocode in a paper publication).
SNARK
A SNARK is an important cryptographic primitive that has many applications in web3 from scaling blockchains (e.g., L2 rollups) to ensuring privacy (e.g., zero knowledge).
SNARK is the most used and efficient ZKP-proof system within blockchain.
SNARK stands for Succinct Non-interactive Argument of Knowledge.
There is an extension to a SNARK called ZK-SNARK: the proof “reveals nothing” about private inputs.
ZK-SNARK is the ability to prove honest computation without revealing private inputs.
ZK-SNARKS: this is a kind of ZKP that satisfies six properties. The inherent properties of ZKP: are completeness, soundness, and zero knowledge. They have three additional properties:
Non-interactive: the prover only sends one message to the verifier.
Publicly verifiable: everyone can verify the proof without any secrets.
Succinct: the proof should be very short and very fast to verify.
There are different SNARK implementations (Groth16, Marlin, Plonk, Bulletproofs,etc). They are trade-offs between multiple aspects:
Proof size
Prover time
Verifier time
Trusted setup
Quantum resistant
Non-interactive zero-knowledge (NIZK) proof system, in which the protocol involves a single message from the prover to the verifier. This message may depend on a common reference string (CRS) that can either be uniformly random (URS) or structured (SRS). This is done using a trusted setup.
A trusted setup called URS(uniform reference string) knows as a public or transparent setup. It just basically consists of public randomness. Another complicated type of trusted setup is called SRS(structured reference string) also known as a private setup. The SRS can be circuit-specific or universal setup.
In non-transparent SNARK, the prover will have to know what’s called a structured reference string(SRS). There’ll be a trap door such that if the prover knew the trap door it could easily find convincing proof of a false statement. To sort minimize the trust assumption, people will run a giant secure multi-party computation protocol with hundreds of participants(MPC ceremony). If the SRS is not universal though, the ceremony needs to be re-run every time the protocol changes.
If the SNARK is transparent, you don’t worry about that at all. No trusted setup, no trapdoor, could not forge proof of false statements.
