Cryptology ePrint Archive: Report 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.

Category / Keywords: Proof of Human Work, Distributed Consensus, Cryptocurrency, HumanCoin, Bitcoin, CAPTCHA, Password Protection

Original Publication (with minor differences): IACR-TCC-2016

Date: received 16 Feb 2016, last revised 24 Aug 2016

Contact author: hszhou at vcu edu; jblocki@purdue edu

Available format(s): PDF | BibTeX Citation

Version: 20160824:185521 (All versions of this report)

Short URL: ia.cr/2016/145

Discussion forum: Show discussion | Start new discussion