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.
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 move 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 use
Mind Bit coins out of midair just by
leaving their computers on overnight.
A computer that they already had.
This was really good for
a low barrier to entry because
it gave a compelling reason for
ordinary users around the world to joining
the Bit Coin 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 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 manufactures from
dominating the bitcoin mining game.
There are only a few companies
that are able to produce
large semi-conductor 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 a trade secret to themselves and
use it to build their own very
powerful industrial mining center.
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 a 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 mos efficient processors and
the most efficient memory and storage.
And this gap actually grows over time.
This means that if we had a puzzle that
requires lots of memory to compute,
rather than just processing circuits,
then the potential improvement from
next generation's optimized hardware and
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's 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 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 crypto currency,
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.
Now this going to be the first step and
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 of v2 is
the hasha 2 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 of 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 x, n 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.
They'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 accumulator's
value with this updated value.
Now after, n iterations,
the final value of the accumulator
a is the output of this 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, do this by only storing
every other value V in the table.
Only the odd values in this case.
So, what happens if you need to access one
of the even numbered values of v which you
aren't storing,
well you need to compute it from
the values of v that you are storing.
Now, you can always compute v i.
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 reduce the amount of computation
cycles you need by 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
disadvantage of being memory hard to
compute, the scrypt-based mining puzzle
also requires an amount of memory and
end 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.
Now, a good question is, is this
memory puzzle actually ASIC resistant?
And there's some uncertainty here.
A script ASICs are already available,
at least the first generation of these.
And they are 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 ASIC's and
it's unclear how much better this
performance gap will be able to get.
There's some concern that in the alt coins
that currently use that scrypt base mining
puzzles that the parameter N
hasn't been set correctly and
this is one of the factors
Leading to ASIC's arriving.
Now this general approach of having a
memory hard hash function is good because,
as I mentioned, a 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 has 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's completed,
we want to determine whether or
not there's 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.
where tip to end then they
form a complete cycle.
So here's what a cycle of size 4 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 indexes of the edges.
Now, it's not as intuitive why
this is a memory hard function.
But the explanation is that finding
cycles in 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 check.
The only thing you need to do in order
to check the puzzle solution is to
re-compute what the edge
end 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 functions than the ones that
we've talked about so far.
One example 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.
And customize mining hardware
that's only good at solving
one instance of the puzzle, won't be
very useful once the puzzle does change.
You know 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 consists 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.