High-Throughput Permissionless Blockchain Consensus under Realistic Network Assumptions

Throughput, i.e., the amount of payload data processed per unit of time, is a crucial measure of scalability for blockchain consensus mechanisms. This paper revisits the design of secure, high-throughput proof-of-stake (PoS) protocols in the permissionless setting. Existing high-throughput protocols are either analyzed using overly simplified network models or are designed for permissioned settings, with the task of adapting them to a permissionless environment while maintaining both scalability and adaptive security (which is essential in permissionless environments) remaining an open question.

Two particular challenges arise when designing high-throughput protocols in a permissionless setting: message bursts, where the adversary simultaneously releases a large volume of withheld protocol messages, and—in the PoS setting—message equivocations, where the adversary diffuses arbitrarily many versions of a protocol message. It is essential for the security of the ultimately deployed protocol that these issues be captured by the network model.

Therefore, this work first introduces a new, realistic network model based on the operation of realworld gossip networks—the standard means of diffusion in permissionless systems, which may involve many thousands of nodes. The model specifically addresses challenges such as message bursts and PoS equivocations and is also of independent interest.

The second and main contribution of this paper is Leios, a blockchain protocol that transforms any underlying low-throughput base protocol into a blockchain achieving a throughput corresponding to a (1−δ)-fraction of the network capacity—while affecting latency only by a related constant. In particular, if the underlying protocol has constant expected settlement time, this property is retained under the Leios overlay. Combining Leios with any permissionless protocol yields the first near-optimal throughput permissionless “layer-1” blockchain protocol proven secure under realistic network assumptions.