What is the difference between broadcast, crusader broadcast, gradecast, weak broadcast, detectable broadcast, and broadcast with abort? This post is a follow up to our basic post on: What is Broadcast?

The focus of this post is on computationally unbounded adversaries in the synchronous model, but we begin with considering both bounded and unbounded adversaries for the (classic) Broadcast problem.

Broadcast

Let’s start by defining the basic Broadcast problem again. We assume a set of $n$ parties. One party is designated as being called the sender. We assume the sender has some initial value.

A protocol solves the (classic) broadcast problem:

  1. Agreement: If an honest party outputs $x$, then all honest parties output $x$.
  2. Validity: If the sender is honest, then all honest parties output the sender’s value.

Assuming a PKI and a computationally bounded adversary, the Dolev-Strong Broadcast protocol solves Byzantine broadcast assuming an adversary that can control up to $n−1$ parties out of $n$ in the Synchronous model.

For computationally unbounded adversaries the FLM lower bound shows that broadcast is possible only when $n>3f$.

So for computationally unbounded adversaries, it is natural to ask are there relaxations of the broadcast problem that circumvent the $n\leq 3f$ lower bound?

Weak Broadcast and Detectable Broadcast

If we keep the agreement property and relax the validity property we arrive at the classic weak Byzantine Broadcast problem of Lamport from 1984.

A protocol solves the weak broadcast problem:

  1. Agreement: If an honest party outputs $x$, then all honest parties output $x$.
  2. Weak Validity: If the sender is honest, then all honest parties output either sender’s value or ⊥.
  3. Non-triviality: If all parties are honest, then all parties output the sender’s value.

Note on lower bounds: Fischer, Lynch, and Merritt show that weak broadcast is impossible for deterministic protocols for $n \leq 3f$.

For randomized protocols Karlin and Yao 1984, unpublished show that Broadcast must have a constant (more than $1/3$) error probability for $n\leq 3f$.

This lower bound for randomized protocols does not hold for weak Broadcast. Using randomization and private channels, Fitzi, Gisin, Maurer, and von Rotz 2002 strengthen Weak Broadcast to a notion of Detectable Broadcast that also provides a stronger notion of fairness that is important for SMPC. They show that it is possible to solve weak broadcast for $n>2f$ with just a negligible error probability.

Fitzi, Gottesman, Hirt, Holenstein, and Smith 2002 improve this bound to $n>f$ again with just a negligible error probability.

Crusader Broadcast and Gradecast

An alternate way to relax the broadcast problem is to keep the validity property and relax the agreement property. This gives us the Crusader broadcast of Dolev 1981.

A protocol solves the crusader broadcast problem:

  1. Weak Agreement: If an honest party outputs x, then all honest parties output either x or ⊥.
  2. Validity: If the sender is honest, then all honest parties output the sender’s value.

See this post for Crusader Boardcast with $O(n^2)$ words and $O(1)$ rounds, for any $f<n$ given a PKI.

Feldman and Micali 1988, 1997 strengthened the definition of crusader agreement so the output of the protocol is both a decision value and a $grade \in {0,1,2}$.

A protocol solves the Gradecast problem:

  1. Knowledge of Agreement: If an honest party outputs x with grade 2 then all honest parties output $x$ with $grade \in {1,2}$.
  2. Weak Agreement: If an honest party outputs x, then all honest parties output either x or ⊥.
  3. Validity with knowledge: If the sender is honest, then all honest parties output the sender’s value with grade $2$.

Gradecast and its variants are very important building blocks in many MPC and Byzantine Agreement protocols.

Note on lower bounds for adversaries that can simulate (for example computationally unbounded adversaries): impossibility for $n\leq 3f$ for deterministic protocol was shown by Dolev 1982. For randomized protocols, even a small constant error is impossible. This extension of the FLM lower bound to crusader agreement is folklore and was first mention by Goldwasser and Lindell, 2002, see this post for more details.

Broadcast with Abort

If we relax both Agreement and Validity we obtain the notion of Broadcast with abort of Goldwasser and Lindell, 2002.

A protocol solves the Broadcast with abort problem:

  1. Weak Agreement: If an honest party outputs x, then all honest parties output either x or ⊥.
  2. Weak Validity: If the sender is honest, then all honest parties output either sender’s value or ⊥.
  3. Non-triviality: If all parties are honest, then all parties output the sender’s value.

Goldwasser and Lindell show that this relaxation can be solved even if the adversary controls $n-1$ parties out of $n$. The solution is a natural two-round protocol and obtains perfect security. Here is the protocol for Broadcast with abort:

  1. The sender sends $x$ to all parties.
  2. Denote by $x_i$ the value received by party $i$ from the sender in the previous round. If $i$ did not receive a value from the sender in the first round, then it sets $x_i = ⊥$. Then, every party $i$ (for $i > 1$) sends its value $x_i$ to all other parties.
  3. Denote the value received by $i$ from $j$ in the previous round by $x_{i,j}$ Then, $i$ outputs $x_i$ if this is the only value that it saw ($\forall i>1: x_i=x_{i,j}$). Otherwise, it outputs $⊥$.

Notes

Many of the results of this post have been extended to Secure Multi Party Computation. More on that in later posts.

Please leave comments on Twitter