AlphaBlock: An Evaluation Framework for Blockchain Consensus Protocols

PoA is a type of permissioned NC algorithms that are used by blockchains like Parity¹¹1Proof-of-Authority Chains - Wiki Parity Tech Documentation: https://wiki.parity.io/Proof-of-Authority-Chains and VeChain²²2VeChain: https://www.vechain.com. In this paper, we propose a simple PoA algorithm which is merely a permissioned version of PoW. Firstly, we assume that honest nodes have a consistent view of Global Standard Time (GST) and the time is divided into rounds with a predetermined duration. Then, associated with each block, rather than a hash preimage proving the computation work conducted by the block proposer, a proof proving that the block is proposed by an authorized node which is in charge of proposing block in that round is provided.

The block will be broadcast to the network through gossip protocol. When each node receives a block, it should first validate the block before broadcast it and append it to its blockchain. Invalid block, i.e., blocks including invalid transactions or proposed by the incorrect or unauthorized nodes, will not be broadcast. A malicious node may create a fork, i.e., more than one valid block in a round. Then, honest nodes should apply the “longest chain rule” to determine the valid chain and the valid block. It is guaranteed that honest nodes could eventually reach consensus if blocks could be synchronized in a round and honest nodes are more than 50% of the network.

In HBFT, in each round, a leader is selected according to a predetermined schedule. When a block is proposed by the leader, the leader will broadcast the block to the whole network and all nodes should send their votes with their signature to the leader to participate in the consensus process. When $2f$ agree with votes from the network are received, a quorum consensus (QC) is reached. Here, $f$ is number of the adversaries and $3f+1\leq N$ holds. In HBFT, a three-phase commitment approach will be used to reach consensus for this block. More specifically, a block is only confirmed when it reaches QC for 3 times. In this paper, we consider the chained HBFT proposed in (Yin et al., 2019), where the three-phase commitment scheme is pipelined in a chain. More precisely, in each round, a block is proposed with $2f+1$ votes from different nodes (including the block proposer). Then, a block is confirmed when it is appended by 2 blocks. Moreover, HBFT could function in partial synchronous network by increasing the timeout every time a QC is failed to be reached before the timeout. In this paper, in order to make a fair comparison, we consider a synchronous network where the network delay is known and thus the round duration could be set such that $2f$ votes could be collected with high probability.

In this section, we introduce key concepts relating to our AlphaBlock.

With key concepts defined, we propose the evaluation framework, namely AlphaBlock, which is able to accommodate to both PoA of NC and HBFT of BFT. AlphaBlock loop over the following five parts adapted from (Xiao et al., 2020): Initialization; block proposal; information propagation; block validation; block finalization.

• •

  Initialization. A communication network $G(N,p,D,B_{\textrm{width}})$ is set according to 3.1.1, in which there are a proportion of $\alpha$ malicious or byzantine nodes. At the beginning of each round, A leader is randomly selected to propose a block, which matches PoA and HBFT. A committee of size $C$ is randomly selected to validate a block, and at least $d$ endorsements are needed to validate a block. In HBFT, $C=N,d=2f$. In PoA, $C=0,d=0$.

• •

  Block Proposal. In a round, the leader proposes a block, in which $B_{\textrm{size}}$ transactions are added by the leader. The probability that selected leader happens to be malicious is $\alpha$. If the leader is malicious, it may create an empty block, and the probability of a non-empty block is block rate $B_{\textrm{rate}}$. The malicious leader may also create a fork, and the probability of a fork is fork rate $F_{\textrm{rate}}$. Note $B_{\textrm{rate}}$ and $F_{\textrm{rate}}$ apply to both HBFT and PoA as explained in key concepts.

• •

  Information propagation. When a block is proposed by the leader, the leader will send the block to the whole network using gossip, which takes time the bigger of broadcast time BBT and BBL. Meanwhile the leader communicate with the committee to confirm the block, which takes time CCT. Note BBT, BBL and CCT are explained in block interval of key concepts and all accommodated to HBFT and PoA. Therefore, the block propagation time BBT, the block broadcast latency BBL, and the back-and-forth of committee communication time CCT should all be smaller than or equal to block interval to ensure successful propagation.

• •

  Block validation. After Each node receiving the block, AlphaBlock will need to implement $R$ rounds of votes to validate the block. When the block is validated, it is appended to the blockchain, and the round starts over. In each round, at least $d$ votes must be collected to validate the block, otherwise the block will be nullified and the round will fail. In HBFT, a node will agree the proposed block by signing it and sending the signed vote to the leader. The leader will collect at least $2f$ signatures sent by other nodes, wrap them up, and broadcast the wrapped collected signatures to the whole network. Nodes then add the received wrapped signatures into the block before appending the block to its local blockchain; In PoA, it will take $R=0$ round: a node will just validate the block as long as the leader’s signature is verified, and there is no need of extra committee communication.

• •

  Block confirmation. To confirm a transaction in a block, It requires $K-1$ appending blocks. As explained in the key concepts, $K$ is protocol based. In HBFT, $K=3$, namely it takes 3 rounds of votes from the super-majority to achieve definitive consensus. In PoA, $K=5$, and it only guarantees a probabilistic consensus with a security level of $\epsilon$.

We present the above idea in Algorithm 1. As a simplified version, instead of validating a block, we compute the exact probability of a block being validated and compute variables regardless of the validity of the round. This is reasonable because the variables computed within and without a valid round only differ with respect to the Byzantine ratio, but the communication network is assumed symmetric with respect to being Byzantine. The schematic workflow goes as in Algorithm 1:

AlphaBlock accommodates more protocols than HBFT and PoA. It is interesting to find some optimal protocols in this framework by changing controllable parameters. In terms of throughput and latency, we can figure out these optimal protocols by the throughput-latency frontier in the sense that the throughput cannot be improved without compromising latency and vice versa. The frontier is a strong guidance of future blockchain system design.

More accurately, we are interested in optimising the throughput and latency of a system by choosing proper parameters $(C,d,B_{\textrm{size}})$ from a certain feasible set ${\mathbb{D}}$. If we denote by $T(C,d,B_{\rm size})$ and $L(C,d,B_{\rm size})$ the throughput and latency of the system with parameters $(C,d,B_{\rm size})$, then the problem can be formulated as

The solution of this two-objective optimisation can be defined by Pareto Dominance. Given $y^{1}=(-t^{1},l^{1})$ and $y^{2}=(-t^{2},l^{2})$ then $y^{1}$ is said to Pareto Dominate $y^{2}$(namely $y^{1}\prec_{Pareto}y^{2}$), iff

and the set of all optimal solutions to the problem is described as the Pareto Frontier, which is defined as

Namely, Pareto Frontier is the set in which no other points outside the set can Pareto dominate any point in the set. We find the Pareto frontier by Algorithm 2.

In this subsection, we focus on the latency of HBFT and PoA with different values of block size, network delay and Byzantine ratio, respectively. We take the block size $B_{\textrm{size}}\in\{1,2,...100\}\times 40$, the network delay $D\in\{0.1,0.3,0.5\}$, and the byzantine ratio $\alpha\in\{0.1,0.2,0.3\}$. We show the dependence of the latency on these three variables and the comparison between HBFT and PoA by our numerical experiments shown in Figure 1.

In the left panel of Figure 1, we can see that the latency of both consensus protocols remain flat when the block size stays below 1000, and start to rise after the block size exceeds 1000. This phenomenon can also be seen from the definition of the latency, in which the block size plays it role through the block interval defined as the maximum value among $B_{\textrm{size}}/B_{\textrm{width}}$, the committee communication, and the blockhead broadcast. This maximum will increase together with the increasing of block size only when the block size is big enough, in which case the increasing is a linear style. Furthermore, with the bigger confirmation number $K$, the slope of this increasing for PoA should be bigger, and this is also shown in Figure 1. By the definition of latency, block size only affects latency through block interval, the behavior of latency regarding block size results from block interval. In fact, the flat region is mainly due to the block interval setting that takes maximum from three variables as in key concepts. When block size is smaller than around 1000, the block interval will remain unchanged because the blockhead broadcast and committee communication are dominant to the determination of block interval. Therefore, we see a flat region. When block size larger than 1000, the block interval is dominated by block broadcast, so latency increases linearly in block size. The slope of PoA is greater than HBFT because of their difference in confirmation number $K$.

The middle panel of Figure 1 shows that the latency is increasing in the networkdelay factor $D$ for both HBFT and PoA. This monotonicity can also be explained by the block interval. For a given block size, a bigger network delay factor $D$ will result in a bigger blockhead broadcast and a bigger committee communication, which pushes the latency higher. While our figure shows that this increasing relation is strict, it is true only for big block size according to our explanation here.

The right panel of Figure 1 shows that latency is increasing in Byzantine ratio for both HBFT and PoA. For PoA, this monotonicity comes from the increasing confirmation number $K$ decreasing block rate, as implied in Equation (9) and (13). While for HBFT, this monotonicity comes only from the decreasing block rate. Therefore, it is natural that PoA has a greater slope of the increasing than HBFT, which is also confirmed in Figure 1.

Compare the latency between HBFT and PoA in all three panels in Figure 1, we can find that HBFT has less latency than PoA, and we interpret this comparison mainly by the higher confirmation number $K$ of PoA. While this conclusion contradicts the common belief that BFT performs poorer than PoA when the block size is small. The key argument in this common belief is that BFT has a heavier committee communication overhead. This argument is true for traditional BFT whose communication overhead is $\mathcal{O}(N^{2})$. While for HBFT, the communication overhead is reduced to $\mathcal{O}(N)$, and hence the argument does not apply.

In this subsection, we study the throughput of HBFT and PoA as a function of the block size, the network delay and the Byzantine ratio. We take the block size $B_{\textrm{size}}\in\{1,2,...100\}\times 40$, the network delay factor $D$ in the set $D\in\{0.1,0.3,0.5\}$, and the Byzantine ratio $\alpha\in\{0.1,0.2,0.3\}$. Our experimenal results are shown in Figure 2. To understand implications of these figures, we need the following theorem, whose proof is deferred to Appendix.

In fact, the limit in Theorem 1 is the ratio of $1-\mbox{Fork rate}$ between the two consensuses, and we know the fork rate of PoA is $\alpha$, while it is $0$ for HBFT.

In Figure 2(a), we can see that the throughput of both consensus protocols increase linearly when the block size is below 1000, and then remain flat after the block size exceed 1000. We can examine this phenomenon by the definition of the throughput as in (13), in which the block rate $B_{\textrm{rate}}$ is a constant, the bandwidth efficiency $B_{\textrm{eff}}$ is very close to the constant value $1-F_{\textrm{rate}}$. So the throughput is approximately a linear function of $B_{\textrm{size}}$. As explained in the Subsection 4.1, the block interval remains a constant when When the block size is below 1000, and increases linearly otherwise. This shows the dependence of the throughput on the block size. With the flat property and the limit in Theorem 1, we can conclude that the throughput of PoA is lower than that of HBFT when the block size is big. This conclusion can also be interpreted in another way: when the blockchain system is dominated by bandwidth bottleneck, PoA throughput will be smaller than HBFT throughput.

Figure 2(b) shows then moving of throughputs when the network delay factor $D$ changes. We can see that both throughputs are decreasing in $D$. The reason is similarly due to changes in the block interval, as analyzed in the last subsection. Moreover, we can see from the figure that BFT throughput is more sensitive to the network delay. This is consistent with the comparison of the block intervals. The committee communication is $0$ in PoA, but it can be the dominating factor among the three factors involved in the block interval, which makes the throughput of HBFT more sensible.

In Figure 2(c), we can see that throughput of both HBFT and PoA are decreasing in the Byzantine ratio $\alpha$. This can be confirmed by the fact that both the block rate and the fork rate are decreasing in $\alpha$.

In all three panels of Figure 2, we find that HBFT has better throughput than PoA. Although this is not an unconditional conclusion, we are confident that it holds for most practical settings of parameters.

Throughputs and latencies are studied separately in the last two subsection. In this subsection, we check these two measures jointly for PoA and HBFT in different settings. In Figure 3, we present the joint performance on throughtputs and latencies for PoA and HBFT with different parameter settings. In all 9 settings of parameters, we find that HBFT dominates PoA in the sense that HBFT has higher throughput and lower latency. In this dominance, the higher fork rate of PoA plays a key role, which pushes up the latency and pulls down the throughput. Furthermore, in all cases, when the throughput is pushed up, the latency stays approximately flat before some critical value of throughput, and then spikes up a little bit the value. For a throughput-latency curve, we call the point on the curve with the critical throughput as the turning point (Tpt) of the curve. A Tpt is informative to measure the performance of a consensus protocol, in which its throughput and latency indicate the bottleneck values of the protocol. In all $3\times 3$ panels in Figure 3, we have the following observations.

• •

  Tpt’s throughputs for both HBFT and PoA decrease in $\alpha$. This naturally arise from the block rate in bandwidth efficiency. The difference between the Tpt’s throughputs of HBFT and PoA increases in $\alpha$ because of the difference in their fork rates.

• •

  Tpt’s throughput for both PoA and HBFT remains almost unchanged in the network delay factor $D$. This means that the network delay has little impact on the bottleneck throughput of either system.

• •

  Tpt’s latency for PoA increases in $\alpha$, but remains unchanged for HBFT, so their difference increases in $\alpha$. This phenomenon can be confirmed by the fact that the fork rate for HBFT does not depend on $\alpha$, but it equals $\alpha$ for PoA. We conclude that the Byzantine ratio affects the bottleneck latency for PoA only.

• •

  Tpt’s latency for PoA and HBFT increases in the network delay factor $D$. This is natural given the fact that a greater delay leads to a greater block interval in general. The difference between the two Tpt’s latencies increases in the network delay factor $D$, which is due to the greater confirmation number $K$ of PoA compared with that of HBFT.

In the previous subsections, we showed that the performance of PoA is dominated by HBFT in all numerical experiments. Although the communication overhead hurts the performance of HBFT, the bandwidth wasted by forks in PoA bites on the performance of PoA. In our experiments, the minimal fork rate is $0.1$, which is high enough to make HBFT outperform PoA. In practice, if the malicious nodes use different strategies, the fork rate can vary in a wider range. For instance, on the one hand, by introducing economic penalty, the fork rate in Bitcoin is only $0.0178$ according to (Decker and Wattenhofer, 2013) in 2013, and this fork rate can be reduced further by stronger economic penalty. On the other hand, in Proof-of-Stake (PoS) algorithms like Peercoin, malicious nodes could perform Nothing-at-stakes attack to create a large number of forks (Bentov et al., 2016), resulting a large fork rate. In this work, we fix other parameters and vary the fork rate in $(0,1)$, and find that the PoA will dominate HBFT when the fork rate is less than $0.001$. We show our comparison when taking the fork rate at $0.001$ in Figure 4. By this comparison, we conclude that PoA can be a better choice if the fork rate can be pressed low by introducing some discouraging on forks.

In our previous numerical experiments, the number of nodes is set to be a relatively small number $N=101$ for the convenience of our experiments. In practice, HBFT and PoA are deployed on much larger systems. To make sure that our comparison still makes sense in a large system, we set $N=1001$, and present the same comparison in Figure 5, which shows that the dominance of BFT over PoA still holds. Therefore, although contrary to the common belief, we are confident that HBFT dominates PoA even in a practically larger system.

Finally, let us zoom out of the comparison between HBFT and PoA, and go to find better systems in AlphaBlock in terms of throughput and latency. The variables we can choose here are committee size $C$, endorsement size $d$ and block size $B_{size}$. We show in figure 6 the throughput-latency performance of AlphaBlock systems with different choices of the three variables above. In this figure, we highlight those for HBFT, PoA, and those on the Pareto frontier who has the highest throughput with a certain level of latency or the lowest latency with a certain level of throughput. It may not be possible to achieve some throughput-latency on the Pareto frontier, but we can sense the performance of a system by its difference to the Pareto frontier.