Proof Systems for Sustainable Decentralized Cryptocurrencies

Abusalah, Hamza (2018) Proof Systems for Sustainable Decentralized Cryptocurrencies. PhD thesis, IST Austria.

[img] Text
THESIS.pdf - Published Version
Available under License All rights reserved.
Download (855Kb)
[img] Archive
Restricted to Repository staff only
Available under License All rights reserved.
Download (1981Kb) | Request a copy


A proof system is a protocol between a prover and a verifier over a common input in which an honest prover convinces the verifier of the validity of true statements. Motivated by the success of decentralized cryptocurrencies, exemplified by Bitcoin, the focus of this thesis will be on proof systems which found applications in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies. In particular, we focus on proofs of space and proofs of sequential work. Proofs of space (PoSpace) were suggested as more ecological, economical, and egalitarian alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling lower bounds, and are therefore complex. Moreover, when these PoSpace are used in cryptocurrencies like Spacemint, miners can only start mining after ensuring that a commitment to their space is already added in a special transaction to the blockchain. Proofs of sequential work (PoSW) are proof systems in which a prover, upon receiving a statement x and a time parameter T, computes a proof which convinces the verifier that T time units had passed since x was received. Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics, Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come up with more than one accepting proof for any true statement. In this thesis we construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and unlike current constructions of PoSW, which either achieve efficient verification of sequential work, or faster-than-recomputing verification of correctness of proofs, but not both at the same time, ours achieve the best of these two worlds.

Item Type: Thesis (PhD)
DOI: 10.15479/AT:ISTA:TH_1046
Additional Information: The following papers are part of my Ph.D. work, and this thesis is based on the first two: Reversible Proofs of Sequential Work. In submission. Coauthored with: Chethan Kamath, Karen Klein, Krzysztof Pietrzak, Michael Walter. Beyond Hellman’s Time-Memory Trade-Offs with Applications to Proofs of Space. Appeared in: ASIACRYPT (2) 2017: 357-379. Coauthored with: Joël Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, Leonid Reyzin. Offline Witness Encryption. Appeared in: ACNS 2016: 285-303. Coauthored with: Georg Fuchsbauer, Krzysztof Pietrzak. Constrained PRFs for Unbounded Inputs with Short Keys. Appeared in: ACNS 2016: 445-463. Coauthored with: Georg Fuchsbauer. Constrained PRFs for Unbounded Inputs. Appeared in: CT-RSA 2016: 413-428. Coauthored with: Georg Fuchsbauer, Krzysztof Pietrzak.
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Pietrzak Group
Depositing User: Hamza Abusalah
Date Deposited: 18 Sep 2018 12:12
Last Modified: 01 Oct 2018 14:08

Actions (login required)

View Item View Item