On the (In)Security of Proofs-of-Space Based Longest-Chain Blockchains

Table of Contents

1. Introduction

This work presents a fundamental impossibility result for constructing secure longest-chain blockchains based solely on Proof-of-Space (PoSpace) under conditions of dynamic availability. It formally quantifies the vulnerability, showing that an adversary can always create a winning fork of bounded length, necessitating additional cryptographic assumptions like Verifiable Delay Functions (VDFs) for security.

2. Background & Problem Statement

2.1. Nakamoto Consensus & Proof-of-Work

Bitcoin's security relies on Proof-of-Work (PoW) and the longest-chain rule. It guarantees security if honest parties control a majority of hashing power, even under variable total power ("resource variability").

2.2. Proof-of-Space as a Sustainable Alternative

PoSpace has been proposed as an energy-efficient alternative to PoW, where miners dedicate storage space rather than computation. However, its security in a dynamic, permissionless setting was an open problem.

2.3. The Security Challenge: Dynamic Availability

The core challenge is "dynamic availability": honest space can fluctuate ($1 \pm \varepsilon$ factor per block), and adversaries can "replot" their space (reuse it for multiple challenges) with a time cost equivalent to $\rho$ blocks.

3. Formal Security Model & Impossibility Result

3.1. Game Definition & Adversarial Capabilities

The security game assumes honest parties control $\phi > 1$ times more space than the adversary at any point. The adversary can:

• Vary honest space by factor $1 \pm \varepsilon$ per block.
• Replot space with time cost $\rho$ blocks.

3.2. The Lower Bound Theorem

Theorem (Lower Bound): For any chain selection rule, in this game, an adversary can create a fork of length $L$ that will be accepted, where:

$L \leq \phi^2 \cdot \rho / \varepsilon$

This is an impossibility result: security cannot be guaranteed against forks shorter than this bound.

3.3. The (Strange) Upper Bound & Matching Rule

Theorem (Upper Bound): There exists a (highly unnatural) chain selection rule that requires the adversary to create a fork of length at least:

$L \geq \phi \cdot \rho / \varepsilon$

This shows the lower bound is tight up to a factor of $\phi$.

4. Technical Details & Mathematical Formulation

The impossibility stems from the adversary's ability to leverage the time vs. space asymmetry. While honest space is tied up for the duration of a challenge, the adversary, by concentrating a fixed amount of space and replotting, can simulate more "virtual" space over time. The key inequality driving the bound relates the adversary's effective space-time resource $A_{eff}$, the honest space-time resource $H_{eff}$, and the fork length $L$:

$A_{eff} \approx \frac{L}{\rho} \cdot A \quad \text{and} \quad H_{eff} \approx \phi \cdot A \cdot \frac{L}{\varepsilon^{-1}}$

Manipulating these under the game constraints leads to the final bound $L \approx \phi^2 \rho / \varepsilon$.

5. Results & Implications

5.1. Core Security Bound

5.2. Necessity of Additional Primitives (e.g., VDFs)

The result proves that PoSpace alone is insufficient. Protocols like Chia correctly incorporate Verifiable Delay Functions (VDFs) to add a mandatory, non-parallelizable time delay between blocks, mitigating the replotting attack vector. This validates Chia's architectural choice from a theoretical standpoint.

5.3. Case Study: The Chia Network

Chia uses PoSpace + VDFs ("Proofs of Time"). The VDF ensures a minimum wall-clock time between blocks, making the $\rho$ parameter effectively very large for an adversary trying to create an alternative chain, thereby raising the practical fork length bound to infeasible levels.

6. Analysis Framework & Example Case

Framework for Evaluating PoX Longest-Chain Protocols:

1. Resource Identification: Define the scarce resource (Space, Time, Compute).
2. Dynamic Model: Model honest resource fluctuation ($\varepsilon$) and adversarial resource manipulation (e.g., replotting cost $\rho$).
3. Attack Vector Analysis: Identify how an adversary can translate one resource into another (space into time via replotting).
4. Bound Derivation: Formulate an inequality between adversarial and honest resource-time product for a given fork length $L$.
5. Primitive Gap Analysis: Determine if the bound is practically secure. If not, identify necessary additional primitives (VDF, PoW, stake).

Example Application: Evaluate a hypothetical "Proof-of-Storage" chain. Parameterize storage reallocation speed ($\rho$) and stake volatility ($\varepsilon$). The framework would quickly show susceptibility to a similar "re-allocation" attack unless a time-lock (VDF) or slashing mechanism is added.

7. Future Applications & Research Directions

• Hybrid Consensus Models: Rigorous design of PoSpace+PoS or PoSpace+PoW hybrids to achieve security without excessive overhead.
• Enhanced VDF Designs: Research into more efficient or decentralized VDF constructions to reduce the overhead of adding time guarantees.
• Formal Verification: Applying this model to other "proof-of-X" paradigms (Proof-of-Useful-Work, Proof-of-Physical-Work) to pre-empt security flaws.
• Post-Quantum Considerations: Exploring PoSpace-based designs that remain secure in a post-quantum computing era, where VDFs based on sequential squaring may be vulnerable.

8. References

1. Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System.
2. Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. (2015). Proofs of Space. CRYPTO 2015.
3. Cohen, B., & Pietrzak, K. (2018). The Chia Network Blockchain. https://www.chia.net/assets/ChiaGreenPaper.pdf
4. Boneh, D., Bonneau, J., Bünz, B., & Fisch, B. (2018). Verifiable Delay Functions. CRYPTO 2018.
5. Garay, J., Kiayias, A., & Leonardos, N. (2015). The Bitcoin Backbone Protocol: Analysis and Applications. EUROCRYPT 2015.
6. Pass, R., & Shi, E. (2017). FruitChains: A Fair Blockchain. PODC 2017.

9. Expert Analysis & Critical Commentary

Core Insight

This paper delivers a devastatingly elegant kill shot to the naive dream of a "green Bitcoin" built solely on Proof-of-Space. It's not just an attack on a specific protocol; it's a fundamental thermodynamic argument about the relationship between space, time, and security in decentralized consensus. The core insight is that space, unlike compute in PoW, is not inherently "burned". An adversary can recycle it. This recyclability, under dynamic participation, creates a fatal arbitrage loop that any longest-chain rule cannot defend against. It formally explains why projects like Chia had to bolt on a Verifiable Delay Function (VDF)—it wasn't an optional optimization but a theoretical necessity.

Logical Flow

The authors' logic is impeccable and follows a classic impossibility proof structure: 1) Define a realistic adversarial model ($\phi$, $\varepsilon$, $\rho$) that captures the real-world constraints of storage (replotting time) and network churn. 2) Show that within this model, for any conceivable rule to choose between chains, an adversary with less space can always outpace honest nodes over a sufficiently long, but bounded, fork. 3) The bound $L \leq \phi^2 \rho / \varepsilon$ is the smoking gun. It quantifies the insecurity. The follow-up showing a near-matching upper bound with a "strange" rule is the final nail, proving the bound is tight and the vulnerability is intrinsic to the resource, not the rule design.

Strengths & Flaws

Strengths: The model's parameters ($\rho$ for replotting, $\varepsilon$ for fluctuation) are brilliantly chosen, capturing the essential physics of the problem. The result is clean, general, and immediately actionable. It elevates the discussion from "is this protocol secure?" to "what is the minimum extra assumption needed for security?".

Flaws/Limitations: The model assumes a passive honest majority that doesn't adapt its strategy based on detected forks—a standard but sometimes limiting assumption in longest-chain analysis. More importantly, while it proves the necessity of an additive primitive like a VDF, it doesn't quantify the sufficient parameters for that VDF (how much delay is enough?). This leaves a gap between theory and practice. Furthermore, the "strange" chain selection rule that nearly matches the bound is a cryptographic curiosity but has no practical utility, highlighting the depth of the problem.

Actionable Insights

For protocol designers: Stop trying to build pure PoSpace longest-chain protocols. This paper is your formal cease-and-desist notice. The viable path forward is exclusively through hybrids.

1. Mandatory Time Delay (VDF Path): Follow Chia's lead. Integrate a VDF to make $\rho$ effectively astronomical for an attacker, pushing the fork length bound beyond feasibility. Research focus should be on making VDFs more efficient and decentralized.
2. Explore Non-Longest-Chain Paradigms: Consider alternative consensus families like Proof-of-Stake (PoS) with finality gadgets (e.g., Casper FFG) or committee-based BFT protocols. These may integrate PoSpace differently, potentially avoiding this attack vector altogether. The work by the Ethereum Foundation on combining VDFs with PoS for randomness (RANDAO+VDF) shows the broader applicability of these primitives.
3. Parameter Rigor: If building a hybrid, use this paper's framework. Explicitly model your adversary's space-time trade-off, define your network's $\varepsilon$, and use the derived bound to stress-test your design. This isn't just academic; it's your security blueprint.

In conclusion, Baig and Pietrzak haven't just solved an open problem; they've drawn a bright red line in the sand of consensus theory. They've moved the field from hopeful engineering to rigorous physics, defining what's impossible and thereby clearly illuminating the narrow path to what might be possible. This is foundational work that will save countless future projects from dead-end architectures.