Abstract
This paper presents new protocols for Byzantine state machine replication and
Byzantine agreement in the synchronous and authenticated setting. The PBFT state
machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n=
3f+ 1 replicas. We improve the Byzantine fault tolerance to n= 2f+ 1 by utilizing the
synchrony assumption. Our protocol also solves synchronous authenticated Byzantine
agreement in fewer expected rounds than the best existing solution (Katz and Koo, 2006).