Epicenter - Learn about Crypto, Blockchain, Ethereum, Bitcoin and Distributed Technologies - Ajay Prakash & Gavin Brennen: Qubit Protocol – Quantum Computing & The Coming Threat to Crypto

Episode Date: April 17, 2018

With the advent of mature quantum technologies, many of the critical cryptographic protocols which secure the Internet, financial transactions and even military secrets may become susceptible to new attack vectors. For instance, while it may take a computer millions of years to decipher a public key’s corresponding private key, a sufficiently powerful quantum computer might achieve this in a reasonable amount of time. With this reality looming over us, many in the blockchain space worry that someone with access to a quantum computer might one day have the ability to steal their hard-earned crypto. We’re joined by Ajay Prakash and Gavin Brennen, founders of the Qubit Protocol, a decentralized blockchain-enabled governance protocol that is meant to select and fund the best startups in the quantum world. As a co-author of the recent paper “Quantum attacks on Bitcoin, and how to protect against them,” Gavin walks us through the primary threats that quantum computing poses on Bitcoin. Among the major vulnerabilities are hashing functions and Elliptic Curve algorithms used for digital signatures, both fundamental components of Bitcoin, as well as many other blockchain protocols. Topics covered in this episode: What are quantum technologies and how they differ from the existing paradigm The areas and industries which are to benefit most from quantum computing A refresher on hashing algorithms as one-way functions What a quantum attack on Bitcoin mining might look like How Elliptic Curve digital signature algorithms work and how public and private keys are generated The three types of attacks a quantum computer could perform digital signatures The expected timelines for these attacks to be viable The potential countermeasures which could circumvent quantum attacks on Bitcoin The Qubit Protocol as a DAO to fund quantum technology startups and the challenges of investing in the quantum space The project’s roadmap and upcoming ICO Episode links: Qubit Protocol Quantum attacks on Bitcoin, and how to protect against them Quantum Computers Pose Imminent Threat to Bitcoin Security - MIT Technology Review" Shor's algorithm - Wikipedia Elliptic-curve cryptography - Wikipedia This episode is hosted by Sébastien Couture. Show notes and listening options: epicenter.tv/231

This is Epicenter, Episode 231 with guests, A.J. Prakesh and Gavin Brennan. This episode of Epicenter is brought you by Shapeshift.io, the easiest, fastest, and most secure way to swap your digital assets. Don't run a risk of leaving your funds on a centralized exchange. Visit Shapeshift.io to get started. Hi, welcome to Epicenter, the show which talks about the technologies, projects, and startups driving decentralization and the global blockchain revolution. My name is Sebast and Kutjouill, and today we are going to talk about a topic that I think most people will have heard of, but perhaps need a better understanding in order to fully grasp the potential of this technology, and that is quantum technologies and specifically quantum computing. We've been thinking about this for quite a while at Epicenter and didn't really know how to address. it or from what angle. But while I was here in Singapore, I was fortunate enough to meet someone

who is doing work in this field and told me about a white paper that had been written by his team about the quantum attacks that are possible on Bitcoin and how we can mitigate against those attacks. And so our guests today are A.J. Prakesh, and he is the CEO of the Qbit Protocol. and Gavin Brennan, and Gavin is CCO, chief community officer at QBIT, and Gavin is also an associate professor in physics at Macquarie University in Sydney. And so QBIT is a governance protocol

that is used to select and fund the best quantum technology startups in the world. And so we'll talk about the QBIT protocol, but while we'll spend most of this discussion dissecting quantum technologies and quantum computing, so getting a high level understanding of what these technologies are and how different they are from classical computing or binary computing. And also we'll learn about how quantum technologies and quantum computing can affect the technologies and specifically the algorithms that are used in Bitcoin and a lot of

blockchain. So hashing algorithms, digital signatures, elliptic curves signatures, etc. So guys, super excited to have you on today and to dive into this topic. Yeah, thanks for having us too. Yes, thanks for having us on. All right, so before we dive into the topic of Bitcoin and how Bitcoin can be vulnerable to certain types of quantum attacks, let's perhaps start with describing and keep in mind here that, Some of our listeners are not necessarily engineers or mathematicians or physicists. So, you know, think of it as like an explain like on five exercise here.

Like how would you explain quantum computing to a five-year-old? Sure. Yeah. So it's always good to go back to what you know. Like we think we know classical computing. I mean, everyone is used to using laptops or cell phones and those are all doing classical computing. And if you were to zoom in on the trussical computing. on the transistors there, it would be, you know, involving voltages, which, you know, some amount of voltage would represent a one and some different amount of voltage would be a zero, and all this stuff could be measured, and you would just be doing lots and lots of operations, flipping ones and zeros, doing things like adding and doing NAND gates and or gates and things like that. And of course all this happens incredibly fast, billion operations per second, and at the end, you get out some answer to a problem.

And I mean, a quantum computer is also doing that kind of thing. It has an input and an output. An output is that something you measure and you find whether you've got an answer to your problem. But it's using quantum bits. So if you were to zoom down to really small sizes, like the size of an individual atom or a single photon of light, then the laws of physics really look different than they do in our everyday experience. And you can have, like, instead of a bit, which would just be up or down, zero or one, a quantum bit, a qubit, can be in a rotated superposition, they call it, of zero and one.

And it's really, you can just view it as like a spin that is rotated away from being straight up. And quantum systems can do this. You can have it with electrons, with atoms, with pieces of light. And now the exciting thing is that they're building technologies, with superconductors, where you have current that flows in one direction or another, representing a zero or a one, and you can amazingly get currents that has a zero and a one. So it's going some amplitude to be going in one direction and amplitude to go another direction. And that's a qubit.

And when you get a bunch of these quantum bits together, you get a quantum register, which is part of a quantum computer. And you often hear that quantum computers get their magic from the ability to do parallel processing. So they can act on all the possible bit strings at once, like 0-0-0-1-0-0-0-0-0-0-et- etc. And that's true, but at the end, you only measure one thing. And so if you were just operating on all these things at once and just measuring one thing, you would have an exponentially small probability of getting the right. result. So the real power of quantum computers comes in because you can, in clever design

of an algorithm, you can make it so that the correct solutions to a problem are reinforced by adding up probability amplitudes. And the wrong solutions are cancelled out because in quantum mechanics you can have positive and negative probabilities amplitudes. So you clever design an algorithm so that the right solutions are reinforced, the bad ones cancel out, and at the end you get an answer that's much, much faster than any supercomputer in existence today could ever do. So that's a very brief description of how these things work. Just the way that I understand this is that in binary computing, a single piece of information can be either zero or one or on or off.

In quantum computing, a single piece of information or a qubit can be anywhere on an XYZ axis. So essentially, I think some people would describe that as a sphere. And when you line these qubits up, you can perform computations on it. But the thing that's unique about quantum computing is that because you're measuring quantum particles, as soon as you measure them,

you essentially disrupt their state, and so you can't effectively just look at it and measure it because the light that you used to measure it will disrupt the quantum particle. And so what you need to do is you need to perform many measurements on this, and then with probabilistic functions, one can extract actual meaning or an answer to a function or an algorithm?

Yeah, that's right. So if you imagined it like a spinning top, a classical bit would be like the top can only be pointing up and down. So it's like vertically oriented. A quantum qubit, as you say, could be pointing like anywhere on a sphere, so it could be rotated.

But when you measure it, you can only measure if it's up or down. And once you measure it, it's stuck there. It's in its either up or down state, not in a rotated state. And so the point is you want to design the algorithm so that you can force all the right solutions to a problem to be, say, pointing all up. And then you'll know that those were the ones that had the solution to your problem. Okay. And so why is that this is so much more powerful than binary computing? What are this about these quantum properties that make it so much more powerful?

Yeah, well, so to tell you the truth, we don't know the full answer to that. And actually proving that quantum computers are faster than classical computers is very hard. In many cases, you can't. So, you know, the big example that got everyone excited about quantum computers was Shores algorithm for factoring. and it solves, you know, taking a big number and finding the prime factors quickly, which it does this in polynomial time, I think it's n cubed time where n is a number of bits. And people think that the classical algorithm is hard, so super polynomial, but we don't have a proof of that. it could be that, you know, in five years someone comes up with a fast classical algorithm,

or it could be it's already been found and the NSA is keeping it secret. We don't know. We do know that there are provably some cases where quantum algorithms do better, but having those proofs is actually quite of rare. But we can say generally that quantum computers make use. of some properties that you just can't get with classical physics. And one of the key properties is entanglement, which gives you correlations between qubits

in lots of different directions that you can't get with classical physics. And another one is superposition and interference. This is where you can have the state of a system in a combination of being, up and down with lots of these cubits. So you can have something like 0-0-0-1 and 1-1 and 1-1 at the same time. So yeah, these do the elements of entanglement and superposition and interference are all really new things that show up in quantum physics that give the power. So give us an idea then of like where we are in terms of technology maturity with regard.

as to quantum computing. Like if you were to compare it to, it's like the advent of binary computing, like take maybe like the 50s and like the first computers, the first like electrical computers, electronic computers that were built. Like in terms of timeline, like what's, what's the maturity level? Yeah, we're like in the 1940s. So we're, you know, we're talking like, you'll see press releases coming out from Google and IBM that talk about 52 qubits. And there's a 72 cubit device that Google has announced. However, that device is actually not completely wired up and working. They do have the qubits.

But as of today, it's not a completely working device. So basically, it's like having a regular computer with like a transistor. that has 72 bits of storage or of memory? Yeah, so you could use it for storage, yeah. But it does do some quantum things that a classical computer couldn't do. And the big push right now is to really prove that they can build a device that can do things that would be extremely hard for a classical computer to do. And there's a hope that we'll actually see evidence of that this year.

By the end of 2018, there should be firm evidence that they've got a device that does things that are beyond what our supercomputers can do right now. And so what are the applications? So in terms of advantages over binary computing, quantum computing isn't necessarily better than regular computing for anything. There are specific applications and specific types of computations that are better. Can you describe what those are? At the moment, there are some really cool applications that we're looking at. And I think it's also important to understand that quantum computing is not just the only field in quantum technology. So yes, quantum computing, I think some of the biggest things we're going to see some improvements in

is going to be things like AI and machine learning. And I think Gavin can go into more detail about it, but essentially, quantum computers are really good at multiplying matrices upon each other, which is essentially what AI and machine learning is doing. And then we'll see disruption in all these other fields like supply chain management, financial services, anything that really is to do with AI. And I think the way you can sort of think about quantum technologies is sort of like a backbone to all of these other fields and industries

that will be using it going forward. Not necessarily will it be, will it be, sort of a forefront technology. It would be sort of like the internet where people don't even realize they're using it, but it has impacted significantly what they're doing. And then there's other fields such as like quantum circuit communication, which we're sort of seeing a bit more maturity in, where you can use qubits to essentially transfer information.

And if someone sort of eavesdrops on that qubit stream, then you'll know simply because, as you explained before, when you try to measure these cubits, they collapse into a little. a state and as a result you can sort of see if someone's eavesdropping or looking into the information that you're sending. So that's an interesting field. And then finally something like quantum sensing, so some of the applications of quantum sensing could be using quantum tunneling.

So you use superposition entanglement in quantum computers, but you can use quantum tunneling where you can sort of measure the potential difference across a small space. and you can feed nucleotides through it, which is what genes are made up of. And as a result, you could essentially read an entire gene sequence using quantum tunneling and quantum sensors. So there's a huge array of different applications.

But I think what we're going to see is it being sort of a backbone player to all of these different industries. Interesting. So we shouldn't expect a quantum smartphone at any point. From what you're saying, these technologies sort of operate in the back end, feeding these models and sort of like improving our AI and machine learning and this sort of thing, but not necessarily like in consumer products. Yeah, I think unless sort of we come up with a way, perhaps there will be a startup that we fund that comes up with a way to apply quantum computing to universal touring machines. but until then we're not really going to see it being applied wide scale in laptops and in mobile phones and things like that.

Yeah, and some of the examples of algorithms for quantum computers include quantum chemistry, so finding the best configuration of atoms for drug design, or another big one is understanding the Heber process, process, which is describing the chemical activation process behind fertilizer design. So I think, I can't remember, I think it's something like 5% of the world's energy is devoted to fertilizer production, agriculture, feeding people. And having a more efficient way to design this catalysis would be a huge benefit to the world's economy. And then there's, of course, code cracking.

And another big one is materials design. So like a very basic thing you might learn in high school is, you know, solving a linear system equation like matrix A times vector X equals vector Y. And you want to find out what X is. And quantum computers can do this very fast. And that has tons of applications like, you know, designing radar, and routing of systems. So it's actually quite a few applications I'm sure we haven't thought of yet.

What about brute forcing sort of classical computer science problems like the traveling salesman problem? Yeah, good question. So you might think, okay, this is something we know is hard. That's like one of the first things you learn if you take a computer science course. but actually classical algorithms are quite good at solving traveling salesman problem. It's only like pathological examples in the hardest case that are exponentially hard in the number of cities, the number of nodes. And the good heuristics exist. In fact, you can get, I think, within a factor of three halves of an optimal solution using good classical heuristics.

And it turns out that that kind of problem doesn't have enough structure that we know of to make quantum computers much faster. So it's always good to tame your expectations. Not all problems see a big speed up with quantum. And the traveling salesman problem is one where we generically would not expect a big speed up. Okay. So now that I think we've got a good grasp. on quantum computing, how it works, what are the applications, and how it's better than binary computing for certain types of applications. Let's dive into this paper, this research paper.

So we'll link to the show notes. And so the paper again is titled quantum attacks on Bitcoin and how to protect against them. So this paper describes primarily two types of attacks. So one attack on the hashing algorithms that are used in mining for Bitcoin mining. And of course, a hashing algorithm is an algorithm where one inputs data, and the hashing algorithm will generate a hash or a unique set, a unique string representing its data. So this is used in Bitcoin mining. Of course, ASIC processors use for Bitcoin mining do nothing but create hashes or generate hashes. And the other attack that you described in this paper is on digital signatures. So specifically the elliptic curve algorithm and the specific curve to Bitcoin.

So before we dive into this topic and these two types of attacks, could you tell us, why did you choose to write this paper? What was interesting to you about how quantum computers could potentially attack Bitcoin or other cryptocurrencies? Yeah, it was the news. So we just kept reading these news articles about, you know, quantum computers are going to be the end of cryptocurrency and, you know, these apocalyptic stories about how the new quantum machines coming out are going to ruin all the investments in Bitcoin. And we decided, no, this is bunk. We need to get some reality to this. And so yeah, we took it to task and just put in some numbers and some thinking to it. So before you wrote this paper, there was no prior work on this topic, like real scientific work.

Not much, no. I mean, there had been some papers that talked about alternative blockchains using quantum technology. But actually, there are things you can do that don't even require quantum technology that can make that cryptocurrency can be made safe against quantum computers. Okay, so let's get into it. So first, let's talk about the hashing algorithm section of the paper. So before we dive into how hashing can be affected by quantum technologies, let's just maybe dissect a hashing algorithm at a high level.

How does a hashing algorithm work? Yeah, so it takes as input a message, and the message can be huge, actually. You know, it could be an encoding of an image or, you know, audio, even pieces of a video. And it applies a bunch of operations like, you know, you might represent that input in hexadecimal, some big string of hex. And the hashing algorithm will do additions and multiplications and bit shifts and permutations. and it's actually a non-linear function. And at the output, you get a string, also in hexadecimal, and that's called the hash.

And hashing is what's referred to as a one-way function. So it's very easy to perform the hash. Like, there's actually a funny video on YouTube of a guy just in pen and paper doing a applying the shaw, 256 algorithm with a hash. It's a very low hashing rate. So it's very easy to do, but it's very hard to invert. So given the output, working out what the input is, is very hard.

So it's called one way. What's unique about this algorithm that makes it hard to go the other way, at least with a binary computer or with pen and paper? Yeah, it's just these compositions of nonlinear operations that don't have enough structure for you to invert. And I mean, we get these things happening a lot. I mean, even in physics, like you have a chaotic system, if you change the initial input a little bit, the output is completely different. And that's the key to it. It's just, it's a physical process here, a computation that's, if you were to change like your input string by one bit, the output is completely different.

So what is the sort of classical attack on Bitcoin then in terms of cracking the hashing algorithm with a quantum computer? How would one attack, like walk us through the attack? Right. So, yeah. So the mining problem, at least for Bitcoin, is you apply two hashes to an input, and the input would include transaction information and timestamp and so forth about the block you want to verify.

And what you want to do is you want to find a nonce that is a certain string that you add on to the transaction data such that when you do the double hash, you get a certain number of leading zeros in the output. And the number of leading zeros you want is determined by the difficulty in the Bitcoin mining available at that particular time. So, of course, as computing power gets better, the difficulty increases, and Bitcoin mining demands that you have more leading zeros that you need to find. And since there's very little structure in this, what classical ASIC devices do is they just try lots of different nonses. They just iterate over all the possible nuances they could do

until they get the double hash that has the right number of leading zeros. So it's just a brute force trial and error. And the quantum attack would be to try to find a faster way to do that using quantum mechanics. But the thing is, because has no structure, there's no real structure that a quantum computer can take advantage of to get a big speed up. So the best attack we know of is just to use what's called a Grover search. So it's just a fancier accelerated quantum search where you're doing everything in parallel.

So you're basically acting on all possible nonce values at the same time. and it turns out that a quantum computer can search an N-item database in root n-time, whereas the classical one would take n-time. So there's a speed-up, but it's only a square root speed-up, which is not a tremendous amount, and especially when you compare the speeds of quantum devices versus ASICs. So there's like an ASIC you can buy that does 14 terahash per second. And that's so much faster than what a clonum computer can do even for small scale now.

Like, you know, typical speeds for the computers that are being used at Google and IBM are like, you know, 66 megahertz. And even if you imagine improvements in the future to the speed, it's still going to take quite a long time for them to be competitive, even with ASIC machines today. So the attack then is not necessarily to reverse the hash that a miner would have discovered that matches the number of leading zeros defined by the difficulty, but to really outspeed, to outperform the minor in getting more hashes per second than a standard ASIC. Yeah, so like an ASIC will just do this brute force thing.

They'll try one nonce, do the double hash. Do you get a good answer? No. Try another nonce, et cetera. What a quantum computer does is it acts on all the nonce values at once. So you store in the initial state the data of the transaction for the block and all the possible nonce values at once. you act with your quantum computer to process that state to, and it will reinforce the nonses

which give you a good result, that is giving you the leading zeros you want, and it will cancel out the strings which give you bad results, and at the end you get an answer which is a correct nonce. And that whole process takes root end time on a quantum computer. That's the best that we know of to do for a quantum attack. So your conclusion on this particular attack is that A6 would always be faster at doing this brute forcing than a quantum computer would be at attempting to do this massively parallel processing operation on all the non-sus-at-once at once? Well, no, so eventually if you get a big enough quantum computer, and if the difficulty is hard enough, it will take over A6. It would be faster. But it's just that the timescale for us to get those machines is pretty far. So we did a kind of quantum Moore's law analysis where we looked at how the number of qubits has been. increasing over the past few years and also how good those qubits are. That's called the

gate fidelity, how well they're doing those gates, and also how fast those gates are. And you can find estimates for an exponential improvement in all three of those things. And then we just did a forecasting given the current rates of growth with possibly improvements or slightly worse, how How long would it take, you know, a quantum computer to be a real threat to Bitcoin mining? And, yeah, we don't see any real threat coming until maybe, you know, 2040. Okay. So it's not an imminent thing. And, you know, of course, these cryptocurrencies that use this kind of proof of work mining,

they could, once quantum computers become ubiquitous, is what they should do is to increase the difficulty just to make it so that you know it compensates for the speed up okay so then in in in that scenario one would just need like a lot more a six attempting to to find the right hash but for presumably like a much much larger difficulty and then the quantum computer would still wouldn't still be unable to outperform uh these a six yeah And eventually, I mean, if quantum technologies really take off, everything will be quantum. Like all the computers will be quantum.

And then like quantum A6. Yeah, exactly. Yeah. Okay. And I mean, I know the paper doesn't address this, but are there any types of attacks that one could perform on alternative consensus algorithms like proof of stake, for instance, is proof of stake quantum resistant? Yes, this is a good question. and I consider this still research. I don't think we have an answer to that. There's been some work, so the coin QRL has some statements about having a quantum resistant proof-of-stake protocol,

but I haven't gone through that in detail, or I haven't seen the arguments that's convincing for that. And yeah, I think this is a very interesting research area. Also, Cardano is using the Oroborious protocol for proof of stake, which is claimed to be secure against classical attacks. So this would be interesting to understand the security of that against quantum attacks. This episode is brought to you by ShapeShift, the world's leading trustless. asset exchange, quickly swap between dozens of leading cryptocurrencies including Bitcoin, Ether, Zcash, Gnosis, Monero, Golem, Auger, and so many more.

When you go to Shapeshift.io, you simply select your currency pair, give them your receiving address, send the coins, and boom. Shapeshift is not your traditional cryptocurrency exchange. You don't need to create an account. You don't need to give them your personal information and they don't hold your coins, So you are never at risk from a hacker or other malicious actor. Shapeshift has competitive rates and has even integrated in some of your favorite wallet apps like Jacks. So you can swap your digital assets directly within your wallet just as easily as putting on your slippers.

Whenever you see that good looking fox, you know that's where Shapeshift is. So to get started, visit Shapeshift.io and start trading. And we'd like to thank Shapeshift for their supportive Epicenter. So the paper describes this alternative consensus algorithm through proof of work, which is momentum. Can you describe momentum and why it's quantum resistant? Yeah, so, you know, we were imagining, well, okay, maybe you want to see if you can come up with something which is even more secure against quantum attacks on mining. Imagine that somehow you got really fast quantum computers, like a whole new technology showed up, which made them work at tens of gigahertz clock speeds or 100 gigahertz,

so that it really did become a significant threat to mining. There's a way to modify the mining using momentum, where you demand that not just that the hash or the double hash of some string, is below a certain number, but also that the hashes of two subsets are equal to each other. So you demand that it's the hash of a string that includes like the transaction data of the block, one nonce and a second nonce. And you also demands that the hash of those, that the first nonce and the second nonce is equal.

So you're sort of forcing some kind of structure. to the nonces. And it turns out that there's some provable statements in quantum mechanics that say you can't do better than solving that kind of problem in time end of the two-thirds. So you've gone from a time

which was end of the one-half to a time which is end of the two-thirds and that's a lot slower. So you've done some clever modification of your mining to make quantum computers have less of an advantage. So are there any blockchains or cryptocurrencies that are using this algorithm today? I don't know the answer to that. So this is something that you guys came up with? No, so I mean, I think momentum has been discussed before as something to...

you know, make mining more difficult. But yeah, we have a proof that this is the speed that what the classical, or what a quantum computer could do against that kind of countermeasure. Okay, so just to sort of close this topic on the hashing algorithm part of the paper, in conclusion, you're finding so that

with current proof of work, hashing algorithms are quantum resistant to a certain threshold and we shouldn't get to that threshold for at least another 20 years. Presumably a lot will have changed before then so you know if your bitcoins are stored somewhere right now and you're wondering whether or not a quantum computer will be able to

steal them or if you're sending Bitcoin transactions and afraid that maybe an attacker will be able to come in with a quantum computer and double spend those transactions or revote those transactions, you should not worry, at least not for that attack vector for the moment, because quantum computers are not, don't outperform ASICs in terms of their ability to solve the mining problem in proof of work. That's right. if we do get there and if you know bitcoin still uses proof of work mining in 20 years or 25 years or whatever

we can reinforce mining by by using this this new algorithm that you described called momentum that essentially makes it exponentially difficult for a quantum computer to solve the to solve the mining problem yeah you can you can modify the the mining problem to make it harder for quantum yeah that's okay that's reassuring yeah because uh you know wouldn't want quantum computers selling my bitcoins right great okay so now that now that we've been reassured on that front uh let's let's move out to the second part of the paper which is about digital signatures and specifically paper describes how the elliptic curve signature or algorithm and the specific curve that is used in Bitcoin could potentially be

attacked by a quantum computer. So as a primer, let's first sort of dissect the elliptic curve signature algorithm and how digital signatures work. Yeah. So the elliptic curve signature is taking some input and it applies this function, an elliptic curve function, to the input lots and lots of times, and then you get an output. So you can go on Wikipedia and look up what this looks like,

but it basically involves, you have some funny-looking elliptic curve in a 2D plane, and you're given some points and you can go to another point on the curve, and doing that is applying this curve function once. Then you do it again, to another point in the curve, and again and again and again, and at the end, you'll get to some final point,

and that's called the output of the elliptic curve function. And this is thought to be hard for classical computers to work out how many times you applied that function. It's called a discrete log function. So you know the output is equal to a function operated on x times. And you want to find out what x is. It's like taking the log of A to the x. Well, the log would give you x.

So you're trying to find out what that is. And this is thought to be really hard for classical computers to do. It's kind of like the hashing problem where it's easy to do it, but to find out how many times you had to apply it is hard. So in 1993, Peter Shore came up with this brilliant quantum algorithm for solving the discrete log problem. And since that's the basis for having security, of different signatures based on elliptic curves.

This got everyone really, you know, standing up. The NSA and the U.S. got very excited about this. And this really made the field of quantum computing take off. In fact, if Shores' algorithm didn't exist, it would have taken

much longer for quantum technologies to be where they are today. Just one clever idea like that made a big difference. Yeah, so what happens then is because quantum computers can solve this discrete log problem efficiently, and by efficient I mean it goes like order N cubed where N is a number of bits, N is typically 256 bits, then there's a real threat to digital signatures used on, a platform like Bitcoin.

And the way it would work is that, say, after a transaction has been broadcast to the network, but before it's placed on the blockchain, then a quantum computer attacks this. So if the secret key can be derived from the broadcast public key, before the transaction is placed on the blockchain, then an attacker can use this secret key to broadcast a new transaction from the same address to say her own. She can basically steal money. And the attacker ensures that a new transaction is placed on the blockchain first by, say, offering a high transaction fee, and there you've got a theft.

So, yeah, the threat is if you can do this quantum computer attack within a typical block time, but for Bitcoin is 10 minutes. then you're able to steal. So let's just back up a little bit. And so describe this attack vector on elliptic curve signatures. So with the quantum computer, we're able to, so a public-private key pair is derived from entropy. So we generate this random data.

from that random data we apply a function that function generates a private key and from that private key we apply another function and we get the public key and in a Bitcoin transaction

when we broadcast the transaction we broadcast the public key and the transaction which is signed by the private key and the attack that you're describing is one in which with the private key

we would be able to use a quantum computer to sort of reverse engineer the function and obtain the private key. Yeah, so that's right. So, I mean, of course, if you're worried about quantum attacks, you would want to generate new public keys.

You shouldn't keep public keys sticking around. But if you stick something on the blockchain and you're waiting for it to be verified, you've announced your public key. And a quantum computer can infer what the private key is from that public key, just like what you were saying. And then once they do that, then they can generate their own transaction

because they have your private key. But a Bitcoin address is actually a hash of the private key. Sorry, of the public key. It's not actually the public key itself, correct? Yeah, but they could basically spoof you because they have your private key. So you can still derive the private key from the discrete log problem,

given the public key. Could you describe what that works? I don't understand what you mean, but they could spoof you. Well, so yeah, it's just that if you know, you can, you can derive the secret key from the broadcast public key.

So from the hash of the public key. And then, so then before, the transaction was placed on the blockchain then an attacker with the access to the secret key could broadcast a new transaction

from the same address to her own account for example okay but if it's a hash of the unless just refresh my memory here unless the

actual public key is also broadcast in the transaction in addition to the hash of the public key isn't it true that with the hash of the public key given what we know about hashing algorithms we can't get the actual public key but we only have the hash? Yeah, no, so you have to have the public key.

Yeah. Okay, I see. So you need the public key. You're right. If you'd only have the hash of it that you wouldn't be able to get it. Okay. And so in the paper you described three types of attacks.

So you've talked about one. So one type of attack is that when we broadcast a transaction, we can derive the private key from the public key that we've obtained, which is in the mempool. And while that transaction is waiting to be added to a block, someone could presumably within 10 minutes derive the, private key from the public key and issue a new transaction with a higher transaction fee and that would presumably get picked up by a minor and essentially you know it it looks like

like two transactions and the minor would would pick the one that has the higher transaction fee right but that would we would need to assume that one could um do this attack within 10 minutes can you give us some sort of an idea of like like given current maturity of quantum technology Is this something that can be done today? Or, again, is there sort of a timeline here where? Yeah, so that's exactly right. So basically we consider this the most dangerous attack because even if you're paranoid as users,

so you don't like, you're not reusing the same public key over and over. You use a new one for each transaction. Even then, this is still a threat. And so yeah, we're not using the same public key over and you're not using a new one for each transaction. And so yeah, we're just, really wanted to know how long do we have to wait before this is a viable threat. And this is where you have to really get into the physics because we can estimate the growth of qubits, quantum more's law and how good those qubits are.

But because the gates aren't perfect, you have to use what's called quantum error correction. And I mean, our correction already occurs in classical computers all the time in your cell phone we're using air correction all the time. And quantum computers have to do the same. And it turns out there's a big overhead. So what we found is using the quantum Morse law and the number of gates and qubits you need to solve this discrete log problem to crack the signature.

We estimate optimistically, quantum computers could do this by a 2027. That's a, you know, a significant threat. I mean, of course, that assumes that there's, you know, a lot of progress. But, you know, China's throwing a lot of money into quantum computing, Europe and the U.S., Australia. So, I mean, if you want to be conscientious, then this is something to be worried about. So what counterme?

So that's actually in less than 10 years. so you know presumably it could be before it could be after but how can what countermeasures do we have to protect against this type of attack yeah so fortunately

the computer scientists have been working on this for a long time and the best countermeasure is using what's called post quantum cryptography post quantum crypto and in fact there's a whole field like this, there's conferences devoted to this topic. And the idea is to change the digital signature to use a different kind of algorithm. Not elliptic curve, but there's a whole host of other algorithms. Some of them are hashing based, other than use what are called lattice-based.

They co-buy names of things like things like the lithium, Bliss, Rainbow, XMSS, and these to our best knowledge are secure against quantum attacks, basically because they don't have the kind of structure

that the elliptic curve signatures do. So one thing that we haven't really addressed here is that public, private key, cryptography and elliptic curve algorithms are used to secure all kinds of stuff not only bitcoin i mean these are used in banking uh in encryption in uh military i mean these these technologies are used to secure any type of transaction online uh you know htps uh or tls so you know if if one finds a way and if we get enough maturity in quantum computing to crack public-private key cryptography, Bitcoin is one of the things we should be worried about,

but it's one of many that power the world economy. I believe you when you say that people are working hard on this problem, because there is much more at stake than simply the couple hundred billion dollars in market cap in Bitcoin and other cryptocurrencies. Sure. I mean, maybe the location of nuclear silos is, been encoded using RSA or something like that. And yeah, people have to worry about that.

So this quantum cryptography, these new algorithms that, you know, presumably protect us against these types of attacks, do you need a quantum computer in order to generate like a quantum public-private key pair or can you do this with a regular computer? Will there be sort of a discrepancy in, you know, who has access to this technology? Or is this something that you've been able to do with any type of computer? Yeah, so for the post-quantum crypto, that can be done with any type of computer. But the downside is that the transactions rates will be slower.

So there's a lot of work now in trying to speed up the transaction rates. What do you mean by transaction rates? Well, just because the key links end up being longer than would be used for like elliptic curve. So it just, you know, things would be slow. So you mean it takes more time to generate a private key pair? Yeah. I see. And then there's all kinds of fun things you'll look like when you look at what's going on in the conferences.

People talk about side channel attacks where you can try to learn about the key, the secret key, by monitoring the CPU usage of the computer that is generating the key using post-Quantum crypto. So there's all kinds of fun science about really proving that these things are secure. Okay, not to be confused with like blockchain side channels. This is another type of side channel. Yeah, that's right. Right. Okay.

So that was one attack vector. So the paper also describes this other attack factor that you briefly mentioned, which is that, you know, since we reuse addresses, once you've, so say you, you, you issue a transaction to the network. work, you've issued the public key, say, for instance, there's a, there's a, there's a, there's change that goes to an address. If we know the public key of, um, of the, of the, of the address that has this change, then we can again, sort of derive the, uh, the private key and spend, uh, unspent outputs, uh, after, uh, coins have been sent to a new address. And so the way to mitigate against this would be to just keep using new addresses all the time and never reuse addresses. Yeah, that's right. Okay. And there's a third type of attack that you

described in the paper. Can you talk about that one? Yeah, this is the processed transaction attack. So yeah, if a transaction's been made from address, which has not been spent from before, then, yes, as you say, this transaction would be placed on the blockchain with several blocks following it and one could then try to use the quantum attack to get the private key, but then you have to catch up to the current block, which requires that you solve this hashing problem we described above, which is still hard for a quantum computer. So that one we don't see is a really serious threat. So basically if users use due diligence and always using new private public keys, we continue

to assume that quantum computers are not going to get a big advantage with hashing, then the only real significant threat is being able to crack this private key during one of these transaction times for Bitcoin 10 minutes. Okay. Okay, and presumably by then we will have made enough advances in quantum cryptography to be able to mitigate against this type of attack. And the entire world of public-private key cryptography at some point will have to be overhauled from the ground up in order to protect against quantum attacks.

Yeah, yeah. Good employment for coders. Okay, so in this case, a bit shorter timeline on the attack vector that we described, but you know, if you're worrying about your bit of Bitcoin's being stolen, you should probably also worry about everything else, including the funds of your bank account, the military and, you know, the nuclear bombs that are protecting your country against mutually a short destruction. Exactly.

Exactly. We got bigger problems. We got bigger problems than the Bitcoin's sitting on your ledger nano type of thing. Right. Okay. So that's, I guess, reassuring that if Bitcoin's going to be secured, then other more important things perhaps would also need to be secured. So the paper doesn't address any other blockchains, but these algorithms, specifically the hashing algorithms used in mining and hashing algorithms that are used just, multiple areas sort of in a way of blockchain works and these signature algorithms are using other

blockchain. So have you thought about how this can also affect other blockchain such as Ethereum, you know, Ripple or any other blockchain networks and blockchain stacks that we see today? Yeah. So, I mean, at least from the signature part, there are some cryptocurrencies that have taken this issue pretty seriously. So, for example, example, H-Cash is using the Bliss algorithm, the post-Quatum crypto digital signature algorithm. Cardano is using a quantum secure signature. Quantum-resistant ledger is also, I think they're using an XMSS version. But yes, in this paper, we were really focusing on the proof of work mining.

and the threats to proof of stake is a very interesting one, which is ongoing research. Can't say now that we know that proof of stake would be quantum secure, but there are people working on it. Okay, great. Well, those who are more interested in this topic should definitely read the research paper that was written. We'll have links to that in the show notes. also we'll have links to an article in the technology review that describes this, you know, this white paper, this research paper and the attack factors in a much more understandable and sort of layman's terms kind of way. So we'll have the links to that in the show notes.

Before we, before we wrap up here, I also like to talk about Q-bit and spend some time on this new governance mechanism, this new, I think AJ you described it as a Dow to, that will invest in quantum technology startups. So can you tell us what is QBIT and why did you choose to start this company? Yeah, so it actually spawned off the back of this paper when we sort of thought, started thinking about how quantum technologies were going to impact the world and how we could play a bigger role in where this was going. And I actually went to an event where there was a few VCs and investors there. And it was called, should VCs get entangled with quantum technologies?

And the biggest question that everyone was asking is, like, how do we get involved? You know, I don't understand the field. How do we vet these startups and make sure they're actually going to have viable commercial outcomes? And then on the startup end, it was difficult for them to find funding. when their commercial outcomes were 10, 15 years away. So we started thinking about how could we come up with a way that allows these startups to get funded, allows VCs to get exposure to quantum technologies,

and how do we ensure that we pick the best startups? And then Quinn came on board, who was a chief governance officer, and he was really into the governance and blockchain space, and he wrote a few papers on it. And together we sort of came up with this governance protocol to select the best startups and get a layer of 50 experts across the world, such as Gavin, to help us make these decisions in where we should fund. So what is it about the quantum technology space that is so unique and that maybe doesn't apply

to other industries in terms of how VCs and investors make decisions about what companies they should invest in? My personal feel is that it's like the internet all over again. When the internet first came out, you had all these people that didn't understand it and were really adverse to it and they didn't really know how to go about it. I think it's a very similar landscape right now with quantum where quantum technology is coming out and a lot of ECs and people aren't really sure what to do with it or how to go about this opportunity.

And that's essentially because, you know, quantum is going to be like a backbone to all of these other technologies, like I said before. So like the internet spawned a bunch of different companies, you know, web applications, mobile applications, etc., quantum is really going to spawn a lot of other fields like, you know, medical industry, AI, etc. So give us a sense of the sort of quantum startup ecosystem. I mean, of course we hear about like AI and blockchain and like machine learning and like there are these sort of hot topics and like hot startup fields at the moment.

that a lot of investors are interested in, but I mean, personally, I don't know if many, you know, quantum startups are certainly not heard of very many. And to me, the only actors that are really doing a lot of working through this are, you know, like was mentioned earlier, IBM and Google. So give us a sense of the ecosystem at the moment. Like, what are people working on? Yeah. So it's cool because we get to sort of interview all of these interesting startups. are doing really cool projects in quantum technologies. So some of them could be around quantum random number generation. Then some of them looking at middleware.

So looking at the layer between the qubits and how we operate algorithms on it. Medical applications, I think I mentioned before about quantum tunneling and how you can use it for genetic mapping. Then you go into hardware cloud computing. So Riggetti is a cloud computing company has done quite well. And then also things like secure communication. So how do we take Telegram to a completely new level of secure communication? And how do we take cryptography and security to a new level as well?

So these are kind of the startups that we've been talking to over the last couple of months. I mean, these startups don't have the hardware to actually build anything right now. I mean, they don't actually have quantum computers. what are they mostly just at the research stage for the moment? So generally what we're seeing is a lot of these startups are being backed by academics. So for example, even Cupid Protocol, we have four quantum professors on our team. So a lot of these guys do have a very strong academic background. And also on top of that, we now see all these systems like IBMQ, Rikgeti Forest,

where you can use simulations and cloud computers to, write software and algorithms, which is quite interesting. So we're trying to see how we can really help the ecosystem as well with these resources and the expertise to help them really cultivate these companies. So for someone who wants to start a company in the quantum technology field, say, for instance, you wanted to build a product that does secure messaging using quantum technology. So you mentioned this example of Telegram at an entire new level.

Given the uncertainties and given the fact that you don't actually have any actual hardware, what's the risk involved here for an entrepreneur but also for an investor? So I think it's important with these new companies coming up that they do have an academic presence. I think it's a bit difficult for companies without that academic backing or someone who's, you know, research this for years to go out and say, hey, we're going to start a quantum messaging service. However, with that said, there are a lot of quantum cloud computing services out there, like Ruggeti Forest and IBMQ. So there are starting to pop up some tools that people can start using. But I think at this stage, at this early stage, just like the internet, like, you know,

back when the internet was first starting, you really needed a, a, a, a, research background or something very inherently technical to start these things. Nowadays, when it comes to websites, you can just go Squarespace and make it. But really early days was very difficult. So I think it's a very similar ecosystem right now where you do need someone with a high level of technical expertise, research background to help you out if you are going to go into this endeavor. But I think going forward, we're going to see more of these platforms like Rigetti Forest and

IBMQ to help entrepreneurs get into the quantum space. So one of your opinion are the areas that we should see sort of innovation occur first. Are there any specific types of application of quantum that we should see sort of mature in the next few years? Yeah. So just looking at the sort of startups that we're talking to right now, we're still seeing more software companies. I think there's going to be a lot of innovation in the offshoots,

so helping quantum hardware become more efficient. So I think Gavin sort of touched upon the fact that right now, one of the biggest limitations is this gate error and creating stabilized qubit. So looking at surrounding technologies and how we can help improve that as opposed to directly impacting it, and also just applications of quantum cloud computing.

Now that it's available, what kind of algorithms can we design? What kind of specific applications, maybe for genetic composition of people, like how to read that, maybe looking into how we can impact AI. So those are sort of fields that are up and coming. Yeah, and also, like with quantum sensing is actually a really big area that AJ brought up, miniatureized atomic clocks. There are actually companies already making these.

and that's really great, especially in the case of a GPS spoofing attack. If you have a very accurate clock, you can do navigation. Also, gravimiters, which can be used for mining and construction to find cavities under the Earth surface. And magnetometers, there's a company based in Europe that is Envision that is working with polarized diamond spins that are quantum spins inside of diamond. And you can use this for enhanced MRI. So you get much better resolution of MRI imaging. And so there's interest in the medical community in that.

And this kind of stuff is a lot more near term than quantum computing. Fascinating. So tell us a bit more about this DAO. How is it going to work and sort of what are you expecting in terms of the types of startups that will sort of apply for investment and who you're targeting in terms of investors. Yeah, so the way it works is it's the governance protocol, so there's two layers. We'll have 50 experts across the world in various different fields, so academic background, quantum commercialization, et cetera.

And then you have your public voters, so essentially just like a normal government, except in this case, public voters will also be able to vote on the proposals themselves. so it's kind of like a liquid democracy as opposed to a purely representative one. So that's really interesting how we're pushing the boundaries of governance through Quinn's input because he's written a few papers on it. He's analyzed the Dow from 2016, an academic paper.

And then that's connected to a Dow, which is obviously storing all the funds that we then invest into the quantum startups that are selected through this governance protocol. And the kind of startups that we're going for is in, we're sort of seeing two types. One is sort of the accelerator standard type where we're seeing a lot of PhD students

sort of graduate from university and sort of say, hey, we want to study a company in quantum. We've done a lot of research in this area. So that's where we can come in with the expertise and the money with an accelerator program, so a more formulated program that something like 500 startups might do. And then we're sort of seeing a more established, sort of research

direction, sort of becoming a company later. So a professor might do some research in, you know, five years into quantum random number generation and then decide to incorporate it and then, you know, try to commercialize the product. And that's sort of the second

half of it. And that's also something we're looking into helping out as well. And so these funds, so this DAO is sort of an investment fund. So investors will invest money in this DAO. And And then these sort of advisors will curate the projects that sort of bubble to the top in which investors will place their money. What's the structure, what's the legal structure then for a company?

Is it like an IC, are they sort of doing an ICO on this platform? Are they giving away equity? So to clarify, it won't be investors putting money into the fund. We'll put money into the fund through our ICO. So when we sell our tokens and you buy it to take part in the governance protocol, we'll use 60% of the funds to put into the Dow, and that will be used to invest into companies. Any profit that derives back to the fund is we're looking at buyback schemes

such as Swarby and Binance to help derive value back to our token holders. Now in terms of the startups, we will get equity from them for a certain amount of money. So traditional investments into quantum. And the idea is that the value always flows back to everyone who's in the community. So it's not just the money that we're giving. It's just that with this whole token design, now you're sort of vested into the portfolio company as we get this quantum community. Everyone gets behind it. Everyone's trying to help out, including the 50 experts that we have.

Okay. So tell us about the roadmap. When will this launch? Yeah. So we're currently in the private ICO. So we're raising a 20,000-Eth hard cap at the moment. we're getting on board experts. So we're at about 10 confirmed

and about 20 that we're sort of still negotiating things with with a goal of 50 in the next month or so. And then we're looking to do a pilot program which is really great in the next two to three months. So we've already started applications. So we've interviewed startups and funneling them through the process with a main platform launch at the end of the year and even a conference that we're planning,

a world quantum conference. great well this has been a fascinating topic i'm really happy i was able to speak to two experts on the topic to better understand some quantum computing quantum technologies and how it relates to cryptocurrencies i hope that all the listeners now have also a better understanding and uh sort of grasp this concept with a lot more a lot more certainty so thanks for coming on guys thanks for having us excellent thanks for having us and thanks for all the the good questions. And thank you to our listeners for once again tuning in. You can get new episodes of Epicenter every week and so you can find Epicenter on iTunes, SoundCloud, or wherever you

get your podcast. You can also watch the video version of the show on YouTube. If you want to support the show, a great way to do that is to leave us an iTunes review. It helps people find the show and we're always happy to see your reviews. And if you want to join our community, you can do so by going to Epicenter.tv slash Gitter to join our Gitter community. So thanks so much and we look forward to being back next week.