[math-fun] Post-quantum proof-of-work system?
If you were not worried about having exponentially large memory for a classical computer I suppose to be fair we should allow this for a quantum computer too. In that case, you could have the quantum computer seek 2^(n*C) words, at least two of which agree about the first n bits of their hash. This has probability of occurrence that is of order 2^(-max(1-2*C, 0)*n) if random words are tried. Now there are versions of Grover search algorithm, which run in expected #steps proportional to about squareroot(1/p) where p=probability of occurrence. If time for a step is here 2^(n*C), then total time is of order 2^( (C + max(1-2*C,0)) * n ) which is optimized by choosing C=1/3, which causes the quantum runtime to be of order 2^( n*2/3 ). So... no. The quantum computer here is faster than the classical algorithm, so Adam Goucher's proposal only partially worked. While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind. Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever). Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken. These still will be busted by quantum computers though (which bust the PKC schemes that were used).
Warren Smith wrote:
While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind.
?! Have you read the original paper? It's quite a beautiful system.
Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever).
It already uses about half of the world's computing power, apparently. Of course, one can replace the proof-of-work system with something different (and useful), such as how PrimeCoin resulted in vast quantities of Cunningham chains being discovered. Basically, the proof-of-work can be anything that's in NP but not in P. And ideally we don't want quantum computers to be vastly better than classical computers, although it doesn't matter too much when quantum computers go mainstream (since then the `honest nodes' will again have more processing power than `attacker nodes').
Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken.
How do you prevent double-spending without either a proof-of-work-driven blockchain (a la Bitcoin) or a centralised server (in which case the owners can cheat)?
These still will be busted by quantum computers though (which bust the PKC schemes that were used).
It's fairly easy to replace every instance of `elliptic curve DSA' with `lattice-based cryptography' to make a public-key cryptosystem resistant to quantum computers.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Adam P. Goucher -
Warren D Smith