In this portion of the lecture, we'll
look at where e-cash gets its value from.
We didn't cover this in the previous
portion when we talked about
different e-cash systems.
And the reality is that there's
a bunch of different proposals for
how you do this and
different companies do it differently.
In the very early portion of this lecture
we looked at credit card based systems,
and so in this case it's obvious that
the user's credit card is getting billed
every time they conduct a transaction.
In the case of DigiCash we have
these digital cash objects,
and they might be worth $100, but
what makes them actually worth $100?
The answer is that in order to be
issued DigiCash that's worth $100,
you would have to take $100
out of you bank account and
give it to the bank that was
issuing you the DigiCash.
Some other,
maybe more far fetched ideas was,
what if the government actually
authorized services to mint money?
They were actually authorized by
the mint of a particular country
in order to create new
cash out of thin air.
That was the idea behind NetCash.
Another proposal thought that what
if we took a pile of gold, and
we put it in a vault, and
we only issued digital cash,
that was of the same value of
the gold that was in the vault?
So e-Gold used this.
There was another company,
called Digigold,
they weren't fully backed by gold, but
they at least had partial reserves for
the amount of digital cash that they
issued that was backed by gold.
So in a digital realm, how do you create
something that has value out of thin air?
Especially when digital bits
can be copied and pasted?
The idea is to create
something that's scarce.
Scarcity is one of the features of all,
not just cash,
but other things that have been
used like gold or diamonds.
As substitutes for cash.
One way to achieve scarcity in
cryptography is to look at the solutions
to a moderately hard puzzle or
the output of a moderately hard function.
So, a moderately hard function is
a function that takes some amount of time,
computational resources, maybe memory,
in order to compute the output of.
In this case by moderate,
we mean it might take you know for
example, in BitCoin you know that in the
entire peer to peer network it takes them
about 10 minutes to solve a block, that's
the idea of a moderately hard function.
It takes a significant amount of time but
it's not also completely infeasible,
as would be the case if you were trying
to recover someone's private key
from their public key in the signature
scheme that BitCoin uses.
So, the idea of applying moderately
hard puzzles to solving cash like
systems, cash like problems was
first proposed by Dwork and
Naor, and they looked at email spam.
And so their idea was what if
every time you spend an email,
you would have to compute the solution
to some moderately hard puzzle?
For the average user it wouldn't be
that much of a barrier to sending
emails because you're not sending
emails very frequently, but
if you're a spammer and
you're trying to send out thousands or
millions of emails all at once then that
cost would become prohibitive once you
multiply it by the thousand or
million emails that you're trying to send.
This idea was later
actually implemented and
sort of independently discovered by
Adam Back in a proposal called Hashcash.
Now, proof of work or
moderately hard puzzles,
they also can be used
just to slow things down.
So if you have some function and you want
to delay the amount of time that it takes,
think about the creation of blocks
in the block chain in Bitcoin,
you can also apply it to
this problem as well.
So Hashcash as mentioned was
proposed by Back in '97 and
it was the same idea which is
that if you're a emailer or you
can think of it as a more general level,
if you are the consumer of some resource.
Then in order to consume that resource or
send an email,
you would have to generate the solution
to one of these moderately hard puzzles,
or they're also known as
proof of work protocols.
So the specific puzzle that Hashcash uses,
which will look familiar to you,
having looked at BitCoin, what happens
is you're given a hash function,
and your'e giving some string, we will
talk about what's in this string, but
the idea is you have a nonce value and
you can choose any value you want.
So the easiest thing would be to set
it equal to 0 like a counter then
step through.
So what you would do is you would hash
this string together with your chosen
nonce, say 0, and
you would look at the output.
Now the output would be random looking.
And just by chance it will have
a certain number of leading zeroes.
Maybe it has none.
The output happens to start with a 1.
Maybe you get two or
three leading zeroes, and
the idea is that you would
change this nonce value.
And you would keep computing this hash
until you happen to find some nonce value
that satisfies an output where
there's m leading zeroes,
where m could be a number like 20 or 40.
Now, what's inside the string
that you're hashing
that ties it back into the email
system that we're trying to do?
So the first thing is there's some
name that describes the service
that you're going to use
this Hashcash to spend on.
And what this does is it just means that
this cash can only be spent consuming that
service, okay?
So if you generate one coin,
you can't use it to both send email and,
you know, download a file with it.
Another thing is a validity period.
So, Hashcash has the problem of double
spending, like all e-cash systems.
And it solves it the same
way as everyone else does.
Which is the person that's receiving
the Hashcash, they just keep a list of all
the Hashcash they've seen, and they check
it to see if someone spends it twice.
Okay.
Now, this list would get really long
over time, and so if you put
a validity period into the Hashcash,
say the Hashcash lasts three months, then
your list, you can at least shorten it.
As soon as Gashcash that you've
seen that expired a month ago,
you can purge it from your list and
you can end up with a shorter list.
Another thing, another alternative if
you don't want to maintain a list,
is if you have an interactive protocol
where the person that you're giving
the Hashcash to is online when you're
ready to deliver or consume the resource.
Then what that person can do is
they can send you a challenge.
And if they send you a challenge you can
incorporate in your proof of work and
now that proof of work or
that Hashcash is specific to that person.
That person gave you the challenge, they
know that it's not a double spends because
they choose random challenges
every time they ask for Hashcash.
The final alternative is if you
are not in the interactive setting,
if you're just generating
Hashcash yourself,
it could be that a spammer still is able
to send a million emails just by spending
a really long time computing Hashcash for
all the emails that they want to spend.
And so one thing you can do is you can
prove that your Hashcash is fresh,
that it was freshly generated.
It wasn't generated before
some period in the past.
And the way you can do
this is with a beacon.
A beacon is just a fancy way of saying
some source of unpredictable randomness.
So in the Hashcash proposal,
they thought about lottery tickets.
You could use the lottery
numbers of a certain day, and
if that was involved in the creation
of this Hashcash, you know that
the person started computing the Hashcash
after those lottery numbers were released.
You could also use stock market prices, or
you could use the cover of the Times of
London, because no one could predict what
the story would be on a particular day.
At least, not before say a day
before that newspaper was published.
Now you might recognise
the Beacon from BitCoin,
because in BitCoin what Satoshi did is in
the very first block, the Genesis block,
he incorporated a newspaper article
that proved that he didn't start working
on the block chain until after the date
that that newspaper was published.
Okay?
So this could prevent some
sort of farfetched attack, but
maybe where he pre-computed
a huge block chain.
And then as other people came
into the BitCoin network and
started competing with
him to solving blocks.
If someone else solved a block,
he could just drop two or
three blocks because he had this long,
pre-computed chain, okay?
So he proved that he didn't actually do
this attack by incorporating a beacon into
the genesis block.
Let's compare and
contrast Hashcash with Bitcoin.
Now, the problem with Hashcash
is that the granularity of
the proof of worker moderately
hard puzzle, is very course.
Essentially all you can do is you
can increase the number of zeros
that are required at the output of the
hash function or you can decrease them.
What this effectively does is
double how hard the problem is.
Or you can it scale it back and
have the problem as well.
So, we know, from BitCoin,
that the block chain.
You want to solve blocks, on average,
the whole network wants to solve
them in a ten minute interval.
So let's say that, for some reason,
the network got really fast, and
they started solving blocks on average,
in eight minutes instead of ten minutes.
And so you want to make
the problem a little more hard.
Now, if BitCoin used Hashcash's, proof
of work, then they could only double it.
So we go from eight minutes to 16 minutes,
and then that's way too long.
And so what we want is a finer grade
precision where we can make it harder so
that something that's taking eight
minutes can take exactly ten minutes.
So Satochi observed that there's way of
thinking about the Hashcash proposal for
proof of work that's equivalent but
looks at it slightly different.
If you think about an output that has
a whole bunch of leading zeros, well any
number with a huge number of leading
zeros is actually just a small number.
That's another way of thinking about it.
Small numbers are numbers that
have a lot of leading zeros.
And so, what you can think of it as
equivalently is you're hashing this thing
until you get a number that's
smaller than some upper bound.
Okay?
And in Hashcash,
because they're selecting bits, that upper
bound has to be a perfect power of two.
But there's no reason that it has
to be a perfect power of two.
It could be any number that you want.
You can just pick a number and say, keep
hashing until it's less than this number.
And so with that tweak, Satoshi proposed
that, that number just be any integer.
It's called the target and the proof of
work that Bitcoin uses is very similar to
Hashcash but with this twist that
you're trying to generate a number,
an output of your hash that's
less than this particular number.
Now another proposal for
how to mint coins using proof of work
comes from Rivest and Shamir in '97.
These are the R and the S and
the RSA crypto system, respectively.
And they observed that with Hashcash style
minting what happens is when you solve,
say you create one coin,
if you want to solve the proof of work
to create a second coin, a third coin,
it takes you the same amount of
work every time you want to do it.
Now for Rivest & Shamir,
unlike at Hashcash,
where users themselves are generating
their own Hashcash, Rivest & Shamir were
interested in what if a government decided
they wanted to mint money instead?
And if you think about how
anti-counterfeiting works just in say
paper currency, in order to counterfeit
a bill there is a huge initial cost.
You have to acquire all the equipment to
mimic the security features that are on
the bills.
But, once you have all that equipment,
then it doesn't matter if you print one
bill, or you print a hundred bills,
your costs go down.
So, it has a huge fixed overhead cost,
but it has a low marginal cost.
And so, they were interested in
whether you could do a proof of
work scheme that would
mimic these properties.
Where it would cost real lot
to mint that first coin, but
once you have the computational
abilities to mint that first coin,
then minting a second, third, and
forth coin became a lot cheaper.
And so they had a proposal,
it was also based on hash functions.
In this case it was based on finding
collisions as opposed to preimages.
We won't go through
the details of their scheme but
it was interesting at a high level the
problem that they were trying to solve.
Another extension of Hashcash
comes from Hal Finney.
And what Hal didn't like about Hashcash is
that once you create a unit of Hashcash,
you spend some computational
resources creating it.
You spend it.
But then you have to retire that
coin to prevent double spending.
You have to check that that
coin doesn't get spent again.
There's no way that,
once you mint a piece of Hashcash,
it can be passed around
from person to person.
So he thought, well,
what if I set up a server?
And every time you spend
a piece of Hashcash,
you could send it to the server and
the server will sort of refresh that coin.
It won't refresh it by computing a new
proof of work, it will just refresh it
because you trust the server to only
refresh coins that it receives and
not create new coins.
Out of thin air.
And then to provide a layer of security,
what he did is,
he based this server using
a trusted platform module or a TPM.
Which is a little chip where
you can create programs.
And you can actually remotely,
over the Internet.
Check and
see that that computer is running
exactly the program that was specified.
So he set up a server that used
this remote attestation, so
you can check that this refreshing service
wasn't creating its own new coins.
It was just refreshing existing hashcash.
Now, let's think about the differences
between Hashcash and BitCoin.
So, as we mentioned, Bitcoin effectively
uses Hashcash's proof of work but
it modifies it slightly,
instead of shooting for
a number that's smaller than a perfect
power of two, it's any number.
But, that's just a slight modification.
The more substantial difference
is a little more subtle.
In Bitcoin,
the proof of work is being used for
a different purpose than minting coins.
You're not solving the proof of
work in order to mint coins.
Now you might be saying, wait a minute,
that's not right, we have these miners.
And we call them miners because
they're minting new coins.
And all miners do is solve proof of work,
right?
So obviously the proof of work is being
solved in order to mine new coins or
mint new coins.
However there is a subtle distinction
here that needs to be made.
The best way to think about this is maybe
think about what happens to BitCoin
after all 21 million BitCoins are created.
What happens is the miners, the so called
miners, they continue solving the proof of
work even though they are not
getting any new money.
Okay?
So
they're not actually solving the proof
of work to generate new money,
they're doing something else
to solve the proof of work.
Specifically what they're doing is they're
solving the proof of work to add blocks to
the block chain.
Okay?
Now the mechanism for minting new
coins piggy backs on that system
where if you create a new block will
also insert new coins into that block,
at least for a certain time period
that the claim runs over, but
it's not the idea of Hashcash where any
individual can fire up their computer and
directly mint coins by solving
a proof of work system.
BitCoin also differs from
Hashcash In the sense that
Bitcoin has a lot more to
it than Hashcash does.
In Hashcash, it's a simple
system where you mint a coin,
you send it to someone else.
In Bitcoin you have a distributed
peer-to-peer network,
you have the blockchain with the ledger,
you have transactions which have
very complicated transaction types.
So I only belabor this point because
there is this notion that, for example,
in the words of Adam Back
who invented Hashcash,
he says that Bitcoin is hashcash
extended with inflation control.
I think that's overreaching a bit,
it's sort of like saying a Tesla is just
a battery that has transportability.
So, why did Hashcash never catch on?
Probably the issue is that spam just
wasn't a big enough problem to solve.
For a lot of people,
they view spam as a nuisance, but
it's not something they want to spend
their computing cycles on combatting.
We have spam filters today, and
they work pretty well at keeping
spam out of our inboxes.
It's also possible that it wouldn't
actually prevent spammers.
In particular, if spammers had a botnet,
where they took control of a large
number of other people's computers,
then they could use those
computers to harvest hashcash.
And then they could continue spamming us.
However, that said, the idea of using
proof of work to limit resources,
it's still an idea that's kicking around.
You can see it in some proposals for
replacing network protocols, for example,
MinimaLT.