QUANTUM COMPUTERS AND THEIR IMPACT ON CRYPTOECONOMICS - Gavin K Brennen

it's its pleasure be here it's usually speaking too nerdy physicists and I'm glad to get a different crowd with a lot of different expertise and you might actually have some ideas that are thinking outside the box of what we've been thinking about but yes so I'm a physicist but what got me interested in this topic was hype basically there were a lot of articles that came out in 2016-2017 especially about how crypto currencies like Bitcoin we're going to be destroyed by quantum computers and you should sell now because these things would last even for a couple years and yeah I mean even just this year they've been several about quantum computing threats to crypto currencies and

blockchain in general can it be hacked with quantum computers where does the threat to Bitcoin and then just this funny collection just today actually I saw the first thing I saw my my type tip threats to crypto came this this Forbes article NASA to develop a quantum resistant cryptocurrency and then and then I mean look at Gizmodo that no NASA did not say that it's not developing means don't prickly currency and then I'm actually the story is that the NSA is looking at the quantum resistant clip do okay someone got excited on third but there's a lot of money to be made in crypto so this is just from coin market cap today the capitalization of all the

cryptocurrencies is about two hundred and sixty three billion and bitcoin is by far the dominant currency at seventy one percent there was a big spike in December of 2017 and people were hoping that would reach one trillion market capitalization overall but those folks got moderated and now we're back in territory which is relatively stable for the kinds of things but you know people want to know how they can make money and whether you could actually use quantum computers to try to steal Bitcoin all right so I don't know what people's expertise is or what you've heard about quantum computing so I'm just gonna give you a lightning statements about it but we do have in existence some prototype

devices so Google has probably the largest quantum computer 72 qubits qubit is a quantum bit and you can see it's this big thing that has to be run at extremely cold temperatures liquid helium temperatures and it's extremely difficult to work with it's very noisy they can't run many gates they can you know the depth of the circuits they can run is quite quite shallow and you know this is nowhere near any kind of desktop device but there's been a lot of research and IBM Microsoft Intel as well as some startups like Righetti computing in Berkeley psych you in Silicon Valley I am Q and Alpine in Europe and us so as many companies and then there's a

silicon computing based here you need to receive New South Wales so just to give you just a brief look another hood of a quantum computer let's just look at what a classical computers do well what do you need for a classical computer not much actually the ability prepared bits in a 0 or 1 state and well actually you can do everything with one type of gate the tottaly gate which is a reversible and gate and normally you don't do that of course they use irreversible gates like and and or is it cetera but you can do everything with reversible gates for a quantum computer you put a little vector sign on your zero and you're

wanting to call them States and you're allowed to prepare qubits in the state 0 or 1 you can also do the game but you get one extra thing provided by the laws of physics how to mark gate which can take a zero and spit out a superposition of 0 and 1 and a 1 which is a superposition of 0 and 1 but with a minus sign on those components and this can take an arbitrary input and act as an operator to give you the appropriate outlet just accidentally it's not really that much of a change it looks like you've just changed the laws a little bit allowing for super positions and when you include super

positions over many different bits that gives you a property called entanglement and that turns out to be powerful enough to give you dramatic improvements in your processing power so let's look at just a couple logarithms which are quite important and happen to be useful in the context of crypto currencies the first is known as Grover's algorithm and this is a quantum algorithm discovered by love Grover in the late 90s and the idea is to search an unstructured database of size capital N and it can do so in time square root of n in fact that it's constant is like PI over 4 x squared of n and okay well maybe you don't stumble a prom across unstructured data bases

too frequently but the important thing is that you can use this to invert one-way functions so if you have a function f I can add an input X that gives you an output Y and you have the output Y and you know the function but you want to know the preimage X you can find it with this provided you can implement the function efficiently which you can do with one-way functions so this will generically give you a quadratic speed-up over classical computers and as I'll explain this is very useful for crypto mining and just to give you a rough sketch of what these things look like we tend to draw circuits like this where these are a

spacetime diagram so what happens in a quantum computer so you have space along this axis and time along this axis so this is like one qubit that's flowing forward in time there's another qubit etc you start off with the qubits in superposition States a zero and one for each one and so you take the product of all those and you get a product of sum over all possible input bit strings then you put that into your function call whatever it is it could be a one-way function it will act linearly on all those bit strings at the same time and that on its own is not very good because if you just have that you still would need to measure the

output and you'd only have an exponentially small probability to actually get the output you wanted but then you use this thing called a grover operator which basically reinforces the thing you're looking for and destructively removes the answers you're not looking for and if you repeat this on order of square root number of times this whole process you will get an output which is very high probability is the thing you're looking for and in this thing in the case one wave functions it will be the premiums you're looking for if you don't exactly get it you can run it again and with exponentially close exponentially converging probability you'll get the right answer the other algorithm that's very useful is due to

shore actually there's two algorithms to him this was discovered in the mid 90s the first is the discrete log problem and that is to find and exponents given this equation a to the x equals Z so you know what a is you know what Z is you want to find X that's the the essential thing you would need to do in order to find the private key in elliptic curve digital signal [Music] the other one is for factoring so if you're given a composite number and you want to find its prime factors that's what you need to do to crack RSA and Shores algorithms will do this so these algorithms will realize an exponential or a quasi exponential speed-up over the

best known classical logarithms and it was just a sketch of what segments of Shor's algorithm for cracking discrete logs it involves a bunch of qubits are coming in and some these patum are gates and a bunch of more controlled gates there's this thing called the QFT which is a quantum Fourier transform and it's a kind of thing that you can look in a textbook and it's it's pretty straightforward and it's something that's actually being taught a lot more now in undergraduate courses in physics and computer science okay so some cryptocurrencies now because of the existence of Shor's algorithm have actually started to adopt using post quantum cryptography which is cryptography that is thought to be

secure against quantum computer attacks and just some of these are our hyper cache which uses a lot of space post quantum ring protocol there's another one called quantum resistant ledger based in the UK that uses a hex MSS have a signature scheme dab cache using a ring signature scheme and card Don oh yeah you know they say that they haven't developments a post quantum signature scheme as well as a proof of stake scheme Ouroboros which they claim is quantum security so there are there is financial interest of doing this and people are spending money on it so before getting on to crypto parenthesis I don't know what people know about mining and so forth I find it helpful to

just understand the history of this little bit actually the idea behind how you mind for cryptocurrencies it really goes back to you know the early 90s when people were trying to find a way to fight spam and there was this protocol called Hashcash so the idea of hashcash was to make it costly to send email by requiring the sender to solve a hard problem which is a good idea and it used a concept called proof of work which is the idea that it requires much computational effort to solve a problem but the proof can be verified efficiently so in a context of email you would in order to be able to send an email you would need to calculate some

problem which would require the expense of CPU time and then if it's exceeded that you can send it but the receiver could quickly check that you actually solve that problem and that is a valid email so you might have to send a kind of header like this and basically given some recipients address and some time and date stamp then the sender is to work out an extra piece and nonce to add to this whose hash has a certain number of leading zeroes so for example the first 20 bits of the hash well zeros and that's considered a successful mining to be able to send the email then the recipient receives this and can quickly compute the hash and check that indeed

the sender's the work to do that so it's a good way to slow down spamming tons of people with terrible ads for enlargements so now this was using a hash function and hash functions happen to be highly nonlinear functions they're her stupid functions are just adding multiplying shifting and so forth registers bit strings but they're high entropy in the sense that if you say you take a stream like this the quick brown fox jumps over the lazy dog and you change one letter there the outcome is vastly different so it's highly sensitive to the input and originally in Hashcash was proposed to use a sha-1 which has takes an input of a 202 to the

64 bit message input up to that level and that puts 160 bit message digest it was found though by cryptographers that this is actually vulnerable because of the existence of collisions which make this not so secure so they moved on to then using sha-256 which has better security and outputs a 256 bit message this happens to be also is used in Bitcoin so Bitcoin uses the essential same idea as half cash but applies it to digital currency so it takes the the idea that's you want to make legitimating new transactions on the network difficult and that's in order to avoid something called double spending which I'll explain shortly but the idea is that you've got whenever you want to

have a transaction occur so you want to you want to buy a car with Bitcoin or do whatever transaction you want to do with it you you propose that you want to you know sense a Bitcoin from yourself to some receiver and this is you will attempt then to add it as a block with some other transactions to their blockchain it's a chain because the blocks are all connected to earlier blocks which gives you a permanent sort of ledger which cannot be corrupted and tampering the past blocks is detectable in the future blocks so this will avoid being able to cheat the system and the two components that quantum computers will come into play is the possibility

to affect how quickly you can verify transactions which is called mining and also being able to spoof signatures on claiming ownership of bitcoins when you send it so let's first look at a mining attack by a quantum computer or just in general any fast computer so the idea is that if you have a blockchain for example for Bitcoin it's it's a records of as I said the each block carries many transactions and in order for your transaction to be verified you have to solve a problem like solving one of these one-way functions or in particular you need to solve something very similar to what hash hash needed to do or you have to work out what is this

extra string of bits I need to add two hash of a previous blog in order to have that hash be less than some number so it's just it's a dumb problem that you have to keep calculating over and over and over again until you happen to find the right answer but if you have really big computing resources what you can do is let's say that there is a valid chain here and this includes records of you know valid transactions of the network degrees 2 and let's say one of the players says ok I'm gonna send a 100 Bitcoin to buy a car but at the same time this this person has very strong and powerful computational resources and

keeps another chain going which doesn't include that history of that transaction now if his chain can get long enough is he be if he was able to solve these proof of work problems faster than anyone else his chain will actually get longer than the valid chain and the other members of the network will decide oh I'll go with the longer chain because that should be a more valid one and now he would have been able to not have any record than having spent his Bitcoin but haven't received the the car over ever he did to to spend it on so if you have powerful computational resources you can do this kind of attack which is called double

spending you basically you're being able to spend without a record of having you spent and here's how this could be done on a quantum computer so basically what you need to do with Bitcoin is you want the hash of some header to be less than some value T just like with Hashcash you wanted to have some money some number of leading zeroes and actually with Bitcoin you have to hash the hash so you double patch it and classically the number of runs of trial headers you need to apply scales with some quantity called capital D the difficulty and the difficulty is something that's actually set by the network dynamically according to the computational power across the globe so

as of today the difficulty is ten point eight Tara hashes so ostensibly you know if computers become faster that's difficult to become higher so that's what is designed is that Bitcoin is a network so that designs so that you will get an acceptance of new transactions approximately every ten minutes and without any structure to the hashing function the best we could expect as a speed-up from quantum computers is the grover speed-up which is a square root yeah so let's work under that assumption and see what consequences there would be all right so here's the sketch of the Grover attack on mining we'll let n be 2 to the 256 that's 256 bits and we're gonna set some probability very very

high that a random sets of is with 10 times and block headers will contain at least one element satisfying the hash of that header is less than the prescribed value record the Bitcoin network and then we fix some deterministic easily computed function which basically spits out this string of zeros and ones which will be the block headers and then we define an indicator function which is zero if the hash of this this function G is greater than T and one if it's less than T so it's just like a decision problem now if your header is good it's a 1 if it's not as a zero and then we can apply Grover's algorithm where we

take an input over all possible headers apply this function and it will do so in superposition all at once it will apply a minus sign on the components of the superposition where you have this this condition satisfied and put just a 1 if it's not satisfied and the total number of times you will need to call this function then will scale like the square root of the difficulty Thanks as opposed to the classical algorithms which will scale out the difficulty anyway you can work out what the circus look like for this to implement these hashing functions and they're pretty straightforward they can be done efficiently on a quantum computer but the rub is that quantum computers are

very delicate they're subject to noise in ways that are class computers aren't they have to worry about fluctuating electric fields magnetic fields people walking into the lab and you need to use very sophisticated error correction techniques this imposes an overhead so each each physical bit of their system is actually only very very small part of a logical bit and you need to then do kinds of these kinds of encodings where you know a single zero bit of your computation might be encoded in thousands of physical bits these all need to be controlled and this is a kind of thing they're trying to do at Google so in the end you need to include the overheads due to all these extra qubits

you need to make things tolerant errors as well as the fact that quantum gates might not be as fast as classical gates so in fact if we look at what classical computers can do with ASIC devices you can reach place you know 14 tera hashes per seconds using one of these and other devices and even if you include parallelism for quantum computers the advantage we get is very modest so we looked at the kind of effective caching rate you would get for a quantum computer assuming a 50 gigahertz clock speed which is very very optimistic and look at it as a function of difficulty the network and the error rates of the gates and what you end up finding is

that the hashing wave isn't terribly fast compared to what you would get from when these HD devices and the number of cuba's you need is tens of millions so in fact if we just look at the average clock speed now for quantum computers the effective paths for able to be about 13.8 Giga hashes per second which is a thousand times slower than current basic devices so quantum computers are actually not too much of a threat to Bitcoin mind and we can actually give some estimates on how things might improve so we looked we took some data from current devices in terms of how many qubits are being actually built that worked the gate speed for the corner computers and

the gate error rate and you can do some sort of economic type forecasting where you do curve fitting and then do some optimistic versus pessimistic scaling performance of these three things and you go with you know kind of quantum Moore's law and then we can look at the likelihoods of quantum computer is actually having a substantial threat to the Bitcoin mining and you see that even if you park masticate way out into 2045 the this is on a log scale here the fractional hashing capability of quantum computers is going to be much less than the estimated of the Bitcoin network all right so I'm getting low on time I just want to finish up with how you can use

quantum attacks and signatures you can use this discrete log problem to crack elliptic curve digital super algorithms and this is what we estimate for the likelihood of a quantum computer to be able to crack the 256 bit elliptic curve digital signatures based on the current growth in the number of qubits speed of gates and quality of gates so in a very optimistic scenario we can see this cracked in less than ten minutes in ten years more likely though will be 15 years or so all right so I'll just leave it there for now Thanks [Applause] you