Cryptocurrency, Blockchain, and the Byzantine Generals Problem (Vitalik Buterin) | AI Podcast Clips

If we could, can we go to the very basic what is the blockchain? Or perhaps we might even start at the Byzantine general's problem and Byzantine fault tolerance in general, that Bitcoin was taking steps to providing a solution for so.

The Byzantine general's problem. It's this paper that Leslie lamport published in 1982, where he has this thought experiment where if you have two generals that are camped out on opposite sides of a city and they're planning when to attack the city, then the question is, how could those generals coordinate with each other? And they could send messengers between each other, but those messengers could get sniped by the enemy on the road. Some of those messages could end up being traced. And if things could end up happening and with just two mess generals, it turns out that there's kind of no solution in a finite number of rounds that guarantees that they will be able to coordinate on the same answer. But then in the case where you have more than two generals, then Leslie analyzes cases like, are the messages kind of just oral messages? Are the messages kind of signed messages? So I could give you a signed message, then you can pass along that signed message, and the third party can still verify that I originally made that message. And depending on those different cases, there's kind of different bounds on, like, given how many generals and how many traitors among those generals and under what conditions you actually can agree when to launch an attack. So it's actually a big misconception that the Byzantine generalist problem was unsolved. So Lesnol Lamport solved it. The thing that was unsolved, though, is that all of these solutions assume that you've already agreed on a fixed list of who the generals are. And these generals have to be kind of semi trusted to some extent. They can't just be anonymous people, because if they're anonymous, then the enemy could just be 99% of the generals. So in the 1980s and the 1990s, the general use case for distributed system stuff was more kind of enterprise Y stuff where you could assume that you know who the nodes are that are running these NF computer networks. So if you want to have some decentralized computer network that pretends to be a single computer and that you can kind of do do enough operations on, then it's made out of these 15 specific computers. And we know kind of who and where they are. And so we have a good reason to believe that, say, at least 11 of them would be fine.

And it could also be within a single system. Exactly Almost a network of devices, sensors, so on, like in airplanes, and I think, like flight systems in general still use these kinds of ideas.

Yep, yep. So that's the 80s, that's the 80s and 90s. Now, the cypherpunks had a different use case in mind, which is that they wanted to create a fully decentralized, global, permissionless currency. And the problem here is that they didn't want any authorities and they didn't even want any kind of privileged list of people. And so now the question is, well, how do you use these techniques to create consensus when you have no way of kind of measuring identities? Right. You have no way of determining whether or not some 99% of participants aren't actually all the same guy. And so the clever solution that Satoshi had. This is kind of going back to that presentation I made at DEFCON a few months ago where I said that the thing Satoshi invented was crypto economics, is this really neat idea that you can use economic resources to kind of limit how many identities you can get. And if there isn't any existing decentralized digital currency, then the only way to do this is with proof of work. With proof of work, the solution is just you publish a solution to a hard mathematical puzzle that takes some and if clearly calculable amount of computational power to solve. You get an identity, and then you solve five of those puzzles, you get five identities, and then these are the identities that we run the consensus algorithm between.

So the proof of work mechanism you just described is like the fundamental idea proposed in the white paper that defines Bitcoin. What's the idea of consensus that we wish to reach? Why is consensus important here? What is consensus?

So the goal here, in just simple technical terms, is to basically kind of wire together a set of a large number of computers in such a way that they kind of pretend to the outside world to be a single computer where that single computer keeps working, even if a large portion of the constituents, computers that make it upbreak and kind of break in arbitrary ways, like they could shut off, they could try to actively break a system. They could do lots of mean things. So the reason why the cypherpunks wanted to do this is because they wanted to run one particular program on this virtual computer. And the one particular program that they wanted to run is just a currency system. Right? It's a system that just processes a series of transactions. And for every transaction, it verifies that the sender has enough coins to pay for the transaction. It verifies that the digital Signature is correct, and if the check's passed, then it subtracts the coins from one account and adds the coins to the other account, roughly.

So, first of all, the proof of work idea is kind of, I mean, at least to me, seems pretty fascinating.

It is.

I mean, that's kind of a revolutionary idea. Is it, Is it obvious to come up with that you can use, you can exchange basically computational resources for identity.

It actually has a pretty long history. It was first proposed in a paper by Cynthia Dwork and Nayor in 1994, I believe. And the original use case was combating email spam. So the idea is that if you send an email, you have to send it with a proof of work attached. And like this makes it reasonably cheap to send emails to your friends, but it makes it really expensive to send spam to a million people.

Yeah, that's a simple, brilliant idea. So maybe also taking a step back. So what is the role of blockchain in this? What is the blockchain?

Sure. So the blockchain. My way of thinking about it is that it is this kind of system where you have this kind of one virtual computer created by a bunch of these nodes in the network. And the reason why the term blockchain is used is because the data structure that these systems use, at least so far, is one where different nodes in the network periodically publish blocks. And a block is a kind of list of transactions together with a pointer, like a hash of a previous block that it builds on top of. And so you have a series of blocks that nodes in the network create where each block points to the previous block. And so you have this chain of them.

Is a fault tolerance mechanism built into the idea blockchain, or is there a lot of possibilities of different ways to make sure there's no funny stuff going on?

There are indeed a lot of possibilities. So in a kind of just simple architecture, as I just described, the way the fault tolerance happens is like this, right? So you have a bunch of nodes and they're just happily, occasionally creating blocks, building on top of each other's blocks. And let's say you have one block, we'll call it kind of block one, and then someone else builds another block. Honestly, we'll call it Block 2. Then we have an attacker. And what the attacker tries to do is the attacker tries to revert block 2. And the way they revert block 2 is instead of doing the thing they're supposed to do, which is build a block on top of block two, they're going to build another block on top of block one. So you have block one, which has two children, block two, and then block two prime. Now, this might sometimes even happen by random chance, if two nodes in the network just happen to create blocks at the same time, and they don't hear about each other's things before they create their own. But this also could happen because of an attack. Now, if this happens, you have an attack.

Then.

In the Bitcoin system, the nodes follow the longest chain. So if this attack had happened when the original chain had more than two blocks on it, so if it was trying to kind of revert more than two blocks, then everyone would just ignore it, and everyone would just keep following the regular chain. But here we have block two, and we have block two prime. And so the two are kind of even. And then whatever block the next block is created on top of, so say block 3 is now created on top of block 2 prime. Then everyone agrees that block 3 is the new head and block 2 prime is just kind of forgotten. And then everyone just kind of peacefully builds on top of block three, and the thing continues.

So how difficult is it to mess with the system? So how, like, if we look at the general problem, like how many, what fraction of people who participate in the system have to be bad players in order to mess with it? Truly? Is there a good number?

There is. Well, depending on kind of what your model of the participants is and what kind of attack we're talking about, it's anywhere between 23.2 and 50%.

Of what?

Of all of the computing power in the network.

Sorry, so 22.

Between 23.2 and 50%.

And 50% can be compromised.

So once your portion of the total computing power of the network goes above the 23.2 level, then there's kind of things that you could mean, things that you can potentially do. And as your percentage of the network kind of keeps going up, then the. Your ability to do mean things kind of goes higher. And then if you have above 50%, then you can just break everything.

So how hard is it to achieve that level? Like, it seems that so far, historically speaking, it's been exceptionally difficult.

So this is a challenging question. So the economic cost of acquiring that level of stuff from scratch is fairly high. I think it's somewhere in the low billions of dollars.

And when you say that stuff, you mean computational resources?

Yeah, so specifically specialized hardware and of ASICs that people use to solve these puzzles, to do the mining these days.

Small, small tangent. So obviously I work a lot in deep learning with GPUs and ASICs for that application. And I tangentially kind of hear that so many of these, you know, sometimes Nvidia GPUs are sold out because of this other application. Like what do. If you can comment, I don't know if you're familiar or interested in this space. What kind of asics, what kind of hardware is generally used these days to do the actual computation for the proof of work?

Sure. So in the case of Bitcoin and Ethereum are a bit different. So in the case of Bitcoin, there is an algorithm called SHA256. It's just a hash function. And so the puzzle is just coming up with a number where the hash of the number is below some threshold. And so because the hashes are designed to be random, you just have to keep on trying different numbers until one works. And the ASICs are just specialized circuits that contain circuits for evaluating this hash over and over again. And you have millions or billions of these hash evaluators just stacked on top of each other inside of a box, and you just keep on running the box 24 7.

In the ASICS, there's literally specialized hardware designed for this.

Yes.

Oh, this is living an amazing world. Another tangent. I'll come back to the basics, but does quantum computing throw a wrench into any of this?

Very good question. So quantum computers have two main kind of families of algorithms that are relevant to cryptography. One is a Shor's algorithm. And Shor's algorithm is one that kind of completely breaks the hardness of some specific kinds of mathematical problems. So the one that you've probably heard of is it makes it very easy to factor numbers. So figure out what prime factors are that you need to multiply together to get some number, even if that number is extremely big. Shor's algorithm can also be used to break elliptic curve cryptography. It can break any kind of hidden order group. It breaks a lot of cryptographic nice things that we're used to. But the good news is that for every major use of things that Shor's algorithm breaks, we already know of quantum proof alternatives. Now, we don't use these quantum proof alternatives yet because in many cases they're five to ten times less efficient. But the crypto industry in general kind of knows that this is coming eventually and it's ready to take the hit and switch to that stuff when we have to. The second algorithm that is relevant to cryptography is Grover's algorithm. And Grover's algorithm might even be more familiar to AI People that's basically usually described as solving search problems. But the idea here is that if you have a problem over the form, find a number that satisfies some property. Then if with a classical computer you need to try, and if n times before, before you find a number, then with a quantum computer, you only need to do square root of n computations. And Grovers could potentially be used for mining. But there's two possibilities here. One is that Grovers could be used for mining, and whoever creates the first working quantum computer that could do Grovers will just mine way faster than everyone else. And we'll see another round of what we saw when a six came out, which is that kind of the new hardware just kind of dominated the old stuff and then eventually it switched to a new equilibrium.

But by the way, way faster. Not exponentially faster.

Quadratically faster.

Quadratically faster. Which is not sort of. It's not game changing, I would say it's like Asics, like you said it would be.

Exactly, yeah. So it would not necessarily break proof of work as of now.

That's right, yeah.

Now the other kind of possible world. Right. Is that quantum computers have a lot of overhead. There's a lot of complexity involved in maintaining quantum states. And there's also, as we've been realizing recently, making quantum computers actually work requires kind of quantum error correction, which requires kind of a thousand real qubits per logical qubit. And so there's the very real possibility that the overhead of running a quantum computer will be higher than the speed up you get with Grover's, which would be kind of sad, but which would also mean that given proof of work would just keep working. Fine.

Beautifully put. So proof of work is the core idea of Bitcoin. Is there other core ideas before we kind of take a step towards the origin story and ideas of Ethereum? Is there other stuff that were key to the white paper of Bitcoin?

There's proof of work and then there's just the cryptography, just kind of public keys and signatures that are used to verify transactions. Those two are the big things.