---
OA_place: repository
OA_type: green
_id: '21134'
abstract:
- lang: eng
text: "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.\r\nProofs 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.\r\nThe 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.\r\n\r\nProofs 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.\r\n\r\nConcretely, we consider a security game in which
the honest parties at any point control 0 > 1\r\n times more space than the adversary.
The adversary can change the honest space by a factor 1+- E with every block (dynamic
availability), and “replotting” the space (which allows answering two challenges
using the same space) takes as much time as p blocks.\r\nWe prove that no matter
what chain selection rule is used, in this game the adversary can create a fork
of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe
also provide an upper bound that matches the lower bound up to a factor o. There
exists a chain selection rule (albeit a very strange one) which in the above game
requires forks of length at least o . p/E\r\nOur results show the necessity of
additional assumptions to create a secure PoSpace based longest-chain blockchain.
The Chia network in addition to PoSpace uses a verifiable delay function. Our
bounds show that an additional primitive like that is necessary."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) 10.55776/F85.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain
blockchains. In: 29th International Conference on Financial Cryptography and
Data Security. Vol 15752. Springer Nature; 2026:127-142. doi:10.1007/978-3-032-07035-7_8'
apa: 'Baig, M. A., & Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space
based longest-chain blockchains. In 29th International Conference on Financial
Cryptography and Data Security (Vol. 15752, pp. 127–142). Miyakojima, Japan:
Springer Nature. https://doi.org/10.1007/978-3-032-07035-7_8'
chicago: Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” In 29th International Conference on Financial
Cryptography and Data Security, 15752:127–42. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-07035-7_8.
ieee: M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based
longest-chain blockchains,” in 29th International Conference on Financial Cryptography
and Data Security, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142.
ista: 'Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based
longest-chain blockchains. 29th International Conference on Financial Cryptography
and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752,
127–142.'
mla: Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” 29th International Conference on Financial
Cryptography and Data Security, vol. 15752, Springer Nature, 2026, pp. 127–42,
doi:10.1007/978-3-032-07035-7_8.
short: M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-02-01T23:01:43Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07035-7_8
external_id:
arxiv:
- '2505.14891'
fulldoi: https://doi.org/10.1007/978-3-032-07035-7_8
intvolume: ' 15752'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.14891
month: '01'
oa: 1
oa_version: Preprint
page: 127-142
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070340'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: On the (in)security of Proofs-of-space based longest-chain blockchains
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15752
year: '2026'
...