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