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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usetikzlibrary{shapes}

% beamer stuff 

\renewcommand{\slidecaption}{APP 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 Access Control and \\[-3mm] 

  \LARGE Privacy Policies (8)\\[-6mm] 

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

  \normalsize

  \begin{center}

  \begin{tabular}{ll}Ch

  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}

\begin{center}

\Huge\bf ?

\end{center}

\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 two ``mining pools'' produce\\ currently more than 50\% 

  of bitcoins 

\item can be stolen and also lost

\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

\begin{itemize}

\item cloud-based (passwords)

\item paper-based

\end{itemize}

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

\end{itemize}

\end{frame}

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

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

\begin{frame}

\frametitle{Underlying Ideas}

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}}$}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\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 forgery possible only after Alice created the string

  (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

\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

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{No Banks Please}

With banks we could implement:

\begin{itemize}

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

      number belongs to Alice and

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

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Blockchain}

The solution for double spend: 

\begin{itemize}

\item make everybody the bank, everybody has the entire

      transaction history --- will be called

      \alert{blockchain}\medskip

\item Bob checks whether infocoin belongs to Alice and then

      broadcasts the message to anybody else 

\end{itemize}

\begin{center}

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

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Blockchain}

\begin{center}

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

\end{center}

\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}[t]

\frametitle{Double Spend Again}

\begin{bubble}[10cm]\addtolength{\leftmargini}{5mm}

\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.

\end{itemize}

\end{bubble}\bigskip

How should other people update their blockchain (public

register)?\pause

\begin{center}

\includegraphics[scale=0.3]{../pics/bitcoindisagreement.png}

\end{center}

Once enough people have broadcast that message, everyone

updates their block chain to show that infocoin 1234567 now

belongs to Bob, and the transaction is complete.

\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\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]

The idea is counterintuitive and involves a combination of two

ideas:\bigskip

\begin{bubble}[10cm]

\addtolength{\leftmargini}{5mm}

\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\bigskip

\small

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

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

transaction fees

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Solving Puzzles}

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

zeros?\bigskip

\begin{bubble}[10cm]

\begin{tabular}{l}

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

\;\;\scriptsize\code{1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64}\\

\pause

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

\;\;\scriptsize\code{e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8}\\

\pause

\ldots\\

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

\;\;\scriptsize\code{0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9}

\end{tabular}

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

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

10 mins

\end{textblock}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Order of Transactions}

\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

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 Again}

a longer chain:

\begin{center}

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

\end{center}

\end{frame}

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

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

\begin{frame}

\begin{columns}

\begin{column}{4.5cm}

\includegraphics[scale=0.3]{../pics/bitcoin_doublespend_blockchain_race.png}

\end{column}

\begin{column}{5.5cm}

\includegraphics[scale=0.3]{../pics/bitcoin_transaction_order_race.png}

\end{column}

\end{columns}\bigskip\bigskip\pause

\small

A transaction is ``confirmed'' if:\smallskip

(1) it is part of a block in the longest fork, and (2) at

least 5 blocks follow it in the longest fork. In this case we

say that the transaction has ``6 confirmations''.\bigskip

\footnotesize (might take 1h+\ldots but for creditcards you have 

6 months chargeback)

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Mining Pools}

\begin{bubble}[10cm]

On average, it would take several years for a typical computer

to solve a block, so an individual’s chance of ever solving

one before the rest of the network, which typically takes 10

\end{bubble}\bigskip\pause

\small

Many people join groups called mining pools that collectively

work to solve blocks, and distribute rewards based on work

contributed. These 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.\medskip

\footnotesize

BTC, the largest mining pool, has limited its members to 

not solve more than 6 blocks in a row.

\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)

\end{itemize}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{A Transaction Msg}

\small

\lstinputlisting[language=Scala,

                 numbersep=3pt, 

                 xleftmargin=-6mm]{msg}

\DOWNarrow{2}{3.5}{1.6}

\LEFTarrow{3}{3.5}{3}

\LEFTarrow{4}{4.7}{4}