To really understand what is special about Bitcoin, we need to understand how it works at a technical level. We’ll address the important questions about Bitcoin, such as: How does Bitcoin work? What makes Bitcoin different? How secure are your Bitcoins? How anonymous are Bitcoin users? What determines the price of Bitcoins? Can cryptocurrencies be regulated? What might the future hold? After this course, you’ll know everything you need to be able to separate fact from fiction when reading claims about Bitcoin and other cryptocurrencies. You’ll have the conceptual foundations you need to engineer secure software that interacts with the Bitcoin network. And you’ll be able to integrate ideas from Bitcoin in your own projects. Course Lecturers: Arvind Narayanan, Princeton University
Incentives and Proof of Work
Loading...
來自 Princeton University 的課程
比特币和数字货币技术
1815 個評分
從本節課中
How Bitcoin Achieves Decentralization
Learn Bitcoin's consensus mechanism and reason about its security. Appreciate how security comes from a combination of technical methods and clever incentive engineering.
與講師見面
Arvind NarayananAssociate Professor
Computer Science
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.
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?
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?
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?
Well again, sort of the same problem, we don't have node identity,
so we can't mail them cash to their home addresses.
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.
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.
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.
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?
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.
So that's the first incentive mechanism.
Let's come back to this point now.
This weird sort of halving phenomenon that we see here.
And this can be best illustrated graphically.
Here, I'm gonna show you a graph of time on the X-axis,
versus the total number of BitCoins in circulation.
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.
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,
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
In fact, the size of this target space is not nearly as high as 1% of
the output space.
It's much, much smaller than that, which we'll get to in a second.
But fundamentally, this is the computational problem
that a node is required to solve in order to produce the block.
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.
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.
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.
All right, so if you look at it in terms of the amount of computing that your
laptop needs to do, for example, this is simply a humongous and infeasible number.
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.
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.
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.
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.
Which means that if she has mining hardware that's about 0.1% of
total hash power, she will compute roughly one in every thousand blocks.
So why does this readjustment happen?
Why do we want to maintain this ten minute invariance?
Well, the reason is simple.
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.
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.
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.
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.
So this is a graph that shows how frequently
blocks are going to be created by the entire network.
Now I'm caring about which miner this is coming from.
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,
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.
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.
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.
