\documentclass{article}\usepackage{../style}\usepackage{../graphics}\usepackage{../langs}\usepackage{../data}%https://crypto.stanford.edu/cs251/%https://programmingblockchain.gitbooks.io/programmingblockchain/content/%% spying self defence%%https://ssd.eff.org/en/module/communicating-others%https://www.theguardian.com/technology/2016/oct/04/yahoo-secret-email-program-nsa-fbi%https://nakedsecurity.sophos.com/2015/11/12/california-collects-owns-and-sells-infants-dna-samples/%http://randomwalker.info/teaching/fall-2012-privacy-technologies/?%https://josephhall.org/papers/NYU-MCC-1303-S2012_privacy_syllabus.pdf%http://www.jetlaw.org/wp-content/uploads/2014/06/Bambauer_Final.pdf%http://www.cs.cmu.edu/~yuxiangw/docs/Differential%20Privacy.pdf%https://www.youtube.com/watch?v=Gx13lgEudtU%https://fpf.org/wp-content/uploads/Differential-Privacy-as-a-Response-to-the-Reidentification-Threat-Klinefelter-and-Chin.pdf%http://research.neustar.biz/2014/09/08/differential-privacy-the-basics/% hard forks% https://github.com/bitcoin/bips/blob/master/bip-0050.mediawiki% only 25% needed to obtain larger shares of mining% http://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf% re-identification attacks% https://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf% bit-coin papers% https://crypto.stanford.edu/cs251/syllabus.html% bit coin talk --- at 20:00 mins%https://www.usenix.org/conference/lisa16/conference-program/presentation/perlman% In fact, far from freeing people from the oppression of the state,% blockchains perversely promise the perfect tool for a fully% auditable, tax compliant, cashless society. Similarly, the belief it% is an anonymous digital cash has quickly vanished and we are now% seeing a large number of analytics companies, set-up specifically to% work with law enforcement agencies, to police this new parallel% financial system.%% But today blockchain is riddled with% contradictions and misunderstandings. Most of its problems are very% fixable, if you want to fix them% history of bitcoins% https://futurism.com/images/this-week-in-tech-jan-15-22-2016/\begin{document}\fnote{\copyright{} Christian Urban, 2014, 2015}\section*{Handout 7 (Bitcoins)}In my opinion Bitcoins are an elaborate Ponzischeme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---stillthe ideas behind them are really beautiful and not toodifficult to understand. Since many colourful claims aboutBitcoins float around in the mainstream and not-so-mainstreammedia, it will be instructive to re-examine such claims from amore technically informed vantage point. For example, it isoften claimed that Bitcoins are anonymous and free from anypotential government meddling. It turns out that the firstclaim ignores a lot of research in de-anonymising socialnetworks, and the second underestimates the persuasive means agovernment has at its disposal. There are a lot of articles, blogposts, research papersetc.~available about Bitcoins. Below I will follow closely thevery readable explanations from\begin{center}\url{http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/} \;\;and\smallskip\\\url{http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html}\end{center}\noindent The latter also contains a link to a nice youtubevideo about the technical details behind Bitcoins. I willalso use some of their pictures.Let us start with the question who invented Bitcoins? Youcould not make up the answer, but we actually do not know whothe inventor is. All we know is that the first paper\begin{center}\url{https://bitcoin.org/bitcoin.pdf}\end{center}\noindent is signed by Satoshi Nakamoto, which however islikely only a pen name. There is a lot of speculation whocould be the inventor, or inventors, but we simply do notknow. This part of Bitcoins is definitely anonymous so far.The paper above is from the end of 2008; the first Bitcointransaction was made in January 2009. The rules in Bitcoin areset up so that there will only ever be 21 Million Bitcoinswith the maximum reached around the year 2140. Currently thereare already 11 Million Bitcoins in `existence'. Contrast thiswith traditional fiat currencies where money can be printedalmost at will. The smallest unit of a Bitcoin is called aSatoshi, which is the $10^{-8}$th part of a Bitcoin. Remembera Penny is the $10^{-2}$th part of a Pound.The two main cryptographic building blocks of Bitcoins arecryptographic hashing functions (SHA-256) and public-privatekeys using the elliptic-curve encryption scheme for digitalsignatures. Hashes are used to generate `fingerprints' of datathat ensure integrity (absence of tampering). Public-privatekeys are used for signatures. For example sending a message,say $msg$, together with the encrypted version\[msg, \{msg\}_{K^{priv}}\]\noindent allows everybody with access to the correspondingpublic key $K^{pub}$ to verify that the message came from theperson who knew the private key. Signatures are used inBitcoins for verifying the addresses where the Bitcoins aresent from. Addresses in Bitcoins are essentially the publickeys. There are $2^{160}$ possible addresses, which is such avast amount that there is not even a check for duplicates, oralready used addresses. If you start with a random number togenerate a public-private key pair it is very unlikely thatyou step on somebody else's shoes. Compare this with theemail-addresses you wanted to register with, sayGmail, but which are always already taken.One major difference between Bitcoins and traditional bankingis that you do not have a place, or few places, that record thebalance on your account. Traditional banking involves acentral ledger which specifies the current balance in eachaccount, for example \begin{center}\begin{tabular}{l|r}account owner & balance\\\hlineAlice & \pounds{10.01}\\Bob & \pounds{4.99}\\Charlie & -\pounds{1.23}\\Eve & \pounds{0.00}\end{tabular}\end{center}\noindent Bitcoins work differently in that there is no suchcentral ledger, but instead a public record of alltransactions ever made. This means spending money correspondsto sending messages of the (oversimplified) form \begin{equation}\{\text{I, Alice, am giving Bob one Bitcoin.}\}_{K^{priv}_{Alice}}\end{equation}\noindent These messages, called transactions, are the onlydata that is ever stored in the Bitcoin system (we will cometo the precise details later on). The transactions areencrypted with Alice's private key so that everybody,including Bob, can use Alice's public key $K^{pub}_{Alice}$ toverify that this message came really from Alice, or moreprecisely from the person who knows $K^{priv}_{Alice}$. The problem with such messages in a distributed system is thatwhat happens if Bob receives 10, say, of these transactions?Did Alice intend to send him 10 Bitcoins, or did the messageget duplicated by for example an attacker re-playing a sniffedmessage? What is needed is a kind of serial number for suchtransactions. This means transaction messages shoul look more like \begin{center}$\{\text{I, Alice, am giving Bob Bitcoin \#1234567.}\}_{K^{priv}_{Alice}}$\end{center}\noindent There are two difficulties, however, that need to besolved with serial numbers. One is who is assigning serialnumbers to Bitcoins and also how can Bob verify that Aliceactually owns this Bitcoin to pay him? In a system with a bankas trusted third-party, Bob could do the following:\begin{itemize}\item Bob asks the bank whether the Bitcoin with that serial number belongs to Alice and Alice hasn't already spent this Bitcoin.\item If yes, then Bob tells the bank he accepts this Bitcoin. The bank updates the records to show that the Bitcoin with that serial number is now in Bob’s possession and no longer belongs to Alice. \end{itemize}\noindent But for this banks would need to be trusted andwould also be an easy target for any government interference,for example. Think of the early days of music sharing wherethe company Napster was the trusted third-party but also the single point of ``failure'' whichwas taken offline by law enforcement. Bitcoins is more like asystem such as BitTorrent without a single central entity thatcan be taken offline.\footnote{There is some Bitcoininfrastructure that is not so immune from being taken offline:for example Bitcoin exchanges, HQs of Bitcoin mining pools,Bitcoin developers and so on.}Bitcoins solve the problem of not being able to rely on a bankby making everybody the ``bank''. Everybody who cares can havethe entire transaction history starting with the firsttransaction made in January 2009. This history of transactionsis called the \emph{blockchain}. Bob, for example, can use hiscopy of the blockchain for determining whether Alice owned theBitcoin he received, and if she did, he transmits the messagethat he owns it now to every other participant on the Bitcoinnetwork. An illustration of a three-block segment of theblockchain is (simplified) as follows\begin{equation}\includegraphics[scale=0.4]{../pics/bitcoinblockchain0.png}\label{segment}\end{equation}\noindent The chain grows with time. Each block contains alist of individual transactions, written txn in the pictureabove, and also a reference to the previous block, writtenprev. The data in a block (txn's and prev) is hashed so thatthe reference and transactions in them cannot be tamperedwith. This hash is also the unique serial number of eachblock. Since this previous-block-reference is also part of thehash, the whole chain is robust against tampering. I let youthink why this is the case?\ldots{}But does it actuallyeliminate all possibilities of fraud?We can check the consistency of the blockchain by checkingwhether all the references and hashes are correctly recorded.I have not tried it myself, but it is said that with thecurrent amount of data (appr.~12GB) it takes roughly a day tocheck the consistency of the blockchain on a normal computer.Fortunately this ``extended'' consistency check usually onlyneeds to be done once. Afterwards the blockchain only needs tobe updated consistently.Recall I wrote earlier that Bitcoins do not maintain a ledger,which lists all the current balances in each account. Insteadonly transactions are recorded. While a current balance of anaccount is not immediately available, it is possible toextract from the blockchain a transaction graph that lookslike the picture shown in Figure~\ref{txngraph}. Eachrectangle represents a single transaction. Take for examplethe rightmost lower transaction from Charles to Emily. Thistransaction has as receiver the address of Emily and as thesender the address of Charles. In this way no Bitcoins canappear out of thin air (we will discuss later how Bitcoins areactually generated). If Charles did not have a transaction ofat least the amount he wants to give Emily to his name(i.e.~send to an address with his public-private key) thenthere is no way he can make a payment to Emily. Equally, ifnow Emily wants to pay for a coffee, say, with the Bitcoin shereceived from Charles she can essentially only forward themessage she received. The only slight complication with thissetup in Bitcoins is that ``incoming'' Bitcoins can becombined in a transaction and ``outgoing'' Bitcoins can besplit. For example in the leftmost upper transactions inFigure~\ref{txngraph}, Fred makes a payment to Alice. But thispayment (or transaction) combines the Bitcoins that were sendby Jane to Fred and also by Juan to Fred. This allows you to``consolidate'' your funds: if it were only possible to splittransactions, then the amounts would get smaller and smaller. In Bitcoins you have the ability to both combine incomingtransactions, but also to split outgoing transactions topotentially more than one receiver. The latter is also needed.Consider again the rightmost transactions inFigure~\ref{txngraph} and suppose Alice is a coffeeshop ownerselling coffees for 1 Bitcoin. Charles received a transactionfrom Zack over 5 Bitcoins, say. How does Charles pay for thecoffee? There is no explicit notion of \emph{change} in theBitcoin system. What Charles has to do instead is to make onesingle transaction with 1 Bitcoin to Alice and with 4 Bitcoinsgoing back to himself, which then Charles can use to give toEmily, for example.\begin{figure}[t]\begin{center}\includegraphics[scale=0.4]{../pics/blockchain.png}\end{center}\caption{Transaction graph that is implicitly recorded in thepublic blockchain.\label{txngraph}}\end{figure}Let us consider another example. Suppose Emily received 4Bitcoins from Charles and independently received anothertransaction (not shown in the picture) that sends 6 Bitcoinsto her. If she now wants to buy a coffee from Alice for 1Bitcoin, she has two possibilities: She could just forward thetransaction from Charles over 4 Bitcoins to Alice split insuch a way that Alice receives 1 Bitcoin and Emily sends theremaining 3 Bitcoins back to herself. In this case she wouldnow be in the possession of two unspend Bitcoin transactions,one over 3 Bitcoins and the independent one over 6 Bitcoins.Or, Emily could combine both transactions (one over 4 Bitcoinsfrom Charles and the independent one over 6 Bitcoins) and thensplit this amount with 1 Bitcoin going to Alice and 9 Bitcoinsgoing back to herself. I think this is a good time for you to pause to let thisconcept of transactions to really sink in\ldots{}You shouldcome to the conclusion that there is really no need for a central ledger and noneed for an account balance as familiar from traditionalbanking. The closest what Bitcoin has to offer for the notionof a balance in a bank account are the unspend transactionsthat a person (more precisely a public-private key address)received. That means transactions that can still be forwarded. After the pause also consider the fact that whatevertransaction is recorded in the blockchain will be in the``historical record'' for the Bitcoin system. If a transactionsays 1 Bitcoin goes from address $A$ to address $B$, then thisis what will be---$B$ has then the possibility to spend thecorresponding Bitcoins, whether the transaction was donefraudulently or not. There is no exception to this rule.Interestingly this is also how Bitcoins can get lost: Onepossibility is that you send Bitcoins to an address for whichnobody has generated a private key, for example because of atypo in the address field---bad luck for fatfingers\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}in the Bitcoin system. The reason is that nobody has a privatekey for this erroneous address and consequently cannot forwardthe transaction anymore. Another possibility is that youforget your private key and you had messages forwarded to thecorresponding public key. Also in this case bad luck: you willnever be able to forward this message again, because you willnot be able to form a valid message that sends this tosomebody else (we will see the details of this later). Butthis is also a way how you can get robbed of your Bitcoins. Byold-fashioned hacking-into-a-computer crime, for example, anattacker might get hold of your private key and then quicklyforwards the Bitcoins that are in your name to an address theattacker controls. You will never again have access to theseBitcoins, because for the Bitcoin system they are assumed tobe spent. And remember with Bitcoins you cannot appeal to anyhigher authority. Once the Bitcoins are gone, they are gone.This is much different in traditional banking where at leastyou can try to harass the bank to roll back the transaction. This brings us to back to problem of double spend. Suppose Bobis a merchant. How can he make sure that Alice does not cheathim? She could for example send a transaction to Bob. But alsoforward the ``same'' transaction to Charlie, or even herself.If Alice manages to get the second transaction into theblockchain, Bob will be cheated out of his money. The problemin such conflicting situations is how should the networkupdate their blockchain? You might end up with a picture likethis\begin{center}\includegraphics[scale=0.4]{../pics/bitcoindisagreement.png}\end{center}\noindent where Alice convinced some part of the ``world''that she is still the owner of the Bitcoin and some other partof the ``world'' thinks it's Bob's. How should such adisagreement be resolved? This is actually the main hurdlewhere Bitcoin really innovated. The answer is that Bob needsto convince ``enough'' people on the network that thetransaction from Alice to him is legit. What does, however, ``enough'' mean in a distributed system?If Alice sets up a network of a billion, say, puppy identitiesand whenever Bob tries to convince, or validate, that he isthe rightful owner of the Bitcoin, then the puppy identitiesagree. Bob would then have no reason to not give Alice hercoffee. But behind his back she has convinced everybody elseon the network that she is still the rightful owner of theBitcoin. After being outvoted, Bob would be a tad peeved. The reflex reaction to such a situation would be to make theprocess of validating a transaction as cheap as possible. Theintention is that Bob will easily get enough peers to agree with himthat he is the rightful owner. But such a solution has alwaysthe limitation of Alice setting up an even bigger network ofpuppy identities. The really cool idea of Bitcoin is to gointo the other direction of making the process of transactionvalidation (artificially) as expensive as possible, but rewardpeople for helping with the validation. This is really a noveland counterintuitive idea that makes the whole system ofBitcoins work so beautifully.\subsubsection*{Proof-of-Work Puzzles}In order to make the process of transaction validationdifficult, Bitcoin uses a kind of puzzle. Solving the puzzlesis called \emph{Bitcoin mining}, where whoever solves a puzzlewill be awarded some Bitcoins. At the beginning this was 50Bitcoins, but the rules of Bitcoin are set up such that thisamount halves every 210,000 transactions or so. Currently youwill be awarded 25 Bitcoins for solving a puzzle. Because theamount will halve again and then later again and again, aroundthe year 2140 it will go below the level of 1 Satoshi. In thatevent no new Bitcoins will ever be created again and theamount of Bitcoins stays fixed. There will be still anincentive to help with validating transactions, because thereis the possibility in Bitcoins to offer a transaction fee towhoever solves a puzzle. At the moment this fee is usually setto 0, since the incentive for miners is the 25 Bitcoins thatare currently awarded for solving puzzles. What do the puzzles that miners have to solve look like? Thepuzzles can be illustrated roughly as follows: Given a string,say \code{"Hello, world!"}, what is the salt so that the hashstarts with a long run of zeros? Let us look at a concreteexample. Recall that Bitcoins use the hash-function SHA-256.Suppose we call this hash function \code{h}, then we could trythe salt \code{0} as follows:\begin{quote}\code{h("Hello, world!0") =}\\\mbox{}\quad\footnotesize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\end{quote}\noindent OK this does not have any zeros at all. We could next try the salt \code{1}: \begin{quote}\code{h("Hello, world!1") =}\\\mbox{}\quad\footnotesize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\end{quote}\noindent Again this hash value does not contain any leading zeros. We could now try out every salt until we reach\begin{quote}\code{h("Hello, world!4250") =}\\\mbox{}\quad\footnotesize\pcode{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}\end{quote}\noindent where we have four leading zeros. If four zeros areenough, then the puzzle would be solved with this salt. Thepoint is that we can very quickly check whether a salt solvesa puzzle, but it is hard to find one. Latest research suggestit is an NP-problem. If we want the output hash value to beginwith 10 zeroes, say, then we will, on average, need to try$16^{10} \approx 10^{12}$ different salts before we find asuitable one. In Bitcoins the puzzles are not solved according to how manyleading zeros a hash-value has, but rather whether it is belowa \emph{target}. The hardness of the puzzle can actually becontrolled by changing the target according to the availablecomputational power available. I think the adjustment of thehardness of the problems is done every 2060 blocks(appr.~every two weeks). The aim of the adjustment is that onaverage the Bitcoin network will most likely solve a puzzlewithin 10 Minutes. \begin{center}\includegraphics[scale=0.37]{../pics/blockchainsolving.png}\end{center}\noindent It could be solved quicker, but equally it could take longer, but on average after 10 Minutes somebody on the network will have found a solution. Remember that the puzzles are a kind of proof-of-work thatmake the validation of transactions artificially expensive.Consider the following picture with a blockchain and someunconfirmed transactions. \begin{equation}\includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}\label{unconfirmed}\end{equation}\noindent The puzzle is stated as follows: There are someunconfirmed transactions. Choosing some of them, the miner(i.e.~the person/computer that tries to solve a puzzle) willform a putative block to be added to the blockchain. Thisputative block will contain the transactions and the referenceto the previous block. The serial number of such a block issimply the hash of all the data. The puzzle can then be statedas the ``string'' corresponding to the block and which salt isneeded in order to have the hashed value being below thetarget. Other miners will choose different transactions andtherefore work on a slightly different putative block andpuzzle.The intention of the proof-of-work puzzle is that theblockchain is at every given moment linearly ordered, see thepicture shown in \eqref{unconfirmed}. If we don’t have such alinear ordering at any given moment then it may not be clearwho owns which Bitcoins. Assume a miner David is lucky andfinds a suitable salt to confirm some transactions. Should hecelebrate? Not yet. Typically the blockchain will look asfollows\begin{center}\includegraphics[scale=0.65]{../pics/block_chain1.png}\end{center}\noindent But every so often there will be a fork\begin{center}\includegraphics[scale=0.65]{../pics/block_chain_fork.png}\end{center}\noindent What should be done in this case? Well, the tie isbroken if another block is solved, like so:\begin{center}\includegraphics[scale=0.4]{../pics/bitcoin_blockchain_branches.png}\end{center}\noindent The rule in Bitcoins is: If a fork occurs, people onthe network keep track of all forks (they can see). But at anygiven time, miners only work to extend whichever fork islongest in their copy of the block chain. Why should minerswork on the longest fork? Well their incentive is to mineBitcoins. If somebody else already solved a puzzle, then itmakes more sense to work on a new puzzle and obtain theBitcoins for solving that puzzle, rather than waste efforts ona fork that is shorter and therefore less likely to be``accepted''. Note that whoever solved a puzzle on the``loosing'' fork will actually not get any Bitcoins as reward.Tough luck.\subsubsection*{Alice against the Rest of the World}Let us see how the blockchain and the proof-of-work puzzlesavoid the problem of double spend. If Alice wants to cheatBob, she would need to pull off the following ploy:\begin{center}\includegraphics[scale=0.4]{../pics/bitcoin_blockchain_double_spend.png}\end{center}\noindent Alice makes a transaction to Bob for paying, forexample, for an online order. This transaction is confirmed,or validated, in block 2. Bob ships the goods around block 4.In this moment, Alice needs to get into action and try tovalidate the fraudulent transaction to herself instead. Atthis moment she is in a race against all the computing powerof the ``rest of the world''. Because the incentive of therest of the world is to work on the longest chain, that is theone with the transaction from Alice to Bob:\begin{center}\includegraphics[scale=0.4]{../pics/bitcoin_doublespend_blockchain_race.png}\end{center}\noindent As shown in the picture she has to solve the puzzles2a to 5a one after the other, because the hash of a block isdetermined via the reference by all the data in the previousblock. She might be very lucky to solve one puzzle for a blockbefore the rest of the world, but to be lucky many times isvery unlikely. This principle of having to race against therest of the world avoids the ploy of double spend.In order to raise the bar for Alice even further, merchantsaccepting Bitcoins use the following rule of thumb: Atransaction is ``confirmed'' if \begin{itemize}\item[(1)] it is part of a block in the longest fork, and \item[(2)] at least 5 blocks follow it in the longest fork. In this case we say that the transaction has 6 confirmations. \end{itemize} \noindent A simple calculation shows that this amount ofconfirmations can take up to 1 hour and more. While this seemsexcessively long, from the merchant's point of view it is notthat long at all. For this recall that ordinary creditcardscan have their transactions been rolled-back for 6 months orso. The point however is that the odds for Alice being able tocheat are very low, unless she can muster more than 50\% ofthe world Bitcoin mining capacity. In this case she couldout-race the rest of the world. The point is however thatamassing such an amount of computing power is practicallyimpossible for a single person or even a moderately large group.Connected with the 6-confirmation rule is an interestingphenomenon. On average, it would take several years for atypical computer to solve a proof-of-work puzzle, so anindividual’s chance of ever solving one before the rest of theworld, which typically takes only 10 minutes, is negligiblylow. Therefore many people join groups called \emph{miningpools} that collectively work to solve blocks, and distributerewards based on work contributed. These mining pools actsomewhat like lottery pools among co-workers, except that someof these pools are quite large, and comprise more than 20\% ofall the computers in the network. It is said that BTCC, alarge mining pool, has limited its number of members in orderto not solve more than 6 blocks in a row. Otherwise this wouldundermine the trust in Bitcoins, which is also not in theinterest of BTCC, I guess. Some statistics on mining pools canbe seen at\begin{center}\url{https://blockchain.info/pools}\end{center}\noindent Here is an interesting problem: You are part of a lotterypool, if you chip in some of the money to buy a lottery ticket. Inthis setting it is clear when you are in or outside of the pool. Buthow do you make sure people work hard in a mining pool in order tojustify a fraction of any reward? If evil me had its way, I would justclaim I do work and then sit back and relax. Or even if I do some workfor a mining pool and I happen to find a correct salt, I would keep itsecret and submit it to the bitcoin network on the ``side''. Actually,the idea of mining pools has opened up a full can of interestingproblems.\subsubsection*{Bitcoins for Real}Let us now turn to the nitty gritty details. As a participantin the Bitcoin network you need to generate and store apublic-private key pair. The public key you need to advertisein order to receive payments (transactions). The private keyneeds to be securely stored. For this there seem to be threepossibilities\begin{itemize}\item an electronic wallet on your computer\item a cloud-based storage (offered by some Bitcoin services)\item paper-based\end{itemize}\noindent The first two options of course offer conveniencefor making and receiving transactions. But given the nature ofthe private keys and how much security relies on them (recallif somebody gets hold of it, your Bitcoins are quickly lostforever) I would opt for the third option for anything exceptfor trivial amounts of Bitcoins. As we have seen earlier inthe course, securing a computer system that it can withstand atargeted breakin is still very much an unsolved problem.An interesting fact with Bitcoin keys is that there is nocheck for duplicate addresses. This means when generating apublic-private key, you should really start with a carefullychosen random number such that there is really no chance tostep on somebody's feet in the $2^{160}$ space ofpossibilities. Again if you share an address with somebodyelse, he or she has access to all your unspend transactions.The absence of such a check is easily explained: How would onedo this in a distributed system? The answer you can't. It ispossible to do some sanity check of addresses that are alreadyused in the blockchain, but this is not a fail-proof method.One really has to trust on the enormity of the $2^{160}$space for addresses.Let us now look at the concrete data that is stored in an transaction message:\lstinputlisting[language=Scala]{../slides/msg}\noindent The hash in Line 1 is the hash of all the data thatfollows. It is a kind of serial number for the transaction.Line 2 contains a version number in case there are someincompatible changes to be made. Lines 3 and 4 specify howmany incoming transactions are combined and how many outgoingtransactions there are. In our example there are one for each.Line 5 specifies a lock time for when the transaction issupposed to become active---this is usually set to 0 to becomeactive immediately. Line 6 specifies the size of the message;it has nothing to do with the Bitcoins that are transferred.Lines 7 to 11 specify where the Bitcoins in the transactionare coming from. The has in line 9 specifies the incomingtransaction and the \pcode{n} in Line 10 specifies whichoutput of the transaction is referred to. The signature inline 11 specifies the address (public key $K^{pub}$) fromwhere the Bitcoins are taken and the digital signature of theaddress, that is $\{K^{pub}\}_{K^{priv}}$. Lines 12 to 15specify the value of the first outgoing transaction. In thiscase 0.319 Bitcoins. The hash in Line 14 specifies the addressto where the Bitcoins are transferred.As can be seen there is no need to issue serial numbers fortransactions, the hash of the transaction data can do thisjob. The hash will contain the sender addresses andhash-references to the incoming transactions, as well as thepublic key of the incoming transaction. This uniquelyidentifies a transaction and the hash is the uniquefingerprint of it. The in-field also contains the address towhich a earlier transaction is made. The digital signatureensures everybody can check that the person who makes thistransaction is in the possession of the private key. Otherwisethe signature would not match up with the public-key address.When mining the blockchain it only needs to be ensured thatthe transactions are consistent (all hashes and signaturesmatch up). Then we need to generate the correct previous-blocklink and solve the resulting puzzle. Once the block isaccepted, everybody can check the integrity of the wholeblockchain.A word of warning: The point of a lottery is that some peoplewin. But equally, that most people lose. Mining Bitcoins haspretty much the same point. According to the article below, avery large machine (very, very large in terms of June 2014)could potentially mine \$40 worth of Bitcoins a day, but wouldrequire magnitudes more of electricity costs to do so. \begin{center}\url{http://bitcoinmagazine.com/13774/government-bans-professor-mining-bitcoin-supercomputer/}\end{center}\noindent Bitcoin mining nowadays is only competitive, orprofitable, if you get the energy for free, or use specialpurpose computing devices. This about ``free'' energy can actually hurt you very badly inunexpected ways. You probably have heard about, or even used,Amazon's Elastic Compute Cloud (EC2). Essentially, Amazon isselling computing power that you can use to run your web site,for example. It is \emph{elastic} in the sense that if youhave a lot of visitors, you pay a lot, if you have only a few,then it is cheap. In order to bill you, you need to setup an account with Amazon and receive some secret keys inorder to authenticate you. The clever (but also dangerous) bitis that you upload the code of your web site to GitHub andAmazon will pull it from there. You can probably already guesswhere this is going: in order to learn about Amazon's API, itgives out some limited computing power for free. Somebody usedthis offer in order to teach himself Ruby on Rails with amildly practical website. Unfortunately, he uploaded also hissecret keys to GitHub (this is really an easy mistake). Now,nasty people crawl GitHub for the purpose of stealing suchsecret keys. What can they do with this? Well, they quicklymax out the limit of computing power with Amazon and mineBitcoins (under somebody else's account). Fortunately for thisguy, Amazon was aware of this scam and in a goodwill gesturerefunded him the money the nasty guys incurred overnight with their Bitcoin mining. If you want to read thecomplete story, google for ``My \$2375 Amazon EC2 Mistake''.\subsubsection*{Multi-Signature Transactions}To be explained.\subsubsection*{Anonymity with Bitcoins}One question one often hears is how anonymous is it actuallyto pay with Bitcoins? Paying with paper money used to be aquite anonymous act (unlike paying with credit cards, forexample). But this has changed nowadays: You cannot come to abank anymore with a suitcase full of money and try to open abank account. Strict money laundering and taxation laws meanthat not even Swiss banks are prepared to take such money andopen a bank account. That is why Bitcoins are touted as filling this niche again of anonymous payments. While Bitcoins are intended to be anonymous, the reality isslightly different. I fully agree with the statement byNielsen from the blog article I referenced at the beginning:\begin{quote}\it{}``Many people claim that Bitcoin can be usedanonymously. This claim has led to the formation ofmarketplaces such as Silk Road (and various successors), whichspecialize in illegal goods. However, the claim that Bitcoinis anonymous is a myth. The block chain is public, meaningthat it’s possible for anyone to see every Bitcoin transactionever. Although Bitcoin addresses aren't immediately associatedto real-world identities, computer scientists have done agreat deal of work figuring out how to de-anonymise`anonymous' social networks. The block chain is a marvelloustarget for these techniques. I will be extremely surprised ifthe great majority of Bitcoin users are not identified withrelatively high confidence and ease in the near future.''\end{quote}\noindent The only thing I can add to this is that with the Bitcoinblockchain we will in the future have even more pleasure hearingconfessions from reputable or not-so-reputable people, like theinfamous ``I did not inhale'' from an USpresident.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}} Thewhole point of the blockchain is that it public and will always be.There are some precautions one can take for boosting anonymity, forexample to use a new public-private key pair for every newtransaction, and to access Bitcoin only through the Tor network. Butthe transactions in Bitcoins are designed such that they allow one tocombine incoming transactions. In such cases we know they must havebeen made by the single person who knew the corresponding privatekeys. So using different public-private keys for each transactionmight not actually make the de-anonymisation task much harder. And thepoint about de-ano\-nymising `anonymous' social networks is that theinformation is embedded into the structure of the transitiongraph. And this cannot be erased with Bitcoins.One paper that has fun with spotting transactions made to Silk Road (2.0)and also to Wikileaks is\begin{center}\url{http://people.csail.mit.edu/spillai/data/papers/bitcoin-transaction-graph-analysis.pdf}\end{center}\noindentA paper that gathers some statistical data about the blockchain is\begin{center}\url{https://eprint.iacr.org/2012/584.pdf}\end{center}\subsubsection*{Government Meddling}Finally, what are the options for a typical Western government tomeddle with Bitcoins? This is of course one feature the proponents ofBitcoins also tout: namely that there aren't any options. In myopinion this is far too naive and far from the truth. Let us assumesome law enforcement agencies would not have been able to uncover thebaddies from Silk Road 1.0 and 2.0 (they have done so by uncoveringthe Tor network, which is an incredible feat on its own). Would thegovernment in question have stopped? I do not think so. The nexttarget would have been Bitcoin. If I were the government, this iswhat I would consider:\begin{itemize}\item The government could compel ``mayor players'' to blacklist Bitcoins (for example at Bitcoin exchanges, which are usually located somewhere in the vicinity of the government's reach). This would impinge on what is called \emph{fungibility} of Bitcoins and make them much less attractive to baddies. Suddenly their ``hard-earned'' Bitcoin money cannot be spent anymore. The attraction of this option is that this blacklisting can be easily done ``whole-sale'' and therefore be really be an attractive target for governments \& Co.\item The government could attempt to coerce the developer community of the Bitcoin tools. While this might be a bit harder, we know certain governments are ready to take such actions (we have seen this with Lavabit, just that the developers there refused to play ball and shut down their complete operation).\item The government could also put pressure on mining pools in order to blacklist transactions from baddies. Or be a big miner itself. Given the gigantic facilities that are built for institutions like the NSA (pictures from the Utah dessert) \begin{center} \includegraphics[scale=0.04]{../pics/nsautah1.jpg} \hspace{3mm} \includegraphics[scale=0.031]{../pics/nsautah2.jpg} \end{center} this would not be such a high bar to jump over. Remember it ``only'' takes to be temporarily in control of 50\%-plus of the mining capacity in order to undermine the trust in the system. Given sophisticated stories like Stuxnet (where we still do not know the precise details) maybe even such large facilities are not really needed. What happens, for example, if a government starts DoS attacks on existing miners? They have complete control (unfortunately) of all mayor connectivity providers, i.e.~ISPs. There are estimates that the Bitcoin mining capacity outperforms the top 500 supercomputers in the world, combined(!): \begin{center}\small \url{http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/} \end{center} But my gut feeling is that these are too simplistic calculations. In security (and things like Bitcoins) the world is never just black and white. The point is once the trust is undermined, the Bitcoin system would need to be evolved to Bitcoins 2.0. But who says that Bitcoin 2.0 will honour the Bitcoins from Version 1.0? \end{itemize} \noindent A government would potentially not reallyneed to follow up with such threads. Just the rumour that itwould, could be enough to get the Bitcoin-house-of-cards totumble. Some governments have already such an ``impressive''trackrecord in this area, such a thread would be entirelycredible. Because of all this, I would not have too much hopethat Bitcoins are free from interference by governments \& Co whenit will stand in their way, despite what everybody else issaying. To sum up, the technical details behind Bitcoins aresimply cool. But still the entire Bitcoin ecosystem is in myhumble opinion rather fragile. \subsubsection*{Isn't there anything good with Bitcoins?}As you can see, so far my argument was that yes the Bitcoin system isbased on a lot of very cool technical ideas, but otherwise it is a bigscam. You might wonder if there is not something good (in terms ofvaluable for civilisation) in the bitcoin system? I think there isactually: diamonds are quite valuable and because of this can beused as a form of `money'---just remember the song with the line`diamonds are forever'.The problem with diamonds is that in some places where they are found,they also fund some stupid wars. You like to set up a usable systemwhereby you can check whether a diamond comes from a reputable source(not funding any wars) or from a dodgy source. For this you have toknow that `clearing houses' for diamonds can engrave with lasersunique numbers inside the diamonds. These engravings are invisible tothe naked eye and as far as I remember these numbers cannot be removed,except by destroying the diamond. Even if it can be removes, diamondswithout the number cannot (hopefully) be sold.How do bitcoins come into the picture? The idea is called\emph{coloured coins}, where you attach some additional information tosome `coins'. In the diamond example the bitcoin transactions aresupposed to act as a certificate where diamonds are from (reputablesources or not). For this you have to know that you can attach a veryshort custom-made message with each bitcoin transaction. So you wouldrecord the diamond number inside the message.Now, you would set the system up so that a trusted entity (whichexists in the diamond world) buys with their public key bitcoins (orsmaller amounts). These trusted entities are essentially the placesthat also cut the raw diamonds. The idea is whenever you buy adiamond, you like to have also the corresponding bitcointransaction. If you want to sell the diamond, you make a transactionto the new owner. The new owner will ask for this message, becauseotherwise he/she cannot sell it later on.The advantage is that for each diamond you can trace back that thetransaction must have originated from the trusted entity. If yes, yourdiamond will be sellable. If you do not have the message, the diamondcomes from a dodgy source and will (hopefully) not be sellable lateron. In this way you skew the incentives such that only legitimatediamond are of value. The bitcoin system just helps with being able tocheck whether the message originates from the trusted entity ornot....you do not have to consult anybody else and pay money for thisconsultation. Or in any way reveal your identity by such a consultation(the police might just keep a particularly close an eye on who contactssuch a clearing house).Since we hopefully all agree that funding stupid wars is bad, anysystem that can starve funds for such wars must be good. Piggy-bagging on the trust established by the bitcoin system on the public block chainmakes such a system realisable. \subsubsection*{Further Reading}Finally, finally, the article\begin{center}\small\url{http://www.extremetech.com/extreme/155636-the-bitcoin-network-outperforms-the-top-500-supercomputers-combined}\end{center}\noindent makes an interesting point: If people are willing tosolve meaningless puzzles for hard, cold cash and with thisachieve rather impressive results, what could we achieve ifthe UN, say, would find the money and incentivise people to,for example, solve protein foldingpuzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}}For this there are projects likeFolding@home.\footnote{\url{http://folding.stanford.edu}} This might help with curing diseases such as Alzheimer ordiabetes. The same point is made in the article\begin{center}\small\url{http://gizmodo.com/the-worlds-most-powerful-computer-network-is-being-was-504503726}\end{center}A definitely interesting and worthy use of Bitcoins has been explored in the thesis\begin{center}\url{http://enetium.com/resources/Thesis.pdf}\end{center}\noindent where the author proposes ways of publishing informationthat is censor-resistant as part of the blockchain. The idea is thatif a government wants to use Bitcoins, it would also have to put upwith plain-text data that can be included in a transaction.Ken Shirrif in his blog at\begin{center}\small\url{http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html}\end{center} \noindent writes that every day the electricity consumption of miningfor bitcoins is roughly 15 Mega Watts---the energy consumption of a countrylike Cambodia. He writes:\begin{quote} \it{}``The difficulty of mining a block is astounding. At the current difficulty, the chance of a hash succeeding is a bit less than one in $10^{19}$. Finding a successful hash is harder than finding a particular grain of sand from all the grains of sand on Earth. To find a hash every ten minutes, the Bitcoin hash rate needs to be insanely large. Currently, the miners on the Bitcoin network are doing about 25 million gigahashes per second. That is, every second about 25,000,000,000,000,000 blocks gets hashed. I estimate (very roughly) that the total hardware used for Bitcoin mining cost tens of millions of dollars and uses as much power as the country of Cambodia.''\end{quote} \end{document}bit coinA fistful of bitcoinshttp://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdfhttp://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdfRoss Anderson & Co (no dispute resolution; co-ercion)http://www.cl.cam.ac.uk/~sjm217/papers/fc14evidence.pdfhttp://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.htmlhttp://randomwalker.info/bitcoin/Jeffrey RobinsonBitcon: The Naked Truth about BitcoinThe Bitcoin Backbone Protocol: Analysis and Applicationshttps://eprint.iacr.org/2014/765.pdfBitcoin bookhttp://chimera.labs.oreilly.com/books/1234000001802/ch04.html#public_key_derivation