Brief Announcement: Malicious Security Comes for Free in Consensus with Leaders

We consider consensus protocols in the model that is most commonly considered for use in state machine replication, as initiated by Dwork-Lynch-Stockmeyer, then by Castro-Liskov in 1999 with “PBFT”. Such protocols guarantee, assuming n players out of which t < n/3 are maliciously corrupted, that the honest players output the same valid value...