A review of Strengthened Fault Tolerance in Byzantine Fault Tolerant Replication (SFT-BFT)
In this post, I will summarize the SFT-BFT paper. This paper implemented on Diem project that uses at its core the HotStuff consensus algorithm. SFT-BFT is inspired by Nakamoto Consensus where any block obtains higher assurance as buried deeper in blockchain. Normally, BFT-SMR has a threshold resilient equals to F where N≥3F+1.
The SFT-BFT argues that this threshold might increase during optimistic period where the network is synchronous and has less faulty nodes. After both the block committed and optimistic period, the threshold of tolerating the faulty nodes increased up to 2/3. This means that once the blocks are committed with higher resilience, they are safe even if the number of malicious parties later exceeds 1/3. How? By adding more information on the voting messages.
SFT-BFT goals is to increase the safety assurance in permissioned blockchain over time. Also similar to Nakamoto consensus, the client can wait for valuable blocks trading latency with safety.
SFT-BFT denotes Byzantine nodes as t where t≤F during optimistic period but the the aims to secure the blocks even if there are more than F Byzantine faults after the optimistic period. If you remember, the BFT has a single commit rule called regular commit rule or F-strong where F is the total number of fault. In contrast, SFT-BFT has a set of commit rules that commit blocks with different level of guarantee. The SFT-BFT requires that there is no other conflict block say B’ can be x-strong guarantee if number of byzantine does not exceed x.
Now let’s define what are the Safety and Liveness.
Safety: SFT-BFT is a safe with a set of commit rules if any x-strong committed block B, no other conflicting block B’ can bee x’-strong committed where x’≥x in the presence of t≤x Byzantine faults.
Liveness: SFT-BFT lives if during optimistic period t≤F Byzantine faults, a block will be (x=2f-t)-strong committed.
If there is a fork, the new vote is not enhancing the results if the replica already vote on the another branch. To avoid this, SFT-BFT attached a simple solution for the voting message called marker with relatively weak liveness guarantee. This message with marker called a strong vote message.
Marker is the largest round number of any block that voted by the replica and conflicts with B. Replica can vote for block B, if B=B’ or the round number of B is larger than the value of marker and B’ extends B.
Below, you will find the SFT-DiemBFT algorithm and three chain-commit rules.
To generalize the strong vote for better liveness, the paper introduced the interval. The interval defines as a set of intervals of round numbers that strong vote endorses. The strong vote endorses any B’ whose round number r’ in Interval.
When replica h, votes for a block B on a chain C. For every Fork F on which h ever voted for some conflicting block B’, it computes an interval of rounds number that does not endorse say D_F.
Interval=[1,r]\{U_f D_F}.
D_f= [r_l+1,r_h], where r_h is the largest round number of any conflicting block B’ that h voted for on F, and r_l is the largest round number of the common ancestor block of both B and B’.
