PoSAT: proof-of-work availability and unpredictability, without the work

DOI10.1007/978-3-662-64331-0_6MaRDI QIDQ2147235zbMATH OpenOpenAlexFDO

Authors Soubhik Deb, Sreeram Kannan, David N. C. Tse

Publication date 22 June 2022

Full work available at URL https://arxiv.org/abs/2010.08154

Mathematics Subject Classification ID

Cryptography (94A60)

Abstract: 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.

Recommendations

• Multi-stage proof-of-works: properties and vulnerabilities
• Non-interactive proofs of proof-of-work
• Publicly verifiable proofs of sequential work
• Post-quantum verifiable random function from symmetric primitives in PoS blockchain
• scientific article; zbMATH DE number 7255566
• Proof-of-work certificates that can be efficiently computed in the cloud (invited talk)
• CArrency: an energy-efficient proof-of-work scheme for crypto-currencies

Cites work

• Analysis of the Blockchain Protocol in Asynchronous Networks
• Branching random walks. École d'Été de Probabilités de Saint-Flour XLII -- 2012
• Continuous verifiable delay functions
• Efficient verifiable delay functions
• FruitChains: a fair blockchain
• HotStuff
• Ledger combiners for fast settlement
• Ouroboros Praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain
• Ouroboros: a provably secure proof-of-stake blockchain protocol
• Public Key Cryptography - PKC 2005
• Publicly verifiable proofs of sequential work
• The Bitcoin Backbone Protocol: Analysis and Applications
• The Bitcoin backbone protocol with chains of variable difficulty
• The sleepy model of consensus
• Verifiable delay functions

Cited in

(6)

• Ouroboros Praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain
• Cryptanalysis of algebraic verifiable delay functions
• Three attacks on proof-of-stake ethereum
• Proof of availability and retrieval in a modular blockchain architecture
• Account management in proof of stake ledgers
• On elapsed time consensus protocols

This page was built for publication: PoSAT: proof-of-work availability and unpredictability, without the work

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2147235)