  There is surge of interest to the blockchain technology not only in the
scientific community but in the business community as well. Proof of Work (PoW)
and Byzantine Fault Tolerant (BFT) are the two main classes of consensus
protocols that are used in the blockchain consensus layer. PoW is highly
scalable but very slow with about 7 (transactions/second) performance. BFT
based protocols are highly efficient but their scalability are limited to only
tens of nodes. One of the main reasons for the BFT limitation is the quadratic
$O(n^2)$ communication complexity of BFT based protocols for $n$ nodes that
requires $n \times n$ broadcasting. In this paper, we present the {\em Musch}
protocol which is BFT based and provides communication complexity $O(f n + n)$
for $f$ failures and $n$ nodes, where $f < n/3$, without compromising the
latency. Hence, the performance adjusts to $f$ such that for constant $f$ the
communication complexity is linear. Musch achieves this by introducing the
notion of exponentially increasing windows of nodes to which complains are
reported, instead of broadcasting to all the nodes. To our knowledge, this is
the first BFT-based blockchain protocol which efficiently addresses
simultaneously the issues of communication complexity and latency under the
presence of failures.
