From Off-Chain to On-Chain: Proof Systems
Socrates once said, "True knowledge exists in knowing that you know nothing.” In the context of cryptography, zero-knowledge proofs take this expression to another level by enabling utilities that knowledge brings without actually sharing that knowledge.
It all started back in 1985 at MIT when Shafi Goldwasser, Silvio Micali (who also founded Algorand) and Charles Rackoff published The Knowledge Complexity Of Interactive Proof Systems. Now over 30 years, the technology has evolved from being theoretically probable to being used across several use cases ranging from scaling Ethereum with rollups and to enabling private interactions across defi and socials.
ZKPs and Fraud proofs have been compared as competitors but there are interesting ways in which some teams are using them together. Even STARKs and SNARKs seemed to be separate, but a team has figured out a way to combine them together. These complementary proofs unlock more performance and capabilities. Let’s dive in.
INDEX
Off-chain execution, how?
Which proof do you like?
ZK proofs
SNARKs
STARKs
Fraud proofs
Validity vs Optimistic
New directions for proof systems
Making Zk proof generation more efficient
Proofs are used everywhere, not just rollups
RAAS and Rollup SDKs - The Aggregators
Conclusions
Off-chain execution, how?
Rollups are off-chain execution solutions that have their own sequencers that order the transactions, VMs, and proof systems that send proofs for batches of transactions. We have previously covered VMs and Sequencers. Let's take a look at different types of proof systems, their limitations, and applications.
There are two main types of rollups based on the proof systems since other parts are more or less the same.
Optimistic Rollups: These assume all transactions are valid and use fraud proofs to prove false transactions within 7 days.
Zero Knowledge (ZK) Rollups: Instantly prove if transactions are valid or not using validity proofs. Validity proofs and fraud proofs verify the legitimacy of transactions before they're recorded to the base chain's state.
Which proof do you like?
ZK proofs
ZK proofs use math and cryptography to guarantee the validity of transactions and are hence immediately settled once the proofs are posted. There’s no challenge period like optimistic rollups and fear of reverts. Some of the rollups that use SNARKS are good at compressing the proofs, so we get amortized costs. EVM compatibility for the ZKRUs is an issue currently, but fortunately, ZKEVMs by multiple teams like Polygon, Scroll, and Taiko have arrived early to the rescue.
There are two types of common proof types, ZK-SNARKS and ZK-STARKS
ZK-SNARKS
The acronym means Zero-Knowledge Succinct Non-Interactive Argument of Knowledge.
The ZK-SNARK proof should be small enough for quick verification, hide the inputs, and have no interaction between the prover and verifier. Usually, in proof systems, there is back-and-forth communication between the prover and verifier; this could lead to leakage of information, and SNARKS tries to avoid that. ZkSync, Loopring, Aztec, and Polygon Hermez use SNAKRs
ZK-STARKS
The acronym means Zero-Knowledge Scalable Transparent Argument of Knowledge.
ZK STARKs refer to implementations of non-interactive zero-knowledge proofs, that allow the prover to keep their data hidden from the verifier. Being non-interactive implies that the prover can transmit a solitary message to the verifier, eliminating the need for back-and-forth communication. This property enables blockchains to incorporate ZK proofs effectively, given their unidirectional nature. Once a block is created on the blockchain, it becomes unchangeable. StarkWare, Polygon Miden
SNARKs vs STARKs
Fraud proofs
Fraud proofs work by assuming that all the transactions are valid, but settling the transactions only after a challenge period (usually a week) during which anyone can challenge a transaction. This is done via a fraud-proof using data containing full transaction details on the chain. Optimistic rollups are compatible with EVM, which enables quick migration of code and smart contracts on the rollup and can take advantage of the programming languages, testing tools, etc. So it seems that in the short term, as Vitalik says, optimistic rollups do have some advantages due to EVM compatibility, but over the long term, ZKEVM could really add some real value due to privacy.
For the fraud-proof, the challenger provides,
Disputed state transition
The pre-state
Rollup state data
Their version of the post-state root.
The transaction is then replayed on a smart contract that acts like a virtual machine, and if the computation results in a state root that matches the challenger, the sequencer state transition is deemed invalid. The rollup state then reverts to the previous state. There are gas costs associated with running fraud proofs through EVM like smart contracts, we’ll cover some interesting solutions in the new directions section.
Validity vs Optimistic
ZK proofs and fraud proofs have multiple differences, including the amount of computation they need, the time it takes for them to validate a transaction, their security, and their difficulty of implementation.
It's important to note that while both zk-proof systems and fraud-proof systems serve different purposes, they can complement each other in certain contexts. For instance, zk proofs can be used to provide privacy and confidentiality within a fraud-proof framework, ensuring secure and trustworthy transactions on the blockchain.
New directions for proof systems
Although ZKPs and Fraud proofs have been compared as competitors, there are interesting ways in which some teams are using them together. This just shows how complimentary they are, and so much more performance could be unlocked by bringing them together.
Proof diversity and technical decentralization
Multi-client design for consensus execution nodes has proven to be resilient against attacks and bugs and, in general, leads to other benefits like better performance and new innovations due to different implementations. The recent issue with the ETH Geth client and the finality issue also point toward the same lesson.
When it comes to systems like rollups, similar considerations come into play. In fact, we already have various client implementations, such as Magi, for the OP stack. However, what caught my attention is that the OP team has taken it a step further with the Bedrock update. They have incorporated multiple redundant proof systems within OP rollups. This move adds an extra layer of security and reliability to the roll-up solution. For this, the OP stack has made standard APIs to swap different proof systems and also allow m out of n designs, where few proof systems would be needed for the operation of a bridge.
ZKPs with FHE - Fully Homomorphic Encryption enables computation over encrypted data without decrypting it. Zama is building a framework for the use of FHE across several verticals, such as FHE-based Optimistic rollups and ZK Rollups.
ZK-Fraud Proofs!!
An interesting innovation by RISC Zero, Layer N caught my eye. The fraud proofs for Arbitrum and Optimism are also called replay proofs because they have to be re-run according to the same instructions set, off-chain and on-chain. Optimism and Arbitrum have created a modified version of EVM called OVM and WASM called WAVM for running these fraud proofs and comparing the states. But the costs of rerunning these on ETH in solidity are high.
RISC Zero has creatively combined ZK and fraud proofs to get around these costs. They do this by running the fraud proofs in Layer N’s execution environment in RISC Zero’s zkvm. The initial state, the DA containing transactions, and the fraud proofs are given as input to the execution environment inside the ZKVM. It generates a ZK proof that either the state posted on L1 matches the one derived after applying transactions to the initial state. If the proofs are valid and the output state doesn’t match the one posted on L1, the state must be reverted. Although ZKFPs don’t completely solve this, they are able to drastically reduce withdrawal times due to their “one-shot” methodology. Rather than a lengthy back-and-forth bi-section protocol on ETH, ZKFPs allow for a single back-and-forth transaction to prove/disprove fraud.
MetisDAO & Tezos have also employed a similar approach to Hybrid rollups. Metis DAO’s hybrid rollups allow for transactions to selectively decide whether they want to be executed in an optimistic rollup or a zk rollup whereas the LayerN design still executes all transactions in an optimistic rollup. The only difference is instead of traditional bisection interactive fraud proofs, it utilizes ZK succinct fraud proofs.
As for Tezos Hybrid roll-up, validity proofs will be used when it is deemed best, otherwise, the whole system runs on fraud proofs. The team will continue balancing validity elements on the roll-up through kernel upgrades as validity tech matures.
Combination of STARKs and SNARKs?!
We are seeing a lot of combinations, Fraud proofs and ZKPs, but also within ZKPs themselves. It seems optimization sees no limits and some teams are able to push the boundaries of what’s possible.
Plonky2 is a SNARK that uses a technique called Plonk arithmetization to achieve incredibly fast proving times (only 170 milliseconds on an average laptop). However, its proof size can be quite large, ranging from 50 to 130 kilobytes.
Groth16 is a SNARK that uses a different technique called R1CS relying on elliptic curve pairings. Groth16 has one of the smallest proof sizes, at only around 300 bytes. However, its proving time is slower than Plonky2, taking anywhere from 50 to 100 times longer.
Horizen labs have found a way to use a technique called “wrapping” that converts one proof into another and have faster proof generation at smaller sizes. This is just a week old and we expect its impact on rollup designs.
Making Zk proof generation more efficient
TVL and throughput for ZK Proofs are yet to scale and gain adoption. ZK applications' proofs have become more complex, requiring larger arithmetic circuits and resulting in longer proving times. Packing thousands of transactions into a single proof involves significant computation, leading to extended proving times. ZKP production can require up to a 1,000,000-fold increase in computation compared to the underlying computation.
Approaches to accelerate ZK proofs on hardware include parallel processing, pipelining, overclocking (with caution), increasing memory bandwidth, implementing improved integer representations, and making memory access patterns predictable. Predictable memory access patterns facilitate the parallelization of computations, including Non-Interactive Zero-Knowledge Transforms (NTTs).
Long proving times cause delays in achieving transaction finality, as proofs need to be submitted to the base chain. For example, Starknet's expected proving times can take several hours. Projects like Supranational, Ingonyama, and DZK are working on improving proof generation efficiency.
Proofs are used everywhere, not just rollups
ZK-SNARK lite client for messaging: Succinct Labs has created a protocol called Telepathy that uses ZK-SNARKS to trustlessly communicate the ETH consensus into the execution layer of any other chain using lite clients. Then these block headers can be tracked on the source chain, and later all other information like state, accounts, etc can be derived. This is an alternative to the MPC bridges with much better security.
Source: Succinct Labs Privacy-preserving oracle with Chainlink: Chainlink DECO connects the off-chain world to the on-chain world. It uses ZK-SNARKs to verify the source of the API and generates proofs if necessary while keeping the data private. This ensures that the data comes from verified sources and remains private.
Bridging: ZK bridges solve cross-chain vulnerabilities while being cheaper and safer than traditional bridges. Electron Labs is building a ZK Light client bridge between Ethereum ↔ Near, Amherst Labs between IBC ←→ Ethereum L2.
Decentralized Storage: Filecoin leverages ZKPs executed on GPUs to provide evidence that nodes within its network accurately store data.
Private L1 Chains: Aleo, Mina, and Zcash, offer privacy features that enable transactors to conceal senders, receivers, or transaction amounts through the use of ZKPs.
Account Abstraction: ZKPs could enable a protocol where users use web2 logins to access dapps across multiple blockchains with a single identifier as mentioned here.
Multi-chain Data Sharing: ZKPs are also seen to enable trustless computation over on-chain data. Lagrange and Axiom enable the creation of generalized state proofs across all major blockchains. Herodotus and ETHStorage are a few more projects tackling this issue.
Blockchain Compression: Mina and Celo using ZKPs to compress blockchain data required to sync with the latest state proofs.
ZKPs with FHE - ZKPs alone may not be able to solve complex privacy settings. The use of FHE coupled with ZK can be used for use cases such as blind auctions, anonymous voting, trustless bridges, and confidential voting.
ZKML - There has been much speculation on how ZK-snarks could bring more utility to Machine Learning. The idea is to let smart contracts exercise judgment, enable one-person oracles, and generally get data on-chain in a scalable way. Making KYC and fraud checks efficiently private, and enabling autonomous management of DAOs are some potential use cases. Projects like ZKConduit are building the tools required to make this possible.
Fully-on-chain games - Using ZKPs, whole games could be hosted on rollups without putting any load on layer 1. This solves network congestion and reduces transaction costs. Games could also allow the concealment of information to create fair play games. Dark Forest, a fully-on-chain RTS game built on Ethereum & Gnosis, and MatchBoxDAO is an ecosystem building fully-on-chain games.
Deploy models for inference as Python micro-rollups. Let users verify that it’s truly GPT-2 and not GPT or some other flavor.
RAAS and Rollup SDKs - Aggregators
Rollup-as-a-service (RaaS) — a type of service that helps users to easily create and manage rollups based on their specific needs, call them L2s or L3s. The traction gained by Arbitrum and Optimism, along with the anticipated launches of zkSync, Starknet, and others, has accelerated the rate at which new execution layers are being built. Well, over $2b in venture funding has gone into this category since 2018. With dozens of projects now building in the space, it has gotten challenging to follow all of them. This is exacerbated by the recent trend towards rollup SDKs/rollup as a service providers. The goal of this market map is to give a thorough overview of the execution landscape as it sits today.
Frameworks
Frameworks refer to software that can be reused to build your own rollup.
Stackr allows for modularity specific to use cases, also known as mirco-rollups. from app-specificity to logic-specificity, where individual functions within a decentralized app are developed, optimized, and maintained as independent state machines.
Rollkit a similar framework, eliminates the need to bootstrap a validator set, manage consensus or other trade-offs when deploying a new L1. Rollkits are also deployed on Celestia’s DA layer and transactions are executed off-chain within their own computational resources so as to not end up sharing those resources with other applications.
Slush aims to make it easy to spin up L3s with ZK-provable virtual machines. These could be centralized or decentralized
More such frameworks include OP Stack (Bedrock) a work-in-progress modular stack that will make it easier to spin up L2s on superchains Orbit & Sovereign Labs
Services: Services assist with the deployment and actual running of the rollup.
Dymension’s roll-apps are based on fraud proof. Similar to Celestia’s Rollkit, there is no need to bootstrap a validator set as DA is outsourced to other DA providers, and the consensus is outsourced to DymensionHub.
Eclipse makes use of optimistic rollups on the Eclipse sovereign settlement layer that circulates fraud proofs directly to light clients. Eclipse uses the IBC to bridge between its different chains.
Source: Eclipse Caldera also uses fraud proofs, allowing them to leverage the security of a parent chain and benefit from already established security.
Source: Caldera More such services include AltLayer, Opside, Anytrust
Conclusion
The OP stack’s introduction of multiple proofs represents a new paradigm where multiple proof systems would lead to robust and agnostic rollups. It will make the rollups resilient against bugs or faults in the individual-proof systems. This could catalyze the testing of new proof systems since it won’t be as dangerous due to redundancy.
ZKFPs represent a completely new way of combining ZKVM, ZK proofs, and fraud proofs to improve gas costs and withdrawal times for optimistic rollups. Though far from a complete solution, we might be entering the era of combining proofs to optimize.
Proof systems are applicable not only to rollups, but they have found the most adoption with them. They could be potentially used everywhere, especially where trustless verification is required. This includes critical use cases like Identity and credit scores for financial applications.
RAAS, Rollup SDK providers appear to be aggregators of a lot of rollup components. Rollup architecture is also moving in a modular direction, and these simplified access points would be major distributions for rollup components. For the applications, it will be possible to have a customized stack just for execution from these providers.
ZK proofs are a general technology that has applications in AI and ML. ZKVMs could be used to prove the integrity of the computation of the models while keeping the data private. The models won’t be able to learn anything without the consent of the user and could pave the way for the user to get fair value for the data and interaction.
In the short term, fraud proofs have taken the lead in terms of the TVL for the bridges. But ZK proofs are quickly catching up with earlier-than-expected progress on ZKEVM and other VMs like ZKWASM. SNARKs are good at compression and don’t have to pay for gas costs like re-running. There are ongoing efforts to reduce the proving costs, and time using specialized hardware. With the combination of FHE and ZK, it would be possible to run computations privately while hiding the inputs as well as the details of the computation. But we do ZKPs, and ZKEVMs to dominate in the long term.