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.