13 Bitcoins float around in the mainstream media, it will be

    14 Bitcoins float around in the mainstream and not-so-mainstream

    14 instructive to re-examine such claims from a more technically

    15 media, it will be instructive to re-examine such claims from a

    15 informed vantage point. For example, it is often claimed that

    16 more technically informed vantage point. For example, it is

    16 Bitcoins are anonymous and free from any potential government

    17 often claimed that Bitcoins are anonymous and free from any

    17 meddling. It turns out that the first claim ignores a lot of

    18 potential government meddling. It turns out that the first

    18 research in de-anonymising social networks, and the second

    19 claim ignores a lot of research in de-anonymising social

    19 underestimates the persuasive means a government has at their

    20 networks, and the second underestimates the persuasive means a

    20 disposal. 

    21 government has at its disposal. 

    21 

    22 

    22 There are a lot of articles, blogposts and so on available

    23 There are a lot of articles, blogposts, research papers

    23 about Bitcoins. Below I will follow closely the very readable

    24 etc.~available about Bitcoins. Below I will follow closely the

    24 explanations from

    25 very readable explanations from

    31 \noindent 

    32 \noindent The latter also contains a link to a nice youtube

    32 The latter also contains a link to a nice youtube video.

    33 video about the technical details behind Bitcoins.

    45 know. This part of Bitcoins is definitely anonymous. The first

    46 know. This part of Bitcoins is definitely anonymous. The paper

    46 Bitcoin transaction was made in January 2009. The rules in

    47 above is from the end of 2008; the first Bitcoin transaction

    47 Bitcoin are set up so that there will ever only be 21 Million

    48 was made in January 2009. The rules in Bitcoin are set up so

    48 Bitcoins with the maximum reached around the year 2140.

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

    49 Contrast this with traditional fiat currencies where money can

    50 maximum reached around the year 2140. Currently there are

    50 be printed almost at will. The smallest unit of a Bitcoin is

    51 already 11 Million Bitcoins mined. Contrast this with

    51 called a Satoshi which is the $10^{-8}$th part of a Bitcoin.

    52 traditional fiat currencies where money can be printed almost

    52 Remember a Penny is the $10^{-2}$th part of a Pound.

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

    54 which is the $10^{-8}$th part of a Bitcoin. Remember a Penny

    55 is the $10^{-2}$th part of a Pound.

    58 integrity. Public-private keys are used for signatures. For

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

    59 example sending a message, say $msg$, together with the

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

    60 encrypted version

    63 together with the encrypted version

    66 \noindent allows everybody with access to the public key to

    69 \noindent allows everybody with access to the corresponding

    67 verify the message came from the person who knew the private

    70 public key $K^{pub}$ to verify the message came from the

    68 key. Signatures are used in Bitcoins for verifying the

    71 person who knew the private key. Signatures are used in

    69 addresses where the Bitcoins are sent from. Addresses in

    72 Bitcoins for verifying the addresses where the Bitcoins are

    70 Bitcoins are essentially the public keys. There are $2^{160}$

    73 sent from. Addresses in Bitcoins are essentially the public

    71 possible addresses, which is such a vast amount that there is

    74 keys. There are $2^{160}$ possible addresses, which is such a

    72 not even a check for duplicates, or already used addresses. If

    75 vast amount that there is not even a check for duplicates, or

    73 you start with a random number to generate a public-private

    76 already used addresses. If you start with a random number to

    74 key pair it is very unlikely that you step on somebody else's

    77 generate a public-private key pair it is very unlikely that

    75 shoes. Compare this with email-addresses you ever wanted to

    78 you step on somebody else's shoes. Compare this with the

    76 register with, say, Googlemail, but which were always already

    79 email-addresses you always wanted to register with, say

    77 taken.

    80 Googlemail, but which are already taken.

    78 

    81 

    79 One main difference between Bitcoins and, say, traditional

    82 One main difference between Bitcoins and traditional banking

    80 banking is that you do not have a place that records the

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

    81 balance on your account. Traditional banking involves a

    84 your account. Traditional banking involves a central ledger

    82 central ledger which specifies the current balance in each

    85 which specifies the current balance in each account, for

    83 account, for example 

    86 example 

    98 to sending messages of the (rough) form 

   101 to sending messages of the (oversimplified) form 

   104 \noindent These are the transactions that are the only data

   107 \noindent These messages, called transactions, are the only

   105 that is ever stored (we will come to the precise details later

   108 data that is ever stored in the Bitcoin system (we will come

   106 on). The transactions are encrypted with Alice's private key

   109 to the precise details later on). The transactions are

   107 such that everybody, including Bob, can use Alice's public key

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

   108 $K^{pub}_{Alice}$ for verifying that this message came really

   111 including Bob, can use Alice's public key $K^{pub}_{Alice}$

   109 from Alice, or more precisely from the person who knows

   112 for verifying that this message came really from Alice, or

   110 $K^{priv}_{Alice}$. 

   113 more precisely from the person who knows $K^{priv}_{Alice}$. 

   143 was taken offline by law enforcement. 

   146 was taken offline by law enforcement. Bitcoins is more a

   144 

   147 system like BitTorrent without a single central entity that

   145 Bitcoin solves the problem of not wanting to rely on a bank by

   148 can be taken offline.

   146 making everybody the ``bank''. Everybody who cares can have

   149 

   150 Bitcoin solves the problem of not being able to rely on a bank

   151 by making everybody the ``bank''. Everybody who cares can have

   151 Bitcoin and if yes transmits the message to every other

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

   152 participant on the Bitcoin network. The blockchain looks

   157 other participant on the Bitcoin network. The blockchain looks

   167 the case. \ldots{}But does it eliminate all possibilities of

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

   168 fraud?

   173 possibilities of fraud?

   169 

   174 

   170 We can check the consistency of the blockchain by checking the

   175 We can check the consistency of the blockchain by checking

   171 entire block\-chain whether the references and hashes are

   176 whether all the references and hashes are correctly recorded.

   172 correctly recorded. I have not tried it myself, but it is said

   177 I have not tried it myself, but it is said that with the

   173 that with the current amount of data (appr.~12GB) it takes

   178 current amount of data (appr.~12GB) it takes roughly a day to

   174 roughly a day to check the consistency of the blockchain on a

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

   175 ``normal'' computer. Fortunately this ``extended'' consistency

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

   176 check usually only needs to be done once.

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

   182 to be updated consistently.

   180 record only transactions. Therefore it is possible to extract

   186 record only transactions. While a current balance of an

   181 from the blockchain a transaction graph that looks like the

   187 account is not immediately available, it is possible to

   182 picture shown in Figure~\ref{txngraph}. Take for example the

   188 extract from the blockchain a transaction graph that looks

   183 rightmost lower transaction from Charles to Emily. This

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

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

   190 example the rightmost lower transaction from Charles to Emily.

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

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

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

   192 received from Charles she can only make a transaction to

   199 received from Charles she can essentially only forward the

   193 forward the message she received. The only slight complication

   200 message she received. The only slight complication with this

   194 with is that incoming transactions can be combined in a

   201 setup in Bitcoins is that ``incoming'' Bitcoins can be

   195 transaction and ``outgoing'' Bitcoins can be split. For

   202 combined in a transaction and ``outgoing'' Bitcoins can be

   196 example in the leftmost upper transactions in

   203 split. For example in the leftmost upper transactions in

   202 smaller. But it is also important to be able to split the

   209 smaller. 

   203 money from one or more incoming transaction to more than one

   210 

   204 receiver. Consider again the rightmost transactions in

   211 But in Bitcoins it is also important to have the ability to

   205 Figure~\ref{txngraph} and suppose Alice is a coffeeshop owner

   212 split the money from one or more incoming transaction to

   206 selling coffees for 1 Bitcoin. Charles received a transaction 

   213 potentially more than one receiver. Consider again the

   207 from Zack over 5 Bitcoins. How does he pay for the coffee? 

   214 rightmost transactions in Figure~\ref{txngraph} and suppose

   208 There is no real notion of change in the Bitcoin system. What 

   215 Alice is a coffeeshop owner selling coffees for 1 Bitcoin.

   209 Charles has to do instead is to make one single transaction 

   216 Charles received a transaction from Zack over 5 Bitcoins, say.

   210 with 1 Bitcoin to Alice and with 4 Bitcoins going back to 

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

   211 himself. Which Charles can then use to give to Emily.

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

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

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

   221 use to give to Emily, for example.

   225 Bitcoin she has two possibilities. She could just forward the

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

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

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

   236 I let you have time to let this concept of transactions sink

   246 I think this is a good time for you to pause to let this

   237 in\ldots{}in the words of a famous 60ies Band: ``All you need

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

   238 is transactions''. There is no need for a central ledger and

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

   239 no need for an account balance from traditional banking. The

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

   240 closest what Bitcoin has to offer for a notion of a balance in

   250 and no need for an account balance as familiar from

   241 a bank account are the unspend transaction that a person (that

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

   242 is public-private key address) received. That means

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

   243 transactions that can still be forwarded. 

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

   244 

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

   245 Also consider the fact that whatever transaction is recorded

   255 forwarded. 

   246 in the blockchain is what will set the ``historical record''.

   256 

   247 If a transaction says 1 Bitcoin from address $A$ to address

   257 After the pause also consider the fact that whatever

   248 $B$, then this is what will be recorded. This is also how

   258 transaction is recorded in the blockchain will be in the

   249 Bitcoins can actually get lost: if you forget your private key

   259 ``historical record'' for the Bitcoin system. If a transaction

   250 and you had just a message forwarded to you address of the

   260 says 1 Bitcoin goes from address $A$ to address $B$, then this

   251 public key, then bad luck: you will never be able to forward

   261 is what will be---$B$ has then the possibility to spend the

   252 this message again, because you will not be able to form a

   262 corresponding Bitcoins, whether the transaction was done

   253 valid message that sends this to somebody else (we will see

   263 fraudulently or not. There is no exception to this rule.

   254 the details of this later). But this is also a way how you can

   264 Interestingly this is also how Bitcoins can get lost: One

   255 get robbed of your Bitcoins. An attacker might get hold of

   265 possibility is that you send Bitcoins to an address for which

   256 your private key and then quickly forward the Bitcoins in your

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

   257 name to an address the attacker controls. You have never again

   267 the address field---bad luck for fat

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

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

   270 address and consequently cannot forward the transaction

   271 anymore. Another possibility is that you forget your private

   272 key and you had messages forwarded to your address

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

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

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

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

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

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

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

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

   281 address the attacker controls. You will never have again

   259 are assumed to be spend. And remember with Bitcoins you cannot

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

   262 can try to harass the bank to rollback the transaction.

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

   266 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?

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

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

   268 Charlie, or even herself. If Bob is also in the coffee

   292 forward the ``same'' transaction to Charlie, or even herself.

   269 business, he would potentially be cheated out of his money.

   293 If Alice manages to get the second transaction into the

   270 The problem is how should people update their blockchain?

   294 blockchain, Bob will be cheated out of his money. The problem

   271 You might end up with a picture like this

   295 in such conflicting situations is how should the network

   272 

   296 update their blockchain? You might end up with a picture like

   273 \begin{center}

   297 this

   274 \includegraphics[scale=0.3]{../pics/bitcoindisagreement.png}

   298 

   275 \end{center}

   299 \begin{center}

   276 

   300 \includegraphics[scale=0.4]{../pics/bitcoindisagreement.png}

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

   301 \end{center}

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

   302 

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

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

   280 resolved? This is actually the main hurdle where Bitcoin 

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

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

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

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

   306 resolved? This is actually the main hurdle where Bitcoin

   283 Alice to him is legit. But what means enough in a distributed 

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

   284 system? If Alice sets up network of a billion puppy identidies

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

   285 and whenever Bob tries to ask whether Alice is the rightful 

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

   286 owner of the Bitcoin and Alice just send a transaction to him,

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

   287 the puppy network of identities just says yes. Bob would then 

   311 puppy identities and whenever Bob tries to convince, or

   288 give the coffee to Alice, but then for everybody else the

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

   289 

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

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

   315 everybody else on the network that she is still the rightful

   316 owner of the Bitcoin. After being outvoted, Bob would be a tad

   317 peeved. 

   318 

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

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

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

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

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

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

   325 the other direction of making the process of transaction

   326 validation (artificially) as expensive as possible, but reward

   327 people for helping with the validation. This is really a novel

   328 and counterintuitive idea that makes the whole system work so

   329 beautifully.

   330 

   331 \subsubsection*{Proof-of-Work}

   332 

   333 In order to make the process of transaction validation

   334 difficult, Bitcoin uses a kind of puzzles. Solving the puzzles

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

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

   337 Bitcoins, but the rules of Bitcoin are set up such that this

   338 amount halves every 210,000 transactions or so. Currently you

   339 will be awarded 25 Bitcoins for solving a puzzle. Because the

   340 amount will halve again and then later again and again, around

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

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

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

   344 validating transactions, because there is the possibility in

   345 Bitcoins to award a transaction fee to whoever solves a

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

   347 incentive for miners is the currently 25 Bitcoins that are

   348 awarded for solving puzzles. 

   349  

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

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

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

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

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

   355 the salt \code{0} as follows:

   356 

   357 \begin{quote}

   358 \code{h("Hello, world!0") =}\\

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

   360 \end{quote}

   361 

   362 \noindent OK this does not have any zeros at all. We could 

   363 next try the salt \code{1}: 

   364 

   365 \begin{quote}

   366 \code{h("Hello, world!1") =}\\

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

   368 \end{quote}

   369 

   370 %\begin{center}

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

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

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

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

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

   376 %\end{tabular}

   377 %\end{center}