Now let's turn to Zerocoin and
Zerocash, which are a completely
different approach to Bitcoin anonymity.
The approach is sort of to bake
it in at the protocol level, and
these are cryptographic heavyweights, and
so Zerocoin was first developed by
cryptographers at Johns Hopkins.
And later on, they started collaborating
with other researchers around the world
who had been developing a very efficient
cryptographic technique that would enable
making some of the cryptographic
operations in Zerocoin more efficient.
And that resulted in Zerocash.
As you'll see, these techniques provide a
qualitatively different level of anonymity
than mixing solutions that
sit on top of Bitcoin.
But what's the catch?
The problem is that this is not quite
backward compatible with Bitcoin.
Zerocoin and
Zerocash are going to require Altcoins.
Technically, it's possible that Zerocoin
can be deployed as what is known as a soft
fork of Bitcoin, but the practical
difficulties are high enough that this
is not really considered feasible and,
in fact,
Zerocoin developers, Intent to
deploy it as an Altcoin themselves,
instead of trying to be
compatible with Bitcoin directly.
Let's start talking about the details.
Here, let's read some of
the things that I've just said.
So Zerocoin brings protocol level mixing.
And being baked into the protocol,
what it gives you is a cryptographic
guarantee of mixing.
What does that mean?
You don't need to trust a single mix, or
even a set of mixes or a set of peers, or
anybody at all, to ensure your anonymity.
You just need to rely on
the underlying crypto being solid.
You don't een need to rely on
the miners enforcing this,
in order to achieve anonymity,
it's purely a cryptographic guarantee.
So that's really great,
that's qualitatively better
than what we have so far.
And of course, it's not currently
compatible with Bitcoin, and
here's the paper if you
wanted to look it up.
So how does Zerocoin work?
I'm going to introduce
a concept called Basecoin.
And I'm taking a few liberties with the
presentation here in order to simplify and
clarify the concepts.
I'm going to do that by mixing some
concepts from Zerocoin and Zerocash, but
toward the end, I'll make very clear what
the differences are between the two.
So like I said,
Zerocoin is an Altcoin, and
I'm going to call that Altcoin basecoin.
I'm not calling it Zerocoin because
Zerocoin is something else.
It's an extension of this basecoin.
It's something that sort of
sits on top of this Altcoin.
And the key property that gives
the anonymity is that these basecoins
can be converted into zerocoins and
back again, and when you
do that it breaks the link between the
original basecoin and the new basecoin.
So think of this as
a cryptographic mixing system.
That's provided by the protocol itself.
So how might this work?
Another way of looking at a Zerocoin
is that it's a cryptographic proof
that you own the Basecoin,
not anymore, but you owned it.
And then you made it unspendable.
A Zerocoin is something that
allows you to assert that,
to say any miner who might care.
And miners can verify these proofs and
that's what gives you the right to later
redeem a new Basecoin in exchange for
the Zerocoin.
And the analogy is a little
bit like poker chips.
So how could that work,
and what properties do these proofs
need to have in order to enable this?
So one challenge is how to
construct these proofs.
And the other trick is how do you make
sure that each proof can be spent only
once, can be used only once
to redeem a base client?
Because if you don't have that property,
then it's going to lead
to double spending.
So let's see how to do that.
It crucially involves a concept
called zero knowledge proofs.
What are zero knowledge proofs?
I'm going to tell you at a little
bit of an intuitive level,
so I'm calling it crypto magic again.
But, what it is is its a way for
somebody to prove a statement,
without revealing any other information
that makes that statement true.
You might be able to
prove a statement like,
I know an input that hashes
to this particular value.
I notice that if the input that you
had picked were long and random,
if you did a proof in such a way that
you don't actually reveal the input,
it won't necessarily allow somebody
else to infer what that input is.
A more complex version of this
is you could say I know an input
that hashes to some hash in a following
set of several different possible outputs.
And the Zero-knowledge proves that
Zerocoin is going to use something that is
very similar to the second category here.
Let's dive in a little bit more.
So, zerocoins are minted.
They come into existence by minting.
And anybody can do this.
And zerocoins come in
standard denominations.
Let's assume, for the rest of this,
that zerocoins are worth 1 basecoin each.
You could also imagine multiple
denominations co-existing.
How do you make a Zerocoin?
Well, we're going to see
that in the next slide.
But let me just say for
now that minting a Zerocoin doesn't
automatically give it any value.
You can't get free money.
It only acquires value once you
put it onto the block chain.
And so putting it on to the block chain
is going to be about as expensive
as the value of that zerocoin that
you're later going to be able to redeem.
So you have some sort of
a conservation principle here.
Okay.
So here's how specifically
in cryptographic terms
how we mint a Zerocoin.
It's something called
a cryptographic commitment.
What a cryptographic commitment is is
intuitively you can think of it as
you're taking a serial number.
A random serial number that you generated.
And putting it into an envelope.
So this intuitive notion of
putting it into an envelope,
cryptographically what
does that correspond to?
What it corresponds to is
generating another random secret r,
which you're never going
to make public and
computing the hash of the coin serial
number together with this random secret.
Now this is a little bit of a
simplification, but it really helps you to
understand the properties of the system,
so let's go with this description.
So what just happened here?
You generated arbitrarily, just like
you generate Bitcoin public keys,
a serial number for your zerocoin.
And if it were long and random,
hopefully no one else has ever picked
that same serial number before.
And you also generated this other random
number that you're going to keep secret.
And intuitively, generating a commitment
to the serial number corresponds to
putting it in an envelope and sealing it.
And mathematically, it happens by
computing the hash of the serial number
together with this random value.
Once you've generated this commitment,
what do you do with that?
At the next step is to put that
commitment onto the block chain.
That's when the zerocoin
sort of becomes real.
And doing this requires,
in a sense, burning a basecoin and
making it unspendable.
So, in concrete terms,
how would that work?
You've got the block chain over here, and
one of those transactions
might be a mint transaction.
And if you zoomed in, it would be
a transaction that's signed by Alice,
who created this zerocoin,
who minted the zerocoin.
And what we saw early in the structure
of transactions is that over here,
you would have the recipient's public,
the recipient's.
Instead of that, here you have
this cryptographic commitment.
And just like before, just like a
transaction having a pointer to a previous
transaction, the same structure is carried
over for zero coin transactions as well.
So, what has happened here,
we've spent the space coin in
order to mint the zero coin.
And this commitment, the sealed envelope
that we've put into the zero coin
that's what is going to allow us to redeem
that zerocoin later in exchange for
a basecoin once again.
So how does that work?
To spend the zerocoin later,
you will reveal that serial number
that you put inside the envelope.
And what miners will do,
it's their job to verify that the serial
number has not been spent before.
That the serial number
has not been revealed,
as a number that was put
inside some other envelope.
That's what prevents double
spending in the system.
Next you'll create a zero knowledge
proof that we just talked about, and
specifically the zero
knowledge proof will say,
I know a number r such that
the hash of the serial number
together with r corresponds to one
of the zerocoins of the block chain.
And we'll make that statement more
mathematically precise in a second.
But, think about what this says.
It doesn't reveal that random number r,
but
somehow you're proving that you
are in possession of that number.
Combined with the serial number
that you have just made public
Will result in the zerocoin that was once
in the past, put onto the block chain.
Right.
So for
somebody looking at this proof,
this is all they need to know
to verify that you earlier spent a base
coin in order to get to this point.
So this now, should give you
the right to redeem a basecoin.
But which basecoin?
And here's where the anonymity
property comes in.
You can pick an arbitrary
zerocoin in the block chain and
use that as an input to a new transaction
out of which comes a base coin and
miners will allow you to do that.
All right?
So, put a zerocoin in, take a zerocoin
out, but a different zerocoin.
And all that anybody needs to know is
that you have the right to do that
because you put in some
zerocoin in the past.
It doesn't matter which zerocoin.
And you can do that twice, you can spend
twice corresponding to a single mint
because the serial number
now will become public and
there's only one serial number
corresponding to one zerocoin.
And you only know the serial numbers
corresponding to your zero coins and
not anyone else's zerocoins.
Great.
So, where does the anonymity
property come from?
Here's the anonymity property.
Since you have kept this
random number r a secret.
And this is what is available
on the block chain.
There are a number of hashes or
commitments corresponding to
the different zerocoins that have
been put on the block chain.
Even though you've revealed the serial
number Not knowing this other random input
r,, nobody can try to brute force this and
guess which of these zero coins
corresponded to your serial number.
So even after the serial number
inside an envelope has been revealed,
and it's been verified that this serial
number was inside one of the envelopes,
we still don't know which
serial number it is.
So this is the sort of magical property
that zero cryptography give us that you
wouldn't get in a real world,
physical world base analogy of this.
So the next cool thing about this whole
construction is the fact that these
proofs are efficient I'm putting
efficient in quotes here.
The sense in which they're
efficient is that,
compared to what we know of zero knowledge
proofs and have come to expect on them,
it's quite an achievement that these
proofs are as efficient as they are.
However, compared to the efficiency
of Bitcoin transactions themselves,
these are in fact quite slow.
It occupies a space in between those two.
So exactly what I mean by efficient,
the reason it's efficient is that it
manages to avoid being linear in
the number of zerocoins on the chain,
even though that's what you would expect.
Why is that what you would expect?
Think about the statement that
the spender is proving here.
I know a random number r such that either
the hash of the serial number with
r corresponds to the first commitment, or
the first hash, or the second commitment.
Or any one of these giant
number of commitments
that reside on the block chain.
So it's a very long statement
that the prover is proving.
It's a statement whose
length is proportional
to the number of zercoins
on the block chain.
And yet,
the proof is much smaller than that.
It's not linear,
it's only logarithmic in the value N here.
And that's part of the magic of zerocoin,
that's what makes it possible
to even run the system.
All right, moving on,
let's talk about Zerocash now.
Zerocash kind of takes the cryptography
sort of to the next level.
It uses a cryptographic tool called
Snarks which we won't get into at all.
But the upshot of that,
the upshot of the use of these more
efficient cryptographic constructions for
proofs Is that the efficiency gets
to a point where the authors suggest
that you can in fact run the whole
system without having any base coin.
All transactions can be done
in the zero-knowledge matter.
You don't need to have separate expensive
transactions that are used only for
mixing, and a set of regular everyday
transactions that you use when
you don't want special anonymity
properties, that distinction is now gone.
The claim is that you can run
all of these transactions
sort of inside these envelopes, and
what I mean by that is the following.
All transactions are zerocoins, and
so zerocash becomes untraceable in
a sense because there is no base coin.
And the reason for that is that spilling
and merging of coins are also transactions
that are supported in zero cash
itself without going to basecoin.
And in particular, the transaction value
is the transaction amounts You can put
those inside the commitments, those won't
be visible on the block chain anymore.
The only thing that
the ledger records publicly,
is the existence of these transactions.
You know that Alice put in some
transaction, you know much later that Bob
retrieves some transaction, that might be
the same user, might be a different user,
but the only people who need to know
what the amount is are the sender and
the receiver of any
particular transaction.
The miners don't need to know that.
If there's a transaction fee then
the miners need to know that fee.
But that doesn't really compromise
your anonymity properly.
So the ability to run zero coin in it's
different configuration where it's
not two different coins anymore, it's not
a base coin with a mixed layer on top, but
instead an entirely untraceable
system of transactions,
puts Zerocash sort of in the next
level when it comes to anonymity.
Because a lot of the possible side channel
attacks that were true for mixing, that
were true to a certain extent at least for
Zerocoin, are no longer true for Zerocash,
because the transaction amounts will no
longer be visible in the public ledger.
But that almost sounds
too good to be true,
a completely untraceable
electronic cash system.
It is ledger-based, but
the ledger doesn't record anything that
might compromise anonymity or privacy.
Well there is one catch.
Here's the catch in zerocash,
it requires a certain setup
process to even set up the system.
Specifically one needs random and
secret inputs in order to
generate the public parameters.
Think of those as public keys,
except that these are giant public keys,
they're over a gigabyte in size.
And not only that, not only is the size a
bit of a problem, these secret inputs for
the security of the system then
have to be securely destroyed, so
that nobody knows what
those secret inputs were
that were used in order to
generate these public parameters.
That seems like a bit of a problem.
And the reason that no one can know
them is because if somebody knows them,
it doesn't mean that they will be
able to compromise anonymity, but
they will be able to create new
zerocoins for themselves and
nobody will be the wiser, which is also
an equally bad problem for the currency.
So it's kind of an interesting
sociological problem here.
How could some entity set up this system,
and then convince everybody that
they have securely destroyed
the parameters that were of course
necessary to set up the system?
So it's not entirely clear
how that can be solved.
There have been various proposals for
us, but
at the moment we don't have a very clear
idea of how to go forward on this.
So what have we seen so
far in all of the different efforts
to improve anonymity in Bitcoin?
Well, if we put them on a line,
as I'll show you in a second,
we see that there are five clearly
different levels of anonymity
that we've seen in different
proposed solutions.
And what are these?
So, let's look at not only the levels of
anonymity that these systems provide, but
also the deployability of these systems.
Let's start with Bitcoin,
which is already here.
It's only pseudonymous, it doesn't
even aspire to be really anonymous.
And we've seen that pretty bad
transaction graph analysis are possible.
I showed you many beautiful graphs with
a clustering of different address and
in many cases how to go from
those addresses to identities.
So, not a lot of anonymity
provided by Bitcoin.
The next level is simply using a single
mix stirred up in a manual way in which
people are doing right now with some
of these dedicated mix services.
And that still allows you
transaction graph analysis,
because, as you might remember from
the four principles that I gave you,
if you don't have this automated system
that has uniform chunk sizes and so on,
a lot of transaction graph
analysis is still possible.
And in addition,
you have to worry that this mix might not
be trustworthy as storing records and
might be sharing them with other people,
and, again, could get hacked, etc.
The third level that we saw
is a chain of mixes, and
this can be in a centralized model or
a decentralized model.
It doesn't matter.
Both models give you roughly
the same level of anonymity.
But where really the anonymity improvement
comes in, for this one compared to
a single mix, is that, you have
these standardized chunk sizes, and
you have a series of mixes, and
you have a variety of other bells and
whistles on top of it,
like automated clients and so on.
And for this,
some side channels are still possible,
not as bad as before, transaction
graph analysis is no longer that easy.
And you still have to worry about an
adversary who might collude with multiple
mixes or, in the decentralized model,
some peers that might be malicious and
compromise your anonymity.
This is, of course, perfectly
backward compatible with Bitcoin.
Could be deployed and adopted any day.
Hasn't quite happened yet in a way that
we would consider to be truly anonymous.
And then we saw zerocoin,
which is cryptographic mixing baked into
the protocol, doesn't depend on anybody
promising to destroy their records or
anything like that.
You just need to trust them out.
So that's a whole different
level of anonymity.
In my opinion, it still has some
possible side channels, but
it's not as bad as the other
mixing-based solutions that we saw,
where it's not baked into the protocol.
And Zerocoin of course
as we saw is an Altcoin.
So it's not quite Bitcoin compatible
in a way that one might hope.
And finally, Zerocash.
The difference between Zerocash and
Zerocoin is not so
much at a fundamental mathematical level,
but because of the fact that you can
run Zerocash in a configuration where
you get rid of the base coin altogether.
The efficiency is not too
bad in that configuration.
What that gives you is untraceability,
which is something on
top of unlinkability.
That's a new anonymity property.
There really aren't any anonymity
attacks that I can think of at least.
The downside of course is that not only
is it Altcoin, but it also has this very
tricky setup process that we don't
necessarily know how to make progress on.