Consensus from proof-of-work puzzles

Supervisor(s)Univ.-Prof. Dr. Rainer Böhme


This thesis analyzes the role of puzzles in blockchain-based distributed systems. It extracts the relevant properties from existing puzzle mechanisms and uses them to define an abstract notion for proof-of-work puzzles. The resulting puzzles have exponentially distributed solving time and allow to consider nodes and parties with individual solving capabilities. The the new definition of proof-of-work puzzles is used in a bottom-up construction of a blockchain protocol. The new model is compatible with the Bitcoin backbone protocol in the sense that the backbone protocol’s properties can be transferred to it.


  • Garay, J. and Kiayias, A. The Bitcoin Backbone Protocol: Analysis and Applications. In E. Oswald and M. Fischlin, eds., Advances in Cryptology (Proceedings of EUROCRYPT). LNCS 9057, Springer, Berlin Heidelberg, 2015, pp. 281–310.