Source-linked AI summary
Scalable Byzantine Consensus via Hardware-assisted Secret Sharing
Jian Liu, Wenting Li, Ghassan O. Karame, N. Asokan
TL;DR
Existing BFT protocols face limited deployment and scalability in blockchain systems because PBFT requires O(n^2) messages and scales only to a few tens of nodes. FastBFT combines TEE-assisted secret-sharing aggregation with complementary protocol optimizations. The paper reports improved efficiency and scalability, including 6× faster performance than Zyzzyva and over 100,000 transactions per second under a stated Bitcoin-like configuration.
Problem
Existing BFT protocols have poor efficiency and scalability for blockchain deployment, with PBFT limited to a few tens of nodes by O(n^2) message complexity.
Method
FastBFT combines TEE-based message aggregation using lightweight secret sharing with optimistic execution, tree topology, and failure detection.
Results
FastBFT outperforms other BFT variants in efficiency and scalability, is 6 times faster than Zyzzyva, and can process over 100,000 transactions per second under a stated configuration.
Takeaways & Limitations
FastBFT is presented as an ideal consensus layer candidate for next-generation blockchain systems.
Takeaways & Limitations
During view-change, some replicas can have counters out of sync and cannot rejoin the active quorum until the protocol advances using the execution history of other replicas.
Abstract
from arXiv · showhide
The surging interest in blockchain technology has revitalized the search for effective Byzantine consensus schemes. In particular, the blockchain community has been looking for ways to effectively integrate traditional Byzantine fault-tolerant (BFT) protocols into a blockchain consensus layer allowing various financial institutions to securely agree on the order of transactions. However, existing BFT protocols can only scale to tens of nodes due to their $O(n^2)$ message complexity. In this paper, we propose FastBFT, a fast and scalable BFT protocol. At the heart of FastBFT is a novel message aggregation technique that combines hardware-based trusted execution environments (TEEs) with lightweight secret sharing primitives. Combining this technique with several other optimizations (i.e., optimistic execution, tree topology and failure detection), FastBFT achieves low latency and high throughput even for large scale networks. Via systematic analysis and experiments, we demonstrate that FastBFT has better scalability and performance than previous BFT protocols.
1 INTRODUCTION
FastBFT addresses the scalability and efficiency limits that have hindered practical BFT deployment in blockchain systems. It combines hardware-assisted secret-sharing aggregation with optimistic execution, tree communication, and failure detection, and experiments report improved performance and scalability.
- Motivation: BFT protocols have seen limited real-world deployment because current designs have poor efficiency and scalability.Commercial systems often use crash fault-tolerant variants instead, partly because Byzantine faults are not perceived as major concerns in well-maintained data centers.
- Motivation: PBFT scales only to a few tens of nodes because consensus requires O(n^2) messages among n servers.Improving BFT scalability and performance is presented as essential for practical industrial blockchain deployment.
- FastBFT design: FastBFT reduces message complexity from O(n^2) to O(n) using hardware-based TEEs and lightweight secret sharing for message aggregation.Unlike multisignature-based schemes, the aggregation technique does not require public-key operations, reducing computation and communication overhead.
- FastBFT design: FastBFT combines message aggregation with a tree topology, optimistic BFT execution, and failure detection to balance communication, computation, and fault handling.The optimistic design actively runs the protocol on only a subset of nodes, while the tree organizes communication and aggregation along its edges.
- Evaluation: Over 100,000 transactions per second are achievable with 1 MB blocks and 250-byte transaction records, while throughput declines more slowly as network size increases.The stated configuration follows the block and transaction sizes used in Bitcoin.
- Evaluation: The paper contributes a framework for comparing BFT variants and a systematic implementation-based performance analysis.The analysis reports that FastBFT outperforms other variants in latency, throughput, and scalability.
2 PRELIMINARIES
The preliminaries define state machine replication and classical BFT, then review speculative and optimistic optimizations, hardware security, and message aggregation as routes to lower BFT overhead.
- State Machine Replication: State machine replication replicates system state across nodes that execute client operations in the same order.Fault-tolerant SMR targets safety and liveness despite crash or Byzantine failures.
- Practical Byzantine Fault Tolerance: Classical BFT uses a primary and a three-phase pre-prepare, prepare, and commit protocol before replicas respond to clients.Clients accept a result after receiving at least f + 1 consistent replies, and faulty primaries trigger view-change.
- Optimizing for the Common Case: Speculative BFT executes requests without explicit agreement in the normal case, whereas optimistic BFT actively involves only a subset of replicas.Zyzzyva uses speculation; ReBFT passively updates non-active replicas until agreement fails.
- Hardware Security Mechanisms: TEEs provide protected, isolated execution and remote attestation, and are assumed to crash but not behave Byzantine.Hardware security has been used to reduce replica counts and communication phases in BFT protocols.
- Message Aggregation: BFT commit communication has O(n^2) complexity because replicas multicast commit messages, motivating message aggregation.FastBFT uses secret sharing rather than multisignatures to aggregate messages, reducing complexity to O(n) with an additional communication step.
3 FASTBFT OVERVIEW
FastBFT combines TEEs, secret sharing, and a tree topology to aggregate commit messages while preserving request-specific secret binding. Its design assumes TEEs with monotonic counters and rollback-resistant memory, and distributes aggregation across a balanced tree.
- System model: FastBFT requires replicas with TEEs that maintain monotonic counters and rollback-resistant memory.The protocol guarantees safety in asynchronous networks but requires weak synchrony for liveness.
- Message aggregation: O(n) message complexity is achieved by sending commit messages to the primary for secret-share aggregation instead of multicasting to all replicas.Secret sharing avoids the public-key operations associated with multisignature-based aggregation.
- Message aggregation: During preprocessing, the primary generates secrets, hashes them, splits them into shares, and distributes one share to each active replica.Replicas later reveal their shares during commit so the primary can reconstruct the aggregated secret.
- Secret binding: TEEs bind each secret to a unique monotonic-counter value and bind each request to a freshly incremented counter value.This prevents a faulty primary from using one secret for multiple requests or one counter value for multiple secrets.
- Communication topology: A balanced tree rooted at the primary distributes share propagation and aggregation costs across active replicas.The tree addresses the bottleneck of the primary receiving and aggregating O(n) shares directly.
4 FASTBFT: DETAILED DESIGN
FastBFT’s detailed design combines TEE-hosted counters and secret-sharing operations with preprocessing, tree-based normal-case execution, failure detection, view-change, and a classical-BFT fallback. These mechanisms reduce communication complexity while addressing replica failures and fallback tradeoffs.
- TEE-hosted Functionality: FastBFT’s TEEs maintain counters, views, replica keys, and tree structure while generating one-time secrets and authenticated shares for aggregation.The primary TEE manages active replicas and topology; preprocessing creates secret shares and verification hashes encrypted under per-replica keys.
- Normal-case Operation: Preprocessing supplies authenticated counter-bound packages, allowing the primary to bind requests to counters before replicas collectively open the corresponding secret.The primary signs a request hash with the current counter and multicasts a PREPARE message; replicas verify the binding and propagate shares through the tree.
- Normal-case Operation: The primary reconstructs the secret, executes the operation, and multicasts COMMIT; replicas verify the secret, execute the operation, open the next secret, and return replies.Reply validation binds the request, result, and counter values while checking that active replicas agreed to execute and completed the operation.
- Failure Detection: Parent replicas detect missing child shares with timers and verification, after which the primary replaces the accused replica, restructures the tree, and can move the accuser to a leaf.A Byzantine primary may evict correct replicas, but at least one correct replica remains among the f + 1 active replicas; a displaced replica can rejoin by updating its counter.
- Failure Detection and Fallback: Failure detection can trigger repeated tree reconstructions as a denial-of-service attack, so FastBFT can fall back to a classical BFT protocol after a threshold of detected non-primary failures.The fallback abandons the tree because a faulty internal node can make its subtree faulty, and it uses polynomial secret sharing for subset-based commitment.
- Fallback Protocol: O(n)The aggregation technique reduces MinBFT’s message complexity from O(n^2) to O(n), although polynomial-based secret sharing is more expensive than FastBFT’s XOR-based sharing.
5 CORRECTNESS OF FASTBFT
FastBFT’s correctness argument establishes safety through consistent operation ordering across views and liveness through eventual transition to stable views. The paper explicitly leaves a formal machine-checked proof as future work.
- FastBFT’s informal correctness argument leaves a formal, ideally machine-checked, proof of safety and liveness as future work.
- 5.1 Safety: Safety requires that correct replicas execute the same operation sequence or a prefix of the sequence executed by any correct replica.
- 5.1 Safety: A view cannot contain different operations with the same counter value, and changing views cannot omit an operation already executed by a correct replica.
- 5.2 Liveness: During a stable view, a correct client’s operation eventually completes, with faulty replicas detected and either replaced or triggering view-change.
- 5.2 Liveness: If f + 1 correct replicas request view-change, the system eventually reaches a stable view, ensuring that correct clients’ requests complete.
6 DESIGN CHOICES
FastBFT’s design choices address counter persistence, message complexity, and communication bottlenecks while exposing tradeoffs between performance and resilience. The framework situates alternative BFT variants along these dimensions.
- 6 DESIGN CHOICES: FastBFT assumes TEEs maintain monotonic counters, but hardware counters can bottleneck BFT protocols because of their low efficiency.
- 6 DESIGN CHOICES: Virtual counters avoid hardware-counter overhead but can reset after reboot and enable rollback attacks when state is stored naively.
- 6 DESIGN CHOICES: FastBFT uses a hardware-counter-backed persistent-state scheme and treats unscheduled reboots as crashes before allowing replicas to rejoin through a reset-counter protocol.
- 6 DESIGN CHOICES: The framework compares BFT variants by common-case performance—latency and peak throughput—and resilience to non-primary faults.
- BFT paradigms: Speculative protocols offer the best performance, classical protocols tolerate non-primary faults for free, and speculative protocols have the weakest resilience.
- Hardware assistance and message aggregation: Hardware assistance improves performance across paradigms, while message aggregation reduces communication complexity and can make optimistic protocols more efficient than speculative ones.
- Communication topology: The authors conjecture that hardware, aggregation, and tree topology narrow performance gaps while preserving or improving resilience, pending experimental confirmation.
7 EVALUATION
FastBFT is evaluated against several BFT variants using an SGX-based implementation and controlled throughput and latency measurements. Across payload sizes, fault thresholds, and network sizes, it generally achieves superior performance and scalability, while its TEE design introduces additional functionality and security considerations.
- Evaluation setup: The evaluation compares FastBFT with Zyzzyva, MinBFT, CheapBFT, and XPaxos, including both normal-case and fallback protocols.The fallback protocol is treated as FastBFT’s worst case.
- Evaluation setup: Latency measurements use closed-loop clients, back-to-back requests, 1,500 samples per data point, and 95% confidence intervals where appropriate.Concurrency increases until aggregate throughput saturates.
- Pre-processing time: 0.6 ms: FastBFT’s TEE generates additive shares for 20 replicas, increasing linearly to 1.6 ms for 200 replicas in the normal case.The paper argues this preprocessing does not bottleneck FastBFT; fallback Shamir-share generation takes approximately 100 ms for 200 replicas.
- Performance results: 490 operations per second: FastBFT’s peak throughput at f = 51, five times larger than Zyzzyva’s.FastBFT has the highest throughput and lowest average latency when f > 24; its fallback reaches 320 op/s versus 110 op/s for CheapBFT at f = 51.
- Performance results: 260 times faster than Zyzzyva: FastBFT’s peak throughput for a 1 MB payload at n = 199.Other protocols deteriorate substantially with large payloads because they require many full replies, whereas FastBFT requires only the primary to reply.
- Performance results: 113,246 transactions per second: FastBFT’s maximum throughput for 250-byte transactions in a network of around 199 replicas.The experiments conclude that FastBFT balances performance and resilience.
8 RELATED WORK
Related work spans randomized Byzantine protocols, alternative fault models, cryptographic aggregation, and TEE-based designs. FastBFT is positioned as a deterministic protocol whose aggregation approach avoids the all-to-all communication or public-key operations used by several alternatives.
- Byzantine consensus protocols: The paper focuses on deterministic Byzantine consensus because randomized protocols typically incur high communication and time complexities.Randomized protocols complete in O(k) rounds with probability 1 − 2^-k.
- Alternative fault models: XPaxos tolerates f faults with n = 2f + 1 replicas but retains O(n^2) message complexity through all-to-all multicast.Its model combines crash tolerance in weakly synchronous networks with Byzantine tolerance in synchronous networks.
- Aggregation techniques: FastBFT’s aggregation resembles PowerStore’s proof of writing, which uses commitments to avoid public-key operations.PowerStore’s procedure commits to a random value and later opens the commitment to prove completion.
- TEE-based protocols: Hybster improves TEE-based BFT through parallelization, which the paper describes as orthogonal to FastBFT’s contribution.
9 CONCLUSION AND FUTURE WORK
The paper concludes that FastBFT provides a highly efficient BFT protocol whose throughput declines more slowly as networks grow. It also identifies TEE portability and topology selection as areas relevant to deployment and future study.
- Conclusion: 6 times faster than Zyzzyva: the paper’s reported FastBFT performance comparison.The authors argue this approaches optimal BFT efficiency because Zyzzyva reduces replica overheads near theoretical minima.
- Conclusion: FastBFT’s throughput declines considerably more slowly with network growth than other BFT protocols.The authors identify this scalability as supporting FastBFT’s candidacy for next-generation blockchain consensus layers.
- Assumptions and scope: FastBFT assumes TEEs with certified keypairs, but can be implemented on standard TEE platforms beyond Intel SGX.The implementation uses Intel SGX, while the protocol is described as applicable to platforms such as GlobalPlatform.
- Future work: Future work will examine topologies beyond trees to identify optimal or near-optimal choices for particular FastBFT network sizes.