Paper 2016/145

Designing Proof of Human-work Puzzles for Cryptocurrency and Beyond

Jeremiah Blocki and Hong-Sheng Zhou

Abstract

We introduce the novel notion of a Proof of Human-work (PoH) and present the first distributed consensus protocol from hard Artificial Intelligence problems. As the name suggests, a PoH is a proof that a {\em human} invested a moderate amount of effort to solve some challenge. A PoH puzzle should be moderately hard for a human to solve. However, a PoH puzzle must be hard for a computer to solve, including the computer that generated the puzzle, without sufficient assistance from a human. By contrast, CAPTCHAs are only difficult for other computers to solve --- not for the computer that generated the puzzle. We also require that a PoH be publicly verifiable by a computer without any human assistance and without ever interacting with the agent who generated the proof of human-work. We show how to construct PoH puzzles from indistinguishability obfuscation and from CAPTCHAs. We motivate our ideas with two applications: HumanCoin and passwords. We use PoH puzzles to construct HumanCoin, the first cryptocurrency system with human miners. Second, we use proofs of human work to develop a password authentication scheme which provably protects users against offline attacks.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
Proof of Human WorkDistributed ConsensusCryptocurrencyHumanCoinBitcoinCAPTCHAPassword Protection
Contact author(s)
hszhou @ vcu edu
jblocki @ purdue edu
History
2016-08-24: revised
2016-02-16: received
See all versions
Short URL
https://ia.cr/2016/145
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/145,
      author = {Jeremiah Blocki and Hong-Sheng Zhou},
      title = {Designing Proof of Human-work Puzzles for Cryptocurrency and Beyond},
      howpublished = {Cryptology ePrint Archive, Paper 2016/145},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/145}},
      url = {https://eprint.iacr.org/2016/145}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.