The detailed explanation of the original text of V God: solving the 51% attack problem of the blockchain through the timeliness detector (TD)

Note: The original author is Ethereum co-founder Vitalik Buterin. In this article, he proposed a structure called Timeliness Detector (TD) to try to solve the problem of 51% attacks on the blockchain.

(Photo: Vitalik Buterin)

The following is a translation:

• Active change, Libra or USD single anchor
• Lamborghini has a correlation with Bitcoin. Can it predict the price trend?
• DAO, rises in 2020

Summary

I proposed a construct based on Lamport's 99% fault-tolerant consensus , and called it timeliness detectors. Timelyness detector (TD) allows online clients ( that is, clients connected to other clients with delays ≤ δ, also known as users ) to detect whether a block was released "on time" while ensuring correctness and consistency.

In the event of a 51% attack, this allows at least a portion of the online clients to agree on (i) whether a "bad enough" 51% attack has occurred and determine (ii) what is the "correct" chain, and it is even possible (Iii) Determine which verifiers are responsible for the attack. This reduces the ability of a 51% attack to cause chaos, speeds up recovery time, and potentially increases the cost of a successful attack.

Timelyness detector (TD)

The most basic structure of the timeliness detector is as follows. For each data block received by the client, the client maintains a "whether timely" basis, which will indicate whether the client believes that the block was received "on time". The purpose is to try to distinguish the attack chain from the "correct" chain in 51% of attacks:

Our model is simple: each block B has a self-declared timestamp t (in actual protocols, timestamps are usually hidden, such as displayed in the number of slots). Then there is a mutually agreed synchronization constraint δ. The simplest time detector is: if you receive block B before time t + δ, then you think the block is timely, and if you receive it after time t + δ, you won't think It is timely. But this does not agree:

We solve this problem in the following way. For each block, we randomly select N "proofer" samples (v1 … vn). Each prover follows the rule: if they see a block B with a timestamp t that has signatures from k provers before time t + (2k + 1) δ, they use their signatures to recreate broadcast. The rules that clients follow are: if they see a block B with a timestamp t and signatures from k provers before time t + 2kδ, they will accept it in time. If they see block B, but it never meets this condition, the client considers block B to be untimely.

Let's see what happens when only one client considers a block B to be timely, but other clients may initially not consider it to be timely due to delay differences. We first assume that there is an honest prover.

This picture shows the rationale behind what happened. If the client sees a block before the deadline T, then the block will fall into the hands of the prover before the deadline T + δ of the prover, and the prover will add their signature and they will be at time T Rebroadcast it before + δ to ensure that other nodes see the signed block before T + 2δ. The key mechanism is the ability to attach a signature to delay the deadline.

Now, let us consider the case of n−1 dishonest prover and 1 honest prover. If the client sees a timely block with k signatures, there are two possibilities:

1. One of these k signatures is honest;
2. None of the k signatures are honest;

In case (1), we know that the prover is honest, so the prover broadcasts block B with j ≤ k signatures before time T + (2j−1) δ, which means (by the synchronization assumption ) Each client sees the bundle before time T + 2jδ, so each client accepts block B as the current block.

And in case (2), we know that the honest prover will see the bundle before time T + (2k + 1) δ, so they will rebroadcast it with their own signature, and all other clients will be at k The extension bundle was seen before the +1 signature deadline T + (2k + 2) δ.

So now we have a "timeliness detector" that clients can use to track which blocks are "on time", which blocks are "out of time", and when all delays are less than δ The client will agree which blocks are on time.

The simplest blockchain architecture

To decide who can make a proposal, who can prove the goal of a block in any slot. We can define a "99% fault-tolerant blockchain" like this: To determine the current state, simply process all timely blocks in their own timestamp order.

This is actually feasible (and provides resistance to final reversal and censorship of 51% attacks), and gives a rather simple blockchain architecture under its own assumptions! The only problem is: everything is built on the assumption that all clients will be online and the network will never be interrupted. Therefore, it may take a week or more to make it work securely , and this is actually a reasonable structure of an “auxiliary chain” that can track deposits, withdrawals, and forfeitures of validators , for example, (By reviewing newly added validators, etc.) to prevent long-term 51% attacks. But we do not want to apply this architecture to the main chain.

More reasonable choice

In this article, however, we will focus on system architectures that satisfy a set of weaker security assumptions. That is, they are good if any of the following two assumptions are true: (i) network latency is low, including network latency between the verifier and the client, and (ii) most validators are honest Yes . First, let's go back to a model where we have a blockchain with some fork selection rules, not just discrete blocks. We will go through our two favorite examples of final fork selection rules, (i) FFG and (ii) LMD GHOST.

For FFG, we extend this fork selection rule as follows. Starting from the founding block, whenever you see a block where both sub-chains have completed, please select lower-epoch to complete the block's chain in time. Then from there continue to go the same way. In general, in two cases, there will only be two conflicting final chains: (i) 33% of attacks, and (ii) many nodes going offline (or censoring) leading to long-running inactivity leaks.

Case (i):

Case (ii), option 1 (a few offline):

Case (ii), option 2 (offline majority, reappears later with the finalized chain):

Therefore, in all cases, after at least a certain time point (T + 2kδ, after this time point, if the client does not accept a block in time, then we know that it will never accept it in time), we all Can prevent 51% attacks from damaging finality. Also note that the figure above is a bit misleading. What we care about is not the timeline for completing the block, but the timeliness of the block, including evidence that the block has been finalized.

For clients that are sometimes offline, as long as there is no 51% attack, this will not change anything: if the chain is not attacked, the blocks in the canonical chain will be timely, so the final determined block will always be Timely.

The main situation that can lead to increased risk is that clients have high latency but are unaware that they have high latency. They may regard timely blocks as non-real-time blocks, or they may regard non-real-time blocks as timely blocks. The goal of this mechanism is that if the non-temporal dependency fork selection and the temporal dependency fork selection are inconsistent, the user should be notified so that they can verify what is happening. They should not be instructed to blindly accept reliance on timeliness fork selection as a norm.

When dealing with review issues, we can also use the timeliness detector to automatically detect and block reviews. This is simple: if block B with self-declared time t is timely, then any chain that does not contain the block before time t + (2k + 2) δ (whether as an ancestor block or as an uncle block) will Automatically determined as a non-canonical chain . This ensures that chains whose review blocks exceed (2k + 2) δ will be automatically rejected by the client.

The main benefit of using the Timeliness Detector (TD) here is that it can form a consensus when reviewing "too much" and avoid the risk of "edge attacks" which are deliberately designed to target certain users (But not other users) is bad enough, causing the community to waste time and energy arguing about whether to fork the censorship chain (in contrast, most users will agree to the correct course of action in any case).

Note that this requires an uncle block inclusion mechanism, which is currently not available in Ethereum 2.0. In addition, it also needs a mechanism to execute transactions inside the block, so that censorship resistance can be extended to transactions, not just the original body of the block. This needs to work well with stateless clients .

Another problem is that care needs to be taken to deal with the possibility of many blocks being published and gaining a state of timeliness. This may be due to a publishing delay, or due to a proponent maliciously publishing multiple blocks in the same slot. The former can be processed by a modified rule, where the block must include all timely blocks or the maximum allowable number (such as 4) of uncle blocks that are all earlier than (2k + 2) δ.

The latter can be handled by a rule: if a block from a specific slot is included, all other blocks from that slot can be effectively ignored.

Please note that in the Casper-CBC framework, reviewing and preventing and canceling priority operations on chains containing non-temporary or censorship blocks is sufficient to provide the same finality guarantee as the FFG framework described above.

Challenges and tasks

1. Figure out the best way to explain to users in non-technical language what happens when the timeliness awareness and non-timeness awareness fork selection rules are inconsistent, and how they should respond to this situation;
2. Analyze the system's behavior when the delay is sometimes higher than δ, or the delay is always potentially higher than δ, and we have assumptions (for example, the prover of some fixed part is honest, or other mixed assumptions). See if there are ways to modify the rules to improve performance in these scenarios;
3. Analyze and implement these attributes without the need to include new proofs. Instead, only existing proofs need to be reused (for example, a validator's proof for each epoch in the FFG);
4. Determine if there are some minor modifications to the "simple" longest chain fork selection rules that will allow them to benefit from the timeliness detector and thus achieve some kind of finality.

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