On Christmas Eve, December 25th, Dr. Ming Wu, Conflux CTO, was a guest of “Mars Finance Founding Learning Group” and shared “Conflux: Using DAG structure to improve the throughput rate of Zhongben Cong Consensus”.
Guest Profile:
Conflux CTO: Dr. Ming Wu
He received his ph. D. degree in Computer System architecture from The University of Science and Technology of China, Chinese Academy of Sciences. He was a senior researcher in the System Research Group of Microsoft Research Asia (MSRA), with research interests including distributed transaction processing system, graph computing engine and artificial intelligence platform. In recent years, he has published papers in several top conferences in the field of systems (such as SOSP, OSDI, NSDI, ATC, etc.) and served as a member of the program committee of OSDI, ASPLOS, HotDep, etc.
Quick overview:
1. Based on the idea of Satoshi consensus, DAG technology transformation can greatly improve throughput efficiency without sacrificing decentralization and security.
2. Why is the throughput rate of traditional POW-based Satoshi consensus mechanism very low? In summary, it has to be for safety.
3. Security is the core requirement of public chain system. Although PoS reduces the resources consumed by mining in PoW, it also introduces many new attack situations and security threats, so there is no perfect solution at present.
Dr. Wu Ming acknowledged that some existing POW-based blockchain systems offer very low transaction throughput, which brings many problems, including poor user experience, high transaction costs, and further limits the ability to develop more meaningful applications on blockchain systems.
In this context, Conflux combines directed Acyclic graph technology (DAG) with Satoshi Consensus (bitcoin’s consensus mechanism) to improve throughput of proof-of-work (PoW) based blockchain systems without sacrificing decentralization and security.
Below are the details of Dr. Wu Ming’s live broadcast
Part ONE: Industry background
As we all know, one of the biggest problems facing the current blockchain field is the problem of efficiency. Some of the existing POW-based blockchain systems (such as Bitcoin and Ethereum) offer very low transaction throughput. Bitcoin’s maximum speed is about seven transactions per second on average, while Ethereum’s is 30 transactions per second, far below the thousands of transactions a centralized transaction service like Visa can handle.
Inefficiency brings many problems:
First, the user experience of existing blockchains is poor due to inefficiencies, such as long waits for transactions to be added to the block.
Second, transaction costs are high due to limited throughput.
Furthermore, high transaction costs limit the ability to develop more meaningful applications on blockchain systems.
In order to improve efficiency, there are the following ideas:
1. The Satoshi consensus is still adopted, but the parameters of the protocol are adjusted.
Improve efficiency by adjusting block generation time and block size. For example, litecoin (2.5min /1MB block) and BCH (10min/32MB block). However, studies have shown that no matter how these two parameters are adjusted, higher throughput inevitably comes at the expense of lower safety. In part 2, I will explain why.
2. Based on the idea of Satoshi Consensus, DAG technology is used for transformation.
This can greatly improve throughput efficiency without sacrificing decentralization and security.
3. Use PoS or dPoS.
DPoS algorithms such as EOS sacrifice decentralization to a large extent, which is not a small controversy. However, PoS algorithm also has decentralization or security problems such as equity concentration and difficulty in dealing with Long Range attacks.
4. Use side-chain or sub-chain solutions such as Sharding, State Channel, etc.
Some of them are called Layer 2 by some people. These solutions are orthogonal to the current solutions of Conflux. They try to solve the throughput rate problem from another Angle. The improvement of throughput rate can be superimposed or complementary. For example, techniques that improve throughput across all nodes can help systems that use sharding to reduce performance bottlenecks caused by cross-chain transactions and to complete more state channel settlement transactions.
Part II: Why is the consensus mechanism of Satoshi Nakamoto low throughput
Why is the throughput rate of traditional POW-based Satoshi consensus mechanism very low? In summary, it has to be for safety.
In a public chain, in order for the machines participating in the network protocol to agree on the execution of the transaction, miners need to broadcast the blocks over a P2P network so that all the machines get a consistent ledger structure. Each miner chooses to attach the newly excavated block to the end of the longest chain it sees, according to the longest chain rule. So all of the honest nodes are going to lengthen the longest main chain. Thus, it is impossible to reverse the main chain if the malevolent node does not have >50% computational power.
However, if the network latency is so large that a new block is generated before it has time to spread to the whole network, other nodes will generate another new block, resulting in a large number of forks on the blockchain.
Let’s use a picture to show what the blockchain ledger would look like after the fork.
These forks pose two problems. First, forked blocks are eventually discarded, wasting network and computing resources. Second, forking also compromises security. If a large number of blocks generated by honest nodes are discarded due to forking, an attacker needs less than 50% of the computing power to generate the longest malicious chain.
Therefore, in the currency or the etheric lane, in order to guarantee the security, they need to keep a long piece of time (i.e., low block rate), or to maintain a small size to reduce the block in the network broadcast delay, in order to reduce the frequency of bifurcation, but at the same time, thus greatly reduces the system throughput.
Increased throughput results in forks, and two blocks on different forks are competing. They compete for subsequent blocks of confirmation to make their branch the longest chain, and the loser is discarded. This senseless competition between blocks dug up by honest nodes creates an opportunity for attackers. In order to improve security, Bitcoin has chosen to slow down the block speed to avoid this situation.
So if we go the other way, by allowing each block to choose multiple blocks as its parent or ancestor, we can avoid meaningless competition between honest blocks even when blocks are produced quickly. In this way, the dilemma of safety and efficiency in The Satoshi consensus is avoided.
In this way, the whole network will form a directed acyclic graph structure (DAG). The next thing to consider is, in what order should transactions in different blocks be executed? At this time, we design a secure topological sorting algorithm of directed acyclic graph. Each node only needs to execute this algorithm once on its own local DAG to obtain the execution order of a block. This algorithm should ensure that:
· The sequence of each mining machine node should be consistent.
· This order cannot be changed even under a two-flower attack.
Later, I’ll look at how to design this secure topological sorting algorithm using Conflux as an example.
There are many DAG technologies, such as Spectre and Phantom algorithms, which are the most similar to our design ideas. Both of them use DAG Angle to optimize the efficiency of PoW chain. Unfortunately, Spectre doesn’t have the ability to sort all the blocks in order, so it can’t run smart contracts on it. We found bugs with the Phantom.
At the same time, there are some DAG based algorithms that are similar but not magical to what we’re going to talk about today, such as Avalanche consensus, Hashgraph. These algorithms are all alliance chain algorithms in essence. And through the way of “equity pledge”, the alliance chain algorithm is transformed into PoS common chain algorithm. However, there are security problems in the process of converting alliance chain into PoS public chain algorithm. Some of the more well-known attacks against PoS are nothing-at-stake attacks and long-range attacks.
Part THREE: Using PoW+DAG to improve blockchain throughput Example analysis -Conflux mechanism design
Let’s take Conflux as an example to see how the idea of using DAG to improve throughput is implemented in technical detail.
In Conflux, each block contains two kinds of edges, parent and reference edges. Parent and reference edges together form a directed acyclic graph. Remove the reference edges, and all parent edges form a tree. In mining, miners listen to blocks broadcast in P2P networks and maintain a directed acyclic graph of block ledgers locally. When miners are mining, the selection of new block parent edge and reference edge should follow the following rules:
1. Select a main chain according to Ghost rules in the tree formed by the parent side. Specifically, starting with the Creation block, iteratively select the next block on the main chain from the child block. The rule for selection is to pick the child block with the largest subtree. The parent edge of the new block should point to the last block in the main chain.
2. In addition, for blocks that have neither parent edges nor reference edges to point to, we call them “leaf blocks”, and the reference edges of the new block point to all the remaining leaf blocks.
With these edges defined, the structure of the ledger is settled, and after the blocks are broadcast, all the nodes end up with a uniformly structured directed acyclic graph, that is, a consistent ledger.
So with a consistent ledger, how do all nodes decide on a safe, consistent block ordering? The core idea is that these nodes first decide on a consistent main chain in the DAG, and then decide on a consistent block ordering based on that main chain.
Let’s use an example to see how to determine a consistent block ordering.
The main chain selection also follows the Ghost rule, which I mentioned when I was picking the parent side. We follow this rule, we select blocks C,E,H into the main chain.
According to the side selection rules we just talked about. The parent edge of the new block should point to H, with K being the leaf block. So the reference edge of the new block should point to K. (note: the reference edge of H points to G, so G is not a leaf block).
Now we have a mechanism for all the nodes to agree on the main chain. Then, how do these nodes agree on the full order of the block? To do this, we introduce the concept of Epoch. Each block on the main chain defines an Epoch. Which Epoch the block on the fork belongs to is determined by the Epoch of the first main chain block created after it. For example, block D belongs to Epoch E. Because D was first referenced by E, it was generated before E, but D was not generated before C. Following this rule, we can get a consistent ordering, as shown in the figure below.
Therefore, in Conflux, we first order the blocks according to the order of Epoch. Then, within each Epoch, we determine the order of the blocks by topological sorting. If there is a tie, we break the tie based on the block’s hash value. So the blocks in this diagram are sorted like this. Next, we will sort the transactions. Conflux first sorts the transactions according to the block order. Then, within each block, we rank the transactions according to where they are in the block.
Finally, let’s look at how the transaction can be resolved if there is duplication or conflict. Let’s use another example to illustrate:
In this example, transaction 2 conflicts with transaction 3. After transaction 2 is executed, there is not enough balance in account X to complete transaction 3. In the whole transaction sequence, transaction 3 takes place after transaction 2, so we will make transaction 3 invalid. Alternatively, the same transaction may be packaged into different concurrent blocks by different nodes, such as transaction 4. In this case, Conflux will only accept the first such transaction in the whole sequence and invalidate subsequent duplicate transactions.
Q&a:
Q1: How does Conflux compare with PoS public chain project?
A1: As we all know, security is the core requirement of a public chain system, because the public chain itself is building a trusted system. PoS reduces the amount of resources needed to mine PoW, but it also introduces many new attack scenarios and security threats, and there is no perfect solution. Some of the more well-known attacks against PoS are nothing-at-stake attacks and long-range attacks. For this reason, Conflux insists on adopting a POW-based consensus mechanism by introducing DAG technology to break the performance bottleneck of consensus mechanism. This is the actual result of our prototype test system.
Q2: How long can a deal be confirmed?
A2: 5s a 4MB block in the case of no attack by bad guys, the confirmation time is about 8 minutes. In the case of a 30% computational attack, the confirmation time is about 16 minutes.
Q3: How far can Conflux’s TPS run?
A3: When talking about and comparing TPS, we need to be careful to distinguish between experimental Settings used to test TPS. In Bitcoin, for example, every block needs to be broadcast to all miners, and every transaction is verified by everyone, which we call “full node verification” of a transaction. In some experiments of Sharding schemes, all transactions are divided into 30 pieces, and each node may validate only one of them. Such a transaction is called partial node verification. Obviously, the total TPS of a partial-node verification transaction can be multiplied by that of a full-node verification transaction.
Conflux can achieve the “all-node verification” of 4000-6000 TPS at the consensus level. The actual deployment may be lower if factors such as contract execution and state read and write are considered. Sharding technology is a good complement to the consensus layer technology, and Conflux plans to implement Sharding in the future, providing higher “partial node verification” TPS and a variety of options for users.
Q4: What is the roadmap and timeline for Conflux?
A4: We plan to test the online line after the Spring Festival, and expect to launch the main network in Q3 next year.
Q5: Will there be a coin issue in Conflux? Or mining?
A5: Conflux does not have ERC20, and there will be mining after the main network goes online.
Q6: Will PoW or mining power be involved here? And what’s the main difficulty here? What are the main technical issues facing you?
A6: Conflux is an improvement based on Satoshi Consensus. It is a PoW consensus mechanism, and of course there will be mining.
The main challenge here is to design an efficient and consistent sorting algorithm for the DAG ledger. The algorithm needs to be able to keep good people on the same page and resist complex attack scenarios.
Q7: How does Conflux prevent double-flower attacks?
A7: It’s a complicated question to answer. Let’s look at a picture first
In this figure, let’s first look at how an attacker can reverse a transaction in the ledger, such as transaction 4. To do this, an attacker needs to generate a double-flower transaction of transaction 4, package it into a block, and insert the block before block B in the block’s full order.
But this is hard for attackers to do for two main reasons. The first is that unless an attacker can change the main chain, he cannot reverse the transaction, because the order of the transaction is determined by the main chain. For example, if an attacker wanted to insert a block early, he could simply create a new block after a block inside a very early Epoch. But as long as the block is not on the main chain, it will still end up belonging to a very late Epoch. Because when an honest new block is created, it pulls the attacker’s block into the new Epoch by referring to the edge.
The second reason is that if the attacker doesn’t have more than 50% of the power, he can’t change the main chain.
Q8: Does the CTPS of Conflux have test data?
A8: CTPS refers to THE TPS for confirming a transaction. The TPS measured in our experiment is actually the TPS for confirming the transaction. About 4000~6000.
