Designing Proof of Human-Work Puzzles for Cryptocurrency and Beyond
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 human invested a moderate amount of effort to solve
- PDF / 404,837 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 43 Downloads / 262 Views
2
Purdue University, West Lafayette, USA [email protected] Virginia Commonwealth University, Richmond, USA [email protected]
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 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.
1
Introduction
The emergence of decentralized cryptocurrencies like Bitcoin [45] has the potential to significantly reshape the future of distributed interaction. These recent cryptocurrencies offer several advantages over traditional currencies, which rely on a centralized authority. At the heart of Bitcoin-like cryptocurrencies is an efficient distributed consensus protocol that allows for all users to agree on the same public ledger. When combined with other cryptographic tools like digital signatures the distributed consensus protocol prevents users from engaging in dishonest behavior like “double spending” their money or spending another user’s money. Fundamentally, the applications of a tamper-proof blockchain like the one in Bitcoin are not limited to cryptocurrency. For example, a tamper proof blockchain could help us construct secure and fair multiparty computation protocols [1,7,36,38], develop smart contracts [38,53], and build distributed autonomous agents, to name a few applications. In this paper we propose a fundamentally new technique, Proofs of Human-work (PoH), for constructing a secure blockchain, and we show that our techniques have several other valuable applications like password protection and non-interactive bot detection. c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part II, LNCS 9986, pp. 517–546, 2016. DOI: 10.1007/978-3-662-53644-5 20
518
J. Blocki and H.-S. Zhou
At its core, Bitcoin’s distributed consensus protocol is based on moderately hard Proofs of Work (PoW) [23]. In Bitcoin the Hashcash [3] PoW puzzles are used to extend the blockchain, a cryptographic data-structure in which the public ledger is recorded. A PoW puzzle should be moderately hard for
Data Loading...
