Paper 2016/680

Fair Client Puzzles from the Bitcoin Blockchain

Colin Boyd and Christopher Carr

Abstract

Client puzzles have been proposed as a mechanism for proving legitimate intentions by providing ``proofs of work'', which can be applied to discourage malicious usage of resources. A typical problem of puzzle constructions is the difference in expected solving time on different computing platforms. We call puzzles which can be solved independently of client computing resources \emph{fair client puzzles}. We propose a construction for client puzzles requiring widely distributed computational effort for their solution. These puzzles can be solved using the mining process of Bitcoin, or similar cryptocurrencies. Adapting existing definitions, we show that our puzzle construction satisfies formal requirements of client puzzles under reasonable assumptions. We describe a way of transforming our client puzzles for use in denial of service scenarios and demonstrate a practical construction.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. ACISP 2016
Keywords
BitcoinClient PuzzlesDenial of Service ResistanceDistributed ComputationProofs of Work
Contact author(s)
chris carr @ item ntnu no
History
2016-07-06: received
Short URL
https://ia.cr/2016/680
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/680,
      author = {Colin Boyd and Christopher Carr},
      title = {Fair Client Puzzles from the Bitcoin Blockchain},
      howpublished = {Cryptology ePrint Archive, Paper 2016/680},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/680}},
      url = {https://eprint.iacr.org/2016/680}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.