It's clear that, as a first pass, Hashcash is in FNP. For instance, say that R(x,y) is a binary relation, where x is a "maximum" target hash, and y is an input string (working block + nonce), R(x,y) ...
A long time ago, I read that the definition of "cryptographic hash function" is "collision-resistant one-way function". (A similar definition shows up in the FIPS standards for SHA-1 etc.) But this ...
I am looking for a proof-of-work scheme which cannot be effectively parallelized. For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target ...