slides

1 files changed, 189 insertions, 177 deletions

diff --git a/presentation/slides.tex b/presentation/slides.tex
index b7e0813..f53a0b9 100644
--- a/presentation/slides.tex
+++ b/presentation/slides.tex
@@ -58,6 +58,7 @@
 
 % remove the navigation symbols from the bottom of all slides
 \setbeamertemplate{navigation symbols}{}
+\setbeamertemplate{page number in head/foot}[appendixframenumber]
 }
 
 \usepackage{graphicx} % Allows including images
@@ -84,7 +85,7 @@
 
 \author[F. Dold]{Florian Dold \\ \textit{dold@taler.net}} % Your name
 
-\date{\today} % Date, can be changed to a custom date
+\date{February 25, 2019}
 
 \begin{document}
 
@@ -107,18 +108,24 @@
 %--------------------
 
 \begin{frame}
-\frametitle{Motivation}
+\frametitle{Motivation / Thesis Statement}
 The internet has many standards, but not a standard payment system.
 
 $\Rightarrow$ Proliferation of ads, proprietary payment systems that collect user data.
 
 \vfill
 
-\begin{block}{Question}
-  How can new network protocols and cryptographic protocols
-  improve online payment systems?  Can a payment system be secure
-  and follow certain \emph{ethical/societal} goals?
-\end{block}
+\begin{exampleblock}{}
+  New networking and cryptographic protocols can substantially improve
+  electronic online payment systems.
+\end{exampleblock}
+
+\vfill
+In particular:  The design, implementation and security analysis of GNU Taler
+contributes towards an online (micro-)payment method that is privacy
+friendly, and at the same time ethically/socially responsible.
+\vfill
+
 \end{frame}
 
 %--------------------
@@ -256,9 +263,7 @@ Byzantine \emph{Set-Union} Consensus
 
 %----------------------------
 
-\begin{frame}
-\Huge{\centerline{Implementation Demo}}
-\end{frame}
+% Was:  implementation demo
 
 %----------------------------
 
@@ -398,7 +403,7 @@ $\Rightarrow$ Naive refresh protocol enables tax evasion
   \vfill
   \pause
 
-  Relax requirement to make implementation easy:
+  Relax requirement to make implementation efficient:
 
   $\Rightarrow$ Exchange provides data to help derive new coin
 
@@ -409,6 +414,38 @@ $\Rightarrow$ Naive refresh protocol enables tax evasion
 
 \end{frame}
 
+
+\begin{frame}{Refresh Protocol (Simplified Sketch)}
+  Expected result:
+  \begin{itemize}
+    \item Every successful refresh results in a \emph{transfer public key}
+    \item Given the old coin's public key, the exchanges provides the transfer public key and blinded
+      signature on new coin.
+    \item Diffie-Hellman exchange between transfer public key and coin secret key gives seed
+      for deriving the new coin's blinding factor and secret key
+    \item \emph{Catch:} How can the exchange know that the transfer public key is correct?
+  \end{itemize}
+\end{frame}
+
+
+\begin{frame}{Refresh Protocol (Simplified Sketch)}
+  Answer:  Cut-and-choose
+  \begin{itemize}
+    \item Naive refresh is run with multiple ($\kappa$, typically 3) instances in parallel, thus there are $\kappa$ candidates
+      for the new coin
+    \item At most one instance will result in a signature
+    \item At the beginning, customer makes a hiding+binding commitment to private values (priv. key / blinding factor)
+    \item For $\kappa - 1$ other instances, private values must be revealed, checked by exchange and thrown away
+    \item Diffie-Hellman exchange ($DH(a, B) = DH(b, A)$) allows us to check that commitment is correct
+      by revealing transfer key, but \emph{not} the old coin's secret key.
+    \item With probability $1/\kappa$, adversary can sneak in wrong transfer public key.
+    \item If cheating is attempted, with probability $1-1/\kappa$ the coin will be ``seized'' by the exchange.
+    \item $\Rightarrow$ Cheating not profitable
+  \end{itemize}
+\end{frame}
+
+%----------------------------
+
 %----------------------------
 
 \begin{frame}{Taxability}
@@ -525,143 +562,9 @@ $\Rightarrow$ Naive refresh protocol enables tax evasion
 %  \end{itemize}
 %\end{frame}
 
-\begin{frame}{Refresh Protocol (Simplified Sketch)}
-  Expected result:
-  \begin{itemize}
-    \item Every successful refresh results in a \emph{transfer public key}
-    \item Given the old coin's public key, the exchanges provides the transfer public key and blinded
-      signature on new coin.
-    \item Diffie-Hellman exchange between transfer public key and coin secret key gives seed
-      for deriving the new coin's blinding factor and secret key
-    \item \emph{Catch:} How can the exchange know that the transfer public key is correct?
-  \end{itemize}
-\end{frame}
-
-
-\begin{frame}{Refresh Protocol (Simplified Sketch)}
-  Answer:  Cut-and-choose
-  \begin{itemize}
-    \item Naive refresh is run with multiple ($\kappa$, typically 3) instances in parallel, thus there are $\kappa$ candidates
-      for the new coin
-    \item At most one instance will result in a signature
-    \item At the beginning, customer makes a hiding+binding commitment to private values (priv. key / blinding factor)
-    \item For $\kappa - 1$ other instances, private values must be revealed, checked by exchange and thrown away
-    \item Diffie-Hellman exchange ($DH(a, B) = DH(b, A)$) allows us to check that commitment is correct
-      by revealing transfer key, but \emph{not} the old coin's secret key.
-    \item With probability $1/\kappa$, adversary can sneak in wrong transfer public key.
-    \item If cheating is attempted, with probability $1-1/\kappa$ the coin will be ``seized'' by the exchange.
-    \item $\Rightarrow$ Cheating not profitable
-  \end{itemize}
-\end{frame}
-
-%----------------------------
-
-%----------------------------
-
-\begin{frame}
-\frametitle{Real-World Deployment: Architecture}
-\includegraphics[width=\textwidth]{pics/taler-arch-full.pdf}
-\end{frame}
-
-\begin{frame}
-\frametitle{Implementation Overview}
-  \begin{itemize}
-    \item Implemented in multiple components:
-    \begin{itemize}
-      \item Exchange
-      \item Auditor
-      \item Merchant backend
-      \item Merchant frontends (donations, blog, survey, backoffice, codeless payments)
-      \item Browser Wallet (WebExtension)
-    \end{itemize}
-    \item Communication through HTTP/JSON protocol.
-    \item Plugin architecture for different wire methods
-  \end{itemize}
-\end{frame}
-
-\begin{frame}
-\frametitle{Entities / PKI}
-\includegraphics[width=\textwidth]{pics/taler-diagram-signatures.png}
-\end{frame}
-
-\begin{frame}
-\frametitle{Exchange Architecture}
-\includegraphics[width=\textwidth]{pics/taler-diagram-exchange.png}
-\end{frame}
-
-\begin{frame}
-\frametitle{Auditor Architecture}
-\includegraphics[width=\textwidth]{pics/taler-diagram-keyup.png}
-\end{frame}
-
-\begin{frame}
-\frametitle{Merchant Architecture}
-\includegraphics[width=\textwidth]{pics/taler-diagram-merchant.png}
-\end{frame}
-
-\begin{frame}
-\frametitle{Wallet Architecture}
-\includegraphics[width=\textwidth]{pics/taler-diagram-wallet.png}
-\end{frame}
 
 %----------------------------
 
-\begin{frame}{Web Integration}
-  payto:// URIs
-  \begin{itemize}
-    \item Well known: \url{mail:dold@taler.net?subject=hello} describes a mail address with
-      some additional info for sending the mail
-    \item Payto does the same for bank accounts / bitcoin wallets / ... ($=$ payment targets)
-    \item Used by Taler internally, as well as externally to prompt sending money to the exchange
-    \item Currently trying to find the right WG / AD at the IETF to make it a standard
-  \end{itemize}
-\end{frame}
-
-%----------------------------
-
-\begin{frame}
-\frametitle{Alternatives?}
-W3C Web Payments?  No, only concerned with showing payment request in browser UI.
-
-\vfill
-
-Proprietary Systems?
-
-\vfill
-
-Blockchain?
-
-\end{frame}
-
-%----------------------------
-
-\begin{frame}
-\frametitle{Experiments / Performance}
-  \begin{itemize}
-    \item Wallet: Most operations take in the order of 10s of milliseconds per
-      coin, even on semi-recent android phones
-    \item How many coins consitute one ``transaction''?  How many / what kind of refreshes per transaction?
-    \begin{itemize}
-      \item Depends on denominations, coin selection, typical amounts
-      \item Results from naive simulation (denominations $2^0,\dots,2^12$, uniform random spends $4-5000$)
-      \item $8.3$ spend operations, $1.3$ refresh operations with $4.2$ outputs
-    \end{itemize}
-    \item Benchmarks done on 96-core AMD EPYC 7451 CPU with 256GiB DDR42667 MHz
-      RAM
-  \end{itemize}
-\end{frame}
-
-\begin{frame}
-\frametitle{Experiments / Performance}
-  \begin{itemize}
-    \item \textit{taler-exchange-benchmark}: Testbed with parallel clients and one exchange
-    \item $\Rightarrow$ CPU / network bandwidth dominated by refreshing
-    \item $\Rightarrow$ $\approx 1/2$ of time spent in cryptographic operations
-    \item $\Rightarrow$ Many db tx conflicts observed leading to retries, potential for some optimization
-    \item $\Rightarrow$ Pessimistic assumptions:  $230$ transactions/second on one machine
-    \item $\Rightarrow$ Fixed microtransactions:  $1560$ transactions/second on one machine
-  \end{itemize}
-\end{frame}
 
 %----------------------------
 
@@ -730,10 +633,8 @@ How do you know that your protocols are ``secure''?
   \pause
 
   \begin{block}{(Weak) Income Transparency}
-    Adversary can't obtain \textbf{exclusive} control of a coin,
-    without the exchange having a record (withdraw/spend) of the coin.
-
-    FIXME!!!
+    The adversary's \textbf{laundering ratio} $\frac{p}{b+p}$ (untaxed income $p$, losses $b$)
+    is lower than $1/\kappa$ \textbf{on average}.
   \end{block}
 \end{frame}
 
@@ -789,50 +690,109 @@ game (non-negl.), then they can break some underlying assumption.
 
 %----------------------------
 
-\section{Byzantine Set Union Consensus}
+\begin{frame}
+\frametitle{Real-World Deployment: Architecture}
+\includegraphics[width=\textwidth]{pics/taler-arch-full.pdf}
+\end{frame}
 
 \begin{frame}
-  \frametitle{Byzantine Consensus}
+\frametitle{Implementation Overview}
   \begin{itemize}
-    \item Classic problem in distributed systems
-    \item Group of peers have to agree on a bit / value.
-    \item Some peers are actively malicious (byzantine)
-    \item FLP impossiblity result: no deterministic protocol can solve the
-      consensus problem in the asynchronous communication model, even in the
-      presence of only one crash-fault
+    \item Implemented in multiple components:
+    \begin{itemize}
+      \item Exchange
+      \item Auditor
+      \item Merchant backend
+      \item Merchant frontends (donations, blog, survey, backoffice, codeless payments)
+      \item Browser Wallet (WebExtension)
+    \end{itemize}
+    \item Communication through HTTP/JSON protocol.
+    \item Plugin architecture for different wire methods
   \end{itemize}
 \end{frame}
 
 \begin{frame}
-  \frametitle{Byzantine Consensus}
+\frametitle{Entities / PKI}
+\includegraphics[width=\textwidth]{pics/taler-diagram-signatures.png}
+\end{frame}
+
+\begin{frame}
+\frametitle{Exchange Architecture}
+\includegraphics[width=\textwidth]{pics/taler-diagram-exchange.png}
+\end{frame}
+
+\begin{frame}
+\frametitle{Auditor Architecture}
+\includegraphics[width=\textwidth]{pics/taler-diagram-keyup.png}
+\end{frame}
+
+\begin{frame}
+\frametitle{Merchant Architecture}
+\includegraphics[width=\textwidth]{pics/taler-diagram-merchant.png}
+\end{frame}
+
+\begin{frame}
+\frametitle{Wallet Architecture}
+\includegraphics[width=\textwidth]{pics/taler-diagram-wallet.png}
+\end{frame}
+
+%----------------------------
+
+\begin{frame}{Web Integration}
+  payto:// URIs
   \begin{itemize}
-    \item PBFT (Practical Byzantine Fault Tolerance, Liskov et. al 1999) is the most well-known
-      implementation in the partially synchronous model, works as long as there is a $2/3$ majority of honest peers.
-    \item Agrees on a sequence of states
+    \item Well known: \url{mail:dold@taler.net?subject=hello} describes a mail address with
+      some additional info for sending the mail
+    \item Payto does the same for bank accounts / bitcoin wallets / ... ($=$ payment targets)
+    \item Used by Taler internally, as well as externally to prompt sending money to the exchange
+    \item Currently trying to find the right WG / AD at the IETF to make it a standard
   \end{itemize}
-  \pause
-  Common consensus application:  Collect elements from different sources, agree on an exact set.
+\end{frame}
+
+%----------------------------
+
+\begin{frame}
+\frametitle{Alternatives?}
+W3C Web Payments?  No, only concerned with showing payment request in browser UI.
+
+\vfill
+
+Proprietary Systems?
+
+\vfill
+
+Blockchain?
+
+\end{frame}
+
+%----------------------------
+
+\begin{frame}
+\frametitle{Experiments / Performance}
   \begin{itemize}
-    \item Collecting ballots, transactions for a block, \ldots
-    \item Sequential agreement on $m$ elements with $n$ peers with PBFT: $\mathcal{O}(mn^2)$
+    \item Wallet: Most operations take in the order of 10s of milliseconds per
+      coin, even on semi-recent android phones
+    \item How many coins consitute one ``transaction''?  How many / what kind of refreshes per transaction?
+    \begin{itemize}
+      \item Depends on denominations, coin selection, typical amounts
+      \item Results from naive simulation (denominations $2^0,\dots,2^12$, uniform random spends $4-5000$)
+      \item $8.3$ spend operations, $1.3$ refresh operations with $4.2$ outputs
+    \end{itemize}
+    \item Benchmarks done on 96-core AMD EPYC 7451 CPU with 256GiB DDR42667 MHz
+      RAM
   \end{itemize}
 \end{frame}
 
 \begin{frame}
-\frametitle{Byzantine Set Union Consensus}
-Can we improve on the $\mathcal{O}(mn^2)$ bound?
+\frametitle{Experiments / Performance}
   \begin{itemize}
-    \item Idea: Combine existing, simple consensus protocol with set reconciliation algorithm (Eppstein)
-    \item Requires some modification to Eppstein to tolerate Byzantine behavior
-    \item With no Byzantine behavior, complexity is $\mathcal{O}(mn+n^2)$
-    \item With $f$ Byzantine peers with exclusive access to $k$ set elements, 
-      complexity is $\mathcal{O}(mnf+kfn^2)$
-    \item Typically, $kf \ll m$
-    \item Proof of correctness in thesis.
-    \item Implementation in the GNUnet peer-to-peer framework.
+    \item \textit{taler-exchange-benchmark}: Testbed with parallel clients and one exchange
+    \item $\Rightarrow$ CPU / network bandwidth dominated by refreshing
+    \item $\Rightarrow$ $\approx 1/2$ of time spent in cryptographic operations
+    \item $\Rightarrow$ Many db tx conflicts observed leading to retries, potential for some optimization
+    \item $\Rightarrow$ Pessimistic assumptions:  $230$ transactions/second on one machine
+    \item $\Rightarrow$ Fixed microtransactions:  $1560$ transactions/second on one machine
   \end{itemize}
-
-$\Rightarrow$ Could be useful as building block for a value-based payment system (underneath Taler e-cash).
 \end{frame}
 
 %----------------------------
@@ -911,6 +871,58 @@ Burdges, J., Dold, F., Grothoff, C. and Stanisci, M., 2016, June. Taler: Usable,
 \Huge{\centerline{The End}}
 \end{frame}
 
+\appendix
+
+
+\begin{frame}
+  \frametitle{Backup Slides: Byzantine Set Union Consensus}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Byzantine Consensus}
+  \begin{itemize}
+    \item Classic problem in distributed systems
+    \item Group of peers have to agree on a bit / value.
+    \item Some peers are actively malicious (byzantine)
+    \item FLP impossiblity result: no deterministic protocol can solve the
+      consensus problem in the asynchronous communication model, even in the
+      presence of only one crash-fault
+  \end{itemize}
+\end{frame}
+
+\begin{frame}
+  \frametitle{Byzantine Consensus}
+  \begin{itemize}
+    \item PBFT (Practical Byzantine Fault Tolerance, Liskov et. al 1999) is the most well-known
+      implementation in the partially synchronous model, works as long as there is a $2/3$ majority of honest peers.
+    \item Agrees on a sequence of states
+  \end{itemize}
+  \pause
+  Common consensus application:  Collect elements from different sources, agree on an exact set.
+  \begin{itemize}
+    \item Collecting ballots, transactions for a block, \ldots
+    \item Sequential agreement on $m$ elements with $n$ peers with PBFT: $\mathcal{O}(mn^2)$
+  \end{itemize}
+\end{frame}
+
+\begin{frame}
+\frametitle{Byzantine Set Union Consensus}
+Can we improve on the $\mathcal{O}(mn^2)$ bound?
+  \begin{itemize}
+    \item Idea: Combine existing, simple consensus protocol with set reconciliation algorithm (Eppstein)
+    \item Requires some modification to Eppstein to tolerate Byzantine behavior
+    \item With no Byzantine behavior, complexity is $\mathcal{O}(mn+n^2)$
+    \item With $f$ Byzantine peers with exclusive access to $k$ set elements, 
+      complexity is $\mathcal{O}(mnf+kfn^2)$
+    \item Typically, $kf \ll m$
+    \item Proof of correctness in thesis.
+    \item Implementation in the GNUnet peer-to-peer framework.
+  \end{itemize}
+
+$\Rightarrow$ Could be useful as building block for a value-based payment system (underneath Taler e-cash).
+\end{frame}
+
+
 \begin{frame}
 \frametitle{Backup Slides: Implementation Screenshots}
 \end{frame}