0:00

So, in the previous section, we got a basic look at BitCoin's consensus

Â algorithm and a good intuition for why we believe that it's secure.

Â But recall that at the beginning of the lecture I told you that

Â BitCoin's decentralization is partly a technical mechanism and

Â partly clever incentive engineering.

Â So far, we've mostly looked at the technical mechanism.

Â Now let's talk about the incentive engineering that happens in BitCoin.

Â 0:26

I asked you to take a leap of faith with me earlier in assuming that we're able to

Â pick a random node.

Â And perhaps more problematically, that at least 50% of the time,

Â this process will be pick an honest node.

Â But of course this assumption of honesty is quite problematic, especially if there

Â are financial incentives for participants to subvert this.

Â Then why would we be expect any node to be honest, really?

Â So what we want to ask is, can we give nodes an incentive for behaving honestly?

Â 0:52

Let's look at this with respect to the picture we've been looking at.

Â This is the long-term consensus chain, and

Â this block contains an attempt to double-spend.

Â We can ask, can we penalize, somehow, the node that created this block?

Â 1:05

But this is problematic for a number of reasons, including the fact that nodes

Â don't have identities, and so there's no way to go after them to penalize them.

Â So instead, let's flip the question around and ask, can we reward the nodes that

Â created all these blocks that did end up on the long-term consensus chain?

Â 1:29

If only there were some sort of digital currency that we can use to incentivize

Â them, a decentralized one perhaps.

Â You probably see where I'm getting at.

Â In other words, we're gonna use BitCoins in order to incentivize

Â the nodes that created these blocks.

Â So how are we gonna do that?

Â Well, so far everything that I've said is just an abstract algorithm for

Â achieving distributed consensus.

Â Now we're gonna break out of that model.

Â What I'm gonna say now is specific to the fact that what we're achieving through

Â this distributed consensus process is, in fact, a currency.

Â And we're gonna incentivize these nodes by paying them in units of this currency.

Â 2:06

So how do we do that?

Â There are in fact, two separate incentive mechanisms in BitCoin.

Â And the first one is called the block reward.

Â So what is the block reward?

Â It's just this.

Â According to the rules of BitCoin, the node that creates each block

Â gets to include a special transaction in that block.

Â And that special transaction is a coin creation transaction.

Â 2:29

And this node can also choose the recipient address of this transaction.

Â So of course, that node will typically choose and address belonging to itself

Â as a recipient of this coin creation transaction, there-by paying itself.

Â You can think of it as a payment in exchange for

Â the service of creating that block to go onto the consensus chain.

Â 2:49

In fact, the value of this coin creation transaction has an interesting property.

Â It's currently fixed at 25 bitcoins, but it actually halves every four years.

Â We're now in the second period.

Â For the first four years of BitCoin's existence, it was 50 BitCoins.

Â Now it's 25, and it's going to keep halving.

Â This has some interesting consequences.

Â We'll come back to that on the next slide.

Â But let me ask you this.

Â It appears, based on what I've said here, that this node gets the block award

Â regardless of whether it proposes a block with only valid transactions,

Â or it behaves maliciously.

Â So how are we actually providing any incentives for

Â honest behavior via this block reward?

Â 3:30

But aha, think about this.

Â Well, how well does node sort of get to collect its reward?

Â That will only happen if this block ends up on the long-term consensus branch,

Â because that's the only case in which this coin creation transaction will be

Â considered valid, because the coin creation transaction is not special.

Â It's just like every other transaction.

Â It's only valid if it ends up on the consensus chain, so

Â that's the incentive mechanism here.

Â It's very subtle, but it's a very neat trick, and so

Â if it incentivizes nodes to behave honestly, or

Â at the very minimum, it incentivizes nodes to behave in a way that they think other

Â nodes are going to agree with in creating the next blocks of the block chain.

Â 4:34

And this over here was the first period where each block

Â resulted in 50 new BitCoins being created.

Â And roughly at the end of last year, that block reward halved from 50 to 25, and

Â you can see that every four years,

Â extending well into the future, the slope of this curve is gonna keep halving.

Â And this is a geometric series, and

Â you might know that it means that there is a finite sum.

Â And in fact, there is a total finite supply of BitCoins.

Â And if you add up all these numbers, it works out to 21 million,

Â based on the rate of new block creation, which I'm gonna get to in a second.

Â 5:07

Also worth noting is that this is the only way in which new BitCoins are created.

Â There is no other coin generation mechanism, and

Â that's why this is a final and total number as the rules stand now at least,

Â 5:18

for how many BitCoins there can ever be.

Â And this new block creation reward is actually gonna run out.

Â So that sounds a bit weird.

Â Does that mean that the system will stop working and

Â become insecure because nodes no longer have the incentive to behave honestly?

Â Well not quite, because this is only the first of two incentive mechanisms.

Â There is quite another incentive mechanism, called the transaction fee.

Â And what is a transaction fee?

Â So the creator of any transaction, not the creator of a block,

Â but the creator of a transaction when Alice is paying Bob.

Â What she can do,

Â is she can choose to make the output value of that coin less than the input value.

Â 5:58

And the way that all the nodes interpret this difference, according to the rules of

Â BitCoin, is that it's a transaction fee, and whoever creates the block that first

Â puts that transaction into the block chain gets to collect that transaction fee.

Â 6:12

So if you're a node that's creating a block that contains, say 200 transactions,

Â then the sum of all those 200 transaction fees accrues to you, and

Â to the address that you put into that block.

Â 6:24

Of course, this transaction fee is purely voluntary, like a tip.

Â But we expect, based on our understanding of the system,

Â that as the block reward starts to run out, it'll become more and

Â more important to almost mandatory for nodes to put a transaction fee into

Â their transactions in order to get a reasonable quality of service.

Â And to a certain degree, this is already starting to happen now.

Â But precisely how this system will evolve, it really depends on a lot of game theory,

Â which hasn't been fully worked out yet.

Â So that's an interesting area of open research in BitCoin.

Â So now we've acquired an understanding of how the nodes that create these blocks

Â are incentivized to act honestly or follow the protocol.

Â And so if we address a few more of these remaining problems, we'll be all set

Â to have a really good understanding of how Bitcoin achieves decentralization.

Â What are these remaining problems?

Â Well one of them, the first major one, is the leap of faith that I

Â asked you to take, which is that somehow we can pick a random node.

Â And the second is,

Â that we've created a new problem by giving nodes these block rewards and

Â incentives, which is that you could easily get into a free-for-all where everybody

Â wants to run a Bitcoin node in the hope of capturing some of these rewards.

Â And a third one is an even trickier version of this problem,

Â which is that an adversary might create a whole different number of civil nodes

Â in order to really try to subvert this consensus process.

Â So number three is sort of a trickier version of number two.

Â 7:50

It turns out that all of these problems are related, and

Â all of them have the same solution.

Â And that solution is called Proof of Work.

Â So what is Proof of Work?

Â Here's the key idea.

Â 8:00

Instead of picking a random node, we do something a little bit different.

Â Which is, we approximate selecting a random node by instead selecting nodes

Â in proportion to a resource that we hope that nobody can monopolize.

Â What does that mean?

Â Well, if that resource that we're talking about is computing power,

Â then it's a proof-of-work system where we somehow select nodes

Â in proportion to their computing power.

Â 8:25

Alternately, it could be in proportion to ownership of the currency,

Â and this is a legitimate alternate model.

Â It's not used in BitCoin, but it's been proposed, and

Â it's used in a lot of alternatives to BitCoin.

Â And that's called proof-of-stake, which we'll see in a later lecture.

Â 8:40

But let's come back to proof-of-work,

Â let's try to get a better idea of what this means.

Â Selecting nodes in proportion to their computing power,

Â another way to understand this is that we're allowing nodes to compete with

Â each other by using their computing power.

Â 8:56

And that will result in nodes automatically being picked

Â in that proportion.

Â So those are two equivalent ways to view proof-of-work.

Â You can also think of a third way, which is that we're making it moderately hard

Â through proof-of-work to create new identities.

Â So it's sort of attacks on identity creation and on the civil attack.

Â This may all appear a bit vague.

Â So let me actually go ahead and show you, what is the exact proof-of-work system

Â that's used in BitCoin, and that's gonna make things a lot clearer.

Â So, here it is.

Â 9:29

It's called hash puzzles, and what these means, is that in order to create a block,

Â the node that proposes that block is required to find a number, a nonce.

Â Such that, when you put together in the block the nonce, the prev_hash,

Â and the list of transaction that comprised that block, and

Â take the hash of this whole, long string.

Â Then that hash output

Â should be a number that is very small that falls into this small target space here

Â in relation to this very large space that is the output space of that hash function.

Â 10:03

Let's look at it one more time.

Â As we looked at it earlier,

Â normally a block contains series of transactions that you're proposing.

Â In addition, a block also contains a pointer to the previous block,

Â as we saw, and a pointer is just a string in this context.

Â But in addition here, we're requiring that a block also contain a nonce.

Â 10:22

And why is this?

Â And the idea is that we wanna make it moderately difficult to in fact,

Â find a nonce that satisfies this required property,

Â which is that hashing the whole block together including that nonce

Â is going to result in a particular type of output.

Â 10:40

And so we believe that if the hash function is secure,

Â then the only way to succeed in solving this hash puzzle

Â is to just try enough nonces one by one until you get lucky.

Â So specifically, if this target space were just 1% of the overall output space,

Â you would have to try about 100 nonces before you got lucky.

Â And if this hash function were to behave essentially randomly, only 1 in 100

Â nonces will result in an output that falls within this target space.

Â 11:26

Now, this notion of hash puzzles and proof-of-work completely does away with

Â the requirement for somebody, somehow to pick a random node.

Â Instead, nodes are simply all the time

Â independently competing to solve these hash puzzles.

Â 11:42

And once in a while, one of them will get lucky and will find a random nonce

Â that satisfies this property, and that node then gets to propose the next block.

Â That's how it's completely decentralized.

Â There is nobody deciding which node it is that gets to propose the next block.

Â 12:01

So let's look at it in a little bit more detail now.

Â There are three properties that I wanna show you,

Â essential properties of this proof-of-work function of this hash puzzle.

Â And the first is, that it needs to be quite difficult to compute.

Â I said moderately difficult, but what I mean by moderately difficult as of today,

Â and you'll see why it varies with time,

Â it's about 10 to the 20 hashes per block that you need to compute.

Â So the size of the target space is only 1 over 10 to the 20 of the size of

Â the output space of this hash function.

Â 12:40

And because of this, only some nodes even bother to compete

Â in this block creation process, and this is what is known as BitCoin mining.

Â Basically, the process of repeatedly trying and solving these hash puzzles, and

Â we call these node miners.

Â 12:55

And because of how capital incentive this process is,

Â this goes back to what I said at the beginning.

Â That even though technically anybody can be a miner, there's been a lot of

Â concentration of power, or concentration of participation in the mining ecosystem.

Â So that's the first property of these proof-of-work puzzles.

Â 13:16

The second property, is that we want this cost to be parameterizable.

Â It's not a cost that is fixed over all time.

Â And the way that that's accomplished is that all the nodes in

Â the BitCoin Peer-to-Peer network will automatically re-calculate the target,

Â that is the size of the target space as a fraction of the output space,

Â every two weeks.

Â And they do it in such a way that they maintain this invariant,

Â which is that the average time between any two successive walks produced globally

Â in the overall BitCoin network is about ten minutes.

Â 13:48

So let's think about what this means.

Â What this means is, that if you're a miner, and

Â you've invested a certain fixed amount of hardware into BitCoin mining, but

Â the overall mining ecosystem is growing.

Â More miners are coming in, or they're deploying faster and faster hardware.

Â That means that over a two week period,

Â slightly more blocks are going to be found than expected.

Â And so nodes will automatically readjust the target.

Â And so the amount of work that you have to do

Â to be able to find a block is going to increase.

Â So if you put in a fixed amount of hardware investment, the rate at which you

Â find blocks is actually dependent upon what other miners are doing.

Â So there's a very nice formula to capture this,

Â which is that the probability that any given miner Alice is going to win the next

Â block is equivalent to the fraction of global hash power that she controls.

Â 14:57

If blocks were to come very close together,

Â then there would be a lot of inefficiency, and

Â we would lose the optimization benefits of being able to put a lot of transactions.

Â As it currently stands, several hundred transactions in a single block.

Â If you went down from ten minutes to five minutes, it would probably be okay,

Â and there are a lot of discussions about if we're doing an altcoin now,

Â what is the block latency that we should have?

Â But everybody agrees that the block latency should be a fixed amount.

Â It can not be allowed to go down without limits, and

Â that's why you have this automatic target recalculation property.

Â Now, because of the way that this cost function and proof-of-work is set up,

Â it allows us to reformulate our security assumption.

Â Here's where we finally depart from the leap of faith that I asked you to take

Â several slides ago.

Â Instead of saying that somehow the majority of nodes are honest, in a context

Â where nodes don't even have identities and not being clear about what that means,

Â we can now state crisply that a lot of attacks on BitCoin are infeasible

Â if the majority of miners weighted by hash power are following the protocol.

Â Or, are honest.

Â 16:07

And the reason for that is if a majority of miners, weighted by hash power

Â are honest, because of this competition for proposing the next block, this will

Â automatically ensure that there is at least a 50% chance that the next block to

Â be proposed at any point is coming from an honest node, instead of a malicious one.

Â 16:26

Let's now look at the consequences of the fact that solving hash puzzles

Â is probabilistic.

Â Why is it probabilistic?

Â Because nobody can predict which nonce is going

Â to result in solving the hash puzzle.

Â The only way to do it is to try nonces one by one, and hope that one succeeds.

Â Right?

Â And so this process is called mathematically, Bernoulli trials.

Â I won't go into detail on that, but you can look it up.

Â But typically, nodes try so many nonces that

Â a discrete probability process called Bernoulli trials can be well approximated

Â by a continuous probability process called a poisson process.

Â And the end result of all of that is that the distribution,

Â the probability density function of the time to find the next block

Â by any node in the network globally, looks something like this.

Â It's called an exponential distribution.

Â But really, the upshot is, that there is some small probability

Â that if a block has been found now, the next block is going to be found very soon,

Â or within a few seconds, or within a minute.

Â 17:30

And there is also some small probability that it'll take a long time,

Â maybe an hour to find the next block.

Â But overall, the network automatically adjusts the difficulty so

Â that the inter block time is maintained at an average long-term of ten minutes.

Â 17:56

If you're a miner specifically interested in how quickly you're finding blocks,

Â what does this probability density function look like?

Â Well, it's going to have the same shape, but

Â it's just going to have a different scale on the X-axis.

Â Again, it can be represented by a nice equation.

Â For a specific miner, the mean time to find a block,

Â given that you've just found a block,

Â 18:16

is going to be 10 minute divided by the fraction of hash power that you control.

Â So again, if you have 0.1% of the total network hash power,

Â you're gonna find blocks once every 10,000 minutes, which is several days.

Â And so, not only is your main time between blocks going to be very high, the variance

Â of the time between blocks found by you is also going to be very high.

Â And this has some important consequences that

Â we're gonna be looking at in later lectures.

Â 18:44

So now let's turn to the third important probability of

Â this proof-of-work function.

Â Which is, that it's actually trivial to verify

Â the new node has computed proof-of-work correctly.

Â What does that mean?

Â Even if it takes a node on average ten to the 20 tries to find a nonce

Â that succeeds in finding the right property of the hash function,

Â that nonce must be published as part of the block.

Â So it's trivial for any other node to look at the block contents,

Â hash them all together, and verify that the output is less than the target.

Â 19:19

So this is an important property because,

Â once again, it allows you to get rid of centralization.

Â You don't need any centralized authority verifying that miners are doing their

Â job correctly.

Â Any node, or any miner, can instantly verify that a block found by another miner

Â satisfies this proof-of-work property, and there-by they can be sure that

Â this miner put a lot of computing power into finding that block.

Â