\documentclass{beamer}

\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}

%\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
%\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

% 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
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables

\usepackage{eurosym}

\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}


\newcounter{sauvegardeenumi}
\newcommand{\saveEnumCounter}{\setcounter{sauvegardeenumi}{\theenumi}}
\newcommand{\continueEnumCounter}{\setcounter{enumi}{\thesauvegardeenumi}}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

% The short title appears at the bottom of every slide, the full title is only on the title page
\title[The GNU Taler System]{The GNU Taler System:  Practical and Provably Secure Electronic Payments}

\author[F. Dold]{Florian Dold \\ \textit{dold@taler.net}} % Your name

\date{February 25, 2019}

\begin{document}


\titlegraphic{%
 \includegraphics[width=2.5cm]{pics/logo-inria.png}\hspace*{2cm}~%
 \includegraphics[width=1cm]{pics/logo-bretagne.png}\hspace*{2cm}~%
 \includegraphics[width=2.5cm]{pics/logo-rff.png}
}


\begin{frame}
\titlepage % Print the title page as the first slide

\end{frame}

\section{Introduction and Motivation}


%--------------------

\begin{frame}
\frametitle{Thesis Statement}
\vfill

\begin{exampleblock}{}
  \Large
  New networking and cryptographic protocols can substantially improve
  electronic online payment systems.
\end{exampleblock}

\pause

\vfill
  In particular:  We present GNU Taler (with its design, implementation and security analysis),
  a privacy-friendly payment system designed for practical usage as online (micro-)payment
  method.
\vfill

\end{frame}

%--------------------

\begin{frame}
\frametitle{Payment System Characteristics}
  \begin{itemize}
    \item Different payment instruments have different, often conflicting requirements.
    \item Anonymity, compliance (KYC/AML), security, convenience, tx rate, decentralization
    \item Payment systems are often used in combination / layered.
    \item Value-based vs register-based.
    \item Value-based typically good for privacy, bad for AML
  \end{itemize}
\end{frame}

%--------------------

\begin{frame}
\frametitle{Grossly Simplified:  Payments in France}
\includegraphics[width=\textwidth]{pics/payment-stack-france.png}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Design Goals: ``Cash for the Internet''}
% say:  design goals are entirely objective
Not all payment systems have the same requirements.  We want ours to
\begin{enumerate}[<+- | alert@+>]
  \item \ldots be implemented as free software.
  \item \ldots protect the privacy of buyers.
  \item \ldots enable the state to tax income and crack down on illegal business
    activities.
  \item \ldots prevent payment fraud.
  \item \ldots only disclose the minimal amount of information necessary.
  \item \ldots be useable.
  \item \ldots be efficient.
  \item \ldots avoid single points of failure.
  \item \ldots foster competition.
\end{enumerate}
\pause $\Rightarrow$ The GNU Taler system is an effort to implement this system.
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Contributions I: Value-based payments}
%This thesis focuses mainly on value-based payments
%on top of an existing register-based system.  Also makes
%contribution towards register layer.

Income-transparent online e-cash
\begin{itemize}
  \item Extension and practical instantiation of (Chaumian) online e-cash.
  \pause
  \item New \emph{income transparency} property for e-cash.
  \item Introduction of a \emph{refresh operation} to support exact spending
    and preserve anonymity after aborts, network failures, refunds, restore from backup/sync.
  \pause
  \item Provisions against ``perfect crime'' / kidnapping scenario.
  \pause
  \item Auditor component: Detection mechanism and responses to
    different compromise scenarios.
  \pause
  \item Formal model and security properties, including income transparency.
  \pause
  \item Usable, practical implementation (GNU Taler) with good performance.
  \item Seamless and native integration into Web platform / architecture.
\end{itemize}

\end{frame}

%----------------------------

\begin{frame}
\frametitle{Contributions II: Register-based payments}

Byzantine \emph{Set-Union} Consensus
\begin{itemize}
  \item Agreement on an exact (super-)set of elements contributed by participants,
    tolerates actively malicious parties.
  \item Asymptotically faster than state of the art.
  \item Approach can be transfered to new/different consensus protocols.
  \item Validated by practical implementation.
\end{itemize}

\vfill
\pause

(To be used in a decentralized ``banking'' / register layer for GNU Taler, fully discussed
  in thesis and backup slides)

\end{frame}

%----------------------------

\section{Income-transparent offline E-cash}

\subsection{Design}


%----------------------------

\begin{frame}
\frametitle{Technical foundation: E-cash}
  \begin{itemize}
    \item First invented / discovered by David Chaum in the 1980s 
    % focused on offline
    \item Huge body of research that builds on e-cash
    \item Foundation:  Blind signatures
    \begin{itemize}
      \item Signer signs a message, but doesn't see the message's contents.
      \item (Unblinded) signature can't be linked to signing request.
      \item First construction:  RSA blind signatures
    \end{itemize}
  \end{itemize}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Taler Overview}
\begin{center}
\begin{tikzpicture}
 \tikzstyle{def} = [node distance= 5em and 6.5em, inner sep=1em, outer sep=.3em];
 \node (origin) at (0,0) {};
 \node (exchange) [def,above=of origin,draw]{Exchange};
 \node (customer) [def, draw, below left=of origin] {Customer};
 \node (merchant) [def, draw, below right=of origin] {Merchant};
 \node (auditor) [def, draw, above right=of origin]{Auditor};

 \tikzstyle{C} = [color=black, line width=1pt]

 \draw [<-, C] (customer) -- (exchange) node [midway, above, sloped] (TextNode) {withdraw coins};
 \draw [<-, C] (exchange) -- (merchant) node [midway, above, sloped] (TextNode) {deposit coins};
 \draw [<-, C] (merchant) -- (customer) node [midway, above, sloped] (TextNode) {spend coins};
 \draw [<-, C] (exchange) -- (auditor) node [midway, above, sloped] (TextNode) {monitor};

\end{tikzpicture}
\end{center}
\end{frame}


%----------------------------

% Was:  implementation demo

%----------------------------

\begin{frame}
\frametitle{E-Cash features and trade-offs}
  Some selected aspects (more in thesis)
  \begin{enumerate}[<+- | alert@+>]
    \item Online/Offline \uncover<+->{$\Rightarrow$ Online}
      \begin{itemize}
        \item Offline = After-the-fact double spending detection
        \item Hard to enforce
        \item Easy to do accidentally (failures / backups)
      \end{itemize}
    \item Change/Divisibility \uncover<+->{$\Rightarrow$ Multiple denominations, partial spending, change protocol}
      \begin{itemize}
        \item Real divisibility nice in theory.
        \item In practice:  complex, trusted setup, multiple withdraw ``sizes''
          needed anyway
        \item Fixed denominations shown to be efficient in spending simulation
      \end{itemize}
    \item Transferability \uncover<+->{$\Rightarrow$ No!}
      \begin{itemize}
        \item Anti-feature, enables black markets / tax evasion!
        \item Taler provides \emph{income transparency}, roughly the \emph{opposite}
      \end{itemize}
    %\item Atomic Swaps / Fair Exchange \uncover<+->{$\Rightarrow$ Supported, coin serial no. is public key}
  \end{enumerate}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Live Demo}
  \vfill

  \url{https://demo.taler.net/}

  \vfill

  Not enough time for demo during this talk!

  \vfill
\end{frame}

\begin{frame}
\frametitle{Taler Protocols:  What is happening under the hood?}
  Setup:
  \begin{enumerate}
    \item Customer has list of trusted exchange / auditor (= exchange CA) public keys
    \item Customer downloads latest key material (response signing / denominations) and wire information from selected exchange
  \end{enumerate}
  \vfill
  Reserve creation:
  \begin{enumerate}
    \item Customer creates reserve key pair (ephemeral)
    \item Customer sends transaction with reserve public key in payment instructions to the exchange
  \end{enumerate}
\end{frame}

\begin{frame}
\frametitle{What is happening under the hood?}
  Withdrawal
  \begin{enumerate}
    \item Customer creates coin key pair (public key is coin identity, private key used to authorize operations with coin)
    \item Customer blinds coin public key, sends withdraw request (signed with reserve private key) to exchange
    \item Exchange signs blinded coin, decreases remaining amount in reserve
    \item Customer unblinds the signature to obtain signed coin
  \end{enumerate}
\end{frame}

\begin{frame}
\frametitle{What is happening under the hood?}
  Spending
  \begin{enumerate}
    \item Merchant sends signed \emph{contract terms} to customer
    \item Customer signs contract terms with the private key(s) of the coins used to pay.
      In each signature, the fraction of the coin spent is specified.
    \item Merchant receives these signatures in \emph{deposit permissions},
      which also include the exchange's signatures on the coins and a hash of the contract terms
    \item Merchant sends deposit permissions to the exchange
    \item Exchange checks signatures, checks double spending, marks coins as (partially) spent
    \item Exchange aggregates deposit permissions for some time
    \item Exchange sends payment (e.g. bank money) to merchant
  \end{enumerate}
\end{frame}

\begin{frame}
\frametitle{What is happening under the hood?}
  Getting anonymous change
  \begin{enumerate}
    \item Customer obtains anonymous coins as change for partially spent coins
    \item More on details later ...
  \end{enumerate}
\end{frame}

%----------------------------


\begin{frame}
\frametitle{Making E-Cash Practical}
  \begin{itemize}
    \item Existing work: surprisingly little focus on practical use.
      \begin{itemize}
        \item What do customers do \textbf{before} the blind signature protocol?
        \item How do customers agree to specific contract terms for a transaction?
        \item How are payments with multiple coins handled?
        \item How are refunds handled?
        \item What happens after data loss / aborts / restore from backup?
      \end{itemize}
    \pause
    \item Separating knowledge of coin from ownership (c.f. Camenisch endorsed e-cash)
    \begin{itemize}
      \item Traditional e-cash $\approx$ sending cash in envelope by mail.
    \end{itemize}
    \item Protocol for anonymous change?
  \end{itemize}

\end{frame}

%----------------------------

\begin{frame}{New Idea: Refresh Protocol}
A coin that is e.g.
\begin{itemize}
  \item partially spent, or
  \item revealed in aborted transaction
  \item restored from offline backup
\end{itemize}
is \emph{dirty}, and can break anonymity.

\pause
\vfill

Strawman idea:  Spend coin with exchange, obtain fresh coin
via blind signing.

$\Rightarrow$ Can be abused:  Merchant provides (blinded) fresh coin to customer

$\Rightarrow$ Naive refresh protocol enables tax evasion

\end{frame}

\begin{frame}{Refresh Protocol}
  Insight:  Owner of the old coin should be able to derive
  private key of new coin (link protocol).

  $\Rightarrow$ Makes untaxed ``transactions'' unreliable.

  $\Rightarrow$ Even if illicit ``transaction'' receiver spends immediately,
  only one hop is hidden.

  \vfill
  \pause

  Relax requirement to make implementation efficient:

  $\Rightarrow$ Exchange provides data to help derive new coin

  $\Rightarrow$ Make it probabilistic:  In $1/3$ of attempts, invisible ``transaction works'',
  in $2/3$ of attempts, the coin is seized by the exchange.

  $\Rightarrow$ Invisible transaction attempts are not economically infeasable anymore.

\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 exchange provides the transfer public key and blinded
      signature on new coin.
    \item Key exchange (Diffie-Hellman) 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
    \pause
    \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 key exchange ($DH(a, B) = DH(b, A)$) allows exchange 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.
    \pause
    \item $\Rightarrow$ Cheating not profitable
  \end{itemize}
\end{frame}

%----------------------------

%----------------------------

\begin{frame}{Taxability}
  We say Taler is taxable because:
  \begin{itemize}
  \item Merchant's income is visible from deposits.
  \item Hash of contract terms is part of deposit data.
  \item State can trace income and enforce taxation.
  \end{itemize}\pause
  Limitations:
  \begin{itemize}
  \item withdraw loophole
  \item {\em sharing} coins among family and friends
  \end{itemize}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{The Auditor:  Post-compromise Security}
  Auditor continuously monitors
  \begin{itemize}
    \item exchange's database
    \item exchange's bank transactions
    \item merchant's deposit (probabilistic selection)
  \end{itemize}
  
  \vfill

  Compromise Scenarios (simplified):
  \begin{itemize}
    \item Exchange's denomination compromised $\Rightarrow$ denomination revoked,
      customers use emergency payback protocol to recover funds
    \item Exchange's signing key compromised $\Rightarrow$ signing key revoked,
      merchants compensated proportional to correct participation in deposit auditing
  \end{itemize}
  (HSMs can make these less likely!)
\end{frame}


\begin{frame}
\frametitle{Emergency Payback Protocol}
  A denomiation $D$ with coin value $v$ that issued $n$ legitimate coins is revoked.
  \begin{itemize}
    \item Freshly withdrawn coins are returned to source reserve (customer shows withdraw transcript)
    \item Partially spent coins can be refreshed into non-revoked denomination.
    \item Refreshes on revoked coins can be ``reversed'' to obtain funds again.
  \end{itemize}

  \vfill

  \vfill

  Revocation triggered after seeing $n+1$ pairwise different $D$-coins, payback for at most $n$ coins.
  
  $\Rightarrow$ Financial loss of the exchange limited to $2nv$.

  $\Rightarrow$ Anonymity of customer preserved (one exception can be fixed with perf tradeoff)
\end{frame}

%----------------------------

\begin{frame}{``Perfect Crime'' Countermeasures}
  \begin{itemize}
    \item Scenario:  Kidnapper wants anonymous E-Cash as ransom.
    \item Existing tracing approaches can be circumvented by just requesting plain e-cash,
      threat to user privacy.
  \end{itemize}

  \begin{block}{Taler's Perfect Crime Response}
    \begin{itemize}
      \item Honest user's coins must only be used in either refreshing or spending (w.l.o.g.)
      \item Ransom coins are withdrawn from some reserve(s), given to the attacker
      \item Denominations given to the attacker are revoked, reserves used to withdraw ransom are blocked.
      \item Normal customers use recovery protocol.
    \end{itemize}
  \end{block}
\end{frame}

%----------------------------

\subsection{Overview of Protocol}

%----------------------------

%\begin{frame}{Taler Cryptography}
%  We use a few ancient constructions:
%  \begin{itemize}
%  \item Cryptographic hash function (1989)
%  \item Blind signature (1983)
%  \item Schnorr signature (1989)
%  \item Diffie-Hellman key exchange (1976)
%  \item Cut-and-choose zero-knowledge proof (1985)
%  \end{itemize}
%  But of course we use modern instantiations.
%\end{frame}

%\begin{frame}{Refresh Protocol (Simplified Sketch)}
%  Cut-and-choose to ensure linkability!
%  \begin{itemize}
%    \item Customer has old coin with key $(c_0, C_0)$
%    \item Customer generates $\kappa$ (usually $\kappa=3$) transfer key pairs $(t_i, T_i)$,
%    \item Customer derives $\kappa$ candidates (coin key pair,
%      blinding factor, signing request) from \textbf{ECDH between old coin and
%      transfer key}
%    \item Customer sends transfer public keys and commitments to the $\kappa$ candidates to the exchange
%    \item Exchange marks $C_0$ as spent and asks customer to reveal all candidates except $\gamma$-th
%    \item Customer reveals all candidates except the $\gamma$-th, reveals blinded coin for $\gamma$-th candidate
%    \item Exchange checks if commitments match revealed values (knowing the
%      transfer secret key), i.e. if the new coin's private key could be derived
%      knowing $T_i$ and $c_0$ (as $\textrm{ECDH}(t_i, C_0) = \textrm{ECDH}(c_0, T_i)$).
%    \item If a commitment does not match, refreshing denied, no new attempts allowed.
%    \item If commitments were correct, exchange signs blinded coin
%  \end{itemize}
%\end{frame}


%----------------------------


%----------------------------

\subsection{Security}

%----------------------------

\begin{frame}
\frametitle{Provable Security}
\vfill
How do you know that your protocols are ``secure''?
  \begin{itemize}
    \item Bad answer:  Implement, wait for someone to find a flaw, fix it, iterate.
    \item Better answer: Formal model, security properties.
  \end{itemize}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Formal Model / Provable Security}
\includegraphics[width=\textwidth]{pics/provable-security.png}
\end{frame}

%---------------------------

%\begin{frame}
%\frametitle{Security Properties}
%Other systems don't focus that much on aborts.  Something goes wrong, then what do you do?
%
%What if you restore from backup?
%
%Most work focuses on offline e-cash.
%
%No considerations of practical compromise.
%\end{frame}

%----------------------------

\begin{frame}
\frametitle{Security Properties (cont'd)}
  \begin{block}{Anonymity}
    Adversary can't correlate withdraw/refresh operation
    with coin used in spend operation.
  \end{block}

  \pause

  \begin{block}{Unforgeability}
    Adversary can't obtain coins of a higher value
    than they legitimately withdraw.
  \end{block}
\end{frame}


%----------------------------

\begin{frame}
\frametitle{Security Properties (cont'd)}
  \begin{block}{Conservation}
    For honest customers, value of coins withdrawn cannot exceed value in their
    wallet plus value spent on transactions known to that customer.
  \end{block}

  \pause

  \begin{block}{Strong Income Transparency}
    Adversary can't obtain \textbf{exclusive} control of a coin,
    without the exchange having a record (withdraw/spend) of the coin.
  \end{block}

  \pause
  \alert<+>{Strong Income Transparency is not satisfied by Taler!}
  \pause

  \begin{block}{(Weak) Income Transparency}
    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}

%----------------------------


\begin{frame}
\frametitle{Syntax and Oracles}
\begin{columns}
\begin{column}{0.5\textwidth}
  Algorithms / interactive protocols
  \begin{itemize}
    \item $\textrm{ExchangeKeygen}$, $\textrm{CustomerKeygen}$, $\textrm{MerchantKeygen}$
    \item $\textrm{WithdrawRequest}$, $\textrm{WithdrawPickup}$
    \item $\textrm{Spend}$
    \item $\textrm{Deposit}$
    \item $\textrm{RefreshRequest}$, $\textrm{RefreshPickup}$
    \item $\textrm{Link}$
  \end{itemize}
\end{column}
\begin{column}{0.5\textwidth}
  Oracles
  \begin{itemize}
    \item Oracles to run algorithms / interactive protocols the game's entities
    \item $\mathcal{O}\textrm{AddCustomer}$, $\mathcal{O}\textrm{AddMerchant}$
    \item $\mathcal{O}\textrm{CorruptCustomer}$
    \item $\mathcal{O}\textrm{Share}$
  \end{itemize}
\end{column}
\end{columns}

\vfill

Games use algorithms / give oracle access to adversary.  Proofs show:  If adversary can win
game (non-negl.), then they can break some underlying assumption.
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Provable Security:  Limitations}
  \begin{itemize}
    \item Hard to verify that implementation matches model
    \item Some features of the actual system not formally modelled
    \item Bugs in the implementation, side channels, etc.
  \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(S)/JSON protocol.
    \item Plugin architecture for different wire methods
    \item Web integration / payto://
  \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}
%\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}

%----------------------------

%\begin{frame}
%  \frametitle{But what about Blockchain}
%  What is Blockchain?  (Consensus + Tamper-Proof DB)?
%\end{frame}

%----------------------------

\begin{frame}
\frametitle{Future Work}
  \begin{itemize}
    \item Mechanize security properties (e.g. ProVerif / CryptoVerif / F-star)
    \item Applications:  Network incentives, anti-spam
    \item Smart(er) contracts / auctions
    \item Backup + Sync
  \end{itemize}
\end{frame}

\begin{frame}
\frametitle{Funded/Ongoing Work}
  \begin{itemize}
    \item Me:  Work on Taler NFC / PoS terminal for the next 6 month, supported
      by German government grant (Prototype Fund)
    \item Taler Systems:  Employs 1 engineer (Marcello Stanisci), looking for funding!
  \end{itemize}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Conclusion}
  \begin{itemize}
    \item Taler is a implementation of income-transparent e-cash,
      designed for practical usage, backed by a formal model.
    \item Byzantine Set Union Consensus is a new consensus primitive that could
      be useful in constructing a robust register-based payment system.
    \item Taler might enable new business models on the Web.
    \item Income-transparency might help with adoption in the traditional banking world
    \item Unlike Blockchain, it is efficient and provides the right level of anonymity.
  \end{itemize}
\end{frame}

%----------------------------

\begin{frame}
\frametitle{Publications}
{
\small
\vfill
Dold, F. and Grothoff, C., 2017. Byzantine set-union consensus using efficient
set reconciliation. EURASIP Journal on Information Security, 2017(1), p.14.
\vfill
Burdges, J., Dold, F., Grothoff, C. and Stanisci, M., 2016, December. Enabling Secure Web Payments with GNU Taler. In International Conference on Security, Privacy, and Applied Cryptography Engineering (pp. 251-270). Springer, Cham.
\vfill
Dold, Florian, and Christian Grothoff. "GNU Taler: Ethical online payments for the internet age." ERCIM NEWS 106 (2016): 12-13.
\vfill
Burdges, J., Dold, F., Grothoff, C. and Stanisci, M., 2016, June. Taler: Usable, privacy-preserving payments for the Web. In HotPETS 2016-Workshop on Hot Topics in Privacy Enhancing Technologies.
\vfill
Dold, F., Grothoff, C., 2019, January.  The 'payto' URI scheme for payments.  In IETF Internet-Drafts.
\vfill
}
\end{frame}

%------------------------------------------------

%\begin{frame}
%\frametitle{References}
%\footnotesize{
%\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below
%\bibitem[Smith, 2012]{p1} John Smith (2012)
%\newblock Title of the publication
%\newblock \emph{Journal Name} 12(3), 45 -- 678.
%\end{thebibliography}
%}
%\end{frame}

%------------------------------------------------

\begin{frame}
\Huge{\centerline{Q+A}}
\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}{Backup Slides: 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}


%----------------------------------------------------------------------------------------

\end{document}