High-Throughput Blockchain Consensus under Realistic Network Assumptions

In blockchain consensus, messages are validated based on proof-of-X, where X stands for some underlying resource such as work (PoW) or stake (PoS). Protocol message validation via such a “resource lottery” allows the following adverse behaviors that are seemingly antithetical to high throughput operation: (I) Protocol bursts, occur when large volumes of valid protocol messages are withheld by the adversary and released altogether with the intention of emaciating the bandwidth available to honest parties. (II) Message replays and equivocations take place when the adversary exploits PoX outcomes and hiding behind the pseudonymity of the network spams honest protocol participants with a message rate much higher than its designated PoX rate, crippling in this way the ability of honest parties to communicate effectively. Reconciling these shortcomings with high bandwidth blockchain operation has so far been unsuccessful: prior work either shies away from utilizing all available bandwidth or if it does, it introduces unrealistic network assumptions that “abstract away” the above adversarial behaviors.

We put forward Leios, a blockchain protocol overlay combining a number of techniques that may be of independent interest and reconciling the above shortcomings. Leios transforms any underlying low-throughput base protocol to a high-throughput blockchain achieving (1 − 𝛿) of the optimal capacity for any constant 𝛿 > 0. Furthermore, it impacts latency asymptotically only by a related constant hence if the underlying protocol has constant time expected settlement, the Leios overlay retains this property. Combining Leios with any underlying permissionless protocol, either in the PoS or PoW setting, we obtain for the first time a near-optimal throughput permissionless “layer-1” blockchain protocol that is proven secure under realistic network assumptions.