Paper 2024/200

A Better Proof-of-Work Fork Choice Rule

Abstract

We propose a modification to the fork choice rule of proof-of-work blockchains. Instead of choosing the heaviest chain, we choose the chain with the most intrinsic work. The intrinsic work of a block is roughly the number of zeroes at the front of its hash. This modification allows us to safely speed up the protocol, yielding a roughly 40% improvement in confirmation delay as compared to Bitcoin for adversaries close to 10%. Our modification is at the level of the proof-of-work inequality, and thus can be composed with any other methods to improve latency proposed in the literature (e.g., GHOST). We compile detailed simulation evidence from 3,000 years of simulated executions of our system across different parameters. We formally prove the security of our new protocol in the Bitcoin Backbone model. These proofs use a new technical tool, the real-valued Random Oracle which may be of independent interest.

Note: Version 2 of this paper (Nov 2024) completely revises the simulation methodology and corrects important mistakes in several of the theorem and lemma proofs. We also revised all the figures, from which we now draw different, more precise, conclusions, and rewrite the narrative of the paper.