Non-Parallelizable Hashcash

Change the hashcash assignment from “find x such that H(x) starts with N zeroes” to “find x[1]…x[k] such that H(x[1]), H(x[1] || x[2]), H(x[1] || … || x[3]), … H(x[1] || … || x[k]) all start with N zeroes” and you can twiddle N and k to trade off between verification speed and parallelizability. (The double bars mean string concatenation here.)

Also, I believe there are many hash functions where you almost necessarily calculate H(A) as part of calculating H(A || B). (For example, I believe SHA1 has this property.) If that’s the case, then there is very little cost in verification speed. The only cost of increasing k is that your nonces get longer.

changed January 14, 2011