Linear View Change in Optimistically Fast BFT

To be competitive with centralized applications, consensus protocols in blockchains must provide minimal latency while being able to scale to thousands of participants in order to preserve a high level of decentralization. A common way to minimize latency is to augment a consensus protocol with a fast track, which ensures that a decision is reached in just a couple of message delays in favorable conditions. However, it is a challenging task to preserve safety and good performance when these favorable conditions do not hold. To the best of our knowledge, all existing Byzantine fault-tolerant consensus protocols with fast tracks require view change protocols with quadratic authenticator complexity. In this paper, we provide the first solution to Byzantine consensus with fast track with a linear view change. The protocol incurs no asymptotic overhead over the baseline while reducing the latency in favorable conditions by a factor of 2. Our construction is based on a novel type of cryptographic proofs, which we call Proofs of Exclusivity (or PoE for short), which may be of independent interest. While our protocol for constructing a PoE comes at no extra costs in latency or asymptotic complexities, it does require some extra computation. To make sure that it does not impair the overall performance, we also show how to apply accountability and proofs of misbehavior in order to reduce to zero the overhead incurred by the computation of a PoE. More precisely, our mechanism guarantees that whenever this overhead is not zero, then automatically honest participants obtain a publicly verifiable proof that a well-identified malicious participant openly misbehaved. In this case, the overhead of computing a few extra threshold signatures for the Proof of Exclusivity can be seen as a relatively small price to get rid of a malicious participant.