Finding blockchain consensus bugs with fork-aware differential testing

Abstract

Designing a good consensus algorithm is of the utmost importance in blockchains, as is its implementation and operation. In a world where multiple independently-developed implementations of a single consensus algorithm coexist in a blockchain system, however, it is difficult to ensure that all clients have the identical implementation of the same consensus algorithm. In this paper, we present a coverage-guided differential testing framework for finding consensus bugs—that is, discrepancies between multiple implementations of a consensus algorithm—in general proof-of-work (PoW) or proof-of-stake (PoS) based blockchain systems. Our tool, which we call Forky, is able to discover a broader range of consensus bugs than existing tools. Utilizing novel fork-aware test cases and bug oracle for differential fuzzing, Forky effectively tests clients with arbitrary temporary forks and their resolutions. We use Forky to test 30 Bitcoin implementations (of all four major clients: Bitcoin Core, Bitcoin Knots, bcoin, and btcd) and discover two new consensus bugs that require temporary forks during testing, both of which are currently exploitable in the live network. We open source Forky in the hopes that it will be widely adopted to secure other PoW/PoS blockchains.