In the past portion of this lecture,
we looked at credit based systems.
Well, we now turn our attention
to cash based systems.
Cash based systems offer two
advantages over credit based systems.
The first is they provide
better anonymity.
When you use a credit card based system,
the bank
always knows what you're doing because
the credit card is issued in your name.
When you pay for something in cash,
nobody necessarily knows who you
are when you purchase something.
The other thing that cash can enable is
offline transactions, where you don't have
to phone home to a third party in
order to get the transaction approved.
You can give someone cash,
and the transaction is done.
And everyone is satisfied.
Maybe later they go to a third party,
like a bank, to deposit the cash.
But that third party doesn't need to
be present in the transaction itself.
Now these two requirements are sort
of a more extreme version of what
Bitcoin offers.
In Bitcoin it doesn't offer
the same anonymity level as cash.
In Bitcoin it offers pseudonymity.
Which means that some of your
transactions could be tied together if
you use the same Bitcoin addresses
to originate transactions.
Bitcoin also doesn't work
in a fully offline way.
It's true, what you could do is you
could create a Bitcoin transaction.
You could sign it.
You could hand it to someone,
maybe email it to them.
But that person won't be content that that
money won't be double spent until they see
that it's incorporated in the block chain.
So unless if you are online and are able
to broadcast that to the peer to peer
network, or alternatively,
you really trust that person you're
receiving the money from, BitCoin operates
in essentially an online fashion.
The earliest ideas of
applying cryptography to
cash came from David Chaum in 1983.
To think about David Chaum's proposal
let's start with a sort of
predecessor to his actual proposal.
So, imagine that I handed you a $100 bill,
and I also handed you a piece of paper.
And the piece of paper was a contract,
and it said that whoever comes back
to you with this piece of paper,
you'll give that $100 bill to them.
Maybe you'll give them $99
to keep a cut for yourself.
In any case,
I want you to sign this paper saying
that you will honor that arrangement.
And then I'll take that paper with me and
I'll give it to someone else.
If I give it to someone else,
then that paper's effectively worth $100.
Now you might be thinking,
what's the big deal?
All you did is convert one small
piece of paper worth $100,
the bill, into a big piece of paper
worth $100 which is the contract.
But of course, this is a physical analogy
of what you can do in a digital realm.
We are able to do digital signatures and
so
this contract could be a digital object.
As long as people trust that
the person who issued the contract
is willing to honor the contract,
then this system works.
And effectively,
this digital contract is worth $100.
Now there is one problem, however.
The problem is once it's a digital
contract, it's very easy to copy and
paste those bits, so
now you have two contracts.
If each contract's worth $100,
you just doubled your money to $200.
If you send those two contracts
to two different people,
this is called the double
spending problem.
And double spending is a problem
that exists in all ecash systems,
all ecash systems have to have some way
of dealing with double spending problem,
including BitCoin.
So the first attempt at fixing the double
spending problem is to encode a unique
serial number in each contract.
This actually isn't sufficient to
completely solve the problem, but
it's a step in the right direction.
Now the problem with the serial
number is that remember
one of the advantages of
cash is that it's anonymous.
But now if you have unique serial numbers
the bank knows who it issued this contract
to, and
they can write down their name, and
they can write down the serial
number that the contract encoded.
And then they can trace this
person as they spend the money.
So David Chaum came up with the digital
equivalent of something called
a blind signature, and
I'll explain it more in paper-based form.
To understand a blind signature, you
could imagine that we take this contract.
But in this case,
instead of it being printed in normal ink,
we print it in invisible ink, okay.
So the bank, we take it to the bank and
we say, will you sign this contract?
And they can't actually read what is
written because it's in invisible ink.
So the ink is providing two properties.
The first is the obvious property,
is that is hides the information
that's in the contract.
But the second property,
which is equally important, is that
whatever I printed on that contract
in invisible ink, I can't change it.
It's locked in.
It's fixed.
And so, if the bank decided to expose it
to see what actually was written there,
then there's no way to change it.
So this is called the binding property.
So this solution, obviously,
solves the problem of the bank
seeing your serial number.
The bank doesn't see your serial number.
However, it creates
an even bigger problem,
which is the bank doesn't see
anything about the contract at all.
It has no idea that it encodes
the fact that it owes someone $100.
The contract might encode that it
owes someone a million dollars.
So the bank wants to be convinced that
this contract is formed correctly,
that the amounts are correct.
But the paradox is,
it can't see the serial number.
Now one solution to this might be that
only the serial number is printed in
invisible ink and the rest of
the contract is printed in regular ink.
So the bank is content.
They can see what the amount is and
the user is content because
they maintain their privacy.
The problem with this is at
a cryptographic level when we transition
into digital signatures we didn't in,
at least in the early eighties
we didn't know how to do this.
Blind signatures back than were all or
nothing.
Either you hid everything that was
being signed or you hid none of it.
And so we needed a different solution.
So the question is how can I convince you
to find something if you can't read it?
And the answer is we can use what's
called the Cut and Choose Protocol.
In this protocol,
what I would do is I would create 100
contracts and hand them to you in a stack.
What you would do is you would pick
one at random from the stack, and
you would reveal the invisible ink.
And when you reveal it, you can check
that at least for that contract,
yes it did encode the fact that you owed
$100 as opposed to a million dollars.
Then you can pick a second
contract out of the pile.
You can reveal it and
make sure it also says $100.
You can keep doing it until
there's one contract left.
When you have this one contract and you're
holding it, even though you don't reveal
the invisible ink, because the other 99
all said $100 and you chose them randomly,
you're pretty sure that this one also
encodes $100, and so you sign it,
convinced to at least to a 99%
probability that it actually says $100.
So how does this help with
the double spending problem?
Well, the cut and choose protocol
allows the bank to sign a contract,
be convinced that it encodes
the right amount, and yet
not be able to see
someone's serial number.
So the idea is that you would get
granted one of these contracts.
When you wanted to do a transaction, you
would give this contract to the merchant
that you're buying the goods from,
and then the merchant would turn around
and get it back to the bank right away.
So in Chaum's earliest system this was an
online transaction system, where you had
to phone home to the bank every time you
received one of these contracts, and
we can stop calling them contracts,
we can call them coins, cause that's
another term for what they actually are.
And so when you spend a coin,
the merchants goes to the bank, and
they give it to the bank, and they ask
the bank, have you seen this coin before?
Has it come in before?
Has this serial number been spent before?
And if the bank says no, it hasn't been
spent before, then they honor the contract
component of the coin and they give
the merchant the money that's owed.
If the merchant goes to the bank and
it has been double spent,
then they can at least detect it.
Now the problem is that
if it is double spent,
you have no idea who the buyer is
because it's an anonymous system.
So that's a drawback that people
worked on later to address.
Another draw back of this system,
is that once you spend a coin,
you can't use it again.
So, it's not like an actual cash
system where you mint coins,
you hand it to the first person.
They send it to a second person,
and then the second person can
give it to a third and a fourth and you
can have a whole chain of transactions.
These type of system, every time you
receive a transaction you have to go back
to the bank and essentially cash it in.
Now the bank might issue a fresh coin,
that's fine.
But the point is that these coins are only
living for one transaction at a time.
Now one proposal of fixing the problem
that the bank has to be online
at all times, came in 1988 from
Chaum along with Fiat and Naor.
What they observed is that if you want
to prevent somebody from double spending
a digital object, it's really hard,
it might be impossible.
There's no way to stop people from
copying and pasting digital strings.
However, they also noted that in
traditional finance we have this idea of
checks and the same problem
arises if i write you a check
you have no guarantee that the money
is actually in my account.
Maybe the money is in my account
I write you a check for $100,
I have $100 in my account but
there is nothing stopping me writing
a second check to someone for $100,.
In which case if both
of you try to cash it,
then one of you won't be able to cash it.
So in order to stop bad
checks from circulating,
what the bank system uses is a detection
system, as opposed to a prevention system.
They don't try and stop you from writing
that second check But what they do is
when you write that second check they
are able to detect that it is exists.
They know who you are because you
have a bank account with the bank and
they'll punish you through a penalty for
doing that.
And so the idea of Chaum, Fiat and
Naor is is there some way to do that
type of system in the digital realm?
So if we go back to idea that coins
encode a unique serial number,
we can think about this
serial number looks like.
If the serial number, if the bank
maintains a mapping between customer
names and serial numbers,
then there's no anonymity in the system.
Every time a coin comes back to the bank
they know who it was that spent it.
And since the coin is coming from
a merchant they know where that user
spent the money.
In the original Chaum 83 scheme, the
serial numbers were just random numbers.
There was no link between
the serial number and the bank.
In fact, the bank couldn't even link
them because of the blind signature had
hid the serial numbers in the coin so the
bank didn't even see the serial numbers.
In this case it offers full anonymity.
Now the question is, is there something in
the middle between having no anonymity and
full anonymity where we can allow
partial traceability of coins
particularly in the case
where they're double spent.
So what Chaum, Fiat, and
Naor came up with is the idea that every
coin would include two serial numbers.
These serial numbers would be arranged so
that when you add them together it
actually forms the identity of
the person who withdrew the cash.
Now this is a more general description of
what this technique is, is secret sharing.
And so in a secret sharing
scheme you have a secret and
you split up into m shares and
you give to n people.
And you do it in such a way that if any m
of the n, where m is some number less than
n, as long as m people come together then
they can reconstruct what the secret is.
So you can think of this as
a 2-out-of-2 secret sharing scheme.
But there's any possibility for n and
m is also possible in the system.
So the idea is you would still
go to the bank as normal.
You would give them a contract,
just like in the previous scheme,
the only difference is that there
would be two serial numbers.
Now the bank would do the cut and choose.
You would them 100 coins and
they would open up 99 of them.
And when they open the 99,
they would check that those two numbers
also add up to your actual identity.
So they're certain that in
the contract they sign,
the coin that they sign, that those two
numbers will also add up to your identity.
So the idea is when I spend a coin,
I give it to the merchant and
these serial numbers are still hidden.
The merchant has no idea what
the two serial numbers are.
But what the merchant can do, they can
ask me to reveal one or the other.
You can think of it as the left serial
number or the right serial number.
So they might flip a coin and
ask me to reveal it.
So what happens if I
just spend the coin once,
which is what we want to encourage,
they only learn half of the secret.
So they're either learning a random number
or a random number minus my identity,
which is also a random number.
That's fully masked, so it doesn't reveal
any information about my identity.
Now if I double spend, if I send that
same coin to a second merchant, there,
one of two things can happen.
The second merchant will also
go through the same protocol,
they'll ask me to either reveal
the left share or the right share.
Assuming the first merchant asks for
the left share, and
if the second merchant also asks for
the left share, then what happens is
my identity still isn't revealed.
Now when both of those merchants cash in
their coins, the bank will detect that
double spending occurred, but they won't
have any idea about who actually did it.
However, 50% of the time,
the second merchant will ask for
a different share than the first.
So if the first asks for the left share,
the second might ask for the right share.
In this case, when they both
cash in their coins at the bank,
the bank sees that it's double spending.
Because they have different shares,
they can add those shares together.
Now they know the identity of the person
who did the double spending, and
they can leverage some fee or
punishment against that person.
Now a 50% chance of catching
double-spending isn't that great, and so
is there any way that we can boost this?
So the idea that Chaum, Fiat, and
Naor had is instead of encoding one pair
of numbers, what if we encode, say, ten?
So for example,
let's assume that they have a table,
and here's my real name, and they assign
a serial number to my name, 31337.
And so here's a list of ten numbers, ten
pairs of numbers and if you do the mental
arithmetic, you'll see that in each
case they add up to this number.
So what happens is when I spend a coin,
these numbers are originally hidden.
And the merchant gets to
go through the list and
they get to pick from each pair, whether
they want to see the left number or
the right pair, but they do this for
all ten instead of just one single pair.
So for example, the merchant might ask for
the left, the left, the right, the left,
and so on.
Now when I go to a second merchant,
we do the same protocol.
They're initially hidden, but
the second merchant gets to also,
for each pair, ask for
either the left or the right.
And what will happen with overwhelming
probability is that at some point
going through these pairs, the two
merchants will ask for different shares.
So for example in the second row, and also
in a lot of other rows in this example,
if they ask for the left share and
the right share, and
in that case you can add
together those two shares and
reveal the identity of
the person who spent the money.
And so this works to boost
the probability from one half
to actually any number that you want.
If you have N pairs,
then the probability of getting
caught is 1 minus 2 to the minus N.
And so it goes up to for
example 99.999% if you use 20 pairs.
Now, this doesn't solve the problem of
being able to spend a coin more than once.
Once you spend your coin, the merchant
still has to go back to the bank, and
they have to cash that coin in.
And you can think about why.
Why can't the merchant accept a
transaction, and then, take that coin and
turn around and spend it?
Well the answer is that that coin encodes
the identity of the original spender.
Okay so if the merchant were able to
re-spend that coin then let's say they
double spent it, then it would be the
original person who was issued the coin,
whose identity is encoded in that coin.
Now you might also think is there some
attack here where, I receive a coin and
than I turn around and
try to double spend it to falsely
blame the person who gave it to me.
But because I don't know what
the other numbers are that are hidden,
I only know the one path
of opening up the pairs,
that's all I can do if I turn around and
try and spend it myself.
I can only open up the same pairs.
Now, there's a couple of ways
we can improve this protocol.
One thing is the efficiency is really bad.
If we think about the idea of
using 20 pairs of serial numbers,
in that case we have 40 serial numbers,
okay?
20 pairs but remember when you go to
the bank initially, you hand them, say,
a 100 coins and
they're going to open at 99.
Now, in that case you have a 1%
chance of deceiving the bank.
And that's probably too high.
You probably want a lot smaller than that.
So you're more likely to go to the bank
with 1,000 coins or 10,000 coins.
And they're going to open all of them but
one.
And so, if you think about serial numbers,
40 serial numbers on each coin,
and then you're handing a thousand coins,
you're handing over 4,000
serial numbers to the bank.
So, this is a large digital object that
you're giving to the bank to audit.
So, what happened over the ensuing years
is that a bunch of cryptographers look at
this problem, and sort of in parallel to
this eCache systems being developed, there
were some advancements in an area called
zero knowledge proofs, which were talked
about in the earlier lecture in this
series when you talked about zero coin.
In this case,
they slowly replaced all these cut and
choose with more compact
zero knowledge proofs.
So it's very easy.
You just go to the bank, you hand them
one contract, and then you prove in zero
knowledge, for example,
that encodes 100 and then you're done.
You don't have to give them 100 coins,
you just give them one and
the proof is very succinct and it's short.
Another area of research was the idea
of adding divisibility to the coins.
So in Chaum's original scheme in Chaum,
Faite, and
Nior, if you got issued a coin that
was worth $100 and you went and
bought, you wanted to buy
something that was say only $75,
there was no way to split
that coin into $75 and $25.
All you could do is go back to
the bank cash in that $100 and
ask for a $75 coin and a $25 coin.
So Okamoto and
Ohta they had some interesting ideas,
it uses Merkel trees
which show up in BitCoin
to create a system that was divisible
where you could actually subdivide
the coin that are issued without
involving the bank in the process.
Now Chaum took his ideas and
he commercialized them.
He formed a company in
1989 called DigiCash.
And this was probably
the earliest company that's
dealt with online transaction or try to
solve the problem of online transaction.
They had a better five year head start.
On other companies like First Virtual and
CyberCash that we talked about
in the earlier lectures.
The actual cash in their
system was called e-cash and
they had another system called cyberbucks.
And there were a couple banks
that actually implemented it.
There were a few in the US.
There was at least one in Finland.
In this case,
in the e-cash systems, because it uses
Chaum's protocols, clients are anonymous.
So, the bank can't trace the money.
When the money comes back, the coin
comes back, it has a serial number, and
the bank doesn't know which user's
serial number that was issued to.
However, the merchants aren't.
The merchants, because they have to return
coins as soon as they receive them,
the bank knows all the information
about the merchants.
How much money's coming in at what time,
etc.
This is what the screenshot
looked like from the software.
And so you can see here, there's a wallet
and it shows you your balance and then
here's all the coins that you have that
have been issued to you from the bank.
And because you can't split coins, because
there's no way to split them up, what
the bank does is they issue you a whole
set of coins in different denominations.
So, for example, you might get eight
pennies, eight two cent coins,
eight four cent coins, etc., etc.
So that you can always sort of reconstruct
the right amount of change to pay for
the exact amount of a transaction.
When you filled out a transaction what
would happen is you would browse to
a website.
So for example,
this is to make a donation to Epic.
And if you wanted to donate the money
you would click the link on the website.
And what it would do is it would open
a server connection back to your computer.
And so your computer had to have
the full ability to be online and
accept incoming server connections.
It had to be running http.
It had to have a port open to receive it.
You had to have a full IP address.
And if it was successful,
the connection was successful,
then your wallet service would
launch on your computer and
then you were able to approve
the transaction and send the money.
Now there were certain variants
to DigiCash that were pursued.
One thing that was sort of
controversial about DigiCash,
is that the technology was patented,
in specifically the blind signature scheme
that was used, had a patent filed on it.
And so that stopped other
people from developing e-cash
systems that use the same protocol.
There were a bunch of cryptographers
that hung out on a mailing list called
the cypherpunks mailing list.
This later transitioned into
the cryptography mailing list.
And you'll know the cryptography mailing
list as the place where [FOREIGN]
originally posted the White Paper and
introduced BitCoin.
So, but before it made that transition,
the cypherpunks,
they implemented a version of e-cash,
of David's e-cash,
that was called MagicMoney, and
MagicMoney was only for experimental use,
so it did violate the patents, but because
it was non-commercial, you could use it to
experiment with, and it was sort of
a fun piece of software to play with.
The interface was all text space.
You could send transactions by email.
You would just copy and
paste literally into email.
Hopefully, you'd use a PGP key to
protect the transaction in transit, and
you could email it to another user.
The other user would import it
into a file on their computer,
which was called allcoins.dat,
which sounds a little bit like wallet.dat,
which is what Bitcoin
uses to store its coins.
Another proposal by Ben Laurie with
contributions from lots of other people is
called Lucre and
in this scheme what they did is they
targeted the blind signature scheme.
And they tried to come up with an
alternative which wouldn't be covered by
the patent, and then you can keep
the rest of the system largely the same.
Another problem that's interesting
that arises when you use DigiCash is,
as we mentioned, you can't make change.
And so, if you need to make change,
you have to go back to the bank,
and you have to get the bank to
reissue the right set of coins, so
that you can make exact change for
something.
Ian Goldberg had the idea that maybe
the merchant could send you coins back,
if they had some coins so
that you might overpay for the item, but
then you would get some coins back.
However, this introduces
a problem with anonymity.
Remember, in e-cash,
the senders are anonymous.
However, the merchants aren't.
And when the merchant sends cash back,
technically, they're the sender, so
they're anonymous.
And you, as the person who has
to turn this cash into the bank,
are not anonymous.
And so there's no way to do that system
without breaking the anonymity of
the original.
User trying to buy the goods and so he
had a different proposal where there were
different types of coins to allow
these types of transactions to occur,
allow you to get the change back and
preserve the anonymity of the user.
Now why did DigiCash fail?
The main problem with DigiCash is,
it was hard to persuade the banks and
the merchants to adopt it.
People didn't want to use it, and because
no merchants, or not a lot of merchants
were using it to accept money,
then users didn't want to use it either.
It also didn't support
user to user transactions.
At least,
it didn't support them very well.
It was really centered on the user
to merchant transaction, and so
if merchants weren't on
board with this system,
then there was no way to really
bootstrap interest in the system.
As a side note, BitCoin, because it
allows both user-to-merchant and
user-to-user transaction,
BitCoin probably part of it's success,
could be attributed to the fact that
it supported user-to-user transactions.
So there was something to
do do with your BitCoin.
At least send it to other users, while
the community tried to drum up support for
BitCoin and get merchants to accept it.
So, at the end of the day, DigiCash lost,
and the credit card companies won.
In the later years of the company,
DigiCash also experimented with
tamper-resistant hardware.
In this case, they had devices.
They might be a small device that
was usually called a wallet, or
it might be some sort of card and
what they were trying to solve
is this double-spending problem.
And in this case they weren't trying
to just merely detect the existence of
double-spending.
They were trying to actually prevent it.
So in this hardware, there might be
a counter that encodes your balance, and
every time you spend money,
the counter decreases.
If you load the card with more money,
then the counter goes up.
But the point is there is no way to
physically or digitally go in and
tamper with that counter.
So if that counter goes to zero, then that
card stops being able to spend money.
Now there were a bunch of companies that
looked at this tamper-resistant hardware,
in addition to DigiCash.
DigiCash worked later with a company
called Cafe which was based in Europe.
There was also another company formed
called Mondex that was later acquired
by MasterCard.
And Visa had their own
variant called VisaCash.
So this is the Mondex system.
Mondex consisted of a card.
This is a smart card with a chip and
there were also these wallet units and
you could load either of them with cash.
So you can get the cards and they would
have some amount of cash on them and
you can have wallets that
would also have cash on them.
And if you wanted to do
user-to-user swap of money,
what would happen is the first user
would put their card into the wallet,
you could move money off of
the card onto the wallet.
Then you'd stick the second
card in the wallet and
you'd move the money off the wallet
onto the second card and so
you could exchange cash in the way,
and it was anonymous.
Now, Mondex actually trialed their
technology in a bunch of communities.
One community is actually a city very
close to where I grew up, in Guelph,
Ontario.
And, needless to say, because it
doesn't exist today, this technology,
you know what the end of the story is,
which is that it didn't really catch on.
And the main problem with it is that
cards, Mondex cards, they're like cash.
If you lose them or
they get stolen, the money's gone.
And if there was some sort of
malfunction with the card,
if the card reader wouldn't read it,
there's no way to determine whether
that card had balance on it or not.
And so Mondex,
typically what they would do in these
scenarios is they would incur the cost.
They would assume that
the card was loaded and
then they would remunerate the user for
that lost money.
But that cost the company a lot of money.
The wallet itself was also sort
of a larger foreign factor.
It was slow.
In order to process, it was much faster
to pay with credit card or with cash.
And retailers hated having
a bunch of these terminals.
They just wanted to have one terminal for
your VISA card.
And they didn't want to have
two different terminals.
So for all of these reasons,
the Mondex experiment was not successful.
However, what was successful is
if you remember these cards,
we have these small chips on them.
So this is a smart card technology.
Today in a lot of countries,
including Canada where I live,
every single credit card and every single
debit card now has this technology on it.
They all are based on smart cards.
It's used for a different purpose.
It's not used to prevent double-spending.
It's used for authentication,
so you prove that you know the pin
that's associated with your account.
But this technology was adopted and
Mondex was using it long before
the wider banking industry made it
a standard for bank-issued cards.