Zero-Knowledge Proof

Relic Protocol employs customized zk-SNARKs to develop a system that can prove the integrity of a block on-chain without relying on block data.

Introduction

Zero-Knowledge Proof (ZKP) is a system that allows a Prover to claim a statement as true and enables a Verifier to verify it without having access to all the information. Essentially, in a ZKP system, the Prover can prove a particular fact without revealing sensitive personal information or a large amount of data to the Verifier. zk-SNARK and zk-STARKs are prominent implementations of ZKP.

Why use custom zk-SNARKs?

The appeal of using a zk-rollup was the massive reduction in calldata costs, but the transaction costs may still be high due to proving costs. After all, we need to transmit 7GB of data and perform roughly 30 million Keccak hashes, which are notoriously expensive to do in arithmetic circuits. Implementing our own SNARK circuits has a few advantages:

  1. No virtual machine overhead: zk-rollups process transactions in some virtual machine, e.g. StarkNet has the Cairo VM, while zkSync 2.0, Polygon Hermez, Scroll, and others have some type of “zk-EVM”. Although these VMs are more convenient to use than circuits, it should always be possible to squeeze out more performance at the circuit level.
  2. Optimized proof system: with such a specific application in mind, we can select and optimize a proving system for our use case.
  3. No cross-domain messaging: if the SNARK computation is directly verified on L1, there is no need to handle L2 to L1 messaging, simplifying the logic.
  4. Production-ready: while zk-rollups and zk-VMs are still being battle-tested and optimized, the underlying SNARK/STARK technologies are much easier to ship today.

Circuit Architecture

To produce validated Merkle roots, our circuits must verify two properties:

  1. The input block headers are correctly linked to one another.
  2. The hashes of the input block headers form the output Merkle root.

Because Keccak hashes are expensive, we won’t be able to hash an entire chunk of block hashes in a single circuit. Thankfully, our computation has a nice recursive structure which lets us divide and conquer, using two circuit designs:

Inner Circuit M, some small power of 2, block headers as hidden input, verifies they are properly linked, and outputs

  1. merkleRoot: the Merkle Root of the M block hashes
  2. parentHash: the parent block hash from the first block header
  3. lastHash: the last input block’s hash

Recursive Circuit two proofs (and their outputs) as input, recursively verifies them, checks they are linked (the lastHashof the first proof equals the parentHashof the second proof), and outputs:

  1. merkleRoot: the Merkle root of the two inputmerkleRoot values
  2. parentHash: the parentHash from the first proof
  3. lastHash: the lastHashfrom the second proof

Choosing a Proof System

With this circuit architecture in mind, we need a proof system which can efficiently handle Keccak hashes and recursive verification. As always, it would be nice to have no trusted setup (or at least a universal trusted setup), so we don’t have any Relic-specific toxic waste. And of course, it must be efficient to verify the proofs in the EVM, so it should either use very small fields or Ethereum’s natively supported BN-254 curve (sometimes called BN256).

There are a few options that meet these criteria, but two stood out:

  1. Polygon’s Plonky2: a relatively new proof system with incredibly fast recursive proof times. However, this efficiency comes with the cost of large proof sizes, which means high calldata costs. For applications that need very high throughput (such as a zk-rollup), this is a worthwhile tradeoff. However, our use case can trade longer proof times for cheaper verification.
  2. Aztec’s UltraPLONK: a more battle-tested proof system which has been used in production for zkSync, Zcash, and others. Conveniently, many of the custom gates we need (for Keccak, SHA, etc) are already implemented by Matter Labs for use in zkSync 2.0. Although the proving times are higher than Plonky2, PLONK has very small proof sizes, so verification costs are currently much lower.

Due to the cheaper verification costs and existing tooling, UltraPLONK fits our needs better. But, high proving times could pose challenges, since we must be fast enough to keep up with the stream of Ethereum blocks. Thankfully, after a few optimizations, proving times are low enough that a single low-end consumer GPU can easily keep up with the chain.

Implementation and Optimizations

Our proof system is based on the Matter Labs fork of bellman, but with a few changes:

  1. Added GPU proving support based on Filecoin’s work
  2. Optimized a few inner functions based on profiling results

Additionally, since proving times are roughly proportional to the number of gates, we used a few tricks to reduce the size of our circuits:

  1. Used hash function gadgets based on lookup tables, greatly reducing the number of gates needed to perform hashes.
  2. Used SHA-256 instead of Keccak to build our Merkle trees. Keccak must be used to compute the block hashes, but we can use any EVM-efficient hash function for our Merkle Trees. SHA-256 offers a nice balance between circuit size and EVM gas cost, due to the Ethereum precompile.
  3. Modified the recursive aggregation logic to use a fixed inner-proof verification key (VK). In our case, the inner proofs come from the same circuit, so we can hard-code the verification key to reduce the number of gates needed to aggregate proofs. This comes at the cost of having a different VK for each proof size (e.g. a proof containing 8K blocks has a different VK than a proof containing 16K blocks), but we only need to support on-chain verification of a few of proof sizes.

If you’re curious, our circuit code is public on github. You may also want to check out our recursive PLONK verifier written in yul assembly, which reduces gas costs for verification on-chain.

Future Work

Our usage of SNARKs so far has enabled very cheap verification of historical block hashes in the EVM. As a result, the gas costs to access historical state are dominated by the Merkle-Patricia Trie proofs. We are experimenting with aggregating many MPT proofs into a single SNARK, which has the potential to bring the proving cost per state fact down dramatically.

Table of Contents