---
_id: '7407'
abstract:
- lang: eng
text: 'Proofs of space (PoS) [Dziembowski et al., CRYPTO''15] are proof systems
where a prover can convince a verifier that he "wastes" disk space. PoS were introduced
as a more ecological and economical replacement for proofs of work which are currently
used to secure blockchains like Bitcoin. In this work we investigate extensions
of PoS which allow the prover to embed useful data into the dedicated space, which
later can be recovered. Our first contribution is a security proof for the original
PoS from CRYPTO''15 in the random oracle model (the original proof only applied
to a restricted class of adversaries which can store a subset of the data an honest
prover would store). When this PoS is instantiated with recent constructions of
maximally depth robust graphs, our proof implies basically optimal security. As
a second contribution we show three different extensions of this PoS where useful
data can be embedded into the space required by the prover. Our security proof
for the PoS extends (non-trivially) to these constructions. We discuss how some
of these variants can be used as proofs of catalytic space (PoCS), a notion we
put forward in this work, and which basically is a PoS where most of the space
required by the prover can be used to backup useful data. Finally we discuss how
one of the extensions is a candidate construction for a proof of replication (PoR),
a proof system recently suggested in the Filecoin whitepaper. '
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- 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: 'Pietrzak KZ. Proofs of catalytic space. In: 10th Innovations in Theoretical
Computer Science Conference (ITCS 2019). Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2018:59:1-59:25. doi:10.4230/LIPICS.ITCS.2019.59'
apa: 'Pietrzak, K. Z. (2018). Proofs of catalytic space. In 10th Innovations
in Theoretical Computer Science Conference (ITCS 2019) (Vol. 124, p. 59:1-59:25).
San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPICS.ITCS.2019.59'
chicago: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In 10th Innovations
in Theoretical Computer Science Conference (ITCS 2019), 124:59:1-59:25. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2018. https://doi.org/10.4230/LIPICS.ITCS.2019.59.
ieee: K. Z. Pietrzak, “Proofs of catalytic space,” in 10th Innovations in Theoretical
Computer Science Conference (ITCS 2019), San Diego, CA, United States, 2018,
vol. 124, p. 59:1-59:25.
ista: 'Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical
Computer Science Conference (ITCS 2019). ITCS: Innovations in theoretical Computer
Science Conference, LIPIcs, vol. 124, 59:1-59:25.'
mla: Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” 10th Innovations in
Theoretical Computer Science Conference (ITCS 2019), vol. 124, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:10.4230/LIPICS.ITCS.2019.59.
short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference
(ITCS 2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25.
conference:
end_date: 2019-01-12
location: San Diego, CA, United States
name: 'ITCS: Innovations in theoretical Computer Science Conference'
start_date: 2019-01-10
date_created: 2020-01-30T09:16:05Z
date_published: 2018-12-31T00:00:00Z
date_updated: 2021-01-12T08:13:26Z
day: '31'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.59
ec_funded: 1
file:
- access_level: open_access
checksum: 5cebb7f7849a3beda898f697d755dd96
content_type: application/pdf
creator: dernst
date_created: 2020-02-04T08:17:52Z
date_updated: 2020-07-14T12:47:57Z
file_id: '7443'
file_name: 2018_LIPIcs_Pietrzak.pdf
file_size: 822884
relation: main_file
file_date_updated: 2020-07-14T12:47:57Z
has_accepted_license: '1'
intvolume: ' 124'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/194
month: '12'
oa: 1
oa_version: Published Version
page: 59:1-59:25
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
publication_identifier:
isbn:
- 978-3-95977-095-8
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Proofs of catalytic space
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2018'
...