Paper Insights #37 - The Honey Badger of BFT Protocols

This paper was presented at ACM SIGSAC 2016, a premier conference in computer security. Authored by Andrew Miller et al. and affiliated with leading global universities, the paper is inherently technical and academically focused.

Readers should be advised that the content is complex. Given the considerable depth of the research, the insights will address only the most salient aspects to facilitate an understanding of BFT protocols generally and the specific innovations introduced by HoneyBadger. We won't go through the proofs of the different algorithms.

Paper Link

Recommended Read: Paper Insights - Paxos Made Simple where I introduced several concepts related to consensus.

Let's begin with some basic concepts.

Failure Types

There are two primary failure modes commonly observed in distributed systems:

• Crash Failures: These occur when a node terminates unexpectedly, potentially due to hardware malfunctions, software errors, or power outages.
• Byzantine Failures: These involve nodes exhibiting arbitrary or malicious behavior, such as sending incorrect data or deviating from protocol specifications.

In private networks, which are controlled and confined environments, only crash failures typically need to be considered. However, public networks, like those used by internet-scale systems and decentralized protocols such as blockchains, must account for Byzantine failures. Byzantine failures are a superset of crash failures.

This article will focus on Byzantine failures.

Network Models

When discussing distributed systems, we typically encounter four primary network models, each with different assumptions about message delivery times:

• Synchronous: In this model, there's a fixed upper bound, Δ, on how long any message can take to be delivered. This means a message sent at time t is guaranteed to arrive by t + Δ.
• Weak Synchronous: Here, the upper bound on message delay, Δ, isn't constant; it can increase over time. So, the delay bound itself is a function of time.
• Partial Synchronous: This model is asynchronous for an initial period but eventually becomes synchronous. There's an upper bound, Δ, on message delay that holds true only after a specific event called the Global Stabilization Time (GST).
• Asynchronous: This is the most permissive model, with no upper bound on message delay. Messages are guaranteed to eventually reach their destination, but there's no fixed time limit for delivery.

These models represent a spectrum of assumptions, from the most restrictive (synchronous) to the most relaxed (asynchronous):

Synchronous > Weak Synchronous > Partial Synchronous > Asynchronous

As we move from right to left, we are increasing our assumptions about the network's behavior. Real-world networks most closely resemble the asynchronous model.

Partial Synchrony

The Partial Synchronous model is particularly interesting because it bridges the gap between purely synchronous and asynchronous systems. It posits that there exists a time bound, Δ, and a special event, the Global Stabilization Time (GST), with these characteristics:

• The network's adversary must eventually cause the GST event to occur.
• Any message sent at time t will be delivered by Δ + max(t, GST). This means:
• If the message is sent after GST (t > GST), it will arrive by t + Δ. 
• If it's sent before or at GST, it will arrive by GST + Δ. 

In essence, a partially synchronous system behaves asynchronously until GST and then switches to behaving synchronously after GST. This model might seem impractical, but it's actually a good representation of how real-world networks behave. Most network experience outages for a limited time before stabilizing and resuming normal operation.

Consensus

Consensus algorithms address the fundamental challenge of achieving agreement on a single value among distributed nodes. These algorithms must satisfy the following properties:

• Termination (Liveness): Every non-faulty node eventually decides on a value.
• Integrity (Safety): If all non-faulty nodes initially propose the same value, that value must be the decided value.
• [Weaker Alternative] Validity (Safety): If a non-faulty node decides a value, then that value must be proposed by some non-faulty node. Validity is slightly weaker than Integrity.
• Agreement (Safety): All non-faulty nodes agree on the same decided value.

Consensus algorithms can generate a totally ordered list of values, which are essential for:

• Distributed logs: Crucial for systems like replicated state machines that need to execute instructions in a specific order.
• Ordered transactions: Necessary for systems such as blockchain (as we'll discuss later).

No Perfect Algorithm Exists! -  The FLP Impossibility

FLP (Fischer-Lynch-Paterson) impossibility result, as presented in Impossibility of Distributed Consensus with One Faulty Process. This theorem establishes that -

In an asynchronous network, no consensus protocol can simultaneously guarantee safety, liveness, and fault tolerance.

Known Algorithms

Although, no perfect algorithms exists, there are several algorithms for consensus particularly under different network and failure model assumptions - 

	Network	Safety	Liveness	Crash Faults	Byzantine Faults
Paxos	Asynchronous	Yes	No	Yes	No
Raft	Asynchronous	Yes	No	Yes	No
PoW/PoS	Asynchronous	No*	No*	Yes	Yes
Dolev-Strong	Synchronous	Yes	Yes	Yes	Yes
PBFT	Synchronous/ Partial-Synchronous	Yes	Yes	Yes	Yes
Streamlet	Partial-Synchronous	Yes	No*	Yes	Yes
HoneyBadger	Asynchronous	Yes	No*	Yes	Yes

* - They actually offer those properties, but only with high probability.

In this article, our focus will be on protocols that can handle Byzantine faults. See Paper Insights - Paxos Made Simple for a crash-failure-only consensus protocol.

Consensus under Byzantine Faults

Reaching consensus is significantly more challenging when Byzantine faults are possible, compared to dealing only with crash faults. Since participants on public networks can't always be trusted to behave correctly, Byzantine faults are a critical consideration.

A prime example of a system requiring Byzantine fault-tolerant consensus is blockchain. A blockchain is essentially a chain of blocks, each containing transactions. These transactions represent values that have been agreed upon through a consensus mechanism, and thus must be totally ordered within the chain.

All modern Byzantine networks under assume makes use of public key cryptography with a trusted party responsible for issuing the 

We can broadly categorize Byzantine based consensus protocols into two main types: non-permissioned and permissioned.

Non-Permissioned Protocols

In a non-permissioned network, any node can join and participate without needing explicit authorization. These protocols are designed to operate in an open, decentralized environment, typically across an asynchronous internet setting and in the presence of Byzantine faults.

Examples include:

• Proof-of-Work (PoW): Bitcoin is the most well-known example. Nodes mine new blocks by solving complex cryptographic puzzles, securing the network.
• Proof-of-Stake (PoS): Ethereum is a prominent example. Participants stake their cryptocurrency as collateral to validate transactions and create new blocks.

Both PoW and PoS protocols are built to achieve consensus and maintain network integrity even when some participants act maliciously (Byzantine faults) within an asynchronous internet environment. However, these protocols can only maintain their consensus properties (safety and liveness) under specific assumptions. For instance, the primary security vulnerability of PoW is the 51% attack. If malicious actors gain control of 51% or more of the network's total computing power (hashrate), they can compromise the network's safety. This majority control allows them to create a longer, alternative blockchain, enabling them to reverse confirmed transactions (like double-spending) or censor new ones.

Additional challenges:

• Vulnerability to Internet-Scale Attacks: They can be susceptible to widespread attacks like Sybil attacks, where a single entity creates numerous fake identities to gain disproportionate influence.
• Reliance on Cryptocurrencies for Incentives: These networks require native cryptocurrencies to incentivize participants (miners or validators) to secure the network.
• Slow Consensus: Reaching final consensus can be very slow, sometimes taking several hours for values to be irreversibly confirmed.

Permissioned BFT Protocols

Permissioned BFT protocols are designed for environments where participation is restricted and known. These protocols aim to solve consensus within a defined set of participants. They offer varying guarantees regarding safety, liveness, and fault tolerance depending on the underlying network model.

All permissioned BFT protocols assume that there can be f faulty nodes out of a total of N nodes in the network. This assumption is vital, as consensus is impossible if all nodes are Byzantine. Even crash consensus protocols (like Paxos) assume that the majority of nodes are non-faulty. Typical values of f are N-1, N/2, N/3.

Additionally, in a permissioned BFT, nodes communicate over authenticated channels. This means if Node A gets a message seemingly from Node B, it can be sure Node B actually sent it; adversaries can't forge/replay these messages. However, these communication channels don't necessarily need to be encrypted. The content of messages can be sent unencrypted, even if adversaries can read them.

BFT protocols are typically evaluated based on their latency, throughput, and scalability. Their complexity, in turn, is measured by the number of messages exchanged and the overall communication overhead.

Here are some notable permissioned BFT protocols:

• Dolev-Strong (1983)
• Practical Byzantine Fault Tolerance (1999)
• Streamlet (2020)
• HoneyBadger (2016)

Let's explore some of the protocols before diving into HoneyBadger.

Dolev-Strong (Synchronous)

The Dolev-Strong protocol is a foundational BFT protocols designed for N nodes to agree on a value, tolerating up to f malicious nodes (f < N). It guarantees both safety and liveness under a synchronous network model.

The protocol unfolds in f + 1 rounds:

• Round 0: A designated leader broadcasts its chosen value.
• Rounds 1 to f: Non-faulty nodes verify received messages. If valid and new, they add their signature and re-broadcast the message.
• Round f + 1: Each non-faulty node nodes the final set of authenticated messages to deterministically decide on the value.

Dolev-Strong has a message complexity of O(N²) and takes f + 1 time steps to complete. Messages also grow in size as they accumulate signatures. While theoretically significant, its synchronous network assumption severely limits its practical applicability in real-world.

Practical Byzantine Fault Tolerance (Synchronous and Weak-Synchronous)

Practical Byzantine Fault Tolerance (PBFT) is a seminal consensus algorithm designed to operate in synchronous and weak-synchronous network models. PBFT is used in Hyperledger Fabric.

PBFT assumes a total of N nodes, where at most f of these can be Byzantine nodes. To guarantee safety and liveness, at least 2f + 1 nodes must be non-faulty. This requires N >= 3f + 1.

PBFT uses a leader-based approach where one replica acts as the primary (leader) and others are backups. It employs a three-phase commit protocol for client requests:

• Pre-Prepare: The primary proposes a sequence number to all backups in a PRE-PREPARE. This phase is crucial for ensuring the primary is honest about the order of requests.
• Prepare: Backups verify the PRE-PREPARE message and broadcast their agreement to all other replicas in PREPARE messages.
• Commit: Once a supermajority of PREPARE messages are received, replicas broadcast COMMIT messages, signaling their final agreement.

It relies heavily on broadcast messages (O(N²) message complexity in its normal operation), which limits its scalability to a relatively small number of replicas (typically dozens to a few hundreds).

PBFT under Asynchrony

Under asynchronous network, PBFT is still safe (just like all consensus protocols, safety over liveness holds). However, liveness is affected. The paper provides a network scheduler (see section A in Appendix) which makes PBFT violate liveness.

Streamlet (Partial Synchronous)

In 2020, Streamlet was released which is a super simple consensus protocol that works under partial synchrony. Note that it is super complex to understand the proof for how it works (try the paper as a challenge!).

Assumes that f < N/3. Additionally, assumes synchronized clocks (required for liveness).

Streamlet proceeds in blocks instead of individual transactions (i.e. individual values). For consensus, one can think of the "blocks" as values itself. In Streamlet, once a proposed block accumulates votes from at least 2N/3 distinct players, it becomes notarized.

The algorithm proceeds as follows:

• In each epoch, the designated leader for that epoch proposes a new block. This proposed block always extends from the longest notarized chain the leader has seen. If there are multiple longest notarized chains, the leader can break ties arbitrarily.
• Every other node in the network (voter) observes the leader's proposal. If the proposed block extends from one of the longest notarized chains that the voter has seen, the voter casts a vote (a digital signature on the proposed block). Importantly, non-faulty nodes typically vote for the first valid proposal they see from the epoch's leader.

If three blocks are notarized in consecutive epochs along a notarized chain, then all blocks up to the second-to-last of these three blocks are confirmed (finalized).

Liveness in Streamlet

Streamlet is always safe under the all conditions. However, Streamlet depends on synchronized clocks for liveness which may not always hold.

Broadcast

In distributed systems, broadcast is how one node sends a message to all other nodes.

Ordering Guarantees

Broadcast mechanisms offer different guarantees about the order in which messages are received:

• Total Order: All messages from all senders are received in the exact same global order by every recipient.
• Causal Order: Messages are delivered in an order that respects their causal relationships (if message A causes message B, A is delivered before B).
• Single-Source FIFO: Messages from the same sender are received in the order they were sent by all recipients.

Reliability Guarantees

Beyond ordering, broadcasts also provide guarantees about reliability:

• Integrity: Only receive messages that were actually sent.
• No Duplicates: Won't receive the same message more than once.
• Non-Faulty Liveness: Messages sent by non-faulty nodes that will be received by all other non-faulty nodes.
• Faulty Liveness: If a faulty node sends a message, either all correctly non-faulty nodes receive it, or none do.

Types of Broadcast

These guarantees combine to define different types of broadcast:

• Reliable Broadcast: Provides only the reliability guarantees, with no specific ordering.
• Atomic Broadcast: Guarantees both total order and reliability.
• FIFO Broadcast: Combines single-source FIFO order with reliability.

Atomic Broadcast (ABC)

An atomic broadcast (ABC) guarantees the following properties:

• Validity (Liveness)*: If a non-faulty node broadcasts a message, then it eventually delivers it.
• Integrity (Safety): Each node delivers message at most once, and only if the message was actually broadcast by some node.
• Agreement (Safety): If a message is delivered by some non-faulty node, then the message is eventually delivered by every other non-faulty node.
• Total Order (Safety): All non-faulty nodes agree on the exact same delivery order of messages.

* - Unlike in consensus protocols, validity is a liveness property in broadcast systems.

ABC and Consensus

It's important to understand that ABC is equivalent to solving consensus. This means that the FLP impossibility result applies to ABC: it's not possible to achieve ABC in a completely asynchronous network if even one node can fail.

Reliable Broadcast (RBC)

A reliable broadcast (RBC) guarantees the following properties (dropping the total order property of ABC):

• Validity (Liveness): If a non-faulty node broadcasts a message, then it eventually delivers it.
• Integrity (Safety): Each node delivers message at most once, and only if the message was actually broadcast by some node.
• Agreement (Safety): If a message is delivered by some non-faulty node, then the message is eventually delivered by every other non-faulty node.

RBC may seem same as consensus, however, there are subtle differences. RBC focuses on getting a single, specific message from one sender to all non-faulty nodes, ensuring everyone consistently receives that same message. In contrast, consensus is about a group of nodes, each starting with its own proposed value, collectively agreeing on one final value from those proposals.

RBC is achievable in asynchronous networks and in presence of Byzantine faults. Bracha's Protocol is a classic example that demonstrates how to achieve Byzantine fault-tolerant RBC. Here's a simplified illustration of its phases (assuming f < N/3):

• A node sends an (SEND, m) message to all other nodes.
• Upon receiving an (SEND, m) message, nodes respond by sending an (ECHO, m) message to everyone.
• A node sends a (READY, m) message to all others when it has seen enough (ECHO, m) messages. This indicates a sufficient number of peers have echoed the message.
• A node delivers m once it has received 2f + 1 (READY, m) messages.

Perhaps, the agreement property is the one that makes this protocol more sophisticated than a simple message send to all the nodes. Due to it, all nodes need to acknowledge to each other that they are ready to send a message. Say the size of the message is |v|, then the complexity will be O(N² |v|).

There is another variant of RBC called terminating RBC which adds a Termination property to RBC. Even that is not equivalent to consensus.

Erasure Encoding

Erasure encoding, also known as Forward Error Correction (FEC), is a powerful technique for protecting data during storage or transmission. It adds redundancy to a message, allowing the original data to be perfectly reconstructed even if some parts are lost or corrupted.

Here's how it works: An original file or message is divided into k data blocks. From these k blocks, m additional parity blocks are computed. The total number of blocks then becomes n = k + m.

• k: Number of original data blocks.
• m: Number of generated parity blocks.
• n: Total number of blocks (n = k + m).

To retrieve the original data, you only need any k of the n total blocks.

Reed-Solomon codes are the most widely used erasure codes, providing the maximum possible fault tolerance for a given amount of redundancy.

RBC with Erasure Encoding

Erasure encoding can be cleverly applied to RBC to enhance efficiency and robustness.

Algorithm

A message is broken into N - 2f data blocks, and 2f parity blocks are computed, resulting in N total blocks.

The node roughly follows these steps (Figure 2):

• The sender distributes each of the N encoded blocks to a different node.
• Nodes that receive a block then echo it by sending their received block to all other nodes.
• Once a node receives N - f distinct echoed blocks, it's guaranteed that at least N - 2f of them are valid (since at most f Byzantine nodes could send incorrect blocks). With N - 2f valid blocks, the original message can be reconstructed.

Ensuring Data Integrity with Merkle Trees

A critical challenge arises: how can a node be sure that the N - f blocks it received are actually correct and not corrupted by Byzantine nodes, which would lead to bad data upon reconstruction? This is where a Merkle tree becomes essential.

The solution involves:

• The sender first computes a Merkle tree of all N encoded blocks (data and parity). A jth node receives only the jth branch of the merkle tree from root to leaf as part of the initial broadcast.
• When a node receives N - f blocks and corresponding branches during the ECHO phase, it can now use any of the N - 2f blocks to interpolate all other blocks. Then, it can verify the integrity of the received blocks by computing the Merkle root hash. If it  doesn't match the Merkle root hash, RBC is aborted.

Complexity Analysis

Let |v| be the size of the message. The complexity of this erasure-encoded RBC scheme can be estimated as:

• SEND: Roughly O(|v|) as the message is split and parts are sent.
• ECHO: This is the most dominant. It involves N nodes each sending parts of the message to N other nodes, leading to O(N |v|) for the message parts themselves. Additionally, the Merkle tree verification adds a factor of log N, leading to an overall O(λ N² log N) for NxN communication. The additional λ factor is the cryptographic security parameter.

The overall complexity is thus approximately O(N |v| + λ N² log N). This provides an improvement when the message size |v| >> N log N.

Threshold Encryption

Threshold Public-Key Encryption (TPKE) lets anyone encrypt a message using a single public key (PK). Decrypting it requires the cooperation of a threshold of participants, each holding a share of the secret key. Specifically, if there are N total secret key shares, at least f + 1 of them are required to decrypt the message, protecting against up to f Byzantine faults.

API

• TPKE.Setup(1^λ) -> PK, {S_i}: Generates the public key and distributes N unique secret key shares (S_i) among the participants.
• TPKE.Enc(PK, m) -> C: Encrypts a message m into ciphertext C using the public key.
• TPKE.DecShare(S_i, C) -> σ_i: A participant uses their secret share S_i to create a partial decryption σ_i. This σ_i doesn't reveal the message on its own.
• TPKE.Dec(PK, C, {i, σ_i}) -> m: Combines at least f + 1 partial decryption shares (σ_i) to fully reconstruct the original plaintext message m.

The Mathematics Behind It

At its core, TPKE leverages Shamir's Secret Sharing Scheme. This mathematical technique allows a secret (like the private key) to be divided into multiple pieces, such that only a predefined minimum number of pieces can reconstruct the original secret.

In a Byzantine system, non-faulty nodes will only release their decryption shares when the protocol demands it. Byzantine nodes, however, will undoubtedly share their shares among themselves. That's why, with up to f Byzantine nodes out of N total, it's essential to require at least f + 1 decryption shares for successful decryption.

Common Coin

A common coin is a distributed protocol that enables a set of nodes to agree on a shared random bit (0 or 1). All participants will ultimately concur on the single value of this random bit.

The common coin has two essential properties:

• Agreement: All non-faulty nodes will output the same random bit.
• Unpredictability: The value of the random bit cannot be predicted by an adversary until a sufficient number of non-faulty nodes have contributed to its generation.

Realizing a Common Coin with Threshold Cryptography

A common coin can be efficiently implemented using TPKE, specifically leveraging its underlying threshold signature scheme.

Instead of encrypting data, we use the threshold signature capabilities of a TPKE setup. In an (N, f) threshold signature scheme:

• There are N unique signature shares distributed among N parties.
• Any f + 1 of these N signature shares are required to reconstruct a complete, valid signature on a message.

Here's how this works to generate a common coin (due Cachin, in Figure 12):

• Each non-faulty node multicasts its threshold signature share (ThresholdSign(PK, SK_i, sid)), where PK is the public key, SK_i is its individual secret key share, and sid is a unique, agreed-upon nonce that serves as the name for this specific common coin instance.
• Upon receiving f + 1 valid signature shares for the sid, a node can combine them to form a complete signature. It then verifies this complete signature using ThresholdVerify(PK, ...).

The bits of this final, verified signature (on sid) serve as the source of the common random bits for the coin. Since the signature is deterministically derived from inputs that are hidden until the threshold is met, its value is unpredictable to an adversary beforehand but universally agreed upon once reconstructed. This method ensures that all non-faulty nodes will eventually agree on the same random bits, as they will all reconstruct the identical signature from the same set of f + 1 valid shares.

Complexity

Common coin requires only one round of asynchronous communication. The communication cost is O(λ N) where λ is the cryptographic security parameter (length of the verified signature).

Binary Agreement

Binary agreement is a specialized form of consensus where distributed nodes agree on a single 0 or 1 bit. It shares the core properties of any robust consensus protocol:

• Termination (Liveness): Every non-faulty node eventually decides on a value.
• Validity (Safety): The decided value must be proposed by at least one non-faulty node.
• Agreement (Safety): All non-faulty nodes agree on the same decided bit.

Consensus and Binary Agreement

Consensus is more general than binary agreement. Yet, binary agreement faces the same fundamental challenge: the FLP Impossibility. This means a deterministic binary agreement algorithm cannot guarantee both safety and liveness in an asynchronous network if even one node fails.

Asynchronous Binary Agreement (ABA) with a Common Coin

In an asynchronous network, the critical challenge for binary agreement (and general consensus) is ensuring liveness. As seen in protocols like Paxos, randomization is key to achieving this. A common coin provides this necessary randomization, allowing nodes to agree on a shared random bit to break deadlocks and ensure progress.

Here's a high-level overview of an Asynchronous Binary Agreement (ABA) protocol using a common coin (shown in Figure 11, due Moustefaoui):

Initialization: Each node P_i starts with an initial proposal v_i ∈ {0, 1}.

Repeated Rounds (k = 1, 2, ...): 

• Each node P_i broadcasts its current estimate e_i for the bit. Upon receiving a sufficient number of valid estimates, nodes ECHO them.
• P_i collects votes. If it sees a clear majority (e.g., 2f + 1 for 0 or 1 in a Byzantine setting), it updates its estimate.
• If P_i has unambiguous support for a value (e.g., N − f votes for 0), it tries to decide that value and broadcasts a DECIDE message.
• If P_i cannot make a deterministic decision (e.g., it sees support for both '0' and '1', or insufficient support for either), it invokes a common coin sub-protocol. This sub-protocol outputs a shared random bit c ∈ {0, 1} that all non-faulty nodes will agree on. P_i uses the common coin c to update its estimate for the next round.
• If a node receives a DECIDE message for a value from enough peers (e.g., 2f + 1), it terminates and outputs that value.

This iterative process, driven by the random input from the common coin, guarantees probabilistic liveness: the protocol will eventually terminate for all non-faulty nodes, even if the exact number of rounds isn't fixed.

The communication complexity is O(λ N²) (the λ factor comes from the use of common coins) with a high probability of completing within O(1) rounds. Additionally, it can complete within O(k) rounds with a probability of 1 - 2^-k. 

Common Subset

This is again a specialized form of consensus. Each node starts with its own private set of values. The goal is for all non-faulty nodes to eventually agree on a single, final set of values such that:

• Termination (Liveness): All non-faulty nodes eventually output a set of values.
• Agreement (Safety): All non-faulty nodes output the exact same set of values.
• Validity (Safety): The output set must only contain values that were initially proposed by some non-faulty node. It doesn't contain any values from Byzantine nodes.

Asynchronous Common Subset (ACS)

Asynchronous Common Subset (ACS) is a fundamental building block that can be implemented using two key primitives: RBC and ABA. RBC ensures that all non-faulty nodes receive the same set of messages from a particular sender. ABA is then used to decide which of these sets to collectively finalize. It's important to note that ABA can begin before all RBCs are complete due to the asynchronous nature of communication (no known Δ for message delivery).

Ben-Or Algorithm

The Ben-Or protocol (as illustrated in Figure 4) is a classic example of this implementation.

In essence, every node i simultaneously initiates an RBC (RBC_i) to broadcast its message. Concurrently, ABA (BA_i) instances are run to agree on N bits, where each bit corresponds to whether a specific node's broadcasted message should be included in the common subset. If BA_i for node i is finalized as 1, that message will be included.

A key aspect of Ben-Or is that RBC and ABA can run in parallel. If a node observes at least N - f bits in the bit vector set to 1, it can assume that any unreceived broadcasts from other nodes will have their corresponding bits set to 0. This mechanism accounts for Byzantine failures, where up to f nodes might not send any messages at all. While it might seem counterintuitive for ABA to finish before RBC, this is an expected behavior of the protocol and doesn't hinder its correctness.

A Critical Downside: Censorship

Despite its utility, the discussed ACS protocol has a significant drawback: censorship vulnerability. Since the protocol can conclude when only N - f bits in the bit vector are 1, an adversary can continuously block messages (and therefore transactions) from a single non-faulty node. This prevents that node's message from ever being included in the common agreed-upon set, effectively censoring its contribution.

Complexity Analysis

Total cost of RBC = N * Cost of single RBC = O(N² |v| + λ N³ log N)

Total cost of ABA = N * Cost of single ABA = O(λ N²)

Total cost = O(N² |v| + λ N³ log N) given |v| >> λ.

Tor

Tor is a public service on the internet that enables anonymous message exchange, ensuring that a message's recipient can't identify the sender's address. This makes it an excellent tool for bypassing censorship by centralized services.

At its core, Tor functions as a distributed multi-hop proxy system. It uses a routing protocol called onion routing. When a client sends a message, it typically travels through multiple hops—for instance, three—before reaching its destination. The client first obtains the public keys of these hops from the Tor public directory. Then, the message undergoes a layered encryption process:

• The message is initially encrypted with the server's public key.
• This encrypted message, along with the server's IP, is then encrypted with the public key of the last hop.
• This process continues backward, with each layer of encryption corresponding to a successive hop.

The result of this onion routing is that each hop in the relay only knows the immediately preceding and succeeding hops, not the entire route. Similarly, the final server only sees the last hop that delivered the message, effectively concealing the original sender's identity.

HoneyBadger

Sorry for a long introduction, but there are so many things that go into building HoneyBadger that I felt it is important to introduce each one of them.

HoneyBadger is a consensus protocol designed for:

• Asynchronous networks.
• Up to f < N/3 Byzantine faults. 
• Trusted setup (i.e. permissioned setup).

HoneyBadger ensures safety under all conditions. However, unlike non-randomized protocols, which cannot guarantee liveness under asynchronous conditions (FLP impossibility), HoneyBadger leverages randomized algorithms to achieve probabilistic liveness. This means it ensures liveness with a high probability, as its underlying components, such as ACS, rely on common coins that also provide probabilistic liveness.

Goals

Beyond simply achieving consensus in an asynchronous environment, HoneyBadger aims for two key objectives:

• High Transaction Throughput: The protocol prioritizes the volume of transactions processed over individual transaction latency. It achieves this by batching and processing large sets of transactions simultaneously, leading to communication efficiency.
• Censorship Resilience: As discussed earlier, standard ACS is susceptible to censorship. HoneyBadger counters this vulnerability by integrating TPKE, which requires a minimum number of parties to decrypt messages, thus preventing individual malicious actors from censoring transactions.

It's worth noting that the problem of atomic broadcast in BFT systems can be reduced to ACS if transactions are batched. ACS provides an unordered set of sub-batches from each node, which are then ordered using a predefined property (e.g., lexicographically).

The Algorithm

Figure 1 illustrates the core HoneyBadger algorithm. Here's a breakdown of its steps:

• Step 1: Batching and Encryption: Each node randomly selects a batch of transactions of size B from its local pool. This selection can be based on priority or FIFO. The selected batch forms a message, which is then encrypted using the public key of the threshold encryption scheme, i.e., TPKE.Enc(PK, m). This encryption ensures that the message cannot be decrypted unless at least f + 1 parties cooperate.

• Step 2: ACS Input: The encrypted messages from all nodes are then input into the ACS protocol. The final vector is agreed-upon (encrypted) messages containing the transactions.

• Step 3: Decryption: For every selected encrypted message, each node obtains a decryption share. These shares are then broadcast using RBC.

• Step 4: Block Generation: Once all selected messages are decrypted, the transactions within them are sorted according to a common order (e.g., by a generated ID or hash). This final sorted list of transactions forms a new block in the blockchain.

The crucial sorting step in Step 4 is what transforms ACS (a common set determination algorithm) into an atomic broadcast or total order broadcast consensus algorithm, enabling the final block to be consistently ordered across all non-faulty nodes.

Complexity

Cost of ACS = O(N² |v| + λ N³ log N) 

Cost of decryption = O(λ N²)

Note, the batch size from each node, |v|, is set to Ω (λ N log N) and hence the total message size across all nodes is Ω (λ N² log N)

Cost of ACS =  O(λ N³ log N)

Total cost = O(λ N³ log N)

Section 4.5 has more analysis and appendix B has some detailed proofs for them.

Evaluation

HoneyBadger's performance characteristics reveal that it's not optimized for small batch sizes. The primary communication overhead stems from RBC and the decryption process in threshold cryptography.

Figure 5  illustrates that the communication cost remains relatively constant even as batch sizes increase up to 128 transactions. Beyond this point (for N=8, f=2), the batch size becomes the dominant factor in the total communication cost. Interestingly, with a larger number of nodes, the batch size becomes less of a dominant cost factor. For instance, with N=128 and f=32, the batch size doesn't dominate the cost until it reaches 16,000 transactions.

The authors conducted experiments on Amazon EC2, though it's important to note that the test environment lacked authentication setup (which would incur additional overhead in a production environment with TLS). As shown in Figure 6, throughput consistently increased with larger batch sizes, even when varying the number of nodes (with f = N/4). Specifically, the system achieved 20,000 transactions/second with 40 nodes and 1,500 transactions/second with 104 nodes.

While throughput increases, so does latency, as depicted in Figure 7. Larger batch sizes necessitate longer processing latencies, with transaction latencies observed in the order of minutes. The positive slope of this plot indicates that throughput can still be increased, avoiding full saturation.

Compared to PBFT, HoneyBadger achieves higher throughput, even though their asymptotic communication costs are similar. This is because HoneyBadger distributes communication across all nodes, whereas PBFT tends to create hotspots around leader nodes.

To assess HoneyBadger's performance over Tor, the authors set up HoneyBadger nodes on single machines and configured communication paths through Tor, using five random relay hops. HoneyBadger achieved a transaction volume of 800 transactions/second. However, latency proved to be highly variable; a single message could be delayed by up to 316 seconds, with an average delay of 12 seconds (variance = 2208). Crucially, HoneyBadger's asynchronous design allowed it to tolerate this significant network variance.

Paper Review

I found this paper to be incredibly challenging and thought-provoking, requiring multiple re-reads to grasp its complexities. My understanding was further aided by extensive research online, particularly on blogs like Decentralized Thoughts. This experience truly underscored the vastness and density of the blockchain space, especially when delving into proof construction, which proved to be a significant mental exercise. While this paper is undoubtedly a foundational read for beginners in blockchain and cryptography, it's clear the field has evolved dramatically since its publication. I highly recommend approaching it with considerable patience.