Now we're going to talk about another
possible desired quality for puzzles.
Which is for them to have some sort
of socially beneficial intrinsic use.
Now there's a sense in which it seems like
Bitcoin mining is extremely wasteful.
If you recall from previous lectures, we
think that BitCoin mining consumes about
150 to 900 megawatts of power in total.
And this is comparable to
the power output of a really small
hydroelectric power plant, for example.
Now, this mining work is put towards
computing these SHA2 mining puzzles
which don't serve any purpose
outside the BitCoin mining system.
So this raises a very natural question,
is there some way that we could have
a puzzle where computing
the puzzle solution actually
provides some sort of useful benefit
to society while still solving the,
satisfying the basic things
that BitCoin puzzles need.
This would amount to
something like recycling, and
it would have advantages such as lowering
the overall cost of the Bitcoin system,
and potentially reducing
Bitcoin's environmental impact.
Now there are a bunch of
natural candidates for
this that seem like they might work.
The general structure of these
possible candidates are problems that
involve finding a solution in
a potentially very large solution space.
Where the good solutions
that you're looking for
are very sparse within this space.
This is like finding
a needle in a haystack.
Problems of this sort include protein
folding, where the goal is to find
a 3D configuration of a molecule that
has a very low potential energy.
Or searching for aliens and signals from
radio signals in space and looking for
anomalous patterns that might
indicate extraterrestrial life.
Now, for the same reason these seem
like they might work as a BitCoin mining
puzzle, these have been successfully used
in the past as crowd source distributed
computing projects such as,
folding at home and at home.
Now, there are a bunch of challenges
that would have to be solved in order to
use a problem like this in Bitcoin.
In the cases that I
just described at home,
like folding at home and at home,
there's a trusted administrator
of the distributed computing project
that's able to choose which instances of
problems all of the participants in
the network are supposed to be working on.
Now in Bitcoin, there is no trusted
administrator to choose the problems.
So instead, instances of the problem
have to be generated pseudo randomly
from public information, such as the hash
of the last block that was found.
Now, in order for these to be useful,
randomly generated puzzle instances of
this sort would have to still be useful.
And also a randomly generated
puzzle solutions have to be hard.
Now it's not known how to turn any of
these problems into such a puzzle scheme.
Now there is one example that seems to
work and has already been implemented and
is somewhat used in practice
which is called Primecoin.
Now the goal here is to have a mining
puzzle where finding a puzzle solution
involves finding a chain of
very large prime numbers.
In particular,
to find a puzzle solution in Primecoin,
you have to find a Cunningham chain.
A Cunningham chain consists of
a sequence of prime numbers.
P, where each of the P's is
of the form two to the power
of some number times
a constant A plus one.
Now each P in the sequence has to be
a large probable prime, where whether or
not it's a probable prime uses
a probabilistic prime checking algorithm.
And also,
the first instance of the prime number P
has to be a multiple of the hash
function of the metadata for the block,
such as the hash of the previous block,
the Merkle root of the transaction, and
a random nonce value that
miners get to choose.
Now this has been used in
an Altcoin called Primecoin, and
it's actually paid off in some sense.
Many of the largest known
Cunningham chains have come from
miners in the Primecoin network.
Now this is interesting because there
have been distributed computing projects,
such as Primegrid, which have also tried
to find prime number chains of this sort.
This also adds some confidence that this
is truly a hard problem, because a lot of
other people are also interested in
finding solutions to this sort of problem.
So, is this actually useful?
Well, possibly.
There is at least one known use of
Cunningham prime number chains, but
the kind of Cunningham chains that
are found by Primecoin miners are actually
entirely overkill for this application.
Now, there's another approach towards
having a proof of useful work, which
is rather than focusing on the amount of
power, or work output of the network.
We might instead focus on the effect
of investment in Bitcoin mining
infrastructure.
Now just as an estimate, a lot more
than $100 million have been spent on
customized Bitcoin
mining hardware overall.
This includes designing new
Bitcoin mining equipment,
as well as actually manufacturing it.
Now this Bitcoin mining equipment is
very good at computing SHA2 hashes, but
this improvement in technology is
only useful for the Bitcoin network.
It has no other use otherwise.
So the idea is, what if we could design
a puzzle where the investment in newer and
better Bitcoin mining hardware
would itself be useful,
even if the work that's done in the power
output of the network is still wasted?
Now here's one example of
a proposal that has this quality.
It's called Permacoin, and the idea is to
replace Bitcoin mining rigs, which compute
SHA2 hash functions, with storage devices,
such as hard drives and memory.
Now the side effect of Bitcoin miners
investing in better mining equipment
would be a side effect of
having a massively distributed
replicated backup storage system.
Now the way that Permacoin works begins by
assuming that we have a large file F which
everyone knows about, and the goal of the
network is going to be to store this file.
Now for simplicity,
imagine that F is chosen globally by
a trusted dealer at the beginning.
Each user is going to store
a random subset of this file.
A Permacoin is based on an alternative
puzzle that uses storage.
Now, assume that you have the file,
F, broken up into several blocks.
The first part of Permacoin involves
building a Merkle hash tree over each of
the blocks of the file.
Now every user is going to generate
a key pair in order to mine,
which is going to include a public key,
pk.
And they're going to use their public pk,
to pseudorandomly select
a subset of these file segments F that
they're now responsible for storing.
Now for each mining attempt, the miner is
going to select a random nonce value, and
they're going to complete a hash function
h1 that includes the previous block hash,
the Merkle root of transactions.
Their public key PK in the nonce
value that they chose.
Now rather than checking if this
is a puzzle solution immediately,
they first have to fetch k pseudo-randomly
chosen file segments from the subset that
they're storing, which is
determined from that hash value h1.
Now, they compute a second hash value h2,
which includes all of the data
used to compute the first hash, as well as
the actual contents of the file blocks F.
Now from the second has value h2,
it's compared to a target,
in order to see if the puzzle solution
is actually a valid solution.
So the idea here is that the only way
to make attempts at finding a puzzle
solution, and determine if
an attempt is a valid solution,
requires you to store
the random subset of files and
blocks that you were supposed
to based on your public key.
Here's one application of
the Permacoin storage puzzle.
And this involves a kind of subtle
point about BitCoin's incentives.
There's a cost to being
an honest miner in BitCoin.
Remember that honest miners are supposed
to validate every BitCoin transaction
that's included in a block.
However validating a transaction requires
storing the unspent
transaction output's database.
Which at the current time requires
about 200 megabytes of storage.
Now maintaining this unspent
transaction output database,
doesn't help you find puzzle
solutions any faster.
It's a little bit like unpaid overtime.
So the idea would be to use the Permacoin
storage space puzzle in order to reward
miners for actually storing copies of
the unspent transaction output database.
This would reduce the marginal cost of
being honest versus just mining for
the sake of getting all of the rewards.
So to summarize this section, having
a proof-of-useful-work is a very natural
goal, but the challenges to have this
secondary side effect while still
maintaining the essential
security requirements.
There's an argument that any benefit
would have to be a pure public good.
Because if there were a way for
an individual miner to get the benefit of
the useful work they were doing, then this
benefit would also benefit an attacker.
So it would make a tax on the network
subsidized to the same amount that it
would add any secondary
improvement to society.
Now potentially viable approaches
to this include storage and
finding large trains of prime numbers.
But other potential approaches
could be possible as well.
So even though some of these useful
proofs of work have been implemented and
practiced, arguably the benefit to society
so far from these is pretty minimal.