# HG changeset patch # User Christian Urban # Date 1418037273 0 # Node ID efad8155513f61bb9b832c5b766275d54767ce77 # Parent 5a6e8b7d20f712f9cac0ee20b0e998a262368409 updated diff -r 5a6e8b7d20f7 -r efad8155513f handouts/ho08.pdf Binary file handouts/ho08.pdf has changed diff -r 5a6e8b7d20f7 -r efad8155513f handouts/ho08.tex --- a/handouts/ho08.tex Mon Dec 08 07:14:28 2014 +0000 +++ b/handouts/ho08.tex Mon Dec 08 11:14:33 2014 +0000 @@ -675,28 +675,27 @@ relatively high confidence and ease in the near future.'' \end{quote} -\noindent The only thing I can add is that with Bitcoins we -will in the future have even more fun hearing confessions from -famous or not-so famous people like the infamous -``I did not -inhale''.\footnote{\url{www.youtube.com/watch?v=Bktd_Pi4YJw}} -The whole point of the blockchain is that it public and will -always be. +\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 ensuring anonymity, like -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. +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 to Silk Road (2.0) -and to Wikileaks is +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} @@ -711,27 +710,27 @@ \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 a government have -stopped? I think no. The next target would have been Bitcoin. -If I were the government, this is what I would consider: +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). - 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 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 @@ -740,7 +739,7 @@ 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 a miner itself. Given the gigantic facilities that + big miner itself. Given the gigantic facilities that are built for institutions like the NSA (pictures from the Utah dessert) @@ -750,16 +749,15 @@ \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\%+ - of the mining capacity in order to undermine the trust - in the system. Given sophisticated stories like Stuxnet - (where we still 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. + 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, @@ -783,7 +781,7 @@ 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 government \& Co when +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 diff -r 5a6e8b7d20f7 -r efad8155513f handouts/ho09.tex --- a/handouts/ho09.tex Mon Dec 08 07:14:28 2014 +0000 +++ b/handouts/ho09.tex Mon Dec 08 11:14:33 2014 +0000 @@ -51,10 +51,10 @@ decidable\ldots{}for example we could always say \emph{don't know}. Of course this would be silly. The point is that we should be striving for a method that answers as often as -possible \emph{yes} or \emph{no}---just in cases when it is -too difficult we fall back on the \emph{don't-know}-answer. -This might sound all like abstract nonsense. Therefore let us -look at a concrete example. +possible either \emph{yes} or \emph{no}---just in cases when +it is too difficult we fall back on the +\emph{don't-know}-answer. This might sound all like abstract +nonsense. Therefore let us look at a concrete example. \subsubsection*{A Simple, Idealised Programming Language} @@ -63,15 +63,19 @@ This language contains variables holding integers. We want to find out what the sign of these integers will be when the program runs. This seems like a very simple problem, but it -will turn out even such a simple analysis is in general -undecidable, just like Turing's halting problem. Is it an -interesting problem? Well, yes---if a compiler can find out -that for example a variable will never be negative and this -variable is used as an index for an array, then the compiler -does not need to generate code for an underflow-test. Remember -some languages are immune to buffer-overflow attacks because -they add bound checks everywhere. This could potentially -drastically speed up the generated code. +will turn out even such a simple analysis if approached +naively is in general undecidable, just like Turing's halting +problem. I let you think why? + + +Is sign-analysis of variables an interesting problem? Well, +yes---if a compiler can find out that for example a variable +will never be negative and this variable is used as an index +for an array, then the compiler does not need to generate code +for an underflow-test. Remember some languages are immune to +buffer-overflow attacks because they add bound checks +everywhere. This could potentially drastically speed up the +generated code. Since we want to