Proof of validity and proof of error in Science-2 |

introduction

In this paper, we will analyze and compare different Layer-2 scalability schemes from the difference between Fraud Proof and Validity Proof. We assert that, in contrast, proof of validity is fundamentally advantageous because the proof of validity scheme guarantees that only state transitions of the form will be accepted.

background

In recent months, proof-based Ethereum scalability options—such as Truebit , Gluon Plasma , dFusion , Roll-Up, and Ignis —have surfaced, and it’s exciting. The idea behind these projects is simple: instead of writing a lot of transactions to the blockchain, it's better to generate a proof (such as a hash) that can succinctly represent these transactions and represent a new state.

All of the projects mentioned above are Layer-2 solutions: they define a protocol (and logic) that runs on Layer-1 and provide multiple services based on these protocols: storing funds/withdrawal of funds, a chain of dependencies The current state of the book is updated and operates as a "global clock". Importantly, these protocols are not embedded with Layer-1, so Layer-1 cannot enforce any of the Layer-2 logic.

Here, we want to develop a framework to compare these programs, especially the difference between the "false proof" and what we call "validity proof." The proof of error and the proof of validity are not patents of Layer-2. They can also exist on Layer-1, but currently everyone only tries on Layer-2, so our analysis is also based on Layer-2.

• Economist Ba Shusong: The Application Value of Blockchain Technology in the Financial Field
• The volume is falling, is it a dishwashing or a shipment?
• Bitcoin becomes a sovereign currency? There are three obstacles to overcome

An error proof is evidence that an state transition is incorrect. This approach reflects an optimistic attitude: assume that the Layer-2 state represented on the block is correct unless someone can prove it is not. In fact, the blocks submitted to the chain are also likely to contain an illogical state transition.

A proof of validity is evidence that a state transition is correct. The attitude of this scheme is more negative: if and only if a certain state is correct, the block should contain values ​​that represent the corresponding Layer-2 state.

Before proceeding with the analysis, it is necessary to emphasize that the certification system (such as SNARK, STARK) can be used both as a proof of error and as proof of validity. We should not confuse the way of proof (for example, SNARK, STARK) and the purpose of the proof (error or validity).

In-depth analysis

False proof

The main advantage of the proof of error is that there is no need to provide proof for each state transition, only when the system needs to be interrupted. Therefore, the error proof scheme requires less computing resources and is more suitable for environments with limited scalability. The main drawback of this scheme comes from its non-interactivity: it defines a "session" between multiple parties. A session requires that parties—especially those who assert that the state transition is incorrect—must be online (the system is active) and allow other parties to interrupt the session in a variety of ways. But the core of the problem is that the agreement will treat silence (ie, the absence of the challenger) as an implicit consent. In fact, an attacker can try to create a surface silence with a DDoS attack.

Conceptually, the proof of error scheme can be expressed as follows: Because the block may contain incorrect state transitions, the error proof protocol sets a time frame, the Dispute Time Window (DTF), to handle incorrect states. The length of this window is also defined by the number of blocks. If no error proof is submitted within the dispute time window, the corresponding Layer-2 state transition will be considered valid. If someone submits a false proof to a smart contract and it proves to be correct (ie, submitted within the window period and proves that a state transition is illogical), then (at least) the smart contract will be Layer-2 The state is rolled back to the last correct state. In addition to this, it is possible to impose punishment on the evil party, and so on.

The choice of DTF length is important: the longer the DTF, the higher the chances of finding a wrong state transition – it sounds great. But at the same time, the longer the time, the longer the user needs to wait (such as when the withdrawal is required), which is a side effect.

Proof of validity

Proof of validity is generally simpler: send evidence to a smart contract that some chain calculations have occurred. Smart contracts update the blockchain only after a new value has been proven to be correct. The main advantage of proof of validity is that the blockchain always reflects a correct Layer-2 state, and a new state can be used immediately. The main disadvantage is that each and every state transition requires a proof, not only when the state transition is challenged, but also requires proof, which affects its scalability.

51% attack

Among the many possible attack methods, we mainly focus on the 51% attack on Layer-1. Recently, 51% of attacks have been frequent, and even the Ethereum classics have not been spared. So how does the proof of error and validity prove how to deal with this kind of attack?

False proof: A 51% attack introduces a fraudulent state in the blockchain, such as “stealing” some funds from the exchange. Details as follow:

• The attacker created the block BlockFr with a fraudulent state transition. For example, the block contains a transaction that transfers all funds in the exchange to the attacker's account.
• After BlockFr, they will also connect to the DTF block and end up with a block containing the withdrawal transaction (the withdrawal transaction will take out all the funds the attacker got from the BlockFr block).
• Then they continue to generate blocks after the DTF block until the current chain becomes a longer chain. They can do this because they have 51% of the computing power
• The hard part is that the operating cost of launching such an attack has nothing to do with the “bonus” size (the amount controlled by the attacked exchange) (it seems to be quite low at the time of the article: only 10 attacks per hour on the Ethereum Ten thousand dollars ). This means that as the volume of cryptocurrency exchanges rises, attacking exchanges will become more attractive.

All in all, the root of the problem is that the Layer-2 solution defines its own logic and allows a block to contain fraudulent state transitions. In this way, the account status after the attacker steals funds will also be considered a legal status! There is no double cost, just a fraud.

Proof of validity: 51% of attacks can only obscure the history of existing books, and may provide another history; but importantly, this new history is also completely correct. The scope of the attack mentioned here is limited to attacks that may be launched on Layer-1. In currency exchanges (especially those exchanges where all assets are recorded on the same chain), it is sometimes a blessing to overwrite history: for example, a seller may be happy to cover up for a while. Look at the transaction at the bottom of the transaction price, but there is no way to directly swallow the other party's money in the exchange on a given blockchain.

Our proposed solution

If there is such a clear disadvantage, false proof systems (such as Gluon Plasma and dFusion) will also be an option?

The main reason is that providing proof of validity is still very expensive and cumbersome to date.

Before using the attestation system, the only "validity proof" in the license-free system was simple replay, so scalability was greatly limited; moreover, this double counting is still on Layer-1 today. Used, although it is known to be an obstacle to scalability. The proof system provides a very attractive feature called succinctness: in order to verify a state transition operation, you only need to verify a proof, and the overhead of the validation is completely independent of the computational magnitude of the state transition. (More precisely, it is a polylogarithmic relationship with the size of the state transition operation).

Ignis/Roll-up are based on SNARK (simple non-interactive knowledge proof) and require a trusted initial setup, and require more data from the certifier than STARK. StrakWare is working hard to deploy StarkDEX to provide a scalable solution for decentralized exchanges; he will use STARK for proof of effectiveness and we expect to deploy to the test site by the end of the first quarter of 2019.

in conclusion

This paper compares the proof of error and proof of validity as the tool value of the Layer-2 scalability solution. We highlight the inherent advantages of proof of effectiveness against 51% of attacks. STARK, because it proves that time is faster, and that verification is simple and does not require a trusted initial setting, is a powerful tool for generating proof of validity.

Thanks to Dan Robinson, Linda Xie, Alexey Akhunov, and Georgios Konstantopoulos for reviewing the first draft of this article.

Original link: https://medium.com/starkware/validity-proofs-vs-fraud-proofs-4ef8b4d3d87a Author: Avihu Levy & Uri Kolodny Translation: A Sword

(This article is from the EthFans of Ethereum fans, and it is strictly forbidden to reprint without the permission of the author.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!