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 slides
