Common Contracts

Accountable Byzantine Agreement

April 19th, 2021

• Filed
  April 19th, 2021

In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm. If among 𝑛 users 𝑡 < 𝑛 3 are malicious then it ensures consensus; otherwise (if 𝑡 𝑛 3), it eventually detects malicious users that cause disagree- ment. Polygraph is appealing for blockchain applications as it allows them to totally order blocks in a chain whenever possible, hence avoiding forks and double spending and, oth- erwise, to punish (e.g., via slashing) at least 𝑛 3 malicious users when a fork occurs. This problem is more difficult than perhaps it first appears. One could try identifying ma- licious senders by extending classic Byzantine consensus algorithms to piggyback signed messages. We show however that to achieve accountability the resulting algorithms would then need to exchange Ω(𝜅2 𝑛5) bits, where 𝜅 is the security parameter of the signature scheme. By contrast, Polygraph has communication complexity 𝑂(𝜅 𝑛4). Finally, we imple- ment Polygraph in a blockchain and compare it to