Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

RSA Laboratories

Proofs of Work and Bread Pudding Protocols

Markus Jakobsson and Ari Juels

Citation: Proofs of Work and Bread Pudding Protocols, In B. Preneel, ed., Communications and Multimedia Security, pages 258-272, Kluwer Academic Publishers, 1999.

Abstract: We formalize the notion of a proof of work (POW). In many cryptographic protocols, a prover seeks to convince a verifier that she possesses knowledge of a secret or that a certain mathematical relation holds true. By contrast, in a POW, a prover demonstrates to a verifier that she has performed a certain amount of computational work in a specified interval of time. POWs have served as the basis of a number of security protocols in the literature, but have hitherto lacked careful characterization. In this paper, we offer definitions treating the notion of a POW and related concepts.

We also introduce the dependent idea of a bread pudding protocol. Bread pudding is a dish that originated with the purpose of reusing bread that has gone stale. In the same spirit, we define a bread pudding protocol to be a POW such that the computational effort invested in the proof may be reused by the verifier to achieve a separate, useful, and verifiably correct computation. As an example of a bread pudding protocol, we show how the MicroMint scheme of Rivest and Shamir can be broken up into a collection of POWs. These POWs can not only serve in their own right as mechanisms for security protocols, but can also be harvested in order to outsource the MicroMint minting operation to a large group of untrusted computational devices.

Note: A simple back-of-the-envelope calculation suggests that the distributed MicroMint scheme is very attractive from a business perspective. Consider the setup described in the paper, and assume that a minting cycle yields one billion coins, each valued at a quarter, with a 1% commission levied on merchants. If 10% of the revenue of the minter goes to remunerating participating entities for their computing time, then it is possible to pay more than $0.05/hr. for the computing time of a typical PC, or about $18/month for its overnight computing time.

Click here for paper

Click here for paper

Full Publication List

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.