Wednesday, August 07, 2013

[pifwgize] Sieve-based proof of work

An alternative to Hashcash (and part of Bitcoin) is a random range of large integers about which the prover is asked to produce some number of distinct pairs (n,p) where n is an integer in the range and p divides n.  The answers can be checked quickly.

Presumably the prover will first sieve the range to get small factors than apply more specific factoring techniques to get the remaining up to the desired quantity.

By specifying a range of integers to factor instead of a single one, we can make probabilistic assumptions of the difficulty of the task (similar to the probabilistic difficulty of finding cryptographic hash pre-images).  They are not all going to be RSA-like numbers.

No comments :