Paradigm

Goldfish: A Provably Secure Replacement for LMD GHOST in PoS Ethereum

Sep 09, 2022 | Francesco D’Amato, joachimneu, Ertem Nusret Tas, David Tse

The Merge: From Proof-of-Work to Proof-of-Stake

The upcoming transition of Ethereum from proof-of-work (PoW) to proof-of-stake (PoS) is the culmination of years of research and development. While PoS brings many potential advantages, it also means Ethereum is switching away from Satoshi Nakamoto’s longest-chain protocol---certainly one of the simplest and most elegant consensus protocols, and one that has been battle-tested for decentralized blockchains.

A notoriously brittle component of Ethereum’s PoS consensus protocol has proven to be its “LMD GHOST” fork-choice rule, with multiple recent attacks and patches, and no proof of its security.

In a new preprint titled “No More Attacks on Proof-of-Stake Ethereum?”, we propose Goldfish, a provably secure drop-in replacement for PoS Ethereum’s LMD GHOST fork-choice rule. We view this as just a first step towards more rigorous protocol design and analysis, with the goal of hardening Ethereum security.

Ethereum’s Proof-of-Stake Protocol

Ethereum’s proof-of-stake (PoS) consensus protocol is considerably more complex than good ol’ PoW longest-chain. It is really a combination of two different consensus protocols: a "finality gadget" (called Casper FFG) that finalizes blocks after 6.4-minute-long epochs, and a "fork-choice rule" (called “latest message driven greedy heaviest observed sub-tree”, “LMD GHOST” for short) that governs the chain within each epoch. If you are curious “why?”, check out this talk. The two components interact in a non-trivial way with each other, here depicted in a block diagram:

Specifically, LMD GHOST guides the block production process, and operates on a time scale of slots of 12 seconds and with subsampled committees of validators. It can thus be thought of as in charge of weaker “short-term consensus” near the tip of the PoS Ethereum blockchain. Once short-term consensus on the transaction ledger has been reached, it is handed over to Casper FFG for additional hardening, which operates on a time scale of epochs comprising 32 slots = 6.4 minutes and involves the full validator set. Thus, Casper FFG is responsible for stronger “long-term consensus” providing finality and accountable safety.

Unfortunately, this complexity comes with challenges. In particular, the LMD GHOST component, and the interaction between LMD GHOST and Casper FFG, both have a history of whack-a-mole going back and forth between attacks and patches. The protocol currently set for adoption with the Merge has neither a publicly known attack, nor a formal security analysis/proof.

The lack of security proof is reason for concern, but not because a proof in a simplistic academic model would necessarily be perfectly indicative of real-world security. Rather, the fact that we cannot explain conclusively why this protocol is supposedly secure, even in a simplistic toy model, suggests that we don’t actually understand the protocols, or the full scope of their consequences and interactions.

Goldfish

In a recent preprint titled “No More Attacks on Proof-of-Stake Ethereum?”, we provide a drop-in replacement for PoS Ethereum’s LMD GHOST fork-choice rule. This protocol, called Goldfish, is similar to LMD GHOST (and thus would not require a massive overhaul of the current client implementations), but comes with a security proof.

To understand Goldfish better, let’s first zoom into how LMD GHOST roughly works:

Suppose the delay incurred by messages in our toy network model is at most a known value . In LMD GHOST, time proceeds in synchronized slots of time. For each slot, one proposer and a small committee of validators are randomly selected from the full validator set. At the beginning of each slot, the slot’s proposer runs the LMD GHOST fork-choice rule (with two modifications, “proposer boost” and “equivocation discounting,” that are patches in response to two earlier attacks) to determine a canonical blockchain tip and propose a new block.

Halfway into the slot, the slot’s committee members also determine a canonical blockchain tip using the same fork-choice rule, and cast a vote in favor of this tip. LMD GHOST does not specify a confirmation rule, but leaves it up to the user to decide which blocks of the blocktree have “enough” votes to be confident that they will not leave the canonical chain.

Goldfish follows this general structure closely, but introduces an additional phase for validators to synchronize their views on the vote counts, and to confirm blocks:

At the beginning of each slot, the slot’s proposer runs the simple GHOST fork-choice rule based on votes from the previous slot, to determine where to propose a block. One-third into the slot, the slot’s committee members use the same fork-choice rule based on votes from the previous slot and votes relayed by the proposer, to determine where to cast their vote. Finally, two-thirds into the slot, all validators run a clearly defined -deep confirmation rule.

Goldfish is based on two key techniques, vote buffering and vote expiry, to carefully synchronize honest validators’ views:

  • Vote buffering (also known as view merge) first appeared in Highway. In short, buffering of votes received from the network together with carefully-timed inclusion of these votes in each validator’s local view guarantees that in slots with an honest proposer, all honest validators vote in favor of the proposer’s proposal. This leads to reorg resilience: honest proposers’ proposals are guaranteed to remain in the canonical chain. Security (i.e., safety and liveness of the output ledger) ensues.
  • Vote expiry (also known as ephemeral votes) means that during each time slot only votes from the immediately preceding time slot affect the protocol’s behavior. (The alleged forgetfulness of its animal namesake gives the Goldfish protocol its name.) Vote expiry keeps the set of votes small that might affect short-term future actions of honest validators. Thus, only a few protocol messages need to be buffered and merged among honest validators’ views at any point in time. Vote expiry is thus a prerequisite for the efficiency/feasibility of vote buffering. Vote expiry is also crucial to support fluctuating levels of validator participation, and to support running the protocol among a smaller subsampled committee of voters per slot, rather than across the full validator set.

Finally, Goldfish’s confirmation rule confirms blocks if they are still on the canonical chain some time after their creation. Analysis shows that the resulting confirmation reversal probability decays exponentially in the delay between block production and block confirmation.

For more details on Goldfish and its security analysis, check out our preprint.

A Challenge for Goldfish: Asynchrony

Goldfish is simple enough to admit a rigorous security proof. And this analysis immediately bears fruit: Remember we assumed at the outset that the network delay in our toy model would be upper-bounded by . In the process of proving security, we were forced to make this and other assumptions explicit.

What happens if this bound is violated, i.e., if the network is temporarily asynchronous? We can trace the steps of our security argument, and see what breaks without the assumption. We see that if the actual network delay was longer than (i.e., 8 seconds in current PoS Ethereum), then Goldfish will not receive the decisive votes of slot in time to build on them in slot . The protocol could suffer from a reorg.

Such a reorg is bad; but at least thanks to the rigorous security argument, we have better insight into what conditions the security of our system critically depends upon, and why, and how. We can make more informed decisions to ensure that these prerequisites are met. For instance, while in current peer-to-peer networking protocols an adversary can probably induce some network delay more easily, there has been renewed interest recently (also due to networking related challenges with data availability sampling) in hardened peer-to-peer gossip protocols that reuse the consensus layer’s stake distribution to guide peer selection. Such protocols are more robust and could plausibly alleviate the delay problem. Furthermore, the finality/accountability gadget (which might eventually be further sped up with “single slot finality”) provides a backstop to any reorgs.

What Remains to be Done

We’ve proposed the Goldfish consensus protocol, which is designed to serve as a drop-in replacement for LMD GHOST in the PoS Ethereum beacon chain. In the preprint, we give a rigorous security analysis of Goldfish by itself, as well as in combination with a finality/accountability gadget (based on another consensus protocol, such as HotStuff). Other PoS Ethereum consensus security challenges remain, e.g., from the interactions of fork-choice and finality gadget, as detailed in Section 6.1 of our preprint. We look forward to seeing further consensus security improvements on these fronts for PoS Ethereum in the future!

If you are working on (or interested to work on) any of these directions, we would love to hear from you! You can reach us on Twitter at @fradamt, @jneu_net, @ErtemTas, and @dntse.

Acknowledgments: Special thanks to Aditya Asgaonkar, Carl Beekhuizen, Vitalik Buterin, Justin Drake, Dankrad Feist, Sreeram Kannan, Georgios Konstantopoulos, Barnabé Monnot, Dan Robinson, Danny Ryan, and Caspar Schwarz-Schilling for fruitful discussions, and to Achal Srinivasan for the beautiful illustrations.

Disclaimer: This post is for general information purposes only. It does not constitute investment advice or a recommendation or solicitation to buy or sell any investment and should not be used in the evaluation of the merits of making any investment decision. It should not be relied upon for accounting, legal or tax advice or investment recommendations. This post reflects the current opinions of the authors and is not made on behalf of Paradigm or its affiliates and does not necessarily reflect the opinions of Paradigm, its affiliates or individuals associated with Paradigm. The opinions reflected herein are subject to change without being updated.