--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/ho08.tex	Thu Nov 20 01:38:08 2014 +0000
@@ -0,0 +1,180 @@
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../graphics}
+
+\begin{document}
+
+\section*{Handout 7 (Bitcoins)}
+
+In my opinion Bitcoins are a 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 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 their
+disposal. Below I will follow the very readable explanations
+about Bitcoins from
+
+\begin{center}
+\url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/}\smallskip\\
+\url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}
+\end{center}
+
+
+Let us start with the question who invented Bitcoins? You
+could not make up the answer, but we actually do not know who
+is the inventor. 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 first
+Bitcoin transaction was made in January 2009. The rules in
+Bitcoin are set up so that there will only be 21 Million
+Bitcoins with the maximum reached around year 2140. Contrast
+this with other 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}$ part of a Bitcoin. Remember a
+Penny is the $10^{-2}$ part of a Pound.
+
+The two main cryptographic building blocks of Bitcoins are
+cryptographic hashing (SHA-256) and public-private keys using 
+elliptic-curve encryption for digital signatures. Hashes are 
+used to generate `fingerprints' of data that ensures its
+integrity. 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 public key 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 come 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 test
+for duplicates\ldots{}or already used addresses.
+
+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
+central ledger, but a public record of all transactions. This
+means spending money corresponds to sending messages of
+the very rough form 
+
+\begin{center}
+$\{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}$
+\end{center}
+
+\noindent They are encrypted with Alice's private key such
+that everybody, including Bob, can use Alice's public key
+$K^{pub}_{ALice}$ in order to verify the 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 messages. Did Alice intend to send him 10 Bitcoins, or
+did the message by Alice get duplicated by for example an
+attacker re-playing a sniffed message. What is needed is
+a kind of serial number for such messages. Meaning transaction 
+messages look more like 
+
+\begin{center}
+$\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$
+\end{center}
+
+\noindent There are two problems 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 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. 
+
+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 transaction history starting with the first transaction
+made in January 2009. This history of transactions is called 
+\emph{blockchain}. Bob can use his copy of the blockchain for 
+determining whether Alice owned the Bitcoin 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. They are hashed so that the data in the
+transactions cannot be tampered with. This hash is the unique
+serial number of each block. Each block also contains a
+reference of the previous block. Since this
+previous-block-reference is also hashed, the whole chain is
+robust against tampering. We can check this by checking the
+entire blockchain whether the references and hashes are
+correctly recorded. I have not tried it myself, but it is said
+that with the current amount of data in the blockchain it
+takes roughly a day to check the consistency of the blockchain
+on a ``normal'' computer. Fortunately this consistency test
+from the beginning usually only needs to be done once.
+
+Recall I wrote earlier Bitcoins that do not maintain a ledger
+listing all the current balances in each account.
+
+\begin{center}
+\includegraphics[scale=0.4]{../pics/blockchain.png}
+\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/