Prisoners of Work: Can Proof-of-Work Detect Quantum Computers?

Transcript

[music] [music] >> I'm really bad at keeping time and it's really I'm used to giving blackboard talks and so it's really crazy to go do in 5 minutes. So I made my own timer. That's what's going on. Okay, so um yeah, I'm Arthur and basically what we're doing is thinking about an existence result. Can we make some type of quantum system or make some type of proof of work that actually is attracting quantum miners to come join the system such so in a way that the whole thing doesn't just break down. And in order to do this in a night or in order to introduce this, there's just two things you have to know about uh

quantum computers. It's simply about Grover that has to do with hashes. It's basically a quantum uh it's a simply a quantum um database search and also Shor's algorithm which is going to have to do with signatures rather than hashes which will be on proof of proof of work with signatures which is in like for example doing a transaction um then Shor's algorithm is what is very very fast is what you you can see on the bottom. The quantum miners are there in the dashes. Um so it's no big secret that uh we think about um getting tokens from doing computational problems, right?

This is just a a bird's eye view of everything that's been going on. At one point there was even this ERC-918 or I guess it's still there for minable tokens. Um so how are we going to get quantum miners to show up and do so in a way that's not going to break everything? Um one thing that we can do is we can add two legs of difficulty. We can keep like a standard hash cash or Bitcoin type and then also allow these seals or it's a word for some type of puzzle that I'm about to introduce and let them come in for for some W blocks later. And what's going on here? Um so if you're in a legacy chain, a legacy chain Bitcoin or Ethereum. Um if somebody shows up with a quantum

miner or they start moving around cash or transactions, uh they then what they've done is a reveal. So, what type of game are they playing? So, if you think about the H and P, the E is utilities. Uh and H is what you gain from hiding. And think about who gains from hiding. If you're a quantum miner, that if you work on quantum computers and you also hold a bunch of ETH, then you do gain from hiding, right? So, there's also a payout. Also, uh E is very small if you're on a chain where everything just breaks. So, say you just if you if you get the you do a first break, then you're not going to be able to sell the token because it becomes worthless. So, this actually just turns back into the attacker's

dilemma when P plus C is in this region. Uh sorry, this turns it the attacker's dilemma is written here. It turns it into prisoner's dilemma. Um so, here's kind of a nasty slide. Uh don't have to pay too much attention to it if you're not a big fan of um cryptography, but this is just a picture of what's going on in D log. And one thing that we're doing in order to set this up is we're looking at fuzzy solutions that live with some noise around the actual target solution. Um this is how you This is what a block would look like in using this type of uh fuzzy puzzle. They These are called seals.

Um so, some W W blocks later after the first cash, which is a hash preimage, which is shown there in the top, some miners will be able to submit these seals. Um >> [sighs] >> So, but yeah, I'm talking about this this type of puzzles. I have to come up with In order to analyze or maybe even find one, first I have to figure out what am I even looking for, right? I have to come up with this thing called the I called it the limbo class. If I turn If turns out recently that there's a um uh Yamakawa and Joundry have also been doing this, and they did so in the random oracle model. Um I did it in the generic group model, which is different.

Um and um yeah. So, in proof of work, you have uh difficulty, right? And it works exactly like a thermometer or a a thermostat. Uh if anybody works with PID controllers, it is the I I the integral. If you look at T hat, that's just a basic integral of time, right? Okay. So, here's the honeypot. We're going to the money shot, right? Boom. So, so we see uh SEAL hardware going up 10 times. We see something funny going on over here. That that's nice high dot. And then what?

So, boom. There we have detected a signal from the noise. Um this is a lag one auto correlation. Um this is a detection of a quantum event coming online without the chain breaking down and crumbling. Um >> [sighs] >> So, yeah. Uh in a in in a legacy system, uh this is what would not be a good situation, but we're designing it in. Um yeah, this is kind of a a shill for for something that's not really this talk, but something that you could do on such a chain is uh so, if you have a system called bring your bring your own uh bring your own signature scheme, for example, using STARKs, you can boot you

can bootstrap into there using, for example, any any a SSH key, just get on the curve you get on the chain using your SSH key, and then switch to any other type of scheme that you like as schemes start to break down. Um so, here's the end. Uh uh The the the word I wanted to mention today was separate, and that's what this NIMBO class was. We wanted to look for types of problems that clearly separate qua- quantum capability and and classical capability, but do so in a way with dials. >> [sighs and gasps] >> Um Yeah.

I think I'm done. Yeah. >> Awesome. That was really interesting. Um my question is, okay, so a quantum computer, how does it speed up the time to search for like a hash pre-image? Does it How does that How does that >> Ah, this this is actually done in a in in a silly way and this is with Grover's algorithm and it it does so in a way that it doesn't speed up much. So So a big quantum computer sitting online mining hashes isn't going to look much different than a really huge group of mining coalition of classical computers.

But it goes totally different in the case of a discrete log. >> Interesting. We don't have much time, but um yeah, so this is one question that I I think might be interesting to answer is do you think Ethereum's current approach to post-quantum is it is it going to work? >> That's a good great question. I I am not an expert or a designer of Ethereum's. I don't even know what is called the current approach. But what I what I've seen, it looks very interesting and I would I guess again, not an expert. I guess like account abstraction is the big thing that's supposed to be able to do this. I know some of the wallet guys have been thinking a lot about this. I think people are doing good work.

This what what I've been showing here is a purely a purely academic result. >> Okay, well, thank you so much, Arthur. Please give a round of applause. >> [music]