Proof systems for sustainable decentralized cryptocurrencies Dissertation Thesis


Author(s): Abusalah, Hamza
Advisor(s): Pietrzak, Krzysztof
Committee Chair(s): Lampert, Christoph
Committee Member(s): Chatterjee, Krishnendu
Title: Proof systems for sustainable decentralized cryptocurrencies
Affiliation IST Austria
Abstract: 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.
Publication Title: IST Dissertation
Degree Granting Institution: IST Austria  
Degree: PhD
Degree Date: 2018-09-05
Start Page: 1
Total Pages: 59
Sponsor: European Research Council, ERC Starting (259668-PSPC) and Consolidator (682815-TOCNeT) Grants
DOI: 10.15479/AT:ISTA:TH_1046
Notes: The research in this thesis was carried out under the financial support of the European Research Council, ERC Starting (259668-PSPC) and Consolidator (682815-TOCNeT) Grants.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work