Overview

In this section we cover the general intuition of a zk proof, we outline the steps in creating a zksnark, we define the actors in a zk proof mainly the prover and verifier. We also introduce the elements in a zkproof like the witness, intermediate representation, trusted setups, structured reference strings and random oracles. We also give the context of where the zksnark proof is used in Aleo.

Introduction

In traditional proof systems, like those we encounter in high school, we provide evidence to a verifier to demonstrate our possession of certain information. However, this typically involves divulging that information to the verifier, which can be a security concern. In contrast, Zero-Knowledge (ZK) proofs address this issue by ensuring that neither party trusts the other entirely. The verifier doesn't trust the prover to possess the information, and the prover doesn't trust the verifier to keep it confidential. This might seem like an insurmountable challenge, but through the realms of mathematics and cryptography, solutions have emerged. Enter zkSNARKs—short for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge—a cryptographic marvel that allows one to prove possession of specific information without actually disclosing that information itself.

Let us break down these words:

• Zero-Knowledge: In a zero-knowledge scenario, neither the prover nor the verifier gains any new information beyond what they're supposed to know. Essentially, the verifier gains confidence that the prover possesses the claimed information, while the prover demonstrates their knowledge without disclosing the specifics.
• Succinct: The proof generated by the prover is compact, making it easily distributable across a network and requiring minimal computational resources for verification.
• Non-Interactive: The process of proof and verification involves minimal back-and-forth between the prover and verifier, streamlining the interaction to ensure efficiency.

But how do they work?

In the realm of blockchains, zkSNARKs serve dual roles: enhancing scalability and bolstering privacy. To break it down, zkSNARKs operate as proof systems between a prover (let's call her Alice) and one or more verifiers (let's name them Bob). These systems come into play in the following scenarios:

1. The prover holds sensitive information but seeks to convince the verifier of its possession without divulging the specifics. For instance, imagine proving that a user meets the legal age requirement (above 18 years) without disclosing the exact age.
2. In another scenario, the prover might be a supercomputer whose services the verifier requires. However, since the verifier can't entirely trust the prover, they need assurance that the computation was carried out faithfully and hasn't been tampered with. This use case is critical for scalability and ensuring computational integrity. For example, in a ZK Roll-ups (Layer 2), zkSNARKs are utilized to demonstrate to the layer 1 (predominantly Ethereum) chain that transactions have been executed accurately since the previous roll-up.

To formulate these scenarios as ZK proofs we follow a few steps:

1. We begin by crafting code that represents the statement under scrutiny. In the initial example scenario above, this code might accept an input (such as age), perform a comparison to determine if it exceeds 18, and subsequently yield a true or false outcome. In the second instance, the code could resemble that of a sequencer. This sequencer would receive the present state of an L2 system, arrange incoming transactions, execute them in a specified sequence, and furnish the resulting state.

2. The next step is to convert this code into a polynomial represented as its linear factors and the quotient polynomial. The Scientific community has established a mathematical way to convert any program into a polynomial of this form. We shall explain this process as used in Aleo in an example later in the docs. In essence, the steps followed for this process are

   1. Flattening - conversion of code to logic gate representation.
   2. R1CS - converting the flattened form into a Rank 1 constraint system. The idea is every logic gate represents a single constraint that must be correct for the final result to be correct. The output at each logic gate forms the witness. [PLONK and AIR are other intermidiate arthimetic representations commonly used]
   3. QAP - Quadratic arthimetic Programs that can convert all the constraint drawn by R1CS into a single constraint and makes verification of a zk proof much simpler

   The witness refers to the additional information provided by the prover alongside the proof. This information serves as evidence to validate the truthfulness of the statement being proven. It acts as the supporting evidence that enables the verifier to confirm the accuracy of the proof without needing to know the underlying details.

3. For a ZKSnark the prover and verifier must engage in a trusted set-up which is where the prover commits to an evaluation of the polynomial created for a value chosen by the set of verifiers. This ensures that the prover uses the correct polynomial and cannot cheat.

4. Now we are ready to perform the actual proof exchange and verification. But all zk proof system are probablistic which means the verifier's confidence in the prover increases proportionally to the number of satisfactory verifications. To make this exchange with as much minimal interactions as possible we take the help of Interactive Random Oracles that facilitate the communication between the prover and verifier in one go and establishes negligible probability of a tampered proof. [Some proof system also use commitment scheme like KZG]

In the upcoming sections, we'll delve into the protocol implemented by Aleo that ensures complete privacy. However, before we explore that, it's important to understand how zero-knowledge proofs (zkps) contribute to Aleo's privacy measures.

Aleo operates as a fully private blockchain, where the entirety of a user's account state remains confidential, known solely to the user and inaccessible to anyone else on the chain (to those who dont know the user's view key). Despite this, users need to conduct transactions on the blockchain and transition to new states that gain network consensus. To achieve this, Aleo treats every piece of sensitive user data, requiring consensus, as a "Record". With each user transaction, the input record(s) are invalidated, and new private record(s) representing the updated state are generated. For every transaction, a zk proof is created to ensure the accurate execution of new record creation. These new records are encrypted and stored on the chain alongside proofs of their creation, maintaining their privacy while allowing network validation through proof verification.