  Large scale cryptocurrencies require the participation of millions of
participants and support economic activity of billions of dollars, which has
led to new lines of work in binary Byzantine Agreement (BBA) and consensus. The
new work aims to achieve communication-efficiency---given such a large $n$, not
everyone can speak during the protocol. Several protocols have achieved
consensus with communication-efficiency, even under an adaptive adversary, but
they require additional strong assumptions---proof-of-work, memory-erasure,
etc. All of these protocols use multicast: every honest replica multicasts
messages to all other replicas. Under this model, we provide a new
communication-efficient consensus protocol using Verifiable Delay Functions
(VDFs) that is secure against adaptive adversaries and does not require the
same strong assumptions present in other protocols.
  A natural question is whether we can extend the synchronous protocols to the
partially synchronous setting---in this work, we show that using multicast, we
cannot. Furthermore, we cannot achieve always safe communication-efficient
protocols (that maintain safety with probability 1) even in the synchronous
setting against a static adversary when honest replicas only choose to
multicast its messages. Considering these impossibility results, we describe a
new communication-efficient BBA protocol in a modified partially synchronous
network model which is secure against adaptive adversaries with high
probability.
