\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}
\usepackage{../langs}

\begin{document}

\section*{Handout 7 (Bitcoins)}

In my opinion Bitcoins are an elaborate Ponzi
scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still
the ideas behind them are really beautiful and not too
difficult to understand. Since many colourful claims about
Bitcoins float around in the mainstream and not-so-mainstream
media, it will be instructive to re-examine such claims from a
more technically informed vantage point. For example, it is
often claimed that Bitcoins are anonymous and free from any
potential government meddling. It turns out that the first
claim ignores a lot of research in de-anonymising social
networks, and the second underestimates the persuasive means a
government has at its disposal. 

There are a lot of articles, blogposts, research papers
etc.~available about Bitcoins. Below I will follow closely the
very readable explanations from

\begin{center}
\url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\
\url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}
\end{center}

\noindent The latter also contains a link to a nice youtube
video about the technical details behind Bitcoins.

Let us start with the question who invented Bitcoins? You
could not make up the answer, but we actually do not know who
the inventor is. All we know is that the first paper

\begin{center}
\url{https://bitcoin.org/bitcoin.pdf}
\end{center}

\noindent is signed by Satoshi Nakamoto, which however is
likely only a pen name. There is a lot of speculation who
could be the inventor, or inventors, but we simply do not
know. This part of Bitcoins is definitely anonymous. The paper
above is from the end of 2008; the first Bitcoin transaction
was made in January 2009. The rules in Bitcoin are set up so
that there will ever only be 21 Million Bitcoins with the
maximum reached around the year 2140. Currently there are
already 11 Million Bitcoins mined. Contrast this with
traditional fiat currencies where money can be printed almost
at will. The smallest unit of a Bitcoin is called a Satoshi
which is the $10^{-8}$th part of a Bitcoin. Remember a Penny
is the $10^{-2}$th part of a Pound.

The two main cryptographic building blocks of Bitcoins are
cryptographic hashing (SHA-256) and public-private keys using
the elliptic-curve encryption scheme for digital signatures.
Hashes are used to generate `fingerprints' of data that ensure
integrity (absence of tampering). Public-private keys are used
for signatures. For example sending a message, say $msg$,
together with the encrypted version

\[
msg, \{msg\}_{K^{priv}}
\]

\noindent allows everybody with access to the corresponding
public key $K^{pub}$ to verify the message came from the
person who knew the private key. Signatures are used in
Bitcoins for verifying the addresses where the Bitcoins are
sent from. Addresses in Bitcoins are essentially the public
keys. There are $2^{160}$ possible addresses, which is such a
vast amount that there is not even a check for duplicates, or
already used addresses. If you start with a random number to
generate a public-private key pair it is very unlikely that
you step on somebody else's shoes. Compare this with the
email-addresses you always wanted to register with, say
Googlemail, but which are already taken.

One main difference between Bitcoins and traditional banking
is that you do not have a place that records the balance on
your account. Traditional banking involves a central ledger
which specifies the current balance in each account, for
example 

\begin{center}
\begin{tabular}{l|r}
account & balance\\\hline
Alice   & \pounds{10.01}\\
Bob     & \pounds{4.99}\\
Charlie & -\pounds{1.23}\\
Eve     & \pounds{0.00}
\end{tabular}
\end{center}

\noindent Bitcoins work differently in that there is no such
central ledger, but instead a public record of all
transactions ever made. This means spending money corresponds
to sending messages of the (oversimplified) form 

\begin{equation}
\{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}
\end{equation}

\noindent These messages, called transactions, are the only
data that is ever stored in the Bitcoin system (we will come
to the precise details later on). The transactions are
encrypted with Alice's private key such that everybody,
including Bob, can use Alice's public key $K^{pub}_{Alice}$
for verifying that this message came really from Alice, or
more precisely from the person who knows $K^{priv}_{Alice}$. 

The problem with such messages in a distributed system is what
happens if Bob receives 10, say, of these transactions. Did
Alice intend to send him 10 Bitcoins, or did the message get
duplicated by for example an attacker re-playing a sniffed
message? What is needed is a kind of serial number for such
transactions. This means transaction messages look more like 

\begin{center}
$\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$
\end{center}

\noindent There are two difficulties, however, that need to be
solved. One is who is assigning serial numbers to Bitcoins and
also how can Bob verify that Alice actually owns this Bitcoin
to pay him? In a system with a bank as trusted third-party,
Bob could do the following:

\begin{itemize}
\item Bob asks the bank whether the Bitcoin with that serial
      number belongs to Alice and Alice hasn’t already spent
      this Bitcoin.
\item If yes, then Bob tells the bank he accepts this Bitcoin.
      The bank updates the records to show that the Bitcoin
      with that serial number is now in Bob’s possession and
      no longer belongs to Alice. 
\end{itemize}

\noindent But for this banks would need to be trusted and
would also be an easy target for any government interference,
for example. Think of the early days of music sharing where
the company Napster was the single point of ``failure'' which
was taken offline by law enforcement. Bitcoins is more a
system like BitTorrent without a single central entity that
can be taken offline.

Bitcoin solves the problem of not being able to rely on a bank
by making everybody the ``bank''. Everybody who cares can have
the entire transactions history starting with the first
transaction made in January 2009. This history of transactions
is called \emph{blockchain}. Bob, for example, can use his
copy of the blockchain for determining whether Alice owned the
Bitcoin he received, and if yes transmits the message to every
other participant on the Bitcoin network. The blockchain looks
roughly like a very long chain of individual blocks

\begin{center}
\includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png}
\end{center}

\noindent Each block contains a list of individual
transactions, called txn in the picture above, and also a
reference to the previous block, called prev. The data in a
block (txn's and prev) is hashed so that the reference and
transactions in them cannot be tampered with. This hash is the
unique serial number of each block. Since this
previous-block-reference is also part of the hash, the whole
chain is robust against tampering. I let you think why this is
the case?\ldots{}But does it actually eliminate all
possibilities of fraud?

We can check the consistency of the blockchain by checking
whether all the references and hashes are correctly recorded.
I have not tried it myself, but it is said that with the
current amount of data (appr.~12GB) it takes roughly a day to
check the consistency of the blockchain on a ``normal''
computer. Fortunately this ``extended'' consistency check
usually only needs to be done once. After that it only needs 
to be updated consistently.

Recall I wrote earlier that Bitcoins do not maintain a ledger
listing all the current balances in each account. Instead they
record only transactions. While a current balance of an
account is not immediately available, it is possible to
extract from the blockchain a transaction graph that looks
like the picture shown in Figure~\ref{txngraph}. Take for
example the rightmost lower transaction from Charles to Emily.
This transaction has as receiver the address of Emily and as
the sender the address of Charles. In this way no Bitcoins can
appear out of thin air (we will discuss later how Bitcoins are
actually generated). If Charles did not have a transaction of
at least the amount he wants to give Emily to his name
(i.e.~send to an address with his public-private key) then
there is no way he can make a payment to Emily. Equally, if
now Emily wants to pay for a coffee, say, with the Bitcoin she
received from Charles she can essentially only forward the
message she received. The only slight complication with this
setup in Bitcoins is that ``incoming'' Bitcoins can be
combined in a transaction and ``outgoing'' Bitcoins can be
split. For example in the leftmost upper transactions in
Figure~\ref{txngraph} Fred makes a payment to Alice. But this
payment (or transaction) combines the Bitcoins that were send
by Jane to Fred and also by Juan to Fred. This allows you to
``consolidate'' your funds: if there was always only a way to
split transactions, then the amounts would get smaller and
smaller. 

But in Bitcoins it is also important to have the ability to
split the money from one or more incoming transaction to
potentially more than one receiver. Consider again the
rightmost transactions in Figure~\ref{txngraph} and suppose
Alice is a coffeeshop owner selling coffees for 1 Bitcoin.
Charles received a transaction from Zack over 5 Bitcoins, say.
How does he pay for the coffee? There is no real notion of
change in the Bitcoin system. What Charles has to do instead
is to make one single transaction with 1 Bitcoin to Alice and
with 4 Bitcoins going back to himself, which then Charles can
use to give to Emily, for example.

\begin{figure}[t]
\begin{center}
\includegraphics[scale=0.4]{../pics/blockchain.png}
\end{center}
\caption{Transaction graph that is implicitly recorded in the
public blockchain.\label{txngraph}}
\end{figure}

Let us make another example. Let us assume Emily received 4
Bitcoins from Charles and independently has another
transaction (not shown in the picture) that sends 6 Bitcoins
to her. If she now wants to buy a coffee from Alice for 1
Bitcoin, she has two possibilities. She could just forward the
transaction from Charles over 4 Bitcoins to Alice splitted in
such a way that Alice receives 1 Bitcoin and Emily sends the
remaining 3 Bitcoins ``back'' to herself. In this case she would
now be in the ``posession'' of two unspend Bitcoin
transactions, one over 3 Bitcoins and the independent one over
6 Bitcoins. Or, Emily could combine both transactions (one
over 4 Bitcoins from Charles and the independent one over 6
Bitcoins) and then split this amount with 1 Bitcoin going to
Alice and 9 Bitcoins going back to herself. 

I think this is a good time for you to pause to let this
concept of transactions really sink in\ldots{}abusing the
words of a famous 60ies Band: With Bitcoins ``all you need is
transactions''. There is really no need for a central ledger
and no need for an account balance as familiar from
traditional banking. The closest what Bitcoin has to offer for
the notion of a balance in a bank account are the unspend
transaction that a person (more precisely a public-private key
address) received. That means transactions that can still be
forwarded. 

After the pause also consider the fact that whatever
transaction is recorded in the blockchain will be in the
``historical record'' for the Bitcoin system. If a transaction
says 1 Bitcoin goes from address $A$ to address $B$, then this
is what will be---$B$ has then the possibility to spend the
corresponding Bitcoins, whether the transaction was done
fraudulently or not. There is no exception to this rule.
Interestingly this is also how Bitcoins can get lost: One
possibility is that you send Bitcoins to an address for which
nobody has generated a private key. For example by a typo in
the address field---bad luck for fat
fingers.\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}
The reason is that nobody has a private key for this erroneous
address and consequently cannot forward the transaction
anymore. Another possibility is that you forget your private
key and you had messages forwarded to your address
corresponding to your the public key. In this case also bad
luck: you will never be able to forward this message again,
because you will not be able to form a valid message that
sends this to somebody else (we will see the details of this
later). But this is also a way how you can get robbed of your
Bitcoins. By old-fashioned hacking-into-a-computer crime, for
example, an attacker might get hold of your private key and
then quickly forward the Bitcoins that are in your name to an
address the attacker controls. You will never have again
access to these Bitcoins, because for the Bitcoin system they
are assumed to be spent. And remember with Bitcoins you cannot
appeal to any higher authority. Once it is gone, it is gone.
This is different with traditional banking where at least you
can try to harass the bank to roll back the transaction. 


This brings us to back to problem of double spend. Say Bob is
a merchant. How can he make sure that Alice does not cheat?
She could for example send a transaction to Bob. But also
forward the ``same'' transaction to Charlie, or even herself.
If Alice manages to get the second transaction into the
blockchain, Bob will be cheated out of his money. The problem
in such conflicting situations is how should the network
update their blockchain? You might end up with a picture like
this

\begin{center}
\includegraphics[scale=0.4]{../pics/bitcoindisagreement.png}
\end{center}

\noindent Alice convinced some part of the ``world'' that she
is still owner of the bitcoin and some other part of the
``world'' thinks its Bob's. How should such a disagreement be
resolved? This is actually the main hurdle where Bitcoin
really innovated. The answer is that Bob needs to convince
``enough'' people on the network that the transaction from
Alice to him is legit. However what does ``enough'' mean in a
distributed system? If Alice sets up network of a billion
puppy identities and whenever Bob tries to convince, or
validate, that he is the rightful owner of the Bitcoin, the
puppy identities agree. Bob would then have no reason to not
give Alice her coffee. But behind his back she has convinced
everybody else on the network that she is still the rightful
owner of the Bitcoin. After being outvoted, Bob would be a tad
peeved. 

The reflex action of a security engineer would be to make the
process of validating as cheap as possible. The idea is that
Bob will get enough peers to agree with him that he is the
rightful owner. But such a solution has always the limitation
of that Alice could set up an even bigger network of puppy
identities. So the really cool idea of Bitcoin is to go into
the other direction of making the process of transaction
validation (artificially) as expensive as possible, but reward
people for helping with the validation. This is really a novel
and counterintuitive idea that makes the whole system work so
beautifully.

\subsubsection*{Proof-of-Work}

In order to make the process of transaction validation
difficult, Bitcoin uses a kind of puzzles. Solving the puzzles
is called mining where whoever solves a puzzle will be awarded
some bitcoins. At the beginning of Bitcoins this was 50
Bitcoins, but the rules of Bitcoin are set up such that this
amount halves every 210,000 transactions or so. Currently you
will be awarded 25 Bitcoins for solving a puzzle. Because the
amount will halve again and then later again and again, around
2140 it will go below the level of 1 Satoshi. In that event no
new Bitcoins will ever be created again and the amount stays
fixed. There will be still an incentive to help with
validating transactions, because there is the possibility in
Bitcoins to award a transaction fee to whoever solves a
puzzle. At the moment this fee is usually set to 0, since the
incentive for miners is the currently 25 Bitcoins that are
awarded for solving puzzles. 
 
What are the puzzles that miners have to solve? Recall that
Bitcoins uses the hash-function SHA-256. The puzzle is roughly
as follows: Given a string, say \code{"Hello, world!"}, what
is the salt so the hash starts with a long run of zeros?
Suppose we call the hash function \code{h}, then we could try 
the salt \code{0} as follows:

\begin{quote}
\code{h("Hello, world!0") =}\\
\mbox{}\quad\footnotesize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\\
\end{quote}

\noindent OK this does not have any zeros at all. We could 
next try the salt \code{1}: 

\begin{quote}
\code{h("Hello, world!1") =}\\
\mbox{}\quad\footnotesize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\\
\end{quote}

%\begin{center}
%\begin{tabular}{@{}l@{}}
%\footnotesize\code{h("Hllo, world!1")}\\ 
%\;\;\scriptsize\code{%\ldots\\
%\footnotesize\code{h("Hello, world!4250")}\\ 
%\;\;\scriptsize\code{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}
%\end{tabular}
%\end{center}



\end{document}

bit coin
https://bitcoin.org/bitcoin.pdf
https://bitcoin.org/bitcoin.pdf

A fistful of bitcoins
http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf

Ross Anderson & Co (no dispute resolution; co-ercion)
http://www.cl.cam.ac.uk/~sjm217/papers/fc14evidence.pdf

http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/
http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html

http://randomwalker.info/bitcoin/