Security analysis of the Byzantine protocol Casper FFG in ethereum | Sperax

Professor yongge wang is a distinguished Chinese cryptographer and tenured professor of computer science at the university of north Carolina, Charlotte. He holds a doctorate from the university of Heidelberg in Germany.

Today we discuss the security of the Byzantine protocol Casper FFG. Our analysis is based on the Casper FFG protocol in the following papers:

● V. Buterin and V. Griffith. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437v4, 2019. https://arxiv.org/pdf/1710.09437.pdf

Traditional Byzantine protocols are primarily used to replicate state machine (state machine) communications SMR environments. The environment of a blockchain is different from that of a replicated state machine. So we can design a simpler Byzantine protocol for the block chain. Buterin and Griffith tried to design a simplified Byzantine protocol as a small pendant with the final certainty of block. In particular, Buterin and Griffith designed the Byzantine protocol Casper the Friendly Finality Gadget (Casper FFG). In Casper FFG, the blocks generated by the PoW system need to be voted on by some of the participants (the block verifier). This prevents the blockchain from branching. To simplify our discussion, we assume that there are n = 3t + 1 equal-weight block verifiers in the system. To ease the verification effort, let's construct a checkpoint tree. The nodes of the checkpoint tree include only block nodes with a height of 100 bootk on the block chain. Suppose s and t are two nodes in the checkpoint tree, and s is the ancestor of t. If a verifier Pi think s to t the block can be confirmed, Pi for all the verifier broadcast a signature of the vote ⟨ Pi: s, t ⟩. For two checkpoints a and b, if we receive 2 t + 1 vote ⟨ P: s, t ⟩, so we say that a and b have an absolute majority of the connection. If we have a supermajority chain of connections starting at the root node a0 a0 → a1 → · · · → a, then it makes sense to say checkpoint a. If we have an absolute majority chain of connections starting from the root node a0 a0 → a1 → ·· → ai → a and a is the biological child of ai, then we say checkpoint a is confirmed.

For a checkpoint s, we use h(s) to indicate the height of checkpoint s on the checkpoint tree. In about Casper FFG, an honest block verifier Pi should not be published two different voting ⟨ Pi that meet the following conditions: s1, t1 ⟩ and ⟨ Pi: s2, t2 ⟩ :

& have spent & have spent "H (t1) = h (t2)" or "h (s1) & lt; h (s2) & lt; h (t2) & lt; h (t1)"

● If a block verifier Pi is found to have cast two votes that meet the above criteria, his deposit will be forfeited. Buterin and Griffith proved the following properties of Casper FFG: & NBSP;

● In Casper FFG, it is impossible to identify two contradictory checkpoints at the same time. So we have achieved the security of the system

If the underlying blockchain construction mechanism can always produce the offspring of confirmed checkpoints, then the absolute majority of connection chains can always be extended to produce new confirmed checkpoints. In other words, the system is reasonably active

To keep the system alive, Buterin and Griffith recommend that the underlying blockchain construction mechanism use the fork mechanism of "correct by construction" : always extend the longest reasonable checkpoint.

Buterin and Griffith's analysis suggests that Casper FFG can prevent long-range revision attacks if users always log in to the system regularly (say, at least once a month) to get system updates and never reply to a confirmed block. Buterin and Griffith also suggest that if a block verifier does not vote for a long time, his deposit will gradually be forfeited. This prevents the tragedy of the crash (e.g., t+1 block verifier can't vote due to network fragmentation). While Casper FFG solves many of ethereum's problems, Buterin and Griffith acknowledge that network fragmentation is still an unresolved issue.

In Buterin and Griffith's article, the authors do not discuss their network model. In a synchronous network, the security of Casper FFG should be guaranteed. However, in an asynchronous network, some messages may be delayed until after GST, and some may be lost. So the security of Casper FFG in asynchronous networks needs to be carefully analyzed. In the following paragraphs, we present several scenarios for asynchronous networks. In these cases, Casper FFG is likely to be inactive (that is, Casper FFG may also be dead).

1. Assume that at time T, checkpoint a is confirmed (there is an absolute majority connection from a to its own child b) and that no block verifier has voted for checkpoint b's offspring. If an honest node vote ⟨ Pi Pi: b, c ⟩ was lost and all t a dishonest node does not vote for the offspring of b. Then no node can get enough votes. This scenario is similar to the crash scenario analyzed by Casper FFG (but slightly different).

2. Buterin and Griffith, in their paper, did not carefully analyze the conditions necessary to achieve their reasonable activity characteristics. Buterin and Griffith simply said that Casper FFG could be used on most PoW blockchains. However, if we do not add special conditions to the PoW mechanism, Casper FFG can go into a dead state (thus not achieving its reasonable activity). Suppose that at time T, checkpoint a is confirmed (there is an absolute majority connection from a to its own child b) and that no block verifier has voted for checkpoint b's offspring. Now assume that the underlying blockchain construction mechanism forks from block b. In other words, b has two checkpoint descendants c and d. If t honest block verifier votes for c, t+1 honest block verifier votes for d, and t dishonest block verifier votes at random. So from node b, no checkpoint can be identified. This results in a dead state. Because all the block verifiers are voting, Buterin and Griffith's proposed mechanism for preventing crashes and deaths doesn't address the problem here. Our analysis points out that, theoretically, Casper FFG does not prevent the system from crashing. That is, Casper FFG is inactive. In practice, however, if the check node tree is constructed in units of 100 base nodes, and the node generation rate is slow enough, then the likelihood of such an attack is low (it still exists).

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia