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

Krzysztof Pietrzak; Mirza Ahad Baig

REVIEW 2 major objections 4 minor 33 references

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

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read No proof-of-space longest-chain blockchain can be secure under dynamic availability without extra assumptions.

desk verdict The paper's core no-go theorem for PoSpace longest-chain blockchains is likely correct but the statement as printed is false due to the constant rule counterexample; with an added antisymmetry axiom and a fixed case split, it is a solid, publishable result. read the letter →

arxiv 2505.14891 v1 pith:IQBB5PBH submitted 2025-05-20 cs.CR

Mirza Ahad Baig , Krzysztof Pietrzak This is my paper · ORCID

classification cs.CR MSC 94A60

keywords proofsofspacelongest-chainblockchaindynamicavailabilityreplottingattackbootstrappingchainselectionruleimpossibilityresultforkinggame

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves an impossibility: a proof-of-space (PoSpace) longest-chain blockchain cannot be secure against double spending when the amount of honest space changes over time, unless the protocol adds some primitive that the space-profile model excludes. It formalizes a forking game where the honest parties always hold $\phi>1$ times more space than an adversary, honest space may drift by a factor $1\pm\varepsilon$ per block, and replotting one's storage takes $\rho$ blocks. The main theorem shows that for every chain selection rule that decides between two equal-length chains using only their space profiles, an adversary can create a fork of length about $\phi^2\cdot\rho/\varepsilon$ that the rule will prefer over the honest chain. The matching upper bound shows this is tight up to a factor $\phi$, so the impossibility is quantitative and essentially optimal. The practical upshot is that any secure PoSpace blockchain must rely on additional mechanisms such as proofs of time or registered identities.

What carries the argument

The load-bearing objects are the space profile $S(C)=(s(b_0),\ldots,s(b_\ell))$, the time-indexed amounts of honest space that each block claims to represent; bootstrapping, which lets an adversary with space $s$ extend a known chain prefix with blocks of weight at most $s$; and replotting, which lets the adversary spend $\rho$ blocks to rewrite its storage and emit a block that appears to have $k+1$ times its real space. The centerpiece of the proof is a pair of mirror tent profiles: one that stays flat at height $1$ and then rises/falls by a factor $(1+\varepsilon)$ to a peak of height $\phi$, and another that is the same tent moved in time so that the heights exchange roles. The adversary who holds $1/\phi$ of the honest space can fake the flat part by bootstrapping once the honest profile peaks above $1$, and can fake the tent by replotting within the $\rho\cdot\phi^2/\varepsilon$ time budget; the two fakes are constructed in Lemmas 3 and 4. The impossibility then follows by the excluded middle: whichever chain the rule prefers, the adversary in the opposite world presents the fork that wins.

What would settle it

A falsifying observation would be a concrete proof-of-space longest-chain protocol that is provably secure under dynamic availability with no added primitive, or a chain-selection rule using time or VDF outputs against which the $(\phi,\varepsilon,\rho)$ forking attack fails at the theorem's predicted length. Running the forking game with a real PoSpace instantiation and finding that the adversary needs a fork far shorter than $O(\rho\cdot\phi^2/\varepsilon)$ would likewise indicate the model misses a relevant constraint.

Watch

Extended reading notes

Core claim

The central claim (Theorem 1) is that in the $(\phi,\varepsilon,\rho,\Lambda)$-forking game, for every chain selection rule $\Lambda$ there is an adversary who wins with a fork of length $\ell = O(\rho\cdot\phi^2/\varepsilon)$ blocks (the theorem states an exact expression with ceilings and log terms). The adversary builds two complementary space profiles $S$ and $\widetilde{S}$, each shaped like a tent under the $(1\pm\varepsilon)$ growth constraint, and shows that each profile can be faked by an adversary holding only a $1/\phi$ fraction of the other profile's honest space, using bootstrapping to generate the flat part and replotting to generate the tent. Since $\Lambda$ must prefer one profile to the other, in the world where the other profile is the honest one the adversary's fork wins, and double spending follows. The paper also proves (Theorem 2) a chain selection rule $\Lambda_{\mathrm{tent}}$ that resists all forks shorter than about $\rho\cdot\phi/\varepsilon$, so the asymptotic bound is tight up to a factor $\phi$.

Load-bearing premise

The load-bearing premise is the model restriction that a chain selection rule decides between two equal-length chains using only their space profiles; if a protocol may also use clock time, verifiable-delay-function outputs, registration, or finality gadgets, the impossibility does not necessarily apply.

Editorial extensions

If this is right

Any PoSpace longest-chain blockchain claiming security under dynamic availability must include an extra signal beyond space profiles, such as a verifiable delay function, timed block arrival, or registered/periodically checked plots.
Slowing the difficulty-recalibration rate (making $\varepsilon$ small) does not prevent the attack; it only scales the required fork length as $1/\varepsilon$, so the adversary can always wait longer.
The quadratic dependence on $\phi$ means that increasing the honest-to-adversary space ratio by a factor of two lengthens the required fork by a factor of four, so naive space-multiplier defenses are inefficient.
Since the upper-bound rule $\Lambda_{\mathrm{tent}}$ matches the lower bound up to a factor $\phi$, no generic chain selection rule can be asymptotically better than the attack, and closing the $\phi$-gap is left as the paper's open problem.
The game's deterministic assumption—that each block perfectly reflects the space used to create it—makes the theorem a worst-case guarantee; in a probabilistic real chain the adversary's success can only become more likely.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: The mirror-profile construction is a template for costless-simulation insecurity: any resource metric that can be re-derived by replotting within a longest-chain protocol, not just disk space, should inherit a similar forking attack, so the theorem likely generalizes to other replot-table resources.
Extension: The result suggests that dynamic availability is not merely a quantitative security parameter but a binary switch: even with an honest-majority resource in every block, the ability to replot turns a minority into a winner, a failure mode distinct from the probabilistic 50%-attack of proof-of-work.
Extension: A concrete experimental check is to instantiate the function-inversion PoSpace (reference [2]) in a small test network, run the $(\phi,\varepsilon,\rho)$ forking game against a few chain selection rules, and verify that a winning fork appears at the predicted length; this would separate the impossibility's mathematical core from any modelling artifact.
Extension: The open $\phi$-gap between the lower and upper bounds suggests that real protocols might survive with slightly larger $\phi$ than the theorem states, but the attacker's ability to choose the better of two profiles means the true threshold is likely closer to the $\phi^2$ lower bound than to the $\phi$ upper bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Baig and Pietrzak prove something close to a no-go theorem for PoSpace longest-chain blockchains under dynamic availability, but the theorem as printed is false. The constant rule Λ≡0, which always prefers the first chain, is a perfectly valid chain selection rule by their Definition in Section 2.2, and no adversary can win the forking game against it. The final paragraph of A.1 also inverts the two games: with their convention 0 means the first chain wins and 1 means the second wins, the case split as written is wrong. Both flaws are repairable by adding the standard antisymmetry axiom (Λ(A,B)=1 iff Λ(B,A)=0) and swapping the two cases. I want to stress this is a formal gap, not a broken approach.

What is genuinely new: prior work gave rule-specific attacks (Spacemint bootstrapping/replotting, Ouroboros Genesis for PoStake). This paper's diagonalization—two profiles that are mutually fakeable via bootstrapping and replotting—rules out any antisymmetric chain selection rule at once, and quantifies the fork length as O(φ²ρ/ε). The matching upper bound, with the strange 'tent' rule, is a real contribution: it shows the bound is tight up to a factor φ. The proof of the tent rule is clear. I also credit the authors for explicitly discussing why Chia and Filecoin escape the impossibility (VDFs and registration respectively).

The soft spots beyond the main theorem: the model only covers rules comparing two equal-length chains using space profiles, so rules with clock time, VDFs, finality gadgets are outside the theorem. The authors acknowledge this; it's a scope limitation, not a hidden flaw. There are smaller notation/off-by-one issues in Lemma 2 and the proof of Theorem 2, but they are minor and don't affect the argument. The lower bound proof is self-contained: no parameter fitting, no circularity, and the construction of the two profiles is explicit.

Who should read this: anyone working on PoSpace or PoStake consensus, and reviewers of consensus papers. The universal theorem, once fixed with antisymmetry, is a significant negative result. I would send it to peer review, and I'd expect the authors to revise the statement of Theorem 1 and correct the final case analysis before it's accepted. The core result is likely correct after those repairs.

Referee Report

2 major / 4 minor

Summary. The paper studies whether proof-of-space (PoSpace) based longest-chain blockchains can be secure under dynamic availability. It abstracts a blockchain to a sequence of space profiles, defines a deterministic forking game parameterized by an honest/adversarial space ratio phi, a maximum per-block availability change factor 1+epsilon, a replotting delay rho, and an arbitrary chain selection rule Lambda. The main lower bound (Theorem 1) claims that for every chain selection rule Lambda an adversary can win the forking game in O(phi^2 * rho / epsilon) steps, by constructing two mutually fakeable space profiles and arguing that any rule must prefer one of them in one of the two worlds. Theorem 2 gives a tent-based chain selection rule Lambda_tent that requires fork length at least about phi * rho / epsilon, so the lower bound is tight up to a factor phi. The paper concludes that PoSpace longest-chain consensus is impossible in the fully permissionless and dynamic-availability settings without additional assumptions such as VDFs or registration.

Significance. If Theorem 1 is correct after the necessary hypotheses are added, the paper establishes a striking and exact impossibility: no chain selection rule that depends only on space profiles can secure a PoSpace longest-chain blockchain under dynamic availability. The lower-bound proof is a genuine diagonalization rather than a circular argument, and the explicit construction of two mutually fakeable profiles is a clean and useful idea. The paper is also commendably honest about its modeling boundary: it notes that Chia avoids the attack with proofs of time and Filecoin avoids it with BFT-style registration, so the result does not apply to those designs. The tent-based upper bound is a legitimate counterexample analysis and makes the claimed phi-factor separation meaningful. However, as written, Theorem 1 is false for the class of chain selection rules actually defined in the paper, because arbitrary Boolean-valued functions need not be antisymmetric. This is a load-bearing gap, but it is cleanly repairable by adding the standard antisymmetry condition and fixing the final case split.

major comments (2)

[Section 2.2 and Section A.1, final paragraph of the proof of Theorem 1] Theorem 1 is false as stated for the chain selection rules defined in Section 2.2. The definition allows any function Lambda:C x C -> {0,1}, and the game in Section 2.4 declares the adversary winning exactly when Lambda(C_i, \tilde C_i)=1. The constant rule Lambda ≡ 0 is therefore a valid chain selection rule, and no adversary can ever make Lambda(C_i, \tilde C_i)=1, so the (phi, epsilon, rho, Lambda)-forking game is never winnable. This directly contradicts the theorem's 'for every chain selection rule Lambda'. The proof's final paragraph also inverts the two worlds: if Lambda(C_ell, \tilde C_ell)=0, then the winning world is the second one, where the honest chain is \tilde C_ell and the adversary creates C_ell, because the game condition there is Lambda(\tilde C_ell, C_ell)=1. The proof silently assumes antisymmetry, namely Lambda(A,B)=0 iff Lambda(B,A)=1. The theorem should state this antisymmetry hypothesis explicitly, and the final case split should use Lambda(\tilde C_ell, C_ell)=1 in the second game. With that correction the diagonalization argument goes through.
[Section A.1, displayed definitions of the space profiles] The formal profile definitions do not match the constructions in Lemmas 3 and 4. In the displayed definition of \tilde s^h_i, the first tent segment gives \tilde s^h_{l+k} = (1+epsilon)^{k-1}, but Lemma 3 constructs the block at position l+k with space (1+epsilon)^k, and the intended tent peak is (1+epsilon)^k. The exponent in the first case of \tilde s^h_i appears to be off by one; it should be i-l rather than i-l-1 (or the ranges should be shifted accordingly). This is a concrete formal error in the proof of the central theorem, and the authors should correct the displayed profiles so that they exactly match the fork that the adversary constructs.

minor comments (4)

[Section 2.4] The game is described as parameterized by 'epsilon > 1', but epsilon should be any positive real; the constraint is already correctly stated as 0 < epsilon in the glossary and in the rest of the paper.
[Remark 1] The word 'Probabilitsic' in the remark heading is a typo and should read 'Probabilistic'.
[Section 2.5, Lemma 2] In the construction of the genesis-rule attack, the first adversarial block is assigned space 1/(1+epsilon), but the adversary's available space is 1/phi; the displayed value appears to be a typo, since the later analysis uses blocks of space 1/phi.
[Section A.1, Lemma 4, step 4] The last displayed equation for the honest chain in step 4 writes 'eC_i^0 = C_{i-1}^0 <- e b_i'; this should be 'eC_i^0 = eC_{i-1}^0 <- e b_i' to match the surrounding notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the impossibility proof is self-contained, with a separate non-circular correctness gap in the final case split.

full rationale

The derivation chain in Theorem 1 is self-contained and does not reduce to its inputs. The proof constructs two explicit space profiles S and S̃, then shows in Lemmas 3 and 4 that an adversary holding a 1/φ fraction of the other profile's space can reproduce the alternative profile using only the modeled bootstrapping and replotting operations; the resource-ratio constraint s_H/s_A=φ is used directly, no parameter is fitted to data, and the conclusion is not assumed. The upper-bound rule Λ_tent is introduced after the lower bound to demonstrate tightness, which is a legitimate counterexample construction rather than a circular maneuver. Citations to prior work (including self-authored PoSpace, Chia, and Spacemint papers) are contextual background and are not load-bearing for the theorem. One formal issue is flagged for correctness rather than circularity: Section 2.2's definition and Section 2.4's game condition imply that Λ(C, C̃)=0 means the honest first chain wins and the adversary wins only when Λ(C, C̃)=1, but the final paragraph of A.1 says 'If Λ(Cℓ0, eCℓ0)=0, then in the first forking game the chain selection rule would choose the adversarial chain,' inverting the defined semantics and silently assuming an antisymmetry axiom that is not stated. Without that axiom, the constant rule Λ≡0 is a counterexample to Theorem 1 as written. This is a genuine proof gap, but it is not circularity: it does not make the theorem equivalent to its assumptions by construction.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters appear in the proof: phi, epsilon, and rho are inputs to the security game, not fitted values, and k and l are derived. The axioms are modeling choices defining the class of protocols and attack capabilities; the central derivation does not assume its own conclusion.

assumptions (6)

domain assumption Each block perfectly reflects the amount of space used to create it, and exactly one block is created per time step.
Section 2.1 and Section 1.2 state this idealization; real chains approximate space statistically over epochs, so the deterministic fork-length bound is an idealized result, though a lower bound under idealization gives the adversary more power.
domain assumption The adversary is allowed to choose the honest space adjustment gamma_i in [1/(1+epsilon), 1+epsilon] each round, so it controls the honest space profile.
Section 2.4, game step 2; footnote 3 acknowledges this is a strong assumption but argues natural profiles suffice for the lower bound.
domain assumption Bootstrapping and replotting are available to the adversary with only a time cost of rho rounds per replot, and no other cost such as computation or registration is modeled.
Section 2.3 defines these capabilities; real replotting also costs computation and initialization, and bootstrapping can be prevented by VDFs, so the theorem applies only to protocols without such countermeasures.
domain assumption Chain selection rules are antisymmetric comparisons, meaning Lambda(X,Y)=1-Lambda(Y,X), though the paper only states that Lambda outputs the winner.
Section 2.2 defines Lambda as a function to {0,1} but the proof of Theorem 1 needs antisymmetry for the two-game diagonalization to go through; without it, a constant-zero rule would defeat the proof as written.
domain assumption No grinding or double dipping attacks are modeled.
Section 1.2 says these are excluded because known countermeasures exist; this makes the lower bound conservative.
standard math Geometric series and ceiling and logarithm inequalities used in fork-length computations.
Used in Lemma 1 and Appendix A.1 to bound sums of (1+epsilon)^i over k rounds and to relate k to log(phi)/log(1+epsilon).

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the (in)security of Proofs-of-Space based Longest-Chain Blockchains." pith.science (2026). https://pith.science/paper/IQBB5PBH

@misc{pith2026250514891,
  author       = {Pith},
  title        = {Pith review of: On the (in)security of Proofs-of-Space based Longest-Chain Blockchains},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQBB5PBH}},
  note         = {Machine review of arXiv:2505.14891}
}

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$.

Figures

Figures reproduced from arXiv: 2505.14891 by the authors.

**Figure 2.** The figs (a), (b) outline how the red profile from Fig 1 is faked using the [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 28 canonical work pages

[1]

https://docs.chia.net/green-paper-abstract/ (2019)

The chia network blockchain. https://docs.chia.net/green-paper-abstract/ (2019)

work page 2019
[2]

In: Takagi, T., Peyrin, T

Abusalah, H., Alwen, J., Cohen, B., Khilko, D., Pietrzak, K., Reyzin, L.: Beyond hellman’s time-memory trade-offs with applications to proofs of space. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASI- ACRYPT 2017 - 23rd International Conference on the Theory and Appli- cations of Cryptology and Information Security, Hong Kong, China, Decem-...

doi:10.1007/978- 2017
[3]

In: Lie, D., Mannan, M., Backes, M., Wang, X

Badertscher, C., Gazi, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availabil- ity. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) Proceed- ings of the 2018 ACM SIGSAC Conference on Computer and Com- munications Security, CCS 2018, Toronto, ON, Canada, October 15-19,

work page 2018
[4]

In: Soares, J.M., Song, D., Vukolic, M

Bagaria, V.K., Dembo, A., Kannan, S., Oh, S., Tse, D., Viswanath, P., Wang, X., Zeitouni, O.: Proof-of-stake longest chain protocols: Se- curity vs predictability. In: Soares, J.M., Song, D., Vukolic, M. (eds.) Proceedings of the 2022 ACM Workshop on Developments in Con- sensus, ConsensusDay 2022, Los Angeles, CA, USA, 7 November

work page 2022
[5]

In: Shacham, H., Boldyreva, A

Boneh, D., Bonneau, J., B¨ unz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 757–788. Springer International Publishing, Cham (2018)

work page 2018
[6]

In: Chaum, D., Rivest, R.L., Sherman, A.T

Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology: Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982. pp. 199–203. Plenum Press, New York (1982). https://doi.org/10.1007/978-1-4757-0602-4 18, https://doi.org/10.1007/978-1-4757-0602-4 18

doi:10.1007/978-1-4757-0602-4 1982
[7]

https://docs.chia.net/files/Precursor-ChiaGreenPaper.pdf (2019), this is an early proposal and differs significantly from the implemented version [1]

Cohen, B., Pietrzak, K.: The chia network blockchain. https://docs.chia.net/files/Precursor-ChiaGreenPaper.pdf (2019), this is an early proposal and differs significantly from the implemented version [1]

work page 2019
[8]

In: Gennaro, R., Robshaw, M

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015. pp. 585–605. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)

work page 2015

Show all 33 references

[9]

In: Katz, J., Shacham, H

Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: A prov- ably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology - CRYPTO 2017 - 37th Annual Inter- national Cryptology Conference, Santa Barbara, CA, USA, August 20-2...

2017 doi
[10]

Lewis-Pye, A., Roughgarden, T.: Permissionless consensus (2024), https://arxiv.org/abs/2304.14701

2024 arXiv
[11]

In: Meiklejohn, S., Sako, K

Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J., Pietrzak, K.: Spacemint: A cryptocurrency based on proofs of space. In: Meiklejohn, S., Sako, K. (eds.) Financial Cryptography and Data Security - 22nd Inter- national Conference, FC 2018, Nieuwpoort, Cura¸ cao, February...

2018 doi
[12]

Proof (Proof of Theorem 1).We already sketched the general idea in Section 1.4 and will make it more formal here

Wood, G.: Ethereum: A secure decentralised generalised transaction ledger A Proofs A.1 Proof of Theorem 1 Theorem 1 (Impossibility Result).For every chain selection ruleΛ, there exists an adversaryAthat wins the(ϕ, ε, ρ, Λ)-forking game in ℓ= & ρ·ϕ 2 ·(1 +ε)· (1 +ε)− 1 ϕ ε !' ...
[15]

= (˜sh i )ℓ i=0 while honest chain isC ℓ 0 withS(C ℓ
[16]

= (sH i )ℓ i=0 Proof (Proof of Lemma 3).The adversary,A, does following to create eCℓ i=0 while honest chain isC ℓ i=0:
[17]

At roundi= 0, C0 0 = eC0 0 =b 0 wheres(b 0) = 1
[18]

Thuss H i = 1 +ε·s H i−1

For 1≤i≤k−1, set 1 +ε i = 1 +ε. Thuss H i = 1 +ε·s H i−1. Honest chain becomes Ci 0 =C i−1 0 ←- bi wheres(b i) = (1 +ε) i. The adversarial chain eC0 0 =b 0 remains unchanged
[19]

So,s H i = 1 +ε·s H i−1 = (1 +ε) k ≥ϕ

Fori=k, set 1 +ε i = 1 +ε. So,s H i = 1 +ε·s H i−1 = (1 +ε) k ≥ϕ. Thus sA i ≥1. Honest chain is Ci 0 =C i−1 0 ←- bi wheres(b i) = (1 +ε) i. NowAbootstraps the adversarial chain to become eCl 0 =b 0 ←-eb1 ←- . . .←-ebl wheres( ebj) = 1 for allj∈[1, l]. This is demonstrated in Fig. 2(a)
[20]

Thus,s H i = (1 +ε) 2k−i

Fork+ 1≤i≤2k, set 1 +ε i = 1 (1+ε) . Thus,s H i = (1 +ε) 2k−i. Honest chain becomes Ci 0 =C i−1 0 ←- bi wheres(b i) = (1 +ε) 2k−i. The adversarial chain remains at eCl 0. 18
[21]

Thuss H i = 1

For 2k+ 1≤i≤l+ 2k, set 1 +ε i = 1. Thuss H i = 1. Honest chain continues as Ci 0 =C i−1 0 ←- bi wheres(b i) = 1. For the adversarial chain,Auses replotting to create eCl+2kl l+1 = ebl+1 ←- . . .←-ebl+2k such that s(bl+i) = ( (1 +ε) i for 1≤i≤k (1 +ε) 2k−i fork+ 1≤i≤2k. This is...
[22]

= (sH i )ℓ i=0 while honest chain is eCℓ 0 withS( eCℓ
[23]

Formally,

= (˜sh i )ℓ i=0 Proof (Proof of Lemma 4).To createC ℓ i=0 while honest chain is eCℓ i=0, the ad- versary,A, does the reverse of Lemma 3,i.e.it first replots and then bootstraps. Formally,
[24]

Note that here eCis the honest chain whileCis the adver- sarial chain

At roundi= 0, C0 0 = eC0 0 =b 0 wheres(b 0) = 1. Note that here eCis the honest chain whileCis the adver- sarial chain
[25]

Thus,s H i = 1

For round 1≤i≤l, set 1 +ε i = 1. Thus,s H i = 1. The honest chain becomes eCi 0 = eCi−1 0 ←-ebi wheres( ebi) = 1.Areplots a chain C2k 0 =b 0 ←- b1 ←- . . .←- b2k such that s(bi) = ( (1 +ε) i for 1≤i≤k (1 +ε) 2k−i fork+ 1≤i≤2k. This is demonstrated in Fig. 2(c). As argued in Le...
[26]

Thuss H i = (1 +ε) i−l

For roundl+ 1≤i≤l+k−1, set 1 +ε i = 1 +ε. Thuss H i = (1 +ε) i−l. The honest chain becomes eCi 0 = eCi−1 0 ←-ebi wheres( ebi) = (1 +ε) i−l. The adversarial chain remains unchanged
[27]

Thuss H i = (1 +ε)k ≥ ⌈ϕ⌉

For roundi=l+k, set 1 +ε i = 1 +ε. Thuss H i = (1 +ε)k ≥ ⌈ϕ⌉. Therefore, sA i ≥ ⌈ϕ⌉ ϕ ≥1. The honest chain continues as eCi 0 =C i−1 0 ←-ebi wheres( ebi) = (1 +ε) k.Auses spaces A i ≥1 to bootstrap the adversarial chain to form C2k+l 0 =C 2k 0 ←- b2k+i ←- . . .←- b2k+l wheres(...
[28]

Thuss H i = (1 +ε)l+2k−i

For roundl+k+ 1≤i≤l+ 2k, set 1 +ε i = 1 (1+ε) . Thuss H i = (1 +ε)l+2k−i. The honest chain continues as eCi 0 = eCi−1 0 ←-ebi wheres( ebi) = (1 +ε) l+2k−i. The adversarial chain remains unchanged. At roundi=l+ 2k=ℓwe have the honest chain as eCℓ 0 with space-profile eSand adve...
[29]

IfΛ(C ℓ 0, eCℓ

= 0, then in the first forking game the chain selection rule would choose the adversarial chain. IfΛ(C ℓ 0, eCℓ
[30]

Therefore in either case it is possible to fool the chain selection

= 1, then in the second forking game the chain selection rule would choose the adversarial chain. Therefore in either case it is possible to fool the chain selection. Note that we made no restriction onΛ; we only used replotting and resource variability. Hence, we can conclude...
[31]

Let’s assumeC j 0 is the honest chain, while eC j 0 is the adversarial one created in the (ϕ,1 +ε, ρ, Λtent) forking game

= 0 ifµ≥eµ. Let’s assumeC j 0 is the honest chain, while eC j 0 is the adversarial one created in the (ϕ,1 +ε, ρ, Λtent) forking game. To win the game it must hold thateµ > µ. We know that during the fork (when the honest parties createdb f , . . . , bj) the honest parties nev...
[32]

Number of rounds required to replot this space, using µ ϕ , is k−1X i=0 ρ· & µ (1+ε)i − µ ϕ µ ϕ ' = k−1X i=0 ρ· ϕ (1 +ε) i −1 ≥ρ· k−1X i=0 ϕ (1 +ε) i −1 =ρ· ϕ·(1 +ε)· 1− 1 ϕ ε −k !

Ifez≥korl−ez≥k, then the fork is long enough to contain a sequence of µ, µ (1+ε) ,· · ·, µ (1+ε)k−1 above the µ ϕ . Number of rounds required to replot this space, using µ ϕ , is k−1X i=0 ρ· & µ (1+ε)i − µ ϕ µ ϕ ' = k−1X i=0 ρ· ϕ (1 +ε) i −1 ≥ρ· k−1X i=0 ϕ (1 +ε) i −1 =ρ· ϕ·(1...
[33]

Thus in total at leastρ∗lsteps are required

Ifez < kandl−ez < k, then the fork is too short for replotting as every step of the tent in the forked chain is aboveµ/ϕand for each of them we need at leastρsteps of replotting. Thus in total at leastρ∗lsteps are required. Sinceρ≥2, replotting is not possible. Therefore,Acann...
[2018]

pp. 913–930. ACM (2018). https://doi.org/10.1145/3243734.3243848, https://doi.org/10.1145/3243734.3243848

2018
[2022]

pp. 29–42. ACM (2022). https://doi.org/10.1145/3560829.3563559, https://doi.org/10.1145/3560829.3563559

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

https://docs.chia.net/green-paper-abstract/ (2019)

The chia network blockchain. https://docs.chia.net/green-paper-abstract/ (2019)

work page 2019

[2] [2]

In: Takagi, T., Peyrin, T

Abusalah, H., Alwen, J., Cohen, B., Khilko, D., Pietrzak, K., Reyzin, L.: Beyond hellman’s time-memory trade-offs with applications to proofs of space. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASI- ACRYPT 2017 - 23rd International Conference on the Theory and Appli- cations of Cryptology and Information Security, Hong Kong, China, Decem-...

doi:10.1007/978- 2017

[3] [3]

In: Lie, D., Mannan, M., Backes, M., Wang, X

Badertscher, C., Gazi, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros genesis: Composable proof-of-stake blockchains with dynamic availabil- ity. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) Proceed- ings of the 2018 ACM SIGSAC Conference on Computer and Com- munications Security, CCS 2018, Toronto, ON, Canada, October 15-19,

work page 2018

[4] [4]

In: Soares, J.M., Song, D., Vukolic, M

Bagaria, V.K., Dembo, A., Kannan, S., Oh, S., Tse, D., Viswanath, P., Wang, X., Zeitouni, O.: Proof-of-stake longest chain protocols: Se- curity vs predictability. In: Soares, J.M., Song, D., Vukolic, M. (eds.) Proceedings of the 2022 ACM Workshop on Developments in Con- sensus, ConsensusDay 2022, Los Angeles, CA, USA, 7 November

work page 2022

[5] [5]

In: Shacham, H., Boldyreva, A

Boneh, D., Bonneau, J., B¨ unz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology – CRYPTO 2018. pp. 757–788. Springer International Publishing, Cham (2018)

work page 2018

[6] [6]

In: Chaum, D., Rivest, R.L., Sherman, A.T

Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) Advances in Cryptology: Proceedings of CRYPTO ’82, Santa Barbara, California, USA, August 23-25, 1982. pp. 199–203. Plenum Press, New York (1982). https://doi.org/10.1007/978-1-4757-0602-4 18, https://doi.org/10.1007/978-1-4757-0602-4 18

doi:10.1007/978-1-4757-0602-4 1982

[7] [7]

https://docs.chia.net/files/Precursor-ChiaGreenPaper.pdf (2019), this is an early proposal and differs significantly from the implemented version [1]

Cohen, B., Pietrzak, K.: The chia network blockchain. https://docs.chia.net/files/Precursor-ChiaGreenPaper.pdf (2019), this is an early proposal and differs significantly from the implemented version [1]

work page 2019

[8] [8]

In: Gennaro, R., Robshaw, M

Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) Advances in Cryptology – CRYPTO 2015. pp. 585–605. Springer Berlin Heidelberg, Berlin, Heidelberg (2015)

work page 2015