Table of Contents

1. A Survey on ZK-Rollups

1.1. A Survey of Interactive Verifiable Computing

file:///home/awang/org/agenda/notes/zkp.html

1.3. Plasma's Code Structure

1.4. ZK-Rollups Simplfied Procedures

1.4.1. Deposit

  1. A user (e.g., Alice) move funds from her L1 account into the Rollup Contract (L1).
  2. The Rollup Contract locks those funds, and the off-chain rollup operator credits Alice's L2 account with teh same amount..
  3. Now ALice's funds "live" inside the rollup.

1.4.2. Off-chain transactions

  1. Users can transact on the rollup without paying L2 gas fees for each each transactions.
  2. The rollup operator periodically aggregates the transactions into batches. Before aggregates transactions, the operator will perform the usual check on those transatcions, and generating inputs for the proving circuit to generate a succint ZK-proof. The oeprator typically generates those four items and feeds them into the circuit as inputs:
  1. Merkle root of the transaction batch

    The operator builds a Merkle tree of all transactions in the batch and provides the root to the circuit.

  2. Merkle proofs for each transaction (batch inclusion)

    For each transaction, the operator provides the Merkle proof (sibling nodes + path bits). The circuit uses these proofs to verify each transaction is actually in the batch.

  3. Merkle proofs for each sends/reciever account (state inclusion)

    The operator provides Merkle proofs showing the sender's account and the receiver's account exist in the current state tree (previous verified by the circuit) for the circuit to check.

  4. Intermediate state roots

    Each transaction updates the rollup state, which modifies the state Merkle tree, resulting in a new Merkle root. That new root is an intermediate state root after transaction i but before transaction i+1.

    Please note that each leaf node is a hash of a user's all states. User can prove that they possess the same state by recomputing the hash of their claimed states and producing the same hash that was originally stored in the Merkle tree (with a corresponding Merkle proof).

1.4.3. Circuit generating proofs

For each batch, the circuit recalculating intermediate and final Merkle roots to check the match the proofs given. More specifically, the circuit checks:

  • Each transactions's proof of batch inclusion.
  • Each sender/receiver's proof of state inclusion.
  • Each transaction's signature validity, balance, nonce, and so on.
  • The correct recomputation of intermediate and final Merkle roots.

For more detailed descrption of the proof generating, please refer to: ZK-SNARKs: How does it works on ZK-Rollups and file:///home/awang/org/agenda/notes/zk-snarks.html

If all constraints pass, the circuit produces a valid proof.

1.4.4. Proof verification

After the proving circuit verifies the correctness of the state updates, the L2 operator submits the computed validty proof & public inputs to the verifier contract on L1.

  1. Inputs
    • SNARKs Proof (a small cryptographic object)
    • Public Inputs (e.g., pre-state root, post-state root, transaction batch root.
    • The verifier contract stores the verification key so it can validate proofs that claim to satisfy the same circuit constrains. In ZK-SNARKs like Groth16 or Plonk, there is a verification key (VK) generated during the setup phase to help validate the proof.
  2. Verification
    • The verifier expects the proof's pre-state root to match the contract's stored root. The verifier contract already knows the latest valid state root for the rollup (stored from a previous update).
    • The contract's verification circuit verifies the proof's validity using the: "verification key" + "proof" + "public inputs" to run the on-chain verification procedures to run the on-chain verification procedure.
  3. Update the contract state tree

    If the proof satisfies the circuit, which means the witness is valid, it means that there exists a sequence of valid transactions that transition the rollup from the previous state (pre-state root) to a new state (post-state root). If the pre-state root matches the root stored in the rollup contract, and the proof is valid, the rollup contract takes the post-state root from the proof and updates its state tree to reflect the rollup's changed state.

1.4.5. Exits

Withdrawing from a ZK-rollup to L1 is straightforward. The user initiates the exit transaction by sending their assets on the rollup to a specified account for burning.

2. ZK-SNARKs: How does it works on ZK-Rollups

A zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) is a cryptographic proof that allows a Prover to convince a Verifier of the correctness of a statement with these key properties:

  1. Succinctness: The proof is constant-sized and can be verified in constant time—regardless of how large the underlying computation is.
  2. Zero-Knowledge (ZK): The proof can hide all the internal details (the "witness") from the verifier.

In many blockchain contexts (e.g., ZK-rollups), we often do not necessarily needed the privacy benefit of zero-knowledge, but we do critically rely on succintness to compress large computations into a tiny proof that can be quickly verifier on-chain, and that is why we need ZK-SNARKs.

Below is a high-level idea of how does ZK-SNARKs works on succint proof generation and soundness of the transactions's validity on-chain.

2.1. Quadratic Arithmetic Programs (QAP)

In the complexity.org, we saw that there are NP-complete problems that are basically only reformulations of all other problems in NP. And as we discussed in The Sum-Check Protocol, some NP-complete (e.g., #-SAT) problem are suitable for picking up as a reduction problem for certain protocol. In 2012, the paper: "Quadratic Span Programs and Succinct NIZKs without PCPs" by Gennaro, Gentry, Parno and Raykova found the NP-complete problem called Quadratic Span Programs (QSP) is particularly well suited for zkSNARKs. A QSP is a representation of boolean circuit as a linear algebratic structure over finite fields, it is used for circuits where the values are binary (0 or 1), and the focus is on enforcing logical operations.

In this section, let's consider a less specialized form of QSP which deals with arithmetic circuit named Quadratic Arithmetic Programs: In short, Quadratic Arithmetic Program is a single polynomial that holds if and only if all the gates in circuit C are satisfied by inputs x. \[ P(x) \;=\; \Bigl(\sum_{j=1}^{n} s_j A_j(x)\Bigr)\, \Bigl(\sum_{j=1}^{n} s_j B_j(x)\Bigr) \;-\; \Bigl(\sum_{j=1}^{n} s_j C_j(x)\Bigr). \] Where \(A_j(x), B_j(x), C_j(x)\) are the polynomials encoding the cofficient vectors of R1CS (Rank-1 Constraint System), the R1CS are the set of coefficients that effectively represent each constrains in the circuit. And a valid witness \(s\) will make \(P(x) = 0\) under all the possible \(x\) evaluation of \(P\), you can get the notion in Walkthrough Example: x3 + x + 5 = 35 that the \(s\) is actually the correct value of all intermediate variables or correct value after each constrains in the circuit.

QAP is the key to understand ZK-SNARks's soundness: if the prover can show a \(s\) that can "satisfy" \(P\) on random input challenge \(x = r\) by the verifier, which strongly implies that \(s\) is correct, thus the evaluation of the circuit must also be correct.

2.2. Pairings

However, if the prover directly reveals the entire witness \(s\) to let verifier checks all constrains, this task is \(\mathcal{O}(\text{size of the circuit}) \), which makes the proof non-succint. Modern ZK-SNARKs protocols use elliptic-curve pairings to create a small proof that can be checked in \(\mathcal{O}(1)\).

The basic idea of using pairings is to leverage the trapdoor function of the Elliptic Curve Discrete Logarithm Problem (ECDLP) Core Security of Elliptic Curves: The Trapdoor Function, to ensure that no one can forge certain polynomial evaluations without knowing the actual witness. Through elliptic-curve pairings, by tying the QAP polynomials and the witness to a single "trapdoor" during the setup, it becomes infeasible for a prover to fabricate a proof on any different polynomial representation. (i.e., we can force the prover to construct the final proof using the correct Quadratic Arithmetic Program (QAP) polynomials \(A, B,\) and \(C\) (which encode the circuit) along with the correct secret witness \(s\)).

3. Example: verifiying computation using gnark

file:///home/awang/benchains/applications/bench-zk/main.go

Actually, comparing Plasma with ZK-Rollups is meaningless from some aspect, since plasma has a challenge period. But we can compare with the throughput in Plasma, ZK-Rollups and Layer 1. Not the finalization time. It is still interesting to see the computational burden in layer 2,

3.1. Structured Design

As the code base increases, it is more and more important to have a modular design to reduce redudancy and debuging efficiency. Typically, for gateway operators, there will be many different packages for each application (plasma, zk-rollups), but also shares some core packages (wrappers, gateway)

3.1.1. Gateway

Package Gateway contains all essencial functions, data structures used to communicate with Fabric and connect with clients. Which is mainly used to forward http transactions to the blockchain.

3.1.2. Wrappers

Package Wrappers contains the internal states and logic of the Operator for the Wrapper application. (Operator)

  1. Fetch newest block from mainchain periodically for newest transactions

The operator's ledger that internally store all user states

  1. UserState

    The operator's ledger that store user balance UserState holds a user's name, balance ($BEN). Each UserState will be commit to the transaction root every period of time. When exiting, user can withdraw all BEN stored on zk-rollups contract chain, but he/she cannot move any unused deposits out.

    • Name string
    • BEN string
  2. Deposit

    The operator's ledger that store transactions Deposit represents an unused deposits which root will also being commited to mainchain.

    • TxID string
    • Args []string

3.1.3. Circuit

Implementing ZK-SNARKs Circuit using gnark library for ZK-Rollups.

3.1.4. Merkle

Package for dealing with Merkle tree, Merkle proof, can be used in Plasma and ZK-Rollups.

4. Current ZK-Rollup Design on Benchains

Created: 2025-01-22 Wed 19:09

Validate