Byzantine Fault Tolerant Consensus under Synchrony: Signed FloodSet (Consensus part 3)
From crashes to lies
In the previous post (part 2), we saw how FloodSet achieves consensus when faulty processes can only crash: everyone repeatedly forwards the values they have seen, then decides after (f+1) rounds.
What if faulty processes can lie?
A Byzantine process can send different messages to different people, withhold messages, or release them at the worst possible moment. Flooding still works, but it needs an extra ingredient: a growing chain of signatures, checked against the round number.
This is the idea behind the Dolev–Strong authenticated broadcast algorithm. We’ll use it to share everyone’s proposals, then choose a consensus value.
The setting
There are (n) processes, at most (f) of them faulty. We assume:
- Synchronous rounds: messages sent by correct processes arrive by the end of that round.
- Digital signatures: everyone can verify who signed a message, and nobody can forge another process’s signature.
- An honest majority: (n>2f), needed for the validity condition below.
- Byzantine faults: A faulty process can send anything to anyone or withhold anything anytime.
Recall that for consensus we want three properties:
- Agreement: all correct processes decide the same value.
- Validity: the decision must be a value someone proposed; if all correct processes propose (v), they decide (v).
- Termination: every correct process eventually decides.
A signature proves who signed something. It does not prove that they told the truth, or told everyone.
Why signing proposals is not enough
Suppose we run ordinary FloodSet, but sign every proposal.
A faulty process can keep its signed proposal secret until the final round, then send it to just one correct process. That process now has a value the others lack, with no time left to forward it.
Depending on the decision rule, they could decide differently.
Get Bhaskar Krishnamachari’s stories in your inbox
Join Medium for free to get updates from this writer.
The problem is late, selective delivery. A valid signature alone does not prevent it.
The fix: longer chains in later rounds
Whenever a process forwards a proposal, it signs the entire message, including the existing signatures. This creates an ordered chain: the originator signed the proposal, the next process signed that signed proposal, and so on.
The acceptance rule is simple:
A proposal received in round (r) is accepted only if its chain contains exactly (r) distinct signers.
The first signer must be the originator, and every signature must verify.
Thus, round 1 requires one signature; round 2 requires two; and the final round, (f+1), requires (f+1).
Here is the protocol, a signed version of FloodSet that is based on the Dolev-Strong authenticated broadcast:
1. Round 1: sign and send your proposal to everyone.
2. Round r: accept only chains with r valid, distinct
signatures, with the originator first.
3. Sign and forward each newly accepted proposal
next round, unless this is round f+1.
4. After round f+1: discard missing or conflicting
originators. Choose value supported by strict majority.
If none, choose a fixed default.
Why it works
The key claim is:
If one correct process accepts a proposal, every correct process accepts it by the end of round (f+1).
There are two cases.
It is accepted before the final round. The accepting process adds its signature and forwards it to everyone in the next round. The chain grows by one, exactly as the acceptance rule requires.
It is accepted in the final round. Its chain contains (f+1) distinct signatures. Since at most (f) processes are faulty, at least one signer is correct. That correct signer must have sent the corresponding chain to everyone in the appropriate earlier round — or in this final round itself. So everyone receives and accepts the proposal in time.
This blocks the late-message attack. Faulty processes alone can produce only (f) signatures. To obtain the extra signature, they must involve a correct process, which shares the proposal with everyone.
Consequently, all correct processes finish with the same accepted proposals and apply the same decision rule. That gives agreement. Stopping after (f+1) rounds gives termination.
For validity, the decision is always a proposed value: choose the strict-majority value if one exists, otherwise the smallest remaining proposal. The remaining set is nonempty because every correct originator contributes exactly one proposal. Moreover, if all correct processes propose (v), then (n>2f) ensures they form a strict majority, so everyone decides (v).
As messages accumulate signatures, they grow longer. BLS aggregate signatures can reduce this overhead, but we’ll leave that for another time.
Further reading
- Danny Dolev and H. Raymond Strong (1983), Authenticated Algorithms for Byzantine Agreement, SIAM Journal on Computing 12(4).
- Dolev–Strong Authenticated Broadcast, Decentralized Thoughts — a step-by-step explanation of signature chains and the timing rule.
AI Use Statement:
I used ChatGPT and Claude for this post; the post including the text and figures are based on my initial idea, inputs, verification, and interactive refinement for clarity and ease of understanding.
