QScale: Probabilistic Chained Consensus for Moderate-Scale Systems

Existing distributed ledger protocols either incur a high communication complexity and are thus suited to systems with a small number of processes (e.g., PBFT), or rely on committee-sampling-based approaches that only work for a very large number of processes (e.g., Algorand). Neither of these lines of work is well-suited for moderate-scale distributed ledgers ranging from a few hundred to a thousand processes, which are common in production (e.g, Redbelly, Sui). The goal of this work is to design a distributed ledger with sub-linear communication complexity per process, sub-quadratic total communication complexity, and low latency for finalizing a block into the ledger, such that it can be used for moderate-scale systems. We propose QScale, a protocol in which every process incurs only $\widetilde{O}(\kappa \sqrt{n})$ communication complexity per-block in expectation, $\widetilde{O}(n\kappa)$ total communication complexity per-block in expectation, and a best-case latency of $O(\kappa)$ rounds while ensuring safety and liveness with overwhelming probability, with $\kappa$ being a small security parameter.