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.
