Firstly, note that `essentially serial' proofs of work, by definition, do not conform to the `one vote per CPU' paradigm required for a Bitcoin protocol. However, since you asked the question, integer factorisation seems to have this property. Specifically, it's painfully slow to use anything other than the General Number Field Sieve, and that's both sequential and complicated -- GPUs and ASICs won't help you. Also, it can be checked really quickly (multiplication takes O(n log n log log n) time). Sincerely, Adam P. Goucher
Sent: Tuesday, August 05, 2014 at 3:09 AM From: "Henry Baker" <hbaker1@pipeline.com> To: math-fun@mailman.xmission.com Subject: [math-fun] "Essentially serial" computations for PoW ?
If there are any computational complexity theorists out there, I was wondering if there were any examples of "essentially serial" computations, in which no amount of parallelism (and no amount of memory) can speed it up. I.e., the only speedup comes from a faster CPU clock.
Obviously, one can use a Turing Machine to "diagonalize" over all Turing Machines with smaller time & space, but this doesn't say much about access to huge amounts of parallelism.
The goal is a Bitcoin-type "proof of work" in which buying more computers won't help at all; hopefully the speedup of special hardware over a random laptop or cellphone would be perhaps 3 orders of magnitude, but not more.
Any links/pointers would be welcomed.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun