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.
블록체인에서 우수한 합의 알고리즘을 설계하는 것과 마찬가지로 이의 구현 및 운영은 굉장히 중요한 요소이다. 그러나 블록체인 시스템에서 독립적으로 개발된 여러 개의 합의 알고리즘 구현이 공존하는 현재, 같은 네트워크의 모든 클라이언트가 동일한 합의 알고리즘 구현을 가짐을 보장하기는 어렵다. 본 논문에서는 작업 증명 또는 지분 증명 기반 블록체인 시스템에서 합의 버그, 즉 합의 알고리즘의 여러 구현 간의 불일치를 찾기 위한 커버리지 유도 차등 테스트를 제시하였다. Forky를 통해 기존 연구에서 찾지 못한 합의 버그를 발견 할 수 있었다. Forky는 차등 퍼징을 위한 분기 인식을 이용해 임의의 임시 분기를 만들어 클라이언트가 이를 해결하는 과정을 효과적으로 테스트한다. 제안한 Forky로 4개의 주요 비트코인 구현체 중 30개의 버전을 테스트하였다. 그 결과 현재 네트워크에서 공격 가능한 분기 인식 차등 퍼징 만으로 찾을 수 있는 두 가지 새로운 합의 버그를 발견하였다.
