Tezos is a blockchain¹, and a blockchain is a distributed database that gets updated by adding blocks (small bunches of database operations). Tezos’ basic design goes back to a 2014 whitepaper, which was genuinely groundbreaking² — not least in its insight of making the protocol of the database itself be a mutable database entry; this is the so-called Tezos protocol upgrades. From this idea has grown a broad blockchain ecosystem.

A key design choice is the consensus algorithm: how our system decides which blocks to add, and which to discard. Thus far, Tezos has used and refined a Nakamoto-style consensus algorithm called Emmy. Consensus algorithms are genuinely subtle,³ so it is high time that we explain what Emmy is and how it works:

A survey (and explanation) of Emmy
How does the Emmy family work?
Forks
The three flavours of Emmy
The mathematics of withstanding attacks
Forks starting now
Forks started in the past
A tool, and the attack model
- A concrete tool
- Notes on the attack model
The future
- Further reading:

\(\newcommand\ie{\mathit{ie}} \newcommand\dpp{\mathit{pd}} \newcommand\te{\mathit{te}} \newcommand\md{\mathit{md}} \newcommand\db{\mathit{bd}} \newcommand\de{\mathit{ed}} \newcommand\trz{\mathit{level\_reward\_zero}} \newcommand\tr{\mathit{level\_reward\_nonzero}} \newcommand\br{\mathit{block\_reward}} \newcommand\er{\mathit{endorsement\_reward}} \newcommand\f[1]{\mathit{#1}} \newcommand{\set}[1]{\{#1\}} \newcommand{\var}[1]{\f{#1}} \newcommand\epdelay{\mathit{emmy}^{\text{+}}\hspace{-.12cm}\_\mathit{delay}} \newcommand\esdelay{\mathit{emmy}^{\star}\hspace{-.12cm}\_\mathit{delay}} \newcommand\edelay{\f{delay}} \newcommand\edelayp{\f{delay^+}} \newcommand\edelays{\f{delay^*}} % syntax highlighting hack \newcommand\edelaydelta{\edelay_{\Delta}} \newcommand\edelays{\f{delay^\star}} \newcommand\params{\lambda} \newcommand\ie{\f{ie}} \newcommand\te{\f{te}} \newcommand\dpp{\f{dp}} \newcommand\de{\f{de}} \newcommand\dpde{\f{dpde}} \newcommand\bd{\f{bd}} \newcommand\bdz{\f{bd_0}} \newcommand\od{\tau} \newcommand\emmy{\f{Emmy}} \newcommand\emmyp{\f{Emmy^+}} \newcommand\emmys{\f{Emmy^{\star}}} \newcommand\emmyf{[\f{Emmy}]} \newcommand\hb{H} \newcommand\cb{D} \newcommand\pr{\mathtt{Pr}} \newcommand\pprio[1]{\mathbb{P}_{prio}(#1)} \newcommand\pendo[1]{\mathbb{P}_{endo}(#1)} \newcommand\pdiff[1]{\mathbb{P}_{\Delta}(#1)} \newcommand\secu{\eta} \newcommand\steal{\f{sb}} \newcommand\seen{\f{seen}} \newcommand\pseen[1]{\mathbb{P}^{#1}} \newcommand\psteal[1]{\mathbb{P}^{#1}} \newcommand\pcst{\f{no\_delay}} \newcommand\pcstn{\f{past}} \newcommand\pc{p^D} \newcommand\maxp{\f{max\_p}} \newcommand\ph{p^H} \newcommand\barpc{\bar{p}^D} \newcommand\barph{\bar{p}^H} \newcommand\tsh{t^H} \newcommand\tsc{t} \newcommand\bh{b^H} \newcommand\difff[1]{\f{diff\_first}(#1)} \newcommand\diff[1]{\f{diff\_subseq}(#1)} \newcommand\diffl[1]{\f{diff}_{\ell}(#1)} \newcommand\difffp[1]{\f{diff\_first^{\f{no\_delay}}}(#1)} \newcommand\diffp[1]{\f{diff\_subseq^{\f{no\_delay}}}(#1)} \newcommand\diffg{\f{diff}} \newcommand\diffgns{\f{diff}^{ns}} \newcommand\diffgs{\f{diff}^{s}} \newcommand\cchain{\f{ch}^\cb} \newcommand\hchain{\f{ch}^\hb}\)

A survey (and explanation) of Emmy

In this blog post we will give an explanation and survey of the Emmy family of consensus algorithms, which has powered the Tezos blockchain since its inception. We will start with

an explanation of how the Emmy family works, then
discuss in specific detail the mathematics of withstanding attacks, then
discuss “forks starting now”, then
discuss “forks starting in the past”, then
mention a concrete tool to compute expected confirmation numbers — how long you expect to wait for transactions to become final; bankers would call this the “settlement time” — and finally
we discuss the future — including a planned move to Tenderbake (which has also been the topic of a previous blog post).

We mentioned there are several flavours of Emmy:

Currently, Tezos uses the Emmy+ consensus algorithm.
This is a successor⁴ to Emmy.
An upgrade to Emmy* is imminent in the Granada protocol proposal (election).

So ‘Emmy’ is a family of consensus algorithms — technically, a collection of proof-of-stake Nakamoto-style consensus algorithms — parameterised over some dials and switches which we can be tweaked to optimise safety and performance — and ideally, both at the same time.

These parameters include (explanations will follow below):

the number of endorsement slots per block,
the minimal delay function, and
the chain fitness function.

The evolution from Emmy to Emmy+ to Emmy* consists of tweaks to these parameters, each of which had to be carefully considered and tested. These tweaks are practically motivated: each iteration offers worthwhile real-world improvements in either speed or security or (preferably) both.⁵

The evolution of these algorithms has been a part of the evolution of Tezos itself, and it illustrates just how far it is possible to optimise Nakamoto-style consensus in a live, functioning, industrial blockchain. So …

How does the Emmy family work?

A blockchain is a sequence of blocks. We call position of a block in this sequence its level: thus, the “block at level $l$” is the $(l{+}1)$-th block in the sequence. We start counting at zero, so the first block (also called the genesis block) is at level $0$. (You can view details of the genesis block of the Tezos blockchain.)

Blocks are timestamped. So the block at level $l$ will also have some timestamp $t_l$.

For simplicity suppose also that the blockchain is unforked, meaning that the network agrees on the blockchain up to and including block $B$ at level $l$ (we consider the more general case of a forked chain below).

Now it’s time to decide on what block to add at level $l{+}1$ to our unforked chain. The consensus algorithm gets to work, according to the following rules:

The rules

High-level view …

At a high level, Emmy acts as follows:

sort participants into random order,
query each participant in order for a block, and
add the first valid block received, to the blockchain.

But this is a blockchain system, so we need an algorithm that can achieve the effect above and

the algorithm is scalable, efficient, and resilient to real-world faults such as network interruptions, and
does not assume a central authority, and
does not assume all participants are well-behaved.

… in more detail

We will need two inputs to the algorithm:

We need a random seed.

This is a number used to seed a (pseudo)random generating function. This is obtained as a hash of the state of the blockchain approximately $4096\times 5$ blocks in the past — at one block per minute that means $20480$ minutes ago (about two weeks).
We need a mathematical function called the delay function.

$\mathit{delay}$ has type $\mathbb N\times\mathbb N\to\mathbb N₊$, meaning that it inputs two nonnegative numbers and returns a strictly positive number. $\mathit{delay}$ is a parameter of the Emmy algorithm, meaning that it varies between Emmy, Emmy+, and Emmy*; for now, it just suffices that this exists. More on this shortly.

We now proceed as follows:

Using the random seed described above, each active blockchain participant $a$ with at least one roll ( = 8,000 ꜩ) is randomly assigned two pieces of data:
- a unique earliest priority $p(a)$, which is a non-negative number.⁷ Smaller numbers are better and each participant gets a different number (think: positions in a queue).
- an endorsement power $w(a)$, which is a number between 0 and 32 (think: magic talismans; see below).
Note that the earliest priority and the endorsement power are abstract data quantities. We discuss below how these quantities get mapped to a time in seconds.

The distribution of earliest priority $p(a)$ is proportional to participants’ stake: if $a$ has more stake then there is a correspondingly increased chance that e.g. $p(a)=0$ or $p(a)=1$.

Equivalently: priorities are dispensed by a uniform random distribution on a per-roll basis, so a participant who controls more rolls, will get proportionally more priorities.

The distribution of endorsement power $w(a)$ is also proportional to participants’ stake, and furthermore the total endorsement power dispensed must sum to 32. Equivalently: the 32 endorsement slots are distributed per roll, so a participant who controls more rolls, is proportionally more likely to get one or more endorsement slots.

So intuitively:

imagine that Tezos is a fantasy magic kingdom which dispenses queue positions and a strictly limited total of 32 magic talismans to its landowners — and, because this is a proof-of-stake system, larger landowners tend to get better queue numbers and more talismans. We will continue this example below.
Recall that we assumed for simplicity that all the participants agree on the state of the blockchain so far, and in particular that it ends at block $B$ at level $l$.

Now, any participant $a$ can endorse (vote for) $B$ by transmitting an endorsement operation $d(a,B)$ across the network.

So suppose at some particular moment that block $B$ has received a set $e_B=\{d(a_1,B), d(a_2,B), \dots, d(a_n,B)\}$ of endorsements from distinct participants $(a_1,a_2,\dots,a_n)$ with endorsement powers $(w(a_1),w(a_2),\dots,w(a_n))$ respectively.⁸ Write $w(e_B)$ for the sum of the endorsement powers of $a_1$ to $a_n$:
$$ w(e_B) = w(a_1) + w(a_2) + \dots + w(a_n) . $$

We see that each endorsement is weighted by the endorsement power $w(a_i)$ of $a_i$ — so in effect, at most 32 participants can usefully endorse $B$, since there are at most 32 endorsement slots to go around.

Then a participant with earliest priority $p(a)$ has the right to bake a valid block $B'$ and attach it to a chain after a delay of
$$ delay(p(a),w(e_B)) $$
seconds. We discuss in detail below what function $delay$ is; for now the function is just a parameter of the algorithm.

Every block contains enough information (timestamp, priority, public key of creating participant, endorsements, and so on) that every participant can check — just by examining it and without reference to any external oracle — whether it validly follows on from the last block.⁶

Then $B'$ is transmitted to the network and, assuming everything is working efficiently, $B'$ gets appended to the blockchain at level $l{+}1$.
If everything is not working efficiently — perhaps the network is slow or participant $a$ is rebooting — then time passes and eventually a delay of $delay(p(a'),w(e_B'))$ may pass, where $a'$ is the next participant in line and $e_B'$ is the number of endorsements that $a'$ sees for $B$. From this moment, both $a$ and $a'$ can bake blocks. In particular, if $a$ remains hors combat then $a'$ may be the one to bake the next valid block. And so it goes on until somebody bakes a valid block and the blockchain is extended.

It might be helpful to continue our analogy of Tezos as a magic kingdom:

Suppose the Tezos blockchain is a magic kingdom and suppose block $B$ at level $l$ is the most recent Law of the magic kingdom to be passed. Landowners line up in a random order and 32 magic talismans are randomly dispensed, where both queue order and talisman distribution are weighted according to how much land each landowner owns. Landowners use their talismans to broadcast a magical blessing of the most recent Law, and — depending on the delay function, which depends on a landowner’s queue position, and on the talisman-weighted number of blessings of the most recent Law $B$ that the landowner has received — the first landowner to bake a block, gets to determine the next $B'$, i.e. to write the next law of the magic kingdom. Of course, this means that large landowners connected to large sections of the magical blessing broadcast network, tend to get early queue positions and receive lots of the magical blessings and so tend to set the laws; whereas those with smaller parcels of land or more restricted access to the network, tend to miss out.

Why we need a consensus algorithm

If this seems complicated, note what it buys us:

there is no central authority, and
the system self-organises to reward having a large stake and following the rules, and is resilient against attack, non-participation, and network delays.

Large fast networks beat small slow ones

The algorithm dispenses endorsements amongst all active participants. Thus if a small group of nodes becomes isolated for a while — or just decides to go its own way — then it is not the case that they can just give one another early priorities, vigorously endorse one another’s blocks, and so build a long chain.⁹

An isolated group may fork, but

its members can garner relatively few priorities (because statistically speaking, most priorities go to participants not in the group) and
relatively few endorsement slots (ditto),

so that the values of the delay function within the group will be relatively large, and it will make relatively slow progress. Thus, if and when the group tries to rejoin the main body of the network, the group’s branch will be short compared to the branch of the rest of the blockchain, and it will die off.

Endorsements

At first sight it might seem strange to endorse the last block $B$. After all $B$ has already been attached to the blockchain, and we assumed for the sake of argument that there are no forks. So why does it even matter if we now endorse it?

Endorsements tend to unify the network and kill off small, slow, isolated chains: a small fragment of the network will find it difficult to ignore the rest of the community and go its own way,

not just because it will struggle to obtain small priorities, but also
because even once it gets a priority it may also struggle to gain endorsements from the wider network for the block that it bakes with that priority.

In principle (withholding) endorsements could also be used to penalise $B$ if we disapprove of its contents. In practice this is not done: participants just endorse $B$ as soon as they can (for which they are rewarded with endorsing rewards). See the algorithm from the point of view of a participant.

Forks

Recall that we simplified and assumed that all participants agree on the state of the blockchain so far. But what if they don’t? In practice the chain can fork, meaning that different participants have different views of the blockchain so far.¹⁰

So what if the blockchain is forked?

Recall that the consensus algorithm depends on these three parameters:

the random seed, which was seeded from the state of the chain at least two weeks ago — we presume that no fork can last that long, so every participant now agrees on this quantity — and
the delay function, which is a fixed parameter of the current economic protocol, so again every participant agrees on this — and
the fitness function which is also a fixed parameter of the economic protocol.

So we can assume that these parameters are shared and everybody is working from a shared notion of “what is a valid chain”. Furthermore, checking validity of a proposed chain is precise and unambiguous: participants should just work from the fittest blockchain branch that they can see. Note that the use of a fitness function to choose the canonical branch is common to Nakamato-style consensus algorithms. This is known in the literature as the fork choice rule.

If the network becomes partitioned then the blockchain may fork for a while, and the partitions could evolve independently for a while, but it will snap back once connectivity is restored, provided that most (= at least half) of the participants work following the rules above. This is called a Nakamoto-style system because this is how Bitcoin works.¹¹

The rules: the Emmy family, from the point of view of a participant

Continually observe blocks and endorsements on the network.
Work from the ‘best’ valid chain $\mathcal B$ that you observe. If the system is unforked then picking the best chain is easy because there is only one. If the system is forked, only switch to another chain if it is ‘better’. What ‘better’ means for a chain is determined by a metric called chain fitness, discussed below.
Endorse the first block you observe that can validly attach to $\mathcal B$.
If you do not observe such a block, then produce one as soon as the delay function says that you validly can.

The need for a chain fitness function

Suppose we are on the blockchain and it is forked. How is an honest participant to decide which chain is better?¹³ Here are two possible answers:

In Emmy:

chain fitness is equal to the sum of the length of a chain and the number of endorsements which it contains.

Thus, an honest participant who bakes on the fittest branch of a fork will prefer the branch with the most blocks-plus-endorsements.
In both Emmy+ and Emmy*:

chain fitness is equal to the length of the chain.

Thus, an honest participant who bakes on the fittest branch of a fork will prefer the longest branch.¹⁴

Reasons for the change in fitness function

This is discussed in the post on Emmy+: search for “simplifies the optimal baking strategy”.

The issue with the Emmy fitness function (item 1 in the list above) is that it gives equal weight to an endorsement and a block — and each block can hold up to 32 endorsements. Thus, in terms of chain fitness, gathering endorsements for the last block is more important than producing the next block and thus extending the chain.

This incentivises bakers to hold off baking a block until they can pack it with as close as possible to a full complement of 32 endorsements, for fear that if they do not then their chain might be overtaken by a shorter fork (as much as ¹⁄₃₂ of the length) but with more endorsements and so greater fitness.

This incentive structure could slow down the blockchain overall, and in particular it could slow down transaction rate (the overall rate at which transactions get included in blocks and baked onto the chain), which is not good for users, who are likely to prefer high transaction rates and rapid transaction settlement times.

Emmy+ and Emmy* address this by setting chain fitness to equal chain length. Endorsements still play a role, but the effect is exerted via the delay function — discussed below; essentially, more endorsements means you can bake earlier. Honest participants just prefer the longest chain and there is no reason not to bake a block, once the delay function permits it.

The three flavours of Emmy

List of flavours

Emmy exists in three flavours:

The original version Emmy. This was used from 2014 until 18 October 2019 (this is the first block to use the Babylon protocol). Emmy is no longer current.
The new version Emmy+. This is current.
The forthcoming upgrade to Emmy* in Granada.

These are essentially the same algorithm but they differ in tweaks to their parameters. Specifically:

Emmy and Emmy+ have 32 endorsement slots per level. Emmy* has 256, speeding up confirmation time and increasing user participation.¹⁵
The chain fitness function of Emmy is “blocks + endorsements”; that of Emmy+ and Emmy* is just “blocks”, as discussed above.
The delay functions of the three algorithms differ, as discussed below.

The Delay function of Emmy

In Emmy, $\edelay$ is a function just of the priority $p$:

$$ \begin{equation}\tag{1}\label{eq:delay} \begin{array}{r@{\ }l} \edelay(p) =& \db + \dpp \cdot p \\ =& 60 + 75 \cdot p \quad \text{(seconds)}. \end{array} \end{equation} $$

$\db=60$ is the base delay. Thus this is a constant minimal offset from one block to the next.
$\dpp=75$ is the priority delay. Thus this establishes the time between priorities, as discussed above.

Worked examples:

A participant with earliest priority $0$ can start baking after $60+75\cdot 0 = 60$ seconds.
A participant with earliest priority $1$ can start baking after $60+75\cdot 1 = 135$ seconds.

The Delay function of Emmy+

Emmy+ adds a dependency on $w$, the endorsement power of the endorsements in the block to be baked:

$$ \begin{equation}\tag{2}\label{eq:epdelay} \begin{array}{r@{\ }l} \edelayp(p, w) =& \db + \dpp \cdot p + \de\cdot \max(0, \frac{3}{4}\cdot\te - w) \\ =& 60 + 40 \cdot p + 8\cdot \max(0, 24 - w) \quad\text{(seconds)}. \end{array} \end{equation} $$

It might help to view $\mathit{delay}$ abstractly as a function that tends to increase on the first argument (the priority slot), and decreases linearly on the second (the endorsement power). So:

later priority slot = more delay;
more endorsements = less delay.

In words, Equation \eqref{eq:epdelay} says that the delay is:

a base delay of $\db=60$ seconds, plus
a priority delay of $\dpp=40$ seconds, plus
a delay per missed endorsement of $\de=8$ seconds for every endorsement slot that the block to be baked falls short of a threshold of $24=\frac{3}{4}\cdot \te$ out of the $\te=32$ available endorsement slots.

From the Babylon protocol upgrade (18 October 2019) to time of writing, these parameters have been fixed at

$$ \db = 60,\quad \dpp=40,\quad \de=8,\quad \te=32. $$

Worked example:

A participant with earliest priority $0$, baking a block with $16$ endorsements for the previous block — thus, with half of the full complement of 32 possible endorsement slots — can start baking after $60+40\cdot 0+8\cdot 8=124$ seconds.
If the participant had gathered $24$ instead of $16$ endorsements, then this would drop to $60$ seconds.
A participant with earliest priority $1$, baking a block with $16$ endorsements for the previous block — thus, with half of the full complement of 32 possible endorsement slots — can start baking after $60+40\cdot 1+8\cdot 8=164$ seconds.
If the participant had gathered $24$ instead of $16$ endorsements, then this would drop to $100$ seconds.

The Delay function of Emmy*

Emmy* builds on the delay function of Emmy+ while observing that during normal operation most blocks are baked at priority 0 and with plenty of endorsements. So let’s fast-track this optimal case:

$$ \begin{equation}\tag{3}\label{eq:esdelay} \edelays(p, w) = \begin{cases} \md & \text{ if } p = 0 \wedge w \geq \frac{3}{5}\te \\ \edelayp(p, w) & \text{ otherwise} \end{cases} \end{equation} $$

Above $\md=30$ is the minimal delay and $\te=256$ is the number of endorsement slots. Furthermore, the constant $\de$ used by $\edelayp(p, w)$ has been changed to 4.

Worked example:

A participant with earliest priority $0$, baking a block with $153$ endorsements for the previous block — thus, with less than 60% of the full complement of 256 possible endorsement slots — can start baking after $60$ seconds.
A participant with earliest priority $0$, baking a block with $154$ endorsements for the previous block — thus, with at least 60% of the full complement of 256 possible endorsement slots — can start baking after $30$ seconds.
If the participant had gathered $192$ instead of $155$ endorsements, then this would make no difference and they can still start baking after $30$ seconds.
A participant with earliest priority $1$, baking a block with $128$ endorsements for the previous block — thus, with half of the full complement of 256 possible endorsement slots — can start baking after $60+40\cdot 1+4\cdot (192 - 128)=356$ seconds.
If the participant had gathered $192$ instead of $128$ endorsements, then this would drop to $60+40\cdot 1=100$ seconds.

So much for our overview of the delay function. How does this help the blockchain to withstand attacks? What does an attack look like, anyway? Read on …

The mathematics of withstanding attacks

An attack scenario (a Valuable Car)

Let the time be $t=0$ and consider the following scenario:

You have a Valuable Car to sell.
I agree to purchase it and we agree on a sum of Quite A Lot for the sale.
I bake a block $B$ at time $t=0$ recording a transfer of Quite A Lot from my account to yours.
I also secretly bake another block $B'$ (this is called double baking). $B'$ is identical to $B$ except that this includes a transaction for Far Less from my account to yours.
The main Tezos chain $\mathcal M$ continues to evolve from $B$, and (still in secret) I bake an alternative chain $\mathcal S$ evolving from $B'$ instead of from $B$.
Meanwhile, I take possession of the Valuable Car, and drive it home.
When I get home, I reveal my chain to the network. In this chain I bought your car, but for Far Less rather than for Quite A Lot.

If you complain, I can say “What’s the problem? I paid you and you gave me the Valuable Car”.

Say that my attack succeeds when there exists some time $t>0$ at which $\mathcal S$ is longer than $\mathcal M$. Then, I can reveal $\mathcal S$ to the world and as per the rules honest participants will bake from $\mathcal S$.
Say that my attack fails when for every time $t>0$, $\mathcal S$ is shorter than $\mathcal M$. I can still reveal $\mathcal S$ to the world, but as per the rules it will be ignored.

Whether or not this attack succeeds or fails depends on the relative rates of growth of $\mathcal M$ and $\mathcal S$. This is dictated by the delay function as discussed above. In the long term my chain $\mathcal S$ will be slower than $\mathcal M$ (so long as I have less than half the total stake on the chain) because I will gain relatively fewer priorities and endorsements. Still: like a gambler in a casino, I might get lucky.

So we can ask:

For a given attacker stake, what are the chances of an attacker undoing a transaction as outlined above?
Turning the question around: after how many blocks on the main chain after I paid you Quite A Lot can you feel safe about handing over your Valuable Car?

Calculating the confirmation number

Setting the scene, and some simplifying assumptions

We can amalgamate multiple dishonest bakers $\cb_i$ into a single ‘composite’ dishonest baker $\cb$ having as stake fraction the sum of the stake fractions of $\cb_i$, and similarly for the honest bakers. We can also think of a fork as two competing chains — an honest main chain $\mathcal M$ and a dishonest hostile chain $\mathcal S$ — both extending some genesis block at level $\ell = 0$.¹⁶

Thus we reason henceforth using

a single honest baker $\hb$ with stake fraction $1-f$ and
a single dishonest adversary baker $\cb$ with stake fraction $f$,
both competing to add a longer chain starting from a common block at level $\ell = 0$.

We’re playing for the adversary $\cb$ in the mathematics below, so we write

$f$ for the stake fraction of $\cb$,
$p$ for the earliest priority of $\cb$, and
$e$ for the number of endorsement slots of $\cb$.

To win, the dishonest chain $\mathcal S$ of $\cb$ must accumulate more blocks than the honest main chain $\mathcal M$. So we need to compute the probability that the timestamp of the $l$th and final block in $\mathcal S$ is less than the timestamp of the $l$th and final block in $\mathcal M$. If this happens, then $\cb$ can reveal the dishonest chain $\mathcal S$ to the network and participants will switch to it.

Assume that everyone favours themselves, and the network favours the attacker

We assume that:

Everybody bakes as early as they can (thus handing minimal advantage to the adversary).
The honest baker’s messages take time $\Delta$ to arrive, which intuitively corresponds to some slowest possible path in the network.
The attacker’s messages arrive instantly.

So this is a worst case scenario for the honest chain, in which honest network communications are as slow as they possibly could be, and dishonest attacker communications are very fast. In symbols, we can calculate¹⁷ that for a block baked by $\hb$, the minimum delay function $\edelaydelta(\ph, e)$ is:

$$ \edelaydelta(\ph, e) = \min\bigl(\max(2\Delta, \edelay(\ph, e)),\ \max(\Delta, \edelay(\ph, 0))\bigr) % \edelaydelta(p, e) = \edelay(p, e)$ for blocks baked by the $$

Some probabilities

We want to calculate the probability that the hostile chain $\mathcal S$ overtakes the main chain $\mathcal M$, under the assumptions above. This can be expressed in terms of differences between minimal block delays, using a large summation over the distribution of priorities and endorsements.

Write $\pprio{f,p}$ for the probability that the earliest priority of a player with stake fraction $f$ is $p$:
$$\pprio{f,p} = \pr[best\_prio = p] = (1-f)^p f$$
(recall: the first priority is $0$).
Write $\pendo{f,e}$ for the probability that $\cb$ gets $e$ many endorsement slots:
$$\pendo{f,e}=\pr[num\_endo = e] = \textstyle\binom{32}{e}f^e(1-f)^{32-e}.$$

We distinguish two cases, depending on whether we are baking a block to follow the shared genesis block, or subsequent blocks:

\begin{align} \difff{\pc, \ph, e} & := \edelay(\pc,32) - \edelaydelta(\ph, 32 - e) \tag{4}\label{eq:diff1}\\ \diff{\pc, \ph, e} & := \edelay(\pc,e) - \edelaydelta(\ph, 32 - e) \tag{5}\label{eq:diff} \end{align}

Above:

$\ph$ and $\pc$ are parameters representing the best priorities of $\hb$ and $\cb$ respectively.
The equations just subtract the minimal delay function for $\hb$ from that of $\cb$. A negative value here is good for the dishonest chain $\mathcal D$, and a positive value is good for the honest chain $\mathcal M$.
$\difff{}$ corresponds to the case when we compute the delay difference for the first block $\cb$ bakes which is on top of genesis and $\cb$ has access to all endorsements for genesis, while $\hb$ only has its own endorsements, not those of $\cb$ — in contrast, $\diff{}$ corresponds to the case of subsequent blocks $\cb$ bakes; for these ones, $\cb$ can only use its own endorsements, since $\hb$‘s endorsements are for blocks on $\mathcal M$ that are not on $\mathcal S$, and $\cb$ therefore cannot use them to extend $\mathcal S$.

We write sequences of priorities and endorsements of length $\ell\geq 1$ as

$$ \barpc = (\pc_1,\dots, \pc_\ell), \qquad \barph = (\ph_1,\dots, \ph_\ell), \quad\text{and}\quad \bar{e} = (e_1,\dots, e_\ell) $$

and, parameterised over these sequences, we define an accumulated difference $\diffl{\barpc,\barph,\bar{e}}$ by

$$ \diffl{\barpc, \barph, \bar{e}} := \difff{\pc_1, \ph_1, e_1} + {\sum_{2\leq i\leq \ell}}\diff{\pc_i, \ph_i, e_i} . $$

Forks starting now

We can now calculate the probability that

for chain length $\ell\geq 1$, the timestamp of the head of $\cb$‘s chain, minus the timestamp of the head of $\hb$‘s chain, is equal to $\delta$ seconds

as follows:

\begin{align} \pr_\ell[\var{chains\_diff}=\delta] := \sum_{\substack{(\barpc, \barph)\in P_2^{\ell},\bar{e}\in [32]^{\ell}\\\diffl{\barpc,\barph,\bar{e}} = \delta}}\;\prod_{1\leq i\leq\ell}\pendo{f,e_i}\cdot \pprio{f,\pc_i,\ph_i} \label{eq:pr0} \end{align}

where above, $P_2 = \{(p,p')\mid \text{either } p = 0 \text{ or } p'=0\}$ and

$$ \pprio{f,\pc,\ph} := \left\{ \begin{array}{ll} \pprio{f, \pc} & \text{if $\ph = 0$}\\ \pprio{1-f, \ph} & \text{if $\pc = 0$}\\ \end{array} \right. $$

to distinguish between the case when either $\cb$ or $\hb$ has priority 0.

Next, we give an inductive characterisation of $\pr_\ell[\var{chain\_diff}=\delta]$ which is amenable to computation.

We first consider the probabilities corresponding to the differences in Equations \eqref{eq:diff1} and \eqref{eq:diff}.

\begin{align} \pr[\var{first\_diff}=\delta] := \sum_{\substack{(\pc, \ph)\in P_2,e\in [32]\\\difff{\pc,\ph,e} = \delta}}\;\pendo{f,e}\cdot \pprio{f,\pc,\ph} \tag{7} \label{eq:pri00} \\ \pr[\var{subseq\_diff}=\delta] := \sum_{\substack{(\pc, \ph)\in P_2,e\in [32]\\\diff{\pc,\ph,e} = \delta}}\;\pendo{f,e}\cdot \pprio{f,\pc,\ph} \tag{8} \label{eq:pri01} \end{align}

Above:

$\pr[\var{first\_diff}=\delta]$ is the probability that the delay difference between the first block $\cb$ bakes on its secret chain $\mathcal{S}$ and the first block $\hb$ bakes on $\mathcal{M}$, is $\delta$.
$\pr[\var{subseq\_diff}=\delta]$ is the probability that the delay difference between a block (other than the first one) $\cb$ bakes on its secret chain $\mathcal{S}$ and the block $\hb$ bakes on $\mathcal{M}$ at the same level, is $\delta$.

For a given difference $\delta$, we define the probability of forks of length $\ell$ inductively by:

\begin{align} &\pr^{\mathit{now}}_1[\var{chains\_diff}=\delta] := \pr[\var{first\_diff}=\delta] \tag{9} \label{eq:prn1} \\ &\pr^{\mathit{now}}_{\ell{+}1}[\var{chains\_diff}=\delta] := \displaystyle\sum_{\substack{(\delta_{\ell}, \delta_1) \in \mathbb{Z}^2\\\delta_\ell+\delta_1=\delta}}\pr^{\mathit{now}}_{\ell}[\var{chains\_diff}=\delta_\ell]\cdot\pr[\var{subseq\_diff}=\delta_1] \tag{10} \label{eq:prnl} \end{align}

We note that $\delta_\ell$ can be negative as long as $\delta_1$ is big enough to compensate.

Putting this all together, the probability that $\cb$ bakes a fork of length $\ell$ that is faster than that of $\hb$ is:

\begin{align} \pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)} = \ell)] = \displaystyle\sum_{\delta \leq 0}\pr^{\f{now}}_\ell[\var{chains\_diff}=\delta] \tag{12} \label{eq:lf} % syntax highlighting hack - !_ \end{align}

We use $\pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}= \ell)]$ to answer the question:

Given some transaction in some block $B$, how many confirmations — blocks after $B$ — must we observe to be Reasonably Sure that the transaction will remain in the chain?

We call this number of blocks the confirmation number. By Reasonably Sure, we mean

“with probability smaller than some reasonable security threshold $\secu$“

whose value can be fixed to the reader’s taste. In practice, we fix a value for our security threshold $\secu$ such that our expectation of being wrong about a block being final is expected to be roughly once every two centuries, and conversely; an attacker would have no reasonable confidence of seeing an attack succeed in their lifetime. For example, when there is one block per minute, we set $\secu=10^{-8}$, as done in our previous analysis of Emmy+.

So to return to our motivating example above of the Valuable Car, and assuming one block per minute, all you need to do is wait confirmation number number of minutes before handing over the keys, and you should be Reasonably Sure that the payment of Quite A Lot is final. If you’re inclined to be paranoid, just wait a few minutes longer (meaning in effect that you use a lower and so more stringent value of $\secu$).

To compute the confirmation number concretely, we simply need to find the smallest $\ell$ such that

$$ \pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)} = \ell)] < \secu. $$

We built a tool for computing this, discussed below. For reference, the maths above also underlies the results presented in “forks starting now”.

In practice — for Tezos as it currently runs Emmy+ and assuming an attacker controlling at most one fifth of the network, a message delay $\Delta$ less than 60 seconds, and a security threshold $\secu$ of $10^{-8}$ — confirmation number is about seven blocks.

Forks started in the past

The analysis above can be refined using conditional probabilities: as time passes we can observe the behaviour of the current blockchain $\mathcal M$ and gather information about its health, and this might inform our estimates of the remaining confirmation time.

We can ask:

My transaction $tx$ was included $n$ blocks ago into $\mathcal M$ (i.e. there are $n{-}1$ blocks on top of the block with my transaction $tx$) and $\delta^o$ time ago. Can I be Reasonably Sure that my $tx$ is final?

To answer this, we consider the accumulated delay of the current chain $\mathcal M$, relative to an ideal chain $\mathcal I$ operating in ideal conditions in which all blocks are produced at priority 0 (i.e. by the first available baker) with a full complement of 32 endorsements and without any network delays.

The accumulated delay $\delta^a$ of $\mathcal M$ is easy to calculate: in ideal conditions the ideal chain $\mathcal I$ bakes one block every $\mathit{time\_between\_blocks}$ seconds,¹⁸ so the accumulated delay of an $n$-block blockchain-fragment is just

$\delta^o$ (the timestamp of the current block minus the timestamp of the block containing my transaction $tx$),
minus $n \cdot \mathit{time\_between\_blocks}$,¹⁹

or in symbols:

$$ \delta^a = \delta^o - n\cdot \mathit{time\_between\_blocks} $$

The accumulated delay $\delta^a$ is a simple measure of the ‘health’ of $\mathcal M$: the smaller $\delta^a$ is, the healthier $\mathcal M$ is. Intuitively an unhealthy chain is easier for a hostile baker $\cb$ to attack with a hostile chain $\mathcal S$, so our task is now to quantify this.

We compute the probability that our hostile baker $\cb$ has a hostile chain $\mathcal S$ that $\cb$ has forked from the main chain just before the block with our transaction $tx$ and that has the same length as $\mathcal M$ but is faster. We conceptually split $\mathcal S$ into two parts: a “past” one consisting of first $n$ blocks, and a “future” one consisting of the subsequent blocks.

We will use our ideal chain $\mathcal I$ as an intermediate reference step. Recall that we assume that blocks on $\mathcal I$ are baked with no delay, that is, every $\bd$ seconds. Then we proceed in three steps:

For the first $n$ blocks, we compare $\cb$‘s chain $\mathcal S$ with the ideal chain $\mathcal I$.
We then shift from $\mathcal I$ to $\mathcal M$ to account for $\delta^a$.
At this point, we are in a similar situation as with forks starting now, and so we compare $\mathcal S$ with $\mathcal M$.

For Item 1, the basic element we need is the difference between the minimal block delays on $\mathcal S$ and on $\mathcal I$:

\begin{align} \difffp{\pc, \ph, e} & := \edelay(\pc,32) - \mathit{time\_between\_blocks} \tag{13} \label{eq:pdiff1}\\ \diffp{\pc, \ph, e} & := \edelay(\pc,e) - \mathit{time\_between\_blocks} \tag{14} \label{eq:pdiff} \end{align}

We note that the above equations are similar to Equations \eqref{eq:diff1} and \eqref{eq:diff}, with the difference that we subtract $\bd$ from the definition of the ideal chain.

We can write the probabilities corresponding to Equations \eqref{eq:pdiff1} and \eqref{eq:pdiff} as follows:

\begin{align} &\pr^{\pcst}[\f{first\_diff}=\delta] = \displaystyle\sum^{32}_{e=0}\pendo{f,e}\cdot \sum_{\substack{\pc\geq 0\\{\difffp{\pc,0,e}=\delta}}} \pprio{f,\pc} \tag{15} \label{eq:pasteq1} \\ &\pr^{\pcst}[\f{subseq\_diff}=\delta] = \displaystyle\sum^{32}_{e=0}\pendo{f,e}\cdot \sum_{\substack{\pc\geq 0\\{\diffp{\pc,0,e}=\delta}}} \pprio{f,\pc} \tag{16} \label{eq:pastge1} \end{align}

Similar to Equations \eqref{eq:prn1} and \eqref{eq:prnl}, for a given difference $\delta$, the probability that the difference between $\mathcal S$ and $\mathcal I$ is $\delta$ is defined inductively as:

\begin{align} &\pr^{\pcst}_1[\f{chains\_diff} = \delta] = \pr^{\pcst}[\f{first\_diff} = \delta] \tag{17} \label{eq:past1} \\ &\pr^{\pcst}_n[\f{chains\_diff} = \delta] = \displaystyle\sum_{\substack{(\delta_{n{-}1}, \delta_1) \in \mathbb{Z}^2\\\delta_{n{-}1}+\delta_1=\delta}}\pr^\pcst_{n{-}1}[\f{chains\_diff} = \delta_{n{-}1}]\cdot\pr^\pcst[\f{subseq\_diff} = \delta_1] \end{align}

For Item 2, $\pr_n^\pcst[\f{chains\_diff} = \delta - \delta^a]$ captures the shift with respect to $\delta^a$ and this probability is the base case in the inductive definition for the probability that the difference between $\mathcal S$ and $\mathcal M$ is $\delta$, which is the probability mentioned in Item 3:

\begin{align} &\pr^\pcstn_1[\f{chains\_diff} = \delta \mid \delta^a,n] = \pr_n^\pcst[\f{chains\_diff} = \delta - \delta^a]\tag{18}\label{eq:shift}\\ &\pr^\pcstn_{\ell{+}1}[\f{chains\_diff} = \delta \mid \delta^a,n] = \displaystyle\sum_{\substack{(\delta_{\ell}, \delta_1) \in \mathbb{Z}^2\\\delta_\ell+\delta_1=\delta\\\delta_{\ell} > 0}}\pr^\pcstn_{\ell}[\f{chains\_diff} = \delta_\ell\,\mid \delta^a,n]\cdot\pr_1^\pcstn[\f{chains\_diff} = \delta_1] \tag{19} \label{eq:ppl} \end{align}

For brevity we will write

$\pr^\pcst$ for the probability that $\cb$ baked $n$ blocks until now and
$\pr^\pcstn$ for the conditional probability that $\cb$ bakes $l$ blocks from now given $\pr^\pcst$ and the accumulated delay.

Note the condition $\delta_{\ell} > 0$ in Equation \eqref{eq:ppl}: since $\delta$ represents the difference between the timestamps of $\hb$ and $\cb$, by means of this condition, we do not take into account the probabilities of forks of length $\ell$ the attacker could have won. Thus the probability in Equation \eqref{eq:ppl} represents the probability that the difference between the timestamps of $\mathcal S$ and $\mathcal M$ is $\delta$ and any prefix of $\mathcal S$ is not faster than the corresponding prefix of $\mathcal M$. In other words, $\ell{+}1$ is the first level at which the attacker might have a faster chain.

We define $\pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell) \mid \delta^a,n]$ to be the probability the attacker has a faster fork of any length smaller than or equal to $\ell$:

\begin{align} \pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell) \mid \delta^a,n] = \displaystyle\sum_i^{\ell}\sum_{\delta \leq 0}\pr^\f{past}_i[\f{chains\_diff} = \delta \mid \delta^a,n]. \end{align}

For a block to be considered final, given an accumulated delay $\delta^a$ we need to find the smallest $n$ such that the probability to have a fork of any length in the future is smaller than our security threshold $\secu$ (e.g. $\secu=10^{-8}$), namely, we need to find the smallest $n$ such that $\forall \ell. \pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell) \mid \delta^a,n] < \secu$. To effectively capture the universal quantifier, we define $\pr[\exists\mathit{faster\_fork} \mid \delta^a,n]$ as the following limit:

\begin{align} \tag{20} \label{eq:pfl} \pr[\exists \mathit{faster\_fork} \mid \delta^a,n] = \displaystyle{\lim_{\ell \rightarrow \infty}} \pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell) \mid \delta^a,n]. \end{align}

To solve Equation \eqref{eq:pfl}, it suffices to compute the least $\ell$ such that:

\begin{align} \frac{\pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell) \mid \delta^a,n]}{\pr[\exists\mathit{faster\_fork}.(\mathit{len(faster\_fork)}\leq \ell{-}1) \mid \delta^a,n]} \leq 1 + \epsilon. \tag{21} \label{eq:pastf} \end{align}

where we introduce $\epsilon$ to denote some desired computational precision, just to limit the computation. That is, the larger $\ell$ is, the smaller the probability, and at a certain point the probability of a fork of length $\ell$ is within $\epsilon$ of the probability of a fork of length $\ell{-}1$, and we decide that we are now precise enough and can stop the computation.

So now, to compute (or rather: to estimate using precision $\epsilon$) the confirmation number for a given accumulated delay $\delta^a$, we just need to find the smallest $n$ such that

$$ \pr[\exists \mathit{faster\_fork} \mid \delta^a,n] < \secu. $$

Calculating this is best done by computer, so we have built …

A tool, and the attack model

A concrete tool

The methodology above underlies the results presented in a previous blogpost on forks started in the past. Since then, we have created a standalone tool to perform relevant calculations, which we have made accessible online as a web demo for forks started in the past.

We can use our tool to compute and then compare concrete confirmation numbers for both the forks starting now and the forks started in the past scenarios considered above. Note that forks starting in the past is simply a conditional probability: forks starting now makes no assumptions about future chain health, whereas forks starting in the past asks “given a particular value for chain health since the transaction concerned, what is the expected confirmation number”? So recall our previous assumptions of

an attacker controlling at most one fifth of the network and
a security threshold $\secu$ of $10^{-8}$.

Under a forks starting now scenario — that is, at the time that we generated our block — we expected to wait seven blocks before considering our transaction final.

Suppose now that time has passed and we see that since our transaction, three blocks have been baked in 190 seconds — i.e. with a 10 second delay with respect to an ideal chain in Emmy+ which bakes one block every 60 seconds. Then our tool tells us that, assuming $\Delta$ is less than 60 seconds, the confirmation number is in fact three, so we can already consider our transaction final — four blocks earlier than our original worst-case scenario. And this is just because we have observed that the chain has been reasonably healthy since it included our transaction.

Thus by taking account of chain health since our transaction was included, we may — if the chain remains healthy — get a smaller number of confirmations than in the case of forks starting now.

Notes on the attack model

As always, our security guarantees depend on our attack model: i.e. what we assume an attacker wants to accomplish, and what powers we assume the attacker has when trying to do so. So it is as well to be clear about the limitations, as follows:

In the case of forks starting now, we have only considered that the attacker’s goal is to undo a transaction, so the attack stops when the attacker succeeds. In an alternative attack model, the attacker could keep switching branches and start again with the purpose of maintaining a fork for as long as possible. (Don’t worry! We have analysed this scenario in our blog post on mixed forks in Emmy.) The attacker could also play on multiple branches, while we consider only two branches.
In the case of forks started in the past, we have only considered the case when the attacker starts a fork at the block with the transaction to be undone. In an alternative attack model, the attacker could have started a fork before the block with the transaction to be undone — though one can always bring this within the scope of our analysis by assuming the attacker is trying to undo an arbitrary transaction in the earlier block.

The future

Tezos plans to switch to the classical BFT-style consensus algorithm Tenderbake, because this offers faster finality. Does that mean the Emmy family of algorithms is obsolete? Yes if you only care about Tezos, but absolutely not, if you care about Nakamoto-style consensus in general.

Emmy* is a perfectly fine consensus algorithm which arguably represents an evolutionary peak in Nakamoto-style consensus: the fact that it and Tezos stand to part ways reflects more on what Tezos requires for its future, than on Emmy itself.

Furthermore, all Nakamoto-style consensus algorithms are quite similar, so the lessons learned from optimising Nakamoto-style consensus to run the Tezos blockchain for seven years with increasing sophistication and real-world reliability may be valid, or at least indicative, of your favourite Nakamoto-style consensus algorithm too. Mathematics doesn’t rust, and if the maths in this blog post might help inform the design of future blockchain protocols, then it will have done its job.

Emmy: seven years of updatable consensus