Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
Generalized Federated Learning via Gradient Norm-Aware Minimization and Control Variables
Previous Article in Journal
Analytically Pricing a Vulnerable Option under a Stochastic Liquidity Risk Model with Stochastic Volatility
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Mathematics
Volume 12
Issue 17
10.3390/math12172643
mathematics-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Dynamic Byzantine Fault-Tolerant Consensus Algorithm with Supervised Feedback Mechanisms

by
Anqi Li
,
Yingbiao Yao
* and
Xin Xu
School of Communications Engineering, Hangzhou Dianzi University, Hangzhou 310018, China
*
Author to whom correspondence should be addressed.
Mathematics 2024, 12(17), 2643; https://doi.org/10.3390/math12172643
Submission received: 18 July 2024 / Revised: 13 August 2024 / Accepted: 24 August 2024 / Published: 26 August 2024
Browse Figures
Figure 1
<p>The node division structure.</p> "> Figure 2
<p>The flow chart of the LTSBFT algorithm.</p> "> Figure 3
<p>Operation flow of LTSBFT algorithm (the red arrow denotes the interactions between intra-group nodes with leaders; the blue arrow denotes the interactions between intra-group nodes with supervisory nodes).</p> "> Figure 4
<p>LTSBFT security analysis.</p> "> Figure 5
<p>Scalability comparison.</p> "> Figure 6
<p>Consensus latency comparison under different number of nodes.</p> "> Figure 7
<p>Consensus latency comparison under different number of leaders.</p> "> Figure 8
<p>Consensus latency comparison under different load size.</p> "> Figure 9
<p>Throughput comparison under different number of nodes.</p> "> Figure 10
<p>Throughput comparison under different payload sizes.</p> ">
Versions Notes

Abstract

:
Among the existing consensus algorithms, there are very few low-latency consensus algorithms that can simultaneously take into account node dynamics, fault tolerance, and scalability, and which are applicable to large-scale open scenarios where low latency is required. Therefore, this paper proposes a low-latency scalable dynamic consensus algorithm with high fault tolerance utilizing a combination of layered and threshold signature technologies, known briefly as LTSBFT. Firstly, LTSBFT achieves linear communication complexity through the utilization of threshold signature technology and a two-layer structure. Secondly, the mutual supervision feedback mechanism among nodes enables the attainment of linear complexity for reaching consensus on the faulty upper-layer nodes during the view-change. Lastly, a node dynamic protocol was proposed for the first time to support dynamic changes in the number of nodes during the consensus process. That is to say, consensus can still be reached when the number of nodes dynamically changes without interrupting the client’s request for consensus in the network. The experimental results indicate that LTSBFT exhibits lower communication latency and higher throughput compared to the classic HotStuff and PBFT algorithms. Furthermore, in comparison to double-layer PBFT, the LTSBFT has been demonstrated to have improved fault tolerance.

1. Introduction

In order to maintain the block consistency of nodes, the consensus mechanism is essential in blockchain technology [1]. The Practical Byzantine Fault Tolerant (PBFT) consensus algorithm [2,3,4], which is an alternative to traditional resource proof-based consensus algorithms [5,6,7], addresses the issues of low throughput and resource wastage. Nevertheless, PBFT still faces challenges of inadequate scalability, low fault tolerance, and high communication latency. Especially concerning scalability, the communication complexity of PBFT is O(N2), which severely restricts its applicable scenarios. Additionally, the communication complexity of view-change caused by a malicious leader is O(N3), leading to huge communication-related resource consumption.
W. Li et al. [8] proposed a multi-layer PBFT consensus algorithm which effectively reduced the communication complexity of Byzantine Fault Tolerant (BFT) consensus algorithms by hierarchizing the nodes. However, the latency and fault-tolerance performance of multi-layer PBFT are degraded compared to PBFT. To address the high latency and low fault tolerance of multi-layer PBFT, some improvement algorithms for multi-layer PBFT [9,10,11] have been proposed. A common problem with hierarchical consensus algorithms is that their tolerance for the number of faulty nodes is less than N/3, where N denotes the total number of nodes in the network. Consequently, the hierarchical consensus algorithm cannot be applied in open scenarios, and is only suitable for private and consortium blockchains that have more rigorous access mechanisms.
The HotStuff consensus algorithm [12] reduces the communication complexity of BFT to O(N) during reaching consensus and view-change. Moreover, algorithm security and liveness are guaranteed when there are less than N/3 faulty nodes in the network. However, the effectiveness of HotStuff is limited by the leader’s bandwidth and computing power, performing poorly in the parallel processing of transactions. Furthermore, HotStuff has more consensus phases, resulting in undesirable latency performance. Novel HotStuff improvement algorithms [13,14,15] have emerged gradually, which have effectively reduced the communication latency by omitting the prepare phase in different ways. Although chained HotStuff solves the problem of low throughput experienced with the basic HotStuff consensus algorithm, the risk of block forks caused by malicious nodes and mistake proposals cannot be ignored. However, these consensus algorithms do not sufficiently account for resource consumption, particularly that of the leaders. In addition, the above mentioned algorithms, except for traditional resource proof-based consensus algorithms, do not provide a clear and effective solution for the dynamic change of nodes in the network.
For the current consensus algorithms, the primary issues are concluded as follows:
(1)
Traditional PBFT consensus algorithms consume high communication resources and have low consensus efficiency and scalability.
(2)
HotStuff-based consensus algorithms address the issues of low efficiency and high consumption of PBFT. However, to ensure consensus performance, they require leader nodes to have strong computing power and high bandwidth.
(3)
The current consensus algorithms do not provide a clear and effective solution for the dynamic change of nodes in the network, except for traditional resource proof-based consensus algorithms.
For consensus algorithms, lower resource consumption and higher consensus efficiency are both desirable. Thus, to address the above problems, this paper proposes a high efficiency, low computational consumption, dynamic consensus algorithm based on the combination layering and threshold signature technologies [16,17,18], known briefly as LTSBFT.
First, threshold signature technology is utilized to reduce the consensus communication complexity of reaching consensus on the client request to O(N). Subsequently, by interleaving the feedback of malicious node information from replica-layer nodes to committee-layer nodes, the combination of confirming the NodeID set of malicious nodes with the consensus process is realized within the network, and the complexity of consensus communication to reach consensus of the malicious leaders or supervisory nodes is reduced to O(N). Finally, the node dynamic change within the network without interrupting the consensus process of inter-node is realized by embedding the information of nodes joining or leaving the network into the consensus message.
To the best of our knowledge, the major contributions of this paper are as below:
(1)
We propose a consensus process with a feedback mechanism for malicious nodes to achieve communication complexity for reaching consensus on normal execution or view-change at O(N).
(2)
Aiming at the issue of dynamic node changes, we firstly propose incorporating the consensus of the nodes to be changed within the network into the client request consensus process.
(3)
We propose to set supervisory nodes to supervise leaders and transfer the message of first-time validation pass to the followers, which improves the success rate of consensus and the identification rate of malicious leaders.
The experimental results indicate that LTSBFT exhibits lower communication latency and higher throughput compared to the classic HotStuff and PBFT algorithms. Furthermore, in comparison to double-layer PBFT, the LTSBFT has been demonstrated to have improved fault tolerance.

2. Related Work

The problems of traditional BFT consensus algorithms mainly include the following aspects: arbitrary selection of the leader, high communication complexity, poor scalability, large communication latency, dynamic joining or exiting of nodes leading to interruption of the network consensus process, and low fault tolerance. In improving the arbitrary aspect of leader selection, the RBFT [19] consensus algorithm proposes to select a leader based on node reputation values, which effectively reduces the probability of a malicious leader. In terms of improving the high communication complexity, consensus algorithms such as Zyzzyva [20], Tendermint [21], and HotStuff [12] reduce the communication complexity of the BFT consensus algorithm to linear level. On improving the communication latency, the HCA [22] consensus algorithm utilizes the re-vote mechanism, which effectively improves the problem of high communication latency in the HotStuff consensus. Dynamic PBFT [23] proposes an improved quorum mechanism to solve the problem of nodes joining or exiting dynamically. Aiming at improving the low fault tolerance, NBFT [24] utilizes the aggregated signature [25] technique to make the upper fault tolerance limit higher than N/3, but the lower fault tolerance limit much less than N/3.
Combining some typical BFT consensus algorithms, two novel directions for improved BFT consensus algorithms have been demonstrated. One of the novel improved directions is to divide a large network into different shards, and the consensus is executed independently within the shards. CSBFT [26] proposes a blockchain protocol with flexible sharding to reduce the confirmation latency when processing cross-shard transactions. SharBFT [27] integrates a sharding optimization model (SOM) to improve the efficiency of consensus under dynamic system environments. The SOM minimizes the average consensus latency and also ensures the security and scalability of the network. Yizhong Liu et al. [28] proposed a secure and scalable hybrid consensus (SSHC) scheme, which designs pipelined Byzantine fault tolerance for intra-shard consensus by combining pipelined technology with threshold signatures, thus effectively improving the intra-shards consensus efficiency of the sharding consensus algorithm.
Another improvement direction is to combine consensus algorithms with digital signatures, i.e., reduce the consensus communication complexity using digital signature technology. One of the most typical HotStuff [12] algorithms reduces the communication complexity to O(N) based on threshold signature technology. In addition, Fast-HotStuff [13] reduces the communication complexity to O(N) using aggregate signature technology. Jieyi L. et al. [29] proposed the aggregated signature Gossip [30] protocol, which utilizes a non-interactive leaderless BLS signature aggregation scheme to significantly reduce the communication complexity of transferring messages.
In addition to the above consensus algorithms, there is another category of typical consensus algorithms designed for crash fault scenarios, e.g., Raft [31] and Paxos [32]. They are non-Byzantine fault-tolerant protocols based on state machine replication and have linear communication complexity. Raft is a simplified version of Paxos, offering better understandability.

3. The Proposed Scheme

3.1. The Model

Assume that in a network, there are total N nodes, and each node has a unique node number. Suppose the node number of each node is denoted as NodeID, and all the nodes are divided into NL groups according to the neighboring NodeID. In addition, it is ensured that the number of nodes in each group is basically the same. After that, from all the groups, NL leaders are selected by a Proof of Work (PoW) consensus algorithm. When selecting the leaders, the node with the smallest NodeID broadcasts the mining proposal to all nodes. In each group, the node that solves the puzzle ξ first is the leader. The selected leaders are placed in the committee layer and are no longer affiliated to any group. The leaders are sorted according to the size of the initial NodeID and renumbered in order starting from 0 (NodeID = 0, ⋯, NL − 1). Subsequently, the remaining nodes are categorized into a replica layer. In the replica layer, NS supervisory nodes are selected. Similarly, the PoW consensus algorithm is used to select the supervisory nodes, and the proposal is broadcasted by the leader with NodeID = 0 to the replica-layer nodes. The top NS nodes that are the first to solve the puzzle ξ are the supervisory nodes. The selected supervisory nodes are no longer affiliated with any group, and the remaining nodes are the followers. In the same way as the committee-layer nodes are numbered, the supervisor nodes are first numbered starting from NL (NodeID = NL, ⋯, NL + NS − 1). The followers are numbered from NL + NS (NodeID = NL + NS, ⋯, N − 1). The node division structure is shown in Figure 1.
The nodes in the network store the NodeID and public key of all the nodes and their corresponding (IP; Port). When a new node joins, based on the number of nodes in each group, the group with the least number of nodes is selected to join, and the node is numbered as NodeID = N. Suppose the kth group from the number of nodes is N f k . When a NodeID = i node exits, each node needs to delete the stored NodeID and the corresponding (IP; Port), and the node with NodeID > i will change its node number to NodeID − 1. The specific node dynamic protocol content is described in an expanded manner in Section 3.4.

3.2. RSA Threshold Signature

The LTSBFT consensus algorithm uses the (t, n)-RSA threshold signature scheme. Each leader in the committee layer has a unique private key s and a verification private key v. All nodes together hold the verification public key VK and the complete digital signature public key PK. v, PK, and VK are made public, and s is secret. Assume that the message m is signed by leaderi via private key si as { t s i g n m , s i } i ∈ I . Each leader contributes a partial signature { t s i g n m , s i } i ∈ I , and when a leader collects |I| = t valid threshold signatures { t s i g n m , s i } | I | = t , it can generate to the complete digital signature σ = c o m b i n e ( t s i g n ( m , s i 1 ) , ⋯ ,   t s i g n ( m , s i t ) ) . In the LTSBFT consensus algorithm (t, n) threshold signature scheme, set t = ⌊NL/2 + 1⌋, n = NL.
Each leader verifies the validity of each partial signature { t s i g n m , s i } i ∈ I sequentially before generating the complete digital signature σ. The pseudocode for partial signature generation, partial signature validity verification, complete digital signature generation, and digital signature verification is shown in Algorithm 1.
Algorithm 1 threshold signature
⊳ Key Generation
//The Key Generation Center (KGC) generates corresponding keys for each node.
1:as a leader
2:storage ( v i , V K , l e a d e r . s , P K ) i = 1 N to local k e y p o o l
  // V K = v , v i = v s i , s i = = l e a d e r i . s
3:as a follower
4:  storage P K to local k e y p o o l
⊳ Partial Signature Generation
5:the leader generates { t s i g n m , s i i } i ∈ I = m 2 Δ s i   ∈ Q n // Q n is an n-element finite field
⊳ Partial Signature Verification
6:the leader computes b = H v r , m 4 Δ r , z = l e a d e r . s · b + r
//r is a random number chosen by the leader ( r ∈ { 0 , ⋯ , 2 512 − 1 } )
7:if  b = = H v z v i − b , m 4 Δ z t s i − 2 b // t s i = = t s i g n m , s i i i ∈ I , H is a Hash function
8:   t s i g n m i i ∈ I is a valid signature
9:else
10:   t s i g n m , s i i i ∈ I is an invalid signature
⊳ Signature Combine
11:if the leader collects | I | = t valid signatures
12:  the leader computes σ =   c o m b i n e ( t s i 1 , ⋯ , t s i t )
⊳ Digital Signature Verification
13:if  V e r i f y σ , P K = = t u r e
14:  σ is a correct digital signature
15:else
16:  σ is a fault digital signature

3.3. Hierachical Consensus Protocols

In the LTSBFT consensus algorithm, a consensus is reached among the leaders in the committee layer using a threshold signature, which produces an acknowledgement of the authenticity of the message by each signing leader. Utilizing the verifiability of the threshold signature, replica-layer nodes only need to validate that the threshold signature sent from any node passes to confirm the authenticity of the message.
Therefore, the LTSBFT consensus algorithm selects S ( S ∈ [ 2 , ( N L + 1 ) / 2 ] ) leaders to send client requests to replica-layer nodes, and the other leaders supervise the behavior of the selected S leaders. Due to the utilization of an interleaved feedback mechanism and the insertion of the NodeID set of malicious nodes within the consensus message for client requests, communication complexity for reaching consensus of malicious nodes only requires O(N).
In the inter-leader generation threshold signature phase, a leader needs to be selected to send pre-prepare messages to other leaders. Here, taking a reference from the PBFT consensus algorithm for leader selection, the leader is selected by Lv = v mod NL, where v is the current view. When the leader leaderi with NodeID = i ( i ∈ [ 0 , N L − 1 ] ) receives a client request, it needs to transfer it to the leader with NodeID = Lv. If leaderi does not enter the prepare phase after receiving a new client request message, it reselects the leader with NodeID = Lv + 1 to send the pre-prepare message. The basic process of the LTSBFT consensus protocol is shown in Algorithm 2, the flow chart is shown in Figure 2, and the operation flow is shown in Figure 3. The LTSBFT layered consensus protocol is implemented as follows:
Client request phase. The client initiates a request to the leader < r e q u e s t , o , t , c > σ c l i e n t , where o is the client request, σ c l i e n t denotes the digital signature of the client, t is the timestamp of generating the message, and c is the client identity (lines 6–7).
Pre-prepare phase. When the l e a d e r L v receives client request, it sends a pre-prepare message < < p r e p r e p a r e , m , t s i g n m , s L v , b L v , z L v > σ L v , m s g > to other leaders. In this case, msg is the request message from the client; σ L v is the digital signature of the l e a d e r L v ; and m denotes < t , n , v , l v , H a s h n > , where, v and n are the view number and the message sequence number, respectively. Furthermore, Hashn = SHA256 (msg) + Hashn−1. b L v and z L v are used to validate the validity of t s i g n m , s L v . lv is the NodeID set of malicious nodes for which the current view leader expects to reach a global consensus, and s L v is the private key of l e a d e r L v .(line 7).
Prepare phase. If leaders receive the pre-prepare messages and successfully validate the pre-prepare messages, they then send a partial signature < p r e p a r e ,   t s i g n m , s i , b i , z i > to the other leaders (lines 8–9).
Commit phase. Leaders receive the prepare message and verify the validity of each partial signature. After the leaders collect |I| = ⌊NL/2 + 1⌋ valid { t s i g n m , s i i } i ∈ I , they generate a complete digital signature utilizing σ = c o m b i n e ( s i g n m ,   s i 1 ,   ⋯ ,   s i g n ( m , s i t ) ) . After that, the S leader with NodeID = LSi (i = 1, 2, ⋯, S) is selected to send the < c o m m i t , t ,   n , v , k v − 1 , m s g , σ , L S i > message to the kth ({k | i = k mod S}) group of followers and all the supervisory nodes (lines 10–19).
Follower reply phase. If followers receive the commit message and verify that the commit message is correct, then followers reply < f r e p l y , n , t , v , f v , r e s ,   i > σ i to the corresponding leader. Here, fv is the NodeID set of the malicious node feedback to the certain leaders from the certain followers in view v, containing the NodeID of the malicious leaders and the malicious supervisory nodes determined by that follower. For the malicious leader or supervisory node identification, if leaders or supervisory nodes do not adhere to the protocol, broadcast a message that fails verification, or fail to broadcast a message, they will be identified as malicious nodes.
In addition, res is the confirmation result of the follower. In this case, res = 1. If the follower obtains the first commit message that can be validated to pass from the leader with NodeID = LSi=k mod S, then LSi=k mod S ∉ fv. Otherwise, LSi=k mod S ∈ fv. If the follower, after confirming the client request, does not receive < s c o m m i t , c o m m i t , j > σ j from a supervisory node supervisory nodej (j  ∈ [NL, NL + NS − 1]) within the maximum network latency, j  ∈  fv+1. The follower will feedback fv+1 to the leader at v + 1 view (Algorithm 2: line 22–line 38). After the first correct commit message received, the supervisory node sends a < s c o m m i t , c o m m i t , j > σ j message to all followers and replies to all the leaders with < s r e p l y , n , t , v , s v , r e s ,   j > σ j . Here, j is the NodeID of the supervisory node. Subsequently, the supervisory node collects commit messages from all S leaders. If within the maximum network latency, a supervisory node does not collect the correct commit message from a leader leaderl (l ∈ C), l  ∈  sv+1. The supervisory node will then feedback sv+1 to all non-malicious leaders at v + 1 view. C is the NodeID set of the selected S leaders (lines 20–46).
Leader reply phase. When the leader with NodeID = k (k  ∈ [0, NL−1]) receives more than N f k / 2 + 1 valid replies with consistent resf = 1 from the followers, then it is considered that the consensus of the kth group has been reached. Thus, the leader replies < l r e p l y , n , t , v , r e s > σ l to the client. When the client receives f + 1 valid and consistent replies, then it is considered that the whole network consensus has been reached (lines 47–51).
Algorithm 2 LTSBFT consensus protocol
1:function t s i g h m , s , v p a r s i g n t s i g n m , s i i , b i , z i , v s i g n σ , p k  
   //signing, validating partial signature, validating digital signature
2:function  v m s g ( m s g ) //validating message with request
 if msg.n==n+1 ∧ msg.v == v+1 ∧ msg.o ≠ msg.o
  return true
3:function  v h a s h ( m s g ) //validating message with hash value
  if msg.v==node.v+1 && msg.v==node.v+1 && msg.hash != msg’.hash 
  return true
4:function c h n o d e I D ( n o d e I D ) //select a n o d e I D for the reply required
 for  i d = n o d e I D + 1 , n o d e I D + 2 , ⋯
  if  i d   ∈ n o n f a u l t s e t  
    R e p l y L I D   =   i d
   break
 return  R e p l y L I D
5:for  v = 0,1 , 2 , ⋯
⊳ request phase
 as a client
6:send r e q u e s t to a random leader
⊳ preprepare phase
 as the certain leader//the leader who receives the r e q u e s t message
7:send p r e p r e p a r e to the other leaders
⊳ prepare phase
 as a leader//the leader is the node that receives the p r e p r e p a r e message
8:if  v m s g p r e p r e p a r e  
9:  send p r e p a r e message to the other leaders
⊳ commit phase
 as a leader
10: l e a d e r . p a r s i g n N u m = 0
11:if vhash(prepare) && vparsign(prepare.sign, prepare.b, prepare.z)
12:   leader.parsignNum=leader. parsignNum+1
13:if  l e a d e r . p a r s i g n N u m = = N L / 2 + 1 && l e a d e r . N o d e I D = = L S i
14:// f n u m = N o d e I d l s | L S i + v 2 m o d N L ∈ [ 0 , S + f n u m ) ∩ f a u l t s e t
15:// C = L S i | L S i + v 2 m o d N L ∈ [ 0 , S + f n u m ) ∩ n o n f a u l t s e t = = S
 // f a u l t s e t is a set of evil leaders NodeID; n o n f a u l t s e t is a set of honest leaders NodeID
16:     σ = c o m b i n e ( p r e p a r e . s i g n 1 , ⋯ ,   p r e p − a r e . s i g n t )
17:     < c o m m i t , t , n , v , l v , m s g , σ , L S i > = C o m m i t m e s s
18:    send C o m m i t m e s s to the followers of k t h   k m o d S = = i group
19:    send C o m m i t m e s s to supervisory nodes// i is the position of L S i in set C
⊳ follower reply phase
 as a follower//the follower is a node in group k
20: i f r e p l y l e a d e r = f a l s e //record whether the follower replies to the corresponding leader
21: R e p l y L I D   =   k
22:if k ∈ f a u l t s e t
23:   R e p l y L I D = c h n o d e I D ( k )
24:if C o m m i t m e s s sent by leader &&   v s i g n C o m m i t m e s s . σ , p k
25:   f v ← n i l , r e s f = 1 , i f r e p l y l e a d e r ← t r u e and send f r e p l y to the l e a d e r R e p l y L I D
26:if  s c o m m i t sent by supervisory nodes && ! t i m e o u t
27://determine if waiting exceeds the maximum network delay
28:  append s c o m m i t . N o d e I D to r e c o r d S I D
29:  if ifreplyleader == false && Verify(Commitmess.σ, PK)
30:    f v ← N o d e I d l f , r e s f = 1  
31:   if  R e p l y L I D = = N o d e I d l f
32:     R e p l y L I D = c h n o d e I D ( k )
33:   send f r e p l y to l e a d e r R e p l y L I D and i f r e p l y l e a d e r ← t r u e
34:if  i f r e p l y l e a d e r
35:  for  S I D = N L , ⋯ , N L + N S − 1
36:   if  S I D ∉ r e c o r d S I D
37:   append S I D to f v + 1
 as a supervisory node
38: i f r e p l y ← f a l s e
39:if  V e r i f y C o m m i t m e s s . σ , P K   & &   ! t i m e o u t  
40:  if   ! i f r e p l y  
41:    i f r e p l y ← t r u e , r e s f = 1
42:   send s c o m m i t to all followers and send s r e p l y to all leaders
43:  append C o m m i t m e s s . N o d e I D to r e c o r d N I D
44:for  l e a d e r I D = range n o n f a u l t s e t
45:  if  l e a d e r I D ∉ r e c o r d N I D
46:   append l e a d e r I D to s v + 1
⊳ leader reply phase
 as a leader
47: l e a d e r . f r e p l y N u m   =   0
48:if  f r e p l y . r e s f = = 1  
49:   l e a d e r . f r e p l y N u m   = l e a d e r . f r e p l y N u m + 1
50:if  l e a d e r . f r e p l y N u m = = F n u m j / 2 + 1
51:  send l r e p l y to the client
If the correctly completed digital signature is not generated among the leaders during the commit phase, all nodes in the network execute the PBFT consensus algorithm. The leader sends pre-prepare messages to all followers to be validated. The follower calculates NodeIDPL = (v + N) mod NL among the leaders that send the pre-prepare message, and the leader whose NodeID is closest to NodeIDPL is selected as the leader that executes the PBFT consensus algorithm. If the NodeIDs of leaders are equal in distance to NodeIDPL, the leader with the larger NodeID is selected. Within the LTSBFT consensus algorithm, a case may exist in which the consensus of a group has been reached, but the corresponding leader does not reply to the client. Thus, when a follower receives a client request which has been saved locally, the follower replies to the client directly, and the consensus of the network is considered reached when the client receives more than ⌊N/2 + 1⌋ replies from the followers. In order to ensure the network liveness, if an honest leader leaderi generates a threshold signature and does not receive a reply from the ith group of followers within the maximum network latency, it sends a commit message to all followers in the group that satisfy {k | k mod S == i mod S}. Here, k is the group number of the followers.

3.4. Node Dynamic Protocol

The dynamic change of nodes in the network is mainly categorized into three cases: (1) nodes actively applying to join the network; (2) nodes actively applying to exit the network; and (3) nodes crashing, resulting in passive exit from the network. The protocols will be described in detail for each of the three cases.
When a new node applies to join the network, it sends < J o i n , t 1 , P K , ( I P ; P o r t ) > σ to a node in the network that can be contacted, where t1 is the timestamp of the Join message generation, and PK is the public key for verifying the new node’s digital signature σ. If the node Nodek with NodeID = k receives a Join request in view v, it will transfer the Join request to all leaders at the end of the execution of the current view. Then Nodek sends the (IP; Port) and public key information of all the nodes within the network stored by itself to the new node applying to join. After the leaders input PK to verify that the Join message has passed, in view v + 1, a consensus protocol which incorporates client request consensus with node join request consensus will be executed. Below, this protocol is described in detail.
In the pre-prepare phase, the l e a d e r L v + 1 sends <<preprepare&&join, m, tsign(m, s L v + 1 , S H A 256 J o i n ) , b L v + 1 , z L v + 1 > σ L v + 1 , m s g > to other leaders, where SHA256(Join) is the hash value of the Join message. The leaderk ( k ∈ [ 0 , N L − 1 ] / L v + 1 ) receives the preprepare&&join message and verifies that the message has passed, then it enters the prepare phase. Then, leaderk sends <prepare&&join, {tsign(m, sk, SHA256(Join))k } k ∈ I , b k , z k > σ k to other leaders. A commit&join message is generated by |I| = ⌊NL/2 + 1⌋ valid prepare&join messages. The commit&join message format is < c o m m i t & & j o i n , t , n + 1 , v + 1 , f v + 1 , m s g , J o i n , σ j o i n > σ i , where σ j o i n = c o m b i n e t s i g n m , s i 1 , S H A 256 J o i n , ⋯ , t s i g n ( m , s i t , S H A 256 J o i n ) . After that, leaderLS sends a commit&&join message to the replica-layer node. The replica-layer node Nodek ( k ∈ [ N L , N − 1 ] ) receives and validates the correctness of the commit&&join message, and then it saves the client request of view v + 1 locally and considers that the consensus of the new node joining has been reached. Thus, Nodek saves the (IP; Port) and PK of the new node locally. Since the follower reply phase and leader reply phase are consistent with the LTSBFT layered consensus protocol, it is not described here.
Suppose Nodei ( i ∈ [ 0 , N − 1 ] ) requests to exit from the network at view v. Nodei sends an Exit message < E x i t , t 2 , i , ( I P ; P o r t ) > σ i to all the leaders after completing the consensus of the current view, where t2 is the timestamp of the Exit message generation. After Nodei sends the Exit message to the leaders, in view v + 1, a consensus protocol which incorporates client request consensus with node exit request consensus will be executed. The execution of this protocol is similar to the case of a node requesting to join the network. At each phase the “join” in the message header is replaced with “exit”, SHA256(Join) in the message body is replaced with SHA256(Exit), and σ j o i n is replaced with σ e x i t = c o m b i n e t s i g n m , s i 1 , S H A 256 E x i t , ⋯ ,   t s − i g n ( m ,   s i t ,   S H A 256 E x i t ) . If Nodei is a leader, the network complements the exiting leader when the leader is re-selected.
There are three main cases through which to judge node crash: (1) followers crash; (2) supervisory nodes crash; and (3) leaders crash. The leaders check the followers’ and supervisory nodes’ storage states by executing the state consistency check protocol in Section 3.5 to judge whether they are in a crash state. If the followers or supervisory nodes do not send Check messages to the majority of the leaders during the state consistency check phase, each leader sends < p r e E x i t , S e t I D , S e t I P , j > σ j to other leaders, where SetID and SetIP are the set of NodeID and (IP; Port) of the nodes that did not send the Check message, and j and σj are the NodeID and digital signature of the leader that sent the preExit message, respectively. If a leader collects more than ⌊NL/2 + 1⌋ valid preExit messages sent by different leaders, it proves that the node represented by the NodeID contained within the SetID has not participated in the state consistency check, and the node may have crashed. After the state consistency check is over, it enters (v + 1)th view, and the leader l e a d e r L v + 1 that tranfers the client request in v + 1 view sends preprepare &&Exit messages to other leaders. Subsequently, a consensus protocol which incorporates the client request consensus with the node exit request consensus will be executed. The Exit message within preprepare&&Exit, prepare&&Exit and commit&&Exit is < E x i t , t 2 ,   s e t I D ,   s e t I P > σ L v + 1 . In this case, multiple crashed nodes can exit the network at the same time.
If a leader crashes during consensus execution, it will be marked as a malicious leader when it is selected to send client requests to replica-layer nodes. At the time of re-selecting the leader, this crash leader is replaced as a follower and exits from the network at the end of the execution of the state consistency check protocol, since the malicious leader is skipped when the leader is selected to send the client request to the replica-layer node. The node is not re-elected as a leader or supervisor node after it is marked as a malicious node. Therefore, the normal execution of the protocol is not affected until the crashed leader is excluded from the network.

3.5. State Consistency Check Protocol

The state consistency check has two main roles: (1) to ensure that the replica-layer nodes and the leader maintain a consistent state, and that the nodes within the network delete the stored logs, reducing the node storage load; and (2) to facilitate the leader checking the state of the replica-layer nodes, resulting in timely clean up of the crashed nodes within the network in order to reduce the adverse impact of the crashed nodes on the network.
Referring to the node state storage structure of PBFT [3], each node manages each state in the form of a partition tree, and each page saves the client requests that have reached consensus. In order to prevent block forking, H a s h n = S H A 256 m s g + H a s h n − 1 is put into the threshold signature during the signature process of the inter-leader. Therefore, the followers or supervisory nodes correctly verify the threshold signature only if they have not lost their previous state. In order to ensure that most replica-layer nodes have the correct state, the leaders are set to execute a state consistency check at a certain interval, based on a fixed number of rounds. The C h e c k , R , i , t 3 σ i is sent to all leaders by replica-layer nodes, where R is all the metadata in the partition tree stored by the replica-layer node, and t3 is the timestamp of the Check message generation. The leader verifies whether each metadata value is correct or not. If a leader verifies that a metadata value of a follower or supervisor node is wrong, it will start the state transfer and send < t r a n s f e r , P , l , v > σ l to this node, where P contains all the page values under the metadata that failed authentication and each page contains a client request, and l is the NodeID of the leader. If a replica-layer node receives consistent transfer messages from more than ⌊(NL + 1)/2⌋ leaders, it considers its own state as in error. In this case, the node will copy the state transferred from the most leaders.
At the end of the state consistency check, the state of the replica-layer node that lost its state is restored and the nodes within the network are in a stable state. After that, in order to prevent the increasing length of the message log stored by the nodes, all the nodes within the network retain only the previously stored digest of each client request.

3.6. View-Change Protocol

Assume that under the current view v, no malicious node has been discovered by the replica-layer node, and the client request reaches consensus normally; then, all nodes within the network will directly change view. If a leader or supervisory node is found to be malicious by the replica-layer nodes under view v, a consensus on the NodeID of the malicious node needs to be reached within the network. Subsequently, all nodes within the network will change view. If a leader is judged to be a malicious node, it will not be selected to send commit messages to the followers and the followers will not reply freply messages to it.
Since the set of malicious NodeIDs is embedded within the freply (sreply), prepare (prepare&&join, prepare&&exit), and commit (commit&&join, commit&&exit) messages, the confirmation of malicious nodes is incorporated into the follower reply, prepare, and commit phases of consensus. leaderi  ( i ∈ [ 0 , N L − 1 ] ) only needs to collect the freply (sreply) messages within the maximum network latency to judge whether a malicious node exists or not. If there is a malicious node, then the freply (sreply) message containing the N o d e I D n f ( n f ∈ [ 0 , N L + N S − 1 ] ) is transferred by leaderi to other leaders, where N o d e I D n f is the NodeID of a malicious node judged by leaderi. In this way, leaderi informs the other leaders that the node n o d e n f with N o d e I D = N o d e I D n f is judged as a malicious node. If the threshold signature containing the N o d e I D n f is generated correctly in the prepare phase of the next view, it proves that the consensus has been reached between the leaders that the n o d e n f is a malicious node.
If a leader collects ⌊N/2 + 1⌋ freply messages which all contain the feedback of the N o d e I D s f of the supervisory node S u p e r v i s o r y   n o d e s f in view v, then the leader judges that the supervisory node S u p e r v i s o r y   n o d e s f is a malicious node. The leader judges whether a node is a malicious leader or not, which can be divided into two cases:
(1)
Feedback from both supervisory nodes and followers: if leaderi collects ⌊Ns/2 + 1⌋ sreply messages in view v and ⌊N/4S + 1⌋ freply messages in view v – 1, and the sreply and freply messages all contain feedback of N o d e I D l f , leaderi considers l e a d e r l f as a malicious node.
(2)
Feedback from followers: if in view v, leaderi collects ⌊N/2S + 1⌋ freply messages which all contain feedback of N o d e I D l f , leaderi considers l e a d e r l f as a malicious node.
Case (1) is given in order to supervise the leaders to send correct commit (commit && join, commit && exit) messages to the supervisory node; case (2) is given in order to supervise the leader to send timely commit (commit && join, commit && exit) messages to the followers. The way followers and supervisory nodes judge whether a leader is malicious, and the way followers judge whether a leader is malicious, are shown below.
If a follower does not receive a corresponding commit message from l e a d e r l s before receiving the correct commit message from the supervisory nodes, it considers l e a d e r l s as a malicious leader. Thus, the follower inserts the NodeID of l e a d e r l s into fv (Algorithm 2: lines 28–31).
If a follower does not receive a scommit message from a particular supervisory node supervisory nodei within the maximum network latency, supervisory nodei is considered as a malicious supervisory node. Therefore, the follower inserts the NodeID of supervisory nodei into fv+1. The fv+1 set sent by the follower contains the NodeID of the malicious leader and the malicious supervisory node (Algorithm 2: lines 35–38).
Suppose leaderf is the node that should send a commit message to the replica-layer node in view v, but leaderf does not send a commit message to the supervisory node supervisory nodei  ( i ∈ [ N L , N L + N S − 1 ] ) within the maximum network latency. Thus, supervisory nodei inserts the NodeID of leaderf into sv+1 during the freply phase within view v + 1 (Algorithm 2: lines 41–48).
Once the number of malicious leaders reaches ⌊(NL − 1)/2⌋, or the upper layer node threshold signature cannot be generated, the non-malicious leader with the smallest NodeID broadcasts a proposal to all the groups to replace all the malicious leaders by PoW consensus algorithm. The top Nf non-malicious followers with successful mining are considered as master nodes, where Nf is the number of the malicious leaders in the committee layer. The NodeID of the elected non-malicious followers and the NodeID of the malicious leaders are sorted, respectively, and the NodeIDs of both of them are exchanged with each other in order. The malicious leader is placed in the group of followers of the same NodeID as the original follower to make the malicious leader a follower. Finally, leaders re-initialize the key.
If the supervisory node is found to be malicious node, a new supervisory node is selected based on NodeIDC = NL + NS + v mod (N − NL − NS). If the node with NodeID = NodeIDC is a malicious node, then the non-malicious follower which is closest to NodeIDC is selected. If the NodeIDs of two followers are equal in distance from NodeIDC, then the follower with the larger NodeID is selected. The NodeIDs of the selected follower and the malicious supervisory node are exchanged, and the malicious supervisory node becomes a follower and is placed into the group where the selected follower node is located.
The original malicious node remains a malicious node after changing to a follower. The nodes within the network replace the previously stored NodeID of malicious nodes with the NodeID of the current malicious node after the leader and supervisory node reselection. A malicious node cannot be selected as a leader or supervisory node.

3.7. State Transfer Protocol

If a node nodei ( i ∈ [ 0 , N − 1 ] ) finds that the message sequence numbers in the state machine are not continuous, then nodei executes the transfer state protocol. nodei sends < F e t c h , n 1 , n 2 , i > σ i to any one of the other nodes, where n1 is the message sequence number at the beginning of the message to be transferred and n2 is the message sequence number at the end of the message to be transferred. When the Fetch message is received by nodej ( j ∈ [ 0 , N − 1 ] / j ), it replies < t r a n s f e r , P , j > σ f to nodei, where P contains correct commit messages from n1 to n2 which have been verified. If nodei initiates a Fetch request but does not receive a reply, it can again initiate a Fetch request to other nodes.

4. Algorithm Analysis

4.1. Security Analysis

The inter-leader conducts the threshold signature in the pre-prepare and prepare phases to generate a complete digital signature σ . If the followers successfully verify the σ , they store the commit message. In the RSA threshold signature scheme, the threshold t = ⌊NL/2 + 1⌋ is set to generate a proof on the votes of the most leaders by commit messages. Therefore, the security of linearly multicasting commit messages from leaders can be guaranteed by the LTSBFT consensus algorithm. After that, we further analyze the security of LTSBFT by referring to the FPD model in [8]. In the FPD model, the number of nodes is fixed, and the consensus success rate of the LTSBFT consensus algorithm is calculated by altering the malicious node probability p.
Suppose that the network contains NL groups, NL leaders, and NS supervisory nodes. There are Nf followers within each group and S leaders are selected to send commit messages to replica-layer nodes. To simplify the case, assume that if the selected leaders is honest, they will send the correct message to the corresponding followers of NL/S groups and all supervisory nodes; if the selected leaders are faulty, they will not send the correct message to any of the nodes. When more than ⌊NL/2 + 1⌋ groups can reach consensus, it can be considered that consensus has been reached within the network.
Subsequently, the discussion is based on the case that the threshold signature can be generated correctly among leaders. If the consensus can be reached, there are two cases for followers receiving the commit message: (1) all followers can receive the valid commit message; or (2) only a partial number of followers can receive the valid commit message. Case 1 is satisfied if there exists any honest leader among the elected S leaders and there exists any honest supervisory node, or all of the elected S leaders are honest leaders; case 2 is satisfied if all the supervisory nodes are malicious nodes and there exists [⌊S/2 + 1⌋, S − 1] honest leaders among the S leaders.
Suppose that the inter-leader can generate the correct threshold signature as event A; more than half of the followers in a group are honest followers as event B; all followers can receive the correct commit message as event C1; and partial followers can receive the correct commit message as event C2. The probabilities of reaching events A, B, C1, and C2 are, respectively, P(A), P(B), P(C1) and P(C2), and their equations are shown in Equation (1).
P ( A ) = ∑ i = 0 N L / 2 + 1 C N L i p i ( 1 − p ) N L − i P ( B ) = ∑ k = 0 N f / 2 + 1 C N f k p k ( 1 − p ) N f − k P ( C 1 ) = 1 − p S + ∑ j = 1 S − 1 C S j ( 1 − p ) S − j p N S + j P ( C 2 ) = ∑ l = S / 2 + 1 S − 1 C S l p S + N S − l ( 1 − p ) l
Here, to simplify the case, it is assumed that events C1 and C2 are independent of event A. In practice, events C1 and C2 are related with event A. Due to this, the possibility for followers to receive the correct commit message is dependent on the correct generation of the threshold signature. When event C1 is held, the probability is calculated as P1; when event C2 is held, the probability is calculated as P2. P1 and P2 equations are shown in Equation (2). Finally, the probability of reaching consensus is calculated as P = P1 + P2. Since both the calculated P1 and P2 are smaller than the actual probability of occurrence, the calculated probability P of reaching consensus will also be lower than the actual simulation.
P 1 = ∑ t = N L / 2 + 1 N L C N L t P ( C 1 ) P ( B ) t [ 1 − P ( B ) ] N L − t P ( A ) P 2 = ∑ l = S / 2 + 1 S − 1 C S l p S + N S − l ( 1 − p ) l ∑ t = N L / 2 + 1 N L l / S C N L t P ( B ) t [ 1 − P ( B ) ] N L − t P ( A )
To verify the correctness of the analysis, the probability of simulation by the actual network is compared with the probability of calculation by the analysis, where NL = 15, NS = 3, S = 3, and Nf = 9. Furthermore, the number of nodes in the first layer of double-layer PBFT is 15 and the number of nodes in each group is 9. The security of the LTSBFT consensus algorithm is evaluated by comparison with the success rate of double-layer PBFT [8]. The comparison results are shown in Figure 4.
As can be observed from Figure 4, the consensus success rate of the LTSBFT consensus algorithm is much higher than the consensus success rate of double-layer PBFT. When the node malicious probability p < 0.2, the LTSBFT consensus algorithm network consensus success rate is close to 1. Therefore, it can be concluded that the LTSBFT consensus algorithm has improved security.

4.2. Liveness Analysis

When the threshold signature cannot be generated correctly among leaders, the PBFT consensus algorithm is executed instead. This ensures the algorithm liveness when more than half of the leaders are malicious leaders. When honest leaders generate a complete digital signature, after maximum network latency, they cannot receive replies from the corresponding followers. Therefore, leaders broadcast commit messages to those followers. This ensures algorithm liveness when more than half of the honest followers fail to receive a correct commit message. When followers receive a committed client request, followers directly reply to the client. This ensures the algorithm liveness when leaders are malicious during replying to the client. To summarize, when the number of malicious nodes in the system is less than N/3, the LTSBFT consensus algorithm can ensure liveness.

4.3. Resource Consumption Analysis

Furthermore, the LTSBFT algorithm also addresses resource consumption, including both communication and computational resources. Compared to PBFT, LTSBFT significantly reduces communication overhead, with only negligible additional communication costs. Specifically, LTSBFT uses threshold signature technology among a small committee of nodes, reducing communication complexity to O(N), whereas PBFT has a communication complexity of O(N2).
For HotStuff-based consensus algorithms, the issues of limited bandwidth and computational power for the leader remain unresolved. Generating complete threshold signatures requires computational complexity of O(N3) for the leader. In contrast, the use of threshold signatures in LTSBFT, limited to the committee layer, significantly reduces computational resource consumption.

4.4. Scalability Analysis

According to the previous description, there are a total of NL leaders, NS supervisory nodes, and Nf followers in each group, and S leaders are selected to send commit messages to replica-layer nodes. Assuming the number of followers in each group is equal, the total number of followers in the network is Z = NL Nf.
In the pre-prepare and prepare phases, leaders generate the threshold signature and the communication overheads are N L N L − 1 + N L = N L 2 . In commit phase, the selected leaders broadcast commit messages to the corresponding nodes in the replica layer. The communication overheads in the commit phase are N L N f + S N S = Z + S N S . In the follower reply phase, once the followers successfully verify the threshold signature, they reply to the corresponding leader; the supervisory nodes successfully verify the threshold signature, and they broadcast scommit messages to all followers and replies to all leaders. The communication overheads in the follower reply phase are Z + N S Z + N L N S = Z + N S ( Z + N L ) . In the leader reply phase, when leaders receive a reply from more than half of the followers within the same group, leaders reply to clients. The communication overheads in leader reply phase are N L . To sum up, the total communication overheads for LTSBFT are 2 + N S Z + N L 2 + S + N L N S + N L . Since N S ≈ S < N L ≪ Z , the LTSBFT consensus communication complexity is O(N).
Finally, the scalability of LTSBFT is evaluated by comparing the communication overheads of LTSBFT with that of HotStuff, double-layer PBFT, and PBFT. In this case, when calculating the communication overheads of double-layer PBFT, the node distribution is based on the equation N 3 + 3 N 2 + N = 2 M − 1 ( 3 ≤ N ≤ ( M − 4 ) / 3 ) given in [8], which has a minimum communication complexity of O(N4/3). Here, N and M denote the number of nodes in the network and the number of nodes within groups, respectively. Furthermore, in the actual calculation, the number of nodes within groups is taken as a positive integer closest to n. In the LTSBFT consensus algorithm, NL = 11, NS = 3, and S = 3. The comparison results of scalability are shown in Figure 5.

4.5. Communication Overheads Analysis under Attacks

Based on the LTSBFT consensus algorithm, the replica-layer nodes feedback the NodeID set of malicious nodes to the committee-layer nodes, which is embedded within the freply (sreply) messages. To determine the NodeID of malicious leaders, leaders, excluding the malicious ones, reach consensus on the NodeID set of malicious nodes during the generation of threshold signatures within the committee layer. Therefore, only leaders broadcasting freply (sreply) messages pose additional communication overheads. Assuming that malicious nodes do not broadcast the correct commit (scommit) messages to any node, the communication overheads to reach the consensus of malicious supervisory nodes are (NL − 1)(NL − 1)Z/NL  ≈ NLZ, and the communication overheads to reach the consensus of malicious leaders are (NL − 1)(NL − 1)Z/SNL  ≈ NLZ/S. Since the number of supervisory nodes is fewer, the communication overheads on sreply messages broadcasted by leaders can be ignored. Therefore, the communication complexity of the LTSBFT to reach consensus of malicious leaders is at linear level.
Based on the PBFT consensus algorithm, reaching consensus on malicious leaders requires followers to multicast evidence to the other followers, and therefore requires O(N3) communication complexity. Based on the double-layer PBFT consensus algorithm, the followers confirm malicious leaders within the group, and then the newly elected leader confirmation is embedded within the pre-prepare messages. Therefore, the communication complexity under attacks is O(NL3 + NL2M), where NL and M are the number of leaders and the number of followers within a group, respectively. Moreover, the replacement of leaders in double-layer PBFT will be more frequent than PBFT due to its multiple leaders.
In the HotStuff consensus algorithm, view-change requires O(N) communication complexity. Once the leader may not multicast prepareQC to replicas, nodes of unlocked view launch view-change to ensure liveness after awaiting a maximum network latency. In this case, the consensus efficiency will be reduced. Moreover, the HotStuff consensus algorithm may consecutively change f + 1 (where f = ⌊N/3 + 1⌋) views consensus to commit a request, which causes the consensus efficiency to decrease dramatically.
Although the LTSBFT consensus algorithm re-selects the leaders, resulting in a decrease in throughput, multiple groups simultaneously select leaders by mining, effectively improving the efficiency of selecting leaders. Followers mining to compete for the leader makes the followers with greater computational power more likely to be selected as leaders. Therefore, leaders will be less probable to encounter crash errors. Furthermore, the LTSBFT consensus algorithm only requires linear complexity to reach consensus on Byzantine leaders.

5. Experimental Results

In this section, we implement a test of the performance of the LTSBFT consensus protocol. We use the Golang programming language to implement LTSBFT by listening to multiple TCP ports on the same host to simulate a multi-nodes environment. Specifically, each node is assigned a local loopback address and different port numbers, with nodes communicating by TCP connections. The performance tests include two cases: (1) a performance test without faulty nodes; and (2) a performance test with faulty nodes. In order to simulate an impact on the network consensus in the presence of an attack scenario, a leader that sends commit messages to the replica-layer nodes is designated as a Byzantine node. The attack of Byzantine nodes on the execution of the LTSBFT consensus protocol is simulated by sending error consensus messages.
For the testing of the performance of the LTSBFT consensus algorithm, two critical indicators are included: (1) latency refers to the time (ms) elapsed from the client sending a request to the client receiving the latest reply; and (2) throughput refers to the number of consensus messages processed per second in the system (op/s). The performance of the LTSBFT consensus algorithm is evaluated by comparing it with the PBFT and HotStuff consensus algorithms under the same parameter configuration.

5.1. Latency Test

The latency comparison of the LTSBFT consensus algorithm with the HotStuff and PBFT consensus algorithms at the same number of nodes is shown in Figure 6. In this test, the LTSBFT consensus algorithm takes NL = 11, NS = 3, and S = 3. Starting with 66 nodes, the number of nodes in each group is increased by one each time to achieve a gradual increase in the number of nodes in the network.
The advantage of the LTSBFT consensus algorithm in terms of latency can be shown by Figure 6. The LTSBFT consensus is consistent with the HotStuff consensus algorithm, and their consensus latency increases linearly with the number of nodes. However, the communication latency of the LTSBFT consensus algorithm is lower than that of the HotStuff and PBFT consensus algorithms under the same number of nodes. Meanwhile, it can also be shown by Figure 6 that malicious attacks on Byzantine nodes do not cause a large impact on the communication latency of the LTSBFT consensus algorithm.
In order to test the effect of different node topologies on the latency performance, the LTSBFT consensus algorithm takes NS = 3, S = 3, and N = 135 and the followers are evenly distributed in each group. The consensus latency of the LTSBFT consensus algorithm is measured by varying the number of leaders, and the results are shown in Figure 7.
As can be shown in Figure 7, without changing the number of selected leaders who send commit messages to replica-layer nodes and the number of supervisory nodes, different numbers of leaders do not have a significant impact on the consensus latency. Moreover, in the case of varying the number of leaders, the attacks of the malicious leader who sends commit messages to Replica nodes does not have a significant impact on the consensus latency.
To test the effect of communication load on the consensus latency, the communication latency of client requests of different sizes for inter-node consensus is recorded. Without changing the node LTSBFT node topology and the number of nodes, the recorded results are shown in Figure 8. Here, the LTSBFT consensus algorithm takes NS = 3, S = 3, NL = 11, and N = 135. The HotStuff and PBFT consensus algorithms take N = 135.
As shown in Figure 8, the consensus latency increases steadily with the increase in communication load. Moreover, the consensus latency of the LTSBFT consensus algorithm is significantly lower than the consensus latency of the HotStuff and PBFT consensus algorithms, regardless of whether LTSBFT operates in the Byzantine scenario or not. Therefore, it can be concluded that the LTSBFT consensus algorithm has better latency performance compared to the HotStuff and PBFT consensus algorithms under different communication loads.

5.2. Throughput Test

The throughput performance is tested using the same number of nodes. The parallel processing capability of the LTSBFT consensus algorithm for transactions is evaluated by comparing the throughput of LTSBFT with that of the HotStuff and PBFT consensus algorithms. The throughput measurement results are shown in Figure 9. In this test, the LTSBFT consensus algorithm takes NL = 7, NS = 2, and S = 2. Starting with 42 nodes, the number of nodes in each group is increased by one each time to achieve a gradual increase in the number of nodes in the network.
It can be seen from Figure 9 that the throughput of the LTSBFT consensus algorithm is significantly greater than the throughput of the HotStuff and PBFT consensus algorithms. The attack of Byzantine nodes does not have a significant impact on the throughput of the LTSBFT consensus algorithm. Therefore, it can be concluded that the LTSBFT consensus algorithm has excellent parallel processing capability for transactions.
In order to test the effect of communication load on the throughput, the throughput of client requests of different sizes for inter-node consensus is recorded without changing the node LTSBFT node topology and the number of nodes. The recorded results are shown in Figure 10. The LTSBFT consensus algorithm takes NS = 2, S = 2, NL = 7, and N = 77. The HotStuff and PBFT consensus algorithms take N = 77.
As shown in Figure 10, the throughput decreases as the communication load increases. The throughput of the LTSBFT consensus algorithm is significantly higher than that of the HotStuff and PBFT consensus algorithms under different loads. Therefore, it can be concluded that the LTSBFT consensus algorithm has improved transaction parallel processing capability compared to the PBFT and HotStuff consensus algorithms under different communication loads.

6. Conclusions

In this paper, a low-latency scalable dynamic LTSBFT consensus algorithm with high fault tolerance is proposed. Firstly, the LTSBFT consensus algorithm achieves consensus linear complexity through the utilization of threshold signature technology. Secondly, the mutual supervision feedback mechanism among nodes ensures that reaching consensus on faulty upper-layer nodes during view changes is accomplished with linear complexity. Finally, a node dynamic protocol is proposed for the first time to support dynamic changes in the number of nodes during the consensus process. That is to say, consensus can still be reached when the number of nodes dynamically changes, without interrupting the client’s request for consensus in the network. The LTSBFT can be used in various fields such as the Internet of Things or blockchains. However, it still has some deficiencies, such as the problem of efficiency under attacks. Once most nodes corporately launch an attack in the committee layer, the LTSBFT will transform to the PBFT consensus algorithm, resulting in performance degeneration. Thus, in the future, we will improve its ability in resisting collusion attacks.

Author Contributions

Conceptualization, A.L.; Methodology, A.L.; Software, A.L.; Validation, X.X.; Resources, Y.Y.; Project administration, X.X. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Lu, Y. The blockchain: State-of-the-art and research challenges. J. Ind. Inf. Integr. 2019, 15, 80–90. [Google Scholar] [CrossRef]
  2. Qi, J.; Guan, Y. Practical Byzantine fault tolerance consensus based on comprehensive reputation. Peer-Peer Netw. Appl. 2023, 20, 420–430. [Google Scholar] [CrossRef]
  3. Castro, M.; Liskov, B. Practical Byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst. 2002, 20, 398–461. [Google Scholar] [CrossRef]
  4. Castro, M.; Liskov, B. Practical Byzantine fault tolerance consensus. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, New Orleans, LA, USA, 21–25 February 1999; pp. 173–186. [Google Scholar]
  5. Gervais, A.; Karame, G.O.; Wüst, K.; Glykantzis, V.; Ritzdorf, H.; Capkun, S. On the Security and Performance of Proof of Work Blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016; pp. 3–16. [Google Scholar] [CrossRef]
  6. Bentov, I.; Lee, C.; Mizrahi, A.; Rosenfield, M. Proof of Activity: Extending Bitcoin’s Proof of Work via Proof of Stake. ACM Sigmetrics Perform. Eval. Rev. 2014, 42, 34–37. [Google Scholar] [CrossRef]
  7. Larimer, D. Delegated Proof of Stake (DPoS). 2014. Available online: https://www.weusecoins.com/assets/pdf/library/Delegated%20Proof-of-Stake%20Consensus.pdf (accessed on 23 August 2024).
  8. Li, W.; Feng, C.; Zhang, L.; Xu, H.; Cao, B.; Imran, M.A. A Scalable Multi-Layer PBFT Consensus for Blockchain. IEEE Trans. Parallel Distrib. Syst. 2021, 32, 1146–1160. [Google Scholar] [CrossRef]
  9. Jiang, W.; Wu, X.; Song, M.; Qin, J.; Jia, Z. A Scalable Byzantine Fault Tolerance Algorithm Based on a Tree Topology Network. IEEE Access 2023, 11, 33509–33519. [Google Scholar] [CrossRef]
  10. Li, C.; Zhang, J.; Yang, X. Scalable blockchain storage mechanism based on two-layer structure and improved distributed consensus. J. Supercomput. 2022, 78, 4850–4881. [Google Scholar] [CrossRef]
  11. Gao, S.; Yu, T.; Zhu, J.; Cai, W. T-PBFT: An EigenTrust-Based Practical Byzantine Fault Tolerance Consensus Algorithm. IEEE China Commun. 2019, 16, 111–123. [Google Scholar] [CrossRef]
  12. Yin, M.; Malkhi, D.; Reiter, M.K.; Gueta, G.G.; Abraham, I. HotStuff: BFT consensus in the lens of blockchain. arXiv 2018, arXiv:1803.05069. [Google Scholar]
  13. Jalalzai, M.M.; Niu, J.; Feng, C.; Gai, F. Fast-hotstuff: A fast and robust bft protocol for blockchains. IEEE Trans. Dependable Secur. Comput. 2024, 21, 2478–2493. [Google Scholar] [CrossRef]
  14. Malkhi, D.; Nayak, K. HotStuff-2: Optimal Two-Phase Responsive BFT. Paper 2023/397. Cryptology ePrint Archive. 2023. Available online: https://eprint.iacr.org/2023/397.pdf (accessed on 23 August 2024).
  15. Abraham, I.; Malkhi, D.; Nayak, K.; Ren, L.; Yin, M. Sync hotstuff: Simple and practical synchronous state machine replication. In Proceedings of the 2020 IEEE Symposium on Security and Privacy (SP), Virtual Conference, 18–20 May 2020; pp. 106–118. [Google Scholar]
  16. Shoup, V. Practical Threshold Signatures. In Advances in Cryptology—EUROCRYPT 2000; Preneel, B., Ed.; Springer: Berling/Heidelberg, Germany, 2000; pp. 207–220. [Google Scholar] [CrossRef]
  17. Zhang, Z.; Xu, C.; Jiang, C.; Chen, K. TSAPP: Threshold Single-Sign-On Authentication Preserving Privacy. IEEE Trans. Dependable Secur. Comput. 2023, 14, 1515–1527. [Google Scholar] [CrossRef]
  18. Shi, R.; Feng, H.; Yang, Y.; Yuan, F.; Li, Y.; Pang, H.H.; Deng, R.H. Threshold Attribute-Based Credentials with Redactable Signature. IEEE Trans. Serv. Comput. 2023, 16, 3751–3765. [Google Scholar] [CrossRef]
  19. Lei, K.; Zhang, Q.; Xu, L.; Qi, Z. Reputation-Based Byzantine Fault-Tolerance for Consortium Blockchain. In Proceedings of the 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS), Singapore, 11–19 December 2018; pp. 604–611. [Google Scholar] [CrossRef]
  20. Kotla, R.; Alvisi, L.; Dahlin, M.; Clement, A.; Wong, E. Zyzzyva: Speculative byzantine fault tolerance. In Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles, Stevenson, WA, USA, 14–17 October 2007. [Google Scholar]
  21. Kwon, J. Tendermint: Consensus without mining. Draft V. 0.6 2014, 1, 11. [Google Scholar]
  22. Zhang, Z.; Liu, X.; Li, M.; Yin, H.; Zhu, L.; Khoussainov, B.; Gai, K. HCA: Hashchain-based Consensus Acceleration via Re-voting. IEEE Trans. Dependable Secur. Comput. 2023, 21, 775–788. [Google Scholar] [CrossRef]
  23. Hao, X.; Yu, L.; Zhiqiang, L.; Zhen, L.; Dawu, G. Dynamic practical byzantine fault tolerance. In Proceedings of the 2018 IEEE Conference on Communications and Network Security (CNS), Beijing, China, 30 May–1 June 2018; pp. 1–8. [Google Scholar]
  24. Yang, J.; Jia, Z.; Su, R.; Wu, X.; Qin, J. Improved Fault-Tolerant Consensus Based on the PBFT Algorithm. IEEE Access 2022, 10, 30274–30283. [Google Scholar] [CrossRef]
  25. Boneh, D.; Gentry, C.; Lynn, B.; Shacham, H. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In Proceedings of the 22nd International Conference on Theory and Application of Cryptology and Information Security, Warsaw, Poland, 4–8 May 2003; pp. 416–432. [Google Scholar]
  26. Liu, Y.; Xing, X.; Cheng, H.; Li, D.; Guan, Z.; Liu, J.; Wu, Q. A Flexible Sharding Blockchain Protocol Based on Cross-Shard Byzantine Fault Tolerance. IEEE Trans. Inf. Forensics Secur. 2023, 18, 2276–2291. [Google Scholar] [CrossRef]
  27. Chen, X. Scaling Byzantine Fault-Tolerant Consensus with Optimized Shading Scheme. IEEE Trans. Ind. Inform. 2023, 20, 3401–3412. [Google Scholar] [CrossRef]
  28. Liu, Y.; Liu, J.; Wu, Q.; Yu, H.; Hei, Y.; Zhou, Z. SSHC: A secure and scalable hybrid consensus protocol for sharding blockchains with a formal security framework. IEEE Trans. Dependable Secur. Comput. 2020, 19, 2070–2088. [Google Scholar] [CrossRef]
  29. Long, J.; Wei, R. Scalable BFT consensus mechanism through aggregated signature gossip. In Proceedings of the 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), Seoul, Republic of Korea, 14–17 May 2019; pp. 360–367. [Google Scholar]
  30. Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D. Randomized gossip algorithms. IEEE Trans. Inf. Theory 2006, 52, 2508–2530. [Google Scholar] [CrossRef]
  31. Lamport, L. The Part-Time Parliament. ACM Trans. Comput. Syst. 1998, 16, 133–169. [Google Scholar] [CrossRef]
  32. Ongaro, D.; Ousterhout, J.K. In Search of an Understandable Consensus Algorithm. In Proceedings of the 2014 USENIX Annual Technical Conference, Philadelphia, PA, USA, 19–20 June 2014. [Google Scholar]
Mathematics 12 02643 g001
Figure 1. The node division structure.
Figure 1. The node division structure.
Mathematics 12 02643 g001
Mathematics 12 02643 g002
Figure 2. The flow chart of the LTSBFT algorithm.
Figure 2. The flow chart of the LTSBFT algorithm.
Mathematics 12 02643 g002
Mathematics 12 02643 g003
Figure 3. Operation flow of LTSBFT algorithm (the red arrow denotes the interactions between intra-group nodes with leaders; the blue arrow denotes the interactions between intra-group nodes with supervisory nodes).
Figure 3. Operation flow of LTSBFT algorithm (the red arrow denotes the interactions between intra-group nodes with leaders; the blue arrow denotes the interactions between intra-group nodes with supervisory nodes).
Mathematics 12 02643 g003
Mathematics 12 02643 g004
Figure 4. LTSBFT security analysis.
Figure 4. LTSBFT security analysis.
Mathematics 12 02643 g004
Mathematics 12 02643 g005
Figure 5. Scalability comparison.
Figure 5. Scalability comparison.
Mathematics 12 02643 g005
Mathematics 12 02643 g006
Figure 6. Consensus latency comparison under different number of nodes.
Figure 6. Consensus latency comparison under different number of nodes.
Mathematics 12 02643 g006
Mathematics 12 02643 g007
Figure 7. Consensus latency comparison under different number of leaders.
Figure 7. Consensus latency comparison under different number of leaders.
Mathematics 12 02643 g007
Mathematics 12 02643 g008
Figure 8. Consensus latency comparison under different load size.
Figure 8. Consensus latency comparison under different load size.
Mathematics 12 02643 g008
Mathematics 12 02643 g009
Figure 9. Throughput comparison under different number of nodes.
Figure 9. Throughput comparison under different number of nodes.
Mathematics 12 02643 g009
Mathematics 12 02643 g010
Figure 10. Throughput comparison under different payload sizes.
Figure 10. Throughput comparison under different payload sizes.
Mathematics 12 02643 g010
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Li, A.; Yao, Y.; Xu, X. Dynamic Byzantine Fault-Tolerant Consensus Algorithm with Supervised Feedback Mechanisms. Mathematics 2024, 12, 2643. https://doi.org/10.3390/math12172643

AMA Style

Li A, Yao Y, Xu X. Dynamic Byzantine Fault-Tolerant Consensus Algorithm with Supervised Feedback Mechanisms. Mathematics. 2024; 12(17):2643. https://doi.org/10.3390/math12172643

Chicago/Turabian Style

Li, Anqi, Yingbiao Yao, and Xin Xu. 2024. "Dynamic Byzantine Fault-Tolerant Consensus Algorithm with Supervised Feedback Mechanisms" Mathematics 12, no. 17: 2643. https://doi.org/10.3390/math12172643

APA Style

Li, A., Yao, Y., & Xu, X. (2024). Dynamic Byzantine Fault-Tolerant Consensus Algorithm with Supervised Feedback Mechanisms. Mathematics, 12(17), 2643. https://doi.org/10.3390/math12172643

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop