\documentclass[12pt,oneside]{article}

% Typography
\usepackage[sc,osf]{mathpazo}
\linespread{1.05}
\usepackage[scaled]{helvet} % ss
\usepackage{courier} % tt
\normalfont
\usepackage[T1]{fontenc}
\usepackage{xspace}
\usepackage{microtype}

\usepackage{amsmath}

\usepackage[main=english,french]{babel}

\def\cite#1{\relax}

\begin{document}

\section{French Summary}

New networking and cryptographic protocols can substantially improve electronic
online payment systems.  This thesis is about the design, implementation and
security analysis of GNU Taler, a privacy-friendly payment system that is
designed to be practical for usage as an online (micro\nobreakdash-)payment method, and at
the same time socially and ethically responsible.

The technical foundation of GNU Taler can be traced back to David Chaum's
e-cash.  Our work extends Chaumian e-cash with efficient change and the novel
notion of income transparency, which guarantees that merchants can reliably
receive a payment from an untrusted payer only when their income from the
payment is visible to tax authorities.

Income transparency is achieved by the introduction of a refresh protocol,
which gives anonymous change for a partially spent coin without introducing a
tax evasion loophole. In addition to income transparency, the refresh protocol
can be used to implement Camenisch-style atomic swaps, and to preserve
anonymity in the presence of protocol aborts and crash faults with data loss by
participants.  Furthermore, we show the provable security of our
income-transparent anonymous e-cash, which, in addition to the usual
anonymity and unforgeability properties of e-cash, also formally models
conservation of funds and income transparency.

Our implementation of GNU Taler is usable by non-expert users and integrates
with the modern web architecture. Our payment platform addresses a range of
practical issues, such as tipping customers, providing refunds, integrating
with banks and know-your-customer (KYC) checks, as well as web platform
security and reliability requirements. On a single machine, we achieve
transaction rates that rival those of global, commercial credit card
processors. We increase the robustness of the exchange -- the component that keeps
bank money in escrow in exchange for e-cash -- by adding an auditor component,
which verifies the correct operation of the system and allows to detect a
compromise or misbehavior of the exchange early.

Just like bank accounts have reason to exist besides bank notes, e-cash only
serves as part of a whole payment system stack. Distributed ledgers have
recently gained immense popularity as potential replacement for parts of the
traditional financial industry. While cryptocurrencies based on proof-of-work
such as Bitcoin have yet to scale to be useful as a replacement for established
payment systems, other more efficient systems based on blockchains with more
classical consensus algorithms might still have promising applications in the
financial industry.  We design, implement and analyze the performance of
Byzantine Set Union Consensus, a Byzantine consensus protocol that agrees on a
(super\nobreakdash-)set of elements at once, instead of sequentially agreeing on the
individual elements on a set.  Byzantine Set Consensus can be used as a
building block for permissioned block chains, where (just like in
Nakamoto-style consensus) whole blocks of transactions are agreed upon at once,
increasing the transaction rate.

\subsection{Goals of GNU Taler}

We started the development of GNU Taler with a set of high-level design goals.
They are ranked by the importance we give to them, and when a trade-off must be
made, the one that supports the more highly ranked goal is preferred:

% what about micropayments -> part of 'efficient'
\begin{enumerate}
  \item \textbf{GNU Taler must be implemented as free software.}

    Free refers to ``free as in free speech'', as opposed to ``free as in free beer''.
    More specifically, the four essential freedoms of free software
    \cite{stallman2002essays} must be respected, namely users must have the
    freedom to (1) run the software, (2) study and modify it, (3) redistribute
    copies, and (4) distribute copies of the modified version.

    For merchants this prevents vendor lock-in, as another payment provider can
    take over, should the current one provide inadequate quality of service.
    As the software of
    the payment provider itself is free, smaller or disadvantaged countries or
    organizations can run the payment system without being controlled by a
    foreign company.  Customers benefit from this freedom, as the wallet
    software can be made to run on a variety of platforms, and user-hostile
    features such as tracking or telemetry could easily be removed from
    wallet software.

    This rules out the mandatory usage of specialized
    hardware such as smart cards or other hardware security modules, as the
    software they run cannot be modified by the user.  These components can,
    however, be voluntarily used by merchants, customers or payment processors
    to increase their operational security.

  \item \textbf{GNU Taler must protect the privacy of buyers.}\label{item:privacy}

    Privacy should be guaranteed via technical measures, as opposed to mere
    policies.  Especially with micropayments for online content, a
    disproportionate amount of rather private data about buyers would be revealed, if
    the payment system does not have privacy protections.

%Especially if a payment system is to be used for microtransactions for online
%content, the privacy of buyers becomes important: if micropayments were more
%commonplace, the transaction data could be used to collect extremely detailled
%profiles of users.  Unfortunately practically no commercially used payment
%system has strong anonymity guarantees.
    
    In legislations with data protection regulations (such as the recently introduced GDPR in Europe \cite{voigt2017eu}),
    merchants benefit from this as well, as no data breach of customers can happen if this information
    is, by design, not collected in the first place.  Obviously some private data, such as the shipping
    address for a physical delivery, must still be collected according to business needs.

    The security of the payment systems also benefits from this, as the model
    shifts from authentication of customers to mere authorization of payments.
    This approach rules out whole classes of attacks such as phishing \cite{garera2007framework} or credit
    card fraud \cite{sahin2010overview}.

  \item \textbf{GNU Taler must enable the state to tax income and crack down on
    illegal business activities.}

    % FIXME: provide broader ethical justification!
    As a payment system must still be legal to operate and use, it must comply
    with these requirements.  Furthermore, we consider levying of taxes as
    beneficial to society.

  \item \textbf{GNU Taler must prevent payment fraud.}

    This imposes requirements on the security of the system, as well as on the
    general design, as payment fraud can also happen through misleading user
    interface design or the lack of cryptographic evidence for certain
    processes.

  \item \textbf{GNU Taler must only disclose the minimal amount of information
    necessary.}

    The reason behind this goal is similar to (\ref{item:privacy}).  The
    privacy of buyers is given priority, but other parties such as merchants
    still benefit from it, for example, by keeping details about the merchant's financials
    hidden from competitors.


  \item \textbf{GNU Taler must be usable.}

    Specifically it must be usable for non-expert customers.  Usability also
    applies to the integration with merchants, and informs choices about the
    architecture, such as encapsulating procedures that require cryptographic
    operations into an isolated component with a simple API.

  \item \textbf{GNU Taler must be efficient.}

    % FIXME: provide broader ethical justification (environmental impact,
    % social cost, opportunity cost of lack of micropayments)
    Approaches such as proof-of-work are ruled out by this requirement.  Efficiency is
    necessary for GNU Taler to be used for micropayments.

  \item \textbf{GNU Taler must avoid single points of failure.}

    While the design we present later is rather centralized, avoiding single
    points of failure is still a goal.  This manifests in architectural choices such as
    the isolation of certain components, and auditing procedures.

  \item \textbf{GNU Taler must foster competition.}

    It must be relatively easy for competitors to join the systems.  While the
    barriers for this in traditional financial systems are rather high, the
    technical burden for new competitors to join must be minimized. Another
    design choice that supports this is to split the whole system into smaller
    components that can be operated, developed and improved upon independently,
    instead of having one completely monolithic system.

\end{enumerate}


\subsection{Byzantine Set Union Consensus} The Byzantine Set Union Consensus
protocol that we design, implement and evaluate offers an asymptotic
improvement over a na\"ive implementation using state machine replication.

For $n$ peers and a set of $m$ elements, our protocol has message complexity
$O(mn + n^2)$ when no peers show Byzantine behavior. When $f$ peers show
Byzantine behavior, the message complexity is $O(mnf+kfn^2)$, where $k$ is the
number of valid set elements exclusively available to the adversary.  We will
show how $k$ can be bounded for common practical applications, since in the
general case $k$ is only bounded by the bandwidth available to the adversary.
In practice, we expect $kf$ to be significantly smaller than $m$. Thus,
$O(mnf+kfn^2)$ is an improvement over using SMR-PBFT (State Machine Replication
with Practical Byzantine Fault Tolerance) which would have complexity $O(mn^2)$
under these assumptions.

We achieve this result by combining an existing Byzantine Consensus protocol
with the efficient set reconciliation protocol of Eppstein.  The same
construction is also applicable to other consensus protocols.

\subsection{Contributions}
We claim the following key contributions for this thesis:

\begin{itemize}
  \item We design, implement and analyze an efficient Byzantine consensus
    protocol on set structures that allows an optimized implementation of
    distributed transaction ledgers.
  \item We introduce the notion of income transparency for e-cash, with an
    instantiation in Chaum-style e-cash and proofs.
  \item We design the GNU Taler payment system under consideration of practical
    aspects of e-cash including aborts, network failures, refunds, multi-coin
    payments, faults from wallet synchronization and their effects on anonymity;
    showing the necessity of a refresh operation.
  \item We propose a modification to our protocol that provides protection
    against certain blackmailing and kidnapping scenarios.
  \item We design and implement the seamless, native integration of e-cash into the web architecture, and discuss
    security and privacy aspects of this integration.
  \item We implemented the GNU Taler payment system and evaluate its
    performance.
\end{itemize}


\end{document}