Paper 2024/1830

A Tight Analysis of GHOST Consistency

Abstract

The GHOST protocol was proposed in 2015 as an alternative to the Nakamoto consensus mechanism that underlies Bitcoin. In con- trast to the Nakamoto longest-chain rule, the GHOST rule justifies selec- tion of a chain by maximizing subtree weights rather than path lengths. This chain selection rule has been adopted by a variety of consensus protocols and is featured in the currently deployed protocol supporting Ethereum. We establish an exact characterization of the consistency region of the GHOSTprotocol,identifyingtherelationshipbetweennetworkdelay,the rate of honest block production, and the rate of adversarial block pro- duction that guarantees that the protocol reaches consensus. In contrast to the Nakamoto consensus protocol, we find that the region depends on the convention used by the protocol for tiebreaking: we establish tight results for both adversarial tiebreaking, in which ties are broken adver- sarially in order to frustrate consensus, and deterministic tiebreaking, in which ties between pairs of blocks are broken consistently throughout an execution. We provide explicit attacks for both conventions which stall consensus outside of the consistency region. Our results conclude that the consistency region of GHOST can be strictly improved by incorporating a tiebreaking mechanism; in either case, however, the final region of consistency is inferior to the region of longest-chain rule consensus. On the other hand, in the region where the GHOST protocol is secure it provides superior defense of settled blocks against periods of adversarial majority than the longest-chain rule and, in this sense, is preferable from the perspective of self-healing.