A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary

Davide FreyarXiv 2023 · DOI · arXiv

Abstract: Robust and effective distributed systems require good theory and good engineering, not separately but in concert: user requirements and system constraints are not merely implementation details but often must inform the design of algorithms for such systems. Blockchains are an excellent example. The heart of a blockchain is its (Byzantine) consensus protocol, and consensus protocols have been extensively studied in the theory community for decades. But traditional consensus protocols are not directly applicable to blockchains, which have, or hope to have, millions of participants. Furthermore, public blockchains, which allow anyone to participate, must have some mechanism to guarantee the security of the protocol, and traditional fault models do not adequately capture the assumptions of such mechanisms. In this talk, I will discuss these and other ways in which theory and practice meet in the context of the Algorand blockchain, and how Algorand is able to achieve high transaction throughput with low latency.

Introduction

In the world of distributed systems, Byzantine Reliable Broadcast (BRB) is a foundational protocol. It ensures that even if some participants (nodes) are malicious (Byzantine), all "correct" nodes eventually agree on the same set of messages. Traditionally, researchers assume the network between these nodes is reliable—that every message sent will eventually arrive. However, real-world networks are messy: they drop packets, suffer from "tail latencies," or face targeted attacks.

This research addresses the challenge of building robust broadcast protocols that survive both malicious nodes and a network that actively loses messages, all without the heavy computational overhead of digital signatures. The authors introduce a new communication building block called $k2\ell$-cast to build reliable broadcast protocols that tolerate both Byzantine nodes and message-dropping networks.

The Dual Adversary Model

Most distributed algorithms rely on quorums—waiting for a certain number of responses before moving to the next step. In a standard Byzantine model, we assume up to $t$ nodes are faulty. If we have $n$ nodes, we might wait for $n-t$ responses.

However, this paper introduces a Message Adversary (MA) of power $d$, which can suppress up to $d$ messages for every broadcast. This creates a "dual adversary" scenario where $t$ nodes can lie or collude, and the network can simultaneously "lose" $d$ messages sent by correct nodes. To navigate this complexity, a rigorous set of notations is required to define the system's bounds and quorum sizes.

Table of acronyms and notations defining the system parameters and quorum thresholds.

Methods: The $k2\ell$-cast Abstraction

The core contribution is a new abstraction called $k2\ell$-cast (short for $k$-to-$\ell$-cast). Instead of a monolithic broadcast, the authors break the process down into a many-to-many primitive defined by four parameters ($k', k, \ell, \delta$). It ensures that if enough correct processes ($k$) send a message, then a significant number of correct processes ($\ell$) will eventually deliver it.

Modular Reconstruction

The authors use $k2\ell$-cast to "deconstruct" and then "reconstruct" two classic BRB algorithms:

  • Bracha’s Algorithm (1987): A gold standard for signature-free BRB.
  • Imbs and Raynal’s Algorithm (2016): A more recent, latency-optimized version.

By replacing the internal message-passing logic of these algorithms with $k2\ell$-cast, they make them naturally tolerant to message loss. The implementation follows a specific logical flow from the underlying system constraints to the final object.

Flowchart illustrating the derivation of a $k2\ell$-cast object from system parameters and theoretical assumptions.

Quorum Engineering

The implementation uses two distinct thresholds to overcome the Message Adversary:

  1. Forwarding Threshold ($q_f$): How many messages a node needs to see before it helps "spread the word" to others.
  2. Delivery Threshold ($q_d$): How many messages a node needs to see before it officially "delivers" the broadcast to the application.

This separation creates a "chain reaction" that allows a message to propagate through the network even if the Message Adversary is actively trying to suppress it. By lowering the forwarding threshold, correct nodes can overcome the $d$ messages lost to the adversary.

Key Results and Resilience

The paper provides a formal implementation of a signature-free $k2\ell$-cast and proves its correctness under a set of four assumptions (sf-$k2\ell$-Assumptions 1-4). Surprisingly, when the network is perfect ($d=0$), the reconstructed versions of Bracha’s and Imbs-Raynal’s algorithms are actually more efficient than the originals. They use smaller quorums and terminate faster because the $k2\ell$-cast logic is more refined.

In terms of resilience, for a system of $n=100$ nodes, the protocol maintains high global delivery guarantees even with 6 Byzantine nodes and a network losing 9 messages per broadcast ($d=9$). In the reconstructed Bracha algorithm, the forwarding threshold is reduced to $t+1$, whereas in the original, it was effectively much higher ($\\approx \\frac{n+t}{2}$).

Limitations and Future Work

To guarantee safety and liveness, the system requires a specific relationship between $n, t,$ and $d$. For the Bracha reconstruction, this is $n > 3t + 2d + 2\sqrt{td}$. This is more restrictive than the standard $n > 3t$ required for asynchronous Byzantine systems, representing the "cost" of network unreliability.

Future work suggests that $k2\ell$-cast could be a foundational building block for other distributed problems, such as self-stabilizing systems or churn-tolerant systems where nodes frequently join and leave. For engineers building decentralized systems on unreliable infrastructure, this modular approach offers a way to trade a bit of node overhead for significantly better network resilience without the cost of signatures.

Summary updated

Abstract

Robust and effective distributed systems require good theory and good engineering, not separately but in concert: user requirements and system constraints are not merely implementation details but often must inform the design of algorithms for such systems. Blockchains are an excellent example. The heart of a blockchain is its (Byzantine) consensus protocol, and consensus protocols have been extensively studied in the theory community for decades. But traditional consensus protocols are not directly applicable to blockchains, which have, or hope to have, millions of participants. Furthermore, public blockchains, which allow anyone to participate, must have some mechanism to guarantee the security of the protocol, and traditional fault models do not adequately capture the assumptions of such mechanisms. In this talk, I will discuss these and other ways in which theory and practice meet in the context of the Algorand blockchain, and how Algorand is able to achieve high transaction throughput with low latency.
BibTeX
@misc{frey2023modular,
  author = {Davide Frey},
  title = {{A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary}},
  year = {2023},
  eprint = {2204.13388},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.13388},
}
Figure