--- a/handouts/ho08.tex Sat Sep 23 19:39:53 2017 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1011 +0,0 @@
-\documentclass{article}
-\usepackage{../style}
-\usepackage{../graphics}
-\usepackage{../langs}
-\usepackage{../data}
-
-%https://crypto.stanford.edu/cs251/
-%https://programmingblockchain.gitbooks.io/programmingblockchain/content/
-
-% bug in smart contracts
-% https://www.benthamsgaze.org/2016/06/17/smart-contracts-beyond-the-age-of-innocence/
-% http://hackingdistributed.com/2016/06/18/analysis-of-the-dao-exploit/
-
-% 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 Ponzi
-scheme\footnote{\url{http://en.wikipedia.org/wiki/Ponzi_scheme}}---still
-the ideas behind them are really beautiful and not too
-difficult to understand. Since many colourful claims about
-Bitcoins float around in the mainstream and not-so-mainstream
-media, it will be instructive to re-examine such claims from a
-more technically informed vantage point. For example, it is
-often claimed that Bitcoins are anonymous and free from any
-potential government meddling. It turns out that the first
-claim ignores a lot of research in de-anonymising social
-networks, and the second underestimates the persuasive means a
-government has at its disposal.
-
-There are a lot of articles, blogposts, research papers
-etc.~available about Bitcoins. Below I will follow closely the
-very 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 youtube
-video about the technical details behind Bitcoins. I will
-also use some of their pictures.
-
-Let us start with the question who invented Bitcoins? You
-could not make up the answer, but we actually do not know who
-the 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 is
-likely only a pen name. There is a lot of speculation who
-could be the inventor, or inventors, but we simply do not
-know. This part of Bitcoins is definitely anonymous so far.
-The paper above is from the end of 2008; the first Bitcoin
-transaction was made in January 2009. The rules in Bitcoin are
-set up so that there will only ever be 21 Million Bitcoins
-with the maximum reached around the year 2140. Currently there
-are already 11 Million Bitcoins in `existence'. Contrast this
-with traditional fiat currencies where money can be printed
-almost at will. The smallest unit of a Bitcoin is called a
-Satoshi, which is the $10^{-8}$th part of a Bitcoin. Remember
-a Penny is the $10^{-2}$th part of a Pound.
-
-The two main cryptographic building blocks of Bitcoins are
-cryptographic hashing functions (SHA-256) and public-private
-keys using the elliptic-curve encryption scheme for digital
-signatures. Hashes are used to generate `fingerprints' of data
-that ensure integrity (absence of tampering). Public-private
-keys 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 corresponding
-public key $K^{pub}$ to verify that the message came from the
-person who knew the private key. Signatures are used in
-Bitcoins for verifying the addresses where the Bitcoins are
-sent from. Addresses in Bitcoins are essentially the public
-keys. There are $2^{160}$ possible addresses, which is such a
-vast amount that there is not even a check for duplicates, or
-already used addresses. If you start with a random number to
-generate a public-private key pair it is very unlikely that
-you step on somebody else's shoes. Compare this with the
-email-addresses you wanted to register with, say
-Gmail, but which are always already taken.
-
-One major difference between Bitcoins and traditional banking
-is that you do not have a place, or few places, that record the
-balance on your account. Traditional banking involves a
-central ledger which specifies the current balance in each
-account, for example
-
-\begin{center}
-\begin{tabular}{l|r}
-account owner & balance\\\hline
-Alice & \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 such
-central ledger, but instead a public record of all
-transactions ever made. This means spending money corresponds
-to 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 only
-data that is ever stored in the Bitcoin system (we will come
-to the precise details later on). The transactions are
-encrypted with Alice's private key so that everybody,
-including Bob, can use Alice's public key $K^{pub}_{Alice}$ to
-verify that this message came really from Alice, or more
-precisely from the person who knows $K^{priv}_{Alice}$.
-
-The problem with such messages in a distributed system is that
-what happens if Bob receives 10, say, of these transactions?
-Did Alice intend to send him 10 Bitcoins, or did the message
-get duplicated by for example an attacker re-playing a sniffed
-message? What is needed is a kind of serial number for such
-transactions. 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 be
-solved with serial numbers. One is who is assigning serial
-numbers to Bitcoins and also how can Bob verify that Alice
-actually owns this Bitcoin to pay him? In a system with a bank
-as 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 and
-would also be an easy target for any government interference,
-for example. Think of the early days of music sharing where
-the company Napster was the trusted third-party but also the single point of ``failure'' which
-was taken offline by law enforcement. Bitcoins is more like a
-system such as BitTorrent without a single central entity that
-can be taken offline.\footnote{There is some Bitcoin
-infrastructure 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 bank
-by making everybody the ``bank''. Everybody who cares can have
-the entire transaction history starting with the first
-transaction made in January 2009. This history of transactions
-is called the \emph{blockchain}. Bob, for example, can use his
-copy of the blockchain for determining whether Alice owned the
-Bitcoin he received, and if she did, he transmits the message
-that he owns it now to every other participant on the Bitcoin
-network. An illustration of a three-block segment of the
-blockchain 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 a
-list of individual transactions, written txn in the picture
-above, and also a reference to the previous block, written
-prev. The data in a block (txn's and prev) is hashed so that
-the reference and transactions in them cannot be tampered
-with. This hash is also the unique serial number of each
-block. Since this previous-block-reference is also part of the
-hash, the whole chain is robust against tampering. I let you
-think why this is the case?\ldots{}But does it actually
-eliminate all possibilities of fraud?
-
-We can check the consistency of the blockchain by checking
-whether all the references and hashes are correctly recorded.
-I have not tried it myself, but it is said that with the
-current amount of data (appr.~12GB) it takes roughly a day to
-check the consistency of the blockchain on a normal computer.
-Fortunately this ``extended'' consistency check usually only
-needs to be done once. Afterwards the blockchain only needs to
-be updated consistently.
-
-Recall I wrote earlier that Bitcoins do not maintain a ledger,
-which lists all the current balances in each account. Instead
-only transactions are recorded. While a current balance of an
-account is not immediately available, it is possible to
-extract from the blockchain a transaction graph that looks
-like the picture shown in Figure~\ref{txngraph}. Each
-rectangle represents a single transaction. Take for example
-the rightmost lower transaction from Charles to Emily. This
-transaction has as receiver the address of Emily and as the
-sender the address of Charles. In this way no Bitcoins can
-appear out of thin air (we will discuss later how Bitcoins are
-actually generated). If Charles did not have a transaction of
-at least the amount he wants to give Emily to his name
-(i.e.~send to an address with his public-private key) then
-there is no way he can make a payment to Emily. Equally, if
-now Emily wants to pay for a coffee, say, with the Bitcoin she
-received from Charles she can essentially only forward the
-message she received. The only slight complication with this
-setup in Bitcoins is that ``incoming'' Bitcoins can be
-combined in a transaction and ``outgoing'' Bitcoins can be
-split. For example in the leftmost upper transactions in
-Figure~\ref{txngraph}, Fred makes a payment to Alice. But this
-payment (or transaction) combines the Bitcoins that were send
-by Jane to Fred and also by Juan to Fred. This allows you to
-``consolidate'' your funds: if it were only possible to split
-transactions, then the amounts would get smaller and smaller.
-
-In Bitcoins you have the ability to both combine incoming
-transactions, but also to split outgoing transactions to
-potentially more than one receiver. The latter is also needed.
-Consider again the rightmost transactions in
-Figure~\ref{txngraph} and suppose Alice is a coffeeshop owner
-selling coffees for 1 Bitcoin. Charles received a transaction
-from Zack over 5 Bitcoins, say. How does Charles pay for the
-coffee? There is no explicit notion of \emph{change} in the
-Bitcoin system. What Charles has to do instead is to make one
-single transaction with 1 Bitcoin to Alice and with 4 Bitcoins
-going back to himself, which then Charles can use to give to
-Emily, for example.
-
-\begin{figure}[t]
-\begin{center}
-\includegraphics[scale=0.4]{../pics/blockchain.png}
-\end{center}
-\caption{Transaction graph that is implicitly recorded in the
-public blockchain.\label{txngraph}}
-\end{figure}
-
-Let us consider another example. Suppose Emily received 4
-Bitcoins from Charles and independently received another
-transaction (not shown in the picture) that sends 6 Bitcoins
-to her. If she now wants to buy a coffee from Alice for 1
-Bitcoin, she has two possibilities: She could just forward the
-transaction from Charles over 4 Bitcoins to Alice split in
-such a way that Alice receives 1 Bitcoin and Emily sends the
-remaining 3 Bitcoins back to herself. In this case she would
-now 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 Bitcoins
-from Charles and the independent one over 6 Bitcoins) and then
-split this amount with 1 Bitcoin going to Alice and 9 Bitcoins
-going back to herself.
-
-I think this is a good time for you to pause to let this
-concept of transactions to really sink in\ldots{}You should
-come to the conclusion that there is really no need for a central ledger and no
-need for an account balance as familiar from traditional
-banking. The closest what Bitcoin has to offer for the notion
-of a balance in a bank account are the unspend transactions
-that 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 whatever
-transaction is recorded in the blockchain will be in the
-``historical record'' for the Bitcoin system. If a transaction
-says 1 Bitcoin goes from address $A$ to address $B$, then this
-is what will be---$B$ has then the possibility to spend the
-corresponding Bitcoins, whether the transaction was done
-fraudulently or not. There is no exception to this rule.
-Interestingly this is also how Bitcoins can get lost: One
-possibility is that you send Bitcoins to an address for which
-nobody has generated a private key, for example because of a
-typo in the address field---bad luck for fat
-fingers\footnote{\url{http://en.wikipedia.org/wiki/Typographical_error}}
-in the Bitcoin system. The reason is that nobody has a private
-key for this erroneous address and consequently cannot forward
-the transaction anymore. Another possibility is that you
-forget your private key and you had messages forwarded to the
-corresponding public key. Also in this case bad luck: you will
-never be able to forward this message again, because you will
-not be able to form a valid message that sends this to
-somebody else (we will see the details of this later). But
-this is also a way how you can get robbed of your Bitcoins. By
-old-fashioned hacking-into-a-computer crime, for example, an
-attacker might get hold of your private key and then quickly
-forwards the Bitcoins that are in your name to an address the
-attacker controls. You will never again have access to these
-Bitcoins, because for the Bitcoin system they are assumed to
-be spent. And remember with Bitcoins you cannot appeal to any
-higher authority. Once the Bitcoins are gone, they are gone.
-This is much different in traditional banking where at least
-you can try to harass the bank to roll back the transaction.
-
-This brings us to back to problem of double spend. Suppose Bob
-is a merchant. How can he make sure that Alice does not cheat
-him? She could for example send a transaction to Bob. But also
-forward the ``same'' transaction to Charlie, or even herself.
-If Alice manages to get the second transaction into the
-blockchain, Bob will be cheated out of his money. The problem
-in such conflicting situations is how should the network
-update their blockchain? You might end up with a picture like
-this
-
-\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 part
-of the ``world'' thinks it's Bob's. How should such a
-disagreement be resolved? This is actually the main hurdle
-where Bitcoin really innovated. The answer is that Bob needs
-to convince ``enough'' people on the network that the
-transaction 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 identities
-and whenever Bob tries to convince, or validate, that he is
-the rightful owner of the Bitcoin, then the puppy identities
-agree. Bob would then have no reason to not give Alice her
-coffee. But behind his back she has convinced everybody else
-on the network that she is still the rightful owner of the
-Bitcoin. After being outvoted, Bob would be a tad peeved.
-
-The reflex reaction to such a situation would be to make the
-process of validating a transaction as cheap as possible. The
-intention is that Bob will easily get enough peers to agree with him
-that he is the rightful owner. But such a solution has always
-the limitation of Alice setting up an even bigger network of
-puppy identities. The really cool idea of Bitcoin is to go
-into the other direction of making the process of transaction
-validation (artificially) as expensive as possible, but reward
-people for helping with the validation. This is really a novel
-and counterintuitive idea that makes the whole system of
-Bitcoins work so beautifully.
-
-\subsubsection*{Proof-of-Work Puzzles}
-
-In order to make the process of transaction validation
-difficult, Bitcoin uses a kind of puzzle. Solving the puzzles
-is called \emph{Bitcoin mining}, where whoever solves a puzzle
-will be awarded some Bitcoins. At the beginning this was 50
-Bitcoins, but the rules of Bitcoin are set up such that this
-amount halves every 210,000 transactions or so. Currently you
-will be awarded 25 Bitcoins for solving a puzzle. Because the
-amount will halve again and then later again and again, around
-the year 2140 it will go below the level of 1 Satoshi. In that
-event no new Bitcoins will ever be created again and the
-amount of Bitcoins stays fixed. There will be still an
-incentive to help with validating transactions, because there
-is the possibility in Bitcoins to offer a transaction fee to
-whoever solves a puzzle. At the moment this fee is usually set
-to 0, since the incentive for miners is the 25 Bitcoins that
-are currently awarded for solving puzzles.
-
-What do the puzzles that miners have to solve look like? The
-puzzles can be illustrated roughly as follows: Given a string,
-say \code{"Hello, world!"}, what is the salt so that the hash
-starts with a long run of zeros? Let us look at a concrete
-example. Recall that Bitcoins use the hash-function SHA-256.
-Suppose we call this hash function \code{h}, then we could try
-the 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 are
-enough, then the puzzle would be solved with this salt. The
-point is that we can very quickly check whether a salt solves
-a puzzle, but it is hard to find one. Latest research suggest
-it is an NP-problem. If we want the output hash value to begin
-with 10 zeroes, say, then we will, on average, need to try
-$16^{10} \approx 10^{12}$ different salts before we find a
-suitable one.
-
-In Bitcoins the puzzles are not solved according to how many
-leading zeros a hash-value has, but rather whether it is below
-a \emph{target}. The hardness of the puzzle can actually be
-controlled by changing the target according to the available
-computational power available. I think the adjustment of the
-hardness of the problems is done every 2060 blocks
-(appr.~every two weeks). The aim of the adjustment is that on
-average the Bitcoin network will most likely solve a puzzle
-within 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 that
-make the validation of transactions artificially expensive.
-Consider the following picture with a blockchain and some
-unconfirmed transactions.
-
-\begin{equation}
-\includegraphics[scale=0.38]{../pics/bitcoin_unconfirmed.png}
-\label{unconfirmed}
-\end{equation}
-
-\noindent The puzzle is stated as follows: There are some
-unconfirmed transactions. Choosing some of them, the miner
-(i.e.~the person/computer that tries to solve a puzzle) will
-form a putative block to be added to the blockchain. This
-putative block will contain the transactions and the reference
-to the previous block. The serial number of such a block is
-simply the hash of all the data. The puzzle can then be stated
-as the ``string'' corresponding to the block and which salt is
-needed in order to have the hashed value being below the
-target. Other miners will choose different transactions and
-therefore work on a slightly different putative block and
-puzzle.
-
-The intention of the proof-of-work puzzle is that the
-blockchain is at every given moment linearly ordered, see the
-picture shown in \eqref{unconfirmed}. If we don’t have such a
-linear ordering at any given moment then it may not be clear
-who owns which Bitcoins. Assume a miner David is lucky and
-finds a suitable salt to confirm some transactions. Should he
-celebrate? Not yet. Typically the blockchain will look as
-follows
-
-\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 is
-broken 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 on
-the network keep track of all forks (they can see). But at any
-given time, miners only work to extend whichever fork is
-longest in their copy of the block chain. Why should miners
-work on the longest fork? Well their incentive is to mine
-Bitcoins. If somebody else already solved a puzzle, then it
-makes more sense to work on a new puzzle and obtain the
-Bitcoins for solving that puzzle, rather than waste efforts on
-a 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 puzzles
-avoid the problem of double spend. If Alice wants to cheat
-Bob, 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, for
-example, 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 to
-validate the fraudulent transaction to herself instead. At
-this moment she is in a race against all the computing power
-of the ``rest of the world''. Because the incentive of the
-rest of the world is to work on the longest chain, that is the
-one 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 puzzles
-2a to 5a one after the other, because the hash of a block is
-determined via the reference by all the data in the previous
-block. She might be very lucky to solve one puzzle for a block
-before the rest of the world, but to be lucky many times is
-very unlikely. This principle of having to race against the
-rest of the world avoids the ploy of double spend.
-
-In order to raise the bar for Alice even further, merchants
-accepting Bitcoins use the following rule of thumb: A
-transaction 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 of
-confirmations can take up to 1 hour and more. While this seems
-excessively long, from the merchant's point of view it is not
-that long at all. For this recall that ordinary creditcards
-can have their transactions been rolled-back for 6 months or
-so. The point however is that the odds for Alice being able to
-cheat are very low, unless she can muster more than 50\% of
-the world Bitcoin mining capacity. In this case she could
-out-race the rest of the world. The point is however that
-amassing such an amount of computing power is practically
-impossible for a single person or even a moderately large
-group.
-
-Connected with the 6-confirmation rule is an interesting
-phenomenon. On average, it would take several years for a
-typical computer to solve a proof-of-work puzzle, so an
-individual’s chance of ever solving one before the rest of the
-world, which typically takes only 10 minutes, is negligibly
-low. Therefore many people join groups called \emph{mining
-pools} that collectively work to solve blocks, and distribute
-rewards based on work contributed. These mining pools act
-somewhat like lottery pools among co-workers, except that some
-of these pools are quite large, and comprise more than 20\% of
-all the computers in the network. It is said that BTCC, a
-large mining pool, has limited its number of members in order
-to not solve more than 6 blocks in a row. Otherwise this would
-undermine the trust in Bitcoins, which is also not in the
-interest of BTCC, I guess. Some statistics on mining pools can
-be seen at
-
-\begin{center}
-\url{https://blockchain.info/pools}
-\end{center}
-
-\noindent Here is an interesting problem: You are part of a lottery
-pool, if you chip in some of the money to buy a lottery ticket. In
-this setting it is clear when you are in or outside of the pool. But
-how do you make sure people work hard in a mining pool in order to
-justify a fraction of any reward? If evil me had its way, I would just
-claim I do work and then sit back and relax. Or even if I do some work
-for a mining pool and I happen to find a correct salt, I would keep it
-secret and submit it to the bitcoin network on the ``side''. Actually,
-the idea of mining pools has opened up a full can of interesting
-problems.
-
-
-
-\subsubsection*{Bitcoins for Real}
-
-Let us now turn to the nitty gritty details. As a participant
-in the Bitcoin network you need to generate and store a
-public-private key pair. The public key you need to advertise
-in order to receive payments (transactions). The private key
-needs to be securely stored. For this there seem to be three
-possibilities
-
-\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 convenience
-for making and receiving transactions. But given the nature of
-the private keys and how much security relies on them (recall
-if somebody gets hold of it, your Bitcoins are quickly lost
-forever) I would opt for the third option for anything except
-for trivial amounts of Bitcoins. As we have seen earlier in
-the course, securing a computer system that it can withstand a
-targeted breakin is still very much an unsolved problem.
-
-An interesting fact with Bitcoin keys is that there is no
-check for duplicate addresses. This means when generating a
-public-private key, you should really start with a carefully
-chosen random number such that there is really no chance to
-step on somebody's feet in the $2^{160}$ space of
-possibilities. Again if you share an address with somebody
-else, he or she has access to all your unspend transactions.
-The absence of such a check is easily explained: How would one
-do this in a distributed system? The answer you can't. It is
-possible to do some sanity check of addresses that are already
-used 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 that
-follows. It is a kind of serial number for the transaction.
-Line 2 contains a version number in case there are some
-incompatible changes to be made. Lines 3 and 4 specify how
-many incoming transactions are combined and how many outgoing
-transactions there are. In our example there are one for each.
-Line 5 specifies a lock time for when the transaction is
-supposed to become active---this is usually set to 0 to become
-active 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 transaction
-are coming from. The has in line 9 specifies the incoming
-transaction and the \pcode{n} in Line 10 specifies which
-output of the transaction is referred to. The signature in
-line 11 specifies the address (public key $K^{pub}$) from
-where the Bitcoins are taken and the digital signature of the
-address, that is $\{K^{pub}\}_{K^{priv}}$. Lines 12 to 15
-specify the value of the first outgoing transaction. In this
-case 0.319 Bitcoins. The hash in Line 14 specifies the address
-to where the Bitcoins are transferred.
-
-As can be seen there is no need to issue serial numbers for
-transactions, the hash of the transaction data can do this
-job. The hash will contain the sender addresses and
-hash-references to the incoming transactions, as well as the
-public key of the incoming transaction. This uniquely
-identifies a transaction and the hash is the unique
-fingerprint of it. The in-field also contains the address to
-which a earlier transaction is made. The digital signature
-ensures everybody can check that the person who makes this
-transaction is in the possession of the private key. Otherwise
-the signature would not match up with the public-key address.
-
-When mining the blockchain it only needs to be ensured that
-the transactions are consistent (all hashes and signatures
-match up). Then we need to generate the correct previous-block
-link and solve the resulting puzzle. Once the block is
-accepted, everybody can check the integrity of the whole
-blockchain.
-
-A word of warning: The point of a lottery is that some people
-win. But equally, that most people lose. Mining Bitcoins has
-pretty much the same point. According to the article below, a
-very large machine (very, very large in terms of June 2014)
-could potentially mine \$40 worth of Bitcoins a day, but would
-require 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, or
-profitable, if you get the energy for free, or use special
-purpose computing devices.
-
-This about ``free'' energy can actually hurt you very badly in
-unexpected ways. You probably have heard about, or even used,
-Amazon's Elastic Compute Cloud (EC2). Essentially, Amazon is
-selling computing power that you can use to run your web site,
-for example. It is \emph{elastic} in the sense that if you
-have 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 set
-up an account with Amazon and receive some secret keys in
-order to authenticate you. The clever (but also dangerous) bit
-is that you upload the code of your web site to GitHub and
-Amazon will pull it from there. You can probably already guess
-where this is going: in order to learn about Amazon's API, it
-gives out some limited computing power for free. Somebody used
-this offer in order to teach himself Ruby on Rails with a
-mildly practical website. Unfortunately, he uploaded also his
-secret keys to GitHub (this is really an easy mistake). Now,
-nasty people crawl GitHub for the purpose of stealing such
-secret keys. What can they do with this? Well, they quickly
-max out the limit of computing power with Amazon and mine
-Bitcoins (under somebody else's account). Fortunately for this
-guy, Amazon was aware of this scam and in a goodwill gesture
-refunded him the money the nasty guys incurred over
-night with their Bitcoin mining. If you want to read the
-complete 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 actually
-to pay with Bitcoins? Paying with paper money used to be a
-quite anonymous act (unlike paying with credit cards, for
-example). But this has changed nowadays: You cannot come to a
-bank anymore with a suitcase full of money and try to open a
-bank account. Strict money laundering and taxation laws mean
-that not even Swiss banks are prepared to take such money and
-open 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 is
-slightly different. I fully agree with the statement by
-Nielsen from the blog article I referenced at the beginning:
-
-\begin{quote}\it{}``Many people claim that Bitcoin can be used
-anonymously. This claim has led to the formation of
-marketplaces such as Silk Road (and various successors), which
-specialize in illegal goods. However, the claim that Bitcoin
-is anonymous is a myth. The block chain is public, meaning
-that it’s possible for anyone to see every Bitcoin transaction
-ever. Although Bitcoin addresses aren't immediately associated
-to real-world identities, computer scientists have done a
-great deal of work figuring out how to de-anonymise
-`anonymous' social networks. The block chain is a marvellous
-target for these techniques. I will be extremely surprised if
-the great majority of Bitcoin users are not identified with
-relatively high confidence and ease in the near future.''
-\end{quote}
-
-\noindent The only thing I can add to this is that with the Bitcoin
-blockchain we will in the future have even more pleasure hearing
-confessions from reputable or not-so-reputable people, like the
-infamous ``I did not inhale'' from an US
-president.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}} The
-whole point of the blockchain is that it public and will always be.
-
-There are some precautions one can take for boosting anonymity, for
-example to use a new public-private key pair for every new
-transaction, and to access Bitcoin only through the Tor network. But
-the transactions in Bitcoins are designed such that they allow one to
-combine incoming transactions. In such cases we know they must have
-been made by the single person who knew the corresponding private
-keys. So using different public-private keys for each transaction
-might not actually make the de-anonymisation task much harder. And the
-point about de-ano\-nymising `anonymous' social networks is that the
-information is embedded into the structure of the transition
-graph. 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}
-
-\noindent
-A 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 to
-meddle with Bitcoins? This is of course one feature the proponents of
-Bitcoins also tout: namely that there aren't any options. In my
-opinion this is far too naive and far from the truth. Let us assume
-some law enforcement agencies would not have been able to uncover the
-baddies from Silk Road 1.0 and 2.0 (they have done so by uncovering
-the Tor network, which is an incredible feat on its own). Would the
-government in question have stopped? I do not think so. The next
-target would have been Bitcoin. If I were the government, this is
-what 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 really
-need to follow up with such threads. Just the rumour that it
-would, could be enough to get the Bitcoin-house-of-cards to
-tumble. Some governments have already such an ``impressive''
-trackrecord in this area, such a thread would be entirely
-credible. Because of all this, I would not have too much hope
-that Bitcoins are free from interference by governments \& Co when
-it will stand in their way, despite what everybody else is
-saying. To sum up, the technical details behind Bitcoins are
-simply cool. But still the entire Bitcoin ecosystem is in my
-humble 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 is
-based on a lot of very cool technical ideas, but otherwise it is a big
-scam. You might wonder if there is not something good (in terms of
-valuable for civilisation) in the bitcoin system? I think there is
-actually: diamonds are quite valuable and because of this can be
-used 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 system
-whereby you can check whether a diamond comes from a reputable source
-(not funding any wars) or from a dodgy source. For this you have to
-know that `clearing houses' for diamonds can engrave with lasers
-unique numbers inside the diamonds. These engravings are invisible to
-the naked eye and as far as I remember these numbers cannot be removed,
-except by destroying the diamond. Even if it can be removes, diamonds
-without 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 to
-some `coins'. In the diamond example the bitcoin transactions are
-supposed to act as a certificate where diamonds are from (reputable
-sources or not). For this you have to know that you can attach a very
-short custom-made message with each bitcoin transaction. So you would
-record the diamond number inside the message.
-
-Now, you would set the system up so that a trusted entity (which
-exists in the diamond world) buys with their public key bitcoins (or
-smaller amounts). These trusted entities are essentially the places
-that also cut the raw diamonds. The idea is whenever you buy a
-diamond, you like to have also the corresponding bitcoin
-transaction. If you want to sell the diamond, you make a transaction
-to the new owner. The new owner will ask for this message, because
-otherwise he/she cannot sell it later on.
-
-The advantage is that for each diamond you can trace back that the
-transaction must have originated from the trusted entity. If yes, your
-diamond will be sellable. If you do not have the message, the diamond
-comes from a dodgy source and will (hopefully) not be sellable later
-on. In this way you skew the incentives such that only legitimate
-diamond are of value. The bitcoin system just helps with being able to
-check whether the message originates from the trusted entity or
-not....you do not have to consult anybody else and pay money for this
-consultation. Or in any way reveal your identity by such a consultation
-(the police might just keep a particularly close an eye on who contacts
-such a clearing house).
-
-Since we hopefully all agree that funding stupid wars is bad, any
-system that can starve funds for such wars must be good. Piggy-bagging
-on the trust established by the bitcoin system on the public block chain
-makes 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 to
-solve meaningless puzzles for hard, cold cash and with this
-achieve rather impressive results, what could we achieve if
-the UN, say, would find the money and incentivise people to,
-for example, solve protein folding
-puzzles?\footnote{\url{http://en.wikipedia.org/wiki/Protein_folding}}
-For this there are projects like
-Folding@home.\footnote{\url{http://folding.stanford.edu}}
-This might help with curing diseases such as Alzheimer or
-diabetes. 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 information
-that is censor-resistant as part of the blockchain. The idea is that
-if a government wants to use Bitcoins, it would also have to put up
-with 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 mining
-for bitcoins is roughly 15 Mega Watts---the energy consumption of a country
-like 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 coin
-
-A fistful of bitcoins
-http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
-http://cseweb.ucsd.edu/~smeiklejohn/files/imc13.pdf
-
-Ross Anderson & Co (no dispute resolution; co-ercion)
-http://www.cl.cam.ac.uk/~sjm217/papers/fc14evidence.pdf
-
-http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/
-http://www.imponderablethings.com/2013/07/how-bitcoin-works-under-hood.html
-
-http://randomwalker.info/bitcoin/
-
-Jeffrey Robinson
-Bitcon: The Naked Truth about Bitcoin
-
-The Bitcoin Backbone Protocol: Analysis and Applications
-https://eprint.iacr.org/2014/765.pdf
-
-Bitcoin book
-http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#public_key_derivation