On ZK gas costs and scaling solutions today, tomorrow and beyond

Introduction

As the design and implementation of RLN Relay (Vac - Privacy-preserving p2p economic spam protection in Waku v2) is maturing the topic of gas costs has come up. This is one of several trade-offs that are relevant to consider when designing cryptoeonomic systems.

As usage of Ethereum has exploded in recent years, gas costs have increased a lot. For Waku, being an independent messaging network, this has not directly impacted us so far. However, a lot of cryptoeconomic/incentive mechanisms rely on being able to interact with general-purpose smart contracts to achieve their goals.

This is only becoming increasingly relevant as we are moving towards more Zero knowledge usage and incentive design (see Vac <3 ZK). This is especially true since ZK constructs are quite novel and complex, and require significant gas usage. While a lot of groundwork has been done in the Ethereum world through things such as precompiled EC pairing instructions (EIPs/eip-197.md at master · ethereum/EIPs · GitHub) and ZK-optimized hash functions such as Poseidon (https://www.poseidon-hash.info/ and Gas and circuit constraint benchmarks of binary and quinary incremental Merkle trees using the Poseidon hash function - zk-s[nt]arks - Ethereum Research), there’s just a lot more going on in a ZK proof compared to, say, an ERC20 transacation.

One of the benefits of ZK and public blockchains is that you can verify a proof once in a smart contract executed in, say, the EVM. That way multiple people can trust this. However, this is not always necessary, especially in a p2p network such as Waku. For example, in the case of RLN Relay the verification could happen largely in direct interactions between peers as messages are being relayed. Whether this makes sense or not depends many things, but it should give you some hint of the design space we are working with here.

To reason about this trade-off between gas costs and other factors (compute, storage, security) intelligently we have to know, roughly (a) what the gas costs are (b) how we expect it to be used (c) what scaling solutions give us.

This post will outline some common operations and give a rough overview of what scaling solutions gives us. It is an overview and in no way complete. It is also focusing on what exists right now, and not future possible scaling solutions. It is also aimed at people who might be new to Ethereum and scaling solutions that are being worked on and considered. If you have been in the space for a few years, there probably won’t be much news here. If so, feel free to complement this post with correction or other comments.

The rationale for this is: (a) simplify design space for now, as there are already a lot of factors and unknowns coming with a new domain, novel mechanisms, etc (b) solutions we come up with should transfer well, if we assume a general purpose smart contract execution environment.

Gas on the back of the envelope

Each transaction in Ethereum costs gas, and this is in proportion to how costly it is to perform. The unit of this cost is “gas” (Gas and fees | ethereum.org). There is a gas price that is measured in Gwei, which is 10-9 ETH. The price of gas varies based on supply and demand. In recent years, because of increased demand, the gas price has increased a lot (https://ethgasstation.info/ and Ethereum Average Gas Price). A big change was recently made to how gas prices work in Ethereum, called EIP-1559 (All You Need to Know About EIP-1559 - ETH Gas Station) which aims at optimizing the fee market. As ETH has gone up in price, due to increased demand and supply becoming more limited, gas costs has increased in price.

First, here are some gas cost number so we know what orders of magnitude we are talking about:

  • ETH transfer: ~21k
  • ERC20 transfer: ~65k (x3)
  • Uniswap Token Swap: ~120k (x6)
  • Tornado Cash deposit: ~1000k (x50)

21k is the base fee and the minimum you’d pay. We can look at the other costs as rough multipliers of this to get a rough intuition for how costly an operation is. It is useful to be able to think of both the native gas cost, as well as what this means in, say, USD terms.

Assuming a gas price of 50 Gwei we have 50 * 0.000000001 * 21000 ~= 0.001 ETH. At ETH=4000 USD that’s $4 USD. 100k gas is $20 USD and 1m is $200 USD.

Gas price measured in Gwei varies a lot, from ~10 Gwei to ~200 Gwei. Ditto Ethereum price, from ~100 3y ago to ~4000. This means the cost of a normal ETH transfer can vary from less than a cent a few years ago, to $20 USD during spikes this year. EIP-1559 should make gas fees more stable, but it isn’t obvious that this is the case. As for ETH price, who knows? For simplicity, let’s assume the current state of things - ETH price and rough gas price - stays roughly the same. This is a big assumption but it’ll make it easier to get a basic intuition for the costs involved and how much scaling solutions help.

We see that even normal ETH and ERC20 transfers are quite expensive. Token swaps, common in DeFi, the same. Tornado Cash which is ZK based is very expensive except for very large transfers. This has lead to, especially for DeFi projects, to look to L2 solutions in order to make costs feasible for normal people.

The history of L2s and the search for scaling solutions, including L1s with different semantics, is long and complex and we won’t go into detail of this in this post. One relevant question to understand is: How much do these scaling solutions give us? With an acceptable level of security, do they save us x10 gas costs? x100? x1000? If we don’t understand this we can’t make informed decisions.

RLN Relay

One concrete example of a decision point here is the design of RLN Relay. Like many ZK constructs, there’s a merkle tree at the center of it. Should the root if this be on-chain or off-chain? See Performance and Security Analysis of Waku-RLN-Relay (vs other existing solutions) · Issue #91 · vacp2p/research · GitHub and Off-chain tree root - HackMD for more.

In the pubkey map case, you simply maintain an ordered map on chain. Then calculate merkle tree off chain and use that for proof and verification. In on-chain case, you just keep the root on chain and listen to events from the SC to be able to do proofs.

With merkle tree depth of 20 (1m entries) and some other rough assumptions we have:

Off chain:
Pubkey map deposit: ~40k (x2)
Pubkey map withdrawal: ~40k (x2)

On chain:
On-chain root deposit: ~400k (x20)
On-chain root withdraw: ~800k (x40)

Since deposits are much more common than withdrawals/slashing, this basically boils down to 40k vs 400k gas for a single deposit. For simplicity, we don’t consider other forms of optimizations at this stage (bulk insert, zk proof of root transition, special purpose scaling, etc).

Depending on the use case, this may or may not make sense. In USD terms on current Ethereum L1 this would be $8 USD vs $80USD. The former might work for a social network (comparables: WhatsApp, MetaFilter), whereas the later is quite expensive. In certain scenarios, the second might make sense - for example if it was applied to a specific pubsub channel with only very important and rare information that had a high value.

What dominates this order of magnitude difference? On chain root is similar to Tornado Cash costs which is dominated by doing a ZK verification in the smart contract, where cost is proportional to hash cost of Poseidon and depth of the Merkle tree. E.g. at ~20k per hash * 20 root level = 400k. Poseidon hash itself is optimized for zkSNARKs and running in smart contracts. For comparison, the gas cost of Keccak256 is 36, that’s more than 500x as expensive for a hash operation. As far as I’m aware, there’s no immediate better solution here, and Poseidon is already a lot better than non ZK friendly hash function. This is a hard cryptographic problem.

For a root on-chain, the root transition can be done by a ZKP proof. Basically proving that the root has changed to a new value. However, this leads to races when multiple people try to insert at the same time and complicates the design a bit. Ditto re batching, which requires some form of aggregator to batch things together.

What do you give up in the pubkey approach? There are some trade-offs, but the biggest one is probably storage costs. Because you are storing N pubkeys, this gets quite expensive compared to largely storing a root. Conveniently, Ethereum doesn’t charge for storage. This is an externality that full nodes are paying for, and there has been efforts to change this (state rent etc), however this doesn’t appear to be a priority. Instead, this has morphed into efforts such as “stateless clients” (On the State Rent and pivot to Stateless Ethereum | by Alexey Akhunov | Medium). What that will lead isn’t 100% clear yet, and we’ll see what this means in the Eth1.X/Eth2 roadmap.

What this looks like for other various scaling solutions probably depends, but as far as I can tell most projects punt on the problem of storage. While this probably makes sense for RLN Relay, things likely look different for other ZK approaches such as node reputation and settlement.

Let’s look at existing L2 scaling solutions and see what they give us in terms of order of magnitude.

L2s

Here we are interested in general-purpose Layer 2 solutions with full EVM support. We are not going to consider: (a) Other Layer 1 solutions (i.e. non Ethereum chains) in order to constrain the problem. We are also not going to (b) directly consider non general purpose solutions, such as ones only concerned with, say, payments. Many of the ZK/incentive solutions we are considering are quite novel and require a general-purpose platform. We are also not concerned with (c) things like data sharding because that is quite far out in Ethereum roadmap.

Layer 2 refers to the fact that they get security from Layer 1, and then use some mechanism for compacting multiple transactions into something that can be committed to layer 1. (One can argue about this distinction and say it is too coarse; for this post we’ll use this language since most of the Ethereum community is currently using it.)

A great overview of L2s, and rollups in particular, is An Incomplete Guide to Rollups. According to it, a rollup should allow for around 100-500x decrease in gas cost, depending on what the specific use case is. These are optimistic and theoretical numbers, though, so in practice it might be less.

There are two main families for L2s, optimistic and ZK-based. Optimistic solutions are optimistic because they commit some data that can later be challenged with fraud proofs. ZK based are based on proving transactions happened with ZK. Generally speaking, optimistic solutions are “easier” but a bit slower/less secure, whereas zk based ones - especially generally purpose - is a Hard Problem and thus likely more of a long term solution. There are also many hybrid solutions and other types of solutions that don’t fit neatly into this divide.

Empirical data

Let’s look empirically at existing L2 solutions.

Optimism claims to save 10-100x on fees on website. In Understanding Fees in Optimistic Ethereum: Part 1 | by Ethereum Optimism | Medium they are currently at x10 for Uniswap token swaps and x50 vs Synthesix Exchange. (It isn’t obvious to me what accounts for x5 difference here).

We can also look at https://l2fees.info/ to see how much cheaper scaling solutions are. We can filter by universal solutions based on https://l2beat.com/.

We then see for a more complex use case such as token swap we have x6 for Arbitrum, x15 for Optimism. Both of these are throttled while in beta, and we can expect this to increase. For ZK based ones, we see Loopring at x30, but it isn’t universal and specially targeted payments/exchange. For transfer tokens we around x50 difference for Polygon Hermez, Loopring and ZKSync. Polygon Hermez, Loopring and ZKSync are all working towards becoming universal. This is a very non-trivial task, and there are several approaches to a zk-based EVM.

There’s also another alternative, Polygon (https://polygon.technology/). This is the ugly duckling, and many would argue it isn’t a pure L2 but a side chain (somewhat controversial). Polygon is a collection of of scaling solutions that focuses on lower fee, lower security first. It has its own token, and it has recently acquired/merged Hermez, which is one of the more principally secure and sophisticated scaling solutions with their own zkEVM that is being developed.

How much does the current Polygon PoS/plasma bridge save? They just increased gas fees x30 to combat spam: Recommended Min Gas Price Setting - #8 by kasperk - Matic Mainnet - Forum - Matic Network (hinting at the centralization of some of these solutions, where things can change at the drop of a hat). It is harder to find gas costs here, but because it is a side chain with weaker security guarantees the difference is quite big. E.g. looking at a recent ERC20 transfers (post fee hike), the gas cost is subpennies: Polygon Transaction Hash (Txhash) Details | PolygonScan - basically 1000x. Assuming equivalent of $0.01 transaction fee (measured in MATIC) for ERC20 transfer, that’s ~1000x+ vs Ethereum L1.

Here are some links for current state of zkEVM effforts:
zkSync 2.0 have a zkEVM testnet: zkSync 2.0: Hello Ethereum!. The Alpha version of zkEVM testnet is… | by Matter Labs | Matter Labs | Medium
Hermez zkEVM: Introducing Hermez zkEVM
Loopring zkEVM is a WIP: Loopring Quarterly Update: 2021/Q3 | by Byron @ Loopring | Loopring Protocol | Oct, 2021 | Medium in collaboration with EF
AppliedZKP at EF is working on zkEVM specs here: GitHub - appliedzkp/zkevm-specs

(There are also hybrid zk/optimistic solutions that are focusing on payments, such as Zkopru Zkopru: Wat, Y & Wen. tl;dr Zkopru is almost ready, we… | by Privacy & Scaling Explorations | Privacy & Scaling Explorations | Medium. As well as AZTEC 2.0 which is doing a non-EVM but is a Turing complete ZK. As well some STARK based VM projects.)

As you can tell, there are quite a few solutions and a lot of things going on. Going back to the original question of how much these solution gives us in terms of order of magnitude, where are we at?

Conclusion

We want to understand what we can do today, tomorrow and beyond. We want to simplify this into rough orders of magnitude (x10/x100/x1000) so we can make reasonable trade-offs about designs we are making.

For ZK smart contracts - since that is what we are largely concerned with - many are similar in shape to “privacy preserving withdrawal” in Vitalik’s An Incomplete Guide to Rollups. There we see x77 as a theoretical/optimistic number for optimistic roleup and x570 for zk rollup.

Today: In terms of universal live solutions today we basically get x10 for Optimism and Arbitrum. Both are fine choices and has seen a lot of uptake in terms of community usage. This brings with it tooling, network effects, etc. In the future, this might get up to x50 or so, but we probably shouldn’t expect much more here. Conservatively, we can call this x10 and be pleasantly surprised to see more.

Tomorrow: With one of the zkEVM based approaches, many of which are in a testnet phase, assuming x50-500 seems reasonable. We can call this x100 and be pleasantly surprised to see more.

Beyond: There are many exciting ideas and hybrid solutions here that haven’t been talked about in detail for this post. These would ideally keep the same security, be universal and decentralized etc, and give us x1000 or more decrease in gas costs.

Implications

If we use the heuristic to use the most ready and reasonably secure technology today, basically we have a 3-4 step plan.

  1. Now: Goerli testnet for RLN testnet and others
  2. Today: Optimism/Arbitum for immediate deployment
  3. Tomorrow: Experiment with zkEVM based approaches to stay in the loop here
  4. Beyond: Be open to other approaches that might come along

Of course, this is just a rough idea and depending on how various projects deliver things may change. This is based on current best information.

What would this mean for gas costs of current solutions? Specifically, this would put RLN pubkey map deposit at ~1 USD and on-root mechanism (whether for RLN relay or something like reputation/settlement) at ~10 USD today. This seems feasible for a spam prevention mechanism if stake is, say, $10 and 10% of that goes to fees.

We are going to stick with RLN pubkey map approach for now, since (a) contract storage is not currently a concern (b) it has already been coded (c) given today’s tech it results in reasonable stake/fee. In the paper that we are writing, this trade-off will be elaborated on.

For other ZK incentive mechanism we’ll see. It might be that they are only feasible to deploy “tomorrow”, and/or for high value targets. E.g. if every node is expected to rate every other node, and this requires an on-chain merkle root, a fee of $10 (requiring a stake of ~$100 to be proportional) is probably too much for everyday users (comparable: Tornado Cash real world usage for denomination; DeFi moving to CeDiFi/L2 except whales). Though it might not be for long-term node operators (comparable: ETH2 staking requirements of 32ETH). However, we have a long way to go until then in terms of design, implementation and testing.

There are more factors to take into consideration here too such as tooling (wallet integration, library compatibility, events/state management, etc), different zk constructs (Plonk), more optimized way of doing things (different Poseidon rounds, zk proof for root transition), computational requirements on prover/verifier etc. These are things that can be investigated in more detail in targeted Github issues.

Closing thoughts

As we’ve seen, there are many different solutions here and there are many moving parts. It is likely we are moving towards a multichain world, where different scaling solutions will co-exists. We can see this with DeFi solutions like Aave and Sushi that are trying to deploy to as many chains/l2s as possible. How will these different worlds interact, and what does this mean for Waku as an open p2p network? This is an open question, but one worth thinking about. Do we have “subnets”, like islands with different group identities? Do we decide to go with one at the expense of all others? Do we find a way to compose them? Which one is most in-line with our principles (Status Principles), goals and what the ecosystem values the most?

1 Like