Technical direction: Bandwidth optimization in transaction forwarding (1)

Early blockchain systems tended to have low throughput and correspondingly low bandwidth requirements. The consensus protocol itself was the bottleneck of their performance. For example, the Bitcoin network only generates 1MB blocks every 10 minutes, which is almost negligible in today's broadband network environment.

In recent years, with the development and maturity of new-generation blockchains such as Conflux, the throughput of blockchain has made a qualitative leap, and network bandwidth has become a bottleneck that limits the further improvement of blockchain performance. This time, let's talk about how Conflux optimizes the efficiency of bandwidth usage.

Transaction broadcasting is the first step in reaching consensus on the blockchain. Whenever a user initiates a transaction, the transaction starts from the client program and is sent to one or several full nodes. After that, all the nodes forward the transaction to their neighbor nodes through the point-to-point network, until all the full nodes finally receive the transaction.

The greater the throughput of the blockchain, the more transactions each node needs to forward. Therefore, when the throughput of the blockchain and the network bandwidth are in the same order of magnitude, the bandwidth utilization of the transaction forwarding process will directly affect the final throughput performance of the entire blockchain system.

Let's first look at the simplest solution: whenever a full node receives a new transaction, the full node sends the transaction to all its neighbors.

According to the above scheme, each node will receive the same transaction from different neighbor nodes multiple times. This means that whether the transaction is sent or received, there is double the redundancy, and the utilization of network bandwidth is naturally very high. low. Take a 200-byte transaction as an example. If each node has 8 neighbors, this transaction will bring about 1.6kB of transmission and 1.6kB of reception to each full node-and of which Most of the traffic is wasted.

Even Bitcoin, as a system with a throughput rate of only 7 transactions per second, and the bandwidth utilization of transaction forwarding does not constitute a performance bottleneck at all, will no longer use this non-optimized solution.

Bitcoin's solution is that when a Bitcoin node A receives this transaction for the first time, it sends the hash value (32 bytes) of this transaction to all neighbor nodes (except the node that sent it to it). ). After receiving the hash value, neighbor node B checks whether the transaction has the same hash value. If there is, it means that B has received the transaction and does not need to receive it again; if not, B requests A for the full content of the transaction.

In the above process, the process of sending the transaction hash value is called announcement. The detection of the transaction hash value can ensure that each node only needs to receive the complete transaction content once to avoid the waste of bandwidth caused by repeated transmission of the complete transaction.

But announcement itself also needs to use network bandwidth. A rough calculation shows that each node in the above scheme sends about 250 bytes in the announcement link. Although it is much less than 1.6kB, it still exceeds the amount of data to forward a transaction.

Our goal is to reduce the amount of data sent by the announcement link to one-eighth based on the Bitcoin transaction forwarding scheme.

The easiest way to do this is to shorten the length of the transaction hash value broadcasted by the announcement link. In this article, in order to distinguish this hash value from the 32-byte transaction hash value used at the application level (wallet / smart contract), we will refer to the hash value of the transaction at the application level as the transaction ID. The resulting short hash is called the transaction's FID (Forwarding ID).

In Bitcoin's scheme, FID is the same as ID, up to 32 bytes long. If we set the FID to the first 4 bytes of the ID value, we can achieve the goal of reducing the amount of data sent.

However, shorter transaction FIDs also bring security risks while saving bandwidth. If two different transactions Tx1 and Tx2 have the same transaction FID, after a node receives the first transaction Tx1, when a neighbor node sends a second transaction Tx2 FID, it will mistakenly believe that it has received it because of a FID conflict. This transaction no longer requests the full content of Tx2. This will block the broadcast of the second transaction Tx2 in the network.

We can specifically calculate the probability of FID conflicts in the transaction:

Assume that the transaction generation rate is 6000 transactions per second. When each full node receives a transaction FID, it will compare it with the FID received in the past 5 minutes to determine whether to request the full content of the transaction. In this way, the probability that the FID of a transaction conflicts with the existing transaction FID is 6000 * 300/232, which is about 0.04%. This means that an average of 2.4 transactions per second will not be broadcast due to conflicting FID values.

Although the 0.04% collision probability does not seem to be very high, this is just a normal situation without an attack. Using a specific attack strategy, an attacker can block the broadcast of any transaction, thereby achieving the purpose of blocking a specific transaction.

The attack strategy is also not complicated: there are only 232 possible values ​​for the 4-byte FID, which is about 4.2 billion. The attacker only needs to construct and store a transaction for each FID value in advance, and then based on the FID value of the transaction broadcast by the victim, he can find the transaction with the same FID value from the 4.2 billion transactions that he pre-stored and grab it. The victim sends to as many nodes as possible before, and the node that first receives the transaction sent by the attacker will ignore the victim's transaction because of the FID conflict. Even if the victim reissues another transaction, the attacker has the ability to repeat the process.

Based on probabilistic calculations, an attacker would need to try to construct about 100 billion transactions in order to select 4.2 billion transactions with different FIDs. For a server-level CPU, it takes only one week to construct about 100 billion transactions. The storage space required for the calculation is only 32GB after optimization.

Overall, the cost of implementing these attacks is not high. However, in certain scenarios (such as contracts such as Fomo3D), blocked transactions may bring considerable losses to the victims. So this risk must be eliminated from the beginning.

In the next article, we will introduce how to solve the risk of maliciously blocking transactions by converting static FID to dynamic FID.