PaperlayerView exact revision on arXiv

Source-linked AI summary

SBFT: a Scalable and Decentralized Trust Infrastructure

Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu

arXiv:1804.01626v3cs.DC

TL;DR

SBFT addresses the challenge of scaling Byzantine fault-tolerant permissioned blockchains to decentralized, world-scale deployments. It combines several protocol and cryptographic mechanisms and evaluates them on 209 replicas tolerating 64 Byzantine failures. The system reports almost 2x better throughput and about 1.5x better latency than highly optimized PBFT, while deployments of thousands of replicas remain outside the study’s scope.

  • Problem

    Scaling BFT replication to tolerate tens of malicious nodes requires rethinking and re-engineering BFT algorithms for high scale.

  • Method

    SBFT combines collectors and threshold signatures, an optimistic fast path, reduced client communication, and redundant servers into a scalable BFT system.

  • Results

    Almost 2x better throughput and about 1.5x better latency were measured than with a highly optimized PBFT implementation in a 209-replica deployment tolerating f=64 Byzantine failures.

  • Takeaways & Limitations

    SBFT can be robustly deployed for hundreds of replicas and withstand tens of Byzantine failures in a world-scale geo-replicated setting.

  • Takeaways & Limitations

    Measuring real deployments of thousands of replicas that withstand hundreds of Byzantine failures is beyond the scope of this work.

Abstract

from arXiv · show

SBFT is a state of the art Byzantine fault tolerant permissioned blockchain system that addresses the challenges of scalability, decentralization and world-scale geo-replication. SBFTis optimized for decentralization and can easily handle more than 200 active replicas in a real world-scale deployment. We evaluate \sysname in a world-scale geo-replicated deployment with 209 replicas withstanding f=64 Byzantine failures. We provide experiments that show how the different algorithmic ingredients of \sysname increase its performance and scalability. The results show that SBFT simultaneously provides almost 2x better throughput and about 1.5x better latency relative to a highly optimized system that implements the PBFT protocol. To achieve this performance improvement, SBFT uses a combination of four ingredients: using collectors and threshold signatures to reduce communication to linear, using an optimistic fast path, reducing client communication and utilizing redundant servers for the fast path.

I. INTRODUCTION

SBFT targets scalable, decentralized BFT replication for hundreds of replicas in world-scale deployments. It combines linear communication, an optimistic fast path, reduced client communication, and redundant servers to improve scalability and performance.

  • Scaling BFT replication to tolerate tens of malicious nodes requires rethinking and re-engineering BFT algorithms for high scale.
  • 209 replicas withstanding f=64 Byzantine failures were evaluated in a world-scale geo-replicated deployment.
  • Almost 2x better throughput and about 1.5x better latency were measured relative to a highly optimized PBFT implementation.
  • SBFT combines collectors and threshold signatures, an optimistic fast path, reduced client communication, and redundant servers.Collectors reduce communication toward linear patterns, while threshold signatures reduce collector-message size and client acknowledgements.
  • In the common case, each client receives one acknowledgement message containing a single public-key signature instead of at least f+1 messages.
  • The fast path tolerates up to c crashed or straggler nodes among n = 3f+2c+1 replicas and falls back when more than c replicas are faulty.Experiments found c ≤ f/8 to be a good heuristic for deployments of up to a few hundred replicas.

B. Evaluating SBFT’s scalability.

SBFT was evaluated as a scalable BFT engine and blockchain over a world-scale WAN, including synthetic and Ethereum-derived smart-contract workloads. The evaluation reports strong throughput and latency relative to optimized PBFT, while thousands-replica deployments remain outside scope.

  • B. Evaluating SBFT’s scalability.: The blockchain executes EVM smart contracts, and the evaluation included 500,000 executions processed by Ethereum over a two-month period.
  • B. Evaluating SBFT’s scalability.: SBFT’s evaluation used a real wide-area network deployment that withstands f=64 Byzantine failures.
  • B. Evaluating SBFT’s scalability.: The implementation was compared with scale-optimized PBFT after each SBFT algorithmic ingredient was evaluated for performance improvement.
  • B. Evaluating SBFT’s scalability.: 209 replicas withstanding f=64 Byzantine failures achieved over 170 smart-contract transactions per second with average latency of 620 milliseconds.
  • B. Evaluating SBFT’s scalability.: Almost 2x better throughput and about 1.5x better latency were measured relative to a highly optimized PBFT implementation.

III. MODERN CRYPTOGRAPHY

SBFT combines threshold signatures, collector-based replication, and layered authenticated services to support scalable agreement and execution. Its protocol uses rotating roles, linear communication, and succinct certificates for replica and client acknowledgement.

  • Cryptographic foundation: Threshold signatures let k of n signers combine signature shares into one verifiable signature, while fewer than k shares cannot produce one.The scheme uses a single public key for verification and filters invalid shares from malicious participants.
  • Service architecture: SBFT supports a generic deterministic replicated service, an authenticated Merkle-tree key-value store, and an EVM smart-contract layer.The layered architecture is designed to support future integration of other smart-contract languages.
  • Roles and view changes: Replicas move between views using a protocol where backups may additionally serve as commit or execution collectors.Collectors gather threshold signatures, combine them, and disseminate the resulting signatures.
  • Fast-path agreement: In the fast path, the primary broadcasts a decision block, replicas send threshold-signature shares to C-collectors, and collectors return a succinct commit proof.Choosing different C-collector groups for each block balances load across replicas.
  • Execution and acknowledgement: The execution protocol uses E-collectors to combine state signatures into certificates, while authenticated proofs allow a single message to acknowledge each client request.The resulting fixed-size message contains one signature and supports per-request acknowledgement.

A. The Client

Clients send timestamped operations to the primary and normally accept execution from one authenticated reply. A timeout triggers retransmission and a PBFT-style fallback acknowledgement path.

  • Request submission: Each client maintains a strictly monotone timestamp and sends operation requests to the replica it believes is primary.The primary forwards the request to all replicas for agreement.
  • Fast acknowledgement: A client waits for one execute-ack reply and verifies the execution proof before accepting the returned value.The proof identifies the operation’s position, sequence number, state, and response value.
  • Client completion: After accepting execute-ack, the client marks the operation executed and records its return value.
  • Fallback: If the client timer expires, it resends the request to all replicas and requests a PBFT-style f + 1 acknowledgement path.

B. The Replicas

SBFT assigns replicas primary, commit-collector, and execution-collector roles, then processes decision blocks through pre-prepare, sign-share, and commit-proof phases. A fallback Linear-PBFT path provides progress when the fast path cannot proceed.

  • Replica state: Replicas maintain logs, view information, a stable sequence number, service state, and a window limiting outstanding blocks.
  • Replica credentials: Each replica holds shares for three threshold schemes, while replica communication uses authenticated point-to-point channels.
  • Roles: Replicas can serve as primary, C-collector, or E-collector, with collectors combining threshold signatures and disseminating certificates.
  • Role assignment: The primary is selected round-robin, while collector groups are pseudo-randomly chosen by sequence number and view; fallback always includes the primary as last collector.
  • Fast path: The fast path commits blocks through pre-prepare, sign-share, and commit-proof phases, with replicas signing hashed requests and C-collectors producing combined signatures.

D. Execution and Acknowledgement

SBFT executes committed request blocks, signs the resulting state digest, and uses E-collectors to create execution certificates. The fast path can revert to Linear-PBFT when its progress conditions are not met.

  • State execution: After preceding blocks execute, each replica applies the committed request block sequentially and updates the resulting state digest.
  • Execution proof: An E-collector combines f + 1 verified state-signature shares into a full-execute-proof and sends it to all replicas.
  • Client acknowledgement: For each request, the E-collector sends the client an execution acknowledgement containing the response, state signature, and execution proof.
  • Client verification: Clients mark requests executed after validating the state signature and proof, and retry through a regular PBFT acknowledgement path after timeout.
  • Fallback execution: Linear-PBFT uses collectors and threshold signatures to avoid all-to-all communication, with worst-case communication O(cn) and O(n) for constant c.
  • Fast-to-slow transition: Replicas include both fast-path σi(h) and Linear-PBFT τi(h) shares in sign-share messages, allowing fallback after an adaptive timeout.

F. Garbage Collection and Checkpoint Protocol

SBFT combines stable-sequence garbage collection with a bounded fast-path window and a view-change protocol that safely selects values across two commit modes.

  • A block is stable when at least f + 1 non-faulty replicas have executed it, allowing all previous decisions to be garbage collected.
  • Replicas periodically run checkpointing every win/2 to update the last stable sequence number ls.
  • Fast-path participation is restricted to sequences from le through le + (win/4), and committing sequence s updates ls to max{ls, s−(win/4)}.
  • During view change, replicas report their stable checkpoint and per-slot slow-commit and fast-commit evidence to the new primary.Each report covers ls through ls + win, with proofs or explicit no-commit and no-pre-prepare markers.
  • The new primary gathers 2 f + 2c + 1 view-change messages and processes slots from the highest valid stable sequence through ls + win.For each slot, replicas either decide that a value can be committed or adopt it as the new primary’s pre-prepare.
  • Safe-value selection compares the highest slow-path prepare view with the highest fast value supported by f + c + 1 messages, otherwise choosing a no-op.

1) Efficient view change via pipelining:

SBFT pipelines decisions by allowing later sequence numbers to commit before earlier pre-prepares arrive, while an alternative chained-hash design can make view changes more compact.

  • SBFT permits sequence number x to commit before pre-prepare information for sequences below x arrives, enabling substantial parallelism.View changes therefore suggest values for every sequence from ls through ls + win.
  • An alternative commits x only after all pre-prepares through x arrive and makes h_x commit to the preceding history via h_x = H(r||s||v||h_x−1).
  • Under the chained-hash alternative, the primary gathers two per-replica pairs: the highest slow-path prepare and the highest fast-path pre-prepare evidence.
  • The primary chooses the highest view among the two evidence types, preferring the slow-path pair when views tie.
  • Two values are sent irrespective of the window size, making this view change more efficient.

VI. SAFETY

SBFT’s safety proof handles both fast and slow commit modes by showing that view changes preserve the uniquely safe decision block across later views.

  • The safety theorem states that any two non-faulty replicas committing the same sequence number commit the same decision block.
  • The proof considers the earliest committing view and separates commits formed by τ(τ(h)) from those formed by σ(h).
  • For a τ(τ(h)) commit, a set of f + c + 1 non-faulty replicas preserves the committed value across every later view and excludes conflicting higher-view values.
  • The view-change analysis shows that fast values cannot outrank the relevant prepare evidence, so the protocol selects the committed request as the only possible safe outcome.
  • For a σ(h) commit, a set of 2 f + c + 1 non-faulty replicas preserves the committed value and constrains conflicting pre-prepares across later views.
  • The two lemmas together establish Theorem VI.1.

VII. LIVENESS

SBFT addresses liveness under partial synchrony through tuned view changes and collector-based progress, while its implementation supports parallel execution and cryptographic aggregation.

  • SBFT is deterministic and therefore lacks liveness in asynchronous mode; it uses exponential back-off, complaint-triggered changes, and continued progress when at most f replicas change view.
  • The protocol waits for at most n−f messages in both common-path and view-change progress, making it deadlock free and reactive after GST.After GST, progress follows the fastest n−f replicas rather than the maximum network delay.
  • With a non-faulty primary, progress after GST follows because the primary also serves as a collector.
  • View-change liveness follows because the primary forwards its decision together with signed proof, allowing replicas to repeat the same computation.
  • SBFT is implemented in C++ and includes PBFT-derived state transfer, adaptive batching, and parallel commitment of up to win = 256 sequence blocks.
  • Its implementation uses Crypto++, RELIC threshold BLS on BN-P254, cpp-ethereum’s EVM, and RocksDB.

IX. PERFORMANCE EVALUATION

The evaluation measures SBFT and progressively modified PBFT variants in continent- and world-scale WAN deployments using replicated key-value and Ethereum smart-contract workloads. SBFT’s four ingredients improve throughput, latency-throughput trade-offs, and resilience, with advantages over scale-optimized PBFT in both WAN settings.

  • Experimental setup: 200 replicas are evaluated across continent- and world-scale WANs, with experiments configured to withstand f = 64 Byzantine failures.The world-scale setup spreads replicas and clients across 15 regions on all continents.
  • Experimental setup: 500,000 Ethereum transactions spanning two months, including approximately 5,000 created contracts, are executed and committed to disk for the main evaluation.Micro-benchmarks use a key-value service, while the main workload uses RocksDB persistence.
  • Key-value benchmark: 2k per sec versus 1.5k per sec: Linear-PBFT improves loaded batched throughput over scale-optimized PBFT for 128 to 256 clients, at some latency cost.The improvement comes from reducing communication from quadratic to linear with a collector.
  • Key-value benchmark: 2.8k per sec: adding a fast path to Linear-PBFT increases throughput, improving both latency and throughput when executions have no failures.The fast path does not help when failures occur.
  • Key-value benchmark: A single execution-collector acknowledgement instead of f + 1 messages improves the latency-throughput trade-off in executions with and without failures.The result identifies server-to-client communication as a significant performance bottleneck.
  • Smart-contract benchmark: 378 transaction per second at 254 milliseconds versus 204 transaction per second at 538 milliseconds: SBFT nearly doubles throughput and latency performance over scale-optimized PBFT in the continent-scale WAN.In the world-scale WAN, SBFT obtains 172 transaction per second at 622 milliseconds versus PBFT’s 98 transaction per second at 934 milliseconds.
  • Smart-contract benchmark: 840 transaction per second is the non-replicated single-computer baseline; SBFT incurs a 2x slowdown at continent scale and a 5x slowdown at world scale.The baseline also executes smart contracts and commits results to disk without replication.

X. RELATED WORK

Related work establishes SBFT’s foundations in Byzantine replication, linear communication, fast paths, threshold signatures, and primary-backup designs. It distinguishes SBFT through software-only operation, real-world deployment, and a practical dual-mode protocol for large permissioned systems.

  • Foundations: PBFT and BASE provide foundations, while SBFT separates commitment from execution and builds its linear-message fast path on Zyzzyva techniques.These components connect SBFT to prior Byzantine replication and fast-path research.
  • Trust assumptions: SBFT is software-only and therefore remains bounded by the n ≥3 f + 1 lower bound, unlike systems using trusted hardware.A2M, TrInc, Veronese et al., and CheapBFT use secure hardware or trusted subsystems.
  • Cryptography: Threshold BLS signatures support SBFT’s public-key cryptography design, and the authors report the first deployment of threshold BLS in a real system.Prior systems had mentioned plans to use BLS threshold signatures.
  • Replication model: SBFT’s primary-backup paradigm funnels requests through a designated leader, enabling batching that is crucial for throughput in large multi-client scenarios.This contrasts with Byzantine quorum approaches where each client acts as a proposer.
  • Permissionless systems: Algorand uses a roughly 2000-user dynamic committee but was evaluated only in WAN simulation; under no-failure simulation, its 60-second latency is nearly 100x SBFT’s 600 milliseconds.SBFT is experimentally evaluated in a real world-scale geo-replicated WAN.
  • Closest systems: FastBFT shares linear PBFT and single-message acknowledgements but relies on Intel SGX and LAN-only evaluation, whereas SBFT assumes commodity hardware without a single-vendor trust dependency.The comparison concerns both security assumptions and evaluation setting.

XI. CONCLUSION

SBFT is experimentally validated as a scalable Byzantine fault tolerant replication library for large geo-distributed deployments. Its measured advantage comes from the combined algorithmic ingredients, while deployment beyond hundreds of replicas remains outside the study’s scope.

  • Conclusion: SBFT provides significantly better performance for large deployments over a wide-area geo-distributed network, with its advantage increasing as the number of clients increases.The system performs well when there are tens of malicious replicas.
  • Conclusion: Each of SBFT’s algorithmic ingredients improves measured performance, yielding almost 2x better throughput and about 1.5x better latency than highly optimized PBFT for about 200 replicas.The experiments involve real executions, hundreds of replicas, world-scale WANs, and persistent smart-contract results.
  • Conclusion: SBFT can be robustly deployed for hundreds of replicas and withstand tens of Byzantine failures.The conclusion frames this as evidence for the scalability of the system’s deployment model.
  • Scope boundary: Measuring deployments of thousands of replicas that withstand hundreds of Byzantine failures is beyond the scope of this work.The authors believe linear protocols may have a stronger advantage at higher scales, but that claim is not experimentally measured here.
Loading 1804.01626v3…