(This post is part of the Understanding GHOSTDAG series)

The safety property of blockChains is a statement about how quickly the confidence in a transaction increases as it lingers on the main chain.

The statement is that the longer transaction stays on the selected chan, the less likely it is to revert. The definition of safety says that the longer a transaction is on the selected chain, the less likely it is to revert. Interestingly, this definition does not say anything directly about whether the selected chain changed. It requires the revert probability to keep decaying even if the chain selection rule switches between two chains containing the transaction. Even if the transaction was on different blocks of the chain, like here:

We all know the adage that “Bitcoin is secure as long as 50% are honest”, but that is not quite the case. A more accurate description is that for any fixed $\alpha < 1/2$, the network is secure against an $\alpha$ attacker. What is the significance of this difference? Essentially, it is true that for any fixed $\alpha<1/2$, the expected time to reach confidence $\varepsilon$ is finite. However, this time grows infinite as $\alpha$ becomes closer to $1/2$. Hence, we must look at each $\alpha$ separately.

This foreshadows a bit about the next post, namely, why we talk about confirmation times, plural, and not just confirmation time. The reason is that for any choice of $0<\alpha<1/2$ and $0<\varepsilon$, there is a different time the receiver will have to wait. That is, the time to gain 1%-confidence against a 20% attacker differs from the time it takes to gain 0.1%-confidence against a 10% attacker.

A nice property of the confirmation times is that they are monotonic in $\alpha$. Your security is not risked if you overestimate the adversary and wait longer.

Another clear fact is that for a fixed $\alpha<1/2$, the time it takes to reach a confidence of $\varepsilon$ goes to infinity as $\varepsilon$ goes to $0$. Unlike with $\alpha$, which we consider fixed, we require that the rate at which this happens is slow. That is, we want the time it takes to reach a confidence of $\varepsilon$ will increase mildly as we greately decrease $\varepsilon$.

First Attempt at a Formal Definition*

We can try to quantify the intuitive discussion above. Ostensibly, we only need to specify what “slow” means. Unsurprisingly, we require it to grow logarithimically. That is, we require it to be $O(\log(1/\varepsilon))$.

We can pack all this discussion nicely into the following:

Definition? For a given blockChain protocol, let $T(\alpha,\varepsilon)$ be the expected time it takes to gain $\varepsilon$-confidence against an $\alpha$-attacker. The protocol is safe if for any $\alpha<1/2$ we have that $$T(\alpha,\varepsilon) = O(\log(1/\varepsilon))\text{.}$$

The definition above is, in fact, not the correct definition of safety. It is almost there but is just a hair too strict, and in fact, no PoW blockChain can satisfy it as it is written. If you read the previous section carefully, you already know what we neglected: orphans. Once we discuss orphans and understand their math better, we will note that this definition is almost correct and fix it.

Safety of Bitcoin in an Orphanless World

Say an adversary has $\alpha<1/2$ of the hash rate, and assume that the honest network never has orphan blocks. That is, the block tree looks something like this:

where tx is the transaction the adversary tries to double-spend, and tx’ is a transaction that conflicts with it. To double-spend successfully, the adversary must wait for when her chain is longer than the honest chain.

Since the adversary has a fraction $\alpha$ of the hash rate, for every $\alpha$ blocks she creates, the honest network creates $1-\alpha$ blocks. By assumption, $1-\alpha > 1/2 > \alpha$, so the honest network has a higher production rate of blocks.

In other words, the expected gap between the weight of the honest chain and the adversarial chain constantly increases in favor of the honest network. Intuitively, this implies that as time progresses, it becomes less likely that the attacker ever succeeds as she accumulates a larger gap to cover.

Turning this intuition into a solid mathematical argument requires some sophistication. We provide a sketch of the full proof later in the chapter.

Orphans and the Scaling Problem

The argument above assumes that orphan blocks do not exist, and this assumption is generally not true. What happens if we do have orphans? Say that the orphan rate is $\delta>0$. That is, one in every $1/\delta$ honest blocks is orphaned. Then for every $\alpha$ blocks created by the adversary, the honest network still creates $1-\alpha$ blocks, but only $(1-\delta)(1-\alpha)$ of them will be on the selected chain.

To adapt the argument above, it is no longer sufficient to require that $\alpha<1-\alpha$. The reason we made this requirement is to assure the honest selected chain grows faster than the adversarial chain. Hence, the correct requirement is actually $\alpha < (1-\delta)(1-\alpha)$.

Note that in the no-orphans case we have $\delta=0$, so $(1-\delta)(1-\alpha)=1-\alpha$. Hence, our new expression is a generalization of the one we used in the orphanless case.

The next order of business is to find out which values of $\alpha$ satisfy the new equation. It is easy to see that (for $\alpha\ge 0$) the condition $\alpha<1-\alpha$ is equivalent to $\alpha<1/2$. So it is natural to compute an expresssion to show how far from the non-orphan case we are. By isolating $\alpha$ and some grade-school symbol manipulation we get at the following equation: $$\alpha<\frac{1}{2}\left(1-\frac{\delta}{2-\delta}\right)\text{.}$$We see that it is very similar to the original $\alpha < 1/2$ condition except there is this additional $\left(1-\frac{\delta}{2-\delta}\right)$ factor. As expected, if are no orphans ($\delta = 0$) this factor is just $1$, but goes to $0$ as the orphan rates grows to $1$.

The following graph illustrates this point by showing what $\alpha$ is required for a double-spend attack when the orphan rate is $\delta$:

If we are being strict, this means that Bitcoin could never satisfy our definition of safety. The orphan rate in a blockchain is always positive. So we can say something along the line of “Bitcoin is very close to being safe assuming $\delta$ is very small In Bitcoin, the most pro-orphan estimations say that $\delta<\frac{1}{150}$, meaning that Bitcoin is “only” safe against 49.999% attackers.

To understand the repercussions of orphans we ask ourselves: what determines $\delta$?

Delta is determined by two quantities: the block delay $\lambda$ and network latency $D$. The block delay is a parameter set by the protocol designer, and it determines what should be the expected time between consecutive blocks. The network latency $D$ is how long it takes for the entire network to learn of a newly mined block. It is not controlled directly by the protocol designer, but is affected by various design choice. Most importantly, since any node has to verify each block, and the time it takes depends on the amount of information on the block, it follows that increasing the block size begets larger $D$.

It is clear that as $\lambda$ decreases blocks are generated more rapidly, this increases the chances that two blocks will be created at very close times to each other, increasing the orphan rate $\delta$. It is also clear that as the latency increases the probability that two blocks are created also simultaneously increases. Hence, increasing block sizes or block rates will increase orphan rates. Formally, the security of Bitcoin only holds as long as $\lambda\gg D$. This requirement is more commonly known as “the Bitcoin scaling problem”.

The Math of Orphans**

With some work, we can quantify the effect of $\lambda$ on $\delta$.

An orphan is only created if two blocks are created within a period of $D$ (this is not a sufficient condition, but it is neccesary). In the appendix, we saw that the number of blocks we see in this period distributes like $Poi(D/\lambda)$. We can work out the probability that at least two blocks are created by taking the complement of the probability less than two blocks is created:

$$\begin{aligned}\mathbb{P}\left[Poi\left(\frac{D}{\lambda}\right)\ge2\right] & =1-\mathbb{P}\left[Poi\left(\frac{D}{\lambda}\right)<2\right]\\& =1-\mathbb{P}\left[Poi\left(\frac{D}{\lambda}\right)=0\right]-\mathbb{P}\left[Poi\left(\frac{D}{\lambda}\right)=1\right]\\& =1-\frac{\left(D/\lambda\right)^{0}\cdot e^{-D/\lambda}}{0!}-\frac{\left(D/\lambda\right)^{1}\cdot e^{-D/\lambda}}{1!}\\& =1-e^{-D/\lambda}-\frac{D}{\lambda}\cdot e^{-D/\lambda}\\& =1-e^{-D/\lambda}\left(1+\frac{D}{\lambda}\right)\\& \approx1-\left(1-\frac{D}{\lambda}\right)\left(1+\frac{D}{\lambda}\right)\\& =\left(D/\lambda\right)^{2}\end{aligned}$$ (where we used the Taylor series approximation).

This gives us the amount of orphans we expect per network delay. If we want to get the number of orphans per block delay we multiply everything by $\lambda/D$ to obtain the simple expression $D/\lambda$.

The catch is that the approximation phase we did assumes that $D/\lambda$ is much smaller than one. Once we enter the regime of block delays comparable (or even smaller than) the network delay, it breaks. However, we can still see quite clearly that in the $\lambda\gg D$ regime the orphan rate is inversely proportional to the block delay. In the Bitcoin network, the latency is in sub-seconds and yet, decreasing the block delay from 10 minutes to 30 seconds will increase orphan rates by a factor of at least 20.

Actually, increasing the block rates like this will increase orphan rates by a lot more. The calculation we did assumes that orphan blocks never point at each other, and completely disregards orphan chains. That is, chains of two or more blocks that are outside the selected chain. These are very rare for small orphan rates, but become meaningful as the orphan rates increase.

Fixing the Definition*

A correct definition of safety must take orphans into account. A definition that does not depend at all on $\delta$ should raise suspicion. We need a definition that only requires security for $\alpha$ sufficiently smaller than $\delta$. It might be tempting to use the expression for $\alpha$ we derived above, but that would be a mistake: this computation is specific to Bitcoin and could not be used for a general definition. The correct way, it seems, is to consider the ratio $D/\lambda$, and require that the maximum $\alpha$ attacker we can deal with approaches $1/2$ as this ratio approaches $0$ (that is, as the block delay becomes much larger than the network delay). This leads to the following:

Definition: For a given blockChain protocol, let $T(\alpha,\varepsilon)$ be the expected time it takes to gain $\varepsilon$-confidence against an $\alpha$-attacker. The protocol is $q$-safe if for any $\alpha<(1/2-q)$ we have that $$T(\alpha,\varepsilon) = O(\log(1/\varepsilon))\text{.}$$ The protocol is safe if it is $O(D/\lambda)$-safe.

Orphans and Difficulty

It is a common misconception that “orphan rates decrease gains for miners”. This misunderstanding follows from the reasonable thought that if we have to throw blocks in the garbage then whoever mined this block is in the loss.

However, that is not quite the case. The difficulty adjustment algorithm only controls the issuance rate of non-orphan blocks. There is no other way: since difficulty has to be in consensus, the difficulty of each block can only depend on the chain leading from this block to genesis.

In particular, if we have, say, 20% orphan rates, then mining blocks will be 20% easier, increasing the block rates to compensate. Yes, one fifth of the blocks you make will go to the trash, but you will make 1.25 times more blocks, giving you the same rate of non-orphan blocks.

You might be tempted to think that a 20% orphan rate implies only 80% of the hash rate you see on the blockchain goes towards non-orphan blocks. So if the difficulty requires one tera hash per second to see a block every ten minutes, then an adversary will only need 800 giga hash to 51% attack the network. Again, this is not the case, the hash rate read off the difficulty only takes non-orphan blocks into account. This (combined with the fact that nodes do not broadcast blocks they see as orphans) makes measuring orphan rates in practice extremely difficult (especially if we consider that old orphans can be forged for cheap).

That being said, there are adverse consequences to high orphan rates (besides the wasted work): they introduce noise that increases confirmation times, and increase the advantage for miners with a better internet connection.