On the (in)security of Proofs-of-Space based Longest-Chain Blockchains

• URL: http://arxiv.org/abs/2505.14891v1
• Date: Tue, 20 May 2025 20:35:00 GMT
• Title: On the (in)security of Proofs-of-Space based Longest-Chain Blockchains
• Authors: Mirza Ahad Baig, Krzysztof Pietrzak,
• Abstract summary: We consider a security game in which the honest parties at any point control $phi>1$ times more space than the adversary.<n>We prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length $phi2cdot rho / varepsilon$ that will be picked as the winner by the chain selection rule.
• Score: 1.9934605058107087
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under ``resource variability'', i.e., if the total hashing power varies greatly over time. Proofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a ``longest-chain'' blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound. Concretely, we consider a security game in which the honest parties at any point control $\phi>1$ times more space than the adversary. The adversary can change the honest space by a factor $1\pm \varepsilon$ with every block (dynamic availability), and ``replotting'' the space takes as much time as $\rho$ blocks. We prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length $\phi^2\cdot \rho / \varepsilon$ that will be picked as the winner by the chain selection rule. We also provide an upper bound that matches the lower bound up to a factor $\phi$. There exists a chain selection rule which in the above game requires forks of length at least $\phi\cdot \rho / \varepsilon$.

Related papers

• Nakamoto Consensus from Multiple Resources [1.773699516795303]
  We ask what weight functions Gamma(S,V,W) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.<n>We classify such functions in an idealized "continuous" model: Gamma(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the timed resources V and W.
  arXiv  Detail & Related papers  (2025-08-02T17:36:50Z)
• Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game [48.93355782581436]
  We consider the problem of a game theorist analyzing a game that uses cryptographic protocols.<n>We propose a new solution concept: the pseudo-Nash equilibrium.
  arXiv  Detail & Related papers  (2025-06-27T10:21:28Z)
• A Fully Local Last-Generated Rule in a Blockchain [2.9281463284266973]
  An effective method for suppressing intentional forks in a blockchain is the last-generated rule. This rule helps invalidate blocks that are withheld by adversaries for a certain period. Existing last-generated rules face an issue in that their applications to the system are not fully localized.
  arXiv  Detail & Related papers  (2024-11-13T08:47:40Z)
• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols.<n>Our measurements from the Aptos mainnet show that the optimistic approach reduces latency overhead by 71%.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• Tie-Breaking Rule Based on Partial Proof of Work in a Blockchain [2.9281463284266973]
  We propose another countermeasure that can be easily applied to existing proof of work blockchain systems. By using the characteristic of partial proof of work, the proposed method enables miners to choose the last-generated block in a chain tie. Only weak synchrony, which is already met by existing systems such as Bitcoin, is required for effective functioning.
  arXiv  Detail & Related papers  (2024-03-22T08:24:12Z)
• ADESS: A Proof-of-Work Protocol to Deter Double-Spend Attacks [0.0]
  A principal vulnerability of a proof-of-work ("PoW") blockchain is that an attacker can re-write the history of transactions. We propose a modification to PoW protocols, called ADESS, that contains two novel features.
  arXiv  Detail & Related papers  (2023-09-25T21:50:23Z)
• Refined Bitcoin Security-Latency Under Network Delay [35.16231062731263]
  We study how secure a block is after it becomes $k$-deep in the chain. We analyze the race between adversarial and honest chains in three different phases. We find the probability distribution of the growth of the adversarial chains under models similar to those in [Guo, Ren; AFT 2022] when a target block becomes $k$-deep in the chain.
  arXiv  Detail & Related papers  (2022-12-02T18:54:30Z)
• Bitcoin-Enhanced Proof-of-Stake Security: Possibilities and Impossibilities [45.90740335615872]
  Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners.<n>Proof-of-Stake chains are energy-efficient, have fast finality but face several security issues.<n>We show that these security issues are inherent in any PoS chain without an external trusted source.<n>We propose a new protocol, Babylon, where an off-the-shelf PoS protocol checkpoints onto Bitcoin to resolve these issues.
  arXiv  Detail & Related papers  (2022-07-18T06:01:25Z)
• Token Spammers, Rug Pulls, and SniperBots: An Analysis of the Ecosystem of Tokens in Ethereum and in the Binance Smart Chain (BNB) [50.888293380932616]
  We study the ecosystem of the tokens and liquidity pools. We find that about 60% of tokens are active for less than one day. We estimate that 1-day rug pulls generated $240 million in profits.
  arXiv  Detail & Related papers  (2022-06-16T14:20:19Z)
• Quantum-resistance in blockchain networks [46.63333997460008]
  This paper describes the work carried out by the Inter-American Development Bank, the IDB Lab, LACChain, Quantum Computing (CQC), and Tecnologico de Monterrey to identify and eliminate quantum threats in blockchain networks. The advent of quantum computing threatens internet protocols and blockchain networks because they utilize non-quantum resistant cryptographic algorithms.
  arXiv  Detail & Related papers  (2021-06-11T23:39:25Z)
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security [67.06003361150228]
  A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity.
  arXiv  Detail & Related papers  (2020-12-30T18:03:56Z)
• Controlled quantum state transfer in $XX$ spin chains at the Quantum Speed Limit [62.997667081978825]
  In homogeneous chains it implies that taking information from one extreme of the chain to the other will take a time $O(N/2)$, where $N$ is the chain length. We design control pulses that achieve near perfect population transfer between the extremes of the chain at times on the order of $N/2$, or larger.
  arXiv  Detail & Related papers  (2020-05-15T23:10:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.