Source-linked AI summary
Scalable Byzantine Consensus via Hardware-assisted Secret Sharing
Jian Liu, Wenting Li, Ghassan O. Karame, N. Asokan
TL;DR
PBFT scales only to a few tens of nodes because consensus requires O(n^2) messages, making BFT scalability and performance important for practical industrial blockchain deployment. FastBFT aggregates messages using trusted execution environments and lightweight secret sharing; the authors report it is 6 times faster than Zyzzyva and its throughput declines more slowly as network size grows than other BFT protocols.
Problem
PBFT scales only to a few tens of nodes because consensus requires O(n^2) messages, making BFT scalability and performance important for practical industrial blockchain deployment.
Source: §1 · p. 1Method
FastBFT aggregates messages using trusted execution environments and lightweight secret sharing, reducing message complexity from O(n^2) to O(n).
Source: §1 · p. 1Results
6 times faster than Zyzzyva; FastBFT also outperforms other BFT variants in latency, throughput, and scalability.
Source: §1 · p. 2, §9 · p. 13Takeaways & Limitations
The authors identify FastBFT as a candidate consensus layer for next-generation blockchain systems.
Source: §1 · p. 2, §9 · p. 13View-change can leave counters out of sync, preventing replicas in one quorum from rejoining another, though safety and liveness hold while the other quorum follows the protocol.
Source: §4.4 · p. 7
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 targets BFT’s scalability and performance limits for blockchain consensus through TEE-assisted secret-sharing aggregation and complementary protocol optimizations. The introduction also presents a framework for comparing BFT design variants.
1 INTRODUCTION
- Blockchain revives BFT interest, but Bitcoin PoW is criticized for energy waste and ~7 transactions per second, while PBFT trails payment volumes and scales to tens of nodes at O(n^2).BFT protocols had not seen significant real-world deployment; the introduction cites efficiency and scalability concerns and the low perceived risk of Byzantine faults as possible reasons.Source: §1 · p. 1
- FastBFT combines TEE-backed lightweight secret-sharing aggregation, reducing message complexity from O(n^2) to O(n) without public-key operations, with tree communication, optimistic participation, and failure detection for non-primary faults.These design choices aim to reduce computation and communication overhead while balancing load across tree edges.Source: §1 · p. 1
- The paper introduces a framework that captures key design choices and situates FastBFT among previously proposed and novel BFT variants with different efficiency-resilience tradeoffs.The paper also presents a full implementation and systematic performance analysis comparing FastBFT with several BFT variants.Source: §1 · p. 2
- FastBFT outperforms evaluated BFT variants in latency, throughput, and scalability, with throughput declining more slowly as nodes grow and exceeding 100,000 transactions per second at 1 MB blocks and 250-byte records.The comparison covers protocols,, and; the stated transaction-rate estimate assumes Bitcoin-sized blocks and records.Source: §1 · pp. 1–2
2 PRELIMINARIES
The preliminaries define SMR correctness and asynchronous limits, then review classical BFT, common-case optimizations, TEEs, and message aggregation as context for scalable consensus.
2.1 State Machine Replication (SMR)
- SMR replicates service state across nodes, requiring non-faulty replicas to execute requests in the same order and clients eventually to receive replies; FLP rules out deterministic fault tolerance in asynchronous systems.Replicas may fail by crashing or behaving arbitrarily (Byzantine).Source: §2.1 · p. 2
2.2 Practical Byzantine Fault Tolerance (PBFT)
- PBFT [5] has a primary propose request order for a three-phase pre-prepare/prepare/commit agreement; clients accept after f + 1 consistent replies, and replicas use view-change to replace a faulty primary.The paper calls protocols following this message pattern classical BFT; weak synchrony ensures view-change eventually succeeds.Source: §2.2 · p. 2, Figure 1 · p. 2
2.3 Optimizing for the Common Case
- Speculative BFT, exemplified by Zyzzyva, skips explicit agreement in the common case, while optimistic BFT, exemplified by ReBFT, limits agreement to a subset of replicas.In Zyzzyva, inconsistent replies after primary equivocation prompt recovery; in ReBFT, passive replicas join if agreement fails.Source: §2.3 · p. 2
2.4 Using Hardware Security Mechanisms
- TEEs isolate protected data and execution, support remote attestation, and can crash but not act Byzantine; MinBFT uses trusted counters to reduce replica and phase requirements, while CheapBFT uses active and passive replicas.MinBFT reduces replicas from 3f + 1 to 2f + 1 and phases from three to two; CheapBFT uses f + 1 active replicas without faults, then activates passive replicas and switches to MinBFT if faulty behavior is suspected.Source: §2.4 · pp. 2–3
2.5 Aggregating Messages
- Classical BFT commit multicasts create O(n^2) messages; aggregation can reduce each replica to sending and receiving one message, while CoSi multisignatures offer compact joint signatures but generally increase message size and processing time.ByzCoin used collective signing to improve PBFT scalability.Source: Figure 1 · p. 2, §2.5 · p. 3
3 FASTBFT OVERVIEW
FastBFT combines optimistic active/passive replication with TEE-protected secret sharing and a tree topology to reduce communication and distribute aggregation work. It guarantees safety asynchronously but requires weak synchrony for liveness.
System model
- FastBFT guarantees asynchronous safety but needs weak synchrony for liveness; it assumes Byzantine replicas, crash-only TEEs, and n = 2f + 1 replicas to tolerate f faults.Its optimistic design has f + 1 active replicas agree and execute requests while the other f replicas passively update state; this trades efficiency for resilience.Source: §3 · pp. 3–4
Strawman design
- Preprocessing one-time secrets enables share-based commit aggregation at the primary, reducing commit messages to O(n); aggregated replies give clients and passive replicas one reply.The primary reconstructs and multicasts the commitment after gathering shares from active replicas.Source: §3 · p. 3
Hardware assistance
- TEEs generate and securely distribute shares, releasing each active replica’s share only after a correct prepare, so the primary cannot reconstruct a secret alone.In the strawman, the primary knew the secret and could impersonate any active replica.Source: §3 · p. 3
- The primary’s TEE binds each secret to a counter during preprocessing and each request to a freshly incremented counter, preventing secret reuse across requests.Replicas track the primary’s latest counter, and a replica must present the correct counter in its prepare message to retrieve its share.Source: §3 · pp. 3–4
Communication topology
- A balanced tree distributes share aggregation among active replicas, leaving the primary to receive and aggregate only a small constant number of shares.Shares flow bottom-up, with each intermediate node aggregating its children’s shares together with its own.Source: §3 · p. 4
Failure detection
- For non-primary faults, a parent can flag only its direct children; the primary replaces an accused replica with a passive one and moves the accuser to a leaf.Faulty nodes may crash or send an incorrect share.Source: §3 · p. 4
4 FASTBFT: DETAILED DESIGN
FastBFT’s detailed design combines TEE-managed counters, keys, and secret sharing with tree-based normal-case aggregation, then uses view changes and a classical BFT fallback to handle failures.
4.1 TEE-hosted Functionality
- TEE functions manage view keys, the tree, and monotonic counters; preprocessing creates hashed secret shares, while counter checks bind requests to successive counter values.The primary TEE tracks active replicas and shared keys; replica TEEs verify counter signatures and shares before advancing their counters.Source: §4.1 · pp. 4–5
4.2 Normal-case Operation
- In normal operation, the primary prepares requests with signed counter values, replicas aggregate shares up the tree, and the primary reconstructs the secret before committing and replying.Clients and passive replicas can verify the reply’s signatures, hashes, and successive secrets to confirm the request was agreed and executed.Source: §4.2 · pp. 5–6
4.3 Failure Detection
- Parents suspect children that fail to provide valid shares, and the primary rebuilds the tree by replacing the accused replica and moving its accuser to a leaf.A faulty primary can evict correct replicas, but at least one correct replica remains among the f + 1 active replicas; repeated detections can trigger fallback.Source: §4.3 · p. 6
4.4 View-change
- After f + 1 view-change requests, the new primary constructs a shared execution history and tree; replicas verify and execute it, though counters can diverge until a later view change reconciles them.As long as the advancing quorum follows the protocol, safety and liveness hold; a later view change can bring lagging replicas forward and reset counters for the new view.Source: §4.4 · pp. 6–7
4.5 Fallback Protocol: classical BFT with message aggregation
- FastBFT’s fallback replaces MinBFT’s O(n^2) message complexity with O(n) using TEE-assisted Shamir sharing, at higher sharing cost than its XOR-based scheme.The fallback uses a (f + 1)-out-of-(2f + 1) sharing scheme and does not use the tree, so it cannot tolerate non-primary faults for free.Source: §4.5 · p. 7
5 CORRECTNESS OF FASTBFT
The section gives informal arguments that FastBFT preserves safety and eventually completes correct clients’ requests. Formal, ideally machine-checked proofs of safety and liveness are left as future work.
5.1 Safety
- No two correct replicas execute different operations with the same counter value in one view.The argument uses the TEE’s prevention of conflicting signatures and quorum intersections that preserve PREPARE messages across view changes.Source: §5.1 · p. 8
- If a correct replica executes an operation in a view, every correct replica executes it before changing to a new view.The proof relies on execution histories and intersecting quorums carrying the operation into view-change processing.Source: §5.1 · p. 8
- A correct replica’s executed sequence is also executed by every other correct replica, which may execute only a prefix of it.The theorem follows from preventing conflicting operations within a view and ensuring executed operations are carried across view changes.Source: §5.1 · p. 8
5.2 Liveness
- A view eventually becomes stable if f + 1 correct replicas request a view-change.Under weak synchrony, repeated view-changes eventually reach the case where all replicas receiving a valid NEW-VIEW message can enter a stable view.Source: §5.2 · pp. 8–9
- A correct client’s operation eventually completes: stable views complete requests, and timeouts eventually drive unstable views toward stability.During a stable view, a correct primary enables completion; in fallback, completion holds when non-primary faults are at most f.Source: §5.2 · pp. 8–9
6 DESIGN CHOICES
FastBFT’s design choices pair virtual counters and controlled recovery after unscheduled reboots with alternative BFT paradigms, hardware support, message aggregation, and communication topologies. The section compares these choices in terms of performance and resilience.
6.1 Virtual Counter
- SGX hardware counters take 60–140 ms to read and 80–250 ms to increment, motivating virtual counters that pair persisted state with a hardware-counter check to prevent equivocation.A naive volatile counter backup can be rolled back; the hardware-counter mismatch check prevents processing after an unscheduled reboot.Source: §6.1 · p. 9
- A rebooted replica can reset its counter only after receiving f + 1 consistent signed values, and replicas withhold those values from an unscheduled-rebooted primary until it rejoins after view-change.This prevents a faulty primary from associating two different messages with the same counter value through the reset procedure.Source: §6.1 · p. 9
6.2 BFT `A la Carte
- Speculative BFT offers the best performance but has the weakest resilience, classical BFT offers the best resilience at a performance cost, and optimistic BFT trades between them.Speculative protocols depend on client-assisted recovery and may require rollback; optimistic protocols need transition or view-change for non-primary faults but not client support or rollback.Source: §6.2 · pp. 9–10
- Hardware security improves performance without affecting resilience, while secret-sharing aggregation benefits classical and optimistic protocols more than speculative ones; XOR sharing applies to OH/SH and polynomial sharing to CH.XOR-based sharing is more efficient than polynomial-based sharing; FastBFT uses OHXT and CHP as its fallback.Source: §6.2 · p. 10
- Tree topology improves performance; it preserves SHXT resilience, improves OHXT resilience, but reduces CHPT’s tolerance of non-primary faults, while chains offer high throughput at the cost of O(n) communication steps and large latency.Other communication topologies may offer different efficiency or resilience, which the authors leave for future work.Source: §6.2 · p. 10
- The authors conjecture that hardware and message aggregation bridge the performance gap between optimistic and speculative paradigms without harming resilience, while tree topology further improves performance and resilience.The paper says the following section confirms these conjectures experimentally.Source: §6.2 · p. 10
7 EVALUATION
The evaluation compares FastBFT’s normal and fallback protocols with Zyzzyva, MinBFT, CheapBFT, and XPaxos. FastBFT achieves strong throughput and latency results as replica count and reply payload size increase, while using a small TEE implementation.
7.1 Performance Evaluation: Setup and Methodology
- The evaluation ran replicas across five 8-vCore Xeon E3-1240 machines and clients on a separate 8-vCore Xeon E3-1230 machine.Machines were connected via 1 Gbps links; varying f up to 99 spawned at most 298 replica processes. Clients issued closed-loop requests, and plotted data points averaged 1,500 measurements with 95% confidence intervals where appropriate.Source: §7.1 · p. 11
7.2 Performance Evaluation: Results
- Normal-case share generation takes about 0.6 ms for 20 replicas and 1.6 ms for 200, while fallback share generation takes approximately 100 ms for 200 replicas.Normal-case preprocessing grows linearly with n and is not expected to bottleneck FastBFT; fallback generation grows significantly because it involves n · f modulo multiplications.Source: Figure 8 · p. 11, §7.2 · p. 11
- For 1 KB replies, FastBFT needs 4 ms to answer a request, twice as fast as Zyzzyva, and it has the lowest latency across the tested payload sizes.Latency is mainly affected by payloads larger than 1 KB; the authors attribute this to transmission overhead.Source: Figure 9 · p. 11, §7.2 · p. 11
- At f = 51, FastBFT reaches 490 operations per second, 5 times Zyzzyva’s throughput; FastBFT-fallback reaches 320 op/s versus CheapBFT’s 110, and FastBFT leads in throughput and average latency for f > 24.FastBFT’s throughput advantage over Zyzzyva grows when performance is compared at the same maximum number of tolerable faults.Source: Figure 10 · p. 12, §7.2 · p. 12
- At n = 199 with 1 KB replies, FastBFT reaches 370 operations per second, versus 56 for Zyzzyva, 38 for CheapBFT, and 42 op/s for XPaxos; fallback reaches almost 152 op/s.FastBFT’s performance is more modest at small n, while the other protocols degrade more as n increases.Source: §7.2 · p. 11, Figure 10 · p. 12
- For 1 MB replies, FastBFT is 260 times faster than Zyzzyva at n = 199; it still outperforms the other protocols after single-full-response optimization.FastBFT requires only the primary to reply, whereas other protocols may require many full-size replies; the alternative optimization can reduce their response latency but affects resilience if the designated replica is faulty.Source: Figure 11 · p. 12, §7.2 · p. 12, Figure 12 · p. 13
- With 250-byte transactions, FastBFT can process a maximum of 113,246 transactions per second in a network of around 199 replicas.The authors conclude that FastBFT balances performance and resilience.Source: §7.2 · p. 12
7.3 Security Considerations
- FastBFT’s TEE contains 7 interface primitives and 1,042 lines of code, compared with MinBFT’s 2 interface functions and 191 lines; sensitive keys and shares use side-channel-resistant cryptographic implementations.The paper argues that both TEE implementations are small enough for formal or informal verification, while the Paxos implementation requires more than 4,000 lines of code.Source: §7.3 · p. 13
8 RELATED WORK
The discussion motivates FastBFT’s focus on efficient deterministic variants and relates its aggregation to prior storage and TEE-based work.
8 RELATED WORK
- Randomized Byzantine consensus uses cryptographic coin tossing and completes in O(k) rounds with probability 1 - 2^-k, but typically has high communication and time costs; Honeybadger offers throughput comparable to PBFT.Randomized Byzantine consensus protocols were proposed in the 1980s,.Source: §8 · p. 13
- XFT separates Byzantine faults from asynchrony, tolerating crash faults in weakly synchronous networks and Byzantine faults in synchronous networks; XPaxos uses n = 2f + 1 replicas but retains O(n^2) all-to-all agreement multicast.Source: §8 · p. 13
- FastBFT’s aggregation resembles PowerStore’s two-round proof of writing: commit to a random value, then open it to prove completion, using hashes or polynomial evaluation without public-key operations.Source: §8 · p. 13
- Hybster is a TEE-based BFT protocol that uses parallelization to improve performance, an approach orthogonal to FastBFT’s contribution.Source: §8 · p. 13
9 CONCLUSION AND FUTURE WORK
FastBFT is reported to be 6 times faster than Zyzzyva and to sustain throughput better as network size grows; the authors argue it achieves near-optimal BFT efficiency. Future work will investigate topologies beyond trees.
9 CONCLUSION AND FUTURE WORK
- 6 times faster than Zyzzyva, FastBFT also shows a considerably slower throughput decline as network size grows, which the authors use to argue for near-optimal BFT efficiency.The authors argue near-optimality because Zyzzyva reduces replica overheads to near their theoretical minima.Source: §9 · p. 13
- FastBFT assumes TEEs have certified keypairs, and the protocol can run on standard TEE platforms such as GlobalPlatform.Certification may be performed by the TEE manufacturer or another trusted party at system initialization; the implementation uses Intel SGX.Source: §9 · p. 13
- Future work will examine topologies beyond trees to identify optimal or near-optimal choices for particular FastBFT network sizes.Source: §9 · p. 13