handouts/ho08.tex
changeset 323 0629590fd299
parent 322 8c07340af3b9
child 336 3cb200fa6d6a
equal deleted inserted replaced
322:8c07340af3b9 323:0629590fd299
    28 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\
    28 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\
    29 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}
    29 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}
    30 \end{center}
    30 \end{center}
    31 
    31 
    32 \noindent The latter also contains a link to a nice youtube
    32 \noindent The latter also contains a link to a nice youtube
    33 video about the technical details behind Bitcoins.
    33 video about the technical details behind Bitcoins. I will
       
    34 also use some of their pictures.
    34 
    35 
    35 Let us start with the question who invented Bitcoins? You
    36 Let us start with the question who invented Bitcoins? You
    36 could not make up the answer, but we actually do not know who
    37 could not make up the answer, but we actually do not know who
    37 the inventor is. All we know is that the first paper
    38 the inventor is. All we know is that the first paper
    38 
    39 
    65 \[
    66 \[
    66 msg, \{msg\}_{K^{priv}}
    67 msg, \{msg\}_{K^{priv}}
    67 \]
    68 \]
    68 
    69 
    69 \noindent allows everybody with access to the corresponding
    70 \noindent allows everybody with access to the corresponding
    70 public key $K^{pub}$ to verify the message came from the
    71 public key $K^{pub}$ to verify that the message came from the
    71 person who knew the private key. Signatures are used in
    72 person who knew the private key. Signatures are used in
    72 Bitcoins for verifying the addresses where the Bitcoins are
    73 Bitcoins for verifying the addresses where the Bitcoins are
    73 sent from. Addresses in Bitcoins are essentially the public
    74 sent from. Addresses in Bitcoins are essentially the public
    74 keys. There are $2^{160}$ possible addresses, which is such a
    75 keys. There are $2^{160}$ possible addresses, which is such a
    75 vast amount that there is not even a check for duplicates, or
    76 vast amount that there is not even a check for duplicates, or
    76 already used addresses. If you start with a random number to
    77 already used addresses. If you start with a random number to
    77 generate a public-private key pair it is very unlikely that
    78 generate a public-private key pair it is very unlikely that
    78 you step on somebody else's shoes. Compare this with the
    79 you step on somebody else's shoes. Compare this with the
    79 email-addresses you always wanted to register with, say
    80 email-addresses you always wanted to register with, say
    80 Googlemail, but which are already taken.
    81 Gmail, but which are already taken.
    81 
    82 
    82 One main difference between Bitcoins and traditional banking
    83 One major difference between Bitcoins and traditional banking
    83 is that you do not have a place, or places, that record the
    84 is that you do not have a place, or places, that record the
    84 balance on your account. Traditional banking involves a
    85 balance on your account. Traditional banking involves a
    85 central ledger which specifies the current balance in each
    86 central ledger which specifies the current balance in each
    86 account, for example 
    87 account, for example 
    87 
    88 
   106 
   107 
   107 \noindent These messages, called transactions, are the only
   108 \noindent These messages, called transactions, are the only
   108 data that is ever stored in the Bitcoin system (we will come
   109 data that is ever stored in the Bitcoin system (we will come
   109 to the precise details later on). The transactions are
   110 to the precise details later on). The transactions are
   110 encrypted with Alice's private key so that everybody,
   111 encrypted with Alice's private key so that everybody,
   111 including Bob, can use Alice's public key $K^{pub}_{Alice}$
   112 including Bob, can use Alice's public key $K^{pub}_{Alice}$ to
   112 for verifying that this message came really from Alice, or
   113 verify that this message came really from Alice, or more
   113 more precisely from the person who knows $K^{priv}_{Alice}$. 
   114 precisely from the person who knows $K^{priv}_{Alice}$. 
   114 
   115 
   115 The problem with such messages in a distributed system is that
   116 The problem with such messages in a distributed system is that
   116 what happens if Bob receives 10, say, of these transactions.
   117 what happens if Bob receives 10, say, of these transactions?
   117 Did Alice intend to send him 10 Bitcoins, or did the message
   118 Did Alice intend to send him 10 Bitcoins, or did the message
   118 get duplicated by for example an attacker re-playing a sniffed
   119 get duplicated by for example an attacker re-playing a sniffed
   119 message? What is needed is a kind of serial number for such
   120 message? What is needed is a kind of serial number for such
   120 transactions. This means transaction messages look more like 
   121 transactions. This means transaction messages look more like 
   121 
   122 
   141 
   142 
   142 \noindent But for this banks would need to be trusted and
   143 \noindent But for this banks would need to be trusted and
   143 would also be an easy target for any government interference,
   144 would also be an easy target for any government interference,
   144 for example. Think of the early days of music sharing where
   145 for example. Think of the early days of music sharing where
   145 the company Napster was the single point of ``failure'' which
   146 the company Napster was the single point of ``failure'' which
   146 was taken offline by law enforcement. Bitcoins is more a
   147 was taken offline by law enforcement. Bitcoins is more like a
   147 system like BitTorrent without a single central entity that
   148 system such as BitTorrent without a single central entity that
   148 can be taken offline.
   149 can be taken offline.\footnote{There is some Bitcoin
       
   150 infrastructure that is not so immune from being taken offline:
       
   151 for example Bitcoin exchanges, HQs of Bitcoin mining pools,
       
   152 Bitcoin developers and so on.}
   149 
   153 
   150 Bitcoin solves the problem of not being able to rely on a bank
   154 Bitcoin solves the problem of not being able to rely on a bank
   151 by making everybody the ``bank''. Everybody who cares can have
   155 by making everybody the ``bank''. Everybody who cares can have
   152 the entire transactions history starting with the first
   156 the entire transactions history starting with the first
   153 transaction made in January 2009. This history of transactions
   157 transaction made in January 2009. This history of transactions
   154 is called \emph{blockchain}. Bob, for example, can use his
   158 is called the \emph{blockchain}. Bob, for example, can use his
   155 copy of the blockchain for determining whether Alice owned the
   159 copy of the blockchain for determining whether Alice owned the
   156 Bitcoin he received, and if she did, he transmits the message
   160 Bitcoin he received, and if she did, he transmits the message
   157 that he owns it now to every other participant on the Bitcoin
   161 that he owns it now to every other participant on the Bitcoin
   158 network. An illustration of a three-block segment of the
   162 network. An illustration of a three-block segment of the
   159 blockchain is (simplified) as follows
   163 blockchain is (simplified) as follows
   166 \noindent The chain grows with time. Each block contains a
   170 \noindent The chain grows with time. Each block contains a
   167 list of individual transactions, written txn in the picture
   171 list of individual transactions, written txn in the picture
   168 above, and also a reference to the previous block, written
   172 above, and also a reference to the previous block, written
   169 prev. The data in a block (txn's and prev) is hashed so that
   173 prev. The data in a block (txn's and prev) is hashed so that
   170 the reference and transactions in them cannot be tampered
   174 the reference and transactions in them cannot be tampered
   171 with. This hash is the unique serial number of each block.
   175 with. This hash is also the unique serial number of each
   172 Since this previous-block-reference is also part of the hash,
   176 block. Since this previous-block-reference is also part of the
   173 the whole chain is robust against tampering. I let you think
   177 hash, the whole chain is robust against tampering. I let you
   174 why this is the case?\ldots{}But does it actually eliminate
   178 think why this is the case?\ldots{}But does it actually
   175 all possibilities of fraud?
   179 eliminate all possibilities of fraud?
   176 
   180 
   177 We can check the consistency of the blockchain by checking
   181 We can check the consistency of the blockchain by checking
   178 whether all the references and hashes are correctly recorded.
   182 whether all the references and hashes are correctly recorded.
   179 I have not tried it myself, but it is said that with the
   183 I have not tried it myself, but it is said that with the
   180 current amount of data (appr.~12GB) it takes roughly a day to
   184 current amount of data (appr.~12GB) it takes roughly a day to
   208 payment (or transaction) combines the Bitcoins that were send
   212 payment (or transaction) combines the Bitcoins that were send
   209 by Jane to Fred and also by Juan to Fred. This allows you to
   213 by Jane to Fred and also by Juan to Fred. This allows you to
   210 ``consolidate'' your funds: if it were only possible to split
   214 ``consolidate'' your funds: if it were only possible to split
   211 transactions, then the amounts would get smaller and smaller. 
   215 transactions, then the amounts would get smaller and smaller. 
   212 
   216 
   213 But in Bitcoins it is also important to have the ability to
   217 In Bitcoins you have the ability to both combine incoming
   214 split the money from one or more incoming transaction to
   218 transactions, but also to split outgoing transactions to
   215 potentially more than one receiver. Consider again the
   219 potentially more than one receiver. The latter is needed.
   216 rightmost transactions in Figure~\ref{txngraph} and suppose
   220 Consider again the rightmost transactions in
   217 Alice is a coffeeshop owner selling coffees for 1 Bitcoin.
   221 Figure~\ref{txngraph} and suppose Alice is a coffeeshop owner
   218 Charles received a transaction from Zack over 5 Bitcoins, say.
   222 selling coffees for 1 Bitcoin. Charles received a transaction
   219 How does he pay for the coffee? There is no explicit notion of
   223 from Zack over 5 Bitcoins, say. How does he pay for the
   220 \emph{change} in the Bitcoin system. What Charles has to do
   224 coffee? There is no explicit notion of \emph{change} in the
   221 instead is to make one single transaction with 1 Bitcoin to
   225 Bitcoin system. What Charles has to do instead is to make one
   222 Alice and with 4 Bitcoins going back to himself, which then
   226 single transaction with 1 Bitcoin to Alice and with 4 Bitcoins
   223 Charles can use to give to Emily, for example.
   227 going back to himself, which then Charles can use to give to
       
   228 Emily, for example.
   224 
   229 
   225 \begin{figure}[t]
   230 \begin{figure}[t]
   226 \begin{center}
   231 \begin{center}
   227 \includegraphics[scale=0.4]{../pics/blockchain.png}
   232 \includegraphics[scale=0.4]{../pics/blockchain.png}
   228 \end{center}
   233 \end{center}
   235 transaction (not shown in the picture) that sends 6 Bitcoins
   240 transaction (not shown in the picture) that sends 6 Bitcoins
   236 to her. If she now wants to buy a coffee from Alice for 1
   241 to her. If she now wants to buy a coffee from Alice for 1
   237 Bitcoin, she has two possibilities: She could just forward the
   242 Bitcoin, she has two possibilities: She could just forward the
   238 transaction from Charles over 4 Bitcoins to Alice split in
   243 transaction from Charles over 4 Bitcoins to Alice split in
   239 such a way that Alice receives 1 Bitcoin and Emily sends the
   244 such a way that Alice receives 1 Bitcoin and Emily sends the
   240 remaining 3 Bitcoins ``back'' to herself. In this case she
   245 remaining 3 Bitcoins back to herself. In this case she would
   241 would now be in the ``possession'' of two unspend Bitcoin
   246 now be in the possession of two unspend Bitcoin transactions,
   242 transactions, one over 3 Bitcoins and the independent one over
   247 one over 3 Bitcoins and the independent one over 6 Bitcoins.
   243 6 Bitcoins. Or, Emily could combine both transactions (one
   248 Or, Emily could combine both transactions (one over 4 Bitcoins
   244 over 4 Bitcoins from Charles and the independent one over 6
   249 from Charles and the independent one over 6 Bitcoins) and then
   245 Bitcoins) and then split this amount with 1 Bitcoin going to
   250 split this amount with 1 Bitcoin going to Alice and 9 Bitcoins
   246 Alice and 9 Bitcoins going back to herself. 
   251 going back to herself. 
   247 
   252 
   248 I think this is a good time for you to pause to let this
   253 I think this is a good time for you to pause to let this
   249 concept of transactions really sink in\ldots{}You should see
   254 concept of transactions to really sink in\ldots{}You should
   250 that there is really no need for a central ledger and no need
   255 see that there is really no need for a central ledger and no
   251 for an account balance as familiar from traditional banking.
   256 need for an account balance as familiar from traditional
   252 The closest what Bitcoin has to offer for the notion of a
   257 banking. The closest what Bitcoin has to offer for the notion
   253 balance in a bank account are the unspend transactions that a
   258 of a balance in a bank account are the unspend transactions
   254 person (more precisely a public-private key address) received.
   259 that a person (more precisely a public-private key address)
   255 That means transactions that can still be forwarded. 
   260 received. That means transactions that can still be forwarded. 
   256 
   261 
   257 After the pause also consider the fact that whatever
   262 After the pause also consider the fact that whatever
   258 transaction is recorded in the blockchain will be in the
   263 transaction is recorded in the blockchain will be in the
   259 ``historical record'' for the Bitcoin system. If a transaction
   264 ``historical record'' for the Bitcoin system. If a transaction
   260 says 1 Bitcoin goes from address $A$ to address $B$, then this
   265 says 1 Bitcoin goes from address $A$ to address $B$, then this
   275 not be able to form a valid message that sends this to
   280 not be able to form a valid message that sends this to
   276 somebody else (we will see the details of this later). But
   281 somebody else (we will see the details of this later). But
   277 this is also a way how you can get robbed of your Bitcoins. By
   282 this is also a way how you can get robbed of your Bitcoins. By
   278 old-fashioned hacking-into-a-computer crime, for example, an
   283 old-fashioned hacking-into-a-computer crime, for example, an
   279 attacker might get hold of your private key and then quickly
   284 attacker might get hold of your private key and then quickly
   280 forward the Bitcoins that are in your name to an address the
   285 forwards the Bitcoins that are in your name to an address the
   281 attacker controls. You will never again have access to these
   286 attacker controls. You will never again have access to these
   282 Bitcoins, because for the Bitcoin system they are assumed to
   287 Bitcoins, because for the Bitcoin system they are assumed to
   283 be spent. And remember with Bitcoins you cannot appeal to any
   288 be spent. And remember with Bitcoins you cannot appeal to any
   284 higher authority. Once the Bitcoins are gone, they are gone.
   289 higher authority. Once the Bitcoins are gone, they are gone.
   285 This is much different in traditional banking where at least
   290 This is much different in traditional banking where at least
   310 What does, however, ``enough'' mean in a distributed system?
   315 What does, however, ``enough'' mean in a distributed system?
   311 If Alice sets up a network of a billion, say, puppy identities
   316 If Alice sets up a network of a billion, say, puppy identities
   312 and whenever Bob tries to convince, or validate, that he is
   317 and whenever Bob tries to convince, or validate, that he is
   313 the rightful owner of the Bitcoin, then the puppy identities
   318 the rightful owner of the Bitcoin, then the puppy identities
   314 agree. Bob would then have no reason to not give Alice her
   319 agree. Bob would then have no reason to not give Alice her
   315 coffee. But behind his back, however, she has convinced
   320 coffee. But behind his back she has convinced everybody else
   316 everybody else on the network that she is still the rightful
   321 on the network that she is still the rightful owner of the
   317 owner of the Bitcoin. After being outvoted, Bob would be a tad
   322 Bitcoin. After being outvoted, Bob would be a tad peeved. 
   318 peeved. 
       
   319 
   323 
   320 The reflex reaction to such a situation would be to make the
   324 The reflex reaction to such a situation would be to make the
   321 process of validating a transaction as cheap as possible. The
   325 process of validating a transaction as cheap as possible. The
   322 intention is that Bob will get enough peers to agree with him
   326 intention is that Bob will get enough peers to agree with him
   323 that he is the rightful owner. But such a solution has always
   327 that he is the rightful owner. But such a solution has always
   330 Bitcoins work so beautifully.
   334 Bitcoins work so beautifully.
   331 
   335 
   332 \subsubsection*{Proof-of-Work Puzzles}
   336 \subsubsection*{Proof-of-Work Puzzles}
   333 
   337 
   334 In order to make the process of transaction validation
   338 In order to make the process of transaction validation
   335 difficult, Bitcoin uses a kind of puzzles. Solving the puzzles
   339 difficult, Bitcoin uses a kind of puzzle. Solving the puzzles
   336 is called \emph{Bitcoin mining}, where whoever solves a puzzle
   340 is called \emph{Bitcoin mining}, where whoever solves a puzzle
   337 will be awarded some Bitcoins. At the beginning this was 50
   341 will be awarded some Bitcoins. At the beginning this was 50
   338 Bitcoins, but the rules of Bitcoin are set up such that this
   342 Bitcoins, but the rules of Bitcoin are set up such that this
   339 amount halves every 210,000 transactions or so. Currently you
   343 amount halves every 210,000 transactions or so. Currently you
   340 will be awarded 25 Bitcoins for solving a puzzle. Because the
   344 will be awarded 25 Bitcoins for solving a puzzle. Because the
   382 point is that we can very quickly check whether a salt solves
   386 point is that we can very quickly check whether a salt solves
   383 a puzzle, but it is hard to find one. Latest research suggest
   387 a puzzle, but it is hard to find one. Latest research suggest
   384 it is an NP-problem. If we want the output hash value to begin
   388 it is an NP-problem. If we want the output hash value to begin
   385 with 10 zeroes, say, then we will, on average, need to try
   389 with 10 zeroes, say, then we will, on average, need to try
   386 $16^{10} \approx 10^{12}$ different salts before we find a
   390 $16^{10} \approx 10^{12}$ different salts before we find a
   387 suitable one. In Bitcoins the puzzles are not solved according
   391 suitable one. 
   388 to how many leading zeros a has-value has, but rather whether
   392 
   389 it is below a \emph{target}. The hardness of the puzzle can
   393 In Bitcoins the puzzles are not solved according to how many
   390 actually be controlled by changing the target according to the
   394 leading zeros a hash-value has, but rather whether it is below
   391 available computational power available. I think the
   395 a \emph{target}. The hardness of the puzzle can actually be
   392 adjustment of the hardness of the problems is done every two
   396 controlled by changing the target according to the available
   393 weeks. I am not sure whether this is an automatic process. The
   397 computational power available. I think the adjustment of the
   394 aim of the adjustment is that on average the Bitcoin network
   398 hardness of the problems is done every 2060 blocks
   395 will most likely solve a puzzle within 10 Minutes. 
   399 (appr.~every two weeks). I am not sure whether this is an
       
   400 automatic process. The aim of the adjustment is that on
       
   401 average the Bitcoin network will most likely solve a puzzle
       
   402 within 10 Minutes. 
   396 
   403 
   397 \begin{center}
   404 \begin{center}
   398 \includegraphics[scale=0.37]{../pics/blockchainsolving.png}
   405 \includegraphics[scale=0.37]{../pics/blockchainsolving.png}
   399 \end{center}
   406 \end{center}
   400 
   407 
   402 take longer, but on average after 10 Minutes somebody on the 
   409 take longer, but on average after 10 Minutes somebody on the 
   403 network will have found a solution. 
   410 network will have found a solution. 
   404 
   411 
   405 Remember that the puzzles are a kind of proof-of-work that
   412 Remember that the puzzles are a kind of proof-of-work that
   406 make the validation of transactions artificially expensive.
   413 make the validation of transactions artificially expensive.
   407 The validation and the derivation of the puzzle is done as 
   414 Consider the following picture with a blockchain and some
   408 follows:
   415 unconfirmed transactions. 
   409 
   416 
   410 \begin{equation}
   417 \begin{equation}
   411 \includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}
   418 \includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}
   412 \label{unconfirmed}
   419 \label{unconfirmed}
   413 \end{equation}
   420 \end{equation}
   414 
   421 
   415 \noindent There are some unconfirmed transactions. Choosing
   422 \noindent The puzzle is given as follows: There are some
   416 some of them, the miner (i.e.~the person/computer that tries
   423 unconfirmed transactions. Choosing some of them, the miner
   417 to solve a puzzle) will form a putative block to be added to
   424 (i.e.~the person/computer that tries to solve a puzzle) will
   418 the blockchain. This putative block will contain the
   425 form a putative block to be added to the blockchain. This
   419 transactions and the reference to the previous block. The
   426 putative block will contain the transactions and the reference
   420 serial number of such a block is simply the hash of all the
   427 to the previous block. The serial number of such a block is
   421 data. The puzzle can then be stated as the ``string''
   428 simply the hash of all the data. The puzzle can then be stated
   422 corresponding to the block and which salt is needed in order
   429 as the ``string'' corresponding to the block and which salt is
   423 to have the hashed value being below the target. Other miners
   430 needed in order to have the hashed value being below the
   424 will choose different transactions and therefore work on a 
   431 target. Other miners will choose different transactions and
   425 slightly different putative block and puzzle.
   432 therefore work on a slightly different putative block and
       
   433 puzzle.
   426 
   434 
   427 The intention of the proof-of-work puzzle is that the
   435 The intention of the proof-of-work puzzle is that the
   428 blockchain is at every given moment nicely linearly ordered,
   436 blockchain is at every given moment linearly ordered, see the
   429 see the picture shown in \eqref{unconfirmed}. If we don’t have
   437 picture shown in \eqref{unconfirmed}. If we don’t have such a
   430 such a linear ordering at any given moment then it may not be
   438 linear ordering at any given moment then it may not be clear
   431 clear who owns which Bitcoins. Assume a miner David is lucky
   439 who owns which Bitcoins. Assume a miner David is lucky and
   432 and finds a suitable salt to confirm the transactions. Should
   440 finds a suitable salt to confirm the transactions. Should he
   433 he celebrate? Not yet. Typically the blockchain will look as
   441 celebrate? Not yet. Typically the blockchain will look as
   434 follows
   442 follows
   435 
   443 
   436 \begin{center}
   444 \begin{center}
   437 \includegraphics[scale=0.65]{../pics/block_chain1.png}
   445 \includegraphics[scale=0.65]{../pics/block_chain1.png}
   438 \end{center}
   446 \end{center}
   441 
   449 
   442 \begin{center}
   450 \begin{center}
   443 \includegraphics[scale=0.65]{../pics/block_chain_fork.png}
   451 \includegraphics[scale=0.65]{../pics/block_chain_fork.png}
   444 \end{center}
   452 \end{center}
   445 
   453 
   446 \noindent What should be done in this case? The tie is broken
   454 \noindent What should be done in this case? Well, the tie is
   447 if another block is solved, like so:
   455 broken if another block is solved, like so:
   448 
   456 
   449 \begin{center}
   457 \begin{center}
   450 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_branches.png}
   458 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_branches.png}
   451 \end{center}
   459 \end{center}
   452 
   460 
   453 \noindent The rule in Bitcoins is: If a fork occurs, people on
   461 \noindent The rule in Bitcoins is: If a fork occurs, people on
   454 the network keep track of all forks. But at any given time,
   462 the network keep track of all forks (they can see). But at any
   455 miners only work to extend whichever fork is longest in their
   463 given time, miners only work to extend whichever fork is
   456 copy of the block chain. Why should miners work on the longest
   464 longest in their copy of the block chain. Why should miners
   457 fork? Well their incentive is to mine Bitcoins. If somebody
   465 work on the longest fork? Well their incentive is to mine
   458 else already solved a puzzle, then it makes more sense to work
   466 Bitcoins. If somebody else already solved a puzzle, then it
   459 on a new puzzle and obtain the Bitcoins for solving that
   467 makes more sense to work on a new puzzle and obtain the
   460 puzzle. Note that whoever solved a puzzle on the ``loosing''
   468 Bitcoins for solving that puzzle, rather than wast efforts on
   461 fork will actually not get any Bitcoins as reward. Tough luck.
   469 a fork that is shorter and therefore less likely to be
       
   470 ``accepted''. Note that whoever solved a puzzle on the
       
   471 ``loosing'' fork will actually not get any Bitcoins as reward.
       
   472 Tough luck.
       
   473 
   462 
   474 
   463 \subsubsection*{Alice against the Rest of the World}
   475 \subsubsection*{Alice against the Rest of the World}
   464 
   476 
   465 Let is see how the blockchain and the proof-of-work puzzles
   477 Let us see how the blockchain and the proof-of-work puzzles
   466 avoid the problem of double spend. If Alice wants to cheat
   478 avoid the problem of double spend. If Alice wants to cheat
   467 Bob she would need to pull off the following ploy:
   479 Bob, she would need to pull off the following ploy:
   468 
   480 
   469 \begin{center}
   481 \begin{center}
   470 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_double_spend.png}
   482 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_double_spend.png}
   471 \end{center}
   483 \end{center}
   472 
   484 
   473 \noindent Alice makes a transaction to Bob for paying, for
   485 \noindent Alice makes a transaction to Bob for paying, for
   474 example, for an online order. This transaction is confirmed,
   486 example, for an online order. This transaction is confirmed,
   475 or validated, in block 2. Bob ships the goods around block 4.
   487 or validated, in block 2. Bob ships the goods around block 4.
   476 In this moment, Alice needs to get into action and try to
   488 In this moment, Alice needs to get into action and try to
   477 validate the fraudulent transaction to herself instead. 
   489 validate the fraudulent transaction to herself instead. At
       
   490 this moment she is in a race against all the computing power
       
   491 of the ``rest of the world''. Because the incentive of the
       
   492 rest of the world is to work on the longest chain, that is the
       
   493 one with the transaction from Alice to Bob:
   478 
   494 
   479 \begin{center}
   495 \begin{center}
   480 \includegraphics[scale=0.4]{../pics/bitcoin_doublespend_blockchain_race.png}
   496 \includegraphics[scale=0.4]{../pics/bitcoin_doublespend_blockchain_race.png}
   481 \end{center}
   497 \end{center}
   482 
   498 
   483 \noindent At this moment she is in a race against all the
   499 \noindent As shown in the picture she has to solve the puzzles
   484 computing power of the ``rest of the world''. She has to solve
   500 2a to 5a one after the other, because the hash of a block is
   485 the puzzles one by one, because the hash of a block is
   501 determined via the reference by all the data in the previous
   486 determined by all the data in the previous has. She might be
   502 block. She might be very lucky to solve one puzzle for a block
   487 very lucky to solve one puzzle for a block before the rest of
   503 before the rest of the world, but to be lucky many times is
   488 the world, but to be lucky many times is very unlikely. In
   504 very unlikely. This principle of having to race against the
   489 order to raise the bar for Alice, merchants accepting Bitcoin
   505 rest of the world avoids the ploy of double spend.
   490 use the following rule of thumb: A transaction is
   506 
   491 ``confirmed'' if (1) it is part of a block in the longest
   507 In order to raise the bar for Alice even further, merchants
   492 fork, and (2) at least 5 blocks follow it in the longest fork.
   508 accepting Bitcoin use the following rule of thumb: A
   493 In this case we say that the transaction has ``6
   509 transaction is ``confirmed'' if 
   494 confirmations''. A simple calculation shows that these number
   510 
   495 of confirmations can take up to 1 hour and more. While this
   511 \begin{itemize}
   496 seems excessively long, from the merchant's point of view it
   512 \item[(1)] it is part of a block in the longest fork, and 
   497 is not long at all. For this recall that ordinary credit cards
   513 \item[(2)] at least 5 blocks follow it in the longest fork. In
       
   514            this case we say that the transaction has ``6
       
   515            confirmations''. 
       
   516 \end{itemize} 
       
   517 
       
   518 \noindent A simple calculation shows that this amount of
       
   519 confirmations can take up to 1 hour and more. While this seems
       
   520 excessively long, from the merchant's point of view it is not
       
   521 that long at all. For this recall that ordinary creditcards
   498 can have their transactions been rolled-back for 6 months or
   522 can have their transactions been rolled-back for 6 months or
   499 so. The point however is that the odds for Alice being able to
   523 so. The point however is that the odds for Alice being able to
   500 cheat are very low.
   524 cheat are very low, unless she can muster more than 50\% of
       
   525 the world Bitcoin mining capacity.
   501 
   526 
   502 Connected with the 6-confirmation rule is an interesting
   527 Connected with the 6-confirmation rule is an interesting
   503 phenomenon. On average, it would take several years for a
   528 phenomenon. On average, it would take several years for a
   504 typical computer to solve a proof-of-work puzzle, so an
   529 typical computer to solve a proof-of-work puzzle, so an
   505 individual’s chance of ever solving one before the rest of the
   530 individual’s chance of ever solving one before the rest of the
   506 world, which typically takes 10 minutes, is negligibly low.
   531 world, which typically takes only 10 minutes, is negligibly
   507 Therefore many people join groups called \emph{mining pools}
   532 low. Therefore many people join groups called \emph{mining
   508 that collectively work to solve blocks, and distribute rewards
   533 pools} that collectively work to solve blocks, and distribute
   509 based on work contributed. These mining pools act somewhat
   534 rewards based on work contributed. These mining pools act
   510 like lottery pools among co-workers, except that some of these
   535 somewhat like lottery pools among co-workers, except that some
   511 pools are quite large, and comprise more than 20\% of all the
   536 of these pools are quite large, and comprise more than 20\% of
   512 computers in the network. It is said that BTC, the largest
   537 all the computers in the network. It is said that BTC, a large
   513 mining pool, has limited its members to not solve more than 6
   538 mining pool, has limited its members to not solve more than 6
   514 blocks in a row. Otherwise this would undermine the trust in
   539 blocks in a row. Otherwise this would undermine the trust in
   515 Bitcoins, which is also not in the interest of BTC, I guess.
   540 Bitcoins, which is also not in the interest of BTC, I guess.
       
   541 Some statistics on mining pools can be seen at
       
   542 
       
   543 \begin{center}
       
   544 \url{https://blockchain.info/pools}
       
   545 \end{center}
   516 
   546 
   517 \subsubsection*{Bitcoins for Real}
   547 \subsubsection*{Bitcoins for Real}
   518 
   548 
   519 \ldots
   549 Let us now turn to the nitty gritty details. As a user you 
       
   550 need to generate and store a public-private key pair. The 
       
   551 public key you need to advertise in order to receive payments 
       
   552 (transactions). The private key needs to be securely stored. 
       
   553 For this there seem to be three possibilities
       
   554 
       
   555 \begin{itemize}
       
   556 \item an electronic wallet on your computer
       
   557 \item a cloud-based storage (offered by some Bitcoin service)
       
   558 \item paper-based
       
   559 \end{itemize}
       
   560 
       
   561 \noindent The first two options of course offer convenience
       
   562 for making and receiving transactions. But given the nature of
       
   563 the private key and how much security relies on them (recall
       
   564 if somebody gets hold of it, your Bitcoins are quickly lost
       
   565 forever) I would opt for the third option for anything except
       
   566 for trivial amounts of Bitcoins. As we have seen securing a
       
   567 computer system that it can withstand a breakin is still very
       
   568 much an unsolved problem.
       
   569 
       
   570 An interesting fact with Bitcoin keys is that there is no
       
   571 check for duplicate addresses. This means when generating a
       
   572 public-private key, you should really start with a carefully
       
   573 chosen random number such that there is really no chance to
       
   574 step on somebody's feet in the $2^{160}$ space of
       
   575 possibilities. Again if you share an address with somebody
       
   576 else, he or she has access to all your unspend transactions.
       
   577 The absence of such a check is easily explained: How would one
       
   578 do this in a distributed system? The answer you can't. It is
       
   579 possible to do some sanity check of addresses that are already
       
   580 used in the black chain, but this is not a fail-proof method.
       
   581 One really has to trust on the enormity of the $2^{160}$
       
   582 number.
       
   583 
       
   584 Let us now look at the data that is stored in an transaction 
       
   585 message:
   520 
   586 
   521 \lstinputlisting[language=Scala]{../slides/msg}
   587 \lstinputlisting[language=Scala]{../slides/msg}
   522 
   588 
   523 \noindent
   589 \noindent The hash in Line 1 is the hash of all the data that
   524 The hash in Line 1 is the has of all the data that follows. It
   590 follows. It is a kind of serial number for the transaction.
   525 is a kind of serial number for the transaction. Line 2
   591 Line 2 contains a version number in case there are some
   526 contains a version number. Line 3 and 4 specify how many
   592 incompatible changes to be made. Lines 3 and 4 specify how
   527 incoming transactions are combined and how many outgoing
   593 many incoming transactions are combined and how many outgoing
   528 transactions there are. In our example there are 1 each. Line
   594 transactions there are. In our example there are one for each.
   529 5 specifies a lock time for when the transaction is supposed
   595 Line 5 specifies a lock time for when the transaction is
   530 to become active---this is usually set to 0 to become active
   596 supposed to become active---this is usually set to 0 to become
   531 immediately. Line 6 specifies the size of the message; it has
   597 active immediately. Line 6 specifies the size of the message;
   532 nothing to do with the Bitcoins that are transferred. Lines 7
   598 it has nothing to do with the Bitcoins that are transferred.
   533 to 11 specify where the Bitcoins in the transaction are coming
   599 Lines 7 to 11 specify where the Bitcoins in the transaction
   534 from. The has in line 9 specifies the incoming transaction and
   600 are coming from. The has in line 9 specifies the incoming
   535 the \pcode{n} in Line 10 specifies which output of the
   601 transaction and the \pcode{n} in Line 10 specifies which
   536 transaction is referred to. The signature in line 11 specifies
   602 output of the transaction is referred to. The signature in
   537 the address (public key $K^{pub}$) from where the Bitcoins are
   603 line 11 specifies the address (public key $K^{pub}$) from
   538 taken and the digital signature of the address, that is
   604 where the Bitcoins are taken and the digital signature of the
   539 $\{K^{pub}\}_{K^{priv}}$. Lines 12 to 15 specify the value of
   605 address, that is $\{K^{pub}\}_{K^{priv}}$. Lines 12 to 15
   540 the first outgoing transaction. In this case 0.319 Bitcoins.
   606 specify the value of the first outgoing transaction. In this
   541 The hash in Line 14 specifies the address to where the
   607 case 0.319 Bitcoins. The hash in Line 14 specifies the address
   542 Bitcoins are transferred.
   608 to where the Bitcoins are transferred.
   543  
   609  
   544 \ldots
   610 As can be seen there is no need to issue serial numbers for
       
   611 transactions, the hash of the transaction data can do this
       
   612 job. The hash will contain the sender addresses and
       
   613 hash-references to the incoming transactions, as well as the
       
   614 public key of the incoming transaction. This uniquely
       
   615 identifies a transaction and the hash is the unique
       
   616 fingerprint of it. The in-field also contains the address to
       
   617 which a earlier transaction is made. The digital signature
       
   618 ensures everybody can check that the person who makes this
       
   619 transaction is in the possession of the private key. Otherwise
       
   620 the signature would not match up with the public-key address.
       
   621 
       
   622 When mining the blockchain it only needs to be ensured that
       
   623 the transactions are consistent (all hashes and signatures
       
   624 match up). Then we need to generate the correct previous-block
       
   625 link and solve the resulting puzzle. Once the block is
       
   626 accepted, everybody can check the integrity of the whole
       
   627 blockchain.
       
   628 
       
   629 A word of warning: The point of a lottery is that some people
       
   630 win. But equally, that most people lose. Mining Bitcoins has
       
   631 pretty much the same point. According to the article below, a
       
   632 very large machine (very, very large in terms of June 2014)
       
   633 could potentially mine \$40 worth of Bitcoins a day, but would
       
   634 require magnitudes more of electricity costs to do so. 
       
   635 
       
   636 \begin{center}
       
   637 \url{http://bitcoinmagazine.com/13774/government-bans-professor-mining-bitcoin-supercomputer/}
       
   638 \end{center}
       
   639 
   545 
   640 
   546 \subsubsection*{Anonymity and Government Meddling}
   641 \subsubsection*{Anonymity and Government Meddling}
   547 
   642 
   548 One question one often hears is how anonymous is it actually
   643 One question one often hears is how anonymous is it actually
   549 to pay with Bitcoins? Paying with paper money in the past was
   644 to pay with Bitcoins? Paying with paper money used to be a
   550 quite an anonymous act (unlike paying with creditcards), but
   645 quite anonymous act (unlike paying with creditcards, for
   551 this has changed nowadays. You cannot come to a bank anymore
   646 example). But this has changed nowadays: You cannot come to a
   552 with a suitcase full of money and try to open a bank account.
   647 bank anymore with a suitcase full of money and try to open a
   553 Strict money laundering and taxation laws mean that not even
   648 bank account. Strict money laundering and taxation laws mean
   554 Swiss banks are prepared to take such money and open a bank
   649 that not even Swiss banks are prepared to take such money and
   555 account. With Bitcoins the situation is different, but I fully
   650 open a bank account. That is why Bitcoins are touted as 
   556 agree with the statement by Nielsen from the blog article I
   651 filling this niche again of anonymous payments. 
   557 referenced at the beginning:
   652 
       
   653 While Bitcoins are intended to be anonymous, the reality is
       
   654 slightly different. I fully agree with the statement by
       
   655 Nielsen from the blog article I referenced at the beginning:
   558 
   656 
   559 \begin{quote}\it{}``Many people claim that Bitcoin can be used
   657 \begin{quote}\it{}``Many people claim that Bitcoin can be used
   560 anonymously. This claim has led to the formation of
   658 anonymously. This claim has led to the formation of
   561 marketplaces such as Silk Road (and various successors), which
   659 marketplaces such as Silk Road (and various successors), which
   562 specialize in illegal goods. However, the claim that Bitcoin
   660 specialize in illegal goods. However, the claim that Bitcoin
   570 the great majority of Bitcoin users are not identified with
   668 the great majority of Bitcoin users are not identified with
   571 relatively high confidence and ease in the near future.''
   669 relatively high confidence and ease in the near future.''
   572 \end{quote}
   670 \end{quote}
   573 
   671 
   574 \noindent The only thing I can add is that with Bitcoins we
   672 \noindent The only thing I can add is that with Bitcoins we
   575 will have even more fun with many more confessions like the
   673 will have even more fun hearing confessions like the infamous
   576 infamous ``I did not
   674 ``I did not
   577 inhale''.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}}
   675 inhale''.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}}
   578 The whole point of the blockchain is that it public and will
   676 The whole point of the blockchain is that it public and will
   579 always be. There are some precautions that are suggested, like
   677 always be. 
   580 to use a new public-private key pair for every new transaction
   678 
   581 or access Bitcoin only through the Tor network. But the
   679 There are some precautions that are suggested, like to use a
       
   680 new public-private key pair for every new transaction, and to
       
   681 access Bitcoin only through the Tor network. But the
   582 transactions in Bitcoins are designed such that they allow one
   682 transactions in Bitcoins are designed such that they allow one
   583 to combine incoming transactions. In such cases we know they
   683 to combine incoming transactions. In such cases we know they
   584 must have been made by the single person who new the
   684 must have been made by the single person who new the
   585 corresponding private keys. So using different public-private
   685 corresponding private keys. So using different public-private
   586 keys for each transaction, might not make the de-anonymisation
   686 keys for each transaction might not actually make the
   587 task much harder. And the point about de-anonymising
   687 de-anonymisation task much harder. And the point about
   588 `anonymous' social networks is that the information is
   688 de-ano\-nymising `anonymous' social networks is that the
   589 embedded into the structure of the transition graph. And this
   689 information is embedded into the structure of the transition
   590 cannot be erased with Bitcoins.
   690 graph. And this cannot be erased with Bitcoins.
   591 
   691 
   592 Finally, what are the options for a typical western government
   692 Finally, what are the options for a typical western government
   593 to meddle with Bitcoins? This is of course one feature the
   693 to meddle with Bitcoins? This is of course one feature the
   594 proponents of Bitcoins tout: namely that there aren't any
   694 proponents of Bitcoins also tout: namely that there aren't any
   595 options. In my opinion this is too naive and far from the
   695 options. In my opinion this is far too naive and far from the
   596 truth. Let us assume some law enforcement agencies would not
   696 truth. Let us assume some law enforcement agencies would not
   597 have been able to uncover the baddies from Silk Road 2.0 (they
   697 have been able to uncover the baddies from Silk Road 1.0 and
   598 have done so by uncovering the Tor network, and incredible
   698 2.0 (they have done so by uncovering the Tor network, which is
   599 feat on its own). Would a government have stopped?
   699 an incredible feat on its own). Would a government have
       
   700 stopped? I think no. The next target would have been Bitcoin.
       
   701 If I were the government, this is what I would consider:
   600 
   702 
   601 \begin{itemize}
   703 \begin{itemize}
   602 \item The government could compel ``mayor players'' to
   704 \item The government could compel ``mayor players'' to
   603       blacklist Bitcoins (for example at exchanges). This
   705       blacklist Bitcoins (for example at Bitcoin exchanges).
   604       would impinge on what is called \emph{fungibility} of
   706       This would impinge on what is called \emph{fungibility}
   605       Bitcoins and make them much less attractive to baddies.
   707       of Bitcoins and make them much less attractive to
   606       This blacklisting can be easily done ``whole-sale'' and
   708       baddies. Suddenly their hard-earned Bitcoin money cannot
       
   709       be spent anymore.The attraction of this option is that
       
   710       this blacklisting can be easily done ``whole-sale'' and
   607       therefore be really be an attractive target for
   711       therefore be really be an attractive target for
   608       governments \& Co.      
   712       governments \& Co.      
   609 \item They could attempt to coerce developer community of the
   713 \item The government could attempt to coerce the developer
   610       Bitcoin tools. While this might be a bit harder, we know
   714       community of the Bitcoin tools. While this might be a
   611       certain governments are ready to take such actions (we
   715       bit harder, we know certain governments are ready to
   612       have seen this with Lavabit, just that the developers
   716       take such actions (we have seen this with Lavabit, just
   613       there refused to play ball and shut down their complete
   717       that the developers there refused to play ball and shut
   614       operation).
   718       down their complete operation).
   615 \item The government could also put pressure on mining pools
   719 \item The government could also put pressure on mining pools
   616       in order to blacklist transactions from baddies. Or be
   720       in order to blacklist transactions from baddies. Or be a
   617       big a miner itself. Given the gigantic facilities that
   721       big a miner itself. Given the gigantic facilities that
   618       are built for institutions like the NSA
   722       are built for institutions like the NSA (pictures from
       
   723       the Utah dessert)
   619       
   724       
   620       \begin{center}
   725       \begin{center}
   621       \includegraphics[scale=0.04]{../pics/nsautah1.jpg}
   726       \includegraphics[scale=0.04]{../pics/nsautah1.jpg}
   622       \hspace{3mm}
   727       \hspace{3mm}
   623       \includegraphics[scale=0.031]{../pics/nsautah2.jpg}
   728       \includegraphics[scale=0.031]{../pics/nsautah2.jpg}
   624       \end{center}
   729       \end{center}
   625       
   730       
   626       this would not be such a high bar to jump over.
   731       this would not be such a high bar to jump over. Remember
   627 \end{itemize} 
   732       it ``only'' takes to temporarily be in control of 50\%+
   628 
   733       of the mining capacity in order to undermine the trust
   629 \noindent Finally the government would potentially not need to
   734       in the system. Given sophisticated stories like Stuxnet
   630 follow up with such threads. Just the rumour that it would,
   735       (where we still not know the precise details) maybe even
   631 could be enough to get the Bitcoin-house-of-cards to tumble.
   736       such large facilities are not really needed. What
   632 Because of all this I would not have too much hope that
   737       happens, for example, if a government starts DoS attacks
   633 Bitcoins are free from government \& Co interference when it
   738       on existing miners: They have complete control
   634 will stand in its way.
   739       (unfortunately) of all mayor connectivity providers,
   635 
   740       i.e.~ISPs. 
       
   741       
       
   742       There are estimates that the Bitcoin mining capacity
       
   743       outperforms the top 500 supercomputers in the world,
       
   744       combined(!):
       
   745       
       
   746       \begin{center}\small
       
   747       \url{http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/}
       
   748       \end{center}
       
   749       
       
   750       But my gut feeling is that these are too simplistic
       
   751       calculations. In security (and things like Bitcoins) the
       
   752       world is never just black and white. The point is once
       
   753       the trust is undermined, the Bitcoin system would need
       
   754       to be evolved to Bitcoins 2.0. But who says that Bitcoin
       
   755       2.0 will honour the Bitcoins from Version 1.0?
       
   756       \end{itemize} 
       
   757 
       
   758 \noindent Finally, a government would potentially not really
       
   759 need to follow up with such threads. Just the rumour that it
       
   760 would, could be enough to get the Bitcoin-house-of-cards to
       
   761 tumble. Some governments have already such a ``impressive''
       
   762 trackrecord in this area, such a thread would be entirely
       
   763 credible. Because of all this, I would not have too much hope
       
   764 that Bitcoins are free from government \& Co interference when
       
   765 it will stand in its way, despite what everybody else is
       
   766 saying. To sum up, the technical details behind Bitcoins are
       
   767 simply cool. But still the entire Bitcoin ecosystem is in my
       
   768 humble opinion rather fragile. 
       
   769 
       
   770 \subsubsection*{Further Reading}
       
   771 
       
   772 Finally, finally, the article
       
   773 
       
   774 \begin{center}\small
       
   775 \url{http://www.extremetech.com/extreme/155636-the-bitcoin-network-outperforms-the-top-500-supercomputers-combined}
       
   776 \end{center}
       
   777 
       
   778 \noindent makes an interesting point: If people are willing to
       
   779 solve meaningless puzzles for hard, cold cash and with this
       
   780 achieve rather impressive results, what could we achieve if
       
   781 the UN, say, would find the money and incentivise people to,
       
   782 for example, solve protein folding
       
   783 puzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}}
       
   784 There are projects like
       
   785 Folding@home\footnote{\url{http://folding.stanford.edu}} which have 
       
   786 This might help with curing diseases such as Alzheimer or
       
   787 diabetes, which to a large portion baddies and goodies will
       
   788 suffer at some point. The same point is made in the article
       
   789 
       
   790 \begin{center}\small
       
   791 \url{http://gizmodo.com/the-worlds-most-powerful-computer-network-is-being-was-504503726}
       
   792 \end{center}
   636 
   793 
   637 \end{document}
   794 \end{document}
   638 
   795 
   639 bit coin
   796 bit coin
   640 https://bitcoin.org/bitcoin.pdf
   797 https://bitcoin.org/bitcoin.pdf