PoSAT: Proof-of-Work Availability and Unpredictability, without the Work
This addresses a key limitation in blockchain consensus for PoS systems, offering a solution that matches Proof-of-Work in availability and unpredictability, though it appears incremental as it builds on existing techniques like Verifiable Delay Functions and longest chain protocols.
The paper tackles the problem of achieving full dynamic availability in Proof-of-Stake (PoS) blockchains without additional assumptions, proposing PoSAT, a protocol that uses a Verifiable Delay Function and longest chain to provably achieve this property, with security analysis based on Nakamoto blocks and branching random walks.
An important feature of Proof-of-Work (PoW) blockchains is full dynamic availability, allowing miners to go online and offline while requiring only 50% of the online miners to be honest. Existing Proof-of-stake (PoS), Proof-of-Space and related protocols are able to achieve this property only partially, either putting the additional assumption that adversary nodes to be online from the beginning and no new adversary nodes come online afterwards, or use additional trust assumptions for newly joining nodes.We propose a new PoS protocol PoSAT which can provably achieve dynamic availability fully without any additional assumptions. The protocol is based on the longest chain and uses a Verifiable Delay Function for the block proposal lottery to provide an arrow of time. The security analysis of the protocol draws on the recently proposed technique of Nakamoto blocks as well as the theory of branching random walks. An additional feature of PoSAT is the complete unpredictability of who will get to propose a block next, even by the winner itself. This unpredictability is at the same level of PoW protocols, and is stronger than that of existing PoS protocols using Verifiable Random Functions.