In this lecture we're going to talk about alternatives to BitCoins existing proof of work mining puzzle. Mining puzzles are at the very core of BitCoin because mining puzzles determine the incentive system in BitCoin. BitCoin miners get rewards for the puzzles that they solve. We expect that miners will spend a considerable effort trying to find any shortcuts available to them to solve these puzzles faster or more efficiently. If there's a faster way to solve puzzles, we think they'll take it. Also if there's extra stuff to do that might help the network but doesn't directly help them solve puzzles any faster, we expect that they might eventually not bother to do so at all. Therefore, the nature of the puzzle plays a very important role in steering and guiding participation in the network. Now we've talked about some of the basic features that BitCoins existing SHA-2 hash based mining puzzle already satisfies. So for example it's fairly difficult to solve a whole bunch of puzzle solutions. This makes a tax on the BitCoin network very costly or unlikely to succeed. On the other hand puzzle solutions are found at a fairly predictable rate, once every ten minutes by someone. This means that honest minors to participate have some incentive to keep participating and compensate themselves for the resources that they put into the network. Now if we were going to design a new puzzle system from scratch or modify BitCoins puzzle system to be different somehow, what else could we design the puzzle to achieve? What other kinds of behaviors would we like to encourage or disincentivize? In this lecture we're going to talk about a variety of possible alternative puzzle designs. Some of them are already used in practice in alt coins existing today. Others are research ideas that might turn out to be used in the future. The puzzles that we're look at can achieve a variety of possible goals, such as ASICs resistance, which means leveling the playing field between users with ordinary computing equipment and users with special, optimized custom hardware. We'll also look at puzzles that discourage users from delegating their participation to directors of large centralized pools. And we'll look at useful proofs of work that have some intrinsic social benefit. We'll also talk about some of the essential security requirements for mining puzzles. It doesn't do any good to have some fancy secondary feature if the puzzlel doesn't still satisfy some basic requirements that it needs to keep BitCoin secure. Before going into the alternate puzzle designs, let's talk a little bit about some of the essential requirements that any viable mining puzzle has to satisfy. Now there are many possible requirements. We've talked about some of them before. Mining puzzles need to be cheap to verify those solutions because every node on the network validates all of the puzzle solutions. Even ones that aren't involved in mining directly. Puzzles also have to have adjustable difficulty. So that the difficulty of the puzzle can be adjusted over time as new users join the network with Increasing amounts of hash power contributed. I'm going to talk in detail right now about one other central requirement which is a little bit subtle. This is that the chance of winning a puzzle solution in any unit of time should be roughly proportional to the hash power contributed. In particular, this means that really large miners with very powerful hardware should only have a proportional advantage in being the next miner to find a puzzle solution. Even small players should have some proportional chance of being successful and receiving compensation. Now, to illustrate this point, let me show you an example of a bad puzzle that doesn't satisfy this requirement. Consider a mining puzzle that takes exactly N steps to find a solution. There are examples of puzzles like this. I don't need to go into details though. But consider these a sequential proof of work. A miner would be able to find one of these proof of work solutions by computing N steps in order, in a sequence. Once it reaches N steps, it finds a solution. Now the problem is that if it takes exactly N steps in a sequence to find a puzzle solution, then the fastest miner in the network will always be the one who wins the next reward, right. So consider a scenario with two equally powerful miners and a third miner that's slightly faster at making computational steps than the other two. For every step that the small miners take, the large miner takes two steps here. This means that the large miner finds its puzzle solution at the end of N steps while the smaller are still computing theirs. In this case, the fastest miner would be the only one who would receive any compensation at all. Therefore, none of the other nodes would have any incentive to participate in the first place. So the alternative to this, a good puzzle, is one that gives every miner a chance of winning the next puzzle solution in proportion to the amount of hash power they contribute. This forms a weighted sample of all of the miners. So imagine throwing a dart at a board randomly, at a board of different sized targets where the size of the target corresponds to mining power. The more hash power you contribute, the better your chance of being the node that finds the next puzzle solution. A puzzle that has this property is sometimes called progress-free. Now this was just one of the requirements, there are others but for now we're going to move on to types of alternative puzzles and we'll discuss essential requirements as they come up.
