11-21-2020, 07:12 AM
Can a Quantum Computer break Bitcoin/Blockchain?
<!-- SC_OFF --><div class="md"><p>I was asked to make this it’s own thread, so here you go: A very simplified explanation on the foundational mathematical principle powering encryption and Blockchain. </p> <p>Can a Quantum computer take over the hash power of the Bitcoin blockchain? Maybe, but that isn’t the point being made here. This is about whether the “code” that powers blockchain can be “hacked” by more powerful computers. Answer:</p> <p>Most likely never. Mathematically <em>extremely</em> improbable.</p> <p>The mathematical principle that protects Bitcoin and other cryptocurrencies is <strong>P vs NP</strong> (<a href="https://en.wikipedia.org/wiki/P_versus_NP_problem">https://en.wikipedia.org/wiki/P_versus_NP_problem</a>) and it is a Millenuem Problem (<a href="https://en.m.wikipedia.org/wiki/Millennium_Prize_Problems">https://en.m.wikipedia.org/wiki/Millennium_Prize_Problems</a>). </p> <p>In simple terms, it poses the following question: <strong>Can you go from the solution of any math problem to the inputs in the same amount of time as you can go from those inputs to the solution?</strong></p> <p>An example of this is the problem <code>a * b = c</code>. If you have <code>a</code> and <code>b</code> then you can get <code>c</code> <em>instantly</em> by simply multiplying <code>a</code> and <code>b</code> together. Now, can you go from <code>c</code> and get both <code>a</code> and <code>b</code> in the same amount of time? </p> <p><strong>No.</strong> You would need to go through all the factors of <code>c</code>. Ex. 20 has the factors (1, 20) (2, 10) and (4, 5). That’s 3 checks to go from 20 to (4, 5) and only 1 operation to go from (4, 5) and 20. </p> <p>Now, with Bitcoin it’s more like having 10,000 inputs and one output (the transaction data is the inputs and the signature is the output). The output is data, but all data can be represented by a number. So the data for a Bitcoin signature is a very, <strong>very</strong> large number. </p> <p>The average Bitcoin signature data is 70.5 bytes, this is 565 bits. This means the max integer value a signature can be is:</p> <p><code>60383398797144661635864873295812302254670739526663046854019300803929986598274381633378027602842540280663494000492221518396329354078796682120982948022923136698390325231615</code></p> <p>That is of the magnitude of 10<sup>170</sup> which is unimaginably <strong>HUGE</strong>. </p> <p>That means in order to crack Bitcoin, you’d need to be able to calculate all the different factors of a number that large in a reasonable amount of time. Which is practically impossible. Let’s say the best quantum computer in the year 3,500 can do it in 10 years. Well, if you simply double the signature size from 70.5 bytes to 141 bytes, the max number just grew <em>exponentially</em> to:</p> <p><code>3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731088046102104871310118026124429524895811057809162863601918344981537942578416978660114536064864566618194697491810552574682390899399042017045361314411594716462268422176512674372084045971455.</code></p> <p>That is 10<sup>341</sup> which is astonishingly large. </p> <p>And the principle that makes this all work: If you know <code>a</code> and <code>b</code> you can get <code>c</code> instantly no matter how large the numbers are. If you know <code>c</code> and <code>b</code> you can get <code>a</code> instantly no matter how large the numbers are. <strong>BUT</strong> if you only know <code>c</code> it will take an unfathomable amount of time and energy to get <code>a</code> and <code>b</code> and no matter how quickly you can get an answer the programmers can just keep increasing the byte size at no cost to the instantaneous math and you’ll never be able to catch up no matter how powerful a computer you make.</p> </div><!-- SC_ON --> Kind Regards R
<!-- SC_OFF --><div class="md"><p>I was asked to make this it’s own thread, so here you go: A very simplified explanation on the foundational mathematical principle powering encryption and Blockchain. </p> <p>Can a Quantum computer take over the hash power of the Bitcoin blockchain? Maybe, but that isn’t the point being made here. This is about whether the “code” that powers blockchain can be “hacked” by more powerful computers. Answer:</p> <p>Most likely never. Mathematically <em>extremely</em> improbable.</p> <p>The mathematical principle that protects Bitcoin and other cryptocurrencies is <strong>P vs NP</strong> (<a href="https://en.wikipedia.org/wiki/P_versus_NP_problem">https://en.wikipedia.org/wiki/P_versus_NP_problem</a>) and it is a Millenuem Problem (<a href="https://en.m.wikipedia.org/wiki/Millennium_Prize_Problems">https://en.m.wikipedia.org/wiki/Millennium_Prize_Problems</a>). </p> <p>In simple terms, it poses the following question: <strong>Can you go from the solution of any math problem to the inputs in the same amount of time as you can go from those inputs to the solution?</strong></p> <p>An example of this is the problem <code>a * b = c</code>. If you have <code>a</code> and <code>b</code> then you can get <code>c</code> <em>instantly</em> by simply multiplying <code>a</code> and <code>b</code> together. Now, can you go from <code>c</code> and get both <code>a</code> and <code>b</code> in the same amount of time? </p> <p><strong>No.</strong> You would need to go through all the factors of <code>c</code>. Ex. 20 has the factors (1, 20) (2, 10) and (4, 5). That’s 3 checks to go from 20 to (4, 5) and only 1 operation to go from (4, 5) and 20. </p> <p>Now, with Bitcoin it’s more like having 10,000 inputs and one output (the transaction data is the inputs and the signature is the output). The output is data, but all data can be represented by a number. So the data for a Bitcoin signature is a very, <strong>very</strong> large number. </p> <p>The average Bitcoin signature data is 70.5 bytes, this is 565 bits. This means the max integer value a signature can be is:</p> <p><code>60383398797144661635864873295812302254670739526663046854019300803929986598274381633378027602842540280663494000492221518396329354078796682120982948022923136698390325231615</code></p> <p>That is of the magnitude of 10<sup>170</sup> which is unimaginably <strong>HUGE</strong>. </p> <p>That means in order to crack Bitcoin, you’d need to be able to calculate all the different factors of a number that large in a reasonable amount of time. Which is practically impossible. Let’s say the best quantum computer in the year 3,500 can do it in 10 years. Well, if you simply double the signature size from 70.5 bytes to 141 bytes, the max number just grew <em>exponentially</em> to:</p> <p><code>3646154850295011369707131011438711095400799139943170490872585628683549034362552065955809589514611470241298944167703929337528884908857116141935206466329731088046102104871310118026124429524895811057809162863601918344981537942578416978660114536064864566618194697491810552574682390899399042017045361314411594716462268422176512674372084045971455.</code></p> <p>That is 10<sup>341</sup> which is astonishingly large. </p> <p>And the principle that makes this all work: If you know <code>a</code> and <code>b</code> you can get <code>c</code> instantly no matter how large the numbers are. If you know <code>c</code> and <code>b</code> you can get <code>a</code> instantly no matter how large the numbers are. <strong>BUT</strong> if you only know <code>c</code> it will take an unfathomable amount of time and energy to get <code>a</code> and <code>b</code> and no matter how quickly you can get an answer the programmers can just keep increasing the byte size at no cost to the instantaneous math and you’ll never be able to catch up no matter how powerful a computer you make.</p> </div><!-- SC_ON --> Kind Regards R