Free and easy week review | 6 years of sword grinding, past and present of Ethereum PoS magic

Write in front:

In the coming months, in addition to the deterministic event of halving the production of Bitcoin, there is one more thing that will also become the focus of attention of the blockchain industry. For Vitalik Buterin, there are many reasons for Ethereum to switch from PoW to PoS, such as avoiding 51% attacks, saving energy, improving scalability, etc., and this plan has existed since the birth of Ethereum. It has experienced 6 years. Several versions have been improved, and the latest version has recently been ushered in- Gasper , an ideal version of the PoS consensus protocol combining Casper FFG and LMD GHOST fork selection rules, and this is the academic content to be shared this week.

In the hardcore technical article selection section, we will also see polynomial commitment schemes, anti-51% attacks, bitcoin new transaction replay logic, and more.

In addition, in the past week, Bitcoin and Ethereum have ushered in some new technological developments.

• Blockchain startup Fluree announces completion of new round of financing and announces strategic cooperation with the U.S. Air Force
• Babbitt Column | 3 Thinking Differences to Help You Better Understand Blockchain Investment
• Witness history! Bitcoin plunges sentient beings: mining circle under pressure, exchange shuffled

(Picture from: tuchong.com)

1. Gasper: Combining GHOST and Casper

Ethereum, which is growing under the PoW consensus environment, is about to usher in a new journey. Although the Proof of Stake (PoS) has high expectations, however, there has not yet been a very successful PoS system. Energy-saving and efficient PoS magic seems to still Only exists in the story.

The thoughtful Vitalik, in conjunction with Ethereum 2.0 coordinator Danny Ryan, and several researchers from San Jose State University (SJSU) jointly proposed a PoS consensus protocol called "Gasper", which is Ether Fang 2.0 The consensus version of the ideal version of the beacon chain. Researchers said that the protocol combines the final tool Casper FFG and the fork selection rule LMD GHOST, and its security and liveness have been proven under different assumptions.

Link to the original paper: https://arxiv.org/pdf/2003.03052.pdf

1.1 Introduction

The so-called Gasper is a combination of Casper FFG and LMD GHOST (fork selection rule).

The Casper FFG algorithm is responsible for marking certain blocks in the blockchain as completed so that participants with partial information can still be fully confident that the block is part of the canonical blockchain.

Casper is not a fully specified protocol, it is designed as a "gadget", and it is unknown whether the blockchain is a proof of work (PoW) or a proof of stake (PoS). LMD GHOST is a fork selection rule in which validators (participants) prove blocks to indicate support for those blocks (such as voting). Gasper is a full proof-of-stake (PoS) protocol, which is an ideal version of the protocol proposed for Ethereum PoS implementation.

Terms and goals related to Gasper

Gasper's goal is to become a proof-of-stake (PoS) protocol with some security and liveness. Before understanding it, let's get to know some background of the consensus protocol and blockchain. (Note: Because a lot of academic vocabulary is used in the thesis, the main purpose of this section is to select some specific vocabulary so that everyone can have a good understanding of Gasper)

1.2.1 Consensus protocol, validator and blockchain

For the consensus protocol, its goal is that even if the network is unreliable or many validators are malicious, a group of entities (nodes, people, etc.) can adhere to a set of recognized algorithms to obtain network status Consensus history.

We refer to the entities (people, programs, etc.) participating in the agreement as validators, and are represented by the set V Because of their data verification role in the Ethereum 2.0 beacon chain, they are called "validators". This role is not only unique to the Ethereum abstract protocol, but there are similar concepts in other blockchains (just Different terms are used), such as "copy" in classic PBFT literature, "block producers" in DPoS and EOS, "peer nodes" in PeerCoin and NXT, or "brakers" in Tezos ( baker).

Validators are interconnected in a peer-to-peer network, which means they can broadcast messages (basically packets) to each other.

The first block of the network, we call it the founding block, and use it as the initial "blank board" state. The other blocks are descriptions of state transitions with pointers to the parent blocks. The blockchain is the instantiation of the consensus protocol (that is, with specific network conditions, validators, etc.), in which we use blocks to build the entire state.

However, we do not want all blocks appearing on the network to be accepted as public history, as conflicts between blocks may occur. These conflicts can be caused by honest reasons (such as network delays) or malicious reasons (such as Byzantine validators wanting to spend double transactions). Byzantium here refers to a classic problem in distributed systems-the Byzantine General problem (this term is used to describe the verifier that does not follow the protocol), and the possible reasons are that the verifier is malicious, or they Experiencing network latency. In theory, one can think of the choice of history as the choice of a "chain" from the founding block to a specific block, which is why we call the instantiation of this protocol a "blockchain."

1.2.2 Information and Views

In the Gasper model, the verifier V interacts with the network by broadcasting messages (strings of a certain language). When the honest verifier V broadcasts the message M , we assume that M is sent to all verifiers on the network.

The main type of message proposes a data block to the network. Other messages can be accounting notifications, such as voting for a block ("proof"), setting up a new validator ("activation") on the blockchain, and proving other validators. There are erroneous operations ("penalties"), etc., depending on the specific protocol. We assume that each message is digitally signed by a verifier, which means that we can accurately track the author of each message, and attacks like impersonating an honest verifier are not possible.

Because there may be network delays and malicious verifiers (that is, delaying messages or forwarding incorrect information), the verifiers may have different cognitive states for the full set of messages provided to the network. Each message may have one or more dependencies, and each dependency is another message. At any time, as long as all dependencies of a message are accepted and recursively defined, we accept the message. Now, we define the view of the verifier V at a given time T as view(V, T) , which is the set of all accepted messages that the verifier has seen so far. We also have an "Eye of God view", which we call a network view, which is defined as a set of messages that are assumed to be accepted by a validator who can see all messages broadcast by any validator at any time (including malicious verification) Messages sent by the author to a subset of the network).

We see the network as a "virtual validator", so we use view(NW, T) to represent the network view at time T For any validator V and any given time T , view（NW，T） includes all messages in view(V, T) , although timestamps may not match.

Figure 1: Visualization of the view (only blocks are visualized, no other messages are included)

As shown in the figure above, the blocks in the view form a tree, where blocks C and D are in conflict (E blocks and D blocks also conflict), and E has the longest chain, that is, 链（E）=(B genesis, A, B, C, E) .

1.2.3 Proof-of-stake

The first and most influential implementation of the blockchain protocol is Bitcoin, which uses the Proof-of-Work (PoW) model. This method uses a simple and intuitive fork selection rule, that is, miners (Similar to the validator) will choose to build the block on the heaviest chain (the chain with the most computational workload). This does not mathematically guarantee that any non-originating block is "correct", but it provides a probability Guarantee, because once other miners build blocks on top of it, it becomes less and less likely to conflict with the block. In other words, the consensus history of the PoW blockchain is the chain with the largest workload. Ideally, the blockchain will continue to grow.

In this article, we are discussing a proof-of-stake (PoS) blockchain, in which the validator's voting rights are directly proportional to their equity (or funds) pledged in the system. Compared to PoW's use of computing power to propose blocks, PoS proposed blocks are essentially free.

However, this also brings other challenges to the design of the PoS system. We need an extra layer of mathematical theory to prevent improper incentives generated when the block proposal becomes "easy". Now, we will shift the focus to design A series of considerations that Proof-of-Stake (PoS) blockchains need to consider.

First, suppose we have a set of N validators V = {V1, . . . , VN } , and each validator V ∈ V has a certain amount of pledged interest w(V ) . We further assume that the average amount of equity held by each validator is 1 unit, so the sum of total equity held is N. We assume that the size of the verifier set and the number of pledges is fixed in order to focus on the theoretical points of the agreement.

The main components we need are:

1. Fork selection rule: When given a view G, the fork selection rule will identify a single cotyledon block B. This selection results in a unique canonical chain; in view G, block B is called the head of the blockchain. Intuitively, the fork selection rule tells the verifier a "rule" and lets them To follow what is the "correct" block. For example, the longest chain rule is also a fork selection rule, which returns the cotyledon block farthest from the founding block. This rule is similar to the "heaviest chain rule" used by Bitcoin.
2. The concept of finality: formally, a certain function F , when given a view G , returns a set of completed block sets F(G) . Intuitively speaking, the finalized block refers to "a part of the consensus history" or "the content determined by the blockchain" that everyone finally agrees with.
3. Slashing conditions: These conditions are meaningless to honest verifiers, because they will not be violated, and verifiers who violate them will be seized, and then their pledged rights will be punished or even destroyed. The penalty condition motivates the verifier to comply with the agreement (for example, the agreement can reward honest verifiers to catch dishonest verifiers who violate the conditions).

The key concept we use to define these components is attestation , which is essentially a vote (embedded in a message) to determine which block should be the head of the blockchain.

In order to prevent the verifier from double voting or voting in a way that undermines the agreement, Gasper enforces the use of a forfeiture condition that can be used to destroy the verifier's pledged interest to motivate the verifier to comply with the agreement.

Figure 2: An ideal view with both blocks and attestation

As shown in the figure above, we can see an idealized version of the PoS protocol. In each time period, a new block is created, where the parent block is the last head of the chain (ideally, this is only the last created One block), and validators in the respective committees have perfectly proven the new block. In less-than-ideal situations, blocks may be forked, we may lack attestation, etc. Attestation will work by helping the verifier determine the correct chain head.

1.2.4 Byzantine validators and PBFT

In the protocol, if the verifier follows the protocol, we call it an honest verifier, otherwise it is called a Byzantine verifier. We usually strictly assume that less than 1/3 of the validators are Byzantine. This constant can be traced back to the practical Byzantine fault tolerance (PBFT) protocol, as long as the system has less than 1/3 copies (synonymous with Gasper's validators) is Byzantine, PBFT can ensure that the system operates correctly. In many PBFT-based protocols, this kind of 1/3 fault tolerance is common (the main idea is the pigeonhole principle), and Casper FFG is the most directly related to the Gasper protocol.

The most important aspect of PBFT is that it works under asynchronous conditions, which means that we have no limit on the time to receive messages. Therefore, PBFT is very suitable for blockchain and cryptocurrencies.

1.2.5 Safety and Liveness

The ultimate goal of honest validators is to develop a final chain in which all blocks form a "logically consistent" state transition with each other (although validators may go offline, suffer latency issues, or maliciously propose conflicting state changes). And this translates into two desired attributes:

1. Security : The goal is that the final block set F (G) of any view G can never contain two conflicting blocks. One result that has security is that any final block F (G) of the verifier view G can be "completed" as the sole F（view(NW)） of F（view(NW)） , which starts from the founding block and ends with the last The end of the completion block is what we call the finalized chain.
2. Liveness : It is finally determined that the block set can actually grow. There are different ways to define liveness. In this article, we say that the protocol has: (1) Plausible liveness , which refers to a new block regardless of what happened before (attack, delay, etc.) It is always possible to be finalized (or impossible to fall into a "stalemate"). This is to prevent honest verifiers from continuing unless someone loses their own pledge rights. (2) Probabilistic liveness . If no previous events are considered, new blocks are likely to be finalized (once we make some probabilistic assumptions about network delay, attacker capabilities, etc.).

At first glance, the latter seems to include the former, but the situation is more subtle. The former is about the purely non-probabilistic nature of protocol logic, while the latter requires assumptions about the implementation context to ensure that the protocol "generally works as expected". (Note: For further comparison between the two, the reader can see section 7.3 of the original paper)

1.2.6 Time and Epoch Period

In Gasper's model, there is a concept of time called slots. Each slot represents a constant number of seconds (for example, 12 seconds set by the Ethereum 2.0 phase 0 specification). Then we define some constant C as One epoch period (tentatively set to 64 slots). The main purpose of the Epoch cycle is to divide time into fragments. The boundary between them can be considered as a "checkpoint", which allows the use of concepts in Casper FFG, as we will see below.

1, 3 main components (Casper FFG + LMD GHOST fork selection rules)

1.3.1 Casper FFG

Vitalik and Griffith proposed Casper FFG, a tool designed to handle a wide range of blockchain protocols with a tree structure.

1. Each block has a height, which is defined by their distance from the founding block (a block with a height of 0), that is, the height of block B is equal to the length of chain (B) -1;
2. We define the checkpoint block as a block with a constant multiple of H (in Casper FFG, H = 100). We define the checkpoint height h (B) of the checkpoint block B as the height of B divided by H, where H Always an integer. Therefore, we can consider a subset of the checkpoints in the view as a subtree, which contains only blocks with a height multiple of H;
3. A proof (Attestation) is a signed message containing "checkpoint edge" A → B, where A and B are checkpoint blocks. We can think of each such proof as a "vote" from block A to block B. Each certificate (Attestation) has weight, which is the pledged interest of the verifier to write the certificate.

In addition, Casper FFG introduces the concepts of justification and finalization, which are similar to the concepts of stages in the PBFT literature, such as prepare and commit.

Finally, Casper introduced a penalty condition, an assumption about honest verifiers. When the verifier V breaks this rule, another verifier W can punish V by providing proof that V violates the conditions (destroying V's pledged interest and possibly getting some kind of "forfeiture reward").

1.3.2 LMD GHOST fork selection rules

The greedy heaviest observation subtree rule (GHOST) is a fork selection rule proposed by Sompolinsky and Zohar. Intuitively, GHOST is a greedy algorithm that grows the blockchain on the "most active" branch. And when Vlad Zamfir explored the Casper CBC consensus protocol, he introduced a naturally adapted version of GHOST, which happens to be very suitable for the setup of Gasper. We call this variant the latest news-driven greedy heaviest observation subtree (LMD GHOST).

The idea of ​​LMD GHOST is that in any fork, we use the weight of the fork to create the subtree as a heuristic, and assume that the subtree with the largest weight is the "correct" subtree, which defines a canonical chain.

Figure 3: Example of LMD-GHOST fork selection rule

As shown in the figure above, the number in each block B represents the weight (calculated by the pledge amount). In this example, the weight of all proofs (circles) is 1. Validators using this view will treat the blue chain as the canonical chain and output the latest blue block (weight 3) on the left as the head of the chain.

1, 4 consensus protocol Gasper

Next, let's formally recognize Gasper, the consensus protocol that Ethereum will adopt. It is a combination of GHOST and Casper FFG ideas. Its main concepts are:

1. Epoch boundary pair : Given a chain, pick out certain blocks, and ideally each Epoch has a pair to play the role of Casper checkpoint. However, a block may appear more than once as a checkpoint on the same chain (this is where Gasper and Casper differ), so we use an ordered pair (B, j) to disambiguate, where B is a block, And j is an epoch. These will be called epoch bound pairs, or pairs for short;
2. Committee : At each epoch cycle, validators are assigned to committees. In each slot cycle, one of the validators from the designated committee proposes a block. All validator members of the committee will then use the HLMD GHOST fork selection rule (a modified version of LMD GHOST) to prove the head of the chain they see.
3. Justification and Finalization : These concepts are actually the same as the concepts of Casper FFG, except that the pair is used here instead of justifying and finalizing the checkpoint block.

1.4.1 Hybrid LMD GHOST Fork Selection Rule (HLMD)

Since the final design is quite complex at first glance, we first introduce a "prototype" version of HLMD . Simply put, it starts with the last defense block in the view and then runs LMD GHOST.

However, there are some subtle problems with using this prototype, because the "FFG part" of the attestation is a vote between epoch bound pairs, and LJ (B) only depends on ffgview (B), we can think of " The last defense pair in the chain is "frozen" at the beginning of each epoch period, which is not in harmony with the "non-frozen" (BJ, j), because the definition of the latter changes during an epoch period. Therefore, we need a (BJ, j) version that does not change during an epoch.

Another problem occurs when the algorithm forks: Forked blocks can have completely different final defense pairs, even if they are adjacent to each other.

To solve these problems, Gasper's final solution is as follows:

1.4.2 Penalty conditions

The penalty condition in Gasper is similar to the penalty condition in Casper.

Condition 1 : No verifier makes two different proofs α1 and α2 with ep(α1) = ep(α2) . Note: This condition is equivalent to o aep (LE (α1)) = aep (LE (α2)) ;

Condition 2 : No verifier makes two different proofs α1 and α2 with aep (LJ (α1)) < aep (LJ (α2)) < aep (LE (α2)) < aep (LE (α1)) ;

This makes the protocol a very useful property: unless we are in an unlikely situation where we have enough evidence to punish the verifier with at least 1/3 of the total pledge, in a view G we can Assume that all elements in J (G) have a unique proof epoch.

1.4.1 Rewards and penalties

A validator should include a valid proof in its proposed block, or prove the defense block and finalize the block. Both should be rewarded. The former is called the sponsor reward, and the latter is called the prover reward. (Attester reward).

At the same time, if a verifier violates the forfeiture condition, it should be punished (reduction of the pledge).

The rewards and penalties can be adjusted according to the level of security that needs to be achieved.In addition, more complex incentive mechanisms are also worth considering, such as motivating verifiers to capture other misbehaving verifiers. For the sake of simplicity, we assume that these reward and punishment mechanisms provide sufficient incentives to abstract this analysis into:

1. Honest verifiers follow the agreement;
2. Any honest verifier who observes violations of the forfeiture condition can punish those violators;

(This article has omitted the proof of the security and activity properties of the Gasper consensus protocol. Interested readers can read the original paper.)

1, 5 Summary

Vitalik et al. Proposed an abstract Gasper consensus protocol for a Proof-of-Stake (PoS) -based blockchain, which combines the LMD GHOST fork selection rule and the concept of Casper FFG. This is the first step in the Casper FFG concept to complete a blockchain protocol. A formal certificate.

The goal of this design is guided by a balance between simplicity and practicality, while taking into account safety and activity.

Free and easy comments: Although Gasper is called by Vitalik and others as the ideal version of the PoS consensus protocol, the expected launch time of Ethereum 2.0 Phase 0 is very close, so whether it will be adopted in the short term is still unknown. It remains to be seen whether this PoS magic is really effective or not.

Second, hard core technical articles of the week

2.1 Vitalik: Ethereum state explosion problem, polynomial commitment scheme can solve

In order to deal with the state explosion problem of Ethereum, Vitalik, the co-founder of Ethereum, proposed a new solution, which proposed to replace the Merkle tree with a polynomial commitments scheme, thereby greatly reducing stateless ether. Witnesses of the client.

Article link: https://www.8btc.com/article/567865

2.2 Anti-51% Attack: Harvard MIT Scholars Propose New Theory of Fighting Double Spend

In the history of the blockchain world, 51% attacks have occurred many times, and they all happened on small currencies. According to researchers at Harvard University and MIT, they also saw in the 40 reorganization attacks they observed. A possible counter-attack case. In February 2020, multiple rounds of attacks between attackers and defenders appeared on the Bitcoin Gold blockchain. In response, researchers proposed a counter-attack theory to defend against 51% attacks.

Article link: https://www.8btc.com/article/568133

New developments have been made in Bitcoin development. Core developers propose to modify the logic of Bitcoin transaction replay to better transaction privacy.

Bitcoin Core developer Amiti Uttarwar is working on modifying Bitcoin's network replay logic to introduce more privacy during the transaction replay process.

Article link: https://www.8btc.com/article/569463

2, 4 dry goods | Programming Xiaobai simulates a simple bitcoin system, taking you to write a wave (with code)

If there is a p2p demo, how can we apply it to the blockchain? Author VV Yixiao ヽ provided a tutorial.

Article link: https://www.8btc.com/media/567921

Third, Bitcoin & Ethereum development update progress

3.1 Progress of Bitcoin Development Update

1. Pieter Wuille posted an email on the Bitcoin Developers mailing list outlining a technique to prevent hardware wallets or other offline signing devices from passing confidential information to third parties by using nonce in ECDSA or schnorr signatures;
2. Karl Johan Alm, author of BIP322 , noted that in the past few months, the PR he added for the general signmessage protocol has not made any progress in terms of consolidation. If the wallet developer wants to enable this feature for P2SH, P2WPKH, P2WSH and P2TR addresses activated in the future (waiting for taproot to land), we recommend that they check Alm's email and provide relevant feedback;

3.2 Development progress of Ethereum

Ethereum 1.X updates:

1. Research on Hextree to Binary Tree Conversion ;
2. A summary of stateless Ethereum client development after the EthCC meeting;

Ethereum 2.0 research and development update content:

1. Release v0.11 of phase 0 specification;
2. Nimbus client update to discuss limitations of running Ethereum 2.0 client on mobile devices;
3. Research post on phase 2: (1) evaluation of non-sequential receipt and cross-shard transactions , (2) and atomic cross-shard function calls using system events, real-time parameter checking, and contract locking ;
4. Vitalik proposes using a polynomial commitment scheme, although it is unlikely to be included in the Ethereum roadmap in the short term;

That's it for this issue, see you next week ~

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