Zero-knowledge proof generation and commitment verification

Merlin Chain's ZK-L2 leverages Polygon CDK technology, with zero-knowledge proofs powered by Lumoz's decentralized ZK computing power network.

Generation of Proof

Similar to other Polygon CDK chains, Merlin Chain handles the proof generation and verification of transactions through a component called zkProver, which is a zero-knowledge proof generator. All rules for valid transactions are implemented and executed within the zkProver.

The zkProver executes complex mathematical calculations in the form of polynomials and assembly language, followed by verification on smart contracts. These rules can be seen as constraints that transactions must adhere to in order to modify the state tree or exit the tree.

Interaction with Nodes and Databases (DB)

zkProver mainly interacts with two components, namely nodes and databases. Here is a chart that can clearly explain the process.

As shown in the flowchart above, the entire interaction is divided into four steps.

1 → The node sends the contents of the Merkle tree to the database and stores them there

2 → Then the node sends the input transaction to zkProver

3 → zkProver accesses the database and obtains the information required to generate verifiable proofs of transactions sent by nodes. This information consists of Merkle roots, related sibling keys, and hash values

4 → zkProver then generates transaction proofs and sends these proofs back to the node

However, this is actually just the tip of the iceberg of what zkProver has done. How zkProver actually creates these verifiable transaction proofs involves more details. It will be revealed when we delve into the state machine below.

State Machine

zkProver follows the Modularization design. Except for a few components, it mainly consists of a fine-state machine cluster. It has a total of 13 fine-state machines.

  • Main fine-state machine

  • Auxiliary fine-state machine → Binary SM, Storage SM, Memory SM, Arithmetic SM, Keccak function SM, PoseidonG SM,

  • Auxiliary fine-state machine → Padding-PG SM, Padding-KK SM, Bits2Field SM, Memory Alignment SM, Byte4 SM, ROM SM.

Due to the Modularization design of zkProver, the main finite-state machine can delegate as many tasks as possible to other specialized finite-state machines. This greatly improves the efficiency of the Main SM.

Auxiliary Fine-State Machine

The main SM actuator directly instructs each auxiliary fine-state machine by sending appropriate instructions called "operations", as shown in the figure below.

The dark box in Main SM frame is not a fine-state machine, but represents an operation, which is a specific instruction from the main fine-state machine to the relevant auxiliary fine-state machine. These instructions specify how the state in the fine-state machine should be transitioned. However, each action, whether from the general main SM or specific SM, must be supported by evidence of its correct execution.

There are some natural dependencies between them.

  • Using the storage finite-state machine and Poseidon finite-state machine of the Merkel tree, it is necessary to calculate the hash value of all nodes in the Merkel tree.

  • Each hash finite-state machine Keccak Function SM and PoseidonG SM, as well as their respective fill finite-state machines, namely Padding-KK SM and Padding-PG SM.

Zero-knowledge assembly

As an assembly language, zero-knowledge assembly (or zkASM) language is specifically used to map instructions from the main finite-state machine of zkProver to other finite-state machines. For finite-state machines with firmware, zkASM is the interpreter of the firmware.

The specified assembly code is generated by the zkASM code using instructions from the main finite-state machine to specify how a given SM executor must perform calculations. The Executor strictly adheres to the logic and conventions of the zkASM code, making calculation verification simple.

Polynomial Identity Language

Polynomial Identity Language (or PIL) is specifically designed for zkProver. Almost all finite-state machines use polynomials to express calculations. Therefore, state transitions in finite-state machines must satisfy the calculation of specific polynomial identities.

Polygon zkEVM is creating the most effective solution to solve the blockchain trilemma of privacy, security, and scalability. Its background is an efficient zero-knowledge commitment scheme. So far, the most reliable and effective commitment scheme is the polynomial commitment scheme.

Therefore, it is convenient to convert calculations into some kind of polynomial language, where verification essentially boils down to verifying whether the execution satisfies a specific polynomial identity. Therefore, all PIL codes in the zkProver finite-state machine constitute the DNA of the verifier code.

Proving Execution Correctness

The final-state machine of zkProver is designed to execute programs and ensure that these programs execute correctly.

Therefore, each auxiliary fine-state machine contains its own actuator and a PIL program that can be used to check the correct execution of all instructions from the main SM actuator.

The following is a step-by-step overview of how the system implements transaction proof/verification.

  • Represent the given computation as a fine-state machine (SM),

  • Representing the state change of SM as a polynomial,

  • Capture the tracking of state changes (called execution tracking) as rows in the Look up table.

  • Form the polynomial identities/constraints satisfied by these state transitions.

  • Prover uses a specific polynomial commitment scheme to submit and prove knowledge of the submitted polynomial.

  • Plookup is one of the ways to check if the polynomial submitted by the prover produces the correct trace.

Although polynomial constraints are written in PIL language, instructions were originally written in zkASM, but later expressed and stored in JSON format. Although not all validation involves Plookup, the following figure briefly illustrates the extensive role Plookup plays in zkProver.

Components of zkProver

zkProver consists of the following four components.

  • Actuator or main fine-state machine actuator

  • STARK recursive component

  • CIRCOM Library

  • Zk-SNARK prover

In short, zkProver uses these four components to generate verifiable proofs. Therefore, the constraints that each proposed batch must satisfy are polynomial constraints or polynomial identities. All valid batches must satisfy specific polynomial constraints.

Actuator

The actuator or main fine-state machine actuator handles the execution of zkEVM. This is where the new zero-knowledge assembly language (or zkASM) specially developed by the Polygon zkEVM team is used to interpret the EVM bytecode.

It serves as input; transactions, old and new states, Sequencer's ChainID, etc. The actuator also needs it.

  1. PIL, which is a list of polynomials, a list of registers, and

  2. ROM, which stores and executes a list of instructions

The actuator sets the polynomial constraints that must be satisfied for each batch of valid transactions. Another language specifically developed by the team is called Polynomial Identity Language (or PIL), which is used to encode all polynomial constraints.

Actuactor executes all instructions on top of PIL hardware and generates submitted polynomials; this is the fine-state machine cycle, or a list of all states. It also generates some common data that forms part of the input to the zk-SNARK validator.

STARK Recursion component

Once the main finite-state machine actuator converts the transaction and related data into a committed polynomial, the STARK recursion component takes the following input:

  1. Commitment polynomial,

  2. Constant polynomial,

  3. A script is a list of instructions.

To facilitate fast zk-STARK proofs, the STARK recursion component uses the Fast Reed-Solomon Interactive Oracle Proximity Proof (RS-IOPP) ( also known as FRI) for each zk proof.

This component is called STARK recursion because:

It actually produces several zk-STARK proofs.

→ Organize them into bundles of zk-STARK proofs,

→ and generate further zk-STARK proofs for each bundle,

The zk-STARK proof of this bundle has also been organized and proven, using only one zk-STARK proof.

In this way, hundreds of zk-STARK proofs can be expressed and proven with just one zk-STARK proof.

CIRCOM

The single zk-STARK generated by the STARK recursion component proves to be the input of the CIRCOM component.

The original CIRCOM paper described it as a circuit programming language that defines arithmetic circuits and a compiler that generates both;

  1. A file containing a set of Rank-1 constraint system (or R1CS) constraints associated with arithmetic circuits, and

  2. A program (written in C++ or WebAssembly) that calculates the valid allocation of all lines of an arithmetic circuit, called a witness.

As implemented in zkProver, CIRCOM takes the zk-STARK proof as input to perform two tasks.

  • Define and create an arithmetic circuit corresponding to the input zk-STARK proof. The arithmetic circuit is represented by its equivalent R1CS.

  • Generate witness, which is actually a set of effective input, intermediate, and output values for the circuit line satisfying the above R1CS.

ZK-SNARK Prover

The final component of zkProver is zk-SNARK Prover, especially Rapid SNARK.

Rapid SNARK is a zk-SNARK proof generator, written in C++ and Intel Assembly, which can generate proofs of CIRCOM output very quickly. For zkProver, Rapid SNARK is used as input

  1. CIRCOM's witness

  2. STARK validator data, which specifies how Rapid SNARK must process data and then generate zk-SNARK proofs.

Last updated