6 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015}

    46 \fnote{\copyright{} Christian Urban, 2014, 2015}

     7 

    47 

     8 %https://www.theguardian.com/technology/2016/oct/04/yahoo-secret-email-program-nsa-fbi

    48 \section*{Handout 7 (Bitcoins)}

     9 %https://nakedsecurity.sophos.com/2015/11/12/california-collects-owns-and-sells-infants-dna-samples/

    49 

    10 %http://randomwalker.info/teaching/fall-2012-privacy-technologies/?

    50 In my opinion Bitcoins are an elaborate Ponzi

    11 %https://josephhall.org/papers/NYU-MCC-1303-S2012_privacy_syllabus.pdf

    51 scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still

    12 %http://www.jetlaw.org/wp-content/uploads/2014/06/Bambauer_Final.pdf

    52 the ideas behind them are really beautiful and not too

    13 %http://www.cs.cmu.edu/~yuxiangw/docs/Differential%20Privacy.pdf

    53 difficult to understand. Since many colourful claims about

    14 %https://www.youtube.com/watch?v=Gx13lgEudtU

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

    15 %https://fpf.org/wp-content/uploads/Differential-Privacy-as-a-Response-to-the-Reidentification-Threat-Klinefelter-and-Chin.pdf

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

    16 %http://research.neustar.biz/2014/09/08/differential-privacy-the-basics/

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

    17 

    57 often claimed that Bitcoins are anonymous and free from any

    18 %=====

    58 potential government meddling. It turns out that the first

    19 %Tim Greene, Network World, 17 Dec 2015   (via ACM TechNews, 18 Dec 2015)

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

    20 %

    60 networks, and the second underestimates the persuasive means a

    21 %Massachusetts Institute of Technology (MIT) researchers' experimental

    61 government has at its disposal. 

    22 %Vuvuzela messaging system offers more privacy than The Onion Router (Tor) by

    62 

    23 %rendering text messages sent through it untraceable.  MIT Ph.D. student

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

    24 %David Lazar says Vuvuzela resists traffic analysis attacks, while Tor

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

    25 %cannot.  The researchers say the system functions no matter how many parties

    65 very readable explanations from

    26 %are using it to communicate, and it employs encryption and a set of servers

    66 

    27 %to conceal whether or not parties are participating in text-based dialogues.

    67 \begin{center}

    28 %"Vuvuzela prevents an adversary from learning which pairs of users are

    68 \url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\

    29 %communicating, as long as just one out of [the] servers is not compromised,

    69 \url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}

    30 %even for users who continue to use Vuvuzela for years," they note.  Vuvuzela

    70 \end{center}

    31 %can support millions of users hosted on commodity servers deployed by a

    71 

    32 %single group of users.  Instead of anonymizing users, Vuvuzela prevents

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

    33 %outside observers from differentiating between people sending messages,

    73 video about the technical details behind Bitcoins. I will

    34 %receiving messages, or neither, according to Lazar.  The system imposes

    74 also use some of their pictures.

    35 %noise on the client-server traffic which cannot be distinguished from actual

    75 

    36 %messages, and all communications are triple-wrapped in encryption by three

    76 Let us start with the question who invented Bitcoins? You

    37 %servers.  "Vuvuzela guarantees privacy as long as one of the servers is

    77 could not make up the answer, but we actually do not know who

    38 %uncompromised, so using more servers increases security at the cost of

    78 the inventor is. All we know is that the first paper

    39 %increased message latency," Lazar notes.

    79 

    40 %http://orange.hosting.lsoft.com/trk/click?ref=znwrbbrs9_5-e70bx2d991x066779&

    80 \begin{center}

    41 

    81 \url{https://bitcoin.org/bitcoin.pdf}

    42 %%%%

    82 \end{center}

    43 %% canvas tracking

    83 

    44 %%https://freedom-to-tinker.com/blog/englehardt/the-princeton-web-census-a-1-million-site-measurement-and-analysis-of-web-privacy/

    84 \noindent is signed by Satoshi Nakamoto, which however is

    45 

    85 likely only a pen name. There is a lot of speculation who

    46 %%%

    86 could be the inventor, or inventors, but we simply do not

    47 %% cupit re-identification attack

    87 know. This part of Bitcoins is definitely anonymous so far.

    48 %% https://nakedsecurity.sophos.com/2016/05/20/published-personal-data-on-70000-okcupid-users-taken-down-after-dmca-order/?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+nakedsecurity+%28Naked+Security+-+Sophos%29

    88 The paper above is from the end of 2008; the first Bitcoin

    49 

    89 transaction was made in January 2009. The rules in Bitcoin are

    50 %Differential privacy

    90 set up so that there will only ever be 21 Million Bitcoins

    51 %=====================

    91 with the maximum reached around the year 2140. Currently there

    52 %https://www.wired.com/2016/06/apples-differential-privacy-collecting-data/

    92 are already 11 Million Bitcoins in `existence'. Contrast this

    53 

    93 with traditional fiat currencies where money can be printed

    54 %Differential privacy, translated from Apple-speak, is the

    94 almost at will. The smallest unit of a Bitcoin is called a

    55 %statistical science of trying to learn as much as possible

    95 Satoshi, which is the $10^{-8}$th part of a Bitcoin. Remember

    56 %about a group while learning as little as possible about any

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

    57 %individual in it.

    97 

    58 

    98 The two main cryptographic building blocks of Bitcoins are

    59 %As Roth notes when he refers to a “mathematical proof,”

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

    60 %differential privacy doesn’t merely try to obfuscate or

   100 keys using the elliptic-curve encryption scheme for digital

    61 %“anonymize” users’ data. That anonymization approach, he

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

    62 %argues, tends to fail. In 2007, for instance, Netflix released

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

    63 %a large collection of its viewers’ film ratings as part of a

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

    64 %competition to optimize its recommendations, removing people’s

   104 say $msg$, together with the encrypted version

    65 %names and other identifying details and publishing only their

   105 

    66 %Netflix ratings. But researchers soon cross-referenced the

   106 \[

    67 %Netflix data with public review data on IMDB to match up

   107 msg, \{msg\}_{K^{priv}}

    68 %similar patterns of recommendations between the sites and add

   108 \]

    69 %names back into Netflix’s supposedly anonymous database.

   109 

    70 

   110 \noindent allows everybody with access to the corresponding

    71 %As an example of that last method, Microsoft’s Dwork points to

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

    72 %the technique in which a survey asks if the respondent has

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

    73 %ever, say, broken a law. But first, the survey asks them to

   113 Bitcoins for verifying the addresses where the Bitcoins are

    74 %flip a coin. If the result is tails, they should answer

   114 sent from. Addresses in Bitcoins are essentially the public

    75 %honestly. If the result is heads, they’re instructed to flip

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

    76 %the coin again and then answer “yes” for heads or “no” for

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

    77 %tails. The resulting random noise can be subtracted from the

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

    78 %results with a bit of algebra, and every respondent is

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

    79 %protected from punishment if they admitted to lawbreaking.

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

    80 

   120 email-addresses you wanted to register with, say

    81 %https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

   121 Gmail, but which are always already taken.

    82 

   122 

    83 % Windows 10 data send back to Microsoft (Cortana)

   123 One major difference between Bitcoins and traditional banking

    84 %Here’s a non-exhaustive list of data sent back: location data, text

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

    85 %input, voice input, touch input, webpages you visit, and telemetry

   125 balance on your account. Traditional banking involves a

    86 %data regarding your general usage of your computer, including which

   126 central ledger which specifies the current balance in each

    87 %programs you run and for how long.

   127 account, for example 

    88 

   128 

    89 % Businesses are already using customised pricing online based on

   129 \begin{center}

    90 % information they can glean about you. It is hard to know how

   130 \begin{tabular}{l|r}

    91 % widespread the practice is; companies keep their pricing strategies

   131 account owner & balance\\\hline

    92 % closely guarded and are wary of the bad PR price discrimination

   132 Alice   & \pounds{10.01}\\

    93 % could pose. However, it is clear that a number of large retailers

   133 Bob     & \pounds{4.99}\\

    94 % are experimenting with it. Staples, for example, has offered

   134 Charlie & -\pounds{1.23}\\

    95 % discounted prices based on whether rival stores are within 20 miles

   135 Eve     & \pounds{0.00}

    96 % of its customers’ location. Office Depot has admitted to using its

   136 \end{tabular}

    97 % customers’ browsing history and location to vary its range of offers

   137 \end{center}

    98 % and products. A 2014 study from Northeastern University found

   138 

    99 % evidence of “steering” or differential pricing at four out of 10

   139 \noindent Bitcoins work differently in that there is no such

   100 % general merchandise websites and five out of five travel

   140 central ledger, but instead a public record of all

   101 % websites. (Steering is when a company doesn’t give you a customised

   141 transactions ever made. This means spending money corresponds

   102 % price, but points you towards more expensive options if it thinks

   142 to sending messages of the (oversimplified) form 

   103 % you will pay more.) The online travel company Orbitz raised

   143 

   104 % headlines in 2012 when it emerged that the firm was pointing Mac

   144 \begin{equation}

   105 % users towards higher-priced hotel rooms than PC users.

   145 \{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}

   106 

   146 \end{equation}

   107 

   147 

   108 %%% government will overwrite your wishes if it is annoymous

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

   109 %% https://www.lightbluetouchpaper.org/2016/12/05/government-u-turn-on-health-privacy/

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

   110 

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

   111 %% corporate surveilance / privacy - report and CC3C talk

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

   112 %%      http://crackedlabs.org/en/networksofcontrol

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

   113 %%      https://media.ccc.de/v/33c3-8414-corporate_surveillance_digital_tracking_big_data_privacy#video&t=2933

   153 verify that this message came really from Alice, or more

   114 

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

   115 \section*{Handout 6 (Privacy)}

   155 

   116 

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

   117 The first motor car was invented around 1886. For ten years,

   157 what happens if Bob receives 10, say, of these transactions?

   118 until 1896, the law in the UK (and elsewhere) required a

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

   119 person to walk in front of any moving car waving a red flag.

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

   120 Cars were such a novelty that most people did not know what to

   160 message? What is needed is a kind of serial number for such

   121 make of them. The person with the red flag was intended to

   161 transactions. This means transaction messages shoul look more like 

   122 warn the public, for example horse owners, about the impending

   162 

   123 novelty---a car. In my humble opinion, we are at the same

   163 \begin{center}

   124 stage of development with privacy. Nobody really knows what it

   164 $\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$

   125 is about or what it is good for. All seems very hazy. There

   165 \end{center}

   126 are a few laws (e.g.~cookie law, right-to-be-forgotten law)

   166 

   127 which address problems with privacy, but even if they are well

   167 \noindent There are two difficulties, however, that need to be

   128 intentioned, they either back-fire or are already obsolete

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

   129 because of newer technologies. The result is that the world of

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

   130 ``privacy'' looks a little bit like the old Wild

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

   131 West---lawless and mythical.

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

   132 

   172 

   133 We would have hoped that after Snowden, Western governments

   173 \begin{itemize}

   134 would be a bit more sensitive and enlightned about the topic

   174 \item Bob asks the bank whether the Bitcoin with that serial

   135 of privacy, but this is far from the truth. Ross Anderson

   175       number belongs to Alice and Alice hasn't already spent

   136 wrote the following in his blog\footnote{\url{https://www.lightbluetouchpaper.org/2016/02/11/report-on-the-ip-bill/}} about the approach taken in

   176       this Bitcoin.

   137 the US to lessons learned from the Snowden leaks and contrasts

   177 \item If yes, then Bob tells the bank he accepts this Bitcoin.

   138 this with the new snooping bill that is considered in the UK

   178       The bank updates the records to show that the Bitcoin

   139 parliament: 

   179       with that serial number is now in Bob’s possession and

   140 

   180       no longer belongs to Alice. 

   141 \begin{quote}\it 

   181 \end{itemize}

   142 ``The comparison with the USA is stark. There, all three

   182 

   143 branches of government realised they'd gone too far after

   183 \noindent But for this banks would need to be trusted and

   144 Snowden. President Obama set up the NSA review group, and

   184 would also be an easy target for any government interference,

   145 implemented most of its recommendations by executive order;

   185 for example. Think of the early days of music sharing where

   146 the judiciary made changes to the procedures of the FISA

   186 the company Napster was the trusted third-party but also the single point of ``failure'' which

   147 Court; and Congress failed to renew the data retention

   187 was taken offline by law enforcement. Bitcoins is more like a

   148 provisions in the Patriot Act (aided by the judiciary). Yet

   188 system such as BitTorrent without a single central entity that

   149 here in Britain the response is just to take Henry VIII powers

   189 can be taken offline.\footnote{There is some Bitcoin

   150 to legalise all the illegal things that GCHQ had been up to,

   190 infrastructure that is not so immune from being taken offline:

   151 and hope that the European courts won't strike the law down

   191 for example Bitcoin exchanges, HQs of Bitcoin mining pools,

   152 yet again.''

   192 Bitcoin developers and so on.}

   193 

   194 Bitcoins solve the problem of not being able to rely on a bank

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

   196 the entire transaction history starting with the first

   197 transaction made in January 2009. This history of transactions

   198 is called the \emph{blockchain}. Bob, for example, can use his

   199 copy of the blockchain for determining whether Alice owned the

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

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

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

   203 blockchain is (simplified) as follows

   204 

   205 \begin{equation}

   206 \includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png}

   207 \label{segment}

   208 \end{equation}

   209 

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

   211 list of individual transactions, written txn in the picture

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

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

   214 the reference and transactions in them cannot be tampered

   215 with. This hash is also the unique serial number of each

   216 block. Since this previous-block-reference is also part of the

   217 hash, the whole chain is robust against tampering. I let you

   218 think why this is the case?\ldots{}But does it actually

   219 eliminate all possibilities of fraud?

   220 

   221 We can check the consistency of the blockchain by checking

   222 whether all the references and hashes are correctly recorded.

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

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

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

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

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

   228 be updated consistently.

   229 

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

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

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

   233 account is not immediately available, it is possible to

   234 extract from the blockchain a transaction graph that looks

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

   236 rectangle represents a single transaction. Take for example

   237 the rightmost lower transaction from Charles to Emily. This

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

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

   240 appear out of thin air (we will discuss later how Bitcoins are

   241 actually generated). If Charles did not have a transaction of

   242 at least the amount he wants to give Emily to his name

   243 (i.e.~send to an address with his public-private key) then

   244 there is no way he can make a payment to Emily. Equally, if

   245 now Emily wants to pay for a coffee, say, with the Bitcoin she

   246 received from Charles she can essentially only forward the

   247 message she received. The only slight complication with this

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

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

   250 split. For example in the leftmost upper transactions in

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

   252 payment (or transaction) combines the Bitcoins that were send

   253 by Jane to Fred and also by Juan to Fred. This allows you to

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

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

   256 

   257 In Bitcoins you have the ability to both combine incoming

   258 transactions, but also to split outgoing transactions to

   259 potentially more than one receiver. The latter is also needed.

   260 Consider again the rightmost transactions in

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

   262 selling coffees for 1 Bitcoin. Charles received a transaction

   263 from Zack over 5 Bitcoins, say. How does Charles pay for the

   264 coffee? There is no explicit notion of \emph{change} in the

   265 Bitcoin system. What Charles has to do instead is to make one

   266 single transaction with 1 Bitcoin to Alice and with 4 Bitcoins

   267 going back to himself, which then Charles can use to give to

   268 Emily, for example.

   269 

   270 \begin{figure}[t]

   271 \begin{center}

   272 \includegraphics[scale=0.4]{../pics/blockchain.png}

   273 \end{center}

   274 \caption{Transaction graph that is implicitly recorded in the

   275 public blockchain.\label{txngraph}}

   276 \end{figure}

   277 

   278 Let us consider another example. Suppose Emily received 4

   279 Bitcoins from Charles and independently received another

   280 transaction (not shown in the picture) that sends 6 Bitcoins

   281 to her. If she now wants to buy a coffee from Alice for 1

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

   283 transaction from Charles over 4 Bitcoins to Alice split in

   284 such a way that Alice receives 1 Bitcoin and Emily sends the

   285 remaining 3 Bitcoins back to herself. In this case she would

   286 now be in the possession of two unspend Bitcoin transactions,

   287 one over 3 Bitcoins and the independent one over 6 Bitcoins.

   288 Or, Emily could combine both transactions (one over 4 Bitcoins

   289 from Charles and the independent one over 6 Bitcoins) and then

   290 split this amount with 1 Bitcoin going to Alice and 9 Bitcoins

   291 going back to herself. 

   292 

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

   294 concept of transactions to really sink in\ldots{}You should

   295 come to the conclusion that there is really no need for a central ledger and no

   296 need for an account balance as familiar from traditional

   297 banking. The closest what Bitcoin has to offer for the notion

   298 of a balance in a bank account are the unspend transactions

   299 that a person (more precisely a public-private key address)

   300 received. That means transactions that can still be forwarded. 

   301 

   302 After the pause also consider the fact that whatever

   303 transaction is recorded in the blockchain will be in the

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

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

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

   307 corresponding Bitcoins, whether the transaction was done

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

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

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

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

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

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

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

   315 key for this erroneous address and consequently cannot forward

   316 the transaction anymore. Another possibility is that you

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

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

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

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

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

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

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

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

   325 forwards the Bitcoins that are in your name to an address the

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

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

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

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

   330 This is much different in traditional banking where at least

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

   332 

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

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

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

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

   337 If Alice manages to get the second transaction into the

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

   339 in such conflicting situations is how should the network

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

   341 this

   342 

   343 \begin{center}

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

   345 \end{center}

   346 

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

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

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

   350 disagreement be resolved? This is actually the main hurdle

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

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

   353 transaction from Alice to him is legit. 

   354 

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

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

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

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

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

   360 coffee. But behind his back she has convinced everybody else

   361 on the network that she is still the rightful owner of the

   362 Bitcoin. After being outvoted, Bob would be a tad peeved. 

   363 

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

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

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

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

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

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

   370 into the other direction of making the process of transaction

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

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

   373 and counterintuitive idea that makes the whole system of

   374 Bitcoins work so beautifully.

   375 

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

   377 

   378 In order to make the process of transaction validation

   379 difficult, Bitcoin uses a kind of puzzle. Solving the puzzles

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

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

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

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

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

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

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

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

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

   389 incentive to help with validating transactions, because there

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

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

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

   393 are currently awarded for solving puzzles. 

   394  

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

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

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

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

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

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

   401 the salt \code{0} as follows:

   402 

   403 \begin{quote}

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

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

   155 \noindent Unfortunately, also big organisations besides

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

   156 governments seem to take an unenlightened approach to privacy.

   409 next try the salt \code{1}: 

   157 For example, UCAS, a charity set up to help students with

   410 

   158 applying to universities in the UK, has a commercial unit that

   411 \begin{quote}

   159 happily sells your email addresses to anybody who forks out

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

   160 enough money for bombarding you with spam. Yes, you can opt

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

   161 out very often from such ``schemes'', but in case of UCAS any

   414 \end{quote}

   162 opt-out will limit also legit emails you might actually be

   415 

   163 interested in.\footnote{The main objectionable point, in my

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

   164 opinion, is that the \emph{charity} everybody has to use for

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

   165 HE applications has actually very honourable goals

   418 

   166 (e.g.~assist applicants in gaining access to universities),

   419 \begin{quote}

   167 but the small print (or better the link ``About us'') reveals

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

   168 they set up their organisation so that they can also

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

   169 shamelessly sell the email addresses they ``harvest''.

   422 \end{quote}

   170 Everything is of course very legal\ldots{}ethical?\ldots{}well

   423 

   171 that is in the eye of the beholder. See:

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

   172 

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

   173 \url{http://www.ucas.com/about-us/inside-ucas/advertising-opportunities} 

   426 point is that we can very quickly check whether a salt solves

   174 or

   427 a puzzle, but it is hard to find one. Latest research suggest

   175 \url{http://www.theguardian.com/uk-news/2014/mar/12/ucas-sells-marketing-access-student-data-advertisers}}

   428 it is an NP-problem. If we want the output hash value to begin

   176 

   429 with 10 zeroes, say, then we will, on average, need to try

   177 Another example: Verizon, an ISP who is supposed to provide

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

   178 you just with connectivity, has found a ``nice'' side-business

   431 suitable one. 

   179 too: When you have enabled all privacy guards in your browser

   432 

   180 (the few you have at your disposal), Verizon happily adds a

   433 In Bitcoins the puzzles are not solved according to how many

   181 kind of cookie to your

   434 leading zeros a hash-value has, but rather whether it is below

   182 HTTP-requests.\footnote{\url{http://webpolicy.org/2014/10/24/how-verizons-advertising-header-works/}}

   435 a \emph{target}. The hardness of the puzzle can actually be

   183 As shown in the picture below, this cookie will be sent to

   436 controlled by changing the target according to the available

   184 every web-site you visit. The web-sites then can forward the

   437 computational power available. I think the adjustment of the

   185 cookie to advertisers who in turn pay Verizon to tell them

   438 hardness of the problems is done every 2060 blocks

   186 everything they want to know about the person who just made

   439 (appr.~every two weeks). The aim of the adjustment is that on

   187 this request, that is you.

   440 average the Bitcoin network will most likely solve a puzzle

   441 within 10 Minutes. 

   442 

   443 \begin{center}

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

   445 \end{center}

   446 

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

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

   449 network will have found a solution. 

   450 

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

   452 make the validation of transactions artificially expensive.

   453 Consider the following picture with a blockchain and some

   454 unconfirmed transactions. 

   455 

   456 \begin{equation}

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

   458 \label{unconfirmed}

   459 \end{equation}

   460 

   461 \noindent The puzzle is stated as follows: There are some

   462 unconfirmed transactions. Choosing some of them, the miner

   463 (i.e.~the person/computer that tries to solve a puzzle) will

   464 form a putative block to be added to the blockchain. This

   465 putative block will contain the transactions and the reference

   466 to the previous block. The serial number of such a block is

   467 simply the hash of all the data. The puzzle can then be stated

   468 as the ``string'' corresponding to the block and which salt is

   469 needed in order to have the hashed value being below the

   470 target. Other miners will choose different transactions and

   471 therefore work on a slightly different putative block and

   472 puzzle.

   473 

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

   475 blockchain is at every given moment linearly ordered, see the

   476 picture shown in \eqref{unconfirmed}. If we don’t have such a

   477 linear ordering at any given moment then it may not be clear

   478 who owns which Bitcoins. Assume a miner David is lucky and

   479 finds a suitable salt to confirm some transactions. Should he

   480 celebrate? Not yet. Typically the blockchain will look as

   481 follows

   482 

   483 \begin{center}

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

   485 \end{center}

   486 

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

   488 

   489 \begin{center}

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

   491 \end{center}

   492 

   493 \noindent What should be done in this case? Well, the tie is

   494 broken if another block is solved, like so:

   495 

   496 \begin{center}

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

   498 \end{center}

   499 

   500 \noindent The rule in Bitcoins is: If a fork occurs, people on

   501 the network keep track of all forks (they can see). But at any

   502 given time, miners only work to extend whichever fork is

   503 longest in their copy of the block chain. Why should miners

   504 work on the longest fork? Well their incentive is to mine

   505 Bitcoins. If somebody else already solved a puzzle, then it

   506 makes more sense to work on a new puzzle and obtain the

   507 Bitcoins for solving that puzzle, rather than waste efforts on

   508 a fork that is shorter and therefore less likely to be

   509 ``accepted''. Note that whoever solved a puzzle on the

   510 ``loosing'' fork will actually not get any Bitcoins as reward.

   511 Tough luck.

   512 

   513 

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

   515 

   516 Let us see how the blockchain and the proof-of-work puzzles

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

   518 Bob, she would need to pull off the following ploy:

   519 

   520 \begin{center}

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

   522 \end{center}

   523 

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

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

   526 or validated, in block 2. Bob ships the goods around block 4.

   527 In this moment, Alice needs to get into action and try to

   528 validate the fraudulent transaction to herself instead. At

   529 this moment she is in a race against all the computing power

   530 of the ``rest of the world''. Because the incentive of the

   531 rest of the world is to work on the longest chain, that is the

   532 one with the transaction from Alice to Bob:

   533 

   534 \begin{center}

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

   536 \end{center}

   537 

   538 \noindent As shown in the picture she has to solve the puzzles

   539 2a to 5a one after the other, because the hash of a block is

   540 determined via the reference by all the data in the previous

   541 block. She might be very lucky to solve one puzzle for a block

   542 before the rest of the world, but to be lucky many times is

   543 very unlikely. This principle of having to race against the

   544 rest of the world avoids the ploy of double spend.

   545 

   546 In order to raise the bar for Alice even further, merchants

   547 accepting Bitcoins use the following rule of thumb: A

   548 transaction is ``confirmed'' if 

   549 

   550 \begin{itemize}

   551 \item[(1)] it is part of a block in the longest fork, and 

   552 \item[(2)] at least 5 blocks follow it in the longest fork. In

   553            this case we say that the transaction has 6

   554            confirmations. 

   555 \end{itemize} 

   556 

   557 \noindent A simple calculation shows that this amount of

   558 confirmations can take up to 1 hour and more. While this seems

   559 excessively long, from the merchant's point of view it is not

   560 that long at all. For this recall that ordinary creditcards

   561 can have their transactions been rolled-back for 6 months or

   562 so. The point however is that the odds for Alice being able to

   563 cheat are very low, unless she can muster more than 50\% of

   564 the world Bitcoin mining capacity. In this case she could

   565 out-race the rest of the world. The point is however that

   566 amassing such an amount of computing power is practically

   567 impossible for a single person or even a moderately large 

   568 group.

   569 

   570 Connected with the 6-confirmation rule is an interesting

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

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

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

   574 world, which typically takes only 10 minutes, is negligibly

   575 low. Therefore many people join groups called \emph{mining

   576 pools} that collectively work to solve blocks, and distribute

   577 rewards based on work contributed. These mining pools act

   578 somewhat like lottery pools among co-workers, except that some

   579 of these pools are quite large, and comprise more than 20\% of

   580 all the computers in the network. It is said that BTCC, a

   581 large mining pool, has limited its number of members in order

   582 to not solve more than 6 blocks in a row. Otherwise this would

   583 undermine the trust in Bitcoins, which is also not in the

   584 interest of BTCC, I guess. Some statistics on mining pools can

   585 be seen at

   586 

   587 \begin{center}

   588 \url{https://blockchain.info/pools}

   589 \end{center}

   590 

   591 \noindent Here is an interesting problem: You are part of a lottery

   592 pool, if you chip in some of the money to buy a lottery ticket. In

   593 this setting it is clear when you are in or outside of the pool. But

   594 how do you make sure people work hard in a mining pool in order to

   595 justify a fraction of any reward? If evil me had its way, I would just

   596 claim I do work and then sit back and relax. Or even if I do some work

   597 for a mining pool and I happen to find a correct salt, I would keep it

   598 secret and submit it to the bitcoin network on the ``side''. Actually,

   599 the idea of mining pools has opened up a full can of interesting

   600 problems.

   601 

   602 

   603 

   604 \subsubsection*{Bitcoins for Real}

   605 

   606 Let us now turn to the nitty gritty details. As a participant

   607 in the Bitcoin network you need to generate and store a

   608 public-private key pair. The public key you need to advertise

   609 in order to receive payments (transactions). The private key

   610 needs to be securely stored. For this there seem to be three

   611 possibilities

   612 

   613 \begin{itemize}

   614 \item an electronic wallet on your computer

   615 \item a cloud-based storage (offered by some Bitcoin services)

   616 \item paper-based

   617 \end{itemize}

   618 

   619 \noindent The first two options of course offer convenience

   620 for making and receiving transactions. But given the nature of

   621 the private keys and how much security relies on them (recall

   622 if somebody gets hold of it, your Bitcoins are quickly lost

   623 forever) I would opt for the third option for anything except

   624 for trivial amounts of Bitcoins. As we have seen earlier in

   625 the course, securing a computer system that it can withstand a

   626 targeted breakin is still very much an unsolved problem.

   627 

   628 An interesting fact with Bitcoin keys is that there is no

   629 check for duplicate addresses. This means when generating a

   630 public-private key, you should really start with a carefully

   631 chosen random number such that there is really no chance to

   632 step on somebody's feet in the $2^{160}$ space of

   633 possibilities. Again if you share an address with somebody

   634 else, he or she has access to all your unspend transactions.

   635 The absence of such a check is easily explained: How would one

   636 do this in a distributed system? The answer you can't. It is

   637 possible to do some sanity check of addresses that are already

   638 used in the blockchain, but this is not a fail-proof method.

   639 One really has to trust on the enormity of the $2^{160}$

   640 space for addresses.

   641 

   642 Let us now look at the concrete data that is stored in an transaction 

   643 message:

   644 

   645 \lstinputlisting[language=Scala]{../slides/msg}

   646 

   647 \noindent The hash in Line 1 is the hash of all the data that

   648 follows. It is a kind of serial number for the transaction.

   649 Line 2 contains a version number in case there are some

   650 incompatible changes to be made. Lines 3 and 4 specify how

   651 many incoming transactions are combined and how many outgoing

   652 transactions there are. In our example there are one for each.

   653 Line 5 specifies a lock time for when the transaction is

   654 supposed to become active---this is usually set to 0 to become

   655 active immediately. Line 6 specifies the size of the message;

   656 it has nothing to do with the Bitcoins that are transferred.

   657 Lines 7 to 11 specify where the Bitcoins in the transaction

   658 are coming from. The has in line 9 specifies the incoming

   659 transaction and the \pcode{n} in Line 10 specifies which

   660 output of the transaction is referred to. The signature in

   661 line 11 specifies the address (public key $K^{pub}$) from

   662 where the Bitcoins are taken and the digital signature of the

   663 address, that is $\{K^{pub}\}_{K^{priv}}$. Lines 12 to 15

   664 specify the value of the first outgoing transaction. In this

   665 case 0.319 Bitcoins. The hash in Line 14 specifies the address

   666 to where the Bitcoins are transferred.

   189 \begin{center}

   668 As can be seen there is no need to issue serial numbers for

   190 \includegraphics[scale=0.16]{../pics/verizon.png}

   669 transactions, the hash of the transaction data can do this

   191 \end{center}

   670 job. The hash will contain the sender addresses and

   192 

   671 hash-references to the incoming transactions, as well as the

   193 \noindent How disgusting! Even worse, Verizon is not known for

   672 public key of the incoming transaction. This uniquely

   194 being the cheapest ISP on the planet (completely the

   673 identifies a transaction and the hash is the unique

   195 contrary), and also not known for providing the fastest

   674 fingerprint of it. The in-field also contains the address to

   196 possible speeds, but rather for being among the few ISPs in

   675 which a earlier transaction is made. The digital signature

   197 the US with a quasi-monopolistic ``market distribution''.

   676 ensures everybody can check that the person who makes this

   198 

   677 transaction is in the possession of the private key. Otherwise

   199 

   678 the signature would not match up with the public-key address.

   200 Well, we could go on and on\ldots{}and that has not even

   679 

   201 started us yet with all the naughty things NSA \& Friends are

   680 When mining the blockchain it only needs to be ensured that

   202 up to. Why does privacy actually matter? Nobody, I think, has

   681 the transactions are consistent (all hashes and signatures

   203 a conclusive answer to this question yet. Maybe the following

   682 match up). Then we need to generate the correct previous-block

   204 four notions help with clarifying the overall picture

   683 link and solve the resulting puzzle. Once the block is

   205 somewhat: 

   684 accepted, everybody can check the integrity of the whole

   685 blockchain.

   686 

   687 A word of warning: The point of a lottery is that some people

   688 win. But equally, that most people lose. Mining Bitcoins has

   689 pretty much the same point. According to the article below, a

   690 very large machine (very, very large in terms of June 2014)

   691 could potentially mine \$40 worth of Bitcoins a day, but would

   692 require magnitudes more of electricity costs to do so. 

   693 

   694 \begin{center}

   695 \url{http://bitcoinmagazine.com/13774/government-bans-professor-mining-bitcoin-supercomputer/}

   696 \end{center}

   697 

   698 \noindent Bitcoin mining nowadays is only competitive, or

   699 profitable, if you get the energy for free, or use special

   700 purpose computing devices. 

   701 

   702 This about ``free'' energy can actually hurt you very badly in

   703 unexpected ways. You probably have heard about, or even used,

   704 Amazon's Elastic Compute Cloud (EC2). Essentially, Amazon is

   705 selling computing power that you can use to run your web site,

   706 for example. It is \emph{elastic} in the sense that if you

   707 have a lot of visitors, you pay a lot, if you have only a few,

   708 then it is cheap. In order to bill you, you need to set

   709 up an account with Amazon and receive some secret keys in

   710 order to authenticate you. The clever (but also dangerous) bit

   711 is that you upload the code of your web site to GitHub and

   712 Amazon will pull it from there. You can probably already guess

   713 where this is going: in order to learn about Amazon's API, it

   714 gives out some limited computing power for free. Somebody used

   715 this offer in order to teach himself Ruby on Rails with a

   716 mildly practical website. Unfortunately, he uploaded also his

   717 secret keys to GitHub (this is really an easy mistake). Now,

   718 nasty people crawl GitHub for the purpose of stealing such

   719 secret keys. What can they do with this? Well, they quickly

   720 max out the limit of computing power with Amazon and mine

   721 Bitcoins (under somebody else's account). Fortunately for this

   722 guy, Amazon was aware of this scam and in a goodwill gesture

   723 refunded him the money the nasty guys incurred over

   724 night with their Bitcoin mining. If you want to read the

   725 complete story, google for ``My \$2375 Amazon EC2 Mistake''.

   726 

   727 \subsubsection*{Multi-Signature Transactions}

   728 

   729 To be explained.

   730 

   731 \subsubsection*{Anonymity with Bitcoins}

   732 

   733 One question one often hears is how anonymous is it actually

   734 to pay with Bitcoins? Paying with paper money used to be a

   735 quite anonymous act (unlike paying with credit cards, for

   736 example). But this has changed nowadays: You cannot come to a

   737 bank anymore with a suitcase full of money and try to open a

   738 bank account. Strict money laundering and taxation laws mean

   739 that not even Swiss banks are prepared to take such money and

   740 open a bank account. That is why Bitcoins are touted as 

   741 filling this niche again of anonymous payments. 

   742 

   743 While Bitcoins are intended to be anonymous, the reality is

   744 slightly different. I fully agree with the statement by

   745 Nielsen from the blog article I referenced at the beginning:

   746 

   747 \begin{quote}\it{}``Many people claim that Bitcoin can be used

   748 anonymously. This claim has led to the formation of

   749 marketplaces such as Silk Road (and various successors), which

   750 specialize in illegal goods. However, the claim that Bitcoin

   751 is anonymous is a myth. The block chain is public, meaning

   752 that it’s possible for anyone to see every Bitcoin transaction

   753 ever. Although Bitcoin addresses aren't immediately associated

   754 to real-world identities, computer scientists have done a

   755 great deal of work figuring out how to de-anonymise

   756 `anonymous' social networks. The block chain is a marvellous

   757 target for these techniques. I will be extremely surprised if

   758 the great majority of Bitcoin users are not identified with

   759 relatively high confidence and ease in the near future.''

   760 \end{quote}

   761 

   762 \noindent The only thing I can add to this is that with the Bitcoin

   763 blockchain we will in the future have even more pleasure hearing

   764 confessions from reputable or not-so-reputable people, like the

   765 infamous ``I did not inhale'' from an US

   766 president.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}} The

   767 whole point of the blockchain is that it public and will always be.

   768 

   769 There are some precautions one can take for boosting anonymity, for

   770 example to use a new public-private key pair for every new

   771 transaction, and to access Bitcoin only through the Tor network. But

   772 the transactions in Bitcoins are designed such that they allow one to

   773 combine incoming transactions. In such cases we know they must have

   774 been made by the single person who knew the corresponding private

   775 keys. So using different public-private keys for each transaction

   776 might not actually make the de-anonymisation task much harder. And the

   777 point about de-ano\-nymising `anonymous' social networks is that the

   778 information is embedded into the structure of the transition

   779 graph. And this cannot be erased with Bitcoins.

   780 

   781 One paper that has fun with spotting transactions made to Silk Road (2.0)

   782 and also to Wikileaks is

   783 

   784 \begin{center}

   785 \url{http://people.csail.mit.edu/spillai/data/papers/bitcoin-transaction-graph-analysis.pdf}

   786 \end{center}

   787 

   788 \noindent

   789 A paper that gathers some statistical data about the blockchain is

   790 

   791 \begin{center}

   792 \url{https://eprint.iacr.org/2012/584.pdf}

   793 \end{center}

   794 

   795 \subsubsection*{Government Meddling}

   796 

   797 Finally, what are the options for a typical Western government to

   798 meddle with Bitcoins? This is of course one feature the proponents of

   799 Bitcoins also tout: namely that there aren't any options. In my

   800 opinion this is far too naive and far from the truth. Let us assume

   801 some law enforcement agencies would not have been able to uncover the

   802 baddies from Silk Road 1.0 and 2.0 (they have done so by uncovering

   803 the Tor network, which is an incredible feat on its own). Would the

   804 government in question have stopped? I do not think so. The next

   805 target would have been Bitcoin.  If I were the government, this is

   806 what I would consider:

   208 \item \textbf{Secrecy} is the mechanism used to limit the

   809 \item The government could compel ``mayor players'' to blacklist

   209       number of principals with access to information (e.g.,

   810   Bitcoins (for example at Bitcoin exchanges, which are usually

   210       cryptography or access controls). For example I better

   811   located somewhere in the vicinity of the government's reach).  This

   211       keep my password secret, otherwise people from the wrong

   812   would impinge on what is called \emph{fungibility} of Bitcoins and

   212       side of the law might impersonate me.

   813   make them much less attractive to baddies. Suddenly their

   213 

   814   ``hard-earned'' Bitcoin money cannot be spent anymore. The attraction

   214 \item \textbf{Confidentiality} is the obligation to protect

   815   of this option is that this blacklisting can be easily done

   215       the secrets of other people or organisations (secrecy

   816   ``whole-sale'' and therefore be really be an attractive target for

   216       for the benefit of an organisation). For example as a

   817   governments \& Co.

   217       staff member at King's I have access to data, even

   818 \item The government could attempt to coerce the developer

   218       private data, I am allowed to use in my work but not

   819       community of the Bitcoin tools. While this might be a

   219       allowed to disclose to anyone else.

   820       bit harder, we know certain governments are ready to

   220 

   821       take such actions (we have seen this with Lavabit, just

   221 \item \textbf{Anonymity} is the ability to leave no evidence of

   822       that the developers there refused to play ball and shut

   222       an activity (e.g., sharing a secret). This is not equal

   823       down their complete operation).

   223         with privacy---anonymity is required in many 

   824 \item The government could also put pressure on mining pools

   224         circumstances, for example for whistle-blowers, 

   825       in order to blacklist transactions from baddies. Or be a

   225         voting, exam marking and so on.

   826       big miner itself. Given the gigantic facilities that

   226 

   827       are built for institutions like the NSA (pictures from

   227 \item \textbf{Privacy} is the ability or right to protect your

   828       the Utah dessert)

   228       personal secrets (secrecy for the benefit of an

   229       individual). For example, in a job interview, I might

   230       not like to disclose that I am pregnant, if I were a

   231       woman, or that I am a father. Lest they might not hire

   232       me. Similarly, I might not like to disclose my location

   233       data, because thieves might break into my house if they

   234       know I am away at work. Privacy is essentially

   235       everything which ``shouldn't be anybody's business''.

   236 

   237 \end{itemize}

   238 

   239 \noindent While this might provide us with some rough

   240 definitions, the problem with privacy is that it is an

   241 extremely fine line what should stay private and what should

   242 not. For example, since I am working in academia, I am every

   243 so often very happy to be a digital exhibitionist: I am very

   244 happy to disclose all `trivia' related to my work on my

   245 personal web-page. This is a kind of bragging that is normal

   246 in academia (at least in the field of CS), even expected if

   247 you look for a job. I am even happy that Google maintains a

   248 profile about all my academic papers and their citations. 

   249 

   250 On the other hand I would be very irritated if anybody I do

   251 not know had a too close look on my private live---it

   252 shouldn't be anybody's business. The reason is that knowledge

   253 about my private life can often be used against me. As mentioned

   254 above, public location data might mean I get robbed. If

   255 supermarkets build a profile of my shopping habits, they will

   256 use it to \emph{their} advantage---surely not to \emph{my}

   257 advantage. Also whatever might be collected about my life will

   258 always be an incomplete, or even misleading, picture. For

   259 example I am pretty sure my creditworthiness score was

   260 temporarily(?) destroyed by not having a regular income in

   261 this country (before coming to King's I worked in Munich for

   262 five years). To correct such incomplete or flawed credit

   263 history data there is, since recently, a law that allows you

   264 to check what information is held about you for determining

   265 your creditworthiness. But this concerns only a very small

   266 part of the data that is held about me/you. Also

   267 what about cases where data is wrong or outdated (but do we

   268 need a right-to be forgotten).

   269 

   270 

   271 To see how private matter can lead really to the wrong

   272 conclusions, take the example of Stephen Hawking: When he was

   273 diagnosed with his disease, he was given a life expectancy of

   274 two years. If employers would know about such problems, would

   275 they have employed Hawking? Now, he is enjoying his 70+

   276 birthday. Clearly personal medical data needs to stay private.

   277 

   278 To cut a long story short, I let you ponder about the two

   279 statements which are often voiced in discussions about privacy:

   280 

   281 \begin{itemize}

   282 \item \textit{``You have zero privacy anyway. Get over 

   283 it.''}\\

   284 \mbox{}\hfill{}{\small{}(by Scott Mcnealy, former CEO of Sun)}

   285 

   286 \item \textit{``If you have nothing to hide, you have nothing 

   287 to fear.''}

   288 \end{itemize}

   289  

   290 \noindent If you like to watch a movie which has this topic as

   291 its main focus I recommend \emph{Gattaca} from

   292 1997.\footnote{\url{http://www.imdb.com/title/tt0119177/}} If

   293 you want to read up on this topic, I can recommend the

   294 following article that appeared in 2011 in the Chronicle of

   295 Higher Education:

   296 

   297 \begin{center} 

   298 \url{http://chronicle.com/article/Why-Privacy-Matters-Even-if/127461/} 

   299 \end{center} 

   300 

   301 \noindent Funnily, or maybe not so funnily, the author of this

   302 article carefully tries to construct an argument that does not

   303 only attack the nothing-to-hide statement in cases where

   304 governments \& co collect people's deepest secrets, or

   305 pictures of people's naked bodies, but an argument that

   306 applies also in cases where governments ``only'' collect data

   307 relevant to, say, preventing terrorism. The fun is of course

   308 that in 2011 we could just not imagine that respected

   309 governments would do such infantile things as intercepting

   310 people's nude photos. Well, since Snowden we know some people

   311 at the NSA did exactly that and then shared such photos among

   312 colleagues as ``fringe benefit''.  

   313 

   314 

   315 \subsubsection*{Re-Identification Attacks} 

   316 

   317 Apart from philosophical musings, there are fortunately also

   318 some real technical problems with privacy. The problem I want

   319 to focus on in this handout is how to safely disclose datasets

   320 containing potentially very private data, say health records.

   321 What can go wrong with such disclosures can be illustrated

   322 with four well-known examples:

   323 

   324 \begin{itemize}

   325 \item In 2006, a then young company called Netflix offered a 1

   326       Mio \$ prize to anybody who could improve their movie

   327       rating algorithm. For this they disclosed a dataset

   328       containing 10\% of all Netflix users at the time

   329       (appr.~500K). They removed names, but included numerical

   330       ratings of movies as well as times when ratings were

   331       uploaded. Though some information was perturbed (i.e.,

   332       slightly modified).

   334       Two researchers had a closer look at this anonymised

   830       \begin{center}

   335       data and compared it with public data available from the

   831       \includegraphics[scale=0.04]{../pics/nsautah1.jpg}

   336       International Movie Database (IMDb). They found that

   832       \hspace{3mm}

   337       98\% of the entries could be re-identified in the

   833       \includegraphics[scale=0.031]{../pics/nsautah2.jpg}

   338       Netflix dataset: either by their ratings or by the dates

   834       \end{center}

   339       the ratings were uploaded. The result was a class-action

   340       suit against Netflix, which was only recently resolved

   341       involving a lot of money.

   342 

   343 \item In the 1990ies, medical datasets were often made public

   344       for research purposes. This was done in anonymised form

   345       with names removed, but birth dates, gender and ZIP-code

   346       were retained. In one case where such data about

   347       hospital visits of state employees in Massachusetts was

   348       made public, the then governor assured the public that

   349       the released dataset protected patient privacy by

   350       deleting identifiers. 

   352       A graduate student could not resist cross-referencing

   836       this would not be such a high bar to jump over. Remember it

   353       public voter data with the released data that still

   837       ``only'' takes to be temporarily in control of 50\%-plus of the

   354       included birth dates, gender and ZIP-code. The result

   838       mining capacity in order to undermine the trust in the

   355       was that she could send the governor his own hospital

   839       system. Given sophisticated stories like Stuxnet (where we still

   356       record. It turns out that birth dates, gender and

   840       do not know the precise details) maybe even such large

   357       ZIP-code uniquely identify 87\% of people in the US.

   841       facilities are not really needed. What happens, for example, if

   358       This work resulted in a number of laws prescribing which

   842       a government starts DoS attacks on existing miners? They have

   359       private data cannot be released in such datasets.

   843       complete control (unfortunately) of all mayor connectivity

   360  

   844       providers, i.e.~ISPs.

   361 \item In 2006, AOL published 20 million Web search queries

   362       collected from 650,000 users (names had been deleted).

   363       This was again done for research purposes. However,

   364       within days an old lady, Thelma Arnold, from Lilburn,

   365       Georgia, (11,596 inhabitants) was identified as user

   366       No.~4417749 in this dataset. It turned out that search

   367       engine queries are deep windows into people's private

   368       lives. 

   369   

   370 \item Genome-Wide Association Studies (GWAS) was a public

   371       database of gene-frequency studies linked to diseases.

   372       It would essentially record that people who have a

   373       disease, say diabetes, have also certain genes. In order

   374       to maintain privacy, the dataset would only include

   375       aggregate information. In case of DNA data this

   376       aggregation was achieved by mixing the DNA of many

   377       individuals (having a disease) into a single solution.

   378       Then this mixture was sequenced and included in the

   379       dataset. The idea was that the aggregate information

   380       would still be helpful to researchers, but would protect

   381       the DNA data of individuals. 

   382        

   383       In 2007 a forensic computer scientist showed that

   384       individuals can still be identified. For this he used

   385       the DNA data from a comparison group (people from the

   386       general public) and ``subtracted'' this data from the

   387       published data. He was left with data that included all

   388       ``special'' DNA-markers of the individuals present in

   389       the original mixture. He essentially deleted the

   390       ``background noise'' in the published data. The problem

   391       with DNA data is that it is of such a high resolution

   392       that even if the mixture contained maybe 100

   393       individuals, you can with current technology detect

   394       whether an individual was included in the mixture or

   395       not.

   397       This result changed completely how DNA data is nowadays

   846       There are estimates that the Bitcoin mining capacity

   398       published for research purposes. After the success of 

   847       outperforms the top 500 supercomputers in the world,

   399       the human-genome project with a very open culture of

   848       combined(!):

   400       exchanging data, it became much more difficult to 

   401       anonymise data so that patient's privacy is preserved.

   402       The public GWAS database was taken offline in 2008.

   404 \end{itemize}

   850       \begin{center}\small

   405 

   851       \url{http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/}

   406 \noindent There are many lessons that can be learned from

   852       \end{center}

   407 these examples. One is that when making datasets public in

   853       

   408 anonymised form, you want to achieve \emph{forward privacy}.

   854       But my gut feeling is that these are too simplistic

   409 This means, no matter what other data that is also available

   855       calculations. In security (and things like Bitcoins) the

   410 or will be released later, the data in the original dataset

   856       world is never just black and white. The point is once

   411 does not compromise an individual's privacy. This principle

   857       the trust is undermined, the Bitcoin system would need

   412 was violated by the availability of ``outside data'' in the

   858       to be evolved to Bitcoins 2.0. But who says that Bitcoin

   413 Netflix and governor of Massachusetts cases. The additional

   859       2.0 will honour the Bitcoins from Version 1.0?

   414 data permitted a re-identification of individuals in the

   860       \end{itemize} 

   415 dataset. In case of GWAS a new technique of re-identification

   861 

   416 compromised the privacy of people in the dataset. The case of

   862 \noindent A government would potentially not really

   417 the AOL dataset shows clearly how incomplete such data can be:

   863 need to follow up with such threads. Just the rumour that it

   418 Although the queries uniquely identified the older lady, she

   864 would, could be enough to get the Bitcoin-house-of-cards to

   419 also looked up diseases that her friends had, which had

   865 tumble. Some governments have already such an ``impressive''

   420 nothing to do with her. Any rational analysis of her query

   866 trackrecord in this area, such a thread would be entirely

   421 data must therefore have concluded, the lady is on her

   867 credible. Because of all this, I would not have too much hope

   422 death bed, while she was actually very much alive and kicking.

   868 that Bitcoins are free from interference by governments \& Co when

   423 

   869 it will stand in their way, despite what everybody else is

   424 In 2016, Yahoo released the so far largest machine learning

   870 saying. To sum up, the technical details behind Bitcoins are

   425 dataset to the research community. It includes approximately

   871 simply cool. But still the entire Bitcoin ecosystem is in my

   426 13.5 TByte of data representing around 100 Billion events from

   872 humble opinion rather fragile. 

   427 anonymized user-news items, collected by recording

   873 

   428 interactions of about 20M users from February 2015 to May

   874 

   429 2015. Yahoo's gracious goal is to promote independent research

   875 \subsubsection*{Isn't there anything good with Bitcoins?}

   430 in the fields of large-scale machine learning and recommender

   876 

   431 systems. It remains to be seen whether this data will really

   877 As you can see, so far my argument was that yes the Bitcoin system is

   432 only be used for that purpose.

   878 based on a lot of very cool technical ideas, but otherwise it is a big

   433 

   879 scam. You might wonder if there is not something good (in terms of

   434 \subsubsection*{Differential Privacy}

   880 valuable for civilisation) in the bitcoin system? I think there is

   435 

   881 actually: diamonds are quite valuable and because of this can be

   436 Differential privacy is one of the few methods that tries to

   882 used as a form of `money'---just remember the song with the line

   437 achieve forward privacy. The basic idea is to add appropriate

   883 `diamonds are forever'.

   438 noise, or errors, to any query of the dataset. The intention

   884 

   439 is to make the result of a query insensitive to individual

   885 The problem with diamonds is that in some places where they are found,

   440 entries in the database. That means the results are

   886 they also fund some stupid wars. You like to set up a usable system

   441 approximately the same no matter if a particular individual is

   887 whereby you can check whether a diamond comes from a reputable source

   442 in the dataset or not. The hope is that the added error does

   888 (not funding any wars) or from a dodgy source. For this you have to

   443 not eliminate the ``signal'' one is looking for in the

   889 know that `clearing houses' for diamonds can engrave with lasers

   444 dataset.

   890 unique numbers inside the diamonds.  These engravings are invisible to

   445 

   891 the naked eye and as far as I remember these numbers cannot be removed,

   446 %\begin{center}

   892 except by destroying the diamond. Even if it can be removes, diamonds

   447 %User\;\;\;\;    

   893 without the number cannot (hopefully) be sold.

   448 %\begin{tabular}{c}

   894 

   449 %tell me $f(x)$ $\Rightarrow$\\

   895 How do bitcoins come into the picture? The idea is called

   450 %$\Leftarrow$ $f(x) + \text{noise}$

   896 \emph{coloured coins}, where you attach some additional information to

   451 %\end{tabular}

   897 some `coins'. In the diamond example the bitcoin transactions are

   452 %\;\;\;\;\begin{tabular}{@{}c}

   898 supposed to act as a certificate where diamonds are from (reputable

   453 %Database\\

   899 sources or not). For this you have to know that you can attach a very

   454 %$x_1, \ldots, x_n$

   900 short custom-made message with each bitcoin transaction. So you would

   455 %\end{tabular}

   901 record the diamond number inside the message.

   456 %\end{center}

   902 

   457 %

   903 Now, you would set the system up so that a trusted entity (which

   458 %\begin{center}

   904 exists in the diamond world) buys with their public key bitcoins (or

   459 %\begin{tabular}{l|l}

   905 smaller amounts).  These trusted entities are essentially the places

   460 %Staff & Salary\\\hline

   906 that also cut the raw diamonds. The idea is whenever you buy a

   461 %$PM$ & \pounds{107}\\

   907 diamond, you like to have also the corresponding bitcoin

   462 %$PF$ & \pounds{102}\\

   908 transaction. If you want to sell the diamond, you make a transaction

   463 %$LM_1$ & \pounds{101}\\

   909 to the new owner. The new owner will ask for this message, because

   464 %$LF_2$ & \pounds{97}\\

   910 otherwise he/she cannot sell it later on.

   465 %$LM_3$ & \pounds{100}\\

   911 

   466 %$LM_4$ & \pounds{99}\\

   912 The advantage is that for each diamond you can trace back that the

   467 %$LF_5$ & \pounds{98}

   913 transaction must have originated from the trusted entity. If yes, your

   468 %\end{tabular}

   914 diamond will be sellable. If you do not have the message, the diamond

   469 %\end{center}

   915 comes from a dodgy source and will (hopefully) not be sellable later

   470 %

   916 on. In this way you skew the incentives such that only legitimate

   471 %

   917 diamond are of value. The bitcoin system just helps with being able to

   472 %\begin{center}

   918 check whether the message originates from the trusted entity or

   473 %\begin{tikzpicture} 

   919 not....you do not have to consult anybody else and pay money for this

   474 %\begin{axis}[symbolic y coords={salary},

   920 consultation. Or in any way reveal your identity by such a consultation

   475 %             ytick=data,

   921 (the police might just keep a particularly close an eye on who contacts

   476 %             height=3cm]

   922 such a clearing house).

   477 %\addplot+[jump mark mid] coordinates

   923 

   478 %{(0,salary)   (0.1,salary) 

   924 Since we hopefully all agree that funding stupid wars is bad, any

   479 % (0.4,salary) (0.5,salary)  

   925 system that can starve funds for such wars must be good. Piggy-bagging 

   480 % (0.8,salary) (0.9,salary)};

   926 on the trust established by the bitcoin system on the public block chain

   481 %\end{axis}

   927 makes such a system realisable. 

   482 %\end{tikzpicture}

   483 %\end{center}

   484 %

   485 %\begin{tikzpicture}[outline/.style={draw=#1,fill=#1!20}]

   486 %  \node [outline=red]            {red box};

   487 %  \node [outline=blue] at (0,-1) {blue box};

   488 %\end{tikzpicture}

   489 

   490 \ldots

   491 

   495 Two cool articles about how somebody obtained via the Freedom

   931 Finally, finally, the article

   496 of Information Law the taxicab dataset of New York and someone

   497 else showed how easy it is to mine for private information: 

   500 \begin{tabular}{p{0.78\textwidth}}

   934 \url{http://www.extremetech.com/extreme/155636-the-bitcoin-network-outperforms-the-top-500-supercomputers-combined}

   501 \url{http://chriswhong.com/open-data/foil_nyc_taxi/}\smallskip\\

   935 \end{center}

   502 \url{http://research.neustar.biz/2014/09/15/riding-with-the-stars-passenger-privacy-in-the-nyc-taxicab-dataset}

   936 

   503 \end{tabular}

   937 \noindent makes an interesting point: If people are willing to

   504 \end{center}

   938 solve meaningless puzzles for hard, cold cash and with this

   505 

   939 achieve rather impressive results, what could we achieve if

   506 \noindent 

   940 the UN, say, would find the money and incentivise people to,

   507 A readable article about how supermarkets mine your shopping

   941 for example, solve protein folding

   508 habits (especially how they prey on new exhausted parents

   942 puzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}}

   509 ;o) appeared in 2012 in the New York Times:

   943 For this there are projects like

   510 

   944 Folding@home.\footnote{\url{http://folding.stanford.edu}} 

   511 \begin{center}

   945 This might help with curing diseases such as Alzheimer or

   512 \url{http://www.nytimes.com/2012/02/19/magazine/shopping-habits.html}

   946 diabetes. The same point is made in the article

   513 \end{center}

   947 

   514 

   948 \begin{center}\small

   515 \noindent An article that analyses privacy and shopping habits 

   949 \url{http://gizmodo.com/the-worlds-most-powerful-computer-network-is-being-was-504503726}

   516 from a more economic point of view is available from:

   950 \end{center}

   517 

   951 

   518 \begin{center}

   952 A definitely interesting and worthy use of Bitcoins has been explored 

   519 \url{http://www.dtc.umn.edu/~odlyzko/doc/privacy.economics.pdf}

   953 in the thesis

   520 \end{center}

   954 

   521 

   955 \begin{center}

   522 \noindent An attempt to untangle the web of current technology

   956 \url{http://enetium.com/resources/Thesis.pdf}

   523 for spying on consumers is published in:

   957 \end{center}

   524 

   958 

   525 \begin{center}

   959 \noindent where the author proposes ways of publishing information

   526 \url{http://cyberlaw.stanford.edu/files/publication/files/trackingsurvey12.pdf}

   960 that is censor-resistant as part of the blockchain. The idea is that

   527 \end{center}

   961 if a government wants to use Bitcoins, it would also have to put up

   528 

   962 with plain-text data that can be included in a transaction.

   529 \noindent An article that sheds light on the paradox that

   963 

   530 people usually worry about privacy invasions of little

   964 Ken Shirrif in his blog at

   531 significance, and overlook the privacy invasion that might

   965 

   532 cause significant damage:

   966 \begin{center}\small

   533 

   967 \url{http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html}

   534 \begin{center}