Unraveling Blockchain’s Vulnerability to Quantum Computing with Or Sattath and Bolton Bailey

[00:00:00] Welcome to The Quantum State, a podcast exploring the latest research and innovation in quantum computing.

[00:00:06] Join us as we dive into ground breaking breakthroughs, trends and news shaping the quantum landscape.

[00:00:12] The Quantum State. Today we have Orr Satath, associate professor at Ben Gurion University of the Nagev

[00:00:36] and Bolden Bailey, a PhD student in computer science at the University of Illinois, Urbana-Champaign.

[00:00:41] So thank you both for being here.

[00:00:43] It's great to be here.

[00:00:45] Thank you.

[00:00:47] So Orr, broadly, what kind of research do you do as a theoretical computer scientist?

[00:00:52] And can you tell us how you got involved in topics like quantum money and quantum blockchain?

[00:00:56] Sure.

[00:00:57] So I was working on many aspects actually of quantum computing, quantum algorithms, quantum complexity.

[00:01:05] And at some point I was, I guess at the beginning I looked at quantum cryptography and said, well, this is too hard for me.

[00:01:13] I find just notoriously hard to kind of figure out all the perspectives and all possible attacks.

[00:01:22] And I find it even too confusing, but you know, it took me some time.

[00:01:28] But eventually I got used to it, I guess, and to like it to some extent and started working more and more on aspects related to quantum cryptography.

[00:01:36] And one of the, in some ways like the old topics in quantum cryptography are involved tasks related to quantum money.

[00:01:47] And I started to think about those and I guess even at the time when I started studying it,

[00:01:54] I heard this new kid in the block called Bitcoin and at the time I didn't understand much.

[00:02:01] I think it was pretty early on and there were very few people that they could talk to and understand all the details.

[00:02:09] Do you remember what year it was or what price?

[00:02:13] Oh, like the first time I've heard of it or like, I think it was 2010.

[00:02:20] Oh wow.

[00:02:21] It would be a dollar.

[00:02:22] Yeah, I think I've heard of it pretty early.

[00:02:25] I guess it's kind of interesting that, you know, one of the most interesting money papers that was released was roughly the same time.

[00:02:33] One was by Scott Aronson called, I don't remember the exact name, but maybe you remember the name?

[00:02:38] What a money from hidden subspaces, that paper.

[00:02:42] No, no, no, he had it.

[00:02:44] No, no, that's like, yeah, yeah, he has a, like where he introduced quantum copy protection as well.

[00:02:50] And there was another paper later about quantum money from knots.

[00:02:54] The original paper was by Scott Aronson and the later paper was by a bunch of other people from MIT,

[00:03:00] including Peter Schor and Ed Farhi and many others.

[00:03:03] And I read about it and actually it was at the time I was TA, I kind of thought this topic to some groups and I told them,

[00:03:11] well, maybe it was worth looking at this thing called Bitcoin.

[00:03:15] And again, I didn't know much about it.

[00:03:17] But again, as time evolved, I learned more and more.

[00:03:20] I think one of the first kind of talks I've heard of it was by Adi Shamir,

[00:03:26] who gave a talk about privacy aspects related to Bitcoin.

[00:03:30] And I kind of kept it at the back of my head.

[00:03:32] I guess they were very like, I guess it's worth mentioning other people that like,

[00:03:35] I talked quite a bit with Aviv Zohar, who was at the Hebrew University at the time.

[00:03:39] And that was his main interest.

[00:03:42] So at that point, I definitely understood all the details and I had some, you know,

[00:03:45] a real expert to talk about it whenever I wanted as much as I want.

[00:03:49] He was very open and I like talking about it.

[00:03:52] And he was very, like, interested in broad aspects,

[00:03:56] including aspects related to, you know, quantum cryptography or even quantum attacks,

[00:04:03] you know, could break it and such and such.

[00:04:05] And I learned a lot from him.

[00:04:09] Some point we also got through the paper about aspects related to mining fees in Bitcoin.

[00:04:16] And again, I wouldn't say this is like the main topic that I'm interested in.

[00:04:21] That's kind of a sidekick of mine.

[00:04:23] I'm doing most the aspects related to on-crono, but cryptography more broadly,

[00:04:30] quantum cryptography more broadly.

[00:04:32] But this is definitely something I'm interested in.

[00:04:34] Great.

[00:04:35] So Bolton, what are you working on for your PhD and how did you end up collaborating with Orr?

[00:04:41] Yeah, I mean, I guess it's sort of funny.

[00:04:42] The main topic of my PhD thesis is on sort of the intersection between formal methods and cryptography.

[00:04:51] So my research mainly focuses on how we can use sort of computer theorem checking systems

[00:04:59] to prove that certain cryptographic constructions are secure and correct.

[00:05:05] But, you know, at various points during my PhD, it wasn't...

[00:05:09] I did really have a connection to quantum cryptography from anything that I did during my PhD.

[00:05:16] It was more something that quantum cryptography was something that I really only first learned about when I was in undergrad.

[00:05:23] And then it was only many years later that when I was doing work on sort of blockchains

[00:05:28] that I came to think that there might be some interesting connections there.

[00:05:32] And I think I had read about that point on Of Orr's papers on, you know, sort of various ways.

[00:05:41] As you mentioned, like, unclotable cryptography was that certain things that can be done with quantum computers

[00:05:48] but can't be done with possible computers to potentially be helpful for cryptography.

[00:05:54] And so I think at some point my advisor introduced me to Orr and we had some readings talking about various things.

[00:06:01] And that was basically how I got to know Orr and how I got to be working on quantum cryptography.

[00:06:06] Great, so you both recently published an archive pre-print with the title,

[00:06:10] 51% TAC via difficulty increase, launching some of the details about that paper.

[00:06:17] Or can you just give us a brief primer on blockchain and how quantum computers disrupt blockchain or potentially could?

[00:06:27] Sure. So blockchains are a way to record transactions in a distributed manner.

[00:06:34] So two people can transact without any third party being able to, say, sensor them or, say,

[00:06:41] give some conditions on how they transact, etc.

[00:06:45] So I guess the main feature here is censorship resistance.

[00:06:48] Now the way quantum computing interacts with blockchains is kind of a bit complicated.

[00:06:58] Blockchains use two main mechanisms in terms of their cryptographic techniques that are involved.

[00:07:05] One of them is digital signatures and the other is proof of work.

[00:07:09] I won't explain how Bitcoin works at any level.

[00:07:16] I guess there are other fantastic videos about it.

[00:07:19] I think there are many resources that one could find about that.

[00:07:23] But I guess the way that quantum computing interferes is in both of these things.

[00:07:31] So the one which is more well known is related to digital signatures,

[00:07:35] prone to Shores algorithm or variants of it.

[00:07:38] And in particular, what that means is that if you have the public key of another party

[00:07:45] and you have a quantum computer, then you can efficiently find the private key.

[00:07:50] And therefore you could efficiently forge and sign any message you like using that private key.

[00:07:58] What that essentially means is that if your public key is recorded on the blockchain,

[00:08:04] then a quantum adversary could basically steal all your money.

[00:08:09] Unless of course some precautions are made and some migration to other types of digital signatures is used.

[00:08:17] One of the main ways to do that is to use something which is called post-quantum digital signatures.

[00:08:21] What that means is that this is still a digital signature,

[00:08:24] meaning you have a public key and private key and you can sign messages

[00:08:30] so that others cannot sign messages on your behalf.

[00:08:34] But now even quantum adversaries, ones which have quantum computers,

[00:08:40] cannot break your digital signatures.

[00:08:42] Now this is an active area of research, post-quantum signatures.

[00:08:47] Recently there was a NIST standardization process for digital signatures

[00:08:54] and now we have pretty good candidates for that

[00:08:58] and hopefully one day blockchains such as Bitcoin, Ethereum and others

[00:09:02] would transition to post-quantum signatures and everyone's money would be safe and sound.

[00:09:07] So that's one aspect which is pretty well understood, both the problems and the possible solutions.

[00:09:14] The other mechanism is called proof of work.

[00:09:16] What is proof of work?

[00:09:17] Proof of work is basically a puzzle which is in the form of finding hashes

[00:09:26] which are small than some difficulty level.

[00:09:30] More precisely, we use something such as a hash function such as SHA256

[00:09:35] which is a function which looks like a random function.

[00:09:40] So it behaves like a random function and the sense that if you apply an X

[00:09:45] and like a hash to X, it looks pretty random.

[00:09:49] Now in Bitcoin, the way that this is used is that whenever you want to post a block,

[00:09:54] the miners try to hash a header such that the hash of the header is a relatively low number

[00:10:02] and finding such headers is extremely difficult task.

[00:10:10] Now, quantum computers are only moderately better and finding these solutions.

[00:10:18] So what exactly do I mean?

[00:10:21] For a classical miner to find such a hash or to solve this proof of work,

[00:10:25] the strategy is pretty simple.

[00:10:28] He tries and tries over and over until hash is found.

[00:10:32] So we should think of it as a lottery ticket.

[00:10:35] Now one of the interesting aspects of quantum algorithms is called Grover's algorithm

[00:10:41] which allows you to find such a solution to a problem quadratically faster.

[00:10:49] So the way you should think of it is if you have one needle in a haystack of size n,

[00:10:54] then the number of times that you need to try until you find the needle is roughly n.

[00:11:02] Whereas in a quantum computer, if you have one needle,

[00:11:06] it takes you only square root of n to find such a needle.

[00:11:11] And therefore it means that it is moderately easier to find it for a quantum computer.

[00:11:18] Now the common belief was that this isn't such a big deal in the sense that

[00:11:22] if quantum computers would be realized at some point in the future,

[00:11:27] what this would essentially mean is that the difficulty would go higher.

[00:11:33] So already Bitcoin is designed in such a way that a block is found every 10 minutes

[00:11:39] and expectation.

[00:11:40] Time it took to find such blocks was actually a week rather than two weeks.

[00:11:44] Then the difficulty increases by two.

[00:11:48] So it's harder to find these blocks and therefore in the next two weeks,

[00:11:54] which is called an epoch, it would be adjusted so that blocks are mined every 10 minutes as they were supposed.

[00:12:00] So the common belief was that if quantum miners arrive then the only difference that would happen

[00:12:08] is that the difficulty would increase and okay, that's not such a big deal.

[00:12:12] We already have seen that difficulty increases many, many times in the past.

[00:12:17] When ASICs first appeared then of course such a difficulty already happened and no big deal.

[00:12:25] It was very simple and in some sense Bitcoin is designed to take that into account.

[00:12:32] But I guess this isn't the full picture and it took a while to figure out

[00:12:37] and actually there are several aspects that are not even understood today.

[00:12:42] One is when we talk about multiple miners, right?

[00:12:46] When all the miners use quantum hardware, I can discuss that later if you wish.

[00:12:51] And the one which was done recently by Bolton and myself was about what happens

[00:12:57] even if there's a single quantum miner.

[00:13:00] So Bolton would you like to take it from here?

[00:13:02] Yeah, sure.

[00:13:04] So I guess to begin to explain exactly what happens in this sort of attack that we described.

[00:13:12] I guess as Orr mentioned, the way that blockchain network like Bitcoin functions is that there's supposed to be a block on average every 10 minutes or so.

[00:13:24] And the way that the network keeps that 10 minute average rate sort of constant over time, even as more and more computers join the network and more hashing power is applied to solve the mining problems.

[00:13:39] Is that there's this mechanism which is called the difficulty adjustment mechanism.

[00:13:45] So the way that this works is every 2016 blocks.

[00:13:52] What is done is that the network as a whole will take a look over the past 2016 blocks and they'll take a look at what the time stamps of the first block in that period was in the time stamp of the last block in the period was.

[00:14:08] And they'll use this difference in time stamps to get a sense of how long it took for the network as a whole to solve all of the blocks that came along in that epoch.

[00:14:23] Right, this two week period is called a difficulty adjustment epoch this period of 2016 blocks.

[00:14:28] And so, if the blocks in the epoch come along at a very fast rate faster than the network expects.

[00:14:36] But the network infers is that you know there's actually probably more hash power contributing hashes to the network trying to solve problems than it expected.

[00:14:47] And if it determines this what it will do increase the difficulty for the next 2016 blocks so that again blocks will come more slowly.

[00:14:56] So we have the network it increases the difficulty when when things are going too fast and it decreases the difficulty when things are going too slow.

[00:15:05] But the upshot of this is that someone who is trying to attack the network by making a separate chain of blocks which is, you know completely independent of that of the rest of the network.

[00:15:16] What they can do is they can sort of modify the timestamps that they put in the blocks that they, they may sort of manipulate this difficulty adjustment mechanism into changing the difficulty to be essentially whatever they want.

[00:15:30] And so it's possible for an attacker to either increase or decrease the difficulty basically at will just as long as they can mine the blocks that are needed to do this.

[00:15:45] And so in the case of a world where all of the miners are using classical computers. This is, this is a totally workable thing and it's everything is fine.

[00:15:57] Because even if an attacker does this, even if they are adjusting the difficulty to be either higher or lower. It turns out that an attacker can't really gain an advantage from this.

[00:16:08] And so what the network uses to determine what one true block is the is the the be all and end all the the true sort of change yet that is considered to be the real state of the Bitcoin network.

[00:16:21] They make that decision based on the total number of hashes that were expected to have been required to produce the entire chain up into a certain points.

[00:16:32] Even if an attacker with less hash power than the rest of the network does sort of play with the difficulty in this way. They can't really gain an advantage because they only have a certain amount of past hour.

[00:16:45] They only have a certain number of computers that are capable of contributing blocks to the Bitcoin network. And if this hash power is less than the rest of the network, whatever alternate chain they produce is not going to have that

[00:17:00] to be of having the most apparent, the most apparent work on that chain so everything turns out to be fine. In the case of a classical network, but the problem comes when we combine this with the quantum computers and this grover, this grover sort of mining

[00:17:20] that or outland so with with grover's algorithm. It's possible to spend only the square root of a certain number of hashes in order to produce a block, as it would typically be for as would typically be the case for for a classical

[00:17:37] miner. And what this means is that if a quantum miner goes and increases the difficulty of the block. Well, if I if I as a quantum miner go and quadruple the difficulty of the block.

[00:17:51] And now going to be each each block that I mine will now count for four times as much as it would beforehand. But because I'm using grover's algorithm, it will only take twice as much work for me to mine that block, because every multiple

[00:18:06] factor I add on to the difficulty, I only take the square root of that when I'm using grover's algorithm. And it's only a times two increase in the amount of work that I have to do.

[00:18:17] And so what ends up being the case is a quantum miner can just, you know, double and quadruple again and again the difficulty of the network. And so they really have a large amount of ability to produce a parent has power,

[00:18:31] and this can basically trip the whole network into thinking that a large, large amount of work is then done on the chain that has been mined by this sort of dishonest quantum miner.

[00:18:45] And that's basically how the attack works.

[00:18:47] Is that distinct in any way from if we draw a black box around the grover nodes, it's doing this. Ultimately, the input output of that box is hashes are coming out. That that's all there is. So is this distinct from drawing a black box around just

[00:19:06] an increased number of classical nodes to achieve the same objective? Could a secret mining week with a lot of power do the same thing.

[00:19:15] Well, I would say that it's a little bit different for the for this sort of quantum black box because of this, because of the grover sort of advantage, you could, you could draw a black box around a certain number of classical miners and they would have a certain

[00:19:31] they would have the ability to output a certain number of blocks. But the difference with the quantum miner that has the sort of black box drawn around it is that as the difficulty increases in quantum miner seems to be able to produce more and more hashes, whereas

[00:19:46] the set of classical miners, you know, as the difficulty increases, the number of hashes that they produce per second really just remains the same.

[00:19:55] And so for that reason, the situation with the quantum miner is a little bit incomparable to the classical miner. It's even sort of hard to say what precisely we mean by the actual hash power of the quantum miner.

[00:20:09] You know, in the classical context, we can just say, okay, how many hashes can this one computer produce per second.

[00:20:17] But with quantum miners it's not, it's not exactly clear what that means because with a quantum miner, the number of hashes per second that it can produce really has more to do with the difficulty.

[00:20:29] And so it's a sort of a completely different regime.

[00:20:32] So can, can both of you talk a little bit about I just want to break down again also for our audience. So how serious is this right like we talked about 51% attacks a lot in the form of transactions and that's obviously very serious here.

[00:20:47] So in the history of blockchain, you used to be able to mine Bitcoin with just your laptop back and back in the day right. And then you moved over to GPUs where where you could only mine if you had the GPUs and now the individual who has a GPUs they don't

[00:21:04] have that power anymore it's these big kind of rigs that you need to have to be able to even have a chance in the space so how is this different from kind of that shift the transition we've seen before.

[00:21:18] And how would you rank that seriousness you know obviously like, you know shores algorithm we talked a little bit about the transactions.

[00:21:24] And if it's that serious is there.

[00:21:27] Is there a mitigation that we want to do or is it kind of just this is a consequence of new computing power coming in this is what is going to happen to the blockchain.

[00:21:35] So, I mean, I can sort of, I guess I can, I guess sort of address that question.

[00:21:40] The, it's, it's definitely the.

[00:21:43] It's definitely the case that, you know, like that is sort of an important question how much actual hash power, you know, the rest of the network has because I guess, you know, this is maybe more of a question for quantum experimentalists like, like though, like you all, but it's not totally certain from our point of view, like what actually will be the capabilities of, you know, fully fault tolerant

[00:22:09] quantum computers, even when they come out right. It's sort of a critical question, you know, you can build a quantum computer that's maybe in principle capable of carrying out any quantum algorithm.

[00:22:21] But what will actually the clock speed of that quantum computer be. And if the clock speed is very, very slow then in principle you can use that to carry out our our attack but it may in practice take a long, long time to do that.

[00:22:37] You know, it in the sort of worst case scenario if your quantum computer is only capable of of make producing blocks at a rate of like 1 test the rest of the network it could take, you know.

[00:22:48] Hundreds or tens of thousands of weeks to sort of complete this attack. So it's definitely the case that it's sort of a critical important critically important question what will actually be the performance of the quantum computers themselves and what will their their clocks need be.

[00:23:05] So, we've, we've sort of gone from from GP from CPUs to GPUs to ASEX in the possible world.

[00:23:14] You I guess you could sort of a speculator imagine that something similar might happen with quantum computers as well over the next, you know, decades.

[00:23:23] But I guess that's that's more of a question for like multiple days, rather than just asking, you know, what is the what what is going to be like to see the first sort of problem theater that we have that could that could do this sort of thing.

[00:23:36] So I want to add a few kind of points. So, first of all, I want to be very clear about it. This is not a short term or I would even say medium term threat.

[00:23:46] This is a long term problem. It's going to take years or probably even decades to be relevant.

[00:23:54] So there's definitely no need to panic. I guess we could say a few words about the complexity of the attack here. So, if the minor, suppose the quantum minor can create blocks say every 100 minutes.

[00:24:10] Right. So that means he has some sort of like, so by using Grover's algorithm, this quantum minor can produce blocks every 100 minutes.

[00:24:21] So he has something which is kind of very similar to 10% of the total hashing power, although we call it done exactly mean that because when we use Grover's algorithm you don't just count hashes this is different than the classical setting.

[00:24:36] We call that parameter R. Okay, so in this case, R equals 10. The complexity of the attack is one over R squared where the one over R squared epochs are is 10%. This means 100 epochs, meaning 200 weeks.

[00:24:56] Okay, and I'm ignoring constants here. Okay, so notice this is a really long term attack. Okay, it takes years to actually implement in practice.

[00:25:09] In particular, it also means that you know your quantum computer needs to operate coherently for very long periods of time. Now, quantum computers, you know, usually you could break if you want to use, you know, a quantum algorithm on a modern quantum hardware, it would probably take you a millisecond or so.

[00:25:30] So our hardware is even designed to be able to do these to operate for fairly short amount of time. At this point in time, it seems almost science fiction to have a quantum computer working in a coherent manner meaning without errors, etc.

[00:25:48] By using error correction, etc. operating for months. This is what you actually need for this attack to work.

[00:25:57] So I would put it at the very far end of the spectrum in terms of the hardware that you need in order to apply this attack. On the other hand, I think it's for sure.

[00:26:10] Now, as I mentioned, we have a pretty decent plan in terms of how to deal with the problems that quantum computers create for digital signatures, for example, right? We need to find a migration plan towards post quantum digital signatures.

[00:26:28] We have pretty good ideas regarding how to do that. Now, as for quantum miners, even though it's such a long term threat, etc. I don't think we have a pretty good understanding of the horizon.

[00:26:41] Well, how could we fix it? What how serious is it, etc. etc. This is a little bit too.

[00:26:47] There are very, very few works about it that kind of discussed quantum mining in general. Definitely when we talk about mitigations and you as you were kind of pointing out Anastasia, there were a few works about it.

[00:27:00] Actually, I think I'm not sure right Gavin and Peter right you were on that paper that proposed momentum as an alternative proof of as an alternative type of proof of work.

[00:27:10] This is the person sampling one. Yeah.

[00:27:13] Where we get a no, no, the ball.

[00:27:16] The previous one about the momentum that has like, I don't think I was on that was the.

[00:27:22] Okay.

[00:27:23] I don't think what momentum was initially proposed by them, but they certainly like analyze the question of quantum capabilities for a variety of systems and that bigger, including momentum system.

[00:27:33] Okay.

[00:27:34] So, I guess there are very few works discussing quantum mining and the aspects of it. And we do know quite a bit.

[00:27:45] We do know that, you know, for example, the Bitcoin protocol has to be adapted so that there are no there aren't too many forks because if quantum miners are mining,

[00:28:00] if I say all the network switches to quantum mining, then behavior of the quantum miners would behave differently than classical miners.

[00:28:09] In the following sense, suppose, you know, Bolton is mining now and I hear about Bolton's block. Okay.

[00:28:17] The honest protocol says that I should switch and mine on top of Bolton's block, but suppose now both Bolton and I are mining using quantum hardware.

[00:28:27] So Bolton mind using Grover's algorithm. And that essentially means he applied many, many, many grover iterations and measured his state.

[00:28:37] And suppose he was lucky and he told me about it. What should I do now? I already spent some time applying Grover's iterations.

[00:28:49] So again, Grover's algorithm works by applying many consecutive steps, but it's kind of important not to destroy that state but only at the, you know, at the time that you want.

[00:29:01] So suppose Bolton mine for say 15 minutes and now I come and hear about Bolton block. What should I do? So actually it's not so what should I do?

[00:29:12] But one thing to do is definitely not to just throw that thing away that I worked on and mine on top and just switch to Bolton's fork, but rather I'll measure and hope for the best.

[00:29:28] Meaning I'll stop my computation at the time that I hear that Bolton successfully mined his block. And this is a very different behavior than what happens classically.

[00:29:39] You see, because when we're mining classically, there's nothing so special that happens when Bolton successfully mines a block.

[00:29:48] Everyone's, you know, hear about it and switches. Whereas in the quantum setting, we already spent a lot of time working really hard, right?

[00:29:57] And you won't just throw it away. We probably all try to measure at the time that Bolton successfully mine and maybe some of the other quantum miners would successfully do so.

[00:30:12] And therefore, the probability of having forks could increase dramatically unless you know modifications are made so that this won't happen.

[00:30:22] So that, I guess the point is that unless modifications are made the quantum mining would be or would already be a threat when we have quantum miners. We'd have to switch.

[00:30:33] And the way that we one way to kind of deal with it is to change the tie breaking rule.

[00:30:40] So when, you know, if there are two, if there are forks on the network and you hear about two different blocks that are, you know, competing, what do you do?

[00:30:51] So the honest, the Bitcoin standard rule is to mine on top of the one you've heard first or maybe even just one mine on top of a random one.

[00:31:03] It doesn't really matter which strategies used, like both of them would work to some extent. But if quantum miners would, if quantum mining would start, then we have to use a different tie breaking rule so that Bolton's block would be in rather than mine in some sense.

[00:31:20] So again, suppose Bolton found a successful block. Now, the, the, in some sense, the cheating strategy for me is to mine if I hear of Bolton's block and we want to really rule this out.

[00:31:34] So to get around this problem, we could change the tie breaking rule so that miners would mine on top of blocks that are closer. Sorry. So again, if Bolton mined the block and suppose he mine it at 7pm.

[00:31:52] Okay. Now we could look like all the other guys on the network would hear about Bolton's block at 7pm and Bolton actually wanted to mine a block at 7pm, whereas I was planning to mine my, my block at say 705pm.

[00:32:10] So the timestamp on my block couldn't be adjusted, right? I need to decide in advance what would be my timestamp. So if we change the tie breaking rule to be something of the sort of mine on top of the block which in which the timestamp is very close to the time it was actually

[00:32:30] propagated to the network. I'm not being very accurate here, but this is the kind of intuition for what's going on here. So we need to change to that type of rule. It kind of takes into account the time that it was propagated to the network and the timestamps, the timestamp in that block.

[00:32:50] And that would essentially give Bolton a very high score, whereas if I managed to find the block by mining at the time that I didn't plan to, I would essentially receive a penalty and therefore the others won't mine on my block and rather would stay on Bolton's block, which is what we actually want.

[00:33:09] But I guess the point I'm trying to make is that we already knew that there are some modifications that need to be made in order for Bitcoin to be secure in the quantum setting, which isn't necessary at all in the classical setting.

[00:33:24] And this attack that was just Bolton described essentially means that we need, there are even worse problems in some sense and it's for, I don't know what I would call a fix to that problem.

[00:33:41] Maybe there are some ways to kind of make it a little bit harder, make it better, but I'm not sure if you could completely rule this attack out.

[00:33:52] Should I get into the question of like what types of mitigations can we think of or none of them are very, you know, yeah.

[00:34:02] Yeah, that's interesting. Do you want to answer? I can relay the question or so the question he asked was people have come up with this sort of condition of progress, free-ness, which is sort of considered an important question for important important that we have our free-ness.

[00:34:21] Free-ness, it just sort of results in Nakamoto consensus to hold.

[00:34:25] And what he suggests is that there's work, which I guess I haven't heard about, but work about using random regions in order to sort of interrupt the growth or mining process so that you have to use some sort of data from a random beacon and include that

[00:34:40] in order for your block to be considered valid. I think that's sort of an interesting idea. I mean, as you say, Gavin, that would sort of require like sort of trust in the random beacon.

[00:34:50] It would require some sort of cryptographic guarantee that you have a random beacon that is truly unbiased for randomness that no one can cheat or affect in that way.

[00:35:00] But I think that like if that could be done, and if you could impose it such that the hashes that were being done at any given time had to include that randomness.

[00:35:10] I think that that actually probably would go a long way to mitigating this sort of attack because it really is sort of critical in our attack that the quantum miner is able to mine if uninterrupted for a long period of time on one particular block.

[00:35:28] Because that's very critical for our attack because it really confers on you the advantage of being able to get the full sort of quadratic advantage of the Grover's algorithm.

[00:35:40] And so if you could interrupt that with some sort of random beacon, that's sort of a very appealing way of carrying out a mitigation or if you want to like further a bind.

[00:35:51] Yeah, I'm not sure if I so of course there are many hope that might be potential holes in this argument.

[00:35:57] Bolton suggested it's kind of clear that you to the very minimum you need the trust in that beacon.

[00:36:04] But even more, I'm not sure even if I can understand how exactly it works.

[00:36:10] Would you say that the beacon produces a number every, I know, every minute or so. So you need to include 10 numbers in your block.

[00:36:21] How exactly would it operate and how would it rule out the attack because both of them like we could also just wait for a few minutes so that there are enough things to add to our block.

[00:36:30] And I guess one of the properties that are kind of important in Bitcoin as is that for an outsider.

[00:36:37] An outsider doesn't need to be online, right? An outsider could just join the network in a very later stage and it would look everything like that the history was fine.

[00:36:47] So I'm not even sure if you know how would even if you had a trust to the beacon, how exactly would you use it and how did rule out the attack.

[00:36:57] Yeah.

[00:36:58] Yeah.

[00:36:59] Proceeding a new problem for every beacon you receive.

[00:37:02] I mean, there are technologies that I'm sort of familiar with from, you know, more traditional blockchain research such as like, you know, verifiable delay functions and things like these to sort of provide a random beacon.

[00:37:16] Perhaps.

[00:37:17] I sort of see where it's going though. I see how if you could include those random bits within the the hustle that you were required to solve, then it would sort of, you know, it would mitigate the attack.

[00:37:30] It would make it harder for a grouper miner to operate.

[00:37:33] But I think the sort of point is where that's the attack is already sort of carrying out this sort of timestamp manipulation thing.

[00:37:44] And so it's sort of very hard for the rest of the network to know after the fact that a certain block was was mined at a certain time and is that a block was minded.

[00:37:56] Not at that time.

[00:37:57] It seems like there's a potential for, you know, a particular minor to learn what those random bits are.

[00:38:02] And then for tense that like no further random bits ever came along and just sort of proceed under the assumption that I'm mining these particular random bits so that it would look after the fact like the block was was my much earlier than it was one sort of effective our attack which I think we haven't gotten into so much is that

[00:38:18] because the attacker is doing all this manipulation of the timestamps. There is a significant portion of the attack where it all of the blocks that the attacker seems to be constructing are actually, you know, they're actually very far in the past,

[00:38:35] relative in terms of the timestamps that they display relative to the actual currents true wall fuck.

[00:38:43] And so this is like you could say that this is actually sort of a slight problem with the first version of our, of our attack.

[00:38:51] We also discuss it in our preprint, sort of iterations on the attack that allow you to sort of, you know, undo this problem different iterations where you can sort of undo this sort of gap between the timestamp of the attack blocks and the time stamp of the, you know, of the real true

[00:39:10] by adding an additional stage where you mine later at a very low difficulty so first you you might have a very high difficulty to gain some advantage in terms of the work and then you mine at a low difficulty to gain in vanishing terms of the time stamp.

[00:39:24] So it's certainly the case that, you know, playing with the timestamp allows you to do lots of sort of wild and crazy things maybe about sort of pretending that a certain input to the blockchain was or was not some value.

[00:39:39] So it's an interesting idea.

[00:39:41] Certainly or you identified some vulnerabilities to the blockchain posed by quantum computing mentioning both your Grover based attack and also shores algorithm.

[00:39:52] Do you think the blockchain community is taking these things seriously enough.

[00:39:57] You know, while I'm back, I did some work with economists looking at, you know, based on a forward pricing model.

[00:40:05] How do you is the market actually accommodating for these things in the way that in traditional finance you would when you've got some prediction about future changes.

[00:40:16] What's your impression of that.

[00:40:18] That's a tough one. It's very hard for me to tell.

[00:40:20] I don't think, yeah, I'm not sure I could give a, you know, let me put this way.

[00:40:28] So first of all, I definitely have the feeling that few people are interested in that I didn't find too much interest by the community at large in these topics, but maybe I'm wrong here.

[00:40:45] I'm not sure. I guess another point is, let me think about it for a second.

[00:40:51] One thing I know we've I've at least I'm, I'm talking to folks on Twitter X now right and it's a very interesting situation where a lot of people in the crypto community are getting their information from Wikipedia.

[00:41:06] So they're saying things like, you know, oh, the biggest number that's ever been cracked by shores algorithm is 15. And that's what they base their truth on which we know that's not accurate right.

[00:41:17] And so it's a very interesting discussion where I'm hearing a lot of this blockchain community just going, Oh, well once Satoshi's coins are stolen then we'll just upgrade and figure it out.

[00:41:27] And that to me is very, that's a game I wouldn't want to play with my Bitcoin. But I'm very surprised that you know Bitcoin specifically is very much adamant about not upgrading until they see certain attacks happening.

[00:41:40] I don't know if you've seen that as well Gavin Peter anyone.

[00:41:43] I haven't observed that but now, despite having said what I said about like a forward pricing model if you know that something is going to be bust down the line in principle it shouldn't be worth anything now.

[00:41:54] The other thing to keep in mind is what's the average time span over which people maintain a Bitcoin if people are holding on to it as a short term asset then who cares right but if it's a long term investment like people say digital gold then that's a different story.

[00:42:10] But I definitely don't think that it's unsolvable.

[00:42:16] Okay, that's a that's a, at least from my perspective that's too strong a statement. It would be a long term threat both shores algorithm and aspects related to quantum mining but that's kind of a long term issue.

[00:42:28] I guess another kind of interesting aspect is for example, I tried to kind of edit the Bitcoin wiki and miserably failed. I just couldn't get permission to edit it.

[00:42:40] Now this is kind of embarrassing right I mean, and look, if you kind of read what's going on there. It's simply false. Many aspects there are simply false. And I guess many people try to get edit access to that wiki and simply failed.

[00:42:57] So in some sense, there are some at least systematic problems in that system. Now I don't want to.

[00:43:04] I'm sure it's pretty hard to maintain in that sense like maintaining that wiki is probably pretty hard, but I did honestly try to get access edit access. I went on IRC.

[00:43:17] I tried to say well I'm serious here and just couldn't get.

[00:43:24] Are there any examples of statements that you've seen that are very false? I'd love to hear them.

[00:43:29] Wow, it was a while back. I don't remember the exact but definitely for example the fact that even now I'm pretty sure that aspects related to quantum mining or no that's not probably and look if you I'm not even saying that as this isn't only the I guess one way to fix it is to fix the wiki and then it would propagate right.

[00:43:53] This is probably would be a good start in the center. But all if you look at the entire network, the only thing you'd see is that one to mining is not a problem.

[00:44:02] Maybe okay yeah fixing post like switching to post quantum signatures is indeed a big deal but quantum mind is I didn't see any resource on the internet explaining the probabilities to quantum mind.

[00:44:20] And this is something that you know should be fixed at one point at least in time. Yeah, so now whether how serious it is and whether what's how should it affect the value.

[00:44:34] Honestly I'm not sure if I'm the right person to ask this is to go hard for me.

[00:44:42] Maybe another way of thinking about it is to whoever owns such a corner computer. Is it worth doing this on a cost benefit basis. A corner computer is going to be quite expensive.

[00:44:56] Is there going to be positive return in playing this kind of game. Sure, sure. So that's definitely yeah. And that's something that people often miss right what's the advantage.

[00:45:06] So, I guess the most obvious advantage is simply to short Bitcoin. I'm pretty sure that if a double spending attack would happen that the price will simply crash you know if you start stealing all of you know if you start doing funky business and people realize that the system is insecure it's like run to the bank.

[00:45:27] Right and that's the right thing to do when you see such an attack. The right thing to do is to take your money to take your money and run in some sense, right to put it in an exchange.

[00:45:39] Hopefully the exchange would get a procedure Bitcoin that that's at point switch to dollars and never look back. So I'm pretty sure that if an attack that 51% attack happens for whatever reason by the way that's a good motivation for whether it's a quantum.

[00:45:57] Computer or for any other reason I'm sure you could make many hundreds of millions of dollars to the very least by shorting the Bitcoin price.

[00:46:07] So I think that the incentives are kind of this is at least one way from getting lots of money from it and others simply you know to double spend so I don't think there's any.

[00:46:19] That's not the weak spot of the attack there's ample of multi of financial motivation for doing it despite the enormous cost of developing such a quantum computer that's at least how I look at it.

[00:46:31] I'm not sure what would be the legal ramifications of it. Maybe you'd say that this could be illegal risk. I'm not even sure if that would be illegal risk to short Bitcoin at that point and you just making money from that but I'm not an legal expert I don't know.

[00:46:44] I have a feeling the regulators aren't going to quite keep up with this particular issue. They're a bit.

[00:46:49] Yeah, I don't know. I for me it seems like a legitimate attack in the sense that it's very hard to pinpoint what was this in some sense the model is supposed to take that into account that the miners are not supposed to be trusted.

[00:47:06] It's legitimate to use your mining hardware that however you see fit. If you had 51% of the hashing power buying enough hardware. I'm not sure if it would be legal to double spend.

[00:47:19] So I'm not sure if the legal consequences are major or that's the biggest risk here.

[00:47:25] And of course there are even you know parties who would be willing to take such risks, such legal risks, right.

[00:47:35] So I wouldn't want to bet that there isn't a way to make money from such an attack.

[00:47:46] Yeah, it's very interesting because it really it's a weird time right now right there is who's the guy that just went to jail for a while but basically one of his points was one of the defense was well it's allowed by the smart contract it's allowed by the code that means it's

[00:48:02] allowed by the system and the regulators were like no that's like it's still fraud in the end like you still did a bad thing right so I think it also depends a little bit on the community and how they perceive this is like is the code just whatever the code can do we can do it or are

[00:48:19] the regulators going to kind of win this battle and go like no you know this can't happen.

[00:48:24] Is it going to be considered a monopoly at some point right I think monopoly in the US is defined as.

[00:48:30] I don't know what percent market share 6070% market share on the monopoly side are they gonna say like 51% on any cryptocurrency like market shares a monopoly and we you cannot do that anymore.

[00:48:41] So it's a very interesting time to see how that would affect kind of the long term attack vectors and whether people will be discouraged from doing that or will be more encouragement to upgrade and over time.

[00:48:54] Sure.

[00:48:55] Let me put it put it in another way one way to view Bitcoin.

[00:49:01] At least classically is that you know the security model is that there is an honest majority and the point here is that you know if you have a small quantum minor in the 70 it has a fairly low hashing rate the longest chain.

[00:49:17] So the way that you count whether you're a monopoly or not is very very tricky in that regard right because again by by tweaking the difficulty.

[00:49:27] You gain an unfair advantage in some sense so I don't think that just counting how large your makes any sense anymore.

[00:49:39] And yeah, you know I'm not sure how to deal with the legal questions.

[00:49:44] I'm not sure I would say this I don't want to count as a cryptographer right one of the goals is that you're not supposed to rely on the regulators to make sure that the system is not abused.

[00:49:57] And I don't think this is definitely in the sense of post quantum signatures etc.

[00:50:02] There are good solutions to many of the problems that it would create to probably be you know a very rough sea, you know when a quantum computer which can break a CDSA.

[00:50:17] Like the Bitcoin said the signature scheme would you know arrive.

[00:50:22] I'm sure it's going to create a serious headache for the entire you know community etc.

[00:50:28] But it's not dead end and hopefully for example Bitcoin could realize that this is a serious way problem and for examples which to proof of stake.

[00:50:39] If you know if we'll have enough experience with such a system and see that everything works there aren't really serious downsides to it.

[00:50:47] That's might be a solution, there could be other solutions maybe, you know, similar to the one Gavin mentioned based on because or maybe other alternative that I'm not.

[00:50:57] We haven't thought of so I'm not too pessimistic.

[00:51:01] I do hope that the community will take it.

[00:51:06] You know that I'm not sure if I want to blame the community in some sense, I don't know.

[00:51:11] Maybe that's our job to start building that community maybe maybe that's we had a bunch more questions on the future blockchain and quantum money but I think one of the really interesting things as we wrap up this episode is.

[00:51:24] Do you have any recommendations on the best way to foster this discussion on the topic between the communities whether it's blog post should we all go rogue on Wikipedia right now and just started started getting our expertise up there to make this happen.

[00:51:39] What do you think.

[00:51:40] Oh, by the way, it wasn't that Wikipedia it was the Bitcoin wiki they have their own wiki.

[00:51:46] That makes sense. I'm not sure if I have pretty long.

[00:51:50] Imagine they have a pretty long list of people who would like to make changes and who could get a lot out of doing sure I guess that was why it was so hard for me to edit to get it right but to the point that I couldn't edit right so I'm not sure.

[00:52:05] If the what they were expecting is that you were taking a short position in Bitcoin and then publishing a potential attack back down.

[00:52:14] I was worried about yeah, I don't know.

[00:52:20] Yeah, so, so, yeah, I hope that eventually there would be some. So for example, one of the thing that I tried to do and I think was quite successful was workshop at financial cryptography like the conference.

[00:52:34] And this was actually one of the like, Bolton mentioned Andrew, he's a PhD advisor and that's how I met Andrew right for me this was really successful even just getting to meet Andrew and discuss actually many aspects with him.

[00:52:53] And I did manage to find some interest in the community, but I wouldn't say that my impression was that people are you know too much interested that there are you know there are very few people that got interested and yeah, I don't know what to say.

[00:53:08] I hope this will change. I hope we'll have we won't have to be good, you know that the damages won't be enormous and the potential is quite big even though I was I was kind of sending an optimistic message that I think it could be dealt with if there's a it could be a total

[00:53:25] and utter failure right it could be damages in the order of you know, again hundreds of billions of dollars only to blockchains right because of it. And I hope we won't get there and I hope that people would take action before that.

[00:53:42] You know, one of the things that was discussed not only by, maybe I should mention it.

[00:53:50] I think we can discuss it like the canneries, the quantum canneries I don't know. Gavin have you heard of it.

[00:53:58] Okay so one of the problems with these issues is that it's not so clear when is it going to happen if people you if it's too late it's too late right.

[00:54:14] So if you want to something like a cannery that gives you a head warning and actually think implementing such a cannery is really, really important. And what exactly does that mean so you want in some sense a challenge that on the other on the

[00:54:29] other hand, it would be worth lots and lots of millions of dollars so that people would be incentivized to solve it, rather than to steal you know, others people's money. So you want it to be a challenge that on the one hand is, or me, you know, maybe even challenges that

[00:54:46] would be 10 times easier than to break easy to say five times easier than sets, etc, etc, so that you'd have, you know, a warning ahead of time and you'll be able to prepare. So that's something that I really hopeful that would happen this idea was actually

[00:55:04] a really powerful idea. And I think that's why I owe you a second Justin Drake and actually in another paper we kind of used his idea to implement something. So I think this is really powerful and useful idea.

[00:55:19] And I think that's why we have to fund it, which is a really serious problem, who would contribute to that cannery right. And I guess there are also technical challenges right how do we find the puzzle that on the one hand is say 10 times easier than breaking easy

[00:55:34] on the other hand, no one has a solution to I don't think this is too hard to solve like but there are some technical issues to do that. Is that clear like what I'm saying Peter.

[00:55:45] Yes it is.

[00:55:47] And I gather someone's already taken the price for four bit RSA based on the previous discussions.

[00:55:54] How much was that worth.

[00:55:56] And I'm just like, this is something that I had mentioned or before.

[00:56:02] Before coming on but it's, I definitely see the sort of center chief between this was quantum canary idea and some of the ideas from the quantum crypto economics paper that I think you all have covered on previous iterations of the podcast it definitely seems like there's

[00:56:19] a very strong connection between the ability to you know make these, you know potentially start contracts that allow you to get an early warning and also the ability to you know make, you know financial instruments that sort of hedge the risk or let people understand what

[00:56:34] the risk is.

[00:56:36] And I think that's like a through line here which sort of connects all of these things and maybe we could like improve the infrastructure around that I think I agree with or that asserts to have a very important thing and understanding how the future of quantum risks is going to go.

[00:56:53] So just a technical comment Peter, like notice that here you wanted to create the puzzle so that no one could break the.

[00:57:06] No one knows the secret key to right so I'm not sure if the example that you mentioned like the same four bits RSA falls into this category one has to be careful about how you design it.

[00:57:17] I think that there's like, it's kind of similar to nothing up my sleeve.

[00:57:22] Questions right you want it to be a public key so that no one knows the secret key and on that it's kind of intermediate to solve. I hope that this makes sense.

[00:57:34] You mean, I need a secret public key. I wonder whether there is a way of doing that using multi sigs where all the way contributing parts come from different entities, a bit the way they construct verifiable functions from.

[00:57:49] I think you could even do something like there's something called hash to curve, but I guess you need to have very specific curves so that you have the hashtag curve and you want the hashtag curve to be, you know, in some sense an easier curve you can't use the one that is.

[00:58:04] So on the one hand you don't we want it to be close to Bitcoin's curve. You see what I'm saying.

[00:58:10] You want to have similar properties to it. And you know, the family that of curves isn't too large that Bitcoin uses like there are other parameters but there aren't too many. So on the one hand you want to be of a similar family.

[00:58:24] And then you want something like a hash to curve so imagine that you take the say a block and use the hash of the block as the public key.

[00:58:35] And there are some, you know, has to has to curve techniques that are known and you could use such an approach and again supposedly there's no way to do that by any other means right because it's.

[00:58:49] But again, one needs to be careful about these designs I haven't seen any such design clearly written and explain this and analyze etc. So, sorry go ahead.

[00:59:01] Yeah, that's it. I'm done.

[00:59:04] It sounds like we need to bring you guys back for a second episode where we brainstorm this more deeply so thank you so much Bolton or for coming on the show and discussing this with us so we definitely want to have you back.

[00:59:16] So far listeners if you are watching this on YouTube you can find a lot of information about the papers that we talked about in the description below.

[00:59:24] If you have any questions for us or for Bolton or make sure to comment that below and we'll pass that on and maybe answer that in the next episode of the quantum state. And of course remember to subscribe to us wherever you get your podcasts.

[00:59:38] Thank you so much.

[00:59:39] Thanks guys.

[00:59:40] This is very right yeah.