Free and easy week review | Is blockchain preemptive trading too rogue? Consensus algorithms introduce sequential fairness or can be cracked

Write in front:

"The martial arts in the world, but do not break fast", this phrase often appears in martial arts works.

Its derivative means that as long as one party seizes the opportunity, it can stand invincible. On Wall Street in the real world, this kind of front running (Front Running) phenomenon is common, which is like two people competing, one of them first punches the other's face, and then quickly slips away …

When looking at the financial system, the need for a fair trading order is obvious. Because of the order in which transactions are executed, the effectiveness or profitability of a given transaction can be determined. Let's say Bob has $ 0 and two transactions happen: where tx0 is Alice sending $ 5 to Bob, and tx1 is Bob sending $ 5 to Carol.

• The financial crisis is raging, and the bitcoin bull market is expected to fail?
• 15 million traffic support, 50% high dividends! Babbitt launches industry's first live Queen recruitment plan
• Viewpoints | Several possibilities for driving new development with "new infrastructure" + blockchain after the epidemic rainstorm turns overcast

If the order of tx0 is before tx1, then both transactions will be valid, and the opposite order will cause tx1 to fail.

Recent research shows that this phenomenon is also common in permissionless blockchains based on consensus algorithms. The paper by Daian et al. Mentions that the robots performed rampant adversarial operations on transactions in the Ethereum network, and then obtained more than $ 6 million in revenue from pure users.

Is there a way to crack this "rogue effort" of preemptive trading? This week's academic topic, let's share the latest research "Sequence Fairness of Byzantine Consensus" from Cornell University professor Ari Juels and others.

And in the hardcore technical article selection section, we will also see the content of blockchain activity, tBTC, sparse Merkel tree and so on.

In addition, in the past week, Bitcoin also ushered in updates to the Bitcoin Core 0.19.1 client, schnorr signature, and Taproot scheme, while Ethereum co-founder Vitalik released a new Gasper consensus protocol paper.

(Picture from: tuchong.com)

I. Aequitas protocol: Blockchain consensus requires not only consistency and activity, but also order fairness

Over the past three decades, researchers have studied the abstract concepts of state machine replication in the cryptography and distributed systems literature.

At a high level, the goal of the state machine replication protocol is to get a set of nodes to agree to a growing, linearly arranged message (transaction) log.

Such a protocol needs to satisfy two attributes: (1) Consistency: all honest nodes must have the same view of the agreed logs, that is, they must output messages in the same order; (2) liveness ( Liveness): The messages submitted by the client should be added to the log within a reasonable time. Unfortunately, neither the consistency nor the liveness describes the actual order of transactions in the final log. A protocol that ensures that all nodes agree to the same order, regardless of how they generate the order, will be considered consistent.

1.1 Sequence fairness of blockchain transactions

This leaves room for the definition, that is, the opponent may control the order, and then let all nodes agree on the result. In all existing protocols (including PBFT, FastBFT, HotStuf) that rely on the designated "leader" node, the malicious leader can choose to submit transactions in any order.

To correct this problem, Professor Ari Juels and others from Cornell University and IC3 proposed a third consensus attribute: fairness of transaction order.

Paper link: https://eprint.iacr.org/2020/269.pdf

Intuitively, sequential fairness represents the concept that if a large number of nodes accept transaction tx1 before another transaction tx2, then this should be reflected in the final order in some way.

The main contributions of this paper are threefold:

(1) Study the natural concept of fair trade sequence and explain why it is impossible to achieve;

(2) Researched the slightly weaker concept of fair order, these concepts are intuitive, but they can be realized;

(3) A new type of consensus protocol is introduced, which is called Aequitas. It implements a fair block transaction ordering and also provides consistency and activity. The researchers also discussed the synchronous and asynchronous Aequitas protocol settings;

1,2 How to Avoid the Condorcet Paradox

The nature of sequential fairness is a natural simulation of the validity of the consensus problem, which is to extend the Byzantine agreement to multiple rounds.

If all honest nodes think that transaction tx1 precedes another transaction tx2, then by a natural analogy with validity, the final output log should sort tx1 before tx2. Therefore, researchers believe that the fairness of transaction order is a natural attribute with independent theoretical benefits in the consensus literature.

Defining sequential fairness and impossible outcomes: To model consensus protocols, researchers have used an approach where protocol nodes receive transactions from clients and need to output or deliver them in a way that meets consistency and activity.

Definition 1.1 (the fairness of the receiving order is formally defined in Section 4.1 of the original paper). If enough nodes (at least γ percentage) receive the transaction tx before another transaction tx0, all honest nodes must output before tx0 tx.

Although this definition is intuitive, it turns out that this cannot be achieved unless we assume very strong synchronicity or there is no malicious counterparty.

This result comes from the surprising connection to the preferences of voters in social choice theory. To emphasize this with a simple example, we can consider three nodes A, B, and C, and then each node will receive 3 transactions x, y, and z.

Where A receives them in the order [x, y, z], B receives them in the order [y, z, x], and C receives them in the order [z, y, x].

Please note that most nodes receive (x after y), (z after y) and (x after z)! This situation is often referred to as the Condorcet paradox (also known as the voting paradox), and even if all local orders are transitive, they can lead to nontransitive global orders.

And this is problematic for the concept of reception order fairness.

Theorem 1.2 gives an informal description of impossible results.

Theorem 1.2 (the impossibility of fairness in the receiving order, the formal theorem is described in section 4.4 of the original paper). Consider a system with n nodes, where the external network (between the user and the protocol node) is asynchronous, or the maximum delay δ is at least n rounds. In this way, no agreement can achieve consistency, liveness, and fairness of the receiving order at the same time.

In view of this impossible result, the researchers considered a natural relaxation state of the fairness of the receiving order, and called it the block-order fairness. To understand the main difference between these two definitions, let's look at two transactions tx and tx ', where enough nodes have received tx before tx'. Receiving order fairness requires tx to be output before tx ', while block order fairness relaxes the condition to "before or at the same time".

This refers to transactions that are delivered simultaneously in the same "block".

Definition 1.3 (block order fairness, formally defined in section 4.7 of the original paper): If there are enough nodes (at least γ percentage) to receive transaction tx before another transaction tx ', the honest node cannot Tx is delivered in blocks.

It is this slight relaxation adjustment that allows us to avoid the Condorcet paradox with a simple technique: putting the order of contradictions in the same block. The emphasis on fairness of block order here does not mean that transactions are partially ordered. Consistency still requires that all nodes output transactions in the same order (with or without the same block). The only difference is that in the researcher's definition, as long as these transactions appear in the same block, they are considered fair.

In other words, the researchers noticed that although it is impossible to achieve fairness of the reception order, the fairness of the block order is achievable. In this regard, they proposed a protocol that can guarantee this, and called it Aequitas.

4 implementations of 1, 3 Aequitas protocol

The Aequitas protocol uses two basic primitives in a black-box manner: (1) FIFO broadcast (FIFO-BC), which is a basic extension of standard reliable broadcast; (2) Set Byzantine Consensus Protocol (Set-BA), which is defined in the original In section 3 of the paper, this can be achieved by the Byzantine consensus protocol.

Note that these are weak primitives. Any standard consensus protocol (implementing consistency and liveness) can also be used to construct FIFO-BC and Set-BA primitives. This leads to an interesting observation: Aequitas technology provides a universal compiler that can convert any standard consensus protocol into a protocol that provides sequential fairness.

In simple terms, the Aequitas protocol is divided into three main phases. Each transaction tx goes through these stages before delivery.

Phase 1 Gossip : Node gossip transactions are performed in the order they are received. That is, each node is circulating the order of its local transactions.

To this end, the researchers used the FIFO broadcast primitive (FIFO-BC). FIFO-BC guarantees that honest nodes' broadcasts are transmitted by other honest nodes in the same order as broadcasts. FIFO-BC guarantees that all honest nodes pass messages in the same order even if the sender is dishonest. As a result, nodes will have a consistent view of the transaction order of other nodes.

Phase 2 Agreement : A node should consider its local sequence of nodes when agreeing to determine the global sequence of a particular transaction.

Phase 3 Finalization : The node uses a set of local ordering determined during the agreement phase to finalize the global ordering of transaction processing.

It should be noted that the first two phases (gossip and agreement) are easy to understand and easy to implement, while the third phase is complicated because it needs to avoid the Condorcet paradox while continuing to maintain consistency and sequential fairness .

In this regard, the researchers have proposed a consensus protocol based on the leader and no leader, and then set synchronous and asynchronous settings, so there are a total of 4 protocols. These protocols all provide consistency, fairness of block order, and some degree of liveness. The following figure is the comparison result of these 4 protocols.

Free and easy comments: The idea of ​​the Aequitas agreement is simple. It is like stipulating that two people can only play at the same time. This ensures the fairness between the two sides. The theory behind it is actually very complicated. In addition, according to the paper, Aequitas provides a universal compiler that can convert any standard consensus protocol into a protocol that provides sequential fairness. If it can be achieved, this will solve a major problem facing blockchain financial applications.

Second, hard core technical articles of the week

2.1 Breakthrough of the impossible triangle of the blockchain (six)-blowing a whistle on the activity of the blockchain

In this article, maxdeath lists a series of known issues about the Lightning Network and blockchain. These are all whistle about the security of blockchain activity, and these whistle have been blown more than once. The author hopes that this time, when someone designs a system without considering these issues in the future, and someone benefits from these issues, please do not call it a hack.

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

2.2 tBTC: a new Bitcoin sidechain design

tBTC is a decentralized and guaranteed Bitcoin custody system, which issues a token called TBTC. Users do not need to trust custodians (called signers) because the value of the bonds deposited by these signers is higher than the value of the Bitcoins they host. If they are to transfer unauthorized funds, resulting in the value of outstanding TBTC being higher than the escrow bitcoin, the system will confiscate their bonds to purchase and offset the equivalent TBTC in the market and restore the TBTC and escrow bitcoin Of balance.

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

2, 3 Core developers teach you how to verify a Bitcoin client

In this article, Bitcoin Core developer Luke Dashjr explains how to ensure that the Bitcoin client that he installed is secure and unmodified by malicious parties in three steps.

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

2, 4 Science | What is a sparse Merkel tree multivalued proof

The Ethereum network is a stateful world computer. Its state includes state balance, transaction serial number (nonce), contract code, and contract storage content. Technically, these state data are organized by a structure called "Merkel Tree", so the state of the Ethereum world and its access and updates can be expressed as a Merkel tree and its access, Update. Similarly, all data verification and verification operations related to the Merkel tree can be understood as state verification and verification operations in the context of the Ethereum protocol. In fact, the Merkel tree is an integral part of our understanding, utilization and improvement of the Ethereum protocol.

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

2, 5 In addition to "halving", you need to pay attention to these Bitcoin technologies in 2020

In the past year, Bitcoin technology has achieved good development. Will that trend continue in 2020? Can MAST, Taproot, Schnorr signatures, and other great technologies further improve Bitcoin security and drive its price up?

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

Third, Bitcoin & Ethereum development update progress

3.1 Progress of Bitcoin Development Update

1. Bitcoin Core 0.19.1 client is officially released with some bug fixes, most of which involve wallet / GUI / RPC;
2. Updates to the BIP340 schnorr key and signature scheme, which will also have some impact on the BIP341 taproot. For these improvements, the author Pieter Wuille asked the community to provide feedback on the changes;
3. Proposal for a standardized leak-proof random number protocol: Stepan Snigirev initiated a discussion on the Bitcoin-Dev mailing list about a standardized protocol that prevents hardware wallets from using skewed random numbers to reveal users' private keys;
4. Taproot's security proof: Lloyd Fournier published his research at the Financial Cryptography Conference two weeks ago, which described what attributes must be present in the hash function used by Taproot to ensure the security of Taproot.
5. Lightning Network client LND 0.9.1 is released. This version does not contain any new features, but fixes multiple vulnerabilities, including those that may cause "forced shutdown between nodes."

More updates on Bitcoin's technological progress can be found here: https://bitcoinops.org/en/newsletters/2020/03/04/

3.2 Development progress of Ethereum

Ethereum 1.X updates:

1. Ethereum Foundation member Hudson Jameson: ProgPoW is not worth it, it will die;
2. The ProgPoW algorithm was exposed or could not resist ASIC;
3. Trinity v0.1.0-alpha.35 released;
4. DHT solution or solving stateless Ethereum data retrieval problem;

Ethereum 2.0 research and development update content:

1. Prysmatic client update, reducing a lot of RAM, the first slashing was successful, and it has been updated to the latest specifications;
2. Lighthouse client updated, block processing speed increased by 70%, synchronization speed was 100 blocks per second, and the amount of memory was greatly reduced;
3. Zero-knowledge proof tool for Ethereum 2.0 ewasm EE ;
4. Vitalik et al. Published a paper and proposed a new Gasper consensus protocol, which combines Casper FFG and the fork selection rule LMD GHOST, which can prove security and activity under different assumptions; (Note: Gasper is also an Ethereum 2.0 beacon chain Version to be used)

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!