49 that there will ever only be 21 Million Bitcoins with the

    49 that there will only ever be 21 Million Bitcoins with the

    51 already 11 Million Bitcoins mined. Contrast this with

    51 already 11 Million Bitcoins in `existence'. Contrast this with

    53 at will. The smallest unit of a Bitcoin is called a Satoshi

    53 at will. The smallest unit of a Bitcoin is called a Satoshi,

    58 cryptographic hashing (SHA-256) and public-private keys using

    58 cryptographic hashing functions (SHA-256) and public-private

    59 the elliptic-curve encryption scheme for digital signatures.

    59 keys using the elliptic-curve encryption scheme for digital

    60 Hashes are used to generate `fingerprints' of data that ensure

    60 signatures. Hashes are used to generate `fingerprints' of data

    61 integrity (absence of tampering). Public-private keys are used

    61 that ensure integrity (absence of tampering). Public-private

    62 for signatures. For example sending a message, say $msg$,

    62 keys are used for signatures. For example sending a message,

    63 together with the encrypted version

    63 say $msg$, together with the encrypted version

    83 is that you do not have a place that records the balance on

    83 is that you do not have a place, or places, that record the

    84 your account. Traditional banking involves a central ledger

    84 balance on your account. Traditional banking involves a

    85 which specifies the current balance in each account, for

    85 central ledger which specifies the current balance in each

    86 example 

    86 account, for example 

    90 account & balance\\\hline

    90 account owner & balance\\\hline

   110 encrypted with Alice's private key such that everybody,

   110 encrypted with Alice's private key so that everybody,

   115 The problem with such messages in a distributed system is what

   115 The problem with such messages in a distributed system is that

   116 happens if Bob receives 10, say, of these transactions. Did

   116 what happens if Bob receives 10, say, of these transactions.

   117 Alice intend to send him 10 Bitcoins, or did the message get

   117 Did Alice intend to send him 10 Bitcoins, or did the message

   118 duplicated by for example an attacker re-playing a sniffed

   118 get duplicated by for example an attacker re-playing a sniffed

   127 solved. One is who is assigning serial numbers to Bitcoins and

   127 solved with serial numbers. One is who is assigning serial

   128 also how can Bob verify that Alice actually owns this Bitcoin

   128 numbers to Bitcoins and also how can Bob verify that Alice

   129 to pay him? In a system with a bank as trusted third-party,

   129 actually owns this Bitcoin to pay him? In a system with a bank

   130 Bob could do the following:

   130 as trusted third-party, Bob could do the following:

   156 Bitcoin he received, and if yes transmits the message to every

   156 Bitcoin he received, and if she did, he transmits the message

   157 other participant on the Bitcoin network. The blockchain looks

   157 that he owns it now to every other participant on the Bitcoin

   158 roughly like a very long chain of individual blocks

   158 network. An illustration of a three-block segment of the

   159 

   159 blockchain is (simplified) as follows

   160 \begin{center}

   160 

   161 \begin{equation}

   162 \end{center}

   163 \label{segment}

   163 

   164 \end{equation}

   164 \noindent Each block contains a list of individual

   165 

   165 transactions, called txn in the picture above, and also a

   166 \noindent The chain grows with time. Each block contains a

   166 reference to the previous block, called prev. The data in a

   167 list of individual transactions, written txn in the picture

   167 block (txn's and prev) is hashed so that the reference and

   168 above, and also a reference to the previous block, written

   168 transactions in them cannot be tampered with. This hash is the

   169 prev. The data in a block (txn's and prev) is hashed so that

   169 unique serial number of each block. Since this

   170 the reference and transactions in them cannot be tampered

   170 previous-block-reference is also part of the hash, the whole

   171 with. This hash is the unique serial number of each block.

   171 chain is robust against tampering. I let you think why this is

   172 Since this previous-block-reference is also part of the hash,

   172 the case?\ldots{}But does it actually eliminate all

   173 the whole chain is robust against tampering. I let you think

   173 possibilities of fraud?

   174 why this is the case?\ldots{}But does it actually eliminate

   175 all possibilities of fraud?

   179 check the consistency of the blockchain on a ``normal''

   181 check the consistency of the blockchain on a normal computer.

   180 computer. Fortunately this ``extended'' consistency check

   182 Fortunately this ``extended'' consistency check usually only

   181 usually only needs to be done once. After that it only needs 

   183 needs to be done once. Afterwards the blockchain only needs to

   182 to be updated consistently.

   184 be updated consistently.

   183 

   185 

   184 Recall I wrote earlier that Bitcoins do not maintain a ledger

   186 Recall I wrote earlier that Bitcoins do not maintain a ledger,

   185 listing all the current balances in each account. Instead they

   187 which lists all the current balances in each account. Instead

   186 record only transactions. While a current balance of an

   188 only transactions are recorded. While a current balance of an

   189 like the picture shown in Figure~\ref{txngraph}. Take for

   191 like the picture shown in Figure~\ref{txngraph}. Each

   190 example the rightmost lower transaction from Charles to Emily.

   192 rectangle represents a single transaction. Take for example

   191 This transaction has as receiver the address of Emily and as

   193 the rightmost lower transaction from Charles to Emily. This

   192 the sender the address of Charles. In this way no Bitcoins can

   194 transaction has as receiver the address of Emily and as the

   195 sender the address of Charles. In this way no Bitcoins can

   204 Figure~\ref{txngraph} Fred makes a payment to Alice. But this

   207 Figure~\ref{txngraph}, Fred makes a payment to Alice. But this

   207 ``consolidate'' your funds: if there was always only a way to

   210 ``consolidate'' your funds: if it were only possible to split

   208 split transactions, then the amounts would get smaller and

   211 transactions, then the amounts would get smaller and smaller. 

   209 smaller. 

   217 How does he pay for the coffee? There is no real notion of

   219 How does he pay for the coffee? There is no explicit notion of

   218 change in the Bitcoin system. What Charles has to do instead

   220 \emph{change} in the Bitcoin system. What Charles has to do

   219 is to make one single transaction with 1 Bitcoin to Alice and

   221 instead is to make one single transaction with 1 Bitcoin to

   220 with 4 Bitcoins going back to himself, which then Charles can

   222 Alice and with 4 Bitcoins going back to himself, which then

   221 use to give to Emily, for example.

   223 Charles can use to give to Emily, for example.

   231 Let us make another example. Let us assume Emily received 4

   233 Let us consider another example. Suppose Emily received 4

   232 Bitcoins from Charles and independently has another

   234 Bitcoins from Charles and independently received another

   235 Bitcoin, she has two possibilities. She could just forward the

   237 Bitcoin, she has two possibilities: She could just forward the

   236 transaction from Charles over 4 Bitcoins to Alice splitted in

   238 transaction from Charles over 4 Bitcoins to Alice split in

   238 remaining 3 Bitcoins ``back'' to herself. In this case she would

   240 remaining 3 Bitcoins ``back'' to herself. In this case she

   239 now be in the ``posession'' of two unspend Bitcoin

   241 would now be in the ``posession'' of two unspend Bitcoin

   247 concept of transactions really sink in\ldots{}abusing the

   249 concept of transactions really sink in\ldots{}You should see

   248 words of a famous 60ies Band: With Bitcoins ``all you need is

   250 that there is really no need for a central ledger and no need

   249 transactions''. There is really no need for a central ledger

   251 for an account balance as familiar from traditional banking.

   250 and no need for an account balance as familiar from

   252 The closest what Bitcoin has to offer for the notion of a

   251 traditional banking. The closest what Bitcoin has to offer for

   253 balance in a bank account are the unspend transactions that a

   252 the notion of a balance in a bank account are the unspend

   254 person (more precisely a public-private key address) received.

   253 transaction that a person (more precisely a public-private key

   255 That means transactions that can still be forwarded. 

   254 address) received. That means transactions that can still be

   255 forwarded. 

   266 nobody has generated a private key. For example by a typo in

   266 nobody has generated a private key, for example because of a

   267 the address field---bad luck for fat

   267 typo in the address field---bad luck for fat

   268 fingers.\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}

   268 fingers\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}

   269 The reason is that nobody has a private key for this erroneous

   269 in the Bitcoin system. The reason is that nobody has a private

   270 address and consequently cannot forward the transaction

   270 key for this erroneous address and consequently cannot forward

   271 anymore. Another possibility is that you forget your private

   271 the transaction anymore. Another possibility is that you

   272 key and you had messages forwarded to your address

   272 forget your private key and you had messages forwarded to the

   273 corresponding to your the public key. In this case also bad

   273 corresponding public key. Also in this case bad luck: you will

   274 luck: you will never be able to forward this message again,

   274 never be able to forward this message again, because you will

   275 because you will not be able to form a valid message that

   275 not be able to form a valid message that sends this to

   276 sends this to somebody else (we will see the details of this

   276 somebody else (we will see the details of this later). But

   277 later). But this is also a way how you can get robbed of your

   277 this is also a way how you can get robbed of your Bitcoins. By

   278 Bitcoins. By old-fashioned hacking-into-a-computer crime, for

   278 old-fashioned hacking-into-a-computer crime, for example, an

   279 example, an attacker might get hold of your private key and

   279 attacker might get hold of your private key and then quickly

   280 then quickly forward the Bitcoins that are in your name to an

   280 forward the Bitcoins that are in your name to an address the

   281 address the attacker controls. You will never have again

   281 attacker controls. You will never again have access to these

   282 access to these Bitcoins, because for the Bitcoin system they

   282 Bitcoins, because for the Bitcoin system they are assumed to

   283 are assumed to be spent. And remember with Bitcoins you cannot

   283 be spent. And remember with Bitcoins you cannot appeal to any

   284 appeal to any higher authority. Once it is gone, it is gone.

   284 higher authority. Once the Bitcoins are gone, they are gone.

   285 This is different with traditional banking where at least you

   285 This is much different in traditional banking where at least

   286 can try to harass the bank to roll back the transaction. 

   286 you can try to harass the bank to roll back the transaction. 

   287 

   287 

   288 

   288 This brings us to back to problem of double spend. Suppose Bob

   289 This brings us to back to problem of double spend. Say Bob is

   289 is a merchant. How can he make sure that Alice does not cheat

   290 a merchant. How can he make sure that Alice does not cheat?

   290 him? She could for example send a transaction to Bob. But also

   291 She could for example send a transaction to Bob. But also

   303 \noindent Alice convinced some part of the ``world'' that she

   302 \noindent where Alice convinced some part of the ``world''

   304 is still owner of the bitcoin and some other part of the

   303 that she is still the owner of the Bitcoin and some other part

   305 ``world'' thinks its Bob's. How should such a disagreement be

   304 of the ``world'' thinks it's Bob's. How should such a

   306 resolved? This is actually the main hurdle where Bitcoin

   305 disagreement be resolved? This is actually the main hurdle

   307 really innovated. The answer is that Bob needs to convince

   306 where Bitcoin really innovated. The answer is that Bob needs

   308 ``enough'' people on the network that the transaction from

   307 to convince ``enough'' people on the network that the

   309 Alice to him is legit. However what does ``enough'' mean in a

   308 transaction from Alice to him is legit. 

   310 distributed system? If Alice sets up network of a billion

   309 

   311 puppy identities and whenever Bob tries to convince, or

   310 What does, however, ``enough'' mean in a distributed system?

   312 validate, that he is the rightful owner of the Bitcoin, the

   311 If Alice sets up a network of a billion, say, puppy identities

   313 puppy identities agree. Bob would then have no reason to not

   312 and whenever Bob tries to convince, or validate, that he is

   314 give Alice her coffee. But behind his back she has convinced

   313 the rightful owner of the Bitcoin, then the puppy identities

   314 agree. Bob would then have no reason to not give Alice her

   315 coffee. But behind his back, however, she has convinced

   319 The reflex action of a security engineer would be to make the

   320 The reflex reaction to such a situation would be to make the

   320 process of validating as cheap as possible. The idea is that

   321 process of validating a transaction as cheap as possible. The

   321 Bob will get enough peers to agree with him that he is the

   322 intention is that Bob will get enough peers to agree with him

   322 rightful owner. But such a solution has always the limitation

   323 that he is the rightful owner. But such a solution has always

   323 of that Alice could set up an even bigger network of puppy

   324 the limitation of Alice setting up an even bigger network of

   324 identities. So the really cool idea of Bitcoin is to go into

   325 puppy identities. The really cool idea of Bitcoin is to go

   325 the other direction of making the process of transaction

   326 into the other direction of making the process of transaction

   328 and counterintuitive idea that makes the whole system work so

   329 and counterintuitive idea that makes the whole system of

   329 beautifully.

   330 Bitcoins work so beautifully.

   330 

   331 

   331 \subsubsection*{Proof-of-Work}

   332 \subsubsection*{Proof-of-Work Puzzles}

   335 is called mining where whoever solves a puzzle will be awarded

   336 is called \emph{Bitcoin mining}, where whoever solves a puzzle

   336 some bitcoins. At the beginning of Bitcoins this was 50

   337 will be awarded some Bitcoins. At the beginning this was 50

   341 2140 it will go below the level of 1 Satoshi. In that event no

   342 the year 2140 it will go below the level of 1 Satoshi. In that

   342 new Bitcoins will ever be created again and the amount stays

   343 event no new Bitcoins will ever be created again and the

   343 fixed. There will be still an incentive to help with

   344 amount of Bitcoins stays fixed. There will be still an

   344 validating transactions, because there is the possibility in

   345 incentive to help with validating transactions, because there

   345 Bitcoins to award a transaction fee to whoever solves a

   346 is the possibility in Bitcoins to offer a transaction fee to

   346 puzzle. At the moment this fee is usually set to 0, since the

   347 whoever solves a puzzle. At the moment this fee is usually set

   347 incentive for miners is the currently 25 Bitcoins that are

   348 to 0, since the incentive for miners is the 25 Bitcoins that

   348 awarded for solving puzzles. 

   349 are currently awarded for solving puzzles. 

   350 What are the puzzles that miners have to solve? Recall that

   351 What do the puzzles that miners have to solve look like? The

   351 Bitcoins uses the hash-function SHA-256. The puzzle is roughly

   352 puzzles can be illustrated roughly as follows: Given a string,

   352 as follows: Given a string, say \code{"Hello, world!"}, what

   353 say \code{"Hello, world!"}, what is the salt so that the hash

   353 is the salt so the hash starts with a long run of zeros?

   354 starts with a long run of zeros? Let us look at a concrete

   354 Suppose we call the hash function \code{h}, then we could try 

   355 example. Recall that Bitcoins use the hash-function SHA-256.

   356 Suppose we call this hash function \code{h}, then we could try

   359 \mbox{}\quad\footnotesize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\\

   361 \mbox{}\quad\footnotesize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}

   367 \mbox{}\quad\footnotesize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\\

   369 \mbox{}\quad\footnotesize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}

   370 %\begin{center}

   372 \noindent Again this hash value does not contain any leading 

   371 %\begin{tabular}{@{}l@{}}

   373 zeros. We could now try out every salt until we reach

   372 %\footnotesize\code{h("Hllo, world!1")}\\ 

   374 

   373 %\;\;\scriptsize\code{%\ldots\\

   375 \begin{quote}

   374 %\footnotesize\code{h("Hello, world!4250")}\\ 

   376 \code{h("Hello, world!4250") =}\\

   375 %\;\;\scriptsize\code{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

   377 \mbox{}\quad\footnotesize\pcode{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

   376 %\end{tabular}

   378 \end{quote}

   377 %\end{center}

   379 

   380 \noindent where we have four leading zeros. If four zeros are

   381 enough, then the puzzle would be solved with this salt. The

   382 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

   384 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

   386 $16^{10} \approx 10^{12}$ different salts before we find a

   387 suitable one. In Bitcoins the puzzles are not solved according

   388 to how many leading zeros a has-value has, but rather whether

   389 it is below a \emph{target}. The hardness of the puzzle can

   390 actually be controlled by changing the target according to the

   391 available computational power available. I think the

   392 adjustment of the hardness of the problems is done every two

   393 weeks. I am not sure whether this is an automatic process. The

   394 aim of the adjustment is that on average the Bitcoin network

   395 will most likely solve a puzzle within 10 Minutes. 

   396 

   397 \begin{center}

   398 \includegraphics[scale=0.37]{../pics/blockchainsolving.png}

   399 \end{center}

   400 

   401 \noindent It could be solved quicker, but equally it could 

   402 take longer, but on average after 10 Minutes somebody on the 

   403 network will have found a solution. 

   404 

   405 Remember that the puzzles are a kind of proof-of-work that

   406 make the validation of transactions artificially expensive.

   407 The validation and the derivation of the puzzle is done as 

   408 follows:

   409 

   410 \begin{equation}

   411 \includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}

   412 \label{unconfirmed}

   413 \end{equation}

   414 

   415 \noindent There are some unconfirmed transactions. Choosing

   416 some of them, the miner (i.e.~the person/computer that tries

   417 to solve a puzzle) will form a putative block to be added to

   418 the blockchain. This putative block will contain the

   419 transactions and the reference to the previous block. The

   420 serial number of such a block is simply the hash of all the

   421 data. The puzzle can then be stated as the ``string''

   422 corresponding to the block and which salt is needed in order

   423 to have the hashed value being below the target. Other miners

   424 will choose different transactions and therefore work on a 

   425 slightly different putative block and puzzle.

   426 

   427 The intention of the proof-of-work puzzle is that the

   428 blockchain is at every given moment nicely linearly ordered,

   429 see the picture shown in \eqref{unconfirmed}. If we don’t have

   430 such a linear ordering at any given moment then it may not be

   431 clear who owns which Bitcoins. Assume a miner David is lucky

   432 and finds a suitable salt to confirm the transactions. Should

   433 he celebrate? Not yet. Typically the blockchain will look as

   434 follows

   435 

   436 \begin{center}

   437 \includegraphics[scale=0.65]{../pics/block_chain1.png}

   438 \end{center}

   439 

   440 \noindent But every so often there will be a fork

   441 

   442 \begin{center}

   443 \includegraphics[scale=0.65]{../pics/block_chain_fork.png}

   444 \end{center}

   445 

   446 \noindent What should be done in this case? The tie is broken

   447 if another block is solved, like so:

   448 

   449 \begin{center}

   450 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_branches.png}

   451 \end{center}

   452 

   453 \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,

   455 miners only work to extend whichever fork is longest in their

   456 copy of the block chain. Why should miners work on the longest

   457 fork? Well their incentive is to mine Bitcoins. If somebody

   458 else already solved a puzzle, then it makes more sense to work

   459 on a new puzzle and obtain the Bitcoins for solving that

   460 puzzle. Note that whoever solved a puzzle on the ``loosing''

   461 fork will actually not get any Bitcoins as reward. Tough luck.

   462 

   463 \subsubsection*{Alice against the Rest of the World}

   464 

   465 Let is see how the blockchain and the proof-of-work puzzles

   466 avoid the problem of double spend. If Alice wants to cheat

   467 Bob she would need to pull off the following ploy:

   468 

   469 \begin{center}

   470 \includegraphics[scale=0.4]{../pics/bitcoin_blockchain_double_spend.png}

   471 \end{center}

   472 

   473 \noindent Alice makes a transaction to Bob for paying, for

   474 example, for an online order. This transaction is confirmed,

   475 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

   477 validate the fraudulent transaction to herself instead. 

   478 

   479 \begin{center}

   480 \includegraphics[scale=0.4]{../pics/bitcoin_doublespend_blockchain_race.png}

   481 \end{center}

   482 

   483 \noindent At this moment she is in a race against all the

   484 computing power of the ``rest of the world''. She has to solve

   485 the puzzles one by one, because the hash of a block is

   486 determined by all the data in the previous has. She might be

   487 very lucky to solve one puzzle for a block before the rest of

   488 the world, but to be lucky many times is very unlikely. In

   489 order to raise the bar for Alice, merchants accepting Bitcoin

   490 use the following rule of thumb: A transaction is

   491 ``confirmed'' if (1) it is part of a block in the longest

   492 fork, and (2) at least 5 blocks follow it in the longest fork.

   493 In this case we say that the transaction has ``6

   494 confirmations''. A simple calculation shows that these number

   495 of confirmations can take up to 1 hour and more. While this

   496 seems excessively long, from the merchant's point of view it

   497 is not long at all. For this recall that ordinary credit cards

   498 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

   500 cheat are very low.

   501 

   502 Connected with the 6-confirmation rule is an interesting

   503 phenomenon. On average, it would take several years for a

   504 typical computer to solve a proof-of-work puzzle, so an

   505 individual’s chance of ever solving one before the rest of the

   506 world, which typically takes 10 minutes, is negligibly low.

   507 Therefore many people join groups called \emph{mining pools}

   508 that collectively work to solve blocks, and distribute rewards

   509 based on work contributed. These mining pools act somewhat

   510 like lottery pools among co-workers, except that some of these

   511 pools are quite large, and comprise more than 20\% of all the

   512 computers in the network. It is said that BTC, the largest

   513 mining pool, has limited its members to not solve more than 6

   514 blocks in a row. Otherwise this would undermine the trust in

   515 Bitcoins, which is also not in the interest of BTC, I guess.

   516 

   517 \subsubsection*{Bitcoins for Real}

   518