# Lodestone: An Efficient Byzantine Fault-Tolerant Protocol in Consortium Blockchains

Authors: Chen Shan; Lei Fan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

We present Lodestone, a chain-based Byzantine fault-tolerant (BFT) state machine replication (SMR) protocol under partial synchrony. Lodestone enables replicas to achieve consensus with two phases of voting and enjoys (1) optimistic responsiveness and (2) linear communication complexity on average. Similar to the state-of-the-art chain-based BFT protocols, Lodestone can be optimized with a pipelining idea elegantly. We implement pipelined Lodestone and deploy experiments to evaluate its performance. The evaluation results demonstrate that Lodestone has a lower latency than HotStuff under various workloads.


---

## Body

## 1. Introduction

Consensus in blockchain systems, known as state machine replication (SMR), has attracted more and more interest in recent years. When focusing on permissioned blockchains on so-called consortium blockchains, chain-based Byzantine fault-tolerant (BFT) SMR protocols [1–8] under partial synchrony have been widely used to achieve consistency. In general, chain-based BFT SMR protocols follow the conventional propose-vote paradigm where there exists a special role often called leader who is responsible for packing clients’ requests into proposals, and then all players achieve consensus on these proposals via multiple (two or three) phases of voting.PBFT [9], as the first practical BFT SMR protocol under the partial synchronous network [10], achieves safety even under the asynchronous network and liveness when the network gets synchronous. However, the view-change subprotocol in PBFT, with an On3 communication complexity, is too heavy to be practical. Tendermint [6] innovatively employs a lock-commit scheme, similar to the paradigm in [11], that a replica should lock on the proposal he has voted COMMIT for. This allows one replica to decide if voting for one proposal according to his own local states and the leader has no need to prove the safety of his proposal. Casper [7, 8] takes a similar strategy and also implies a pipelining idea for a further improvement. However, both Tendermint and Casper sacrifice optimistic responsiveness in that there needs to be a fixed interval between proposals to guarantee liveness since a new leader has to ensure that he has observed all other nonfaulty replicas’ lock state; otherwise, his new proposal may not be accepted. HotStuff [1] creatively introduces another phase of vote to achieve both linear view-change and optimistic responsiveness. The additional phase guarantees that a new leader can construct this proposal safely only with n−f replicas’ states. However, in pipelined HotStuff, the three-phase voting scheme not only brings about an increase in latency but also causes an implicit liveness problem. In pipelined HotStuff, there needs to be four consecutive nonfaulty leaders to make a decision which cannot be guaranteed in the n=3f+1 setting. This means pipelined HotStuff cannot provide liveness in the worst case even under the crash fault-tolerant model, which has also been discussed as the silence attack [12].We present Lodestone, a novel chain-based BFT SMR protocol, which achieves the following combined properties under partial synchrony:(1)
Two-phase voting with optimistic responsiveness: Lodestone can achieve responsiveness when liveness is guaranteed after GST. That is, the total time of confirmation on one honest leader’s proposal only relies on the actual network delay instead of any apriori upper bound assumption of network delay.(2)
Linear average-case communication complexity: a view-change subprocess in Lodestone costsOn message complexity on average and On2 in the worst case. Here, we follow the measurement of message complexity in HotStuff [1] which counts the total number of authenticators received by one player in the protocol to achieve a decision.(3)
Deterministic liveness under static corruption: pipelined Lodestone can also achieve deterministic liveness under static corruption where leaders are rotated in a round-robin manner.The difference in detail between these protocols can be shown in figures, of which Figures1 and 2 show HotStuff and existing two-phase voting protocols, respectively, while Figure 3 demonstrates our solution.Figure 1
Pipelined HotStuff.b1,b2,b3,andb4 are in the normal case, while b1,b2,b3′,andb4′ are in the timeout case. In the timeout case, nonfaulty replicas who have received b3′ will lock on b1 but will still vote for b4′ since b4′ also extends from b1.Figure 2
Casper or the two-chain variant of pipelined HotStuff.b1,b2,b3,andb4 are in the normal case, while b1,b2,b3′,andb4′ are in the timeout case. In the timeout case, the leader of b4′ did not receive b3′ in time, while some nonfaulty replicas received b3′ and have locked on b2. Therefore, they would not vote for b4′ since b4′ conflicts with b2.Figure 3
Pipelined Lodestone.b1,b2,b3,andb4 are in the normal case, while b1,b2,b3′,andb4′ are in the timeout case. In the timeout case, the leader of b4′ will attach a proof to his proposal which allows nonfaulty replicas who have locked on b2′ to get unlocked and vote for b4′.


## 2. Other Related Works

### 2.1. BFT SMR Protocols in Alternative Assumptions

There are also many works considering about BFT protocols in alternative assumptions.Firstly, about the network assumption, many recent protocols under a synchronous network [13–15] or under an asynchronous network [16–18] make efforts to reduce confirmation latency and achieve practical throughput. Secondly, about the corruption assumption, some recent works [19, 20] are aimed to provide higher assurance on blocks even if the adversary corrupts more than f replicas in the future. In this paper, we only concentrate on static security under a partially synchronous network.


### 2.2. Single-Shot BFT Protocols

There are some related works [21–23] focusing on the single-shot BFT problem which explore the optimal latency bound when the leader is nonfaulty under various resilience assumptions. Though it is still a long way to construct a protocol from single shot to multishots, some results are interesting and may be combined with our protocols in the future work.


### 2.3. View Synchronization

Another related line of work is about view synchronization [24–26] in the partial synchrony setting. It is also necessary in Lodestone for nonfaulty replicas to stay in the same view for a sufficient long time, and then liveness can be guaranteed. However, view synchronization is not the key point of Lodestone, and we assume that replicas are able to stay in the same view for a sufficient long time after GST.


## 2.1. BFT SMR Protocols in Alternative Assumptions

There are also many works considering about BFT protocols in alternative assumptions.Firstly, about the network assumption, many recent protocols under a synchronous network [13–15] or under an asynchronous network [16–18] make efforts to reduce confirmation latency and achieve practical throughput. Secondly, about the corruption assumption, some recent works [19, 20] are aimed to provide higher assurance on blocks even if the adversary corrupts more than f replicas in the future. In this paper, we only concentrate on static security under a partially synchronous network.


## 2.2. Single-Shot BFT Protocols

There are some related works [21–23] focusing on the single-shot BFT problem which explore the optimal latency bound when the leader is nonfaulty under various resilience assumptions. Though it is still a long way to construct a protocol from single shot to multishots, some results are interesting and may be combined with our protocols in the future work.


## 2.3. View Synchronization

Another related line of work is about view synchronization [24–26] in the partial synchrony setting. It is also necessary in Lodestone for nonfaulty replicas to stay in the same view for a sufficient long time, and then liveness can be guaranteed. However, view synchronization is not the key point of Lodestone, and we assume that replicas are able to stay in the same view for a sufficient long time after GST.


## 3. Materials and Methods

### 3.1. Models

(1)
Threat model: we consider a permissioned system consisting ofn replicas, indexed by i∈n, where n=1,2,…,n. We assume a polynomially bounded adversary who can corrupt less than n/3 replicas. The replicas corrupted by the adversary can deviate from the prescribed protocol arbitrarily within their capabilities which are also called Byzantine faulty replicas, while the remaining ones are nonfaulty. We only consider a static corruption model in that the adversary chooses which replicas to corrupt prior to the execution.(2)
Network model: we assume that each pair of replicas is connected by a reliable authenticated point-to-point channel. Messages are propagated through a partially synchronous network [10] in that there is an unknown global stabilization time (GST). After GST, a message sent by a nonfaulty replica will be delivered to all nonfaulty replicas with a known bound Δ, though the delivery schedule is determined by the adversary.(3)
Cryptographic primitives: we assume a cryptographic hash functionHashm and a standard digital signature scheme. We also assume a (t, n) threshold signature scheme [27, 28] which provides the following interfaces:ThresholdSetup1λ generates a pair of key shares pki,ski for replica i along with a global public key PK.ThresholdSignim produces a signature share λi of message m with ski.ThresholdVerifySharem,i,λi verifies if λi is a valid signature share of message m.ThresholdCombinem,i,λi,i∈I produces the threshold signature λ of message m from t signature shares where I⊂n and I=t.ThresholdVerifym,λ verifies if λ is a valid threshold signature of message m with PK.We use an (n − f, n) threshold signature scheme in our following protocols which is assumed to provide robustness and nonforgeability.(4)
Problem definition: we now give the definition of a chain-based BFT SMR protocol. Each replica in a chain-based BFT SMR protocol receives requests from clients and maintains a sequence of blocks called a blockchain. Blocks in a blockchain are chained by hash digest, and thus, each block in a blockchain has its own position denoted as its height. Given a blockchainC and a block b∈C, all blocks in C lower than b are ancestor blocks of b, and all blocks in C higher than b are descendant blocks of b. Two blocks b1 and b2 are conflicting if and only if b1 is neither an ancestor nor a descendant block of b2. Each block includes a batch of requests, and one replica's blockchain consists of all blocks which have been finalized. Replicas execute requests in finalized blocks in the sequence of the blockchain and then respond to clients. For simplicity, we do not model clients and assume all requests are sent to all replicas. Thus, we say requests from clients are input to all replicas, and at any time, the output of one replica is his blockchain.A secure chain-based BFT SMR protocol should satisfy both safety and liveness defined below (in the presence of an arbitrary adversary with all but negligible probability).Definition 1.
(safety). At any time, if two nonfaulty replicas each have their blockchains denoted asC1 and C2, then it must be either C1≼C2 or C2≼C1, where ≼ means “is a prefix of or equal to.” In other words, two nonfaulty replicas will never finalize different blocks at the same height.Definition 2.
(liveness). If a requestreq has been inputted to all replicas at time t>Tstart, then at time t+Tconfirm, any nonfaulty replica must output a blockchain which includes req, where Tstart is the time after which the protocol provides liveness and Tconfirm is a bounded constant.


### 3.2. Preliminaries

(1)
Block: we now format a blockb in our protocol as b=parent, view, txs, and hash where parent is the hash digest of the parent block of b, view is the view in which b is proposed, txs is a batch of requests from clients, and hash is the hash digest of b (i.e., b.hash=Hashb.parent,b.view,b.txs). In Lodestone, there are three states for one block, namely, PROPOSED, PREPARED, and COMMITTED. Once a block reaches the COMMITTED state, then the block itself and its all ancestor blocks are finalized and can be executed sequentially.(2)
Local states: replicas in Lodestone need to maintain two local states for the protocol execution. The first denoted ascurrView represents the current view number and implies the current leader. It is noted that using the round-robin manner to rotate leaders guarantees that (i) the protocol will be greeted with a nonfaulty leader after at most f consecutive views; (ii) there exist three consecutive views of which leaders are all nonfaulty which will be proved later. The second is lockedQC which stores qc with the largest view number one replica has voted commit for. Once a nonfaulty replica locks on qc (i.e., sets lockedQC as qc), he will only vote for blocks extending from block b that Hashb=qc.hash unless he ensures the majority of nonfaulty replicas have turned to a conflicting branch before locking on qc.(3)
Promise and promise-set: during a view-change, each replica additionally sends to the leader apromise, evidence that helps the leader locate the highest COMMITTED block and prove that he does so in an honest manner. A promise for view v indicates that the replica has not voted commit at view v. If n− f replicas send promises for the view v, then there is no block which has a larger view number than v could be COMMITTED. When the leader proposes a block with the n− f promises, all the nonfaulty replicas can accept it safely. A promise from replica P includes a tuple v,v^ and the corresponding signature share σ=ThresholdSignv,v^ from P. We denote p=v,v^,σ for simplicity. We say p from P for the current view v^ represents that he did not vote commit when he was in the view v. Let v˜ be the last view in which P has voted commit. P will generate a set of promises for each view from v˜+1 to currView. We denote it as a promise-set.(4)
NullQC: before entering a new view, each nonfaulty replicaPi will send his promise-set promise-set to the new leader, along with his lockedQC. Upon receiving valid promise-sets from n− f distinct replicas, the new leader will select lockedQC with the largest view number as highQC and propose his new block following the block b where Hashb=highQC.hash. Let I be the set of indexes of the n− f replicas; we have I=n−f. We use v^ to denote currView and v˜ to denote highQC.view. Each promise-set must contain a promise that promiseiv^,v˜+1=v˜+1,v^,λiv^,v˜+1 where i∈I. The new leader can combine these n−f signature shares as a threshold signature to prove that highQC he selected is exactly the one with the largest view number among n−f replicas. This extra proof is denoted as nullQC in Lodestone. We have nullQC=ThresholdCombinev˜+1,v^,λiv^,v˜+1, where i∈I.


### 3.3. Pipelined Lodestone

We are now ready to describe our protocol pipelined Lodestone. We first define some utilities as shown in Figure4.Figure 4
Utilities in the pipelined Lodestone protocol.Then, we formalize pipelined Lodestone with algorithms. The protocol runs in a succession of views denoted ascurrView. Each view number is mapped into a leader in a round-robin manner. The leader will execute Algorithm 1, all replicas will execute Algorithm 2, and then the next leader will execute Algorithm 3. When timeout triggers during any wait-for procedure in one replica’s local view, he will execute Algorithm 4. We omit any check for brevity.Algorithm 1: Pipelined Lodestone protocol: as the leader of currView.
(1)
Wait forn−f VIEW-CHANGE message m∈M of currView-1(2)
highQC←argmaxm∈Mm.qc.view(3)
iflockedQC.view<highQC.view(4)
lockedQC←highQC(5)
T^←m.proof|m∈(6)
nullQC←NullQChighQC.view+1,currView,T^(7)
b←BLOCKcurrView,lockedQC.hash(8)
Broadcast MSG (PROPOSE, b,lockedQC, NullQC)Algorithm 2: Pipelined Lodestone protocol: as a replica Pi of currView.
(1)
Wait for RROPOSE messagem from LEADER (currView)(2)
b←m.block(3)
ifm.qc.view + 1 = m.proof.view.(4)
v←VOTEcurrView,b,hash,i(5)
send MSG(GENERIC, b, hash,⊥, v) to LEADER (currView + 1).(6)
ifm.qc.view > lockedQC.view(7)
lockedQC←m.qc(8)
b′←b.parent,b″←b′.parent(9)
ifb″.view+1=b′parent(10)
DECIDE (b″)Algorithm 3: Pipelined Lodestone protocol: as the next leader of currView.
(1)
Wait forn−f matched GENERIC messages M^ of CurrView(2)
hash←m^.block,∀m^∈M^(3)
V^←m^.proof|m^∈M^(4)
lockedQC←QCcurrView,hash,V^Algorithm 4: Pipelined Lodestone protocol: TimeOut currView.
Jump here if TIMEOUT triggers during any wait procedure or before entering currView+1(1)
T←PROOFlockedQC.view+1,currView+1,i(2)
send MSG (VIEW-CHANGE,⊥, lockedQC, T) to LEADER (currView + 1)


## 3.1. Models

(1)
Threat model: we consider a permissioned system consisting ofn replicas, indexed by i∈n, where n=1,2,…,n. We assume a polynomially bounded adversary who can corrupt less than n/3 replicas. The replicas corrupted by the adversary can deviate from the prescribed protocol arbitrarily within their capabilities which are also called Byzantine faulty replicas, while the remaining ones are nonfaulty. We only consider a static corruption model in that the adversary chooses which replicas to corrupt prior to the execution.(2)
Network model: we assume that each pair of replicas is connected by a reliable authenticated point-to-point channel. Messages are propagated through a partially synchronous network [10] in that there is an unknown global stabilization time (GST). After GST, a message sent by a nonfaulty replica will be delivered to all nonfaulty replicas with a known bound Δ, though the delivery schedule is determined by the adversary.(3)
Cryptographic primitives: we assume a cryptographic hash functionHashm and a standard digital signature scheme. We also assume a (t, n) threshold signature scheme [27, 28] which provides the following interfaces:ThresholdSetup1λ generates a pair of key shares pki,ski for replica i along with a global public key PK.ThresholdSignim produces a signature share λi of message m with ski.ThresholdVerifySharem,i,λi verifies if λi is a valid signature share of message m.ThresholdCombinem,i,λi,i∈I produces the threshold signature λ of message m from t signature shares where I⊂n and I=t.ThresholdVerifym,λ verifies if λ is a valid threshold signature of message m with PK.We use an (n − f, n) threshold signature scheme in our following protocols which is assumed to provide robustness and nonforgeability.(4)
Problem definition: we now give the definition of a chain-based BFT SMR protocol. Each replica in a chain-based BFT SMR protocol receives requests from clients and maintains a sequence of blocks called a blockchain. Blocks in a blockchain are chained by hash digest, and thus, each block in a blockchain has its own position denoted as its height. Given a blockchainC and a block b∈C, all blocks in C lower than b are ancestor blocks of b, and all blocks in C higher than b are descendant blocks of b. Two blocks b1 and b2 are conflicting if and only if b1 is neither an ancestor nor a descendant block of b2. Each block includes a batch of requests, and one replica's blockchain consists of all blocks which have been finalized. Replicas execute requests in finalized blocks in the sequence of the blockchain and then respond to clients. For simplicity, we do not model clients and assume all requests are sent to all replicas. Thus, we say requests from clients are input to all replicas, and at any time, the output of one replica is his blockchain.A secure chain-based BFT SMR protocol should satisfy both safety and liveness defined below (in the presence of an arbitrary adversary with all but negligible probability).Definition 1.
(safety). At any time, if two nonfaulty replicas each have their blockchains denoted asC1 and C2, then it must be either C1≼C2 or C2≼C1, where ≼ means “is a prefix of or equal to.” In other words, two nonfaulty replicas will never finalize different blocks at the same height.Definition 2.
(liveness). If a requestreq has been inputted to all replicas at time t>Tstart, then at time t+Tconfirm, any nonfaulty replica must output a blockchain which includes req, where Tstart is the time after which the protocol provides liveness and Tconfirm is a bounded constant.


## 3.2. Preliminaries

(1)
Block: we now format a blockb in our protocol as b=parent, view, txs, and hash where parent is the hash digest of the parent block of b, view is the view in which b is proposed, txs is a batch of requests from clients, and hash is the hash digest of b (i.e., b.hash=Hashb.parent,b.view,b.txs). In Lodestone, there are three states for one block, namely, PROPOSED, PREPARED, and COMMITTED. Once a block reaches the COMMITTED state, then the block itself and its all ancestor blocks are finalized and can be executed sequentially.(2)
Local states: replicas in Lodestone need to maintain two local states for the protocol execution. The first denoted ascurrView represents the current view number and implies the current leader. It is noted that using the round-robin manner to rotate leaders guarantees that (i) the protocol will be greeted with a nonfaulty leader after at most f consecutive views; (ii) there exist three consecutive views of which leaders are all nonfaulty which will be proved later. The second is lockedQC which stores qc with the largest view number one replica has voted commit for. Once a nonfaulty replica locks on qc (i.e., sets lockedQC as qc), he will only vote for blocks extending from block b that Hashb=qc.hash unless he ensures the majority of nonfaulty replicas have turned to a conflicting branch before locking on qc.(3)
Promise and promise-set: during a view-change, each replica additionally sends to the leader apromise, evidence that helps the leader locate the highest COMMITTED block and prove that he does so in an honest manner. A promise for view v indicates that the replica has not voted commit at view v. If n− f replicas send promises for the view v, then there is no block which has a larger view number than v could be COMMITTED. When the leader proposes a block with the n− f promises, all the nonfaulty replicas can accept it safely. A promise from replica P includes a tuple v,v^ and the corresponding signature share σ=ThresholdSignv,v^ from P. We denote p=v,v^,σ for simplicity. We say p from P for the current view v^ represents that he did not vote commit when he was in the view v. Let v˜ be the last view in which P has voted commit. P will generate a set of promises for each view from v˜+1 to currView. We denote it as a promise-set.(4)
NullQC: before entering a new view, each nonfaulty replicaPi will send his promise-set promise-set to the new leader, along with his lockedQC. Upon receiving valid promise-sets from n− f distinct replicas, the new leader will select lockedQC with the largest view number as highQC and propose his new block following the block b where Hashb=highQC.hash. Let I be the set of indexes of the n− f replicas; we have I=n−f. We use v^ to denote currView and v˜ to denote highQC.view. Each promise-set must contain a promise that promiseiv^,v˜+1=v˜+1,v^,λiv^,v˜+1 where i∈I. The new leader can combine these n−f signature shares as a threshold signature to prove that highQC he selected is exactly the one with the largest view number among n−f replicas. This extra proof is denoted as nullQC in Lodestone. We have nullQC=ThresholdCombinev˜+1,v^,λiv^,v˜+1, where i∈I.


## 3.3. Pipelined Lodestone

We are now ready to describe our protocol pipelined Lodestone. We first define some utilities as shown in Figure4.Figure 4
Utilities in the pipelined Lodestone protocol.Then, we formalize pipelined Lodestone with algorithms. The protocol runs in a succession of views denoted ascurrView. Each view number is mapped into a leader in a round-robin manner. The leader will execute Algorithm 1, all replicas will execute Algorithm 2, and then the next leader will execute Algorithm 3. When timeout triggers during any wait-for procedure in one replica’s local view, he will execute Algorithm 4. We omit any check for brevity.Algorithm 1: Pipelined Lodestone protocol: as the leader of currView.
(1)
Wait forn−f VIEW-CHANGE message m∈M of currView-1(2)
highQC←argmaxm∈Mm.qc.view(3)
iflockedQC.view<highQC.view(4)
lockedQC←highQC(5)
T^←m.proof|m∈(6)
nullQC←NullQChighQC.view+1,currView,T^(7)
b←BLOCKcurrView,lockedQC.hash(8)
Broadcast MSG (PROPOSE, b,lockedQC, NullQC)Algorithm 2: Pipelined Lodestone protocol: as a replica Pi of currView.
(1)
Wait for RROPOSE messagem from LEADER (currView)(2)
b←m.block(3)
ifm.qc.view + 1 = m.proof.view.(4)
v←VOTEcurrView,b,hash,i(5)
send MSG(GENERIC, b, hash,⊥, v) to LEADER (currView + 1).(6)
ifm.qc.view > lockedQC.view(7)
lockedQC←m.qc(8)
b′←b.parent,b″←b′.parent(9)
ifb″.view+1=b′parent(10)
DECIDE (b″)Algorithm 3: Pipelined Lodestone protocol: as the next leader of currView.
(1)
Wait forn−f matched GENERIC messages M^ of CurrView(2)
hash←m^.block,∀m^∈M^(3)
V^←m^.proof|m^∈M^(4)
lockedQC←QCcurrView,hash,V^Algorithm 4: Pipelined Lodestone protocol: TimeOut currView.
Jump here if TIMEOUT triggers during any wait procedure or before entering currView+1(1)
T←PROOFlockedQC.view+1,currView+1,i(2)
send MSG (VIEW-CHANGE,⊥, lockedQC, T) to LEADER (currView + 1)


## 4. Safety, Liveness, and Communication Complexity

### 4.1. Safety

Lemma 1.
For any two valid quorum certificatesqc1 and qc2, if qc1⋅view=qc2⋅view, then qc1⋅block=qc2⋅block.Proof.
For any validqc, at least n−2f nonfaulty replicas have sent their relevant signature shares, namely, at least n−2f nonfaulty replicas have voted for the block which qc.block represents in qc.view. Suppose qc1 and qc2 are two valid qc such that qc1⋅view=qc2⋅view, but qc1⋅block≠qc2⋅block. We must have that at least n−2f nonfaulty replicas voted for the qc1⋅block and also at least n−2f nonfaulty replicas voted for the qc2⋅block in the same view. Thus, the intersection of the two sets at least includes one nonfaulty replica since 2×n−2f>n−f, a contradiction to Algorithm 2 that a nonfaulty replica can only vote once in a view.Theorem 1.
In pipelined Lodestone, two conflicting blocks cannot be both COMMITTED.Proof.
Letb1 and b2 be two conflicting blocks which are both COMMITTED, namely, there exists a two-chain b_1,b_1′,b_1″ and also one in the form of b_2,b_2′,b_2′. W.l.o.g, we can assume that b2⋅view>b1′⋅view with Lemma 1. Since b1 is COMMITTED, at least n−2f nonfaulty replicas have voted for b_1' and then locked on b1. Let b^ be the PREPARED block with the smallest view number that satisfies b^.view>b1′.view, and b^ conflicts with b1. Such b^ must exist since b2 satisfies all these conditions. Now, consider the proposal m of b^. At least n−2f nonfaulty replicas have locked on b1 in b1′⋅view. These n−2f nonfaulty replicas will only promise on view number larger than b1⋅view since then. Therefore, m⋅proof⋅view>b1⋅view. And due to the minimality of b^, we must have m⋅qc.view<b1⋅view. Then, m.proof.view>m.qc.view+1, a contradiction to the validity of nullQC.


### 4.2. Liveness

Lemma 2.
Under ann=3f+1 setting where leaders are rotated in a round-robin manner, in any consecutive n+2 views, there are three consecutive views all leaded by nonfaulty replicas.Proof.
Consider anyn consecutive views denoted as v,v+1,v+2,…,v+n−1. There are three cases:(i)
The leader ofv is faulty. Then, for the view from v + 1 to v + n −1, there are f− 1 faulty leaders while 2f+1 nonfaulty leaders. The f−1 faulty leaders can at most separate 2f+1 nonfaulty leaders into f segments, with at least one segment owning 3 nonfaulty leaders.(ii)
The leader ofv is nonfaulty, while the leader of v + 1 is faulty. Then, for the view from v + 2 to v + n, there are f−1 faulty leaders while 2f+1 nonfaulty leaders. Then, the situation becomes the same as the first case.(iii)
Bothv and v + 1 are leaded by nonfaulty leaders. Then, if the leader of v + 2 is nonfaulty, three consecutive nonfaulty leaders exist. Otherwise, for the view from v + 3 to v + n +1, there are f−1 faulty leaders while 2f+1 nonfaulty leaders. Then, the situation becomes the same as the first case.Lemma 3.
If a nonfaulty leader of view v collectsn− f valid view-change messages, he can always propose his new block, along with valid nullQC that nullQC⋅view=highQC⋅view+1 where highQC points to the parent block of his new block.Proof.
LetPi be the nonfaulty leader of view v. If Pi collects n−f valid view-change messages, he will select qc with the largest view number among them as highQC. Each of the n−f valid view-change messages must also include a promise on highQC.view+1; then, Pi can combine a threshold signature with these n−f signature shares and construct nullQC that nullQC⋅view=highQC⋅view+1.Theorem 2.
In pipelined Lodestone, after GST, any request from clients will be included in the finalized block in a bounded time.Proof.
According to Lemma2, there are three consecutive views leaded by nonfaulty replicas in any consecutive n+2 views, denoted as v,v+1,v+2. There exists a bounded time duration T that if all nonfaulty replicas stay in the same view during T, then the leader can propose his new block with nullQC⋅view=highQC⋅view+1 according to Lemma 3. Thus, the first nonfaulty leader of v will propose a block b, and all nonfaulty replicas will vote for b. Then, the second nonfaulty leader of v + 1 will collect n− f votes for b and propose a block b' with highQC′⋅view=v∧nullQC′⋅view=v+1. All nonfaulty replicas will also vote for b'. Then, the third nonfaulty leader of v + 2 will collect n−f votes for b' and propose a block b'' with highQC″.view=v+1. Therefore, b, b', and b'' form a two-chain b,b′,b′, and all nonfaulty replicas will consider b as COMMITTED after receiving b''. For any time t, the three consecutive views leaded by nonfaulty players will come within a bounded time duration after t. Therefore, there exists a bounded constant Tconfirm in that for any request input to all replicas at time t, it will be included in the finalized block at t+Tconfirm.


### 4.3. Communication Complexity

We now discuss the communication complexity of pipelined Lodestone. It is noted that we only consider the communication overhead when liveness can be guaranteed after GST. When the network is asynchronous, there may be unbounded views without making a decision. In fact, we can allow replicas at most sendf promises during a view-change which has no effect on the safety property since it is impossible to guarantee liveness under an asynchronous network [29].Theorem 3.
After GST, pipelined Lodestone achieves a linear communication complexity on average whileOn2 in the worst case.Proof.
When liveness can be guaranteed after GST, whenever two consecutive views are leaded by nonfaulty replicas, the second leader can generateqc, and all nonfaulty replicas will update their lockedQC. Therefore, in the worst case, there are 2f+1 consecutive views without generating new qc. And then, one replica needs to send 2f+1 promises on these 2f+1 views. And thus, the total complexity of a view-change is On2 in the worst case.
Now, we discuss the communication complexity of a view-change in the average case. The probability of one view leaded by a faulty replica can be considered as1/3 while 2/3 by a nonfaulty leader approximately with the assumption n=3f+1. Given any view v, let X be the length of views before v without any two consecutive views leaded by nonfaulty replicas. Let P(X) be the probability distribution of X. For any view v, X = k occurs when(i)
Either the leader ofv −1 is faulty and X = k −1 holds for v −1(ii)
Or the leader ofv −1 is nonfaulty while the leader of v −2 is faulty and X = k −2 holds for v −2
As the assumption,v −1 and v −2 also follow the same probability distribution which is denoted as P(X = k −1) and P(X = k −2), respectively. Then, P(X = k) can be expressed as(1)PX=k=13PX=k−1+29PX=k−2.
The expectationE(X) is the length of views before v without any two consecutive views leaded by nonfaulty players on average. E(k) is also the total number of signatures in the promise-set of one replica on average. We have EX=7/4 after simplification. Therefore, the expectation of the total communication overhead of a view-change is On for all n replicas in a view.


## 4.1. Safety

Lemma 1.
For any two valid quorum certificatesqc1 and qc2, if qc1⋅view=qc2⋅view, then qc1⋅block=qc2⋅block.Proof.
For any validqc, at least n−2f nonfaulty replicas have sent their relevant signature shares, namely, at least n−2f nonfaulty replicas have voted for the block which qc.block represents in qc.view. Suppose qc1 and qc2 are two valid qc such that qc1⋅view=qc2⋅view, but qc1⋅block≠qc2⋅block. We must have that at least n−2f nonfaulty replicas voted for the qc1⋅block and also at least n−2f nonfaulty replicas voted for the qc2⋅block in the same view. Thus, the intersection of the two sets at least includes one nonfaulty replica since 2×n−2f>n−f, a contradiction to Algorithm 2 that a nonfaulty replica can only vote once in a view.Theorem 1.
In pipelined Lodestone, two conflicting blocks cannot be both COMMITTED.Proof.
Letb1 and b2 be two conflicting blocks which are both COMMITTED, namely, there exists a two-chain b_1,b_1′,b_1″ and also one in the form of b_2,b_2′,b_2′. W.l.o.g, we can assume that b2⋅view>b1′⋅view with Lemma 1. Since b1 is COMMITTED, at least n−2f nonfaulty replicas have voted for b_1' and then locked on b1. Let b^ be the PREPARED block with the smallest view number that satisfies b^.view>b1′.view, and b^ conflicts with b1. Such b^ must exist since b2 satisfies all these conditions. Now, consider the proposal m of b^. At least n−2f nonfaulty replicas have locked on b1 in b1′⋅view. These n−2f nonfaulty replicas will only promise on view number larger than b1⋅view since then. Therefore, m⋅proof⋅view>b1⋅view. And due to the minimality of b^, we must have m⋅qc.view<b1⋅view. Then, m.proof.view>m.qc.view+1, a contradiction to the validity of nullQC.


## 4.2. Liveness

Lemma 2.
Under ann=3f+1 setting where leaders are rotated in a round-robin manner, in any consecutive n+2 views, there are three consecutive views all leaded by nonfaulty replicas.Proof.
Consider anyn consecutive views denoted as v,v+1,v+2,…,v+n−1. There are three cases:(i)
The leader ofv is faulty. Then, for the view from v + 1 to v + n −1, there are f− 1 faulty leaders while 2f+1 nonfaulty leaders. The f−1 faulty leaders can at most separate 2f+1 nonfaulty leaders into f segments, with at least one segment owning 3 nonfaulty leaders.(ii)
The leader ofv is nonfaulty, while the leader of v + 1 is faulty. Then, for the view from v + 2 to v + n, there are f−1 faulty leaders while 2f+1 nonfaulty leaders. Then, the situation becomes the same as the first case.(iii)
Bothv and v + 1 are leaded by nonfaulty leaders. Then, if the leader of v + 2 is nonfaulty, three consecutive nonfaulty leaders exist. Otherwise, for the view from v + 3 to v + n +1, there are f−1 faulty leaders while 2f+1 nonfaulty leaders. Then, the situation becomes the same as the first case.Lemma 3.
If a nonfaulty leader of view v collectsn− f valid view-change messages, he can always propose his new block, along with valid nullQC that nullQC⋅view=highQC⋅view+1 where highQC points to the parent block of his new block.Proof.
LetPi be the nonfaulty leader of view v. If Pi collects n−f valid view-change messages, he will select qc with the largest view number among them as highQC. Each of the n−f valid view-change messages must also include a promise on highQC.view+1; then, Pi can combine a threshold signature with these n−f signature shares and construct nullQC that nullQC⋅view=highQC⋅view+1.Theorem 2.
In pipelined Lodestone, after GST, any request from clients will be included in the finalized block in a bounded time.Proof.
According to Lemma2, there are three consecutive views leaded by nonfaulty replicas in any consecutive n+2 views, denoted as v,v+1,v+2. There exists a bounded time duration T that if all nonfaulty replicas stay in the same view during T, then the leader can propose his new block with nullQC⋅view=highQC⋅view+1 according to Lemma 3. Thus, the first nonfaulty leader of v will propose a block b, and all nonfaulty replicas will vote for b. Then, the second nonfaulty leader of v + 1 will collect n− f votes for b and propose a block b' with highQC′⋅view=v∧nullQC′⋅view=v+1. All nonfaulty replicas will also vote for b'. Then, the third nonfaulty leader of v + 2 will collect n−f votes for b' and propose a block b'' with highQC″.view=v+1. Therefore, b, b', and b'' form a two-chain b,b′,b′, and all nonfaulty replicas will consider b as COMMITTED after receiving b''. For any time t, the three consecutive views leaded by nonfaulty players will come within a bounded time duration after t. Therefore, there exists a bounded constant Tconfirm in that for any request input to all replicas at time t, it will be included in the finalized block at t+Tconfirm.


## 4.3. Communication Complexity

We now discuss the communication complexity of pipelined Lodestone. It is noted that we only consider the communication overhead when liveness can be guaranteed after GST. When the network is asynchronous, there may be unbounded views without making a decision. In fact, we can allow replicas at most sendf promises during a view-change which has no effect on the safety property since it is impossible to guarantee liveness under an asynchronous network [29].Theorem 3.
After GST, pipelined Lodestone achieves a linear communication complexity on average whileOn2 in the worst case.Proof.
When liveness can be guaranteed after GST, whenever two consecutive views are leaded by nonfaulty replicas, the second leader can generateqc, and all nonfaulty replicas will update their lockedQC. Therefore, in the worst case, there are 2f+1 consecutive views without generating new qc. And then, one replica needs to send 2f+1 promises on these 2f+1 views. And thus, the total complexity of a view-change is On2 in the worst case.
Now, we discuss the communication complexity of a view-change in the average case. The probability of one view leaded by a faulty replica can be considered as1/3 while 2/3 by a nonfaulty leader approximately with the assumption n=3f+1. Given any view v, let X be the length of views before v without any two consecutive views leaded by nonfaulty replicas. Let P(X) be the probability distribution of X. For any view v, X = k occurs when(i)
Either the leader ofv −1 is faulty and X = k −1 holds for v −1(ii)
Or the leader ofv −1 is nonfaulty while the leader of v −2 is faulty and X = k −2 holds for v −2
As the assumption,v −1 and v −2 also follow the same probability distribution which is denoted as P(X = k −1) and P(X = k −2), respectively. Then, P(X = k) can be expressed as(1)PX=k=13PX=k−1+29PX=k−2.
The expectationE(X) is the length of views before v without any two consecutive views leaded by nonfaulty players on average. E(k) is also the total number of signatures in the promise-set of one replica on average. We have EX=7/4 after simplification. Therefore, the expectation of the total communication overhead of a view-change is On for all n replicas in a view.


## 5. Results and Discussion

### 5.1. Implementation and Setup

We have implemented both pipelined Lodestone and pipelined HotStuff in C++ language with the same codebase for a fair comparison, taking the implementation (https://github.com/hot-stuff/libhotstuff) in HotStuff’s paper [1] as a reference. We use Ed25519 for common digital signatures and BLS threshold signatures (https://github.com/herumi/bls) for combining signatures in our protocol.We deploy our experiments on Alibaba Cloud using ecs.ic5.4xlarge instances. The round-trip delay between two instances is less than 1 millisecond, with the bandwidth about 5 Gbps.In all experiments, besides all players and clients, we develop a coordinator who is responsible for notifying all clients sending requests to players. The coordinator collects measurement data to compute the throughput and end-to-end latency of clients. Figure5 shows the architecture in our experiments.Figure 5
The architecture diagram of experiments.We first evaluate these two protocols with zero-sized payload and different choices of batch sizes to get rid of the effects of payload size. Figure6 shows that Lodestone has a prominent lower latency compared with HotStuff under the batch size of both 400 and 800 benefiting from conserving one phase of the vote.Figure 6
Throughput vs. latency with different choices of batch size, 10 replicas, and zero-sized payload.Figure7 depicts different payload sizes for both systems as 512 bytes and 1024 bytes, with a fixed batch size of 800. In such settings, Lodestone still enjoys a remarkable lower latency compared with HotStuff and provides comparable throughput.Figure 7
Throughput vs. latency with different choices of payload size, 10 replicas, and batch size of 800.


## 5.1. Implementation and Setup

We have implemented both pipelined Lodestone and pipelined HotStuff in C++ language with the same codebase for a fair comparison, taking the implementation (https://github.com/hot-stuff/libhotstuff) in HotStuff’s paper [1] as a reference. We use Ed25519 for common digital signatures and BLS threshold signatures (https://github.com/herumi/bls) for combining signatures in our protocol.We deploy our experiments on Alibaba Cloud using ecs.ic5.4xlarge instances. The round-trip delay between two instances is less than 1 millisecond, with the bandwidth about 5 Gbps.In all experiments, besides all players and clients, we develop a coordinator who is responsible for notifying all clients sending requests to players. The coordinator collects measurement data to compute the throughput and end-to-end latency of clients. Figure5 shows the architecture in our experiments.Figure 5
The architecture diagram of experiments.We first evaluate these two protocols with zero-sized payload and different choices of batch sizes to get rid of the effects of payload size. Figure6 shows that Lodestone has a prominent lower latency compared with HotStuff under the batch size of both 400 and 800 benefiting from conserving one phase of the vote.Figure 6
Throughput vs. latency with different choices of batch size, 10 replicas, and zero-sized payload.Figure7 depicts different payload sizes for both systems as 512 bytes and 1024 bytes, with a fixed batch size of 800. In such settings, Lodestone still enjoys a remarkable lower latency compared with HotStuff and provides comparable throughput.Figure 7
Throughput vs. latency with different choices of payload size, 10 replicas, and batch size of 800.


## 6. Conclusions

We presented pipelined Lodestone, a chain-based BFT SMR protocol, which achieves linear view-change on average and optimistic responsiveness with only two phases of voting. Through the experimental results, pipelined Lodestone provides a lower latency and comparable throughput compared with HotStuff in various workloads and network scales.



---

*Source: 2507670-2021-12-03.xml*