Dolev Strong Broadcast Protocol

Byzantine agreement cannot be achieved for \(n\) processors with at most \(t\) faults within \(t\) or fewer phases, provided \(n > t + 1\).

In other words, any protocol tolerating \(t\) Byzantine faults, regardless of what kind of messages it uses (authenticated or not), needs at least \(t+1\) synchronous rounds.

We show 2 rounds are not enough. Suppose for contradiction some protocol achieves agreement in 2 rounds with 4 nodes \(\{1, 2, 3, 4\}\), tolerating \(t=2\) faults.

A configuration is the complete communication pattern: which messages each node sends in each round. Each node has arrows to every other node per round.

This generalizes to any \(n > t+1\) with \(t\) rounds. We start from an honest execution with \(v=0\) and remove messages one at a time, peeling away entire nodes round by round from the last round backward. Each single removal changes only one receiver's view, so agreement forces the same output. After \(t\) nodes are fully hidden (\(t\) faults used), the remaining \(n - t > 1\) nodes hear nothing about \(v\), but the same stripping argument starting from \(v=1\) forces them to output 1. Since the silent configuration is the same in both cases, we have a contradiction.

With \(t+1\) rounds this fails: you can only hide \(t\) nodes, but by round \(t+1\) every surviving value carries \(t+1\) signatures, guaranteeing at least one honest signer.

Byzantine agreement with authentication can be achieved for \(n\) processors with at most \(t\) faults within \(t+1\) phases, using \(O(n^2)\) messages, assuming \(n > t+1\).

This matches the lower bound, so \(t+1\) rounds are tight.

Each processor maintains a set \(\text{extracted}\) of values it has seen with valid signature chains, initially empty. A message is valid at round \(i\) if it has the form \(\langle v \rangle_{S, p_1, \ldots, p_{i-1}}\) where all signers are distinct and the first is the sender \(S\).

Round 1: The sender \(S\) signs its value \(v\) and sends \(\langle v \rangle_S\) to all processors.

Rounds \(i = 2, \ldots, t+1\): Each processor \(p\):

1. Receives all messages from the previous round.
2. Discards any message that does not have \(i\) distinct valid signatures (including \(S\)'s).
3. For each non-discarded message carrying value \(v\): if \(v \notin \text{extracted}\), add \(v\) to \(\text{extracted}\).
4. Sign and relay: for each value just extracted (at most 2 total across all rounds), append \(p\)'s signature and forward to all processors whose signatures do not already appear on the message.
5. Once \(p\) has relayed 2 distinct values total, it stops sending.

Decision (after round \(t+1\)):

• If \(|\text{extracted}| = 1\), output the single extracted value.
• Otherwise, output \(\bot\) (including if \(\text{extracted} = \emptyset\), i.e., "sender fault").

Validity: If the sender is honest, it sends the same \(v\) to everyone in round 1. Authentication prevents faulty nodes from forging a message \(\langle v' \rangle_S\) for \(v' \neq v\). So every correct processor extracts only \(v\) and outputs \(v\).

Agreement: Suppose some correct processor \(p\) extracts value \(v\) for the first time at round \(i \leq t+1\). The message carrying \(v\) has \(i\) distinct signatures including \(S\)'s. Processor \(p\) signs and relays to all processors not yet on the chain. By round \(i+1 \leq t+2\)… but we only have \(t+1\) rounds. The key insight: if \(p\) extracts \(v\) at round \(t+1\), the message has \(t+1\) signatures. Since at most \(t\) processors are faulty, at least one signer is correct and must have relayed \(v\) earlier, so all correct processors already received \(v\) by round \(t\). In general, any value extracted by any correct processor will reach all correct processors by round \(t+1\).

At the end, every correct processor has the same \(\text{extracted}\) set. If it contains exactly one value, they all output it. If it contains multiple values (equivocation detected), they all output \(\bot\).

The sender \(S\) has \(v=0\). The protocol runs for \(t+1=4\) rounds.

• Round 1: \(S\) sends \(\langle 0 \rangle_S\) to nodes 2, 3, 4, 5. All extract \(\{0\}\).
• Round 2: Each node signs and relays \(\langle 0 \rangle_{S,i}\) to the other 3 non-sender nodes.
• Rounds 3–4: No new values extracted, relay limit not triggered. No messages.
• Decision: \(|\text{extracted}| = 1\), all output 0.

The sender \(S\) is Byzantine. It sends \(\langle 0 \rangle_S\) to node 2, \(\langle 1 \rangle_S\) to node 3, and nothing to nodes 4, 5. Blue arrows carry value 0; orange arrows carry value 1; red dotted arrows are missing messages.

• Round 1: Node 2 extracts \(\{0\}\). Node 3 extracts \(\{1\}\). Nodes 4, 5 receive nothing.
• Round 2: Node 2 relays \(\langle 0 \rangle_{S,2}\) to 3, 4, 5. Node 3 relays \(\langle 1 \rangle_{S,3}\) to 2, 4, 5.
  • Now: node 2 has \(\{0, 1\}\), node 3 has \(\{1, 0\}\), nodes 4, 5 have \(\{0, 1\}\).
• Round 3: Nodes relay the second value they extracted. Both values propagate further with additional signatures.
• Round 4: All nodes already have both values. Relay limit reached.
• Decision: \(|\text{extracted}| = 2\) for all correct nodes, all output \(\bot\). Agreement!

Byzantine agreement can be achieved for \(n\) processors with at most \(t\) faults within \(t+1\) phases using at most \(O(e) = O(n^2)\) messages.

This is the protocol described above. The key constraint: each correct processor relays at most 2 distinct values total across all rounds. Since a processor sends at most 2 messages per edge (one per value), and there are \(e = O(n^2)\) directed edges on a complete network, the total message count is \(O(n^2)\).

The honest and faulty run diagrams above illustrate this protocol directly.

Byzantine agreement can be achieved for \(n\) processors with at most \(t\) faults within \(t+2\) phases using at most \(O(nt)\) messages.

Key idea: Designate \(t+1\) nodes as relay processors. Non-relay (passive) processors only send messages to relay processors. This restricts the number of edges used: relay nodes communicate with everyone (\(O(nt)\) edges), passive nodes only reach relay nodes (\(O(nt)\) edges). Passive-to-passive communication is forbidden.

Why \(t+2\) rounds: The extra round (compared to Theorem 3) compensates for the restricted topology. If a correct processor extracts a new value by round \(t+2\), some correct processor extracted it by round \(t\), so some correct relay processor extracted it by round \(t+1\), and all correct processors receive it by round \(t+2\).

Why it works: The \(t+1\) relay processors act as a backbone. Since at most \(t\) are faulty, at least one relay processor is correct and will faithfully forward every value it sees.

Let \(e\) be the number of directed edges in the communication network (on a complete graph, \(e = n(n-1) = O(n^2)\), but on sparser graphs \(e\) can be much smaller). The following three examples show how \(e\) varies with network density:

If \(d\) is the $(t+1)$-diameter of a $(t+1)$-connected network of \(n\) processors with at most \(t\) faults, then Byzantine agreement can be achieved within \(t+d\) phases using at most \(O(e)\) messages.

Key idea: Theorems 1–4 assume a complete network. Theorem 5 generalizes to any network with enough connectivity. Run the same protocol as Theorem 3, but processors can only send messages along edges that exist in the graph. Each edge carries at most 2 messages (one per extracted value), so the total is bounded by \(2e = O(e)\). The tradeoff: on a non-complete graph, values need more hops to reach all processors, adding \(d - 1\) extra rounds beyond the \(t+1\) minimum.

$(t+1)$-connectivity means there exist \(t+1\) vertex-disjoint paths between every pair of nodes. This is necessary: if the adversary corrupts \(t\) nodes, it can block at most \(t\) of these paths, but at least one remains honest, ensuring eventual delivery.

$(t+1)$-diameter \(d\) is the maximum, over all node pairs, of the length of the longest among the \(t+1\) shortest vertex-disjoint paths. Intuitively, \(d\) measures the worst-case number of hops a message needs to reach its destination even when \(t\) intermediate nodes are corrupted. This is why the protocol needs \(t + d\) rounds instead of \(t+1\): the extra \(d - 1\) rounds compensate for the longer paths.

Byzantine agreement can be achieved on a complete network in \(t+1\) phases with \(O(nt)\) messages, assuming \(n > 2t\).

Key idea: Split processors into \(2t+1\) active and \(n - 2t - 1\) passive. Active processors (including the sender) run the Theorem 3 protocol among themselves, ignoring messages signed by passive processors. Passive processors never send; they only observe messages from active processors.

Active processors form a small clique of \(2t+1\) nodes. Running Theorem 3 among themselves costs \(O(t^2)\) messages. They also forward to passive nodes: \((2t+1)(n - 2t - 1) \cdot 2 = O(nt)\) messages. Total: \(O(t^2 + nt) = O(nt)\).

Passive processors decide by counting: if \(\geq t+1\) active processors sent more than one message (equivocation detected), output \(\bot\). Otherwise, extract values from messages that carry \(t+1\) distinct active signatures (guaranteeing at least one honest active signer).

Why \(n > 2t\) is needed: With \(2t+1\) active processors and at most \(t\) faulty, at least \(t+1\) active processors are correct. This majority among actives ensures passive processors can distinguish honest from faulty behavior.

No extra round needed (unlike Theorem 4): active processors reach agreement among themselves in \(t+1\) rounds, and passive processors observe the same messages in real time.