Simpler Security proof for Nakamoto Consensus

Four years ago (time flies!), I made a post on a simple security proof for Nakamoto consensus. While the proof intuition, as outlined in that post, is still reasonably simple, the actual proof has become quite delicate and crafty over the years. What happened was that some colleagues – Chen Feng at UBC and Dongning Guo at Northwestern – identified very subtle flaws in the proof, and clever mathematical maneuvers had to be put in to fix them.

The good news is that my coauthor Dongning Guo and I have since come up with an even simpler proof! Moreover, the new proof is almost concretely tight for Bitcoin parameters. (For more aggressive parameters, more advanced techniques are needed to tighten the result.) The paper recently won the inaugural Chaincode Labs Bitcoin Research Prize. It gives me an excuse to write this long overdue follow-up post on the simpler and tighter proof. I will give a high-level overview without defining a formal model. But if you are interested, the formal model is the same one as in the previous post.

I will start by highlighting the two main challenges in the line of work on Nakamoto consensus security proofs. The first challenge is that the proof must account for all possible attack strategies under a model, including strategies that we may have never thought about. The second challenge is the network delays that make different honest nodes have different views. In our new proof, we managed to find very simple ways to overcome both challenges.

Let us first ignore the second challenge and consider a network with zero delay. With zero delay, we can prove that a fairly simple attack strategy, private mining with lead, is an optimal attack strategy. Here is a short description of this strategy. The attacker first tries to mine some private blocks on top of the public main chain. This part is essentially selfish mining. If the public chain catches up, the attacker releases its private chain to get those block rewards and restart private mining at the new tip of the chain. Once the target transaction shows up on the public chain, the attacker will double down and mine on its private chain forever, i.e., enter a mining race with the public chain. To connect the dots, the few private blocks the attacker got in the selfish mining part serve as a head start (called lead in the paper) for this race. The attacker wins if its private chain is ever longer than the public chain after the target transaction is finalized ($k$ blocks deep).

Rigorously proving this strategy optimal is nontrivial and the hardest part of our paper. (The Everything is a race paper first observed this optimality but only proved it in a special case.) I encourage you to check out our paper. For some quick intuition, when there is zero delay, the best an attacker can hope for is that every block it mines takes it one step closer to victory and that every block mined by some honest node sets it back one step. The private mining strategy achieves precisely that. I will also note that the Bitcoin whitepaper calculated confirmation depths assuming, without proof, that a variant of this strategy is optimal.

The optimality of the above strategy is the answer to the first challenge! Any other strategy, no matter how sophisticated, is at most as good as this one. Thus, we no longer have to worry about all possible attack strategies or some crazy strategy that no one has ever thought about. We just need to calculate the success probability of this one concrete attack, a much easier task. Obviously, it is the following:

Just kidding… Let us do the calculation. Let $k$ be the confirmation depth. Suppose the target transaction shows up in the network at time $t$. Let $L$ be the lead of the attacker at time $t$. The attacker wins only in three cases.

1. $L > k$. The attacker can now just relax, wait for the public chain to finalize the target transaction, and then release its private chain to violate the safety of the target transaction.
2. $L \leq k$ and the attacker’s private chain reaches $k$-deep first. Like in the first case, the attacker wins by waiting for finalization and then releasing its private chain.
3. $L \leq k$ and the public chain reaches $k$-deep first. In order to win, the attacker’s private chain must eventually catch up with the public chain.

The previous formula may look long, but it is simply a breakdown of these three cases. Below is a brief explanation. I encourage you to read the paper for details.

• $P_1(\cdot;p)$ and $\bar F_1(\cdot;p)$ are the probability mass function and (upper) cumulative distribution function of a geometric random variable with parameter $p$. The lead follows a geometric distribution where $p$ is the ratio of honest mining power.
• $P_2(\cdot;n,p)$ and $\bar F_2(\cdot;n,p)$ are the probability mass function and (upper) cumulative distribution function of a binomial random variable with parameter $(n,p)$. The corresponding terms in the formula capture the probabilities that the attacker/public chain reaches $k$ first, respectively, given a starting lead of $i$.
• The probability of catching up also follows a geometric distribution and is captured by the last term.

We now have a concrete (not just asymptotic) formula for the safety violation probability under the $k$-deep confirmation rule, assuming zero network delay. The formula involves standard distribution functions and is easy to calculate numerically for any $k$.

Now, we turn to the second challenge: network delays. Let us first ask: what is the defining feature of zero delay that enables the optimality result above? It is that all the blocks mined by honest nodes (let us call them honest blocks for short) are “aware of” each other, so they always form a chain. With network delay, this is no longer true. Honest blocks mined around the same time are unaware of each other and will fork. But here comes the key observation of our paper. If an honest block “tailgates” (mined too closely to) a previous block, we simply give it to the attacker for free; in other words, we pretend it is mined by the attacker. Now, all the remaining honest blocks are mined reasonably far apart in time and are aware of each other.

This simple trick of giving away some blocks solves the second challenge by reducing the positive-delay case to the zero-delay case! The success probability of any attack in a network with delay is upper bounded by the success probability of the private mining with lead attack where the attacker’s mining power is boosted by the “tailgating” honest blocks. Concretely, the result is still given by the same formula. But the honest mining ratio $p$ to be plugged in needs to be multiplied by a “discount” factor to account for the blocks we give away. The discount factor, which is the probability that a block tailgates, is $e^{-\lambda\Delta}$ where $\lambda$ is the total mining rate (1 block per 10 minutes) and $\Delta$ is the upper bound on the network delay. The previous post has an explanation for this. Because Bitcoin’s expected block internal (10 minutes) is much longer than the block propagation delay (a few seconds), the percentage of tailgating blocks is small, and the final result is almost tight.

That’s pretty much the entire proof. I hope you find it simple and like its simplicity. Even this simple proof took Dongning and me nine months to finish. We got stuck many times. We found and fixed many subtle flaws. These (and previous) flaws get exposed only thanks to the simplicity. So simplicity helps rigor. Simplicity also helps produce tight and practical results. But even without pragmatic benefits, simplicity is immensely valuable:

It can scarcely be denied that the supreme goal of all theory is to make the irreducible basic elements as simple and as few as possible without having to surrender the adequate representation of a single datum of experience. – Albert Einstein, 1933.