Validity Proofs vs. Fraud Proofs
Introduction
In this blog post, we analyze and compare various Layer-2 (L2) scalability solutions, based on the distinction between Fraud Proofs and Validity Proofs. We claim that Validity Proofs have a fundamental advantage, in that they ensure that nothing other than correct state transitions are accepted.
Background
In recent months several exciting proof-based attempts at solving Ethereum’s scalability problem have surfaced — projects such as Truebit, Gluon Plasma, dFusion, Roll-Up and Ignis. The basic idea is simple: instead of writing many transactions to the blockchain, one produces a proof that some succinct representation (e.g. a hash) of these transactions represents the new state of affairs.
The above-mentioned projects are all L2 solutions: they define a protocol (and logic) that runs on top of Layer-1 (L1), and relies on it for various services: deposits/withdrawals, a ledger for commitments to off-chain state, and as a “universal clock”. Importantly, L1 is not aware of, and therefore cannot enforce, any L2 logic.
We would like to present a framework for comparing these solutions, with a particular focus on the difference between Fraud Proofs, and what we shall refer to as Validity Proofs. Fundamentally, Fraud Proofs and Validity Proofs can exist in L1, but current attempts, and therefore our analysis, are all in L2.
Fraud Proofs present evidence that a state transition was incorrect. They reflect an optimistic view of the world: the assumption is that blocks represent only correct states of L2 data, until proven otherwise. In reality, a committed block could well include an incorrect state transition.
Validity Proofs present evidence that a state transition is correct. They reflect a more pessimistic view of the world. Blocks include values representing L2 state if, and only if, that state is correct.
Before proceeding, it is worth emphasizing: Proof Systems (e.g. SNARK, STARK) can be used as either Fraud Proofs or Validity Proofs. One should not confuse how we prove (e.g. SNARK, STARK) with what we prove (Fraud or Validity).
A Deeper Dive
Fraud Proofs
The main advantage of Fraud Proofs is that they are not needed for every state transition, but only when things supposedly break down. As such, they require fewer computational resources, and are a better fit for a scalability-constrained environment. The main disadvantage of these protocols stems from their interactivity: they define a ‘conversation’ between multiple parties. A conversation requires the parties — the party claiming fraud, in particular — to be present (liveness), and allows other parties to interrupt the conversation by various means. But the heart of the problem is the protocol’s interpretation of silence (the absence of a challenge to a new state) as implicit consent. Indeed, an attacker could attempt to create the semblance of silence with DDoS attacks.
Let us describe the conceptual protocol: Since a block may include an incorrect state transition, the Fraud Proof protocol allows for a time frame — the Dispute Time Delay (DTD) — to dispute this incorrect state. This window is measured in blocks. If no Fraud Proof is submitted within the DTD, the L2 state transition is considered correct. If a Fraud Proof is submitted to the smart contract, and is found correct (i.e., was submitted within the DTD, and indeed proves an incorrect state transition), it results, at a minimum, in the smart contract reverting to the commitment of the last correct L2 state. Additional steps, such as penalties to the violating party, may be applied.
The selection of the DTD duration is of consequence: the longer it is, the higher the probability of detecting an incorrect state transition — that is good. But, the longer it is, the longer users have to wait, for example, to withdraw funds — that is bad.
Validity Proofs
These are an altogether simpler beast: a representation of some off-chain computation is sent to a smart contract. The smart contract updates the blockchain with this new value only after it is verified as correct. The main advantages of Validity Proofs are that the blockchain will always reflect a correct L2 state, and that a new state can be immediately relied upon and used. The main disadvantage is that proofs are needed for each and every state transition, and not merely when such a transition is contested, and this impacts scalability.
51%-Attacks
Of the numerous possible attacks, we would like to focus on 51%-attacks on L1. We have seen a surge in these recently, including an attack on Ethereum Classic. How would Fraud Proofs and Validity Proofs fare against such attacks?
Fraud Proofs: A 51%-attack allows an attacker to introduce into the blockchain a fraudulent state and, for example, steal funds from an exchange being attacked. In more detail:
- The attackers create BlockFr with a fraudulent state transition. For example, that includes a transfer of all of the funds in the exchange to their own account.
- On top of BlockFr, they will add DTD blocks, culminating in a block that includes a withdrawal of the funds granted in BlockFr.
- They then continue to extend the chain beyond the DTD, and beyond the current chain. They are capable of doing so, as they control 51% of the hashrate.
- Disturbingly, the operating cost of launching such an attack is independent of the “jackpot” (and remarkably low at the moment: under $100K/hour of an attack on Ethereum), i.e. the funds controlled by the exchange under attack. This means that as the volume of activity in crypto-exchanges grows, they become increasingly attractive targets for such attacks.
To summarize, the root problem is that an L2 solution defines its own logic, and in particular permits a block containing a fraudulent state transition. The state of the ledger after our attacker stole the funds is a legal state! No double spend ever occurred and, yet, a fraud occurred.
Validity Proofs: A 51%-attack can merely unwind recorded history, and possibly offer an alternative history; importantly, this alternative history is also correct. The range of attacks that can be carried out here is limited to the attacks possible at L1. In crypto-to-crypto exchanges (and in particular, when all assets traded reside on the same blockchain), the unwinding of recorded history can at times be a hugely profitable move: a seller, for example, may be delighted to unwind a transaction that took place at what in hindsight was a rock-bottom price, but in an exchange of crypto-assets on a given blockchain there is no means of outright theft of assets.
Proposed Solutions
Why are Fraud Proof systems (e.g. Gluon Plasma and dFusion) being considered, given these substantial disadvantages? The main reason is that proving validity was up until recently too expensive and cumbersome.
Prior to the use of Proof Systems, the only option for “Validity Proofs” in a permissionless system involved naive replay, and as such greatly limited scalability; in essence this replay is what is still done today in L1, with the known penalty to scalability. Proof Systems offer a very appealing trait known as succinctness: in order to validate a state transition, one need only verify a proof, and this is done at a cost that is effectively independent of the size of the state transition (more precisely, it is polylogarithmic in the size of the state transition).
Ignis/Roll-Up both rely on SNARKs that require a trusted setup and considerably more prover computing resources than STARKs. StarkWare is working on deploying StarkDEX, its scalability solution for DEXs, which will use STARKs to achieve Validity Proofs. We intend to see this deployed on testnet by the end of Q1 2019.
Conclusion
This blog post compared Fraud Proofs to Validity Proofs as tools for L2 scalability solutions. We highlighted the inherent advantages of Validity Proofs with respect to 51% attacks. STARKs, with their fast proving time, succinct verification and trustless setup, are a compelling means for producing Validity Proofs.
Thanks to Dan Robinson, Linda Xie, Alexey Akhunov, and Georgios Konstantopoulos for reviewing drafts of this blog post.
StarkWare
.jpg){kind=link}