  This work presents Information Theoretic HotStuff (IT-HS), a new optimally
resilient protocol for solving Byzantine Agreement in partial synchrony with
information theoretic security guarantees. In particular, IT-HS does not depend
on any PKI or common setup assumptions and is resilient to computationally
unbounded adversaries. IT-HS is based on the Primary-Backup view-based
paradigm. In IT-HS, in each view, and in each view change, each party sends
only a constant number of words to every other party. This yields an $O(n^2)$
word and message complexity in each view. In addition, IT-HS requires just
$O(1)$ persistent local storage and $O(n)$ transient local storage. Finally,
like all Primary-Backup view-based protocols in partial synchrony, after the
system becomes synchronous, all nonfaulty parties decide on a value in the
first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff,
IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as
quickly as the network allows them to do so, without regard for the known upper
bound on network delay. Our work improves in multiple dimensions upon the
information theoretic version of PBFT presented by Miguel Castro, and can be
seen as an information theoretic variant of the HotStuff paradigm.
