Original author:Original author:soul machinehttps://v.qq.com/x/page/f07704nx4iq.html
Casper FFG is a PoW/PoS hybrid algorithm proposed by Vitalik, the purpose of which is to allow Ethereum to smoothly transition to pure PoS. The paper is here, Casper the Friendly Finality Gadget, this paper mainly explains the core knowledge points of this paper.
first level title
It is currently 2018, and Ethereum is still a blockchain with a pure PoW algorithm, just like Bitcoin. PoW is a very simple algorithm and very safe. For example, this paper Analysis of the Blockchain Protocol in Asynchronous Networks proves that Bitcoin is actually very safe. Nevertheless, if a miner has more than 51% of the algorithm, it is still theoretically possible to rewrite the previous block.
image description
PoW process
The yellow miners in the picture above suddenly increased their calculations and started to do bad things. Starting from an old block, a new chain was forked and continued to mine on it. If its length exceeds the left, then the new chain will be broken. If the old chain can be successfully replaced, the previous old block will be revoked, and all transactions inside will be overwritten and rewritten.On the basis of the current PoW, Casper FFG adds a layer of PoS voting process, which further enhances Finality, and it is theoretically impossible for old blocks to be revoked. Casper FFG is a non-invasive algorithm. It does not change the current Ethereum PoW algorithm, but adds BFT-style PoS on this layer of PoW. That is to say, all blocks are dug out by PoW miners. This core The process is preserved. On this basis, every time 100 blocks are mined, the PoS verification nodes will vote on the last block. After 2/3 pass, the last block is called checkpoint (checkpoint).Any checkpoint that is finalized cannot be undone.
To sum up, the mechanism of PoW block generation is retained, and at the same time, PoS votes every 100 blocks, which further enhances the security (Safety, or Finality) of Ethereum.
The fields of the voting message are as follows:
As shown in the above table, each voting message contains 5 fields, s represents the block hash of the source checkpoint, t represents the block hash of the target checkpoint, h(s) represents the block height of s, h( t) represents the block height of t, and S represents the signature. Of these 5 fields, only 3 are really core, namely h(s), t, h(t).
The voting message of Casper FFG cleverly combines the two steps into one step. In essence, it is still equivalent to the two-stage voting in pBFT and Tendermint, pre-prepare->prepare, pre-vote -> pre -commit.
The figure below explains why voting requires two stages.
At the same time, the voting message of Casper FFG has a similar effect to the locking mechanism in Tendermint.
The following are the definitions of several terms often seen in the Casper FFG algorithm:supermajority linkone piece
, written as a→b, means that if more than 2/3 of the voting messages start from checkpoint a and point to checkpoint b, then there is a supermajority link between a and b. A supermajority link can span several checkpoints, that is to say, h(b)>h(a)+1 is legal.Two checkpoints a and b mutuallyconflict
, which means that a and b are on different branches, that is to say, a and b are not on the same path.justifiedA checkpoint c is to become a
A checkpoint needs to meet one of the following conditions, (1) it is a genesis block; (2) or there is a supermajority link pointing to it.finalizedA checkpoint c is to become aCheckpoint, it needs to be justified and there is a supermajority link originating from it, c→c', and c' is itsdirect child
, that is, the height of c' is the height of c increased by 1.
The green checkpoint in the above figure is a justified state before voting. When more than 2/3 of the votes are made, the justified block is used as the source and points to another higher block, then the original justified block becomes It has become finalized and can no longer be revoked, and the new block becomes justified. Between the finalized and justfied blocks, a supermajority link is formed.
first level title
Penalty Condition (SlashCondition)
1. No double vote: If the Validator violates any of the following two conditions, it will be punished and all deposits will be confiscated.
2. No surround vote.t1==t2. It is not possible to vote for two different blocks at the same height. This is relatively easy to understand. At the same height, voting for two different blocks is a typical speculative behavior of Nothingat stake, which will be punished.< t1,t2 < t1 < s1 < s2 . For example, a validator first casts a vote, s1 -> t1, after a few blocks, continues to vote, s2 -> t2, since the block height is increasing with time, it is obvious that s2> e1, and the second if t2
It is lower than the target block of the previous vote, which is problematic, because you voted s1 -> t1 earlier, which means that you have recognized that all blocks between s1 and t1 are correct, but the second vote s2 ->t2, the interval is smaller than s1->t1, completely covered by s1->t1, this vote repeatedly agrees the block between s2 and t2, as if you have forgotten the previous vote. Such forgetting behavior will also be punished.
The figure below shows an example of a Nodouble vote violation,
During PoW mining, it is normal for forks to occur at the same height. At this time, among the 4 validator nodes, there are 2 malicious nodes who voted for both forks at the same time, which will cause the two new blocks to become justified. In this case, the two malicious nodes will be punished, the deposit will be destroyed, and the person who reports will get a reward (finder's fee).
The figure below shows an example of a violation of No surround vote,
Next, a validator node can start voting. Since there are two justified checkpoints, it can choose any one as the source point. Suppose it votes for B->E and the other votes for C->D. is illegal and violates the no surround vote rule.
first level title
Proof of Safety and Plausible Liveness
In this section, we will prove the Safety (Finality) and Liveness of Casper FFG.
First of all, Casper FFG claims to be accountable safety and plausible liveness. Accountable means that validator nodes need to pay a considerable amount of deposit. With the deposit, there is initial trust and can be counted on (accountable).
Plausible liveness is actually nothing new. It is exactly the same as the liveness of Bitcoin. It means that when the network splits (partition), the entire system can still write new transactions and generate blocks.
The detailed proof begins below.
Accountable Safety: Two conflicting checkpoints (checkpoint), am and bn cannot be finalized (finalized)prove:
Using the method of counter-evidence, assume that am and bn conflict with each other (that is, on the two branches, not on the same branch) and the finalization is finalized, and they each have a justified sub-block am+1 and bn+1.
If their heights m and n are equal, there must be 1/3 of the verification nodes voting for both checkpoints at the same time. These nodes violate the rule of No double vote, and all deposits will be destroyed, losing 1/3 The verification nodes, am and bn cannot be finalized.If the heights m and n are not equal, let n > m(n
< m proves the same process), the path from the genesis block to bn is genesis→b1→b2→...→bi→bj→...→bn, bi is the first block whose height is less than or equal to am, that is i≤m, bj is the first block whose height is greater than or equal to am+1, that is, j≥m+1. The following proves that:
If i==m, 1/3 of the verification nodes violate the no double vote rule and will be punished, making it impossible for am and bn to be finalized;
If j==m+1, same as above;
m+1, it means that there is a supermajority link bi→bj, which completely surrounds am->am+1, which violates the no surround vote rule, and 1/3 of the nodes will be punished, making am and bn impossible Will be finalized. Some people may ask that bi and bj may not be finalized. Even so, at least genesis→bn surrounds am->am+1, which still violates the no surround rule.
To sum up, it is impossible for am and bn to be finalized under any circumstances, and the proof is complete.
Plausible Liveness: As long as more than 2/3 of the validator nodes vote using the justified block as the starting point, a new finalized block can always be generated.
Simply put, it takes a justified block as the starting point, and you can vote for any node higher than it. For example, there are two new blocks, one am at height m, and one bn at height n (including the starting point, three blocks must be On a line), then you can vote for either of the two, or even both, without violating the nodouble vote and nosurround vote rules. That is to say, you can skip multiple blocks and directly cast higher blocks. The next justified block may be am or bn, or both (both get more than 2/3 votes, at this time there must be more than 1/3 of the nodes voted for both) that's why The reason is called plausible.
Even if the network splits, PoW can continue to generate blocks on both sides, but at this time the Validators nodes can no longer reach 2/3 votes on any checkpoint, because half of one side cannot communicate. Even so, the chain can not be finalized continue to grow. When the network is split into two halves, it can still operate (Tendermint can only wait indefinitely when the network is split). This kind of robust liveness may be another meaning of plausible.Casper FFG can be deduced from Plausible livenessForkChoice Rule: Always choose the longest chain on top of the justified checkpoint with highest.
That is to find the highest justified block first, and then start from this block to select the longest chain. Compared with the simple selection of the longest chain in the PoW algorithm, there is one more prerequisite.
For example, as shown below:
Then, after a period of time, the network finally recovered. Which fork should we choose at this time? The one above or the one below? According to the fork choice rule of PoW, the longest one should be chosen, which is the one above. However, in CasperFFG, the rules are slightly changed. The one with the highest justified block should be selected first. If the justified blocks on both sides are the same height, then the longest one should be selected. According to this rule, although the upper fork is the longest, the latest justified block has the highest height in the lower fork, so the lower fork should be selected first.
first level title
In order to simplify the paper, it is assumed that the validator node is a fixed set. In fact, CasperFFG has a mechanism to dynamically update the validator set, which is not detailed in the paper and will not be expanded here. Because this knowledge point has little to do with understanding the core algorithm of CasperFFG, there is no need to delve into it.
first level title
Nothing At Stack Attack
In the Casper FFG algorithm, PoW is responsible for generating blocks, and there is no non-profit attack in this part. But in the voting stage, there is no cost. In order to prevent non-profit attacks, the method is similar. Validator nodes need to pay a deposit before voting. Once the voting is found to violate the Nodouble vote rule, all deposits of the malicious node will be destroyed. Therefore can effectively prevent attacks.
first level title
Long Range Attack
Long-range attacks refer to the following three situations:
In the case of pure PoS, since there is no cost to generate blocks in pure PoS, it is easy to create a forked chain longer than the real chain.
In the case of PoW, assuming that malicious nodes have more than 51% of the computing power, they can also create a forked chain that is longer than the real chain. This kind of situation is relatively rare, because there is a cost for PoW block production. With such a large computing power, it is better to mine honestly and get more rewards. However, if a malicious node had a transaction with a huge amount a long time ago, driven by profit, the malicious node also has the motivation to re-fork and double spend the money. In this case, the malicious node will also launch a long-range attack.
The third case is applicable to PoS and PoW. If a new full node just goes online, it happens to be connected to several malicious nodes to start synchronizing blocks. The chain is still long. At this time, even if an honest full node is connected later, the chain sent by the full node is shorter and will be rejected by the new node. That's embarrassing.Proof of Stake: How I Learned toLove Weak Subjectivity For the first and third cases, the problem is essentially the same. When a longer chain is received, how to judge whether it is true or false? Vitalik in this post
Explaining the solution, we still need to introduce a little bit of knowledge and trust from the outside world, the so-called weak subjectivity. V God believes that this kind of weak trust is easy to achieve, so it does not weaken the Safety of the blockchain. When a new node comes online, it needs to obtain and trust the following knowledge from the outside world:
1. The protocol definition. This is easy to handle, the protocol of the blockchain exists in the code. Which version of the code a new node runs means that it trusts the code by default.
2. The latest valid block. This block cannot be too old, it must be within the last N. N can be defined in advance, as long as it is fresh enough. For example, for Bitcoin, any block within the last 6 is considered new enough. For Ethereum, the last 12 blocks are relatively new. up.
For 2, the problem is big. When a new full node goes online, where can I get the latest valid block? Additional trust knowledge needs to be introduced here. For example, for CasperFFG, when a new node goes online, it should only trust the full node that has paid the deposit, and it is best to connect multiple nodes to obtain the latest finalized block. When you get the latest finalized block, you can rest assured to start the synchronization. Even if you receive a longer chain from the malicious node, since the hash value of the block of the malicious node must be different at the same height, it can be judged that it must be A fake chain, throw this chain away.
There is an informal proof at the bottom of page 7 of the paper. I think it is meaningful to prove that the refund delay time needs to be greater than 4 times the network delay time, ω>4δ.
first level title
Cases of Massive Crashes (Castastrophic Crashes)
If more than 1/3 of the verification nodes crash at the same time, or the network has problems that cause them to go offline, or the network splits, it is impossible to gather more than 2/3 of the votes when voting at this time, that is to say, from now on , cannot create a new supermajoritylink, that is, cannot finalize any new block. Inactivity leak The paper introduces a method called
first level title
Summarize
Summarize
The Casper FFG algorithm consists of 3 parts: 2 penalty conditions (slash condition), a fork choice rule (fork choice rule) and a dynamic set of verification nodes. Casper FFG is applicable to any PoW algorithm, improving the security of PoW algorithm.
The block generation mechanism of Casper FFG is PoW (PoW based block proposal mechanism). In the future, the block generation mechanism will be replaced by PoS, which is pure PoS.
Regarding the complexity of network communication, in the PoW stage, it is O(n), and in the BFT voting stage, it is O(n2). Generally, due to the capital threshold, the number of verification nodes is small compared to the entire network nodes, so even if it is O(n2), since n is small, the communication volume is still relatively small.
Regarding the maximum fault tolerance, in the PoW stage, the computing power of malicious nodes can be tolerated to be less than 50%, and in the BFT voting stage, the amount of funds required by malicious nodes is less than 1/3. In a simple and rough summary, the maximum fault tolerance can be considered to be 1/3.
Regarding the network assumption, it is synchronous in the PoW stage, and asynchronous in the BFT voting stage. In general, the network assumption is synchronous.
secondary title
References
Casper the Friendly Finality Gadget
EthereumPoS: Casper FFG In Depth - YouTube
Ethereum PoS Overview: Casper FFG
Casper FFG with one message type,and simpler fork choice rule
Ethereum Casper 101
A Simplified Look at Ethereum’sCasper
Consensus Compare: Casper vs.Tendermint - Medium
Proof of Stake: How I Learned toLove Weak Subjectivity
