Towards a Multi-Chain Future of Proof-of-Space

Dawu Gu; Jilai Zheng; Shuyang Tang; Yao Deng; Zhiqiang Liu; Ziyu Wang

arxiv: 1907.07896 · v1 · pith:ZTBZC5YKnew · submitted 2019-07-18 · 💻 cs.CR

Towards a Multi-Chain Future of Proof-of-Space

Shuyang Tang , Jilai Zheng , Yao Deng , Ziyu Wang , Zhiqiang Liu , Dawu Gu This is my paper

Pith reviewed 2026-05-24 20:00 UTC · model grok-4.3

classification 💻 cs.CR

keywords Proof-of-Spacemulti-chain blockchainnewborn attackincentive compatibilitystorage proofconsensus protocolpermissionless blockchain

0 comments

The pith

A multi-chain Proof-of-Space scheme using shared and chain-specific storage proofs resists newborn attacks while remaining incentive-compatible.

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

Existing multi-chain Proof-of-Space designs allow the same storage proof to be reused across chains, which opens a newborn attack when a new chain launches. The paper first defines a single-chain Proof-of-Space framework and then builds a multi-chain variant that interleaves a reusable shared proof with proofs that are unique to each chain. Security analysis shows this hybrid construction blocks the attack. The work further proves the scheme is incentive-compatible, so that rational participants maximize their total utility by following the paper's recommended partition of storage resources across chains.

Core claim

The authors present a novel multi-chain Proof-of-Space scheme that combines shared proof and chain-specific proof of storage. This combination resists newborn attack on newly launched chains. The scheme is shown to be secure and incentive-compatible, meaning participants achieve their greatest utility by partitioning storage resources according to the proposed strategy.

What carries the argument

The hybrid storage proof that pairs a chain-agnostic shared proof with per-chain specific proofs, binding storage allocation to individual chains while still permitting reuse.

If this is right

New chains can launch without exposing the system to storage-reuse attacks.
Participants follow the storage-partition strategy to obtain maximum utility across chains.
The multi-chain construction preserves the security properties established for the single-chain framework.
Rational miners have no incentive to deviate from the recommended resource allocation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The approach may lower the capital cost of supporting multiple independent chains on the same hardware.
Similar hybrid-proof techniques could be tested in other proof-of-resource consensus settings.
If the chain-specific component can be made lightweight, the design might scale to dozens of simultaneous chains without proportional storage growth.

Load-bearing premise

The security and incentive proofs assume that the hybrid proof construction eliminates the newborn attack without creating new attack vectors or altering the utility-maximizing behavior of participants.

What would settle it

An implemented prototype in which an attacker reuses storage from existing chains to launch a new chain and succeeds in the newborn attack despite the chain-specific proof component.

Figures

Figures reproduced from arXiv: 1907.07896 by Dawu Gu, Jilai Zheng, Shuyang Tang, Yao Deng, Zhiqiang Liu, Ziyu Wang.

**Figure 1.** Figure 1: Capacity Resource Partition Initial Step. For a miner to dedicate λN bits of storage to the blockchain network, it computes and stores the labels of their pebbling graph to get (γ, γe) ← ΠPoC.initH(S) at the initial stage. Afterwards sctx = (pk, γ)pk−1 is broadcast to the network. The Mining. Each miner maintains a main chain (the chain branch with the greatest total weight) in its view. We denote the chai… view at source ↗

**Figure 2.** Figure 2: The Main Functionality Specifically, to a chain i with βi = Bi ||B|| (Bi is the sum of si for all participants) fraction of total storage proof, we stimulate the participant to allocate si = βis0 storage on it. To allow for the start-up of new chains, we in actual ask that si ≤ (1 +δ)βis0. Clearly, as an equilibrium of economics, the total storage proof behind a blockchain is proportional to the total mark… view at source ↗

**Figure 3.** Figure 3: The Main Protocol [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

read the original abstract

Proof-of-Space provides an intriguing alternative for consensus protocol of permissionless blockchains due to its recyclable nature and the potential to support multiple chains simultaneously. However, a direct shared proof of the same storage, which was adopted in the existing multi-chain schemes based on Proof-of-Space, could give rise to newborn attack on new chain launching. To fix this gap, we propose an innovative framework of single-chain Proof-of-Space and further present a novel multi-chain scheme which can resist newborn attack effectively by elaborately combining shared proof and chain-specific proof of storage. Moreover, we analyze the security of the multi-chain scheme and prove that it is incentive-compatible. This means that participants in such multi-chain system can achieve their greatest utility with our proposed strategy of storage resource partition.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sketches a dual-proof PoS scheme to share storage across chains while blocking newborn attacks, but the security and incentive claims rest on unshown modeling details.

read the letter

The core contribution is a single-chain PoS framework plus a multi-chain extension that combines shared storage proofs with chain-specific ones, plus the claim that a particular storage-partition strategy is both secure against newborn attacks and incentive-compatible for participants. That combination is presented as the fix for the reuse problem that arises when the same storage is offered to multiple chains at once. The authors also state they have analyzed security and proved incentive compatibility, which would mean rational miners follow the partition rule to maximize their utility. This is a direct response to a practical issue in permissionless multi-chain settings, and the focus on explicit resistance to the newborn attack is the clearest new element. The abstract does a reasonable job of naming the attack and outlining the high-level mitigation. The soft spot is that none of the supporting material appears in the abstract: no game model, no utility function, no derivation steps for either the security or the incentive result. The stress-test concern is on point here—the resistance and compatibility claims depend on an unstated assumption that the shared-plus-specific combination closes the attack without opening new vectors or giving participants a profitable deviation. If the full paper supplies a formal game and walks through why the partition is dominant, that gap closes; otherwise the central assertions remain unverified. This is aimed at researchers working on Proof-of-Space consensus and multi-chain designs. A reader already familiar with the newborn attack literature could extract the proposed pattern and the partition idea as a concrete suggestion, even if the proofs need checking. I would send it to peer review so that experts can examine whether the modeling choices actually deliver the claimed properties. The topic is narrow but the attack class is real, so the work is worth a referee's time if the details are there.

Referee Report

2 major / 0 minor

Summary. The paper proposes a single-chain Proof-of-Space framework and a novel multi-chain scheme that combines shared proofs with chain-specific proofs of storage to resist newborn attacks on new chains. It claims to analyze the security of this multi-chain scheme and prove that it is incentive-compatible, such that participants achieve maximum utility by following the proposed strategy of partitioning storage resources across chains.

Significance. If the claimed security analysis and incentive-compatibility proof are rigorous and rest on a well-specified game model, the work would address a concrete vulnerability in multi-chain Proof-of-Space systems and could enable more robust simultaneous operation of multiple chains without introducing new attack surfaces or violating participant utility maximization.

major comments (2)

[Abstract] Abstract: the central claims that the scheme 'can resist newborn attack effectively' and 'is incentive-compatible' are asserted without any visible formal model of the attack game, definition of participant utility (including costs of chain-specific proofs), or derivation steps showing how the shared-plus-chain-specific combination eliminates the attack while preserving the claimed equilibrium.
[Abstract (and any security/incentive section)] The incentive-compatibility claim is stated to follow from the storage-partition strategy, yet the text supplies no explicit utility function or equilibrium analysis; it is therefore impossible to verify whether the proof is independent of the modeling assumptions or simply restates them.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for highlighting the need for greater explicitness in the formal models underlying our security and incentive-compatibility claims. We address each point below and will revise the manuscript accordingly to improve clarity and verifiability.

read point-by-point responses

Referee: [Abstract] Abstract: the central claims that the scheme 'can resist newborn attack effectively' and 'is incentive-compatible' are asserted without any visible formal model of the attack game, definition of participant utility (including costs of chain-specific proofs), or derivation steps showing how the shared-plus-chain-specific combination eliminates the attack while preserving the claimed equilibrium.

Authors: The abstract is intentionally concise and therefore omits the detailed game model, utility definition, and derivation steps that appear in Sections 4 and 5 of the full manuscript. Section 4 defines the newborn-attack game with honest and adversarial storage allocation strategies; Section 5 introduces an explicit utility function that subtracts the marginal cost of generating chain-specific proofs from the expected rewards across chains. The equilibrium analysis then shows that any deviation from the proposed partition increases an adversary's cost without raising its success probability. To address the referee's concern, we will expand the abstract with a one-sentence reference to these sections and will add a short derivation paragraph in Section 5 that explicitly incorporates the cost of chain-specific proofs. revision: yes
Referee: [Abstract (and any security/incentive section)] The incentive-compatibility claim is stated to follow from the storage-partition strategy, yet the text supplies no explicit utility function or equilibrium analysis; it is therefore impossible to verify whether the proof is independent of the modeling assumptions or simply restates them.

Authors: Section 5 does define a utility function u_i = sum_c (R_c * p_c - C_shared - C_specific,c) where R_c is the reward on chain c, p_c the probability of winning a block, C_shared the amortized cost of the shared proof, and C_specific,c the additional cost of the chain-specific proof. The proof then shows that the partition strategy (allocating storage proportionally to expected rewards) is a Nash equilibrium under the assumption that proof costs are linear in allocated space. If the referee finds the current presentation insufficiently independent of modeling choices, we will add a subsection that relaxes the linearity assumption and re-derives the equilibrium condition. We will also move the utility function into a displayed equation for easier reference. revision: partial

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The provided abstract and context describe a proposal for single-chain and multi-chain Proof-of-Space frameworks, followed by a security analysis and an incentive-compatibility proof tied to a storage partition strategy. No equations, self-citations, or explicit derivations are quoted that reduce the claimed proof or prediction to the input strategy by construction. The incentive-compatibility statement is presented as an analytical outcome rather than a tautological restatement, and no load-bearing self-citation chains or ansatz smuggling appear in the visible text. The derivation chain is therefore treated as self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim implicitly rests on standard cryptographic assumptions about proof-of-space primitives and on an unstated game-theoretic model of participant utility.

pith-pipeline@v0.9.0 · 5667 in / 1176 out tokens · 15290 ms · 2026-05-24T20:00:09.298313+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

we prove that our scheme is incentive-compatible... participants can achieve their greatest utility with our desired strategy of storage resource partition... U(s,B) := sum val(s,B,k) ... opt(c,B) = c/2 ◦ (c/2)β
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the same storage source contributes simultaneously to multiple blockchains and newly set up blockchains are hard to be devastated

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

[1]

Bitcoin: A peer-to-peer electronic ca sh system, 2008

Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic ca sh system, 2008

work page 2008
[2]

Pricing via processing or com batting junk mail

Cynthia Dwork and Moni Naor. Pricing via processing or com batting junk mail. In Advances in Cryptology - CRYPTO ’92, 12th Annual Internatio nal Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, pages 139–147, 1992

work page 1992
[3]

Proof of stake instead of proof of w ork

QuantumMechanic et al. Proof of stake instead of proof of w ork. Bitcoin forum, 2011. https://bitcointalk.org/index.php?topic=27787.0

work page 2011
[4]

Proof of activity: Extending bitcoin’s proof of work via proof of stake [extend ed abstract]y

Iddo Bentov, Charles Lee, Alex Mizrahi, and Meni Rosenfel d. Proof of activity: Extending bitcoin’s proof of work via proof of stake [extend ed abstract]y. SIG- METRICS Performance Evaluation Review , 42(3):34–37, 2014

work page 2014
[5]

Snow white: Prov ably secure proofs of stake

Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Prov ably secure proofs of stake. IACR Cryptology ePrint Archive , 2016:919, 2016. 1 Most existing systems ask for α > 1/ 3, but we treat α as a tunable parameter to allow ﬂexibility. 14 Shuyang Tang et. al

work page 2016
[6]

The sleepy model of consensus

Rafael Pass and Elaine Shi. The sleepy model of consensus. In Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conferenc e on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II , pages 380–409, 2017

work page 2017
[7]

Ouroboros: A provably secure proof-of-stake blockchain pr otocol

Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain pr otocol. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Crypto logy Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Pa rt I , pages 357–388, 2017

work page 2017
[8]

Ouroboros praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain

Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexand er Russell. Ouroboros praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain. In Ad- vances in Cryptology - EUROCRYPT 2018 - 37th Annual Internat ional Conference on the Theory and Applications of Cryptographic Techniques , Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part...

work page 2018
[9]

Ouroboros genesis: Composable proof-of-stake bloc kchains with dynamic availability

Christian Badertscher, Peter Gazi, Aggelos Kiayias, Ale xander Russell, and Vassilis Zikas. Ouroboros genesis: Composable proof-of-stake bloc kchains with dynamic availability. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada , October 15-19, 2018, pages 913–930, 2018

work page 2018
[10]

Pebbling and p roofs of work

Cynthia Dwork, Moni Naor, and Hoeteck Wee. Pebbling and p roofs of work. In Advances in Cryptology - CRYPTO 2005: 25th Annual Internati onal Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, pages 37–54, 2005

work page 2005
[11]

Ke y-evolution schemes resilient to space-bounded leakage

Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. Ke y-evolution schemes resilient to space-bounded leakage. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA , August 14-18,

work page 2011
[12]

Proceedings, pages 335–353, 2011

work page 2011
[13]

On e-time computable self-erasing functions

Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. On e-time computable self-erasing functions. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 201 1. Proceedings, pages 125–143, 2011

work page 2011
[14]

Spacemint: A cryptocurrency based on proofs of space

Georg Fuchsbauer. Spacemint: A cryptocurrency based on proofs of space. ERCIM News, 2017(110), 2017

work page 2017
[15]

Proofs of space: When space is of the essence

Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, an d Nicola Galesi. Proofs of space: When space is of the essence. In Security and Cryptography for Networks - 9th International Conference, SCN 2014, Amalﬁ, Italy, Sep tember 3-5, 2014. Proceedings, pages 538–557, 2014

work page 2014
[16]

Proofs of space

Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogo rov, and Krzysztof Pietrzak. Proofs of space. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, Augu st 16-20, 2015, Proceedings, Part II, pages 585–605, 2015

work page 2015
[17]

Stronger key derivation via sequential memory-hard func- tions

COLIN PERCIV AL. Stronger key derivation via sequential memory-hard func- tions. 01 2009

work page 2009
[18]

Kaliski Jr

Ari Juels and Burton S. Kaliski Jr. Pors: proofs of retrie vability for large ﬁles. In Proceedings of the 2007 ACM Conference on Computer and Commu nications Security, CCS 2007, Alexandria, Virginia, USA, October 28- 31, 2007 , pages 584– 597, 2007

work page 2007
[19]

Paul, Robert Endre Tarjan, and James R

Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celon i. Space bounds for a game on graphs. Mathematical Systems Theory , 10:239–251, 1977

work page 1977
[20]

Noga Alon and Michael R. Capalbo. Smaller explicit super concentrators. Internet Mathematics, 1(2):151–163, 2003. Towards a Multi-Chain Future of Proof-of-Space 15

work page 2003
[21]

Better expanders and superconcentrator s by kolmogorov complex- ity

Uwe Sch¨ oning. Better expanders and superconcentrator s by kolmogorov complex- ity. In SIROCCO’97, 4th International Colloquium on Structural In formation & Communication Complexity, Monte Verita, Ascona, Switzerl and, July 24-26, 1997 , pages 138–150, 1997

work page 1997
[22]

Superconcentr ators of density 25.3

Vladimir Kolmogorov and Michal Rolinek. Superconcentr ators of density 25.3. Ars Comb., 141:269–304, 2018

work page 2018
[23]

David J. Haglin. Bipartite expander matching is in NC. Parallel Processing Letters, 5:413–420, 1995

work page 1995
[24]

Dense expanders and pseudo-random bip artite graphs

Andrew Thomason. Dense expanders and pseudo-random bip artite graphs. Dis- crete Mathematics, 75(1-3):381–386, 1989

work page 1989
[25]

Graham, , and Endre Szemeredi

Paul Erdoes, Ronald L. Graham, , and Endre Szemeredi. On s parse graphs with dense long paths. Technical report, Stanford, CA, USA,, 197 5

work page
[26]

D epth-robust graphs and their cumulative memory complexity

Jo¨ el Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. D epth-robust graphs and their cumulative memory complexity. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory an d Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2 017, Proceedings, Part III , pages 3–32, 2017

work page 2017
[27]

Proof of space from stacke d expanders

Ling Ren and Srinivas Devadas. Proof of space from stacke d expanders. In Theory of Cryptography - 14th International Conference, TCC 2016- B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I , pages 262–285, 2016

work page 2016
[28]

Proofs of catalytic space

Krzysztof Pietrzak. Proofs of catalytic space. In 10th Innovations in Theoreti- cal Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , pages 59:1–59:25, 2019

work page 2019
[29]

Random oracles are pr actical: A paradigm for designing eﬃcient protocols

Mihir Bellare and Phillip Rogaway. Random oracles are pr actical: A paradigm for designing eﬃcient protocols. In CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virgini a, USA, November 3-5, 1993. , pages 62–73, 1993

work page 1993
[30]

Fixing cra cks in the concrete: Random oracles with auxiliary input, revisited

Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing cra cks in the concrete: Random oracles with auxiliary input, revisited. In Advances in Cryptology - EU- ROCRYPT 2017 - 36th Annual International Conference on the T heory and Ap- plications of Cryptographic Techniques, Paris, France, Ap ril 30 - May 4, 2017, Proceedings, Part II, pages 473–495, 2017

work page 2017
[31]

Simple proofs of sequ ential work

Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequ ential work. In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International C onference on the Theory and Applications of Cryptographic Techniques, Tel A viv, Israel, April 29 - May 3, 2018 Proceedings, Part II , pages 451–467, 2018

work page 2018
[32]

John E. Savage. Models of computation - exploring the power of computing . Addison-Wesley, 1998. 16 Shuyang Tang et. al. Protocol Πmain Shared protocol Π main is executed by all participants P1, P 2, . . . , P N . We assume a public-key infrastructureFcert. This functionality is parameterized by the number of candid ates N (this is a variant in the permis...

work page 1998
[33]

Parse com→ ( pk′, s, γ ={γi}i∈ [M ] ) , check pk′ ? = pk

work page
[34]

vrfH ( si, γ i, H (τAi R ), τ i ) and Π PoC

Check Π PoC. vrfH ( si, γ i, H (τAi R ), τ i ) and Π PoC. vrfH ( s0, γ 0, H (τAi R ), τ i′ )

work page
[35]

Check whether each two elements in Γ are diﬀerent

work page
[36]

Reject if the above condition is not satisﬁed

Check whether ( pk, com) /∈ J and for each γi, it holds γi /∈ Γ . Reject if the above condition is not satisﬁed

work page
[37]

Update J := J⊎{ (pk, com)} and Γ := Γ⊎ γ. Fig. 3. The Main Protocol

work page

[1] [1]

Bitcoin: A peer-to-peer electronic ca sh system, 2008

Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic ca sh system, 2008

work page 2008

[2] [2]

Pricing via processing or com batting junk mail

Cynthia Dwork and Moni Naor. Pricing via processing or com batting junk mail. In Advances in Cryptology - CRYPTO ’92, 12th Annual Internatio nal Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings, pages 139–147, 1992

work page 1992

[3] [3]

Proof of stake instead of proof of w ork

QuantumMechanic et al. Proof of stake instead of proof of w ork. Bitcoin forum, 2011. https://bitcointalk.org/index.php?topic=27787.0

work page 2011

[4] [4]

Proof of activity: Extending bitcoin’s proof of work via proof of stake [extend ed abstract]y

Iddo Bentov, Charles Lee, Alex Mizrahi, and Meni Rosenfel d. Proof of activity: Extending bitcoin’s proof of work via proof of stake [extend ed abstract]y. SIG- METRICS Performance Evaluation Review , 42(3):34–37, 2014

work page 2014

[5] [5]

Snow white: Prov ably secure proofs of stake

Iddo Bentov, Rafael Pass, and Elaine Shi. Snow white: Prov ably secure proofs of stake. IACR Cryptology ePrint Archive , 2016:919, 2016. 1 Most existing systems ask for α > 1/ 3, but we treat α as a tunable parameter to allow ﬂexibility. 14 Shuyang Tang et. al

work page 2016

[6] [6]

The sleepy model of consensus

Rafael Pass and Elaine Shi. The sleepy model of consensus. In Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conferenc e on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part II , pages 380–409, 2017

work page 2017

[7] [7]

Ouroboros: A provably secure proof-of-stake blockchain pr otocol

Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. Ouroboros: A provably secure proof-of-stake blockchain pr otocol. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Crypto logy Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Pa rt I , pages 357–388, 2017

work page 2017

[8] [8]

Ouroboros praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain

Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexand er Russell. Ouroboros praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain. In Ad- vances in Cryptology - EUROCRYPT 2018 - 37th Annual Internat ional Conference on the Theory and Applications of Cryptographic Techniques , Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part...

work page 2018

[9] [9]

Ouroboros genesis: Composable proof-of-stake bloc kchains with dynamic availability

Christian Badertscher, Peter Gazi, Aggelos Kiayias, Ale xander Russell, and Vassilis Zikas. Ouroboros genesis: Composable proof-of-stake bloc kchains with dynamic availability. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada , October 15-19, 2018, pages 913–930, 2018

work page 2018

[10] [10]

Pebbling and p roofs of work

Cynthia Dwork, Moni Naor, and Hoeteck Wee. Pebbling and p roofs of work. In Advances in Cryptology - CRYPTO 2005: 25th Annual Internati onal Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, pages 37–54, 2005

work page 2005

[11] [11]

Ke y-evolution schemes resilient to space-bounded leakage

Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. Ke y-evolution schemes resilient to space-bounded leakage. In Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA , August 14-18,

work page 2011

[12] [12]

Proceedings, pages 335–353, 2011

work page 2011

[13] [13]

On e-time computable self-erasing functions

Stefan Dziembowski, Tomasz Kazana, and Daniel Wichs. On e-time computable self-erasing functions. In Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 201 1. Proceedings, pages 125–143, 2011

work page 2011

[14] [14]

Spacemint: A cryptocurrency based on proofs of space

Georg Fuchsbauer. Spacemint: A cryptocurrency based on proofs of space. ERCIM News, 2017(110), 2017

work page 2017

[15] [15]

Proofs of space: When space is of the essence

Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, an d Nicola Galesi. Proofs of space: When space is of the essence. In Security and Cryptography for Networks - 9th International Conference, SCN 2014, Amalﬁ, Italy, Sep tember 3-5, 2014. Proceedings, pages 538–557, 2014

work page 2014

[16] [16]

Proofs of space

Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogo rov, and Krzysztof Pietrzak. Proofs of space. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, Augu st 16-20, 2015, Proceedings, Part II, pages 585–605, 2015

work page 2015

[17] [17]

Stronger key derivation via sequential memory-hard func- tions

COLIN PERCIV AL. Stronger key derivation via sequential memory-hard func- tions. 01 2009

work page 2009

[18] [18]

Kaliski Jr

Ari Juels and Burton S. Kaliski Jr. Pors: proofs of retrie vability for large ﬁles. In Proceedings of the 2007 ACM Conference on Computer and Commu nications Security, CCS 2007, Alexandria, Virginia, USA, October 28- 31, 2007 , pages 584– 597, 2007

work page 2007

[19] [19]

Paul, Robert Endre Tarjan, and James R

Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celon i. Space bounds for a game on graphs. Mathematical Systems Theory , 10:239–251, 1977

work page 1977

[20] [20]

Noga Alon and Michael R. Capalbo. Smaller explicit super concentrators. Internet Mathematics, 1(2):151–163, 2003. Towards a Multi-Chain Future of Proof-of-Space 15

work page 2003

[21] [21]

Better expanders and superconcentrator s by kolmogorov complex- ity

Uwe Sch¨ oning. Better expanders and superconcentrator s by kolmogorov complex- ity. In SIROCCO’97, 4th International Colloquium on Structural In formation & Communication Complexity, Monte Verita, Ascona, Switzerl and, July 24-26, 1997 , pages 138–150, 1997

work page 1997

[22] [22]

Superconcentr ators of density 25.3

Vladimir Kolmogorov and Michal Rolinek. Superconcentr ators of density 25.3. Ars Comb., 141:269–304, 2018

work page 2018

[23] [23]

David J. Haglin. Bipartite expander matching is in NC. Parallel Processing Letters, 5:413–420, 1995

work page 1995

[24] [24]

Dense expanders and pseudo-random bip artite graphs

Andrew Thomason. Dense expanders and pseudo-random bip artite graphs. Dis- crete Mathematics, 75(1-3):381–386, 1989

work page 1989

[25] [25]

Graham, , and Endre Szemeredi

Paul Erdoes, Ronald L. Graham, , and Endre Szemeredi. On s parse graphs with dense long paths. Technical report, Stanford, CA, USA,, 197 5

work page

[26] [26]

D epth-robust graphs and their cumulative memory complexity

Jo¨ el Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. D epth-robust graphs and their cumulative memory complexity. In Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory an d Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2 017, Proceedings, Part III , pages 3–32, 2017

work page 2017

[27] [27]

Proof of space from stacke d expanders

Ling Ren and Srinivas Devadas. Proof of space from stacke d expanders. In Theory of Cryptography - 14th International Conference, TCC 2016- B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I , pages 262–285, 2016

work page 2016

[28] [28]

Proofs of catalytic space

Krzysztof Pietrzak. Proofs of catalytic space. In 10th Innovations in Theoreti- cal Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , pages 59:1–59:25, 2019

work page 2019

[29] [29]

Random oracles are pr actical: A paradigm for designing eﬃcient protocols

Mihir Bellare and Phillip Rogaway. Random oracles are pr actical: A paradigm for designing eﬃcient protocols. In CCS ’93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virgini a, USA, November 3-5, 1993. , pages 62–73, 1993

work page 1993

[30] [30]

Fixing cra cks in the concrete: Random oracles with auxiliary input, revisited

Yevgeniy Dodis, Siyao Guo, and Jonathan Katz. Fixing cra cks in the concrete: Random oracles with auxiliary input, revisited. In Advances in Cryptology - EU- ROCRYPT 2017 - 36th Annual International Conference on the T heory and Ap- plications of Cryptographic Techniques, Paris, France, Ap ril 30 - May 4, 2017, Proceedings, Part II, pages 473–495, 2017

work page 2017

[31] [31]

Simple proofs of sequ ential work

Bram Cohen and Krzysztof Pietrzak. Simple proofs of sequ ential work. In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International C onference on the Theory and Applications of Cryptographic Techniques, Tel A viv, Israel, April 29 - May 3, 2018 Proceedings, Part II , pages 451–467, 2018

work page 2018

[32] [32]

John E. Savage. Models of computation - exploring the power of computing . Addison-Wesley, 1998. 16 Shuyang Tang et. al. Protocol Πmain Shared protocol Π main is executed by all participants P1, P 2, . . . , P N . We assume a public-key infrastructureFcert. This functionality is parameterized by the number of candid ates N (this is a variant in the permis...

work page 1998

[33] [33]

Parse com→ ( pk′, s, γ ={γi}i∈ [M ] ) , check pk′ ? = pk

work page

[34] [34]

vrfH ( si, γ i, H (τAi R ), τ i ) and Π PoC

Check Π PoC. vrfH ( si, γ i, H (τAi R ), τ i ) and Π PoC. vrfH ( s0, γ 0, H (τAi R ), τ i′ )

work page

[35] [35]

Check whether each two elements in Γ are diﬀerent

work page

[36] [36]

Reject if the above condition is not satisﬁed

Check whether ( pk, com) /∈ J and for each γi, it holds γi /∈ Γ . Reject if the above condition is not satisﬁed

work page

[37] [37]

Update J := J⊎{ (pk, com)} and Γ := Γ⊎ γ. Fig. 3. The Main Protocol

work page