Fantastic Zero-Knowledge Proofs

And Where to Find Them (Ethereum Edition)

Outsider Analytics
Blockchain Biz
20 min readOct 4, 2022

--

I’m not a graphic designer, ok?

Zero-knowledge proofs are the future of Ethereum, but they are complicated, and collecting their data is difficult. In this post, I aim to:

  • Give some zkp background and discuss how they help Ethereum
  • Demystify how to collect on and off-chain data for L1-based zkps
  • Share the data that I collected
  • Visualize a few implications of the data

A couple of quick notes before we jump in:

If you want to get in touch:

Background (please skip ahead if this is old news)

Why Zero-Knowledge Proofs?

For all of the decentralization benefits of Ethereum, it fundamentally suffers from two significant limitations: Scalability and Privacy. The transactions per second of Ethereum L1 is currently 13.1 TPS, and an astute data scientist can see almost all transactions within the network. As Ethereum works to cross the chasm towards mainstream adoption, zero-knowledge proofs have emerged as a solution for both issues.

If you are starting from scratch and are lost already, I recommend this video https://www.youtube.com/watch?v=BT88s7_VtC8&t=4s as my favorite zkp jumping-off point. If you really want to go down the rabbit hole, I put this together as a part of the grant: https://github.com/outsider-analytics/ZK-Circuit-Performance-and-Security-Data/blob/main/ZK_Learning_Resources.md.

Scalability: ZK proofs shrink the size of the data on-chain by batching transactions off-chain and only posting a zk validity proof for correct txs (validiums) on Ethereum main chain (L1). Validiums can become zk-rollups and increase their security by posting the data for off-chain state reconstruction in L1 call data and soon data blobs (hello EIP 4844). Since the proof that the L2 transactions are valid is generated off-chain and verified on-chain as correct via a smart contract, the size of the data on L1 is dramatically reduced. Please see https://ethereum.org/en/developers/docs/scaling/zk-rollups/ and https://ethereum.org/en/developers/docs/scaling/validium/ for great explanations for scaling using zk proofs.

Privacy: There is a reason zk stands for “zero knowledge.” A zk proof can assert something is true while revealing zero knowledge about the inputs. This ability can allow users to publicly expose a proof of knowledge or ownership without exposing their identity. The explosion of L2s has also enabled “privacy by default” blockchains as rollups which can still inherit the full security of Ethereum.

Not all zkps are the same. There are many different types, and they all make tradeoffs! So how are they practically being implemented?

Enough Waldo, How are ZKPs Used in Practice?

Poor Waldo

Let’s put the basics of Waldo playing Sudoku aside and explore the practical use of ZKPs on-chain. Storage and computation on L1 Ethereum are EXPENSIVE. ZKPs also require a relatively large amount of computing power to generate their validity proofs. However, verifying proofs requires much less computation than generating them (called an NP problem). Because of this, the natural flow of zkps is:

After generating a zkp off-chain using the circuit, the user will call a “Verify” function of a smart contract and provide the proof as an input. Often this practically works by a separate smart contract requiring the verifier contract to return a “1” (true) before taking an action.

Let’s take a simplified Mixer as a privacy example. Our user Jon starts by

  1. Sending 1 Eth and contributing a hash of a “secret” string as a leaf of a Merkle Tree stored in a smart contract.
  2. Jon later wants his Ether sent to a different un-doxed wallet without connecting the two.
  3. He provides the pre-hash of his secret and the path to his particular leaf as an input to the zero-knowledge circuit off-chain (potentially running in his browser). The pre-hash is the text string before being hashed.
  4. The circuit then generates a zkp which proves Jon knows the “preimage” of his secret and which leaf is his.
  5. Jon then makes the proof an input to a withdraw function of the on-chain smart contract holding his funds. This tx comes from his un-doxed wallet.
  6. The “funds holding” smart contract sends Jon’s proof to a verifier smart contract which returns 0 for false or 1 for true.
  7. If the “funds holding” smart contract receives a true back, it sends 1 Eth from the pool to Jon’s new wallet.
  8. Because only the proof is public and reveals zero knowledge about the inputs, Jon’s new wallet will receive “clean” Eth. (Note there are plenty of ways beyond the inputs that can still dox Jon)

Now for a simplified zk-rollup for a scaling example. Jon starts “zkRollup”.

  1. zkRollup consists of a separate blockchain “L2” whose state’s source of truth is a Merkle root on Layer 1 Ethereum.
  2. Every couple blocks of zkRollup L2 has its transactions batched into an input for a zk-circuit off-chain.
  3. The off-chain zk circuit generates a proof that all tx on zkRollup L2 were valid.
  4. The zkRollup operator EOA address on Ethereum provides the proof computed off-chain, the new state Merkle root, and the state data to an on-chain smart contract.
  5. This smart contract verifies that the proof returns true, at which point it updates the state root and posts the info needed to recreate the state in call data.
  6. In the face of censored L2 transactions, users can directly provide a proof to the L1 rollup contract and have their funds released.
  7. If generating this proof sounds difficult to actually do, you are currently right. l2beat.com is working on this issue, and the topic will likely be my next focus.

What is a ZK Circuit?

In short, a zk circuit is a piece of code that takes inputs and produces a validity proof without revealing the inputs. To make a zk circuit capable of generating zk proofs, you must get back to basics. While newer proving systems have the can around some of these issues, circuits can only be addition and subtraction functions called “constraints” or “gates.” This is similar to how modern CPUs consist of hundreds of millions of physical transistors. The amount of gates in a circuit increases with the complexity and number of inputs, with zk-rollups requiring over a million gates. The proof generated by the circuit will change with the inputs but can always be verified by the same “verifier” smart contract. This allows the “verifier” smart contract to remain the same on Ethereum for a given circuit. The user or zk-rollup operator can collect the new data, input it into the circuit, generate a proof, and prove it is correct with the on-chain verifier smart contract.

What is a Trusted Setup?

Zk SNARKs are a type of proving system which requires a “trusted setup”. Basically, SNARKs need a random string called a CRS (common reference string), which tells the prover and verifier where on the elliptic curve they are evaluating the proof. The input needed to create this CRS is called “toxic waste” and must be kept private, or attackers could create false positive proofs. In practice, the CRS is created in a ceremony with many participants using MPC. Every participant’s input is toxic waste; unless an attacker gets it all, the CRS is safe. STARKs rely on hashing rather than elliptic curves and thus do not need a trusted setup. This also makes STARKs resistant to quantum computing, unlike SNARKs.

How to Collect the Data

Choosing the Right Data

What data to collect on zk proving systems is a nuanced question. While proofs themselves are essential, the important characteristics of the proof come from the circuit. For instance, there have been over 8k calls to verify proofs for zkSync (0xf7bd436a05678b647d74a88ffcf4445efc43bdfc), but these proofs come from the same off-chain circuit.

The issue with gathering data on circuits is that they are off-chain and often not public. However, what is public are the smart contracts used to verify the proofs on-chain. Each verifier must practically be unique to the circuit generating the proof. This means that the best way to identify off-chain circuits on-chain is through their verifying smart contracts.

Proving systems like PLONK have introduced a concept called “recursion”, which allows for a few excellent functionalities. The below 2 attributes challenge the idea of 1 verifier per circuit, but those circuits are linked in practice

  • Proof chaining allows the output of one proof to be an input into a different circuit.
  • Parallelized proof generation allows many different machines to work together to generate the proof.

To take categorization up a level, circuits & circuit systems will be identified with the project behind them whenever possible. L2s often retire verifiers by directing proofs to a new verifier, usually leaving projects with only one active verifier at a time.

How we collected the data

Tools Used: There are several excellent and free sources for on-chain data, such as dune analytics, but they were not powerful enough for this project. Google Big Query’s public crypto_ethereum db is a true treasure and was used as the main source of data. This database includes three tables that I used to SQL query through on-chain Ethereum data: Transactions, Traces, and Contracts. While I am confident these three tables are accurate, I have reason to believe some other tables in the db have issues. Please see https://github.com/outsider-analytics/ZK-Circuit-Performance-and-Security-Data/tree/main/queries for all queries used.

Searching with FF Constants: The first way I queried through the data was to check deployed contract bytecode for the finite field constant “21888242871839275222246405745257275088548364400416034343698204186575808495617” (from the BN128 alternate curve native to Ethereum). In contract bytecode, constants are converted to Hex, which allows simple “IN” SQL queries to find inclusion. This query found about 600 contracts that had the finite field constant in them; a good start. From there, I checked etherscan.io to see which contracts were public and what they were doing. This was a good jumping-off point, but it included a bunch of contracts that were either proxies or not the actual ZKP verifiers.

Searching with Method IDs: After observing the flows of traces and transactions, a pattern emerged for the flow of zk proof verifications on-chain. This flow is detailed below in “verifiers”, but the best way to capture which contracts are verifying proofs is through the method ids of the function calls. Method ids are created by taking the first 4 bytes of the keccak256 hash of the function signature being called.

There is a tremendous public database of method ids here: https://www.4byte.directory/, but it isn’t 100% comprehensive. When manually tracing the function call to the method id follow these steps:

  1. Take the function from the contract: function verifyProof(bytes memory proof, uint256[] memory pubSignals) from https://etherscan.io/address/0xd0abdb2175ef925a3f3780b5489f319db7dae42c#code line 133
  2. Trim out all of the names and spaces: verifyProof(bytes,uint256[])
  3. Hash it with keccak256 using https://emn178.github.io/online-tools/keccak_256.html : 1e8e1e13cf83afc8c835e4b895a9262cbaf15686a6b26043c3e6d266b9269ccd
  4. Take the first 4 Bytes (8 characters) with a 0x id: 0x1e8e1e13

The first 10 characters in the data input section in transactions or traces is the method id. When using SQL queries with BigQuery, I often used “WHERE LEFT(input,10) = ‘Method ID’ to search through transactions and traces for function calls of that method.

Transactions and Traces: Through observation, it became clear that verification contracts were often not called directly by the transaction but were instead being captured as traces. A trace is created for every smart contract function called after the initial transaction call. With this in mind, I used a simple method id query through traces and transactions to get a table of all proof verifications on-chain. Please see https://docs.google.com/spreadsheets/d/1Boo9zmsRDc1nDLUQIp8JyInPddF5F2aXM_1zkKGAG1g/edit#gid=703394848 for the Method Ids used.

Etherscan: Everyone knows Etherscan.io, and as expected, the public posting of contracts was super helpful. Unexpectedly, however, there is a new feature that was also very helpful called “transaction decoder”. It takes the often complicated transaction flow (looking at you Starkware!) and shows which contracts get called with which methods and inputs. For reference, check out the execution trace section at the bottom of this dydx transaction.
L2Beat.com was also instrumental in helping link these contracts with a project. Between L2Beat, project documentation, and helpful discord discussions from the different projects, I was able to identify many of the contracts on main-chain Ethereum.

A Note On Verifiers

The verification flow on-chain depends significantly on the project’s proving system. For Groth16 and standard PLONK, the verification is usually a simple function call to a single verifier contract with the proof as an input. The verifying contract often returns 0x000…001 (indicating a valid proof), and the contract can proceed. For TurboPLONK and STARK-based contracts, the verification flow can get much more complicated and include many contracts. In addition, they often include calls out of the verifying contract for items like vk keys. I grouped all the contracts into one verification system for these more complex projects. For an example, see the dYdX proving flow (see the link in the description to make this bigger):

https://www.figma.com/file/wuaQuAeDDknt8cHkXnnWuN/dYdX-Verify-Proof-and-Register-Transaction-Flow?node-id=3%3A699

I believe that the actual dYdX STARK proof is being verified with “VerifyFRI(Proof)”, but the whole system is a bit complex to reduce too far.

Active Projects

After looking at the different contract’s first and last verification, it became clear that some were more active than others. So I looked at these contracts and decided to put in a project tab that ties the most recent verifier to its project. Using the Public Verifier’s tab, feel free to trace back when projects retired and upgraded their verifiers by looking at the start and stop dates.

Layer 2 Transactions

To understand L2 performance I collected a bit of L2 chain data. I chose 7 days to collect the number of txs (Oct 20–26th 2022). Most of the tx counts required manual counting from a block explorer, but I also used API calls for zkSync due to size. Finally, I only included active projects with public L2 tx data.

L2 Gas Costs

I used the SQL query here to collect the gas costs needed on L1 for different L2s. The gas costs included more than just the cost of verifying the ZKP to gather a more accurate cost of providing data availability. The general collection method was to find the controlling externally owned account and use the method ids to identify what functions they were using.

A note on Starkware projects:

A common prover/verifier between the StarkEx validiums and StarkNet complicates the gas analysis. For the shared gas costs (verifyMerkle, verifyFRI, verifyProofAndRegister, and verifyContinuousMemoryPage), I made the unscientific approach of attributing 25% of the cost to StarkNet and 25% to IMX based on project documentation. Unfortunately, besides IMX I could not find the number of transactions occurring on the other Starkex Validiums, so they were omitted from the analysis.

This equal weight method may be severely underselling the costs of the data verification for StarkNet from some conflicting documentation. Please take Starkware projects with a grain of salt and skepticism.

The Data

Grouping the Data: After the Method Id search, I grouped the transactions by verification contract and filtered out the proxies and false positives with color coding. The data provided was last run on 10/2/22 at 16:00 UTC. This SQL query here resulted in the following data points:

  1. Verification Contract
  2. First Transaction Date
  3. Last Transaction Date
  4. Average Gas Per TX
  5. Method ID
  6. Contract Deployed Time Stamp
  7. Contract Deployed By Address
  8. Contract Creation Input
  9. Contract Runtime Bytecode
  10. Method Type: Internal (Trace) or External (Transaction)
  11. Number of Contract Calls

Off-Chain Data: Unfortunately, I could not collect all data points on-chain. I collected the following data on 68 public verifying contracts:

  1. Proving System
  2. Contract Name
  3. Contract Author
  4. Company Deployed By (different from Author in the case of forks)
  5. Boolean if the Contract is Public
  6. Contract ABI

I collected the project-level data below through off-chain research and placed it in the Active Project sheet. Active project qualification is subjective and comes down to the last transaction and documentation upkeep.

  1. Circuit Development Language (i.e. RUST)
  2. Circuit Library (i.e. Libsnark)
  3. Hash Types Used
  4. Trusted Setup Details

Wanchain might not be a zk project as I found no supporting docs, however, everything on chain signaled zk to me. I am happy to be corrected either way!

Master Sheet: The results of the SQL query combined with off-chain data. Please see the different color descriptions:

  • Green is a contract confirmed as a verifier and whose code is public.
  • Yellow is a contract that seems like a verifier from its activity and bytecode, but whose contract is not public.
  • Orange is a proxy contract with the corresponding contract address in the last column.
  • Blue is one dummy verifier contract used by zkSync to test if I was awake (and maybe their protocol).

Method IDs: This sheet is a table of Method Ids confirmed as zkp verifiers. As a reminder, method IDs are the first 4 bytes of the keccak256 hash of the function signature.

L2 Txs: See above for collection methods. I collected this data from various L2s from September 20–26th, 2022.

L2 Gas Cost Analysis :
This sheet combines the L2 txs from September 20–26th, 2022, with gas collection from this SQL query. Unfortunately, I couldn’t find public transaction history for all projects, notably Aztec and a few StarkExs.

A Bit of Analysis

While the point of collecting and publishing this data was to give enough data and methodology for others to do analysis, I can’t help but dip my toe in a bit.

How Many are There? This chart is the total verifier contracts deployed and the number of verifications on Ethereum main-chain starting with the first in Nov 2018. These are only for publicly verified contracts. As of Oct 2nd, 2022, 68 confirmed verifiers had verified 627,807 proofs.
So What? Knowing how many contracts and verifications deployed on main-chain is nice. There are 41 non-public contracts that I believe are also verifiers, but that I can’t confirm
What Next? Doing this same analysis on the L2s would be interesting! Breaking them down by privacy solutions vs. scaling solutions might also be intriguing.

What About the Proving Systems? Pie Chart: A breakdown of proving system types for all public verifiers. Line Chart: the number of verifications per month by proving system type. Unknowns are probably PLONK or TurboPLONK, but they were so early that I can’t be sure!
What Does it Say? Groth16 is still the king for the number of verifiers deployed and the number of completed verifications. It is interesting to see STARKs having over double the verifications of PLONKs, especially since STARKs are deployed by only 1 company. It’s clear when StarkEx 3.0 hit main-net as the number of STARK verifications took off from PLONKs.
What Does the Trend Say? The proving systems have bifurcated into scaling L2s and privacy solutions. While privacy systems still use Groth16, newer L2s increasingly use alternative solutions for benefits like recursion and custom circuits. With Scroll using Halo-2, it will be interesting to see what the next generation of projects choose.

How are Circuits and Verifiers Being Written? These pie charts are a breakdown of the languages and packages used to write different circuits. Major active projects include Element Finance, zkSync, Aztec Connect, dYdX, ZKSpace, Aztec, StarkEx/Net, Loopring, Polygon Hermez (and separate withdrawal), and Tornado.Cash
Hey Aspiring Devs… If you want to break into zk development, you should know in what languages the zk circuits/verifiers are being written. The full chart is here.
What Next: Circom has yet to penetrate the market outside of Groth16. The only deployed Circom PLONK is in private airdrops. For the ZKEVMs, Starkware is positioning C++/Cairo while Scroll and zkSync are using Rust. It will be interesting to see if Polygon’s incoming ZKEVM drives Circom forward or if they keep it a Groth16 and privacy-focused language.

Hashes? Don’t we just use SHA3 & Keccack256? Certain Hashing is expensive in ZK Circuits, so it requires a whole new set of challenges. Listen to this excellent talk from EF researcher Dmitry Khovratovich. This chart categorizes hashes used for the same major projects as above.
Still a Little Boring… Listen to Dmitry; sometimes hashes get broken! There is a lot of experimentation in zk hashing so if you have funds in a mixer, keep this in mind!

Trusted What? Trusted setups are needed with SNARKs, and are an essential security consideration. Groth16 needs a new trusted setup for every circuit and requires a 2 step process. The first step in the process is often taken from the “Perpetual Powers of Tau” on Ethereum, currently sitting at 71 contributors. The second step must be project specific. For Plonk, there is just one trusted setup needed that everyone can use, and it is one step. STARKs, on the other hand, do not need a trusted setup at all.
So What? If all of the participants in a trusted setup collude or are compromised, the project itself is compromised. There are more TS attack vectors than the number of participants, but there is a clear difference between Hermez’s six-person ceremony and Tornado.Cash’s 1114-person ceremony. It is also interesting that the security of zkSync, ZKSpace, and Aztec/Aztec Connect all depend on the same universal PLONK ceremony. STARKs are fully transparent and don’t require a trusted setup. However, they pay for this with costlier proof generation, gas costs, and complexity.
I Think You Have Trust Issues… I have also always felt that this fear was overblown due to Cryptographers’ inherent and necessary paranoia. However, at ZK Summit 8, Alex from zkSync (currently using a TS) mused that institutions will not be ok with trusted setups. As technology progresses and the tradeoffs from eliminating the TS get reduced, the question will become interesting. With projects desperate for differentiation, eliminating TS will likely be a major talking point for anyone who does so (Scroll/Starkware).

Actual L2 Gas Costs for Sept 20–26, 2022 per L2 Tx

Whoa, what is this? This chart is an oversimplification of the gas cost per transaction from Sept. 20–26 per project. It is oversimplified because:

  1. dYdX tracks net state changes not transactions, inflating their costs per L2 tx
  2. The only validium with public L2 txs on the StarkEx prover is IMX which shares its verifier with Starknet. I assumed 25% cost going to Starknet (1 out of 4 projects), 25% to IMX, and the remainder of the gas costs for the other StarkEx projects. Please see the above “note on Starkware projects” for more.
  3. Transactions have different costs. Comparing simple token transfers to private defi is apples to oranges.
  4. Most of these gas costs depend on demand, as more txs per L2 lower the cost per tx. Make sure to look at all columns for context.
  5. This also means an L2 can lower gas prices by waiting longer to post more txs to L1.

What Can We Learn from This? With the caveats aside, the chart is still instructive. One takeaway is the 18x cost savings per L2 tx for a STARK validium (IMX) vs a STARK rollup (dYdX).

StarkNet’s place in this chart is interesting; significantly cheaper per L1 Tx than IMX. I would like to investigate this further to see if I missed something or if it is a function of lower L2 volume for StarkNet vs. IMX. StarkEx documentation claims that IMX should have lower cost because “Payment for on-chain data is not required. When updating the on-chain state, most gas is spent on the verification of the proof.” (source) This leads me to believe that Starknet deserves much more than 25% of the shared verifier costs.

How About the Future? The significant difference between zk-rollups and validiums is the nature of the L2 state on L1. By posting that state, users can force exit the zk-rollup in the case of L2 transaction censoring, even if the chain is frozen. However, that ability comes with increased gas costs hampering the scalability. Therefore, choosing zk-rollups vs. validiums for the asset security required is a looming question all future projects will need to answer.

Get Into the Data!

Now it’s your turn! This data is available on:

  1. Github
  2. Google Sheets: Please feel free to copy the whole thing :)
  3. BigQuery: See the queries used in the queries folder of Github
  4. Dune.com: Use the addresses in the active sheet and expose cool data for free!

Want to learn more about ZK? Check out my ZK Learning Resource!

Moving Forward

Improvements

There were a few metrics I, unfortunately, fell short of

  • A significant performance metric with ZK projects is off-chain proof generation. L2s need to generate a new proof every time they want to update their state on L1, which is a project constraint. I came into this project hoping to gather data on proof generation, but a combination of closed source and technical complexity pushed that beyond the scope.
  • Optimism and Arbitrum (optimistic rollups) likely have ZK contracts deployed (like Semaphore!) that would be nice to capture.
  • More hard data and metrics on the verifier flow and data availability per project would be instructive. This is complex but certainly doable!
  • The StarkEx vs. StarkNet shared prover has made metrics difficult for these projects. It would be nice to separate this data to learn what is actually happening in each project’s verification process.

Force Exit on L1 Soap Box

When I started this project, I had a basic “where’s waldo” knowledge of ZKPs. Starting essentially from scratch, the most striking deficiency I’ve seen in the zero-knowledge world is with zk-rollup escape hatches. Zk-rollups promise is to inherit the full security of Ethereum while significantly reducing the cost of transactions. Zk-rollups inherit that security by allowing users to transact directly with L1 contracts in case of L2 censorship or chain disruption. The flow is usually:

  1. User submits txn to the zk-rollup contract on L1
  2. If the rollup’s sequencers don’t include the tx within a specific time period (usually 7 days), the L2 is put into exodus mode.
  3. In exodus mode, anyone with funds in the L2 can submit a proof of ownership to the L1 rollup contract and receive their funds.

A few things are needed to make this flow a reality if a zk-rollup provider becomes evil or governments compel them to censure transactions.

  1. There must be enough time delay from an L1 rollup contract upgrade for the rollup to be put into exodus mode, all proofs to be generated, and users to submit force exit txs on L1.
  2. Non-Dev users must have a decentralized front-end solution to submit “force exit” transactions to the L1 rollup contract. Hosting this service on an L2’s centralized front end is not acceptable.
  3. All users must be able to generate the proof and submit the proof to the L1 rollup contract.

I do not believe that with the current infrastructure, users can adequately withdraw funds from an adversarial zk-rollup. All L2 sequencers are currently centralized, a severe attack vector for governments. L2Beat has this on the road map, and I implore anyone who is a champion of a zk-rollup-based future to support their and others’ efforts.

Thank you!

I would like to recognize the following people and organizations for their help and support:

  1. The Ethereum Foundation PSE team: Thanks for the funding and the support! I have really appreciated being a part of a team again and definitely enjoyed the time I spent with you all!
  2. L2Beat.com: Your platform was instrumental in my understanding and data collection for this project. I appreciate your ethos and all the good your project is doing in Ethereum!
  3. The Daily Gwei Podcast/Discord: I haven’t found a more helpful or intelligent group to both ask questions and hang within all of Crypto! Anthony the Pod is truly an awesome resource to the whole community. The discord is a fantastic group, come join: https://discord.gg/whxq3W4q
  4. The Zero Knowledge Podcast (and summit!) IMO the source for learning cutting-edge zk tech.
  5. Justin Martin (@thefrozenfire): Your breadth of knowledge and insights are impressive. Thanks for getting me started and helping me whenever I got stuck!
  6. Mark Roddy (@mroddy5280): Thanks for thinking through the issues with me and being a great sounding board!

Get in Touch

If you have feedback or questions, please feel free to reach out via email, discord, or telegram. I am currently seeking out the next project and am open to collaborations or opportunities!

--

--

Outsider Analytics
Blockchain Biz

Data Scientist Working on Zero-Knowledge Proofs on Ethereum