--- a/handouts/ho08.tex	Thu Nov 20 14:48:11 2014 +0000
+++ b/handouts/ho08.tex	Thu Nov 20 18:11:36 2014 +0000
@@ -1,6 +1,7 @@
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../graphics}
+\usepackage{../langs}
 
 \begin{document}
 
@@ -10,26 +11,26 @@
 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. 
+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 and so on available
-about Bitcoins. Below I will follow closely the very readable
-explanations from
+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.
+\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
@@ -42,45 +43,47 @@
 \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 ever only be 21 Million
-Bitcoins with the maximum reached around the year 2140.
-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.
+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. Public-private keys are used for signatures. For
-example sending a message, say $msg$, together with the
-encrypted version
+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 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 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 email-addresses you ever wanted to
-register with, say, Googlemail, but which were always already
-taken.
+\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, say, 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 
+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}
@@ -95,19 +98,19 @@
 \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 (rough) form 
+to sending messages of the (oversimplified) form 
 
 \begin{equation}
 \{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}
 \end{equation}
 
-\noindent These are the transactions that are the only data
-that is ever stored (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}$. 
+\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
@@ -140,16 +143,18 @@
 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. 
+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 wanting to rely on a bank by
-making everybody the ``bank''. Everybody who cares can have
+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 and if yes transmits the message to every other
-participant on the Bitcoin network. The blockchain looks
+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}
@@ -164,51 +169,56 @@
 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 eliminate all possibilities of
-fraud?
+the case?\ldots{}But does it actually eliminate all
+possibilities of fraud?
 
-We can check the consistency of the blockchain by checking the
-entire block\-chain 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 (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.
+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. Therefore 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
+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 only make a transaction to
-forward the message she received. The only slight complication
-with is that incoming transactions can be combined in a
-transaction and ``outgoing'' Bitcoins can be split. For
-example in the leftmost upper transactions in
+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 it is also important to be able to split the
-money from one or more incoming transaction to 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. 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 Charles can then use to give to Emily.
+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}
@@ -222,10 +232,10 @@
 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
+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
+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
@@ -233,60 +243,138 @@
 Bitcoins) and then split this amount with 1 Bitcoin going to
 Alice and 9 Bitcoins going back to herself. 
 
-I let you have time to let this concept of transactions sink
-in\ldots{}in the words of a famous 60ies Band: ``All you need
-is transactions''. There is no need for a central ledger and
-no need for an account balance from traditional banking. The
-closest what Bitcoin has to offer for a notion of a balance in
-a bank account are the unspend transaction that a person (that
-is public-private key address) received. That means
-transactions that can still be forwarded. 
+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. 
 
-Also consider the fact that whatever transaction is recorded
-in the blockchain is what will set the ``historical record''.
-If a transaction says 1 Bitcoin from address $A$ to address
-$B$, then this is what will be recorded. This is also how
-Bitcoins can actually get lost: if you forget your private key
-and you had just a message forwarded to you address of the
-public key, then 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. An attacker might get hold of
-your private key and then quickly forward the Bitcoins in your
-name to an address the attacker controls. You have never again
+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 spend. And remember with Bitcoins you cannot
+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 rollback the transaction.
+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 to
-Charlie, or even herself. If Bob is also in the coffee
-business, he would potentially be cheated out of his money.
-The problem is how should people update their blockchain?
-You might end up with a picture like this
+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.3]{../pics/bitcoindisagreement.png}
+\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. But what means enough in a distributed 
-system? If Alice sets up network of a billion puppy identidies
-and whenever Bob tries to ask whether Alice is the rightful 
-owner of the Bitcoin and Alice just send a transaction to him,
-the puppy network of identities just says yes. Bob would then 
-give the coffee to Alice, but then for everybody else the
+\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}