\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\usetikzlibrary{shapes}

% beamer stuff 

\renewcommand{\slidecaption}{SEN 08, King's College London}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}

\newcommand{\DOWNarrow}[3]{%

\begin{textblock}{0}(#2,#3)%

\onslide<#1>{%

\begin{tikzpicture}%

\node at (0,0) [single arrow, shape border rotate=270, fill=red,text=red]{a};%

\end{tikzpicture}}%

\end{textblock}}

\newcommand{\LEFTarrow}[3]{%

\begin{textblock}{0}(#2,#3)%

\onslide<#1>{%

\begin{tikzpicture}%

\node at (0,0) [single arrow, shape border rotate=180, fill=red,text=red]{a};%

\end{tikzpicture}}%

\end{textblock}}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\

  \LARGE Security Engineering (8)\\[-3mm] 

  \end{tabular}}\bigskip\bigskip\bigskip

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & S1.27 (1st floor Strand Building)\\

  Slides: & KEATS (also homework is there)\\

  \end{tabular}

  \end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% student prticipation

%\begin{frame}

%\frametitle{Bitcoins}

%

%P2P, 21 Mio, $10^-8$, Mt~Gox, value decreased?, anonymity, 

%Silk Road, verification incentive, puzzle, SHA-256, slow 

%transactions, 

%

%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Last Week's Survey}

{\bf About Bitcoins:}

\begin{textblock}{2.5}(11.5,10)

\begin{bubble}[2.5cm]

  \it bitcoins cannot get lost,

  all transactions are recorded

\end{bubble}

\end{textblock}

\begin{textblock}{5}(3.5,4)

\begin{bubble}[5cm]

\it not regulated by any government

\end{bubble}

\end{textblock}

\begin{textblock}{4}(2,9)

\begin{bubble}[4cm]

\it untracable spending of money?

\end{bubble}

\end{textblock}

\begin{textblock}{5.7}(3,13)

\begin{bubble}[5.7cm]

  \it fixed amount of bitcoins in circulation (no inflation)

\end{bubble}

\end{textblock}

\begin{textblock}{5.6}(8,7)

\begin{bubble}[5.6cm]

\it Should one mine for Bitcoins?

\end{bubble}

\end{textblock}

%\begin{textblock}{2}(12,12.5)

%\begin{bubble}[2cm]

%\it mined by GPUs

%\end{bubble}

%\end{textblock}

\begin{textblock}{3}(11,2.3)

\begin{bubble}[3cm]

\it bitcoins are anonymous

\end{bubble}

\end{textblock}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Bitcoins from 10,000m}

\begin{itemize}

\item a crypto ``currency'' by Satoshi Nakamoto (likely a pen name)

\item a digital resource designed to be scarce 

  (max 21 Mio bitcoins---deflationary currency) 

\item mined by solving special puzzles involving hashes

\item transaction history (ledger/blockchain) is P2P distributed (12 GB)

\item three ``mining pools'' produce\\ currently more than 50\% 

  of bitcoins 

\item can be stolen and also lost

\item anonymous?\pause

\item surely a scam/ponzi scheme!

\end{itemize}

\begin{textblock}{7}(11.5,10)

\includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png}

\end{textblock}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Bitcoins}

\begin{itemize}

\item you create a public-private key pair

\item you have a `wallet' which can be

\begin{itemize}

\item electronic (on your computer, passwords)

\item cloud-based (passwords)

\item paper-based

\end{itemize}

and contains only the public-private key

\item Bitcoins can be stolen or lost

\item Mt.~Gox: hacked $\Rightarrow$ insolvent

\item no form of dispute resolution\\ (against current

consumer laws)

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Underlying Ideas}

It establishing trust in a completely 

untrusted environment\medskip

\begin{itemize}

\item public-private key encryption\medskip

\item digital signatures\medskip

\item cryptographic hashing (SHA-256)

\end{itemize}

\begin{center}

If Alice sends you: \bl{$msg, \{msg\}_{K^{priv}_{Alice}}$}

\ldots ?

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{Lets Start with ``Infocoins''}

\begin{center}

\bl{$\{\text{I, Alice, am giving Bob one infocoin.}\}_{K^{priv}_{Alice}}$}

\end{center}\bigskip

\begin{itemize}

\item no-one else could have created that message

\item Alice cannot deny the ``intend'' of sending Bob money\pause\bigskip

\item Q: What is money?\\ 

  A: Well a string like above

  (or later messages like that)

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Double Spend}

\begin{center}

\bl{$\{\text{I, Alice, am giving Bob one infocoin.}\}_{K^{priv}_{Alice}}$}

\end{center}

\begin{itemize}

\item Alice could keep sending Bob this message over and over

      again (did she mean to send 10 ICs?)\bigskip\pause

\item we need to have a serial number

\begin{center}

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

\end{center}\pause\medskip

\item but then we need a trusted source of serial numbers 

  (e.g.~a bank)

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[c]

\frametitle{No Banks Please}

With banks we could implement:\medskip

\begin{itemize}

\item Bob asks the bank whether the infocoin with that serial

      number belongs to Alice and

\item Alice hasn’t already spent this infocoin.\bigskip 

\item If yes, then Bob tells the bank he accepts the infocoin.

\item The bank updates the records (ledger) to show that the infocoin

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

      no longer belongs to Alice.

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Blockchain (Public Ledger)}

The solution for double spend: 

\begin{itemize}

\item make everybody the bank, everybody has the entire

      transaction history --- will be called

      \alert{\bf blockchain}\medskip

\item Bob checks whether the infocoin belongs to Alice and then

      broadcasts the message to everybody else\\[-10mm]\mbox{}

\end{itemize}

\begin{center}

\includegraphics[scale=0.21]{../pics/bitcoin_ledgers.png}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Blockchain (Public Ledger)}

\begin{center}

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

\end{center}

\begin{itemize}

\item each block is hashed and contains a reference to

the earlier block; ``validates'' potentially more than one

transaction

\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Transaction Graph}

\mbox{}\hspace{3cm}older \hspace{3cm} current

\begin{center}

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

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[squeeze]

\frametitle{Double Spend Again}

\begin{bubble}[10cm]

\begin{itemize}

\item I , Alice, am giving Bob one infocoin, with serial

      number 1234567. 

\item I, Alice, am giving \alt<2->{\alert{Alice}}{Charlie} 

      one infocoin with number 1234567.

\end{itemize}

\end{bubble}

How should other people update their blockchain (public

register)?\\[-10mm]\mbox{}\pause

\begin{center}

\hspace{15mm}\includegraphics[scale=0.31]{../pics/bitcoindisagreement.png}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Creating Agreement}

\begin{bubble}[10cm]

Once \alert{enough} people have broadcast that message, 

everyone updates their block chain to show that infocoin 

1234567 now belongs to Bob, and the transaction is accepted.

\end{bubble}\bigskip

\pause

\small

But what if Alice sets up a large number of separate

identities, let’s say a billion, on the Infocoin network. When

Bob asks the network to validate the transaction, Alice’s

puppet identities say ``Yes his transaction is validated'',

while actually the rest network says Alice's transaction 

is OK?

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{!! Proof-of-Work !!}

The idea is counterintuitive and involves a combination of two

ideas:

\begin{bubble}[10cm]

\begin{itemize}

\item to (artificially) make it computationally costly for

      network users to validate transactions, and

\item to reward them for trying to help validate transactions

\end{itemize}

\end{bubble}\pause

\small

this is called mining: whoever validates a transaction will be awarded with

50 bitcoins --- this halves every 210,000 transactions or

roughly every 4 years (currently 25 BC); no new bitcoins after 2140 -- then only 

transaction fees

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Solving Puzzles}

Given a string, say \code{"Hello, world!"}, what is the 

\alert{salt} so the hash starts with a long run of 

zeros?\bigskip

\begin{bubble}[10cm]

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

\;\;\scriptsize\pcode{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\\

\pause

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

\;\;\scriptsize\pcode{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\\

\pause

\ldots\\

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

\;\;\scriptsize\pcode{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

\end{bubble}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Hardness}

If we want the output hash value to begin with 10 zeroes,

say, then we will need, on average, to try $16^{10} \approx

10^{12}$ different salts before we find a suitable nonce. 

Hardness can be controlled by setting a \alert{target} (maximum

number).

\begin{center}

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

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{How to Adjust the Target?}

\begin{itemize}

\item every 2016 blocks the hardness is adjusted\\ (app 2 weeks)

\end{itemize}

\begin{center}

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

\end{center}

\small

\[

\bl{\begin{array}{@{}l@{}}\text{New}\\ \text{Hardness}\end{array} \dn

\begin{array}{@{}l@{}}\text{Old}\\ \text{Hardness}\end{array} 

* \frac{\text{Actual time for the last 2016 blocks}}{2016}}

\]

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Bitcoin Schedule}

\begin{itemize}

\item every 210000 blocks the amount of bitcoins to be 

  mined halves (``reward era'')

\item every 2016 blocks the hardness is adjusted\\ (app 2 weeks)

\end{itemize}

\begin{center}

\begin{tikzpicture}

\begin{axis}[

    xlabel={\footnotesize year},

    ylabel={\footnotesize \% of total bitcoins},

    ylabel style={yshift=0.0em},

    enlargelimits=false,

    xtick={2009,2011,...,2025},

    xmin=2009,

    xmax=2026,

    ymax=105,

    ymin=0,

    ytick={0,20,...,100},

    scaled ticks=false,

    axis lines=left,

    width=9cm,

    height=6cm,

    legend entries={\footnotesize plan,\footnotesize in reality 2\% ahead},  

    legend pos=south east,

    legend cell align=left,  

    y tick label style={font=\footnotesize}, 

    x tick label style={font=\footnotesize,/pgf/number format/1000 sep={}} 

    ]

\addplot

  table {bitcoinestimate.data};

\only<2>{\addplot[red] 

  table {bitcoinactual.data};}

\end{axis}

\end{tikzpicture}

\end{center}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Order of Transactions}

If we don’t have such an ordering at any given moment 

then it may not be clear who owns which Bitcoins.

\begin{center}

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

\end{center}

\small

Say, miner David is lucky and finds a suitable salt

to confirm the transactions. Celebration!\pause \hspace{5mm}??

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}[t]

\frametitle{Forks}

Typically the blockchain will look as follows

\begin{center}

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

\end{center}

\pause