SBFT - LabMazurokCom/Blockchain GitHub Wiki
Simplified Byzantine Fault Tolerance (SBFT)
SBFT is a permissioned voting based consensus.
Quick overview
SBFT leverages techniques from many of the best previous practical algorithms. This is a practical algorithm that has linear complexity in the common mode and requires just one message for client acknowledgment.
In this algorithm, the block's validator is a known entity. It could be a regulator in a business network for example. This validator creates and proposes a new block of transactions. In a SBFT consensus, a certain number of nodes must accept the block, depending on the number of faulty nodes.
In such a system, (2f+1) nodes at minimum must accept the new block in a business network, where f is the number of faulty nodes. Faulty in this sense could be malicious or non functioning nodes.
Pros: Faster than Proof of Work, better scalability.
Cons: Tendency to centralization. One validator proposes the next block. On the other hand, in a 2018 study concludes that for both Bitcoin and Ethereum the top <20 mining coalitions control over 90% of the mining power.
System Model
We assume a standard asynchronous BFT system model where an adversary can control up to f Byzantine nodes and can delay any message in the network by any finite amount. We say that the system is in the synchronous mode, when the adversary can control up to f Byzantine nodes, but messages between any two non-faulty nodes have a bounded delay. Finally we say that the system is in the common mode, when the adversary can control up to c (c ≤ f provides better properties) nodes that can only crash or act slow, and messages between any two non-faulty nodes have a bounded delay.
Features
For N > 3f+2c replicas SBFT obtains the following properties:
-
Safety in the asynchronous mode. This means that any two replicas that execute a decision block for a given sequence number, execute the same decision block.
-
Liveness in the synchronous mode. This means that client requests return a response.
-
Linearity in the common mode. This means that in an abstract model where we assume the number of operations in a block is n and we assume the number of clients is also n, then the amortized cost to commit an operation is a constant number of constant size messages.
Evaluating SBFT’s scalability
SBFT can execute a workload of real-world EVM contracts at a rate of over 70 transactions per second while being replicated by over 200 replicas and able to withstand up to f=64 malicious replicas. In a experiment, SBFT can execute real-world EVM transactions at over 50 transactions per second while being replicated by over 100 replicas and able to withstand up to f=32 malicious replicas. When it was running on a single region, an SBFT deployment that can withstand f = 64 failures and uses about 200 replicas completes these 1 Million transactions in 20 minutes, or about 833 transactions per second.
Methods
-
Using a collector to reduce all-to-all communication. Instead of sending to everyone, each replica sends to the collector and the collector broadcasts to everyone. SBFT also uses a round-robin revolving collector to reduce the load and also uses (k+1) collectors (instead of one) to improve fault tolerance and handle c slow or faulty collectors.
-
Using threshold signatures to reduce client communication from O(n) to O(1). SBFT reduces the per-client linear cost to just one message cost by adding a phase that uses a single collector to aggregate the threshold signatures and send each client a single message carrying one signature. Just like public blockchains (Bitcoin and Ethereum) SBFT uses a Merkle tree to efficiently authenticate information that is read from just one replica.
-
Exploiting optimism with a correct view change protocol. SBFT allows for a faster agreement path in optimistic executions: where all replicas are non-faulty and synchronous. And one allows the fast track to tolerate up to a small number c (parameter) of crashed or straggler nodes out of N > 3f+2c replicas.
-
SBFT takes advantage of modern cryptographic advances. SBFT uses Boneh–Lynn–Shacham (BLS) signatures with security that is comparable to 2048-bit RSA signatures but are just 33 bytes long.
References
Byzantine Fault Tolerance in a Distributed System
SBFT: a Scalable Decentralized Trust Infrastructure for Blockchains