0:01

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.

Â 2:31

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.

Â 6:49

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.

Â 10:19

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.

Â