Paper 2021/184

Communication-Efficient BFT Protocols Using Small Trusted Hardware to Tolerate Minority Corruption

Sravya Yandamuri
Ittai Abraham
Kartik Nayak
Michael K. Reiter

Agreement protocols for partially synchronous or asynchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.

Available format(s)
Publication info
consensus protocols blockchains trusted hardware communication complexity
Contact author(s)
sravya yandamuri @ duke edu
iabraham @ vmware com
kartik @ cs duke edu
Michael reiter @ duke edu
2022-05-24: last of 2 revisions
2021-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sravya Yandamuri and Ittai Abraham and Kartik Nayak and Michael K.  Reiter},
      title = {Communication-Efficient BFT Protocols Using Small Trusted Hardware to Tolerate Minority Corruption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/184},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.