โšก

Zero knowledge Proofs for Rollups & Stateless Clients

Rollups (aka Layer-2 or L2) are blockchain technologies that help scale Layer-1s (e.g., Ethereum). Rollups allows faster transactions at a cheaper cost in a trustlessly verifiable manner, by periodically publishing the batch of transactions that were executed along with how those transactions modified the state of the rollup chain, such that any party that only trust the layer-1 (e.g., Ethereum) can fully verify that the rollup chain has correctly performed all transactions without trusting the rollup chain. The two broad approaches to Rollups are Optimistic Rollups and ZK-Rollups. They differ in the way they ensure validity of the rollup blocks. For Optimistic Rollups, validity is ensured by a fraud proof (asssume correct until proven wrong) and the synchrony assumption, while for ZK-Rollups, validity is ensured by zero-knowledge proofs (don't trust, just verify). While the Optimistic Rollups can be a cheaper solution, ZK-Rollups are the most secure and they eliminate a key design limitation of the Optimistic Rollup, which is at least 1 week withdrawal wait time. Some of the recent advancements in ZK technology have been able to optimize both time and cost of applying them to not only scale layer-1 (in rollups), but also achieve privacy and interoperability.

๐Ÿ’ก

Zero-knowledge proof (ZK Proofs) technologies enables one party to prove to another party that they know something without the prover having to convey the information itself in order to prove their knowledge.

In this short article, I will present a case for zero knowledge technology and why it is the right time for Harmony to invest heavily on it.

ZK for scalability

Harmony's scalability

Assuming Harmony block gas limit of 80 million and an Uniswap-like swap takes about 200,000 gas, we can only fit 400 transactions in a block. If the block time is 2s, our TPS per shard will be around 200. After the cross-shard smart contracts support, if we are able to keep the overheads to minimum and block time still around 2s, we can clock 800 TPS with 4 shards. Given that, not all transactions will be swaps, we can best approximate ~1K TPS using 4 shards. This scalability is sufficient to serve the needs of today (e.g., solana with so much traction is still doing only 750 TPS). However for the future needs, this is just on-par (if not below par) what some of the Ethereum rollups can achieve, and definitely low compared to other dominant layer1 solutions like solana, algorand, etc and tradfi use cases (Mastercard: 5K TPS, VISA: 24K).

Horizontal scaling vs rollups

One could argue that since Harmony supports sharding, which in theory allows infinite scalability by adding more and more shards to keep on serving the demand. However, there could be challenges when more shards are added and all of them are coordinated by beacon shard (shard 0). While sharding is a defecto scaling method, rollups on top of Harmony will be needed to serve the scalability demand of the future. Ethereum 2.0's 64 shards with approximate 50K TPS heavily promotes rollups as future scaling method for Ethereum in their rollup centric roadmap. A nice article to read: Why rollups + data shards are the only sustainable solution for high scalability.

Stateless clients

Currently, the single greatest bottleneck to scalability is state bloat. When this article was written, Harmony already nearing 350 million transactions and growing. The blockchain state for a full node is few hundred gigabytes and some terabytes for archival nodes. As Harmony blockchain gets utilized more and more, the blockchain bloat problem will be imminent. Further, after the resharding is implemented the validators will be shuffled around different shards and they will need to be able to quickly sync to the destination shard state.

Ethereum researcher have explored two techniques to solve state bloat problem: weak statelessness and state expiry:

  • State expiry: remove state that has not been recently accessed from the state (think: accessed in the last year), and require witnesses to revive expired state. This would reduce the state that everyone needs to store to a flat ~20-50 GB.
  • Weak statelessness: only require block proposers to store state, and allow all other nodes to verify blocks statelessly. Implementing this in practice requires a switch to Verkle trees to reduce witness sizes.

It is worthwhile for us to adopt some of these research to Harmony settings in Q1/Q2 2022, before it becomes too late to solve the problem (e.g., currently it is almost impossible for quickly spin-up a BSC node).

Read more about this in Stateless clients for Harmony

ZK for privacy

Blockchain by design is fully transparent and expose all transaction information. Anyone can track any financial activity on-chain like swapping, transacting, voting, lending, borrowing, and more. This may result in malicious activity, front-running of trades, and degrading the value of a decentralized financial system. Privacy technology is needed to shield users and their transactions from malicious attacks, yet can be fully validated.

Privacy = confidentiality (hiding payment amounts) + anonymity (hiding the identities of senders and recipients)

Some of the challenging in achieving privacy today are:

  • Privacy is expensive (at least in Ethereum)
    • e.g., SNARK recursion for zk-based privacy
    • requirements: bls curve pairing, plonk (without rollup)
  • Client-side privacy, web interactions
    • Client side zk-proofs via browser securely/privately
    • solved by aztec, we can just adopt it

Some of the techniques for achieving transaction privacy are:

  • Popular
    • Zero knowledge proofs
    • Mixers (we already have it)
  • Not so popular (not a scalable solution)

Read more details in Road to privacy on Harmony

ZK for interoperability

Harmony's trustless bridge deploys light clients to facilitate cross-chain transactions. For example, in the token transfer use case, when a user locks their token on ethereum, for minting the equivalent amount of tokens on the harmony side, it require ethereum light client deployed on harmony to validate the lock transaction that happened on ethereum. Similarly, when the user burns the minted token on harmony and tries to unlock the original tokens back to ethereum, it requires the harmony light client deployed on ethereum to validate the burn transaction that happened on harmony.

Harmonyโ€™s light client based on epoch blocks (described below) still requires downloading all the epoch blocks from genesis and verifying BLS aggregated signatures.

Epoch block based lightclient

  • Download the genesis block committee
  • Download all epoch blocks from genesis
  • Perform BLS verification of the epoch blocks aggregated signature using the committee public keys

This can be both time and space inefficient for ultra light weight clients that cannot afford to download all epoch blocks (1 block per day).

A simple ZK-based lightclient can be designed to make it fast and cheap, in which

  • Prover (validator/full nodes): generates a proof of committee transition from epoch i to j
    • Inputs: Epoch numbers i & j, committee (BLS public keys) of epoch i
    • Perform for each epoch block
      • Aggregate public keys from header according to bitmap
      • Check they are more than โ…” threshold
      • Check the epoch number is epoch number + 1
      • Encode the epoch into bits and hash to group element
      • Compute and check BLS signature
    • Proof for epoch i+1 = Proof for epoch i + above operations
    • Aggregate proof either iteratively or recursively
    • Output: Proof that includes the transition from epoch i committee to epoch j committee

Summary

Many layer-1 and layer-2 blockchains are heavily investing in Zero Knowledge Proofs as a solution for scalability, privacy, and interoperability (polygon investing 1 billion $). At Harmony our goal is to "bring the best research to product fast", we should spend Q1 2022 on clearly identifying the key infrastructure elements that will facilitate builders on Harmony to adopt the Zero Knowledge technologies.

Our progress:

  • We have many individuals at Harmony that are keen on bringing ZK infrastructure to Harmony
  • We are also working with ZK experts to fund them to bring some of the basic infrastructures, starting with ZK light client for interoperability.

Resources

Light Clients & Protocols

  • Plumo: An Ultralight Blockchain Client. Psi Vesely (University of California, San Diego), Michael Straka (cLabs), Philipp Jovanovic (University College London), Ariel Gabizon (AZTEC Protocol), Kobi Gurkan (cLabs), Georgios Konstantopoulos (Paradigm), Asa Oines (cLabs), Marek Olszewski (cLabs), Eran Tromer (Tel Aviv University)
  • SoK: Blockchain Light Clients. Panagiotis Chatzigiannis (George Mason University), Foteini Baldimtsi (George Mason University), Konstantinos Chalkias (Novi Financial / Facebook Research)
  • Three Attacks on Proof-of-Stake Ethereum. Caspar Schwarz-Schilling (Ethereum Foundation), Joachim Neu (Stanford University), Barnabe Monnot (Ethereum Foundation), Aditya Asgaonkar (Ethereum Foundation), Ertem Nusret Tas (Stanford University), David Tse (Stanford University), Caspar Schwarz-Schilling (Ethereum Foundation)
  • Jolteon and Ditto: Network-Adaptive Efficient Consensus with Asynchronous Fallback. Rati Gelashvili (Novi Research), Elefteris Kokoris-Kogias (Novi Research & IST Austria), Alberto Sonnino (Novi Research), Alexander Spiegelman (Novi Research), Zhuolun Xiang (UIUC), Eleftherios Kokoris Kogias (IST Austria & Novi Research)