4 

     4 \usepackage{../langs}

     5 \begin{document}

     5 \usepackage{../data}

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

     6 

     7 %https://crypto.stanford.edu/cs251/

     8 %https://programmingblockchain.gitbooks.io/programmingblockchain/content/

    21 %=====

    23 % hard forks

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

    24 % https://github.com/bitcoin/bips/blob/master/bip-0050.mediawiki

    25 

    26 % only 25% needed to obtain larger shares of mining

    27 % http://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf

    28 

    29 % re-identification attacks

    30 % https://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf

    31 

    32 % bit-coin papers

    33 % https://crypto.stanford.edu/cs251/syllabus.html

    34 

    35 % bit coin talk --- at 20:00 mins

    36 %https://www.usenix.org/conference/lisa16/conference-program/presentation/perlman

    37 

    38 % In fact, far from freeing people from the oppression of the state,

    39 % blockchains perversely promise the perfect tool for a fully

    40 % auditable, tax compliant, cashless society. Similarly, the belief it

    41 % is an anonymous digital cash has quickly vanished and we are now

    42 % seeing a large number of analytics companies, set-up specifically to

    43 % work with law enforcement agencies, to police this new parallel

    44 % financial system.

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

    46 % But today blockchain is riddled with

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

    47 % contradictions and misunderstandings. Most of its problems are very

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

    48 % fixable, if you want to fix them

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

    49 

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

    50 

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

    51 % history of bitcoins

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

    52 % https://futurism.com/images/this-week-in-tech-jan-15-22-2016/

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

    53 

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

    54 \begin{document}

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

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

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

    56 

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

    57 \section*{Handout 7 (Bitcoins)}

    36 %outside observers from differentiating between people sending messages,

    58 

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

    59 In my opinion Bitcoins are an elaborate Ponzi

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

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

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

    61 the ideas behind them are really beautiful and not too

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

    62 difficult to understand. Since many colourful claims about

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

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

    42 %increased message latency," Lazar notes.

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

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

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

    44 

    66 often claimed that Bitcoins are anonymous and free from any

    45 %%%%

    67 potential government meddling. It turns out that the first

    46 %% canvas tracking

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

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

    69 networks, and the second underestimates the persuasive means a

    48 

    70 government has at its disposal. 

    49 %%%

    71 

    50 %% cupit re-identification attack

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

    51 %% 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

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

    52 

    74 very readable explanations from

    53 %Differential privacy

    75 

    54 %=====================

    76 \begin{center}

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

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

    56 

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

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

    79 \end{center}

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

    80 

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

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

    60 %individual in it.

    82 video about the technical details behind Bitcoins. I will

    61 

    83 also use some of their pictures.

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

    84 

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

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

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

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

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

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

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

    88 

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

    89 \begin{center}

    68 %names and other identifying details and publishing only their

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

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

    91 \end{center}

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

    92 

    71 %similar patterns of recommendations between the sites and add

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

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

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

    73 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   102 with traditional fiat currencies where money can be printed

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

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

    82 %protected from punishment if they admitted to lawbreaking.

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

    83 

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

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

   106 

    85 

   107 The two main cryptographic building blocks of Bitcoins are

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

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

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

   109 keys using the elliptic-curve encryption scheme for digital

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

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

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

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

    90 %programs you run and for how long.

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

    91 

   113 say $msg$, together with the encrypted version

    92 % Businesses are already using customised pricing online based on

   114 

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

   115 \[

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

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

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

   117 \]

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

   118 

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

   119 \noindent allows everybody with access to the corresponding

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

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

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

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

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

   122 Bitcoins for verifying the addresses where the Bitcoins are

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

   123 sent from. Addresses in Bitcoins are essentially the public

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

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

   103 % general merchandise websites and five out of five travel

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

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

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

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

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

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

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

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

   129 email-addresses you wanted to register with, say

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

   130 Gmail, but which are always already taken.

   109 

   131 

   110 

   132 One major difference between Bitcoins and traditional banking

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

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

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

   134 balance on your account. Traditional banking involves a

   113 

   135 central ledger which specifies the current balance in each

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

   136 account, for example 

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

   137 

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

   138 \begin{center}

   117 

   139 \begin{tabular}{l|r}

   118 \section*{Handout 6 (Privacy)}

   140 account owner & balance\\\hline

   119 

   141 Alice   & \pounds{10.01}\\

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

   142 Bob     & \pounds{4.99}\\

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

   143 Charlie & -\pounds{1.23}\\

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

   144 Eve     & \pounds{0.00}

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

   145 \end{tabular}

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

   146 \end{center}

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

   147 

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

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

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

   149 central ledger, but instead a public record of all

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

   150 transactions ever made. This means spending money corresponds

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

   151 to sending messages of the (oversimplified) form 

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

   152 

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

   153 \begin{equation}

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

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

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

   155 \end{equation}

   134 West---lawless and mythical.

   156 

   135 

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

   136 We would have hoped that after Snowden, Western governments

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

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

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

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

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

   139 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

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

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

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

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

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

   142 parliament: 

   164 

   143 

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

   144 \begin{quote}\it 

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

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

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

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

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

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

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

   148 implemented most of its recommendations by executive order;

   170 transactions. This means transaction messages shoul look more like 

   149 the judiciary made changes to the procedures of the FISA

   171 

   150 Court; and Congress failed to renew the data retention

   172 \begin{center}

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

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

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

   174 \end{center}

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

   175 

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

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

   155 yet again.''

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

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

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

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

   181 

   182 \begin{itemize}

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

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

   185       this Bitcoin.

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

   187       The bank updates the records to show that the Bitcoin

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

   189       no longer belongs to Alice. 

   190 \end{itemize}

   191 

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

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

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

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

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

   197 system such as BitTorrent without a single central entity that

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

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

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

   201 Bitcoin developers and so on.}

   202 

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

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

   205 the entire transaction history starting with the first

   206 transaction made in January 2009. This history of transactions

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

   208 copy of the blockchain for determining whether Alice owned the

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

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

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

   212 blockchain is (simplified) as follows

   213 

   214 \begin{equation}

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

   216 \label{segment}

   217 \end{equation}

   218 

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

   220 list of individual transactions, written txn in the picture

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

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

   223 the reference and transactions in them cannot be tampered

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

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

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

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

   228 eliminate all possibilities of fraud?

   229 

   230 We can check the consistency of the blockchain by checking

   231 whether all the references and hashes are correctly recorded.

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

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

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

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

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

   237 be updated consistently.

   238 

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

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

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

   242 account is not immediately available, it is possible to

   243 extract from the blockchain a transaction graph that looks

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

   245 rectangle represents a single transaction. Take for example

   246 the rightmost lower transaction from Charles to Emily. This

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

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

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

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

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

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

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

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

   255 received from Charles she can essentially only forward the

   256 message she received. The only slight complication with this

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

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

   259 split. For example in the leftmost upper transactions in

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

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

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

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

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

   265 

   266 In Bitcoins you have the ability to both combine incoming

   267 transactions, but also to split outgoing transactions to

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

   269 Consider again the rightmost transactions in

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

   271 selling coffees for 1 Bitcoin. Charles received a transaction

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

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

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

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

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

   277 Emily, for example.

   278 

   279 \begin{figure}[t]

   280 \begin{center}

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

   282 \end{center}

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

   284 public blockchain.\label{txngraph}}

   285 \end{figure}

   286 

   287 Let us consider another example. Suppose Emily received 4

   288 Bitcoins from Charles and independently received another

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

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

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

   292 transaction from Charles over 4 Bitcoins to Alice split in

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

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

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

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

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

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

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

   300 going back to herself. 

   301 

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

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

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

   305 need for an account balance as familiar from traditional

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

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

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

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

   310 

   311 After the pause also consider the fact that whatever

   312 transaction is recorded in the blockchain will be in the

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

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

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

   316 corresponding Bitcoins, whether the transaction was done

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

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

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

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

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

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

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

   324 key for this erroneous address and consequently cannot forward

   325 the transaction anymore. Another possibility is that you

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

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

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

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

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

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

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

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

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

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

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

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

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

   339 This is much different in traditional banking where at least

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

   341 

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

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

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

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

   346 If Alice manages to get the second transaction into the

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

   348 in such conflicting situations is how should the network

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

   350 this

   351 

   352 \begin{center}

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

   354 \end{center}

   355 

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

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

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

   359 disagreement be resolved? This is actually the main hurdle

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

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

   362 transaction from Alice to him is legit. 

   363 

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

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

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

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

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

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

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

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

   372 

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

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

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

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

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

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

   379 into the other direction of making the process of transaction

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

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

   382 and counterintuitive idea that makes the whole system of

   383 Bitcoins work so beautifully.

   384 

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

   386 

   387 In order to make the process of transaction validation

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

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

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

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

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

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

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

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

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

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

   398 incentive to help with validating transactions, because there

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

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

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

   402 are currently awarded for solving puzzles. 

   403  

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

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

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

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

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

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

   410 the salt \code{0} as follows:

   411 

   412 \begin{quote}

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

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

   158 \noindent Unfortunately, also big organisations besides

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

   159 governments seem to take an unenlightened approach to privacy.

   418 next try the salt \code{1}: 

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

   419 

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

   420 \begin{quote}

   162 happily sells your email addresses to anybody who forks out

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

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

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

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

   423 \end{quote}

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

   424 

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

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

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

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

   168 HE applications has actually very honourable goals

   427 

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

   428 \begin{quote}

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

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

   171 they set up their organisation so that they can also

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

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

   431 \end{quote}

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

   432 

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

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

   175 

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

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

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

   177 or

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

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

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

   179 

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

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

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

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

   440 suitable one. 

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

   441 

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

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

   184 kind of cookie to your

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

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

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

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

   445 controlled by changing the target according to the available

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

   446 computational power available. I think the adjustment of the

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

   447 hardness of the problems is done every 2060 blocks

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

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

   190 this request, that is you.

   449 average the Bitcoin network will most likely solve a puzzle

   450 within 10 Minutes. 

   451 

   452 \begin{center}

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

   454 \end{center}

   455 

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

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

   458 network will have found a solution. 

   459 

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

   461 make the validation of transactions artificially expensive.

   462 Consider the following picture with a blockchain and some

   463 unconfirmed transactions. 

   464 

   465 \begin{equation}

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

   467 \label{unconfirmed}

   468 \end{equation}

   469 

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

   471 unconfirmed transactions. Choosing some of them, the miner

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

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

   474 putative block will contain the transactions and the reference

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

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

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

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

   479 target. Other miners will choose different transactions and

   480 therefore work on a slightly different putative block and

   481 puzzle.

   482 

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

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

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

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

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

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

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

   490 follows

   491 

   492 \begin{center}

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

   494 \end{center}

   495 

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

   497 

   498 \begin{center}

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

   500 \end{center}

   501 

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

   503 broken if another block is solved, like so:

   504 

   505 \begin{center}

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

   507 \end{center}

   508 

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

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

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

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

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

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

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

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

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

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

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

   520 Tough luck.

   521 

   522 

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

   524 

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

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

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

   528 

   529 \begin{center}

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

   531 \end{center}

   532 

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

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

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

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

   537 validate the fraudulent transaction to herself instead. At

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

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

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

   541 one with the transaction from Alice to Bob:

   542 

   543 \begin{center}

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

   545 \end{center}

   546 

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

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

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

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

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

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

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

   554 

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

   556 accepting Bitcoins use the following rule of thumb: A

   557 transaction is ``confirmed'' if 

   558 

   559 \begin{itemize}

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

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

   562            this case we say that the transaction has 6

   563            confirmations. 

   564 \end{itemize} 

   565 

   566 \noindent A simple calculation shows that this amount of

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

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

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

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

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

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

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

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

   575 amassing such an amount of computing power is practically

   576 impossible for a single person or even a moderately large 

   577 group.

   578 

   579 Connected with the 6-confirmation rule is an interesting

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

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

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

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

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

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

   586 rewards based on work contributed. These mining pools act

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

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

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

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

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

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

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

   594 be seen at

   595 

   596 \begin{center}

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

   598 \end{center}

   599 

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

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

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

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

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

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

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

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

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

   609 problems.

   610 

   611 

   612 

   613 \subsubsection*{Bitcoins for Real}

   614 

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

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

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

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

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

   620 possibilities

   621 

   622 \begin{itemize}

   623 \item an electronic wallet on your computer

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

   625 \item paper-based

   626 \end{itemize}

   627 

   628 \noindent The first two options of course offer convenience

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

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

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

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

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

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

   635 targeted breakin is still very much an unsolved problem.

   636 

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

   638 check for duplicate addresses. This means when generating a

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

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

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

   642 possibilities. Again if you share an address with somebody

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

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

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

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

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

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

   649 space for addresses.

   650 

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

   652 message:

   653 

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

   655 

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

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

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

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

   660 many incoming transactions are combined and how many outgoing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   675 to where the Bitcoins are transferred.

   192 \begin{center}

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

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

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

   194 \end{center}

   679 job. The hash will contain the sender addresses and

   195 

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

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

   681 public key of the incoming transaction. This uniquely

   197 being the cheapest ISP on the planet (completely the

   682 identifies a transaction and the hash is the unique

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

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

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

   684 which a earlier transaction is made. The digital signature

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

   685 ensures everybody can check that the person who makes this

   201 

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

   202 

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

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

   688 

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

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

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

   690 the transactions are consistent (all hashes and signatures

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

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

   207 four notions help with clarifying the overall picture

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

   208 somewhat: 

   693 accepted, everybody can check the integrity of the whole

   694 blockchain.

   695 

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

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

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

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

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

   701 require magnitudes more of electricity costs to do so. 

   702 

   703 \begin{center}

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

   705 \end{center}

   706 

   707 \noindent Bitcoin mining nowadays is only competitive, or

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

   709 purpose computing devices. 

   710 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   725 mildly practical website. Unfortunately, he uploaded also his

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

   727 nasty people crawl GitHub for the purpose of stealing such

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

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

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

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

   732 refunded him the money the nasty guys incurred over

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

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

   735 

   736 \subsubsection*{Multi-Signature Transactions}

   737 

   738 To be explained.

   739 

   740 \subsubsection*{Anonymity with Bitcoins}

   741 

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

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

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

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

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

   747 bank account. Strict money laundering and taxation laws mean

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

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

   750 filling this niche again of anonymous payments. 

   751 

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

   753 slightly different. I fully agree with the statement by

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

   755 

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

   757 anonymously. This claim has led to the formation of

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

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

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

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

   762 ever. Although Bitcoin addresses aren't immediately associated

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

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

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

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

   767 the great majority of Bitcoin users are not identified with

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

   769 \end{quote}

   770 

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

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

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

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

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

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

   777 

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

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

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

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

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

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

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

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

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

   787 information is embedded into the structure of the transition

   788 graph. And this cannot be erased with Bitcoins.

   789 

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

   791 and also to Wikileaks is

   792 

   793 \begin{center}

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

   795 \end{center}

   796 

   797 \noindent

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

   799 

   800 \begin{center}

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

   802 \end{center}

   803 

   804 \subsubsection*{Government Meddling}

   805 

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

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

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

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

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

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

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

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

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

   815 what I would consider:

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

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

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

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

   213       cryptography or access controls). For example I better

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

   214       keep my password secret, otherwise people from the wrong

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

   215       side of the law might impersonate me.

   822   make them much less attractive to baddies. Suddenly their

   216 

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

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

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

   218       the secrets of other people or organisations (secrecy

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

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

   826   governments \& Co.

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

   827 \item The government could attempt to coerce the developer

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

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

   222       allowed to disclose to anyone else.

   829       bit harder, we know certain governments are ready to

   223 

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

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

   831       that the developers there refused to play ball and shut

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

   832       down their complete operation).

   226         with privacy---anonymity is required in many 

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

   227         circumstances, for example for whistle-blowers, 

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

   228         voting, exam marking and so on.

   835       big miner itself. Given the gigantic facilities that

   229 

   836       are built for institutions like the NSA (pictures from

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

   837       the Utah dessert)

   231       personal secrets (secrecy for the benefit of an

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

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

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

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

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

   237       know I am away at work. Privacy is essentially

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

   239 

   240 \end{itemize}

   241 

   242 \noindent While this might provide us with some rough

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

   244 extremely fine line what should stay private and what should

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

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

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

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

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

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

   251 profile about all my academic papers and their citations. 

   252 

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

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

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

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

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

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

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

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

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

   262 example I am pretty sure my creditworthiness score was

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

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

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

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

   267 to check what information is held about you for determining

   268 your creditworthiness. But this concerns only a very small

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

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

   271 need a right-to be forgotten).

   272 

   273 

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

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

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

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

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

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

   280 

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

   282 statements which are often voiced in discussions about privacy:

   283 

   284 \begin{itemize}

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

   286 it.''}\\

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

   288 

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

   290 to fear.''}

   291 \end{itemize}

   292  

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

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

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

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

   297 following article that appeared in 2011 in the Chronicle of

   298 Higher Education:

   299 

   300 \begin{center} 

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

   302 \end{center} 

   303 

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

   305 article carefully tries to construct an argument that does not

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

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

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

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

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

   311 that in 2011 we could just not imagine that respected

   312 governments would do such infantile things as intercepting

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

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

   315 colleagues as ``fringe benefit''.  

   316 

   317 

   318 \subsubsection*{Re-Identification Attacks} 

   319 

   320 Apart from philosophical musings, there are fortunately also

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

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

   323 containing potentially very private data, say health records.

   324 What can go wrong with such disclosures can be illustrated

   325 with four well-known examples:

   326 

   327 \begin{itemize}

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

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

   330       rating algorithm. For this they disclosed a dataset

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

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

   333       ratings of movies as well as times when ratings were

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

   335       slightly modified).

   337       Two researchers had a closer look at this anonymised

   839       \begin{center}

   338       data and compared it with public data available from the

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

   339       International Movie Database (IMDb). They found that

   841       \hspace{3mm}

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

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

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

   843       \end{center}

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

   343       suit against Netflix, which was only recently resolved

   344       involving a lot of money.

   345 

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

   347       for research purposes. This was done in anonymised form

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

   349       were retained. In one case where such data about

   350       hospital visits of state employees in Massachusetts was

   351       made public, the then governor assured the public that

   352       the released dataset protected patient privacy by

   353       deleting identifiers. 

   355       A graduate student could not resist cross-referencing

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

   356       public voter data with the released data that still

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

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

   847       mining capacity in order to undermine the trust in the

   358       was that she could send the governor his own hospital

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

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

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

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

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

   361       This work resulted in a number of laws prescribing which

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

   362       private data cannot be released in such datasets.

   852       complete control (unfortunately) of all mayor connectivity

   363  

   853       providers, i.e.~ISPs.

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

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

   366       This was again done for research purposes. However,

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

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

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

   370       engine queries are deep windows into people's private

   371       lives. 

   372   

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

   374       database of gene-frequency studies linked to diseases.

   375       It would essentially record that people who have a

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

   377       to maintain privacy, the dataset would only include

   378       aggregate information. In case of DNA data this

   379       aggregation was achieved by mixing the DNA of many

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

   381       Then this mixture was sequenced and included in the

   382       dataset. The idea was that the aggregate information

   383       would still be helpful to researchers, but would protect

   384       the DNA data of individuals. 

   385        

   386       In 2007 a forensic computer scientist showed that

   387       individuals can still be identified. For this he used

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

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

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

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

   392       the original mixture. He essentially deleted the

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

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

   395       that even if the mixture contained maybe 100

   396       individuals, you can with current technology detect

   397       whether an individual was included in the mixture or

   398       not.

   400       This result changed completely how DNA data is nowadays

   855       There are estimates that the Bitcoin mining capacity

   401       published for research purposes. After the success of 

   856       outperforms the top 500 supercomputers in the world,

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

   857       combined(!):

   403       exchanging data, it became much more difficult to 

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

   405       The public GWAS database was taken offline in 2008.

   407 \end{itemize}

   859       \begin{center}\small

   408 

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

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

   861       \end{center}

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

   862       

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

   863       But my gut feeling is that these are too simplistic

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

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

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

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

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

   866       the trust is undermined, the Bitcoin system would need

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

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

   416 Netflix and governor of Massachusetts cases. The additional

   868       2.0 will honour the Bitcoins from Version 1.0?

   417 data permitted a re-identification of individuals in the

   869       \end{itemize} 

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

   870 

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

   871 \noindent A government would potentially not really

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

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

   421 Although the queries uniquely identified the older lady, she

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

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

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

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

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

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

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

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

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

   426 

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

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

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

   428 dataset to the research community. It includes approximately

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

   429 13.5 TByte of data representing around 100 Billion events from

   881 humble opinion rather fragile. 

   430 anonymized user-news items, collected by recording

   882 

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

   883 

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

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

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

   885 

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

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

   435 only be used for that purpose.

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

   436 

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

   437 \subsubsection*{Differential Privacy}

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

   438 

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

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

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

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

   892 `diamonds are forever'.

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

   893 

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

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

   443 entries in the database. That means the results are

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

   444 approximately the same no matter if a particular individual is

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

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

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

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

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

   447 dataset.

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

   448 

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

   449 %\begin{center}

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

   450 %User\;\;\;\;    

   902 without the number cannot (hopefully) be sold.

   451 %\begin{tabular}{c}

   903 

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

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

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

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

   454 %\end{tabular}

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

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

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

   456 %Database\\

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

   457 %$x_1, \ldots, x_n$

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

   458 %\end{tabular}

   910 record the diamond number inside the message.

   459 %\end{center}

   911 

   460 %

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

   461 %\begin{center}

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

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

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

   463 %Staff & Salary\\\hline

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

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

   916 diamond, you like to have also the corresponding bitcoin

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

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

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

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

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

   919 otherwise he/she cannot sell it later on.

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

   920 

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

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

   470 %$LF_5$ & \pounds{98}

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

   471 %\end{tabular}

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

   472 %\end{center}

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

   473 %

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

   474 %

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

   475 %\begin{center}

   927 check whether the message originates from the trusted entity or

   476 %\begin{tikzpicture} 

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

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

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

   478 %             ytick=data,

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

   479 %             height=3cm]

   931 such a clearing house).

   480 %\addplot+[jump mark mid] coordinates

   932 

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

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

   482 % (0.4,salary) (0.5,salary)  

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

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

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

   484 %\end{axis}

   936 makes such a system realisable. 

   485 %\end{tikzpicture}

   486 %\end{center}

   487 %

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

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

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

   491 %\end{tikzpicture}

   492 

   493 \ldots

   494 

   498 Two cool articles about how somebody obtained via the Freedom

   940 Finally, finally, the article

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

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

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

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

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

   944 \end{center}

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

   945 

   506 \end{tabular}

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

   507 \end{center}

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

   508 

   948 achieve rather impressive results, what could we achieve if

   509 \noindent 

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

   510 A readable article about how supermarkets mine your shopping

   950 for example, solve protein folding

   511 habits (especially how they prey on new exhausted parents

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

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

   952 For this there are projects like

   513 

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

   514 \begin{center}

   954 This might help with curing diseases such as Alzheimer or

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

   955 diabetes. The same point is made in the article

   516 \end{center}

   956 

   517 

   957 \begin{center}\small

   518 \noindent An article that analyses privacy and shopping habits 

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

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

   959 \end{center}

   520 

   960 

   521 \begin{center}

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

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

   962 in the thesis

   523 \end{center}

   963 

   524 

   964 \begin{center}

   525 \noindent An attempt to untangle the web of current technology

   965 \url{http://enetium.com/resources/Thesis.pdf}

   526 for spying on consumers is published in:

   966 \end{center}

   527 

   967 

   528 \begin{center}

   968 \noindent where the author proposes ways of publishing information

   529 \url{http://cyberlaw.stanford.edu/files/publication/files/trackingsurvey12.pdf}

   969 that is censor-resistant as part of the blockchain. The idea is that

   530 \end{center}

   970 if a government wants to use Bitcoins, it would also have to put up

   531 

   971 with plain-text data that can be included in a transaction.