Pando: Extremely Scalable BFT Based on Committee Sampling

Pando: Extremely Scalable BFT Based on Committee Sampling

Speakers: Xin Wang

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=gagvu6_5pg8

Overview

This talk presents Pando, a Byzantine Fault Tolerant (BFT) consensus protocol that achieves extreme scalability by decoupling block data transmission from consensus ordering and using committee sampling to reduce communication complexity. While existing BFT protocols have been evaluated with at most 100-200 nodes, Pando successfully scales to 1,000 replicas -- more than four times the previous state-of-the-art -- while delivering approximately 70,000 transactions per second. The protocol achieves O(kappa) communication complexity where kappa is a security parameter independent of network size, maintaining security against weakly adaptive adversaries under partial synchrony.

Named after the world's largest living organism -- a massive grove of aspen trees in Utah that share a single root system underground -- Pando embodies the design goal of spreading across a huge network while remaining connected and resilient.

Background

▶ Watch: Why Pando: BFT scalability challenge and N-squared communication barrier (0:00)

Byzantine Fault Tolerance (BFT) is the fundamental building block of blockchain systems, enabling distributed nodes to reach agreement despite the presence of malicious participants. BFT protocols operate under different timing models: synchronous (known message delay upper bounds), partially synchronous (unknown upper bounds, the most practical model), and asynchronous (no timing guarantees).

Most practical BFT protocols target atomic broadcast (ABC), where replicas agree on a total order of transactions without client involvement. The critical scalability challenge is communication and computational overhead: traditional BFT protocols suffer from O(N^2) communication patterns where every node communicates with every other node, and require O(N) signature verification for quorum certificates. This causes performance to degrade severely as node count increases.

Prior work has explored committee-based approaches to reduce overhead, but faces a fundamental challenge: ensuring that the fraction of Byzantine nodes in a randomly sampled committee approximately mirrors the global fraction. The Algorand protocol, for example, claimed a minimum network size of 2,000 nodes to make committee sampling safe. Pando aims to use smaller committees while maintaining strong safety guarantees through novel probabilistic analysis.

Key Findings

▶ Watch: Committee sampling challenge and Chernoff bound guarantees (4:00)

• Scales to 1,000 replicas, more than 4x the previous state-of-the-art evaluation size
• Achieves approximately 70,000 transactions per second at scale with standard configurations
• O(kappa) communication complexity independent of network size, where kappa is a security parameter
• At 91 nodes, Pando with committee sampling (Pando 0.8) outperforms both the Star protocol and the full-participation variant (Pando 1.0) in peak throughput
• Even on the lowest-tier AWS instances (t2.micro), the protocol still achieves over 95,000 throughput at smaller scales, validating the communication-focused optimization
• Network bandwidth becomes the bottleneck at 1,000 nodes, where throughput drops to 1,600 TPS with limited bandwidth but reaches 73,000 TPS with standard bandwidth
• Three committees are sampled twice per epoch, with only committee members sending votes to minimize network overhead
• The protocol maintains near-optimal Byzantine resilience (tolerating up to approximately one-third Byzantine nodes)
• The implementation is open source in Go (~10,000 lines for the protocol, ~1,000 for evaluation)

Technical Deep Dive

▶ Watch: Atomic broadcast consensus: three committees sampled per epoch (8:00)

Decoupling Architecture. Pando's core architectural insight is separating block data transmission (moving the actual transaction data) from consensus ordering (agreeing on the sequence of blocks). Consensus operates only on digital signatures and compact hashes, not full block payloads. This dramatically reduces the data that must be processed through the expensive consensus mechanism.

Consistent Broadcast (CBC) Primitive. For block data transmission, Pando introduces a novel scalable consistent broadcast protocol that uses committee sampling. The Chernoff bound is used to prove that with high probability, the fraction of Byzantine nodes in a sampled committee mirrors the global fraction. This guarantee holds with communication cost of O(kappa) regardless of network size, enabling efficient block transmission without flooding the entire network.

Atomic Broadcast Consensus. For the ordering layer, Pando samples three committees twice per epoch and restricts voting to committee members only. The communication pattern is optimized so that agreement happens on compact hashes and signatures rather than full transaction payloads. The total communication complexity per consensus round is expressed as a function of message size m and security parameter kappa, both independent of the total network size N.

Probabilistic Safety Analysis. Unlike classical BFT which provides deterministic safety (guaranteed as long as fewer than N/3 nodes are Byzantine), Pando provides probabilistic safety through its committee sampling. The Chernoff bound analysis demonstrates that even with relatively small committee sizes, the probability of a safety or liveness violation is negligibly small. The committee size is parameterized so operators can trade off between communication efficiency and safety probability.

Adaptive Security. Pando targets weakly adaptive adversaries -- adversaries who can corrupt nodes over time but cannot instantly corrupt a node after seeing it selected for a committee. This is a practical threat model for real-world deployments where corruption takes time (social engineering, physical access, etc.).

Demo / Proof of Concept

▶ Watch: Results: 70K TPS at 1000 replicas, outperforming Star and Narwhal (10:00)

The evaluation was conducted on AWS instances with 4 vCPUs and 16 GB memory, scaling up to 500 virtual machines hosting 1,000 replicas. Three configurations were compared: Pando 1.0 (full participation, no committee sampling), Pando 0.8 (committee sampling with 80% of nodes), and the Star and Narwhal protocols as baselines.

Key results: At 91 nodes, Pando 0.8 outperforms both Star and Pando 1.0, demonstrating the efficiency gains of committee sampling even at moderate scale. As network size grows from 100 to 1,000 nodes, Pando shows graceful throughput degradation rather than collapse, with network bandwidth becoming the limiting factor. On low-end instances (t2.micro with limited CPU, memory, and bandwidth), throughput decreases as expected but remains above 95,000 TPS for smaller configurations, confirming that the communication overhead reduction is the primary performance driver. The implementation is open source on GitHub.

Defensive Implications

▶ Watch: Q&A: probabilistic vs deterministic safety guarantees across epochs (14:00)

• Blockchain scalability for security applications: BFT protocols that scale to 1,000+ nodes enable larger and more decentralized validator sets, increasing the cost of compromise for adversaries targeting blockchain-based security infrastructure
• Practical deployment on commodity hardware: Achieving meaningful throughput even on t2.micro instances means BFT-based systems can be deployed across diverse infrastructure without expensive hardware requirements
• Probabilistic vs. deterministic safety trade-offs: Organizations deploying Pando must accept probabilistic rather than deterministic safety guarantees, which requires explicit risk assessment of the committee sampling parameters for their specific threat model
• Adaptive adversary considerations: The weakly adaptive adversary model assumes corruption takes time, which is reasonable for most real-world scenarios but may not hold against highly capable state-level adversaries with pre-positioned access
• Open-source availability: The Go implementation enables security review and independent evaluation of the protocol's claims

Key Takeaways

• Pando scales BFT consensus to 1,000 replicas by decoupling block transmission from ordering and using committee sampling
• Communication complexity of O(kappa) is independent of network size, breaking the O(N^2) barrier of traditional BFT
• The protocol achieves ~70,000 TPS at scale, with graceful degradation as network bandwidth becomes the bottleneck
• Committee sampling uses Chernoff bounds to guarantee that Byzantine fractions in committees mirror the global fraction with high probability
• Safety is probabilistic rather than deterministic, requiring explicit parameterization of committee sizes for target security levels
• The open-source Go implementation enables practical deployment and community evaluation

About the Speaker(s)

Xin Wang (Shinuang) is from Shenzhen University. The work is a collaboration between Tsinghua University and Shenzhen University. The speaker presented the theoretical foundations and evaluation results clearly, though the Q&A session revealed that the probabilistic safety guarantees and their behavior over many epochs remain an area where additional clarity would benefit practitioners evaluating the protocol for deployment.