Fraud Proof vs Validity Proof

Fraud Proof vs Validity Proof
(Picture from internet)

In this article, we analyze and compare various Layer 2 (L2) scalability solutions based on the difference between Fraud Proof and Validity Proof. We believe that proof of validity has a fundamental advantage because it ensures that only correct state transitions are accepted.

Background In recent months, several projects have emerged to address Ethereum scalability issues (such as Truebit, Gluon Plasma, dFusion, Roll-Up, and Ignis, etc.), which are all based on proof. The basic idea is simple: instead of writing a lot of transactions to the blockchain, you generate a proof, using some concise representations of these transactions (such as hashes) to represent the new state. The projects mentioned above are L2 solutions: they define a protocol (and logic) that runs on Layer 1 (L1) and rely on it to provide various services, such as deposits/withdrawals, to confirm the underlying status of the ledger. And as a "general clock". Importantly, L1 does not understand the logic of L2 and therefore cannot perform any L2 logic. We want to propose a framework for comparing these solutions, paying particular attention to the difference between proof of fraud and proof of validity. In essence, fraud proofs and proof of validity can exist in L1, but current attempts and our analysis have focused on L2. The fraud certificate provides evidence that the state transition is incorrect. They reflect an optimistic view of the world: it is assumed that the block represents the correct state of the L2 data until it proves to be not the case. But in reality, a committed block may contain incorrect state transitions. The proof of validity presents evidence that the state transition is correct. They reflect a more pessimistic view of the world. The block will only include the value representing the L2 state if the state is correct. It is worth emphasizing that there are two forms of proof of use systems (such as SNARK, STARK): proof of fraud and proof of validity. People should not confuse how we prove (such as SNARK, STARK) and what we prove (fraud or validity). Explore the fraud certificate in more depth.

The main advantage of fraud certification is that they are not required for each state transition. Therefore, they require less computing resources and are more suitable for environments with limited scalability. The main drawback of these protocols stems from their interactivity: they define a "conversation" between multiple parties. The dialogue requires the parties – especially those who claim fraud – to be online (active) and allow others to interrupt the conversation in a variety of ways. But the core of the problem is that the protocol is silent (ie, no challenge to the new state) is interpreted as the default consent. In fact, an attacker might try to use a DDoS attack to create the illusion of silence.

Let us describe the concept protocol: Since the block may contain incorrect state transitions, the fraud certificate protocol allows for a time frame, the Dispute Time Frame (DTF), to challenge this error state. This time window is measured in blocks. If no evidence of fraud is submitted within the DTF, the L2 state transition is considered correct. If the fraud certificate is submitted to the smart contract and found to be correct (ie, submitted within the DTF and does prove that the state transition is wrong), then at least the smart contract will be restored to the last correct L2 state. Other measures, such as penalties for violators, may also be enforced.

Different choices of DTF duration will lead to the result that the longer it is, the higher the probability of detecting an error state transition - this is the good side. However, the longer the time, the longer the user has to wait, for example, withdrawing funds – this is the bad side.

Proof of validity Proof of validity is much simpler in comparison: some forms of offline computing are sent to smart contracts. The smart contract will update the blockchain with this new value only after the verification is correct. The main advantage of proof of validity is that the blockchain will always reflect the correct L2 state and the new state can be used immediately. The main drawback is that each state transition needs proof, not just when the transition is controversial, which affects scalability. 51% Attacks Among the many possible attacks, we focus on 51% of attacks on L1. We have recently seen this type of attack happening, including the classic attack on Ethereum. How does fraud certification and proof of validity defend against such attacks?

Fraud Proof: 51% of attacks allow an attacker to introduce a blockchain into a fraudulent state, for example, stealing funds from an attacked exchange.

An attacker creates a BlockFr using a fraudulent state transition. This includes, for example, transferring all funds in the exchange to their own account.

On top of BlockFr, they will add DTF blocks and eventually form a block that includes all the funds granted in BlockFr.

Then they continue to extend the chain beyond the DTF, as well as outside the current chain. They have the ability to do this because they control a 51% hash.

The cost of launching such an attack (currently very low, the cost of launching an Ethereum attack below $100,000/hour) is independent of the potential gains (ie, the funds controlled by the attacked exchange). But as trading activity in encrypted exchanges increases, they are more likely to be targets of such attacks.

All in all, the fundamental problem is that the L2 solution defines its own logic, allowing blocks that contain fraud state transitions. The status of the ledger after the attacker steals the funds is still legal! No double payments occurred, but fraud occurred.

Proof of validity: 51% of attacks can only reverse the history of records and may provide new historical records; importantly, this alternative history is also correct. The range of attacks that can be performed here is limited to attacks that may occur with L1. In currency exchanges (especially when all trading assets reside on the same blockchain), reversing the record can sometimes be a profiteering move: for example, the seller may be happy to reverse one after another to find out The cheapest transaction, but in an exchange where an encrypted asset is stored in a given blockchain, there is no way to directly steal the encrypted asset.

Proposed solution Given these obvious shortcomings, why do many projects (such as Gluon Plasma and dFusion) still use fraud proofs? The main reason is that the proof of validity is too expensive and cumbersome. Before using the attestation system, in a system that does not require a license, the "validity of validity" involves native replay, thus greatly limiting the scalability; essentially, the current replay is still on L1. To proceed, everyone has already understood its limitations on scalability. Proof system provides a very attractive feature called simplicity: in order to verify state transitions, only proof of verification is required, and the cost of doing so is actually independent of the size of the state transition (more precisely, it is a state transition) Multi-logarithmic function of size). Ignis / Roll-Up relies on SNARK that requires trusted settings, and it requires more proof computing resources than STARK. StarkWare is working hard to deploy StarkDEX (DEX's scalable solution), which will use STARK for proof of validity. Conclusion We highlight the inherent advantages of proof of effectiveness in 51% of attacks. With its fast verification time, simple verification and untrusted setup, STARK will be a powerful means of proof of production-level effectiveness.