Dashing and Star: Byzantine Fault Tolerance with Weak Certificates

State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use regular certificates obtained from 2f + 1 (partial) signatures. We show that one can use weak certificates obtained from only f + 1 signatures to assist in designing more robust and more efficient BFT protocols. We design and implement two BFT systems: Dashing (a family of two HotStuff-style BFT protocols) and Star (a parallel BFT framework).