[math-fun] Post-quantum proof-of-work system?
The usual proof-of-work system involved in things such as Bitcoin mining is the following: "Find a string S such that hash(S) begins with n leading zeroes" A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining. Instead, I propose the following alternative proof-of-work system: "Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits" Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following: 1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree. The probability of success as a function of n is bounded below due to the birthday paradox. A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method: 1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits. And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory. Sincerely, Adam P. Goucher
The requirement that the classical computer have memory O(2^(n/2)) is restrictive -- more than 10^25 TB for BitCoin's 256-bit hashes, for example. The quantum computer needs only store around 256 qubits + error correction as I understand Grover's algorithm. Even if you dialed it back to 128 bits you're talking about 2 EB which is more than we're presently able to sort over. (Maybe with a sorting network, which would also change the n to a log n in the time factor IIRC. Of course that comes at the cost of making all your storage 'smart' which is undoubtedly more expensive than just plain hard drives.) Charles Greathouse Analyst/Programmer Case Western Reserve University On Sun, Jul 13, 2014 at 8:37 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
The usual proof-of-work system involved in things such as Bitcoin mining is the following:
"Find a string S such that hash(S) begins with n leading zeroes"
A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining.
Instead, I propose the following alternative proof-of-work system:
"Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits"
Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following:
1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree.
The probability of success as a function of n is bounded below due to the birthday paradox.
A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method:
1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits.
And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Quantum computers can get some speedup for this kind of "collision problem": I believe their running time would be O(2^(n/3)) in this case. See http://arxiv.org/abs/quant-ph/9705002 http://arxiv.org/abs/quant-ph/0112086 Best, Cris On Jul 13, 2014, at 6:37 AM, "Adam P. Goucher" <apgoucher@gmx.com> wrote:
The usual proof-of-work system involved in things such as Bitcoin mining is the following:
"Find a string S such that hash(S) begins with n leading zeroes"
A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining.
Instead, I propose the following alternative proof-of-work system:
"Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits"
Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following:
1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree.
The probability of success as a function of n is bounded below due to the birthday paradox.
A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method:
1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits.
And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Finding collisions can be done on a quantum computer in O(2^(n/3)) time on a quantum computer. http://arxiv.org/abs/quantph/9705002 On Sun, Jul 13, 2014 at 5:37 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
The usual proof-of-work system involved in things such as Bitcoin mining is the following:
"Find a string S such that hash(S) begins with n leading zeroes"
A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining.
Instead, I propose the following alternative proof-of-work system:
"Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits"
Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following:
1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree.
The probability of success as a function of n is bounded below due to the birthday paradox.
A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method:
1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits.
And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
participants (4)
-
Adam P. Goucher -
Charles Greathouse -
Cris Moore -
Mike Stay