How efficient is Algorand's bandwidth utilization? How about Cardano’s Ouroboros? Why can Solana and NKN have such high TPS? Ethereum has shortened the block interval to 15 seconds, why is it not much higher than Bitcoin throughput?

Dr. Zhang Ren will answer these questions one by one in the sharing. The following is the transcript of Dr. Ren's speech.

Reading this article has certain requirements for the reader's basic knowledge of blockchain:

• The basic concept of the Bitcoin consensus protocol (that is, Nakamoto Consensus)

• Basic Concepts of Ethereum Consensus Protocol

• Orphan block, uncle block, selfish mining and other concepts

Video link:

Video link:https://v.qq.com/x/page/g0837...

Let me introduce myself. I am Zhang Ren, a researcher at Nervos & Cryptape. I am currently a Ph.D student at COSIC (Computer Security and Industrial Cryptography group) at KU Leuven, under the tutelage of Bart Preneel. If you're not familiar with COSIC, I wonder if you've heard of AES, the encryption standard used in all of our cell phones.

Of course, if you are familiar with Bart Preneel, you will know that he is the designer of RIPEMD 160. RIPEMD 160 is the hash algorithm used when converting a Bitcoin public key into a Bitcoin address.

Nervos CKB is a public chain that can support smart contracts in various programming languages ​​and various Layer 2 protocols. On Nervos CKB, you can use any asset to pay transaction fees. The execution and verification of smart contracts in Nervos CKB are separated to achieve better privacy and performance. Finally, NC-Max—a variant of Nakamoto Consensus—is adopted in Nervos CKB as a consensus protocol with higher throughput.

Disclaimer: This sharing content only focuses on the analysis of Layer 1 consensus protocols, and I will not talk about Layer 2 solutions such as Lightning Network.

secondary title

Why do we love Bitcoin's NC?

Let’s answer a question first, why do we like Bitcoin’s Nakamoto Consensus (NC)?

There are many reasons. First of all, the performance optimization of NC is very good. It can save every byte of every transmission and every calculation cycle. For example, it uses Compact Block to speed up block propagation, and may in the future use Minisketch (a software library used to reduce bandwidth requirements when synchronizing information between different nodes in a distributed system) to save transaction broadcasting. bandwidth resources. At the same time, the developers of Bitcoin proposed Graftroot (a proposal related to the development of smart contracts and privacy on Bitcoin). You can think that it can obtain better privacy and better security by compressing smart contracts on Bitcoin. performance. Perhaps we can also see Signature Aggregation applied to Bitcoin.

Knowledge point: Compact Block Relay, proposed in Bitcoin Improvement Protocol (BIP) 152, can reduce the amount of bandwidth required for P2P network nodes to broadcast blocks.
Compact block is the "summary" of the complete block, including the following three parts of information:
1. The block header of the new block
2. Transaction ID
3. The complete transaction predicted by the sending node but not available to the receiving node
The receiver tries to reconstruct the full block based on the information received and the transactions in its mempool. If some transactions are still missing, it will request the broadcast node.

Another reason to like NC is its versatility. The UTXO model plus the global transaction order can support various sharding technologies and Layer 2 schemes, as well as complex smart contracts.

In comparison, Ethereum's Account model is more difficult to shard; and if you do not have a global transaction order, such as many DAG-type protocols, then it is difficult to support complex smart contracts. This part will It will be described in detail when talking about DAG later.

We also like the security of Bitcoin NC. The Bitcoin network has experienced many attacks and has been running stably for ten years. And strictly speaking, there is currently no known proof-of-work consensus mechanism that surpasses NC as a whole. If you are interested in this topic, you can seehere.

secondary title

Where do we need to change for NC?

As noted in the study above, Bitcoin IPv4 nodes connected to the network had a median bandwidth of 33Mbit/s in 2016 and 56Mbit/s in February 2017.

The improvement method that we can easily think of is whether the protocol itself can dynamically adjust the throughput to adapt to the change of the bandwidth level?

Bitcoin Unlimited made a poor attempt to dynamically adjust the throughput of Bitcoin, but it failed and introduced multiple new attack vectors to make its protocol insecure. The above is a study on the security of Bitcoin Unlimited published on Coindesk (link:https://www.coindesk.com/etf-...), and I was also one of the participants in this study.

Another thing we hope to change in NC is its incentive problem, that is, the problem of selfish mining attacks. Selfish mining attackers withhold discovered blocks in hopes of gaining a bigger lead in the network. When other honest miners discover the block, the attacker will broadcast the withheld block to the network, hoping that the broadcasted withheld block will be received by most honest miners before the honest block. If the attacker is lucky enough that the next block is mined on top of the attacker's block, the honest block will be orphaned. If the attacker is lucky enough to mine multiple blocks in a row, it will be very safe to invalidate an honest miner's block because the attacker will have a longer chain.

Why is selfish mining profitable? Let's take a specific example, assuming that selfish mining attackers have 30% of the computing power of the entire network, and honest miners control the remaining 70%. If there is no selfish mining attack, then the attacker can find 3 out of 10 blocks, the honest miners can find 7, and everyone gets their due rewards. If the attacker launches a selfish mining attack, then it can find 3 blocks, and honest miners can only find 4 blocks, because the blocks found by the other 3 honest miners have become orphan blocks through the aforementioned attack method , the time when 10 blocks could have been generated is now only 7 blocks, and the growth rate of the main chain has slowed down.

secondary title

Other Alternative Consensus Protocols

So why don't we choose other alternative consensus protocols?

There are currently three ways to replace NC, they are PoS (Proof of Stake, proof of rights and interests), DAG and consensus protocols of two types of blocks. Note that these three methods are not mutually exclusive, it is possible to apply 2-3 of them at the same time. Below we further analyze the security, functionality, and throughput of these protocols.

The first is PoS, and virtually all PoS protocols introduce new security premise. Taking Algorand as an example, it requires that messages sent by most honest users can be received by most other honest users within a known time range. This means that when you hold Algorand Token, according to the original design of the protocol, you need to stay online at all times to receive messages. If you are not online you are not a qualified Token holder.

Cardano's consensus protocol, Ouroboros, assumes that all users have a weakly synchronized clock and that all messages can be delivered within a certain time interval. This actually makes a very strong assumption. There are many attacks that can skew the clock on your mining rig, your public node, or your phone. And this solution is very difficult to implement in the real environment.

In addition, Sleepy Protocol also requires users to have roughly synchronized clocks.

When these security assumptions are violated, it can have disastrous consequences for these PoS protocols. And the PoS protocol introduces some new attack methods, such as Nothing-at-stake Attack, Grinding Attack, Long-range Attack, these attack methods do not exist in the PoW protocol, and I will not describe these attack methods in detail here.

So what about the DAG protocol?

All DAG protocols have transaction ordering problems. If blocks are generated synchronously like in the DAG protocol, then different miners or different public nodes will have inconsistent judgments on the order of transactions: I think some transactions are confirmed, but others A human might consider another set of transactions to be confirmed. At this time, you will have two ways of thinking about solving the problem.

One is to sort the transactions after the topological sorting of the blockchain is completed, which means you need to wait a long time for transaction confirmation.

The other is not to confirm the order of transactions. The input of the contract requires a global transaction sequence. If the transaction sequence judged by different miners is different, then each miner has a different understanding of the contract logic execution sequence, especially for complex contracts. This will limit the functionality of the contract, complex contracts cannot be executed, and the Token contained in the contract will be stuck in the contract.

What about those protocols that have two block types? The two-block type protocol, as the name suggests, uses a key block (Key Block) that is the same as the block in NC to ensure the security of transaction confirmation, and broadcasts micro-blocks between two key blocks ( Micro Block) to improve throughput.

These protocols usually have long confirmation delays like DAG protocols. Bitcoin NG adopts the above scheme. It is clearly stated in the Bitcoin NG paper that if users need to ensure transaction confirmation, in Bitcoin NG they need to wait for the confirmation of several key blocks and endure a long transaction delay.

(In the process of sharing, Zhang Ren mentioned that Byzcoin also has a similar problem. However, after further analysis, the problem is not similar. If you are interested in Byzcoin, you can go to the forum:https://talk.nervos.org/t/ner...secondary title

Claimed TPS?

All the projects adopting these alternative consensus protocols claim that they have high throughput, so what is the throughput of these projects? (The following section is recommended to watch the video, at about 15:30, the scene is very exciting)

Solana claims to be able to process 710,000 transactions per second. If you can make such a big breakthrough, you deserve the Turing Award. I can't wait to hear about their awards.

There is also this protocol called NKN, they claim that they can process 1 million transactions per second while having 10,000 nodes in the whole network, I don't know how they do it yet, but I am very impressed with the way they achieve it curious.

I am also curious why Stellar and Ripple also classify their protocols as NC, and I am also very curious about how 10,000 nodes can process 1 million transactions per second.

And if you're going to have a dream, you'd better have a big dream, like this agreement. It claims to be able to have 10000000000000TPS with a final confirmation time of less than 1 second.

Well, I really think the earth is not big enough for them, they really need to find another bigger Odaily to deploy their protocol.

We should note that the self-proclaimed TPS is not comparable. Because they are simulated in different network environments, some simulations even use a bandwidth of 1Gbit/s, which is obviously far from the real network situation.

And these agreements ignore the real situation. None of them allow for synchronization of transactions. For them, it seems that all transactions are already synchronized in the block, and the consensus protocol is only used to sort transactions. And some simulations assume that there is a direct connection between committee members (nodes), but the fact is that all messages in the public chain network are carried out by broadcasting, and broadcasting messages will occupy the bandwidth of public nodes.

secondary title

Simple Model for Comparing Throughput

Here we have a model for evaluating TPS. As shown in the figure, first of all, we believe that the bandwidth of all public nodes has an upper limit, at most 100% of the bandwidth can be used, and you cannot use more than 100% of the bandwidth. There are three components to the bandwidth usage here.

As shown in the figure above, the first part is the proportion of bandwidth occupied by transactions used for synchronous final confirmation, and this part is the real TPS (This is the real TPS). The transaction must first be synchronized before the transaction can be confirmed. The second part is the fraction of bandwidth that is "wasted" by the consensus protocol. The third part is unutilized bandwidth.

So if you want to improve TPS, there are only two things you can do.

1. Reduce the proportion of bandwidth occupied by the consensus protocol
2. Reduce the proportion of unused bandwidth

There are only these two things that can be done, yes, there is no other way, and the protocol bandwidth occupation of Layer 1 cannot exceed 100%.

Then let's take a look at the bandwidth usage of other alternative consensus protocols.

In fact, many protocols waste their precious bandwidth resources communicating between committee members.

Algorand stores block certificates to prove to new users that a block was committed. The size of each block certificate is 300KB, independent of the block size limit. If you calculate by a block size of 1MB, then this means that about 25% of the bandwidth will always be used to synchronize these certificates. So I'm very curious why they claim that their throughput is better than NC, which doesn't make sense at all.

Another way to waste bandwidth in consensus protocols is redundant transactions in block DAGs and orphan blocks. As mentioned in the paper above, if all nodes choose to include the same set of sub-transactions in the block, any two blocks created in parallel may conflict, and the throughput will not be very high.

secondary title

How to break through the dilemma of Satoshi Nakamoto consensus?

From the above analysis, it is obvious that the current throughput cannot satisfy us. Therefore, the consensus protocol NC-Max of Nervos CKB has made some improvements to NC:

NC-Max has three main innovations

Use two-step transaction confirmation to reduce the orphan block rate
Dynamically adjust block intervals and block rewards to better improve bandwidth utilization
Consider all blocks in the cycle when adjusting the difficulty to resist selfish mining attacks.

I will explain in detail next.

NC has a natural throughput limit, because there are only two things you can do to increase the throughput in NC:

The first thing is bigger blocks, like Bitcoin Unlimited and Bitcoin Cash, and many other projects do the same;

The second is to reduce the block interval.

However, since block broadcasting takes time, if other nodes discover the block and broadcast it during the broadcast, it will compete with the block being broadcast, and one of them will become an orphan block. Larger blocks will take longer to broadcast, and reducing the block interval actually reduces the difficulty of block generation, making it easier for nodes to discover blocks. The result of these two schemes is that the orphan block rate becomes higher. These orphan blocks take up more bandwidth, but they do not contribute to transaction confirmation. When the orphan block rate increases, the security of the system decreases and the throughput decreases. Therefore, these two schemes will eventually reach a balance. When the block size or block interval is adjusted to a certain level, the orphan block rate will be high to a certain extent. Even if you further increase the block size or reduce the block interval, the throughput Nor will it be improved.

Why would having too many orphan blocks negatively impact the security and performance of the network? In the figure above, we can see that when the orphan block rate is very high, the attacker can easily build a longer chain privately. An attacker only needs to have a computing power much lower than 51% of the total network computing power to overwrite the blockchain. And orphan blocks will consume a large amount of bandwidth of public nodes, which will have a great negative impact on the throughput of the entire system.

So how do we break the limitation of NC throughput? After the above analysis, if we want to break this limitation, we must reduce the orphan block rate. If the orphan block rate goes down, both the security and throughput of the network can be improved.

How to reduce the orphan block rate? The emergence of orphaned blocks is due to the delay of block broadcasting. If another block is discovered during the broadcasting of a block, one of the blocks is destined to become an orphaned block. If the block broadcast can be completed instantly, there will naturally be no orphan blocks. So how do we ensure that blocks are broadcasted fast enough?

Bitcoin developers have invested a lot of resources and energy to speed up the broadcast speed of blocks, and we need to further find out which blocks are slow to broadcast or have problems.

Let's see how this happens in detail, see the image below.

In the current Bitcoin network, if all goes well, a block is broadcast through a Compact Block relay protocol.

In the Compact Block, the entire transaction (about 250 Bytes per transaction in Bitcoin) is not broadcast, but the transaction ID in the Compact Block is broadcast. These transaction IDs form a Compact Block, which is much smaller than the actual block, so the speed will be much faster.

When node A broadcasts the Compact Block to node B, node B checks these transaction IDs. If none of these transactions are Fresh Transactions for node B (that is, the transaction pool of node B contains these transactions), node B can immediately forward these Compact Blocks. Block to adjacent nodes, this situation is very good, the process is very smooth.

However, if there is a Fresh Transaction in the Compact Block, node B will first need to synchronize the Fresh Transaction from node A, and then verify the signatures of these transactions. These steps are very time-consuming. Node B can continue broadcasting the block only after the entire block has been verified to be correct. This process prevents the received block from being illegal, so that miners will mine and broadcast after this block. If it is not verified and found to be an illegal block, then the blocks after this illegal block will be invalid. of. The process of synchronizing Fresh Transaction is the main reason for the delay of Bitcoin block broadcast.

So, Ethereum was a poor attempt, let me analyze how they did it. Ethereum simply shortens the block interval, but Ethereum has a problem that it cannot verify the validity of transactions before receiving a block. Because the validity of a transaction in Ethereum depends on the order of transactions in the block, so if you want to verify the validity of a transaction you have to wait until the entire block is received, so that each block actually All of them are Fresh Transaction.

And Ethereum's network protocol is very poorly maintained, and there has been no iteration since 2015.

And there is also a lot of redundancy in the transaction broadcasting process. The Ethereum client will broadcast the same transaction 7 times to different nodes, which means that each node will receive the same transaction 7 times. (Ethereum has different clients, such as Parity Ethereum, Geth, etc.) And there are inconsistencies between different types of clients, and the two main Ethereum clients are basically independent.

Therefore, there are very few nodes that can link two different networks, which is why the orphan block rate of Ethereum is sometimes as high as 30%, and the transaction throughput is very low.

And big miners have no incentive to speed up block broadcasting. Because if my blocks can be broadcast more slowly, it means that I can actually achieve "selfish mining" (here, the big miners do not withhold blocks, but the block broadcast is slower, and other miners appear in the process. Competing blocks, and because I am a big miner, I have a higher probability of winning in the process of competing with other competing blocks). This is a good thing for me, why should I speed up block broadcasting?

Uncle block rewards in Ethereum don’t help either, since miners are still rewarded for orphaned blocks. Therefore, small miners will adopt the method of broadcasting block headers and empty blocks first, because the speed of broadcasting block headers will be much faster. And since they don't know which transactions will be included in the next block, miners usually mine an empty block to ensure that the block does not contain transactions that conflict with previous block transactions. This is very bad because empty blocks do not contribute to transaction confirmation.

Below is our design to alleviate some of the problems mentioned above.

This picture is the block structure, we have added several fields on the basis of the Bitcoin block structure.

The above picture is the block structure of our complete block. First we have a transaction proposal area (teal area). Only the transaction proposal area can contain Fresh Transaction, while the traditional transaction confirmation area (orange area) can only contain transactions in the transaction proposal area of ​​the previous few blocks. If the current block height is h, then it is hm to hn blocks Transactions within the transaction proposal area of ​​. Only these transactions can be confirmed, Fresh Transaction cannot be confirmed by the transaction confirmation area. The transaction proposal area does not contain complete transactions, only the transaction ID (Truncated Transaction ID), so the transaction proposal area will be very small.

Any number of uncle blocks (purple area) can be contained in the uncle block header area, and the uncle blocks should contain their block headers and transaction proposal areas. The uncle block header area is not counted in the block size, so it is not limited by the block size, so miners will not be restricted from adding uncle blocks.

Let me further explain the transaction proposal area. This area is very small as it only contains the transaction ID. The complete transaction is broadcast synchronously with the block, because this is a parallel process, so the broadcast of the transaction will not affect the broadcast of the block. And the node only needs to verify the hash after receiving the broadcasted transaction, which will not affect the verification process of the block.

Although this means that there may be invalid transactions in the transaction proposal area, double-spend transactions, and transactions that miners may not accept, it does not matter.

Analogous to the Bitcoin block broadcast process mentioned above, in our protocol, the node that discovers the block will first broadcast the Compact Block (that is, the block header and the ID of the transaction). The Compact Block is slightly larger than Bitcoin, including The transaction proposal area and block headers of several uncle blocks and the transaction proposal area of ​​uncle blocks. However, since the Compact Block itself is small enough, it is usually broadcast to adjacent nodes immediately.

If some of the newly proposed transactions are not in the transaction pool of the node, they will be broadcast after issuing the Compact Block. These are parallel processes and do not affect each other. The node receives the transaction and broadcasts it to adjacent nodes after hash verification.

This naturally raises several questions:

What if the miner refuses to provide the full version of the proposed transaction?
I put this deal in my deal proposal section, but when you asked me for the full deal, I pretended not to know.

In fact, this will not affect the block broadcast, because the block can be broadcast regardless of whether there is a Fresh Transaction in the transaction proposal area.

And other miners will keep mining because there are always enough proposed transactions to confirm. There is no need for the miner to dig out the block, because the transaction proposal area of ​​the previous block contains the transaction IDs it will package, and the blocks that have been discovered broadcast the transaction IDs in the transaction confirmation area packaged in the Compact Block. Miners know which transactions are packaged and which are not, and they will not choose transactions that conflict with the transaction confirmation area of ​​the discovered block. Therefore, miners will choose to continue packaging transactions to generate blocks and get fees to contribute to transaction confirmation.

So what if miners include these proposed but unbroadcasted transactions in their latest blocks, to gain a sort of selfish mining advantage?

In Bitcoin's NC, miners gain a mining advantage by slowing down block broadcasting. Miners are usually able to broadcast only the block header when mining a block, and slow down when broadcasting the full block. In this process, only the miner can mine (because only he knows the information of the next block and can mine based on this new block, this process is similar to withholding blocks).

But in our protocol, adopting this method will only slow down the block broadcasting speed after n blocks. Because transactions that are proposed but not broadcast are known only to selfish miners, and only selfish miners can use them to their advantage. However, this cannot be used in the next block, because in our protocol, only n blocks can be mined before the proposal area contains transactions, and there needs to be an interval in between.

Miners can only mine proposal transactions in hm to hn blocks, but cannot mine proposal transactions in the previous block, unless this block is also mined by the attacker.

As shown, this is a comparison of our consensus protocol and Bitcoin NC. In Bitcoin NC, when a selfish miner finds block h, it can start mining block h+1 immediately, and honest miners can only start mining after receiving the complete block h, because other miners need to know The complete transaction contained in the block is verified to determine that the block is legal, and the selfish miner can slow down the transmission speed of block h to make other miners receive the block later. During the block broadcast period is the advantage period for selfish miners.

However, in our protocol, when a selfish miner finds a block h and broadcasts a Compact Block containing the block header and transaction ID, the honest miner can immediately start mining h+1. If the selfish miner wants to take advantage of these proposed but unbroadcasted transactions, it must find blocks n blocks later that contain these proposed but unbroadcasted transactions so that they can take advantage of this. However, this is difficult to happen. You cannot be sure that the block after n blocks is mined by you. This is very difficult to predict.

In order to make better use of bandwidth, our protocol uses a different difficulty adjustment mechanism, setting a fixed orphan block rate (calculated based on the number of uncle blocks in the previous difficulty adjustment period).

If the orphan block rate is lower than the set orphan block rate in the previous difficulty adjustment cycle, the difficulty of mining will be reduced, the block interval will be reduced, and the throughput will be increased. That said, fewer orphan blocks means that the current state of the network actually has the ability to sync transactions faster, and we're able to increase throughput without compromising the decentralization of the network.

Conversely, if the difficulty increases, the block interval will increase and the throughput will decrease. If the orphan block rate is high, it means that the current network cannot handle so many transactions during this difficulty adjustment period, and the protocol will reduce the throughput.

At the same time, the block reward will be proportional to 1/(expected block interval), so the expected total block reward in each difficulty adjustment cycle is fixed.

This means that assuming we produce a block every ten minutes, there are 12.5 bitcoins in each block, and if the difficulty adjustment changes to a block every 5 minutes, there will be 6.125 bitcoins in each block. Therefore, the currency issuance rate is also kept constant.

Finally, resist selfish mining attacks. We mentioned earlier that the difference between our protocol and NC is that our difficulty adjustment mechanism is calculated based on all blocks that appear in the difficulty adjustment interval, and uncle blocks are also included when estimating the total computing power.

In NC-Max, it is assumed that the attacker accounts for 30% of the total computing power and the honest miners 70%. If there is no selfish mining attack, the attacker can find 3 blocks out of 10 blocks, and the honest miners can find 7 blocks. If selfish mining is carried out, the attacker can find 3 blocks out of 7 blocks, honest miners find 4 blocks, 3 honest blocks will become orphan blocks, and the main chain will grow slowly.

As mentioned earlier, selfish mining has no benefits in the first difficulty adjustment cycle, so what will happen in the second difficulty adjustment cycle?

In the next difficulty adjustment cycle, the difficulty will remain unchanged (because the difficulty will be calculated based on all blocks, including orphaned blocks), and the attacker cannot use the same computing power to find more blocks, so selfish mining is no longer profitable picture.

That is to say, we assume that the currency price remains stable in a short period of time. Since selfish mining attackers are short-sighted, their rewards are defined according to the rewards obtained per unit time, which can be equivalent to the same power consumption. award. In Bitcoin, selfish mining attackers can "force" the protocol to reduce the difficulty of block generation by reducing the growth rate of the chain, so that they can obtain more rewards per unit time after the difficulty adjustment. In the design of the NC-Max protocol, the difficulty of block generation will be calculated based on all blocks, including orphan blocks. The attacker makes the blocks of honest miners become orphan blocks, but it cannot "force" the protocol to reduce the difficulty of block generation. Get higher rewards per unit time.

Finally, to summarize, our protocol will make good use of orphan blocks:

We hope to reduce the number of orphaned blocks through two-step transaction verification. After the number of orphaned blocks is reduced, we use the orphaned block rate as an indicator of bandwidth utilization to dynamically adjust throughput.

And the orphan block information is written in the blockchain, we use this information in the mining difficulty adjustment algorithm to make selfish mining unprofitable.

NC-Max is the PoW consensus protocol of Nervos CKB. NC is the abbreviation of Nakamoto Consensus, which is the consensus protocol of Bitcoin. If after reading this article, you think this consensus protocol should have a better name, please let us know.

Recommended reading: Dr. Zhang Ren's Consensus Safety Analysis Article"Developing Common Criteria: Assessing the Security of PoW Consensus Protocols"