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

DOI10.1007/978-3-662-64331-0_6zbMATH Open1497.94083arXiv2010.08154OpenAlexW3208687847MaRDI QIDQ2147235FDOQ2147235

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

Publication date: 22 June 2022

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.

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

Mathematics Subject Classification ID

Cryptography (94A60)

Cites Work

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

Cited In (4)

• Account management in proof of stake ledgers
• Three attacks on proof-of-stake ethereum
• Cryptanalysis of algebraic verifiable delay functions
• On elapsed time consensus protocols

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)