Common Contracts

Accountable Byzantine Agreement

Accountable Byzantine Agreement • April 28th, 2024

• Contract Type
  Accountable Byzantine Agreement
• Filed
  April 28th, 2024

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 how- ever that to achieve accountability the resulting algorithms would then need to exchange Ω(𝜅 · 𝑛2) more bits, where 𝜅 is the security parameter of the signature scheme. By con- trast, Polygraph has communication complexity 𝑂(𝜅 · 𝑛4). Finally, we implement Polygraph in a blockchain commit