When some machines may lie, replacing a leader has been slow and costly. Can a new leader take over as cheaply as any ordinary step, and at the pace of the messages rather than of a timer?
We find out by exploring how four bandits holding a hilltop took turns keeping their loot scroll, each gathering the others' seals into one bundle instead of every man writing to every other.
After Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta and Ittai Abraham, HotStuff: BFT Consensus with Linearity and Responsiveness, 2019
Each link is an idea one paper took from another. Point at one, or tap it, to read how.
a paper this book retells a paper retold in another book a paper outside the series
First, in machine terms
Replacing a leader that may lie
A group of computers keeps one log in the same order, led by one machine at a time, and some of them may lie.
When a leader stalls, the group must replace it, and in earlier protocols that is the costly part. Every machine tells every other machine, so the messages in one step grow with every pair of machines, and a change of leader costs far more than an ordinary step. HotStuff, which Yin, Malkhi, Reiter, Gueta and Abraham published in 2019, removes both costs with two ideas.
Votes go only to the leader, who combines them into one certificate and sends it back out, so the messages in a step grow only with the number of machines.
One more phase of voting lets a new leader take over as cheaply as an old one.
Together they let the leader change at every step, at the pace of the messages and not of a timer. We tell it with four bandits on a hilltop and their trained rats.
Messages in one step
Every machine to every machine
–
Votes to one leader, one certificate back
–
Pick a size for the group.
The crown of Mount Phyle
Four bandits, out of sight of one another
Bandit 1 sits inside the ring wall on the crown of Mount Phyle, and bandits 2, 3 and 4 hold posts on the slopes below it. The four keep one loot scroll, with a copy at each post, and send word to one another only by rat.*
Rats and sealsA rat arrives with exactly what was written on its strip. Every strip is sealed with the sender's ring, and nobody can forge a ring.
One may lieOne of the four may lie in what they send, and nobody ever learns which.
The windA wind can hold the rats in their holes for as long as it blows, so each post keeps a sandglass to wait by.
The arrangement so far
What a change of job cost
Each entry in the loot scroll is numbered by whoever has the job, echoed twice by the men, and written in the same order at every honest post. When the registrar stalls, the job passes.*
That arrangement keeps the scroll in one order whoever lies, and the four men pay for it in two ways.
First cost
Every man writes to every man
Each echo goes from each man to all the others. With four men that is a dozen rats a stage. With forty it would be over fifteen hundred.
Second cost
A change of job is heavy
The new registrar must gather requests from three men, each carrying sealed proof of every entry readied at their post, and send all of it on, so that each man can check the new numbering.* A change costs far more than an ordinary entry, and the more often the job passes, the more that matters.
The crown, the scroll, the seals, the wind and the four men all stay as they are. Only the procedure changes, and it aims at both costs. The job should be able to pass at every entry, whether or not anyone suspects its registrar, with a change of registrar costing no more than an entry.
The rats come first. A dozen of them run in every stage because every man writes to every man, and the four can do without that.
One stage, two ways
Votes to one man, bundles to all
Every man need not write to every man. Each man sends their sealed vote to the registrar alone, and the registrar tells the rest what the votes came to.
When the registrar has three matching votes, the registrar ties them into a bundle and sends the bundle to everyone. A bundle can be trusted because nobody can forge a seal. Three seals prove that three men voted, and so, with one liar among the four, that at least two honest men did.
The crown below runs one stage each way, with bandit 1 as registrar. Press each button in turn and watch the count of rats.
One stage on the crown count the rats
The crown from above. Bandit 1 has the job and sits inside the ring wall. Each rat takes the colour of the man who sent it.
0rats this stage
Run one stage each way and count the rats.
Twelve rats become six. Each man writes only to the registrar, and the registrar's bundle carries proof of all three votes, so a stage costs rats in step with the number of men and no longer with every pair of them. On the crown a bundle is three seals tied together.
The rats were the lighter of the two costs. The heavy one was the change of registrar, where a new registrar gathered everyone's sealed proofs before numbering anything. A new registrar needs a way to pick up where the last left off with far less in hand.
The new registrar asks for one thing
Three stages and a lock
A new registrar can pick up where the last left off if every man sends the new registrar their latest bundle, and nothing more. For one bundle to be enough, entries now form a chain: each entry names the one before it, so an entry stands only with everything behind it. Two entries conflict if neither lies on the other's chain.
An entry now goes through three stages of voting, and each stage ends in a bundle: a first, a second and a third. Each man keeps two bundles: the latest first bundle they have seen, and their lock, the latest second bundle they have voted on. A term is one registrar's turn at the job, and it goes in six steps. Scroll slowly, and the crown moves with you.
1 · Starting
Every man sends the registrar their latest first bundle
The registrar waits for three, takes the latest of them, and proposes a new entry on top of the entry it names, sending the proposal and that bundle to all.
2 · First vote
A man votes if the proposal is safe for them
A man votes for the proposal if it lies on the chain of the entry they are locked on, or if the bundle it carries is from a later term than their lock.
3 · Second vote
The first bundle
The registrar ties three first votes into a first bundle and sends it. Every man keeps it and votes again.
4 · Third vote
The second bundle, and the lock
The registrar ties three second votes into a second bundle and sends it. Every man locks on it and votes again.
5 · Standing
The third bundle
The registrar ties three third votes into a third bundle and sends it. Every man writes the entry and everything behind it into their copy.
6 · Moving on
A sandglass runs out
If a man's sandglass runs out before the term ends, they move to the next term and send its registrar their latest first bundle.
A term that goes well ends with the entry written at every post. A term that stalls leaves each man with whatever first bundle and lock they had reached, and the next registrar is owed only the first bundles. Whether the men then vote for the next registrar's proposal is decided by the rule for the first vote, and that rule has two halves.
Where the term is in the paper
The steps above are the paper's Basic HotStuff: a first, second and third vote are the prepare, pre-commit and commit votes, and a first, second and third bundle are prepareQC, precommitQC and commitQC.
The rule for the first vote has two halves because it has two jobs to do. A man votes for a proposal if either half holds.
First half
Lies on my locked entry's chain
Second half
Carries a later bundle than my lock
The first half keeps the scroll safe. A proposal on the locked entry's chain builds on that entry, so a locked man who votes for it helps nothing conflicting forward, and a locked man votes for nothing else on the strength of this half.
The second half keeps the scroll moving. A man may be locked on something the rest have gone past. A bundle from a later term than the lock shows that three men have voted for something since, and a man who is shown this lets the lock go.
The four proposals below put the rule to one man. Pick each in turn and watch which half, if either, lets the man vote.
One man's first vote lock: term 4
A proposal reaches a man whose lock is the second bundle of term 4. Which proposal is it?
Pick a proposal. The man votes if either half holds.
A lock, then, can be let go. The worry is that a man who lets go might help a conflicting entry to stand beside the one they had locked on.
The first promise
Never two entries
Letting a lock go can never let a conflicting entry stand. The reason comes in two parts, one for a single term and one for the terms that follow it.
Within a term, two bundles of the same stage cannot vouch for conflicting entries. Each needs three seals out of four, so the two threes share an honest man, and an honest man votes once a stage a term.* Across terms the lock does the work. An entry stands only on a third bundle, and a man casts a third vote only after locking, so an entry that stands has honest men locked on it. A later bundle for a conflicting entry needs three seals too, and so the vote of one of those locked men, who gives it only to a proposal that carries a bundle later than the lock.
Never Two Entries
However the wind blows and whoever lies, no two conflicting entries both stand at honest posts.
The part within a term can be checked by hand. Choose the missing seal of each bundle below, and see how many men sealed both.
Two bundles of the same stage who is in both?
Each bundle has three seals out of four. For each bundle, pick the man whose seal it lacks.
Bundle A lacks
Bundle B lacks
Pick one man for each bundle.
The scroll is safe with three stages, then. Two echoes were enough to keep it safe before, so the third stage has to earn its place some other way. The plain test is to take it away.
Proof — that the locks keep conflicting entries from both standing
Theorem 2. Conflicting nodes cannot both be committed by correct replicas. Here W and B are conflicting entries (nodes); a, b and s are terms (views); and r is an honest man (a correct replica). A third bundle is a commitQC, a first bundle a prepareQC.
Suppose W stands on a third bundle from term a, and a conflicting B on one from term
b. They are not the same term, so say a is earlier.
B's standing needed a first bundle for B, or for something on B's chain, in term b.
Among all first bundles from terms after a, up to b, for entries that
conflict with W, take the one from the earliest term, s.
W's third bundle in term a and that first bundle in term s each carry three
seals, so they share an honest man, r. A man casts a third vote only after locking, so
in term a, r locked on W's second bundle. Nothing between a and s can have moved that lock off W's chain,
since that would need a first bundle for a conflicting entry earlier than s.
So in term s, r was locked on W, and the proposal conflicted with W. It
carried a bundle from no later than term a, again because s is the earliest.
Neither half of the rule lets r vote for it. But r did vote, since r's seal is in the
term-s bundle. Contradiction.∎
What two stages would do
The hidden lock
Take the third stage away, and a lock can hide from the next registrar. With two stages a man locks as soon as they see a first bundle, and an entry stands on the bundle after it.
Suppose that in some term an entry reaches its first bundle, and only one man, say bandit 3, sees that bundle before the others' sandglasses run out. Bandit 3 locks on it. The next registrar need only wait for three men, and hears from three who do not include bandit 3. None of the three has that bundle, so the registrar proposes an entry that conflicts with bandit 3's lock.
The two other honest men vote for it. Bandit 3 refuses, because the proposal conflicts with bandit 3's lock and carries no later bundle. That makes two votes where three are needed. The sandglasses run out, and just then a liar adds a vote, so the registrar forms a first bundle that one man sees and locks on. The next term begins the same way, and nothing stops the terms from going on like this for ever.
The panel below sets up that moment. Choose whose answer comes last under two stages, then switch to three stages and choose again.
The new registrar listens two stages
The registrar waits for the first three answers. Pick the man whose answer is slowest, so that the registrar does not wait for it.
Pick the slowest man.
Two stages can be mended. Each new registrar waits out a full sandglass before proposing, which is long enough, once the wind drops, to be sure of hearing every man's latest bundle. The remedy works, and it ties every change of registrar to the length of a sandglass, however fast the rats run.
The third stage does the same work without the wait. With three stages a man locks only on a second bundle, and a second bundle exists only because three men voted on a first bundle and kept it. So a lock at any honest post means at least two honest men hold the matching first bundle. A new registrar who hears from any three men hears from at least one of those two, and learns the latest bundle without waiting out anything.
A lock that cannot hide is what the third stage buys. With it an honest registrar can go as fast as the rats bring answers, and that can be stated as a promise.
The second promise
Going at the rats' pace
The promise is about pace. Order holds in any wind, but an entry can stand only when the rats run, so the promise speaks of the time after the wind has dropped.
Going at the Rats' Pace
Once the wind has dropped, a term whose registrar is honest, with every honest man in it long enough, ends with an entry standing, and it needs to wait only for the first three answers at each stage, never for a full sandglass.
The promise asks for the honest men to be in the same term for long enough, and the sandglasses see to that. The registrars pass in a fixed order by term number, and each man doubles their sandglass whenever a term ends with nothing standing, as before.* In the end the sandglasses overlap for long enough under an honest registrar. The paper keeps this part, which it calls the pacemaker, apart from the rest, because it affects only whether entries stand and never which.
Pace seems to have a price. Each entry now waits three stages where two echoes did before, which looks as though the scroll must take in entries more slowly.
Proof — that an honest registrar after the wind drops gets their entry through
Lemma 3, Theorem 4 (optimistic responsiveness). After GST, in a view with a correct leader and every correct replica in it long enough, the leader obtains a highQC at least as high as every correct replica's lockedQC, every correct replica votes for its proposal, and each phase completes on the first n − f answers, so the proposal commits. A second bundle is a precommitQC, and a lock is lockedQC.
Take the latest lock held by any honest man: a second bundle. It exists because three men voted
on its first bundle, at least two of them honest, and each keeps it.
The registrar hears the latest first bundles of three men, which include at least one of those two.
So the registrar takes a bundle at least as late as every honest lock.
Every honest man then votes for the proposal. A man whose lock is from the same term as the
bundle the registrar took is locked on that very entry, since one term has only one second bundle, and
the proposal lies on its chain. Every other honest man's lock is earlier, and the proposal carries a
later bundle. In still air all votes and bundles arrive, and each stage completes on three answers.
So the entry stands.∎
The stages run on top of one another
A new registrar every entry
The scroll need not take in entries more slowly. Each entry still waits three stages, but the three stages all look alike: the registrar sends something, the men vote, the registrar bundles the votes. So they can be run on top of one another.
Each term the job passes to the next man, who proposes a new entry carrying the latest first bundle. A vote for it is also a second vote for the entry before it, and a third vote for the one before that. Each new proposal moves the entries before it one stage on, so one vote a term does the work of three stages, spread over three terms.
Run the terms below one at a time. The job starts at bandit 1 and goes round the four posts, and from the fourth term on an entry stands at every term.
Terms in a row no term yet
Each line is one man, and each ring further out is a later moment. The numbered dot is a term's proposal. The arc into it is the bundle it carries for the entry directly before.
The job starts at bandit 1. Press the button to run a term.
A man tells what stands by reading the chain behind each new proposal. If the proposal carries a bundle for its direct parent, the parent has its first bundle. If that parent carries one for its own direct parent, the grandparent is ready to lock on. If the grandparent carries one for its own direct parent too, that entry, the one behind all three, stands. Where a registrar failed and a term left nothing, the chain has a gap, and counting starts again.
The job now passes at every entry, suspected or not, and the passing costs nothing more, for the same reason a change of registrar is cheap: a new registrar only proposes on the latest bundle they hear of, like any other.
The crown now has a new registrar at every entry, going at the rats' pace. Some things the new procedure leaves exactly as they were, and some it gains only on conditions.
Five questions
What it does not say
What the new procedure leaves alone, and what it gains only on conditions, can be set down under five questions.
Does anything stand before the wind drops? Order holds in any wind, but no entry stands until the wind has dropped, and that is so for any arrangement.
Is the bundle always small? The bundle is small only with a threshold seal, where each man holds a piece and any three pieces combine into one seal that anyone can check. Then the bundle is the size of a single seal however many men there are, and each stage costs a number of seals that grows only in step with the number of men. The crown's rings are ordinary seals and make a bundle of three, so the saving here is in rats and leaves the size of what they carry as it was.
Is an entry slower? An entry takes one more stage than before to stand. Chained, the stages overlap, so a new entry still stands at every term.
Does anyone learn who lies? Nobody learns who lies, and a liar may still file nonsense that stands in order.
What follows from any entry? Nothing follows from it.
Back to machines
The crown was a group of machines
Read the crown again with machines at the posts. Every bandit is a replica and every rat a message, a term is a view and its registrar the leader, and a bundle of three votes is a quorum certificate. Hover over a row, or tap it, to see who is who.
On the crown
In the machine room
A leader costs only linear traffic per decision, and a new leader can take over as cheaply as an old one.
HotStuff gets there by having replicas send votes only to the leader, who aggregates them into a quorum certificate, and by chaining three phases of such certificates so that leader replacement is just another round. Once the network behaves, it runs as fast as the network allows.
Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta and Ittai Abraham, HotStuff: BFT Consensus with Linearity and Responsiveness. Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), 2019. — Basic and Chained HotStuff, the safety and liveness arguments, the two-phase liveness failure, and the comparison with PBFT, Tendermint and Casper.
The ideas. HotStuff is a Byzantine state machine replication protocol for n = 3f + 1 replicas under partial synchrony, like PBFT, with two properties together: a new leader costs no more than an ordinary step (linear view change), and after the network stabilizes a correct leader proceeds at the speed of actual messages rather than a timeout (optimistic responsiveness).
Votes go only to the leader, who combines n − f of them into a quorum certificate, one threshold signature, so each phase is linear. There are three phases where PBFT had two. Replicas lock on the second certificate, and vote for a proposal if it extends their lock or carries a certificate from a later view. Because a lock implies that f + 1 correct replicas hold the matching first certificate, a new leader hearing from any n − f replicas learns it without waiting; with two phases a lock can hide, and progress needs a wait for the maximum delay.
Because the phases are identical, they pipeline: every view proposes a new block, the leader rotates every view, and a block commits when three consecutive views extend it.
