Cryptocurrency, Blockchain, and the Byzantine Generals Problem (Vitalik Buterin) | AI Podcast Clips
00:00:00.000 | If we could, can we go to the very basics?
00:00:06.140 | What is the blockchain?
00:00:08.760 | Or perhaps we might even start at the Byzantine Generals problem, the Byzantine fault tolerance
00:00:15.840 | in general that Bitcoin was taking steps to providing a solution for.
00:00:24.800 | So the Byzantine Generals problem, it's this paper that Leslie Lamport published in 1982
00:00:32.360 | where he has this thought experiment where if you have two generals that are camped out
00:00:37.580 | on opposite sides of a city and they're planning when to attack the city, then the question
00:00:45.840 | is how could those generals coordinate with each other?
00:00:49.240 | And they could send messengers between each other, but those messengers could get sniped
00:00:55.560 | by the enemy on the road.
00:00:58.340 | Some of those messages could end up being traitors and things could end up happening.
00:01:03.400 | And with just two mess generals, it turns out that there's no solution in a finite number
00:01:12.800 | of rounds that guarantees that they will be able to coordinate on the same answer.
00:01:19.080 | But then in the case where you have more than two generals, then Leslie analyzes cases like
00:01:24.960 | are the messages just oral messages?
00:01:28.720 | Are the messages signed messages?
00:01:31.220 | So I could give you a signed message and then you can pass along that signed message and
00:01:35.840 | the third party could still verify that I originally made that message.
00:01:40.520 | And depending on those different cases, there's different bounds on given how many generals
00:01:47.040 | and how many traitors among those generals and under what conditions you actually can
00:01:53.840 | agree when to launch an attack.
00:01:56.120 | So it's actually a big misconception that the Byzantine generals problem was unsolved.
00:02:02.720 | So Leslie Lamport solved it.
00:02:04.360 | The thing that was unsolved though, is that all of these solutions assume that you've
00:02:08.900 | already agreed on a fixed list of who the generals are.
00:02:12.960 | And these generals have to be kind of semi-trusted to some extent.
00:02:16.240 | They can't just be anonymous people because if they're anonymous, then the enemy could
00:02:20.160 | just be 99% of the generals.
00:02:27.280 | In the 1980s and the 1990s, the general use case for distributed system stuff was more
00:02:34.200 | kind of enterprising stuff where you could assume that you know who the nodes are that
00:02:42.920 | are running these computer networks.
00:02:45.240 | So if you want to have some kind of decentralized computer network that pretends to be a single
00:02:49.600 | computer and that you can kind of do a lot of operations on, then it's made out of these
00:02:55.480 | kind of 15 specific computers and we know kind of who and where they are.
00:02:59.880 | And so we have a good reason to believe that say at least 11 of them would be fine.
00:03:04.080 | And it could also be within a single system, almost a network of devices, sensors, so on,
00:03:10.640 | like in airplanes.
00:03:11.640 | And I think flight systems in general still use these kinds of ideas.
00:03:16.400 | So that's the 80s.
00:03:19.280 | That's the 80s and 90s.
00:03:20.440 | Now the cypherpunks had a different use case in mind, which is that they wanted to create
00:03:24.680 | a fully decentralized global permissionless currency.
00:03:29.560 | And the problem here is that they didn't want any authorities and they didn't even want
00:03:34.400 | any kind of privileged list of people.
00:03:37.160 | And so now the question is, well, how do you use these techniques to create consensus when
00:03:44.440 | you have no way of kind of measuring identities, right?
00:03:47.000 | You have no way of determining whether or not some 99% of participants aren't actually
00:03:53.760 | all the same guy.
00:03:55.280 | And so the clever solution that Satoshi had, this is kind of going back to that presentation
00:04:01.440 | I made at DEF CON a few months ago, where I said that the thing Satoshi invented was
00:04:05.600 | crypto economics, is this really neat idea that you can use economic resources to kind
00:04:13.600 | of limit how many identities you can get.
00:04:17.480 | And if there isn't any existing decentralized digital currency, then the only way to do
00:04:24.120 | this is with proof of work, right?
00:04:25.800 | So with proof of work, the solution is just you publish a solution to a hard mathematical
00:04:35.240 | puzzle that takes some kind of clearly calculable amount of computational power to solve, you
00:04:41.680 | get an identity.
00:04:42.680 | And then you solve five of those puzzles, you get five identities.
00:04:46.560 | And then these are the identities that we run the consensus algorithm between.
00:04:51.080 | So the proof of work mechanism you just described is like the fundamental idea proposed in the
00:04:57.440 | white paper that defines Bitcoin.
00:05:01.160 | What's the idea of consensus that we wish to reach?
00:05:06.080 | Why is consensus important here?
00:05:09.040 | What is consensus?
00:05:11.000 | So the goal here in just simple technical terms is to basically kind of wire together
00:05:20.000 | a set of a large number of computers in such a way that they kind of pretend to the outside
00:05:25.320 | world to be a single computer, where that single computer keeps working even if a large
00:05:30.280 | portion of the kind of constituents, the computers that make it up break.
00:05:33.760 | They kind of break in arbitrary ways, like they could shut off, they could try to actively
00:05:38.900 | break a system, they could do lots of mean things.
00:05:42.040 | So the reason why the cypherpunks wanted to do this is because they wanted to run one
00:05:49.160 | particular program on this virtual computer.
00:05:51.840 | And the one particular program that they wanted to run is just a currency system, right?
00:05:55.560 | It's a system that just processes a series of transactions and for every transaction
00:06:01.400 | it verifies that the sender has enough coins to pay for the transaction, it verifies that
00:06:06.680 | the digital signature is correct, and if the checks pass then it subtracts the coins from
00:06:11.560 | one account and adds the coins to the other account, roughly.
00:06:15.840 | So first of all, the proof of work idea is kind of, I mean, at least to me, seems pretty
00:06:21.640 | fascinating.
00:06:22.640 | It is.
00:06:23.640 | I mean, that's a, it's kind of a revolutionary idea.
00:06:27.960 | Is it obvious to come up with that you can use, you can exchange basically computational
00:06:33.280 | resources for identity?
00:06:38.920 | It actually has a pretty long history.
00:06:40.600 | It was first proposed in a paper by Cynthia Dwork and Nixon Nayor in 1994, I believe,
00:06:50.140 | and the original use case was combating email spam.
00:06:53.660 | So the idea is that if you send an email, you have to send it with a proof of work attached
00:06:57.040 | and like this makes it reasonably cheap to send emails to your friends, but it makes
00:07:01.260 | it really expensive to send spam to a million people.
00:07:04.020 | Yeah, that's a simple, brilliant idea.
00:07:07.480 | So maybe also taking a step back, so what is the role of blockchain in this?
00:07:13.440 | What is the blockchain?
00:07:14.440 | Sure.
00:07:15.440 | So the blockchain, my way of thinking about it is that it is this kind of system where
00:07:22.280 | you have this kind of one virtual computer created by a bunch of these nodes in the network.
00:07:29.960 | And the reason why the term blockchain is used is because the data structure that these
00:07:35.160 | systems use, at least so far, is one where they, different nodes in the network periodically
00:07:44.200 | publish blocks and a block is a kind of list of transactions together with a pointer, like
00:07:50.360 | a hash of a previous block that it builds on top of.
00:07:55.520 | And so you have a series of blocks that nodes in the network create where each block points
00:08:01.840 | to the previous block.
00:08:02.840 | And so you have this chain of them.
00:08:04.780 | Is a fault tolerance mechanism built into the idea of blockchain or is there a lot of
00:08:09.800 | possibilities of different ways to make sure there's no funny stuff going on?
00:08:15.240 | There are indeed a lot of possibilities.
00:08:18.440 | So in a kind of just simple architecture, as I just described, the way the fault tolerance
00:08:22.920 | happens is like this, right?
00:08:24.240 | So you have a bunch of nodes and they're just happily and occasionally creating blocks,
00:08:29.000 | building on top of each other's blocks.
00:08:31.920 | And let's say you have kind of one block, we'll call it kind of block one.
00:08:36.040 | And then someone else builds another block on a steel called block two.
00:08:40.960 | Then we have an attacker.
00:08:42.920 | And what the attacker tries to do is the attacker tries to revert block two.
00:08:46.720 | And the way they revert block two is instead of doing the thing they're supposed to do,
00:08:50.240 | which is build a block on top of block two, they're going to build another block on top
00:08:54.760 | of block one.
00:08:56.580 | So you have block one, which has two children, block two, and then block two prime.
00:09:00.680 | Now, this might sometimes even happen by random chance if two nodes in the network just happen
00:09:07.120 | to create blocks at the same time and they don't hear about each other's things before
00:09:10.760 | they create their own.
00:09:12.320 | But this also could happen because of an attack.
00:09:15.000 | Now, if this happens, you have an attack, then in the Bitcoin system, the nodes follow
00:09:22.240 | the longest chain.
00:09:23.980 | So if this attack had happened when the original chain had more than two blocks on it, so if
00:09:32.760 | it was trying to kind of revert more than two blocks, then everyone would just ignore
00:09:38.320 | it and everyone would just keep following the regular chain.
00:09:41.900 | But here, we have block two and we have block two prime.
00:09:44.360 | And so the two are kind of even.
00:09:46.440 | And then whatever block the next block is created on top of, so say block three is now
00:09:52.000 | created on top of block two prime, then everyone agrees that block three is the new head and
00:10:01.000 | block two prime is just kind of forgotten.
00:10:03.240 | And then everyone just kind of peacefully builds on top of block three and the thing
00:10:06.360 | continues.
00:10:07.360 | So how difficult is it to mess with the system?
00:10:10.920 | So how, like, if we look at the general problem, like how many, what fraction of people who
00:10:17.240 | participate in the system have to be bad players?
00:10:20.520 | In order to mess with it truly, like what's your, is there a good number?
00:10:26.280 | There is.
00:10:27.280 | Well, depending on kind of what your model of the participants is and like what kind
00:10:32.120 | of attack we're talking about, it's anywhere between 23.2 and 50%.
00:10:39.760 | Of what?
00:10:40.880 | Of all of the computing power in the network.
00:10:43.560 | Sorry, so 22 and-
00:10:45.560 | 23 point, between 23.2 and 50%.
00:10:48.680 | And 50% can be compromised.
00:10:52.760 | So like once your portion of the total computing power of the network goes above the 23.2 level,
00:11:01.800 | then there's kind of things that you can mean things that you can potentially do.
00:11:06.440 | And as your percentage of the network kind of keeps going up, then your ability to do
00:11:10.920 | mean things kind of goes higher.
00:11:12.240 | And then if you have above 50%, then you can just break everything.
00:11:15.760 | So how hard is it to achieve that level?
00:11:18.480 | Like it seems that so far, historically speaking, it's been exceptionally difficult.
00:11:25.000 | So this is a challenging question.
00:11:27.560 | So the economic cost of acquiring that level of stuff from scratch is fairly high.
00:11:33.400 | I think it's somewhere in the low billions of dollars.
00:11:37.520 | And when you say that stuff, you mean computational resources?
00:11:40.840 | Yeah, so specifically specialized hardware and of ASICs that people use to solve these
00:11:46.920 | puzzles, to do the mining.
00:11:49.600 | Small tangent.
00:11:50.600 | So obviously, I work a lot in deep learning with GPUs and ASICs for that application.
00:11:56.560 | And I tangentially kind of hear that so many of these, you know, sometimes NVIDIA GPUs
00:12:02.320 | are sold out because of this other application.
00:12:06.200 | Like what do, if you can comment, I don't know if you're familiar or interested in this
00:12:11.200 | space, what kind of ASICs, what kind of hardware is generally used these days to do the actual
00:12:17.400 | computation for the proof of work?
00:12:19.560 | Sure.
00:12:20.560 | So in the case of Bitcoin and Ethereum are a bit different.
00:12:23.160 | So in the case of Bitcoin, there is an algorithm called SHA-256.
00:12:27.520 | It's just a hash function.
00:12:29.040 | And so the puzzle is just coming up with a number where the hash of the number is below
00:12:33.160 | some threshold.
00:12:34.460 | And so because the hashes are designed to be random, you just have to keep on trying
00:12:38.800 | different numbers until one works.
00:12:41.280 | And the ASICs are just like specialized circuits that contain any of circuits for evaluating
00:12:48.600 | this hash over and over again.
00:12:50.080 | And you have like millions or billions of these hash evaluators and just stacked on
00:12:54.760 | top of each other inside of a box.
00:12:56.360 | And you just keep on running the box 24/7.
00:12:59.040 | And the ASICs, there's literally specialized hardware designed for this.
00:13:02.200 | Yes.
00:13:03.200 | This is a little bit of an amazing world.
00:13:05.640 | Another tangent, I'll come back to the basics, but does quantum computing throw a wrench
00:13:10.840 | into any of this?
00:13:13.140 | Very good question.
00:13:14.260 | So quantum computers have two main families of algorithms that are relevant to cryptography.
00:13:21.360 | One is a Shor's algorithm.
00:13:23.360 | And Shor's algorithm is one that kind of completely breaks the hardness of some specific kinds
00:13:30.360 | of mathematical problems.
00:13:32.060 | So the one that you've probably heard of is it makes it very easy to factor numbers.
00:13:36.320 | So figure out kind of what prime factors are that kind of that you need to multiply together
00:13:40.960 | to get some number, even if that number is extremely big.
00:13:45.120 | Shor's algorithm can also be used to break elliptic curve cryptography.
00:13:50.860 | It can break like any kind of hidden order groups.
00:13:54.800 | It breaks a lot of kind of cryptographic nice things that we're used to.
00:13:58.720 | But the good news is that for every kind of major use of things that Shor's algorithm
00:14:05.840 | breaks, we already know of quantum proof alternatives.
00:14:10.000 | We don't use these quantum proof alternatives yet because in many cases they're five to
00:14:13.380 | ten times less efficient, but the crypto industry in general kind of knows that this is coming
00:14:21.100 | eventually and it's kind of ready to take the hit and switch to that stuff when we have
00:14:26.960 | to.
00:14:27.960 | The second algorithm that is relevant to cryptography is Grover's algorithm.
00:14:33.160 | And Grover's algorithm might even be more familiar to AI people.
00:14:38.760 | It's basically usually described as solving search problems.
00:14:43.340 | But the idea here is that if you have a problem of the form, find a number that satisfies
00:14:50.220 | some property.
00:14:52.240 | And if with a classical computer you need to try n times before you find the number,
00:14:58.720 | then with a quantum computer you only need to do square root of n computations.
00:15:03.840 | And Grover's could potentially be used for mining, but there's two possibilities here.
00:15:11.960 | One is that Grover's could be used for mining and whoever creates the first working quantum
00:15:17.280 | computer that could do Grover's will just mine way faster than everyone else and we'll
00:15:21.600 | see another round of what we saw when ASICs came out, which is that kind of the new hardware
00:15:26.720 | just kind of dominated the old stuff and then eventually it switched to a new equilibrium.
00:15:31.040 | But by the way, way faster, not exponentially faster.
00:15:35.640 | Quadratically faster.
00:15:36.640 | Quadratically faster, which is not sort of, it's not game changing, I would say.
00:15:42.480 | It's like ASICs, like you said, it would be.
00:15:44.800 | Exactly.
00:15:45.800 | Yeah.
00:15:46.800 | So it would not necessarily break proof of work as a thing.
00:15:48.960 | That's right.
00:15:49.960 | Yeah.
00:15:50.960 | So the other kind of possible world, right, is that quantum computers have a lot of overhead.
00:15:55.400 | There's a lot of complexity involved in maintaining quantum states.
00:15:59.280 | And there's also, as we've been realizing recently, making quantum computers actually
00:16:05.680 | work requires a quantum error correction, which requires kind of a thousand real qubits
00:16:10.360 | per logical qubit.
00:16:12.080 | And so there's the very real possibility that the overhead of running a quantum computer
00:16:16.760 | will be higher than the speedup you get with Grovers, which would be kind of sad, but which
00:16:21.360 | would also mean that the given proof of work would just keep working fine.
00:16:25.480 | So beautifully put.
00:16:27.800 | So proof of work is the core idea of Bitcoin.
00:16:31.040 | Is there other core ideas before we kind of take a step towards the origin story and the
00:16:35.720 | ideas of Ethereum?
00:16:37.000 | Is there other stuff that were key to the white paper of Bitcoin?
00:16:41.080 | There's proof of work and then there's just the cryptography, just kind of public keys
00:16:44.880 | and signatures that are used to verify transactions.
00:16:48.960 | Those two are the big things.
00:16:49.920 | Thank you.
00:16:50.920 | Thank you.
00:16:50.920 | Thank you.
00:16:55.920 | Thank you.
00:17:00.920 | Thank you.
00:17:05.920 | [BLANK_AUDIO]