We're going to start by talking about ASIC resistant mining puzzles. These are far and away the most widely discussed and sought after alternative mining puzzles. Now, there are several reasons why we might want an ASIC resistant mining puzzle. If you recall from previous lectures, bitcoin mining used to be done using ordinary computers like CPUs and GPUs, then eventually moved towards customized FPGA devices, and now mining is mostly conducted using very powerful optimized ASIC chips, which are so vastly more effective than general purpose computing equipment that it doesn't even pay off to use an ordinary computer or a very old generation of mining equipment. But this is too bad in a way because it used to be very appealing that ordinary users could mine bitcoins out of thin air just by leaving their computer on overnight, a computer that they already had. This was really good for a lower barrier to entry because it gave a compelling reason for ordinary users around the world to join the bitcoin mining network and participate. So, wouldn't it be nice if we could go back to the good old days when it was possible to mine bitcoins using ordinary general purpose computing equipment? So, the approach to go back to this is to come up with a puzzle that reduces the gap between the most cost effective customized hardware and general purpose equipment that ordinary people already have. A separate goal is to try to prevent the very large ASIC manufacturers from dominating the bitcoin mining game. There are only a few companies that are able to produce large semiconductor fabrication in order to actually produce the ASICs. So, this represents a sort of consolidation of power. Now, a lot of customers of bitcoin mining ASICs have this concern that the manufacturers are going to delay the shipment of their mining devices in order for them, the manufacturers, to use the mining devices themselves in order to use them for their own benefit to get their own rewards at the expense of their customers. Another concern is that if there is some breakthrough, and there is a vastly more efficient ASIC design, whoever comes up with that design might keep it as trade secret to themselves and use it to build their own very powerful industrial mining center, and then they would be able to dominate the network. So, the approach here might be to build a puzzle that reduces the gap between potential future hardware ASIC designs and the ASICs that we already have, which are largely distributed to ASIC mining customers. We're going to start by talking about the most widely used approach towards having an ASIC resistant puzzle. This is called the memory hard puzzle. Now, the premise here is fairly simple, and it's based on a well-known phenomena since the 80s about the change in the performance of computing equipment over time. Since the 80s, the performance of processing has increased at an exponential rate. You've probably heard of this referred to as Moore's Law. Now, the performance of memory and storage have also increased at an exponential rate, but this rate is much slower, much lower rate than that for processors. There's a performance gap between the most efficient processors and the most efficient memory in storage, and this gap actually grows over time. This means that if we had a puzzle that required lots of memory to compute rather than just processing circuits, then the potential improvement from next generations optimized hardware, the current generation of optimized hardware, or even general purpose computing equipment would be much lower, and that's what we want. So, we're going to talk now about the most popular instance of a memory hard puzzle. This is called scrypt. Scrypt is actually a memory hard hash function. And an scrypt-based mining puzzle is the same as the bitcoin mining puzzle, just replacing the SHA2 hash with the scrypt hash. Scrypt is memory hard in the sense that it has a constant time memory tradeoff. This means that the hash can be computed using a fixed amount of memory. It's possible to compute it using less memory, but doing so increases the amount of time that it takes to compute. Now, as I mentioned, this puzzle is actually widely used in bitcoin alternatives, including the second most popular cryptocurrency, Litecoin, and a variety of others. One thing that is to scrypt's advantage is that this hash function is also used in other places in security, especially password hashing which has similar goals to ASIC resistance in bitcoin mining. This gives extra confidence that if there are security problems with the hash function, then other people are looking at them and might find them. Now, the basic way that scrypt works goes in two steps. The first step involves filling a large block of random access memory with random values, and the second step involves reading from this memory in a random order. Now, I'm going to give a detailed illustration of just how the scrypt hash function works. Now, the goal here is going to be to compute the scrypt hash function of an input string X. This is going to be the first step. The goal is to fill a block of memory containing N cells with random values. Here, N is 36. Now, these values are going to be filled in in sequential order. The first value, V1, is simply the hash of the input string X, where the hash function H is an ordinary hash function like SHA2. Now, the second value, V2, is the hash SHA2 of the previous value, V1. This is the same as the hash function applied to the input string X twice, and so on. The third value, V3, is the hash function applied to the input value X three times, and so on. After N iterations, all N memory cells are filled up with pseudo random values, and the last value is the same as the hash function H applied to XN times. Now, in the next step, we're going to read back the values of memory in random order. Now, we're going to begin by having an accumulator value A which involves computing the hash function H one more time on the last value. Now, for N iterations, we're going to use the current value of the accumulator A to pick an index I out of these N potential memory cells. Now, we're going to read that value of memory, xor, with the current accumulator value A, take the hash H once more of this value, and replace the accumulators value with this updated value. Now, after N iterations, the final value of the accumulator A is the output of this hash function. Now, let me explain the intuition for why this scrypt hash function is memory hard. Now, you can compute this by using the N memory cells as described just before. It's also possible to compute the scrypt hash value using less memory. Suppose you wanted to cut down the amount of memory you needed by half. You could do this by only storing every other value, V, in the table, only the odd values in this case. Now, what happens if you need to access one of the even numbered values of V which you aren't storing or you need to compute it from the values of V that you are storing? Now, you can always compute VI by computing the hash H of VI minus one. Now, this works, and you got away with using less memory, but you had to compute an extra value for H. Now, this intuition holds up. On average, if you wanted to reduce the amount of memory by half, you would have to increase the amount of computation cycles you need by a factor of one and a half, and so on. Now, to talk a little bit about scrypt use in practice, there are a couple of disadvantages. One is that, even though it has this advantage of being memory hard to compute, the scrypt-based mining puzzle also requires N amount of memory and N cycles in order to check a proof of work puzzle solution. This puts a constraint on how large you can set N. In other words, how memory hard you can make it. Now, a good question is, is this memory hard puzzle actually ASIC resistant? And there's some uncertainty here. Scrypt ASICs are already available, at least the first generation of these, and they're at least somewhat faster than what you can do with general purpose computing equipment like CPUs and GPUs. There are several companies competing to make faster scrypt ASICs, and it's unclear how much better this performance gap will be able to get. There is some concern that in the alt coins that currently use scrypt-based mining puzzles that the parameter N hasn't been set correctly, and this is one of the factors leading to ASICs arriving. Now, this general approach of having a memory hard hash function is good because, as I mentioned, that scrypt is used in other applications like password hashing. And so, if there's any future improvements in password hashing, then memory hard mining puzzles would be able to use these new password hashing functions and be able to achieve the desired effect. Now, I'm going to talk about another approach to having a memory hard proof of work mining puzzle. This puzzle is called Cuckoo hash cycles. And the main advantage this has over scrypt is that it doesn't require any random access memory to check a puzzle solution. Now, we're going to look at how this works, which involves, for every mining attempt, we're going to start with a potential solution X, which you can think of as a random string. And we're going to use the following procedure to determine whether or not X is a puzzle solution. For the first step, we're going to select the E pseudo random edges in this graph. Now, for each edge, we're going to pick a random node from the top set of nodes and a random node from the bottom set of nodes. Now, we do this by computing hash values using, again, the underlying hash value H, which can just be an ordinary hash function. Now, the edges are filled in in the graph as illustrated below. Once the graph is completed, we want to determine whether or not there is a cycle in the graph of size K. Now, a cycle is a set of edges such that if you align the edges tip to tip or tip to end, then they form a complete cycle. So, here's what a cycle of size four would look like in this illustrated graph. Now, K is another parameter of the puzzle. If the graph determined by input X has a cycle of size K, then we say that this has a solution, and we just output the input value X as well as the evidence that there was a cycle. So, the K index is of the edges. Now, it's not as intuitive why this is a memory hard function, but the explanation is that this as a finding cycles and graphs is a fairly well-studied problem, and the best known algorithms for doing this do require a large amount of memory. Now, what is really clear to see is that this puzzle is very easy to track. The only thing you need to do in order to check the puzzle solution is to recompute what the edge N points would be for each of the K edges provided using the input value X. You only have to compute K hash functions, and no random access memory is required. Now, there are even more approaches towards building ASIC resistant mining puzzles. I'm only going to describe these really briefly. One is to simply build much more complicated hash functions than the ones that we've talked about so far. One example of this is the mining puzzle based on the X11 hash function, which is simply 11 well-known hash functions strung together in a sequence. Another approach is to have a mining puzzle that's a moving target. Here, you would have a mining puzzle that actually changes all together every so often. This means that optimized mining hardware for one puzzle probably wouldn't be good at solving all of the puzzles even after the puzzle changes. In customized mining hardware, that's only good at solving one instance of the puzzle, won't be very useful once the puzzle does change. Now, it's unclear exactly how we would change the puzzle every so often in order to maintain the security requirements that we need. Now, there's a counter argument that says that there's really no point in trying to make an ASIC resistant puzzle because the SHA2-based mining puzzle that we already have is already good enough. Now, the SHA2 circuit is pretty well-understood. We have a good idea of what's the optimal way of computing SHA2. As a result, bitcoin mining ASICs aren't changing very much, and it seems unlikely that there's going to be a breakthrough in computing these proof of work solutions any faster. Now, even as it is today, mining ASICs consist of multiple copies of the same basic SHA2 circuit. And the only difference between the largest ASICs and the smallest or cheapest ASICs is that they have more copies of the same essential circuit. This means that even the biggest mining ASICs are only a little bit more cost effective than the smaller ASICs. They compute puzzle solutions faster, but they're also more expensive.
