Doomslug: block conﬁrmation with single round
of communication, and a ﬁnality gadget with
guaranteed liveness
Alex Skidanov
Near Protocol
7/AlexSkidanov
alex@nearprotocol.com
December 31, 2019, last update January 31, 2020
Abstract
In this paper we present Doomslug1 – a construction that allows a set
of block producers in a blockchain protocol to create blocks with a single
round of communication per block such that each block is irreversible
unless at least one block producer gets their stake slashed. We also present
nightshade ﬁnality gadget that requires more rounds of communication,
but provides stronger and more common safety guarantee that a block is
irreversible unless one third of the total stake is slashed. We also show
that under partially synchronous network both Doomslug and Nightshade
Finality Gadget have liveness.
1
Introduction
The are two dominant approaches to producing blocks in Proof-of-Stake systems:
running a BFT consensus such as Tendermint [1] on each block, or having block
producers produce blocks on some schedule, like for example in Ouroboros [2].
The former has a minor disadvantage that it requires at least two rounds
of communication between the block producers, but also a bigger disadvantage
that the protocol stalls if more than one third of all the block producers simul-
taneously go oﬄine.
The latter has a disadvantage that a block cannot be considered ﬁnal until at
least several other blocks are built on top of it. Also, depending on implemen-
tation, such block producer schedules often either rely on having synchronized
wall clocks, or allows block producers2 to grieve neighboring block proposers.
1Doomslug is a character in science ﬁction novel Skyward by Brandon Sanderson. Brandon
Sanderson allows using character names with attribution.
2Throughout this paper we call the set of all the participants producing blocks block
producers. We call a participant that proposes block at particular height a block proposer
1
In practice we would prefer to have a reasonable ﬁnality guarantee after just
one round of communication, and maintain liveness even if close to one half of
the block producers are oﬄine.
In this paper we present a particular construction that consists of a fast
block producing gadget called Doomslug, and a slower ﬁnality gadget called
Nightshade Finality Gadget.
Assuming there are n = 2t + 1 block producers, Doomslug has the following
properties:
1. Safety. A produced block cannot be reverted unless at least one block
producer has their stake slashed.
2. Liveness.
Under partially synchronous network assumption from any
reachable state of the system for as long as at least t + 1 honest block
producers are online, a block will be produced in ﬁnite time.
3. Performance. Under synchronous network assumption, a honest block
proposer will produce a block with just one round of communication.
Assuming there are n = 3f +1 block producers, Nightshade Finality Gadget
has the following properties:
1. Safety. A ﬁnalized block cannot be reverted unless at least one third of
the total stake of all the block producers is slashed. Or, in other words,
unless f block producers are slashed.
2. Liveness.
Under partially synchronous network assumption from any
reachable state of the system for as long as at least 2f + 1 honest block
producers are online, a block will be ﬁnalized in ﬁnite time.
3. Performance. Under synchronous network assumption, two consecutive
honest block proposers will ﬁnalize a block within two rounds of commu-
nication.
2
Block Production Gadget
2.1
Overview
In this section we provide an overview of block production gadget. In the section
2.2 we provide a more formal deﬁnition.
Throughout this section we assume that there’s a total of n = 2t + 1 block
producers, of which t + 1 are honest, online and follow the protocol, while the
remaining t can be oﬄine or arbitrarily deviate from the protocol.
In Doomslug each block has a height, and each height h has a particular block
producer who is assigned to produce a block at h, whom we call throughout the
paper the block proposer for h. We denote the block proposer for h as BP(h).
Whenever a block B is produced at height h, it is broadcast by BP(h) to
all other block producers. Once a particular block producer p receives B, they
2
Figure 1:
An example timeline of doomslug block production
create an endorsement message E(B, p), unless they previously promised to skip
endorsing height h. The block proposer for height h + 1 cannot produce their
block unless they have messages E(B, p) (or messages indicating some block
producers suggest to skip B, see below) from at least t + 1 block producers.
They must include such messages into the produced block.
The set of such
messages is called witness.
Given some function T(x) each block producer that didn’t receive the block
for height h+1 after time T(1) sends another message S(h+1, 1, p) to BP(h+2)
which indicates that p suggests to skip 1 block starting at height h + 1, and
promises not to endorse any block at height h+1. The block proposer BP(h+2)
for height h+2 can produce their block if they collect t+1 messages S(h+1, 1, p).
If some block B′ is produced at height h + 1 after some block producers started
sending S(h + 1, 1, p), the block producers that sent S(h + 1, 1, p) cannot send
E(B′, p), that would constitute a slashable behavior. Other block producers can
and shall send E(B′, p) to the block proposer for h + 2. In such case the block
proposer for h + 2 must include any combination of S(h + 1, 1, p) and E(B′, p)
from t + 1 block producers in the witness of the block they produce.
Similarly, if the block B′′ produced by the proposer for h + 2 is missed by
some block producers, they would send either
1. S(h + 1, 2, p) if they also missed B′ and time T(1) + T(2) passed since
they received B, indicating that they suggest to skip two blocks starting
at h + 1, or
2. S(h + 2, 1, p) if time T(1) passed since they received B′, indicating that
they suggest to skip one block starting at h + 2.
The block proposer at height h+3 must collect any combination of S(h+1, 2, p),
S(h + 2, 1, p) and E(B′′, p) from t + 1 block producers and include them in the
block they produce.
3
If some block Bh+1 includes t + 1 messages E(Bh, p) for its previous block
Bh, then Bh is ﬁnal in a sense that reverting it would require at least one block
producer committing a slashable behavior.
2.2
Formal Deﬁnition
In this section we provide a more formal deﬁnition of the block production
gadget.
For the purposes of B we deﬁne the following attributes:
prev(B) – previous block of B;
height(B) – the height of B;
witness(B) – witness for B;
There are three kinds of messages that block producers send to each other
over the network:
Block(B) –
announcement of B;
E(B, p) –
an endorsement of B by p;
S(h, n, p) –
a skip-message suggesting to skip n blocks starting
at height h by p;
Each Block(B) message must be signed by the corresponding block proposer
BP(height(B)). Each E(B, p) and S(h, n, p) message must be signed by p.
The witness(B) on the block is a set of endorsement and skip messages from
at least t + 1 block producers.
In a valid block message Block(B) each message m in witness(B) must
satisfy the following conditions:
1. If m is an endorsement message E(B′, p), then
B′ = prev(B) ∧height(B′) + 1 = height(B)
2. If m is a skip-message S(h, n, p), then
h ≤height(prev(B)) + 1 ∧h + n = height(B)
.
We also deﬁne the following slashing conditions:
1. If ∃(B, B′) : B ̸= B′ ∧height(B) = height(B′), then BP(height(B)) is
slashed.
2. If ∃(B, h, n, p) : E(B, p) ∧S(h, n, p) ∧h ≤height(B) < h + n, then p is
slashed.
4
The ﬁrst condition ensures that the same block producer doesn’t propose
two blocks for the same height, and the second condition ensures that a block
producer that suggested to skip a certain height didn’t also produce an endorse-
ment for a block at that height.
2.3
Algorithm
Algorithm 1 Doomslug subroutines
1: initialization
2:
witnesses = MultiMap < height →message >
3:
▷largest height for which a block with t + 1 endorsements was seen
4:
hfinal = −1
5:
▷largest height which p endorsed or promised to skip
6:
hmax = −1
7:
▷the tip of the chain
8:
Btip = genesis
9:
10: procedure processTimer(h)
11:
if hmax < h then
12:
hmax ←h
13:
send S(height(Btip) + 1, h −height(Btip), p) to BP(h + 1)
14:
startTimer(h + 1)
15:
16: procedure startTimer(h)
17:
interrupt skip timer
18:
skip timer = schedule processTimer(h) after T(h −hfinal)
19:
20: function validWitnessMessage(m, Bprev)
21:
m is S(h, n, p′) such that h ≤height(Bprev), or m is E(B, p′) such that
B = Bprev
22:
23: procedure checkBlockProduction(h, delay)
24:
witness ←{m ∈get(witnesses, h)|validWitnessMessage(m, Btip)}
25:
if BP(h) = p ∧h > height(Btip) ∧length(witness) ≥t + 1 then
26:
if delay∧not witness contains t + 1 endorsements then
27:
schedule checkBlockProduction(h, false) after T(h −hfinal)/2
28:
else
29:
Btip = newBlock(prev = Btip, height = h, witness)
30:
broadcast Block(Btip)
The algorithm of Doomslug is described in listings 1 and 2. In the algorithm
each subroutine and message handler is considered to be handled atomically.
The block producers exchange blocks, endorsements and skip messages.
Upon receiving a block, if the block has height higher than the highest known
5
Algorithm 2 Doomslug message handlers
1: upon E(B, p′) do
2:
insert(witnesses, height(B) + 1, E(B, p′))
3:
checkBlockProduction(height(B) + 1, true)
4:
5: upon S(h, n, p′) do
6:
insert(witnesses, h + n, S(h, n, p′))
7:
checkBlockProduction(h + n, true)
8:
9: upon Block(B) do
10:
broadcast Block(B)
11:
if height(B) > height(Btip) then
12:
Btip = B
13:
startTimer(height(Btip) + 1)
14:
if hmax < height(B) then
15:
hmax = height(B)
16:
send E(B, p) to BP(height(B) + 1)
17:
if witness(B) contains t+1 endorsements and height(B) > hfinal then
18:
hfinal = height(B)
19:
startTimer(height(Btip) + 1)
20:
checkBlockProduction(height(B) + 1, true)
21:
tip, the block producer updates the tip. They also immediately send an en-
dorsement if they haven’t promised to skip the height previously.
Block producers produce a block whenever they have endorsements or skip
messages from t + 1 block producers. It is necessary for liveness that a block
producer would wait for half of T(h−hfinal) before producing a block at height
h unless they have t + 1 endorsements. The block production is handled in
the checkBlockProduction subroutine. Note that while the block producer
waits, enough endorsements might accumulate, which would trigger another
invocation of checkBlockProduction and produce the block before the timer
in the original invocation runs out.
We omit from the listings the maintenance of seen message, and assume that
each block producer handles each unique message exactly once, even if they have
received it multiple times. This in particular means that if a block producer p1
received a block message from p2 and re-broadcasted it, p2 will not process the
block message again upon receiving it.
By deﬁnition of the endorsement message it must endorse the block with
height immediately preceding the height of the block including it in its witness.
Therefore for the block producer for height h to include endorsements on tip
Bt, it must be that h = height(Bt) + 1. Otherwise the block proposer for h can
only include skip-messages in its witness.
6
2.4
Analysis
2.4.1
Safety
In this section we provide a formal proof of block production gadget safety.
Theorem 1 (Block Production Gadget Safety). If a block B with prev(B) = B1
has endorsements on B1 from t + 1 block producers, then B1 is irreversible
(meaning that no block B2 with equal or higher height can be produced such that
neither B1 nor B2 are in the ancestry of each other) unless at least one block
producer is slashed.
Proof. Say it is not the case, and another valid block B2 is produced such that
neither B1 nor B2 are in the ancestry of each other. Recall that height(B2) ≥
height(B1). Consider a block B′
2 in the ancestry of B2 such that height(B′
2) ≥
height(B1) and height(prev(B′
2)) < height(B1). Consider two cases, as shown
on ﬁgure 2:
Figure 2:
Reverting a block that has doomslug ﬁnality
1. height(B′
2) = height(B1). Then BP(height(B1)) is slashed for proposing
two blocks at the same height.
2. height(B′
2) > height(B1).
Since height(prev(B′
2)) < height(B1), the
witness(B′
2) cannot contain any endorsement messages (since by deﬁni-
tion an endorsement can only endorse a block if it’s height immediately
precedes the height of the block containing the endorsement). Thus, the
witness(B′
2) contains at least t + 1 skip-messages. There are also at least
t + 1 endorsement messages on B1 in the witness(B). Naturally, there’s
at least one block producer p that signed both of such messages. Consider
their skip message S(h, n, p) in the witness(B′
2) and their endorsement
message E(B1, p) in the witness(B). A skip-message included in B′
2 by
deﬁnition has the property that
h ≤height(prev(B′
2)) + 1 ∧h + n = height(B′
2)
7
.
Since height(prev(B′
2)) < height(B1), and height(B′
2) > height(B1), it
follows that
h ≤height(B1) ∧h + n > height(B1)
which is exactly the slashing condition for endorsing a block at a height
that was previously suggested to be skipped, and thus p is slashed.
In either case at least one block producer is slashed, which proves the theo-
rem.
2.4.2
Liveness
For liveness proof we will assume a partially synchronous network. In other
words, we assume that there’s a moment in time (unknown to us) called global
stabilization time, or GST for short, such that there exists some value ∆(un-
known to us) such that any message between any two honest block producers
sent after GST will be delivered in time not exceeding ∆.
We also assume
that all the messages sent before GST will be delivered to their corresponding
recipients within ∆after GST. We choose such T(x) that:
∀q :∃x : T(x) ≥q∧
∀x|x ≥2 :T(x) ≥T(x −1)
We say a block B has doomslug ﬁnality if at least one honest block producer
saw another block B′ such that the witness(B′) has at least t+ 1 endorsements
on B. Note that according to theorem 1 a block that has doomslug ﬁnality is
irreversible unless at least one block producer is slashed.
Lemma 1. For any height h, at least one block at height h′ > h will be produced
after GST.
Proof. Say it is not the case, and there’s some height h such that no block
at height higher than h will be produced after GST. Let hmax be the largest
height for which a block is ever produced, let such block be Bmax. Consider the
smallest height hnext > max(h, hmax +1) for which no block producer produced
an endorsement, and which no block producer promised to skip, before they
received and processed Bmax, and such that BP(hnext) is online and honest.
As each block producer p receives Bmax, they start a timer, which at some
point reaches height hnext for the ﬁrst time. Let’s show that p will send a skip
message to BP(hnext) once the timer reaches height hnext. Indeed, they would
only not send a skip message if they previously promised to skip or endorsed
a height equal to or greater than hnext.
They didn’t endorse or skip such
height before receiving Bmax by deﬁnition of hnext.
They didn’t skip hnext
after receiving Bmax because this is the ﬁrst time the timer reaches hnext since
receiving and processing Bmax. They couldn’t endorse a block at height higher
or equal to hnext because by assumption no such block was ever produced.
8
Therefore each block producer p will eventually send a skip message to
BP(hnext). Once t + 1 block producers sent such skip messages to BP(hnext),
BP(hnext) can and will produce a block at hnext.
Lemma 2. Let Be be the block with largest height he that has doomslug ﬁnality
at some point in time.
Consider some height h for which an honest block producer p sent a skip
message. For any height h′ < h it must be that either p sent an endorsement
message on some block at h′, or sent a skip message that promises to skip h′,
or observed a block with a height hb, h′ < hb < h.
If a message to endorse or skip h′ was indeed sent, unless block with higher
height than he has doomslug ﬁnality at some point, the time that passed between
sending an endorsement or a skip on h′ and sending a skip for h is at least
T(h −he)
Proof. The ﬁrst part of the lemma can be proven by induction. The base of the
induction is the case when h−h′ = 1. The only way to send a skip message on h is
to call processTimer(h), which can be only be scheduled from startTimer(h),
which in turn is only called when an endorsement or a skip message is being
sent on h −1. For a message not to be sent, it must be that hmax ≥h −1. But
hmax < h, otherwise the skip message on h would not have been sent. Thus for
a skip message or an endorsement message on h −1 not to be sent when we call
to startTimer(h), it must be that hmax = h −1, but the only way for hmax to
assume such a value is for an endorsement message or a skip message on h −1
to be sent earlier.
For a case when h −h′ > 1 by the same reasoning as above either a skip
message or an endorsement message was sent for h−1. If it was a skip message,
by induction the lemma holds. If it was an endorsement message, then a block
is known at height h −1, and h′ < h −1 < h, thus lemma also holds.
In both cases above the skip message or the endorsement message could not
have been sent after the startTimer(h) was called, because whenever we send
a skip or an endorsement message, we always restart the timer. Thus, the skip
or the endorsement message on h′ must have been sent before the timer for h
was started, which was at least T(h −he) before the call to processTimer(h),
which in turn was T(h −he) before the skip message for h was sent by p.
Lemma 3. Let Be be the block with largest height he that has doomslug ﬁnality
at some point in time.
Unless another block with higher height has doomslug ﬁnality at some point, if
an honest block producer p sent a skip message for height h such that T(h−he) >
8∆at time t0, no later than t0 −7∆all honest block producers have either sent
a skip message promising to skip h −1, or an endorsement on some block at
height h −1.
Proof. Consider height(Btip) and hfinal from perspective of p.
p updated
both Btip and hfinal more than ∆before t0, since updating either would have
restarted the timer, and p hasn’t restarted their timer for at least 8∆before t0.
9
It’s easy to show that all the honest block producers have the same height(Btip)
and hfinal. They can’t have smaller values, because within ∆from p learning
the higher value they would have learnt it as well, and vise versa.
Consider the block producer pmin for whom the later of the moments when
they updated Btip or hfinal last time was the earliest among all the block
producers, call that moment tmin, and the block producer pmax for whom such
a moment was the latest, call it tmax. It’s easy to show that tmax −tmin < ∆.
Thus, for all the block producers the last call to startTimer(height(Btip)+1)
was within ∆from each other. Since no honest block producer restarted their
timers since then, their last calls to all heights higher than height(Btip + 1 also
happened within ∆from each other.
If p called processTimer(h) at t0, they must have called startTimer(h)
exactly t0 −T(h −he) ≤t0 −8∆. All other honest block producers must have
called startTimer(h) within ∆, which is no later t0 −7∆. As they called to
startTimer(h), they either sent a skip message on h −1, or an endorsement
message on some block at height h−1, or already had hmax equal to or exceeding
h −1.
If for some honest block producer p′ hmax was equal to h −1, then at some
point preceding t0 −7∆they sent a skip message promising to skip h −1 or an
endorsement message on a block at height h −1.
If hmax was greater than h−1, before t0−7∆p′ sent a skip message on some
height exceeding h −1, because height(Btip) < h. But then according to 2 they
sent a skip message or an endorsement message on h −1 before that moment.
This exhaustively covers all possible cases.
Lemma 4. Let Be be the block with largest height he that has doomslug ﬁnality
at some point in time.
Unless another block with higher height has doomslug ﬁnality at some point,
there’s exists a height h′ such that for any height h > h′ with T(h −he) > 8∆,
a block will be produced as long as the BP(h) is online and honest.
Proof. According to lemma 1, at least one block will be produced after GST.
Let h′ be the height of any such block, that was produced after GST.
Say the lemma is incorrect, and there’s a height h > h′, such that T(h−he) >
8∆and BP(h) is online and honest, such that no block is produced for height h.
According to lemma 1, there will be a block produced for a height higher than h.
Let the height of the ﬁrst such block produced be h1, and the block itself be B1.
height(B1) −height(prev(B1)) must be at least two, because height(B1) > h
and height(prev(B1)) < h (since no block at height h exists by assumption, and
h1 is the ﬁrst block at the height higher than h for which a block is produced).
Therefore witness(B1) cannot contain any endorsement messages in it, and thus
contains at least t+1 skip messages. At least one such message is from an honest
block producer, because there’s less than t + 1 malicious block producers.
According to lemma 2, since no block between heights h −1 and h′ exists at
the time h′ is produced, p sent the skip message for height h or an endorsement
on some block at height h at least T(h1 −he) ≥T(h −he) before they sent a
10
skip message to BP(h′). Let’s call the moment such a skip message was sent
t0. Note that no block at heights higher than or equal to h was produced until
t0, because no block at height h is never produced by assumption, and the ﬁrst
block to be produced at a height higher than h is h′ which is produced after t0.
According to lemma 3, since T(h −he) ≥8∆, no later than t0 −7∆all the
honest block producers sent a promise to skip height h −1 or an endorsement
message on some block at height h −1. Therefore no later than t0 −6∆BP(h)
collected t+1 such messages, and produced a block at height h, and no later than
t0 −5∆all honest block producers saw such a block, causing a contradiction.
Theorem 2 (Block Production Gadget Liveness). For any height h, at least
one block at height h′ > h will be produced after GST that has doomslug ﬁnality.
Proof. Let Be be the block with largest height he that has doomslug ﬁnality
at some point in time. Say the theorem is incorrect, and it is possible that no
block at height height that he will ever have doomslug ﬁnality.
According to lemma 4, there’s a height h′ such that for any height h > h′,
T(h −he) > 8∆with an honest block producer BP(h) a block for height h will
be produced. Consider one such height h that both the block producer for h
and for h −1 are honest, and T(h −1 −he) > 8∆. Given that there are more
than half honest block producers, such height always exists.
Consider the ﬁrst moment in time when BP(h) has skip messages or en-
dorsements on its current head from at least t + 1 block producers. Since the
number of malicious actors is at most t, at least one such endorsement or a skip
message came from an honest block producer, say such a block producer is p.
When BP(h) ultimately produces the block, it doesn’t have t+1 endorsements,
by assumption that no block with doomslug ﬁnality is published with a height
higher than he. Therefore BP(h) will wait for at least T(h −he)/2 > 4∆be-
tween the moment t0 they ﬁrst received an endorsement or a skip message for
height h from an honest actor until the moment t1 BP(h) actually produced
the block.
First consider the case that the ﬁrst message from p for height h received by
BP(h) was a skip-message promising to skip height h −1. According to lemma
3, since T(h−1−he) ≥8∆, no later than t0 −7∆all the honest block producers
sent a promise to skip height h−2 or an endorsement message on some block at
height h −2 to BP(h −1). Therefore no later than t0 −6∆BP(h −1) collected
t + 1 such messages, and produced a block at height h −1, and no later than
t0 −5∆all honest block producers saw such a block, including p. But then p
either immediately endorsed it, or already had hmax ≥h −1, in both cases it
would not send the skip message for h −1 at t0, causing a contradiction.
Thus, it must be that any message sent to BP(h) by any honest block
producer was an endorsement. Note that those block producers that did send
the endorsements did it within ∆from each other. Indeed, block producers only
send endorsements after receiving a block, and the time since the ﬁrst honest
block producer receiving a block until the last honest block producer receiving
the same block never exceeds ∆.
11
Since BP(h) waits at least 4∆since receiving the ﬁrst endorsement until
producing the block, and all the honest block producers send their endorsements
within ∆from each other, BP(h) will include all the endorsements sent by
honest block producers in its witness.
It is now suﬃcient to show that no honest block producer skipped sending
their endorsement. For a honest block producer to skip sending an endorsement
they needed to either send an endorsement for a block at a higher height, or
promise to skip the same or higher height. Consider two cases:
1. There was at least one block with height h′, h′ > h that existed before
the block at height h was produced. Consider the lowest such h′. The
witness of the block at height h′ doesn’t contain any endorsements, because
h′ > h and prev(h′) < h. Thus it contains skip messages from t + 1 block
producers, at least one of which is from an honest block producer. Since
at least one honest block producer sent a skip message for height h′ −1,
all the block producers, including p, sent a skip messages or endorsements
on h′ −2 ≥h′ −1 according to lemma 3.
2. No block with height higher than h was produced before the block at
height h was produced. In this case for p to skip endorsing the block at
h −1 they must have previously sent a skip message on height h −1 or
higher.
In both cases p has sent a skip message on some height hs, hs ≥h −1 such
that no block is known to them with heights between h−1 and hs. According to
lemma 2 p has sent a skip message or an endorsement message on height h −1.
But we already showed that they couldn’t have sent the skip message on h −1,
and therefore it must be that they sent an endorsement message on h −1.
Thus all the honest block producers sent an endorsement message to BP(h)
on the block produced for height h−1. As we showed above BP(h) would include
all such endorsement messages, and therefore the block at height h contains at
least t + 1 endorsements on the block at height h −1.
3
Finality Gadget3
In this section we describe a Casper-like ﬁnality gadget, that we call Nightshade
Finality Gadget, or Casper NFG.
Throughout this section we assume that there’s a total of n = 3f + 1 block
producers, of which 2f + 1 are honest, online and follow the protocol, while the
remaining f can be oﬄine or arbitrarily deviate from the protocol.
3Nightshade ﬁnality gadget was previously presented in [3]. The construction here replaces
the deﬁnition of weight, provides guaranteed liveness and diﬀers in other minor details.
12
3.1
Approvals
Approvals in our construction have the same purpose as votes in Casper FFG
[4]. An approval by a block producer v4 is an ordered tuple
⟨v, p, r⟩
where p is the block that is being approved, r is a so-called reference block. The
reference block must be in the ancestry of p.
We deﬁne a score s(b) and a weight w(b) of a block in section 3.4. For any
two approvals any particular block producer issues
⟨v, p1, r1⟩
and
⟨v, p2, r2⟩
it must be that
1. r1 ̸= r2 ∧s(r1) ≥s(p2) ∧w(r1) > w(p2), or
2. r1 ̸= r2 ∧s(r2) ≥s(p1) ∧w(r2) > w(p1), or
3. r1 = r2 ∧(p1 ∈A(p2) ∨p2 ∈A(p1))
where A(b) denotes all the blocks in the ancestry of b.
In other words, if two approvals have the same reference block, the blocks
they approve must be on the same chain, and if they have diﬀerent reference
blocks, the ranges of scores and weights of (r, p) must not have any points
in common, and moreover the approval that has higher scores must also have
higher weights. Creating two approvals that violate these rules is a slashable
behavior.
3.2
Algorithm
We alter the algorithm presented in section 2.3 in the following way:
When a block producer v receives a block b′ witness of which has t + 1
endorsements on some other block b (thus, b has doomslug ﬁnality from per-
spective of v), if height(b) is the largest height for which v knows a block to
have doomslug ﬁnality and if b is on the canonical chain according to the fork
choice rule (see section 3.4 below), v will produce an approval for b. v will then
repeatedly send such approval with any endorsement or skip-messages they sent
to block proposers until the approval is included in some block and that block
is ﬁnalized.
When producing an approval on b, if the last block v approved is in the
ancestry of b, v should use the same reference block as in the last approval.
4While inconsistent with previous sections, we will use v to refer to block producers when
describing the ﬁnality gadget, and use p to refer to the parent blocks of the approvals
13
Otherwise the reference block must be the lowest score block in the ancestry of
b that has higher weight and at no smaller score than the last block v approved.
If no such block exists in the ancestry of b, v should skip producing an approval.
Such approvals by construction cannot trigger the two slashable conditions listed
above. See ﬁgure 3.
Figure 3:
Approvals for a block that extends the last known canonical chain
and a block that causes a reorg
3.3
Finality
For an approval a = ⟨v, p, r⟩and a block b we call a a pre-vote on b iﬀ
1. b is in the ancestry of p;
2. r is in the ancestry of b.
We say a block bp has a quorum pre-vote for block b, if b is in the ancestry
of bp and there are 2f + 1 block producers for whom there’s an approval
a = ⟨v, p, r⟩
included in a block in the ancestry of bp such that p is in the ancestry of bp and
a is a pre-vote on b.
For an approval a = ⟨v, p, r⟩and a block b we call a a pre-commit on b iﬀ
1. b is in the ancestry of p;
2. r is in the ancestry of b;
3. There’s a block bp in the ancestry of p that has a quorum pre-vote on b.
14
We say a block bp has a quorum pre-commit for block b, if b is in the ancestry
of bp and there are 2f + 1 of block producers for whom there’s an approval
a = ⟨v, p, r⟩
included in a block in the ancestry of bp such that p is in the ancestry of bp and
a is a pre-commit on b.
As will be shown in section 3.5.1, no two blocks, assuming neither is in the
ancestry of the other, can have a quorum pre-commit by the same set of block
producers, unless at least f of the block producers are slashed. Thus, a block
that has a quorum pre-commit in practice can be considered ﬁnal.
3.4
Fork Choice Rule
Here we deﬁne how a canonical chain should be chosen if multiple competing
chains exist.
We ﬁrst deﬁne concepts of the weight and score of a block, and then deﬁne
the fork choice rule.
We deﬁne block weight of a block B (denoted as w(B)) to be some function
such that w(B) > w(prev(B)). For example, the weight can be just the height
of the block.
Let HQV (b) be the heaviest (in terms of weight) block for which a quorum
pre-vote exists in the ancestry of B.
The score of a block (denoted as s(B)) is then:
s(B) = w(HQV (B))
To choose a canonical chain among a set of chains, one ﬁrst computes the
score of the tip of each chain, and then chooses the chain with the higher score
of the tip.
If the scores are equal for the tips of two chains, the chain which has a tip
with higher height is chosen. This is necessary to make the doomslug safety
guarantee in section 2.4.1 meaningful (which states that a block is irreversible
if no block with the same or higher height can be created).
3.5
Analysis
3.5.1
Safety
In this section we prove that two blocks such that neither is in the ancestry of
the other cannot both be ﬁnalized (as in, have a quorum pre-commit) by the
same block producers set.
For a chain with a tip t and a block b that is ﬁnalized in such a chain, we
deﬁne as QV (t, b) the lowest score block in the ancestry of t that has a quorum
pre-vote on b.
Lemma 5. If a block b1 is ﬁnalized in a chain with a tip t1, no block b2 such
that w(b2) > w(b1) can have a quorum pre-vote by the same block producers
15
set in a chain with some tip t2 if neither b1 nor b2 are in the ancestry of one
another, unless at least f block producers committed a slashable act.
Figure 4:
If a block b1 is ﬁnalized on one chain, no heavier block can get a
quorum pre-vote on any other chain
Proof. Say it is not the case, and there’s such block b2. Consider such block b2
with the lowest height.
By deﬁnition of block ﬁnality, there’s 2f + 1 block producers that have an
approval of a form ⟨v, p1, r1⟩such that QV (t1, b1) is in the ancestry of p1. Note
that since QV (t1, b1) has a quorum pre-vote on b1, the score of p1 is at least
w(b1).
Since b2 has a quorum pre-vote in the chain originating at t2, there are 2f +1
block producers that have an approval of a form ⟨v, p2, r2⟩such that b2 is in the
ancestry of p2 and r2 is in the ancestry of b2. At least f block producers have
approvals of both forms.
Consider such block producer. Recall that w(b1) ≤w(b2). Since b2 is in the
ancestry of p2, and r1 is in the ancestry of b1, it follows that w(r1) ≤w(b1) ≤
w(b2) ≤w(p2). Since p2 and p1 are on two diﬀerent chains, unless the block pro-
ducer committed a slashable act, the ranges (w(r1), w(p1)) and (w(r2), w(p2))
do not intersect, and since w(r1) ≤w(p2), it must be that w(p1) < w(r2).
Recall that for two approvals such that w(p1) < w(r2) it is also required that
s(p1) ≤s(r2), as shown on ﬁgure 4.
Since the score of p1 is at least w(b1), the score of r2 is at least w(b1). But
that implies that there is a block b′
2 with weight greater or equal to w(b1) that
has a quorum pre-vote in the ancestry of b2.
Thus, for a block b2 with a weight higher than w(b1) that is not on the same
chain as b1 to exist, another such block b′
2 must exist in its ancestry, which
contradicts the assumption that b2 is the earliest such block.
16
Theorem 3 (Finality Gadget Safety). If a block b1 is ﬁnalized in a chain with
a tip t1, any participant that has seen t1 will have b1 in their canonical chain,
unless at least f block producers committed a slashable act.
Proof. Say it is not the case, and another chain is chosen as canonical. Since the
chain originating at t1 has a quorum pre-vote for b1, its score is at least w(b1).
Thus, the canonical chain that does not include b1 must have a score of at least
w(b1), otherwise it will not be chosen by the fork choice rule. By deﬁnition
of score, that implies that there is a block other than b1 with weight equal or
greater than w(b1) that has a quorum pre-vote. This contradicts lemma 5.
3.5.2
Liveness
To show that Nightshade Finality Gadget has liveness under partially syn-
chronous network, we ﬁrst consider the case when no block producer commits
a slashable act that causes two blocks b1 and b2 have doomslug ﬁnality, while
neither b1 nor b2 are in the ancestry of one another.
Lemma 6. For as long as no block producer commits a slashable act that causes
two blocks b1 and b2 to have doomslug ﬁnality, while neither b1 nor b2 is in
the ancestry of one another, any block b on the canonical chain with doomslug
ﬁnality will be ﬁnalized by the Nightshade Finality Gadget in ﬁnite time.
Proof. Note that for as long as no two blocks b1 and b2 are produced such that
they both have doomslug ﬁnality and are not in the ancestry of one another,
according to algorithm described in section 3.2, the reference block of all the
approvals for a particular block producer v will be the same.
Consider some point in time t at which b is known by all honest block
producers and is on the canonical chain.
Consider the largest score smax and the largest weight wmax for which at
least one block producer created an approval with such a score or weight in
its parent block. Note that smax cannot be larger than the score of the tip of
the canonical chain, since the canonical chain by deﬁnition has the tip with the
largest score. Thus any block built on the canonical chain will have score at
least smax.
According to theorem 2, within ﬁnite amount of time since t a new block
that has doomslug ﬁnality will be produced. And then in ﬁnite time since then
yet another block with doomslug ﬁnality will be produced. Since the weight is
increasing, eventually a block with weight w > wmax will have doomslug ﬁnality.
All the honest block producers will be able to create an approval on it.
When b1 is broadcasted, all honest block producers will create an approval
such that
1. its reference block is b1 or is in the ancestry of b1.
2. its parent block is b1 or has b1 in its ancestry.
17
The above follows from the deﬁnition of the approval.
Since the approvals propagate and get included in the blocks unconditionally,
within ﬁnite amount of time there will be some block b2 which has in itself or in
some blocks in its ancestry approvals from 2f + 1 honest block producers of the
form described above. From perspective of b2, b1 will have quorum pre-vote.
Again due to theorem 2 within ﬁnite amount of time there will be some
block b3 that has b2 in its ancestry that has doomslug ﬁnality. Each honest
block producer will then generate an approval such that
1. its reference block is in the ancestry of b1, since the reference block in all
the approvals in the absence of forks is the same.
2. its parent block has b3 in its ancestry.
Since the approvals propagate and get included in the blocks unconditionally,
within ﬁnite amount of time there will be some block b4 which has in itself or in
some blocks in its ancestry approvals from 2f + 1 honest block producers of the
form described above. From perspective of b4 b1 will have quorum pre-commit.
Thus, within ﬁnite amount of time since t b1 will become ﬁnal. Once b1 is
ﬁnal, all the blocks in its ancestry, including b, are also ﬁnal.
To provide a formal proof for the following theorem we would need to better
deﬁne how slashing works and propagates, which is outside the scope of this
paper. Instead we provide a less formal proof that only relies on an assump-
tion that once a block producer is slashed, within ﬁnite amount of time they
can no longer produce blocks, endorsements, skip-messages and approvals, and
therefore cannot commit slashable acts.
Theorem 4 (Finality Gadget Liveness). From any moment in time t0, within
ﬁnite amount of time at least one block that was not previously ﬁnalized by the
Nightshade Finality Gadget will be ﬁnalized.
Proof. Say it is not the case.
According to theorem 2, within some ﬁnite time after t0 some block b that
previously didn’t have doomslug ﬁnality will have doomslug ﬁnality.
Due to
lemma 6 unless some block producer commits a slashable act, b will get ﬁnalized
by the Nightshade Finality Gadget.
Since we assume no new block can get
ﬁnalized by the Nightshade Finality Gadget, it implies that at least one block
producer v committed some slashable act.
Within ﬁnite amount of time v can no longer commit slashable acts. Within
ﬁnite amount of time after that a new block b′ will have doomslug ﬁnality. Again,
for that block to not get ﬁnalized by the Nightshade Finality Gadget, at least
one other block producer v′ needs to commit some slashable act.
Since the number of malicious actors is ﬁnite, at some point all the ma-
licious actors will be slashed, and no block producers capable of committing
slashable acts will remain. At that point the very next block that will have
doomslug ﬁnality will become ﬁnalized due to lemma 6, causing a contradic-
tion.
18
4
Conclusion
In this paper we presented a block production gadget and a ﬁnality gadget
constructions that under synchronous network allow block producers produce
blocks such that after a single round of communication a block is irreversible
unless at least one block producer is slashed, and after two rounds of commu-
nication a block is irreversible unless one third of all the block producers are
slashed.
While we require synchronous network for the performance guarantees, the
safety is guaranteed even under asynchronous network, and the liveness is guar-
anteed under partially synchronous network.
Doomslug and Nightshade Finality Gadget are both used in NEAR Proto-
col, which is a sharded blockchain protocol. The sharding design of NEAR is
presented in [5]. NEAR reference client is being developed as an opensource
project, you can follow it at https://github.com/nearprotocol/nearcore.
References
[1] Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT
consensus. CoRR, abs/1807.04938, 2018.
[2] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.
Ouroboros:
A provably secure proof-of-stake blockchain protocol.
In
CRYPTO, pages 357–388. Springer, 2017.
[3] Alex Skidanov. Fast ﬁnality and resilience to long range attacks with proof
of space-time and casper-like ﬁnality gadget, 2019. http://near.ai/post.
[4] Vitalik Buterin and Virgil Griﬃth.
Casper the friendly ﬁnality gadget.
CoRR, abs/1710.09437, 2017.
[5] Illia Polosukhin Alex Skidanov. Nightshade: Near protocol sharding design,
2019. http://near.ai/nightshade.
19