\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\\[-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{Recall: Bitcoins}

\begin{itemize}

\item a crypto currency by Satoshi Nakamoto

\item mined by solving special puzzles involving hashes

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

\item surely a scam/ponzi scheme!

\end{itemize}

\begin{textblock}{7}(6.5,8.5)

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

\end{textblock}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Bitcoins for Real}

\begin{itemize}

\item you need a public-private key (the hash of the 

public key to determines your bitcoin address) 

\item if you want to receive bitcoins, you publicise 

this address

\item there are $2^{160}$ possibilities\\ 

(no check for duplicates)\bigskip\pause

\item transactions contain ``payment scripts''

 (non-Turing-complete scripting language)\bigskip

 \small simplest script: pay-to-public-key

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Bitcoin Keys}

\begin{center}

\includegraphics[scale=0.9]{../pics/bitcoin-keys.png}

\end{center}

\begin{itemize}

\item \bl{k} private key: 256 bits (randomly chosen)

\item \bl{K} public key: generated from \bl{k}

\item \bl{A} bitcoin address: 160 Bit/20 Byte number: 

\[\bl{A \dn RIPEMD160(SHA256(K))}\]

\footnotesize RIPEMD160, SHA256 are hash functions

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Bitcoin Addresses}

The ``human readable, checked version'' of \bl{A}:

\begin{center}

\begin{tikzpicture}[scale=1]

  \node (A) at (0,0)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\Large\bl{A}};

  \node (B) at (0,-2)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\Large\bl{A}};

  \node (B2) at (-2,-2)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\large\bl{Prefix}};

  \node (B3) at (-4,-0.5) {1 for P2PKH};      

  \node (C) at (0,-4)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\Large\bl{A}};

  \node at (-2,-4)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\large\bl{Prefix}};

  \node (C2) at (3,-4)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=40mm] 

     {\large\bl{CheckSum}}; 

  \node (D) at (0,-5.8)  [draw=black, rectangle, 

     very thick, minimum height=10mm, minimum width=20mm] 

     {\large\bl{Base58Check(Prefix + A + CheckSum)}};

  \draw[<-, line width=0.5mm] (B2.north west) -- (B3);

  \draw[->, line width=2mm] (A) -- (B);

  \draw[->, line width=2mm] (B) -- (C);

  \draw[->, line width=2mm] (C) -- (D);

  \path[->, line width=2mm] (B.east) edge[bend left] node[right] 

  {\small{}\bl{\begin{tabular}{l}SHA256\\

                             SHA256\\

                             first 4bytes\\[6mm]\end{tabular}}} (C2);

\end{tikzpicture}

\end{center}

\only<2->{

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

\begin{bubble}[10cm]

Example address (Base58):\medskip

\bl{1DSrfJdB2AnWaFNgSbv3MZC2m74996JafV}\bigskip

\mbox{}\hfill\small{}(does not contain 0OlI)

\end{bubble}

\end{textblock}}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Transaction Graph}

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

\begin{center}

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

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Types of Transactions}

\begin{itemize}

\item pay-to-public-key-hash (so far: Alice pays Bob)\pause

\item pay-to-script-hash

\[\bl{RIPEMD160(SHA256(script))}\]\pause

\item Each transaction, including P2PKH, contains a

      \alert{locking} and an \alert{unlocking} script (locking

      from output; unlocking from input).

\item The scripts are written in a Forth-like language (stack

      based).

\item Running both scripts has to evaluate to True.

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Pay-to-Public-Key-Hash}

\begin{itemize}

\item Alice pays Bob:

\begin{center}

\begin{tabular}{ll}

\scode{<Bob's signature>} & {\small(unlocking script from input)}\\

\scode{<Bob's PKey>}\medskip\\

\scode{OP_DUP} & {\small(locking script from output)}\\

\scode{OP_HASH160}\\

\scode{<Bob's PKey Hash>}\\

\scode{OP_EQUALVERIFY}\\

\scode{OP_CHECKSIG}

\end{tabular}

\end{center}

\end{itemize}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{A Transaction Msg}

\small

\lstinputlisting[language=Scala,

                 numbers=none, 

                 xleftmargin=-6mm]{msg}

\only<2->{

\begin{textblock}{2.5}(4.8,2)

\begin{bubble}[8cm]

Question: Sender and receiver are the same; same amount

(no time stamps).\medskip

Can 2 transactions be exactly the same?

\end{bubble}

\end{textblock}}                 

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Pay-to-Script-Hash}

Bob wants to implement a multi-key/signature scheme in his 

company:

\begin{itemize}

\item Bob tells Alice the hash of a locking script:

\item Alice sends the payment to this ``hash address''\bigskip

\item Bob has to supply the locking script matching this hash, 

and the unlocking script\pause\bigskip

\item Bob can use this payment to implement 2-out-of-3 

signature procedures

\end{itemize}

\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{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}}{20160}}

\]

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Hardness}

\begin{itemize}

\item for example block \#277,316 has the hardness 

\[\scode{0x1903a30c}\]

\end{itemize}

where \scode{19} is the exponent and \scode{03a30c} is the 

coefficient.

\[

\bl{target \dn coeffcient * 2^{8 * (exponent - 3)}}

\]

in this example the hash has to be smaller that

\footnotesize

\[

\begin{array}{l}

\scode{0x0000000000000003A30C000000000000}\\

\qquad\qquad\scode{00000000000000000000000000000000}

\end{array}

\]\pause

It is fun to see that nowadays mining equipment is so 

efficient that the hardness is closely related to the 

cost of electricity.

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Bitcoin Schedule}

\begin{itemize}

\item every 210000 blocks the amount of bitcoins to be 

  mined halves (``reward era'')

\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

But every so often there is a fork

\begin{center}

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

\end{center}

\small

\ldots{}bugger this is exactly what we are trying to avoid

\end{frame}

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

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

\begin{frame}[t]

The tie is broken if another block is solved

\begin{center}

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

\end{center}

\small

The rule is: if a fork occurs, people on the network keep

track of all forks. But at any given time, miners only work

to extend whichever fork is longest in their copy of the block

chain.

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Double Spending}

So if Alice wants to fake it, she needs to produce

a longer chain: