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.