BULKBFT Consensus

Leaderless Byzantine fault-tolerant consensus for the BULK Network.

Overview

BULKBFT is a leaderless Byzantine fault-tolerant consensus protocol optimized for low-latency agreement on transaction sets. It achieves consensus in a single vote-commit round under partial synchrony, with no block proposer and no leader election.

System Model

We consider a set of $n$ validators $V = \lbrace v_1, v_2, \ldots, v_n \rbrace$, of which at most $f$ may be Byzantine, where:

$$f = \left\lfloor \frac{n - 1}{3} \right\rfloor$$

Each validator $v_i$ has a stake weight $w_i$ inherited from Solana. A set $S \subseteq V$ forms a supermajority if:

$$\sum_{v_i \in S} w_i > \frac{2}{3} \sum_{v_i \in V} w_i$$

We assume partial synchrony: there exists an unknown Global Stabilization Time (GST) after which all messages between honest validators are delivered within a known bound $\delta$.

Transaction Ingress

When a signed transaction $tx$ arrives at validator $v_i$, the ingress pipeline:

1. Computes a compact hash $h(tx)$ for deduplication
2. Stores the full transaction body in a local cache
3. Broadcasts $h(tx)$ to all validators in $V$ via authenticated channels

Validators only exchange hashes during consensus. Full transaction bodies are fetched from the local cache after commitment.

Authenticated Transport

Validator-to-validator communication uses the Noise Protocol Framework (IK handshake, AEGIS-128L encryption). Each validator’s Noise keypair is derived from their Solana Ed25519 identity key (converted to X25519 for Diffie-Hellman). This binds transport authentication to Solana stake - impersonation requires the validator’s private key.

Minisketch Set Reconciliation

Rather than exchanging full hash lists, validators use minisketch for efficient set reconciliation.

Each validator $v_i$ maintains a sketch $S_i$ - a compact probabilistic data structure representing their pending transaction set $T_i$. Given sketches from two validators, the symmetric difference $T_i \oplus T_j$ can be computed in $O(d)$ where $d = |T_i \oplus T_j|$ is the number of differing elements. This is a significant reduction from the naive $O(|T_i| + |T_j|)$ approach.

Protocol

Round Structure

Each consensus round $r$ proceeds in two phases.

Phase 1 - Vote. Each validator $v_i$ computes a digest $D_i^r$ of its proposed transaction set for round $r$:

$$D_i^r = H\left(T_i^r\right)$$

where $H$ is a collision-resistant hash function and $T_i^r$ is the set of pending transactions at $v_i$ after minisketch reconciliation. Validator $v_i$ broadcasts a signed vote $\langle \text{VOTE}, r, D_i^r \rangle_{\sigma_i}$ to all validators.

Phase 2 - Commit. Upon receiving votes from a supermajority, each validator computes the intersection digest - the set of transactions present in the proposed sets of all supermajority voters:

$$T_{\text{committed}}^r = \bigcap_{v_i \in S} T_i^r \quad \text{where } S \text{ is a supermajority}$$

Validator $v_i$ broadcasts a signed commit $\langle \text{COMMIT}, r, H(T_{\text{committed}}^r) \rangle_{\sigma_i}$.

Commitment. When a validator collects a supermajority of matching commit messages for round $r$, the batch is committed:

$$\text{CommittedBatch}(r) = \left(T_{\text{committed}}^r,\; r,\; \tau(r),\; \Sigma_r\right)$$

where $\tau(r)$ is the deterministic timestamp for round $r$ (see Deterministic Clock) and $\Sigma_r$ is the set of supermajority signatures.

Fast Path

Under partial synchrony (after GST), the protocol completes in one vote exchange plus one commit - two message delays total:

$$\text{latency}_{\text{fast}} = 2\delta$$

This is the theoretical minimum for BFT agreement and the common case during normal operation.

Slow Path

When synchrony breaks (network partitions, delayed messages, Byzantine validators), the protocol falls back to additional rounds for recovery. Safety is never compromised; only liveness may be temporarily affected until synchrony is restored.

Safety and Liveness

Safety. For any round $r$, if two honest validators commit batches $B$ and $B'$, then $B = B'$. This holds under asynchrony (no timing assumptions required).

Proof sketch. Commitment requires a supermajority of matching commit messages. Two distinct supermajorities must overlap in at least one honest validator (since $2 \times \frac{2}{3}n > n + f$). An honest validator sends at most one commit message per round, so both supermajorities must have committed the same digest.

Liveness. After GST, every round eventually produces a committed batch, provided at most $f$ validators are Byzantine.

Fault Tolerance

The protocol tolerates up to $f = \lfloor(n-1)/3\rfloor$ Byzantine validators. With the current validator set of 20+ independent operators, safety holds even if multiple validators are compromised or offline.

This is the same fault tolerance bound as PBFT, Tendermint, and HotStuff - the fundamental limit for Byzantine agreement.

CommittedBatch Output

The output of each consensus round is a CommittedBatch containing:

• $T_{\text{committed}}^r$ - the agreed transaction set (hashes, with bodies fetched from local cache)
• $r$ - the round number
• $\tau(r)$ - the batch timestamp
• $\Sigma_r$ - supermajority signatures attesting to the commitment

Every validator that participated in consensus holds the same CommittedBatch. From this point, execution is fully deterministic - no further communication is needed for validators to independently produce the same output state.