handouts/ho08.tex
changeset 318 f376d16470e0
child 319 e6afcdabd3ea
equal deleted inserted replaced
317:0cdfa8ef4aa2 318:f376d16470e0
       
     1 \documentclass{article}
       
     2 \usepackage{../style}
       
     3 \usepackage{../graphics}
       
     4 
       
     5 \begin{document}
       
     6 
       
     7 \section*{Handout 7 (Bitcoins)}
       
     8 
       
     9 In my opinion Bitcoins are a Ponzi
       
    10 scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still
       
    11 the ideas behind them are really beautiful and not too
       
    12 difficult to understand. Since many colourful claims about
       
    13 Bitcoins float around in the mainstream media, it will be
       
    14 instructive to re-examine such claims from a more technically
       
    15 informed vantage point. For example, it is often claimed that
       
    16 Bitcoins are anonymous and free from any potential government
       
    17 meddling. It turns out that the first claim ignores a lot of
       
    18 research in de-anonymising social networks, and the second
       
    19 underestimates the persuasive means a government has at their
       
    20 disposal. Below I will follow the very readable explanations
       
    21 about Bitcoins from
       
    22 
       
    23 \begin{center}
       
    24 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/}\smallskip\\
       
    25 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}
       
    26 \end{center}
       
    27 
       
    28 
       
    29 Let us start with the question who invented Bitcoins? You
       
    30 could not make up the answer, but we actually do not know who
       
    31 is the inventor. All we know is that the first paper
       
    32 
       
    33 \begin{center}
       
    34 \url{https://bitcoin.org/bitcoin.pdf}
       
    35 \end{center}
       
    36 
       
    37 \noindent is signed by Satoshi Nakamoto, which however is
       
    38 likely only a pen name. There is a lot of speculation who
       
    39 could be the inventor, or inventors, but we simply do not
       
    40 know. This part of Bitcoins is definitely anonymous. The first
       
    41 Bitcoin transaction was made in January 2009. The rules in
       
    42 Bitcoin are set up so that there will only be 21 Million
       
    43 Bitcoins with the maximum reached around year 2140. Contrast
       
    44 this with other fiat currencies where money can be printed
       
    45 almost at will. The smallest unit of a Bitcoin is called a
       
    46 Satoshi which is the $10^{-8}$ part of a Bitcoin. Remember a
       
    47 Penny is the $10^{-2}$ part of a Pound.
       
    48 
       
    49 The two main cryptographic building blocks of Bitcoins are
       
    50 cryptographic hashing (SHA-256) and public-private keys using 
       
    51 elliptic-curve encryption for digital signatures. Hashes are 
       
    52 used to generate `fingerprints' of data that ensures its
       
    53 integrity. Public-private keys are used for signatures. For 
       
    54 example sending a message, say $msg$, together with the 
       
    55 encrypted version
       
    56 
       
    57 \[
       
    58 msg, \{msg\}_{K^{priv}}
       
    59 \]
       
    60 
       
    61 \noindent allows everybody with access to the public key to
       
    62 verify the message came from the person who knew the private
       
    63 key. Signatures are used in Bitcoins for verifying the
       
    64 addresses where the Bitcoins come from. Addresses in Bitcoins
       
    65 are essentially the public keys. There are $2^{160}$ possible
       
    66 addresses, which is such a vast amount that there is not test
       
    67 for duplicates\ldots{}or already used addresses.
       
    68 
       
    69 Traditional banking involves a central ledger which specifies
       
    70 the current balance in each account, for example 
       
    71 
       
    72 \begin{center}
       
    73 \begin{tabular}{l|r}
       
    74 account & balance\\\hline
       
    75 Alice   & \pounds{10.01}\\
       
    76 Bob     & \pounds{4.99}\\
       
    77 Charlie & -\pounds{1.23}\\
       
    78 Eve     & \pounds{0.00}
       
    79 \end{tabular}
       
    80 \end{center}
       
    81 
       
    82 \noindent Bitcoins work differently in that there is no
       
    83 central ledger, but a public record of all transactions. This
       
    84 means spending money corresponds to sending messages of
       
    85 the very rough form 
       
    86 
       
    87 \begin{center}
       
    88 $\{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}$
       
    89 \end{center}
       
    90 
       
    91 \noindent They are encrypted with Alice's private key such
       
    92 that everybody, including Bob, can use Alice's public key
       
    93 $K^{pub}_{ALice}$ in order to verify the message came really
       
    94 from Alice, or more precisely from the person who knows
       
    95 $K^{priv}_{Alice}$. The problem with such messages in a
       
    96 distributed system is what happens if Bob receives 10, say, of
       
    97 these messages. Did Alice intend to send him 10 Bitcoins, or
       
    98 did the message by Alice get duplicated by for example an
       
    99 attacker re-playing a sniffed message. What is needed is
       
   100 a kind of serial number for such messages. Meaning transaction 
       
   101 messages look more like 
       
   102 
       
   103 \begin{center}
       
   104 $\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$
       
   105 \end{center}
       
   106 
       
   107 \noindent There are two problems that need to be solved. One is
       
   108 who is assigning serial numbers to bitcoins and also how can
       
   109 Bob verify that Alice actually owns this Bitcoin to pay
       
   110 him? In a system with a bank as trusted third-party, Bob
       
   111 could do the following:
       
   112 
       
   113 \begin{itemize}
       
   114 \item Bob asks the bank whether the Bitcoin with that serial
       
   115       number belongs to Alice and Alice hasn’t already spent
       
   116       this Bitcoin.
       
   117 \item If yes, then Bob tells the bank he accepts this Bitcoin.
       
   118       The bank updates the records to show that the Bitcoin
       
   119       with that serial number is now in Bob’s possession and
       
   120       no longer belongs to Alice. 
       
   121 \end{itemize}
       
   122 
       
   123 \noindent But banks would need to be trusted and would also be
       
   124 an easy target for any government interference, for example.
       
   125 Think of the early days of music sharing where the company
       
   126 Napster was the single point of ``failure'' which was taken
       
   127 offline by law enforcement. 
       
   128 
       
   129 Bitcoin solves the problem of not being able to rely on a bank
       
   130 by making everybody the bank. Everybody who cares can have the
       
   131 entire transaction history starting with the first transaction
       
   132 made in January 2009. This history of transactions is called 
       
   133 \emph{blockchain}. Bob can use his copy of the blockchain for 
       
   134 determining whether Alice owned the Bitcoin and if yes 
       
   135 transmits the message to every other participant on the 
       
   136 Bitcoin network. The blockchain looks roughly like a very long 
       
   137 chain of individual blocks
       
   138 
       
   139 \begin{center}
       
   140 \includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png}
       
   141 \end{center}
       
   142 
       
   143 \noindent Each block contains a list of individual
       
   144 transactions. They are hashed so that the data in the
       
   145 transactions cannot be tampered with. This hash is the unique
       
   146 serial number of each block. Each block also contains a
       
   147 reference of the previous block. Since this
       
   148 previous-block-reference is also hashed, the whole chain is
       
   149 robust against tampering. We can check this by checking the
       
   150 entire blockchain whether the references and hashes are
       
   151 correctly recorded. I have not tried it myself, but it is said
       
   152 that with the current amount of data in the blockchain it
       
   153 takes roughly a day to check the consistency of the blockchain
       
   154 on a ``normal'' computer. Fortunately this consistency test
       
   155 from the beginning usually only needs to be done once.
       
   156 
       
   157 Recall I wrote earlier Bitcoins that do not maintain a ledger
       
   158 listing all the current balances in each account.
       
   159 
       
   160 \begin{center}
       
   161 \includegraphics[scale=0.4]{../pics/blockchain.png}
       
   162 \end{center}
       
   163 
       
   164 \end{document}
       
   165 
       
   166 bit coin
       
   167 https://bitcoin.org/bitcoin.pdf
       
   168 https://bitcoin.org/bitcoin.pdf
       
   169 
       
   170 A fistful of bitcoins
       
   171 http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
       
   172 http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
       
   173 
       
   174 Ross Anderson & Co (no dispute resolution; co-ercion)
       
   175 http://www.cl.cam.ac.uk/~sjm217/papers/fc14evidence.pdf
       
   176 
       
   177 http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/
       
   178 http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html
       
   179 
       
   180 http://randomwalker.info/bitcoin/