Brief Announcement: Polygraph: Accountable Byzantine Agreement

Abstract

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among n users f < n/3 are malicious then it ensures consensus, otherwise it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchains as it allows to totally order blocks in a chain whenever possible, hence avoiding double spending and, otherwise, to punish at least n/3 malicious users when a fork occurs. This problem is more difficult than it first appears. Blockchains typically run in open networks whose delays are hard to predict, hence one cannot build upon synchronous techniques [Andreas Haeberlen et al., 2007; Vitalik Buterin and Virgil Griffith, 2019]. One may exploit cryptographic evidence of PBFT-like consensus [Miguel Castro and Barbara Liskov, 2002], however detecting equivocation would be insufficient. We show that it is impossible without extra logs of at least Ω(n) rounds [Pierre Civit et al., 2019]. Each round of Polygraph exchanges O(n²) messages.