Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

We generally use hash functions as prof of work, for example we ask client to compute $x$ where $h(y|x)$ produce a sum starting with 64 successive zero bit.

In cryptographic algorithms we can benchmark how much computation is required for one operation and estimate how many cycles this operation cost on general CPUs. But using a hash function as proof of work can't be predictable and each client faces random amount of work to compute $x$. Is there any proof of work scheme with same characteristic that we can for sure say this work will cost 100 million cycles on Intel's dual-core CPUs without expensive verification for verifier?

share|improve this question
If it's no problem that the verifier creates the challenge and can cheat, you can use Rivest's timelock puzzle. –  CodesInChaos Dec 15 '13 at 14:05
is there any implementation for Rivest timelock puzzle? and is that really cost effective as hash functions to verify ? –  cheapcoin Dec 15 '13 at 14:32
It depends on what platform and coding language you want to have an implementation for… this link shows (among other related things) a Python implementation of Rivest's timelock puzzle. –  e-sushi Dec 16 '13 at 9:24
As an alternative you could use hashcash style proof of work, but with the challenger submitting 100 nonces. That will still have variable runtime, but it will peak around the target value with outliers being very rare. –  CodesInChaos Dec 17 '13 at 8:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.