path: root/introduction.tex

\chapter{Introduction}\label{chapter:introduction}

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\footnote{\url{https://taler.net/}}, a privacy-friendly payment
system that is designed to be practical for usage as an online
(micro-)payment method, and at the same time socially and ethically
responsible.

Payment systems can generally be divided into two types: Register-based
and value-based~\cite{riksbank2017riksbank}.  A register-based system
associates value with identities (e.g., bank account balances with
customers), while a value-based system associates value with typically
anonymous, digital or physical tokens (such as cash or prepaid credit
cards).  In practice, these two types of systems are combined, as
different layers have different (and often conflicting) requirements:
the payment system used to pay for a cappuccino in a coffee shop is
most likely not suitable to buy real estate.  Value-based payment
systems typically provide more anonymity and convenience but also more
risk to consumers (as they are responsible to secure the values they
hold), while register-based systems shift risks to the payment service
provider who has to authenticate consumers and ensure the integrity of
the register.

This thesis covers both categories of payment systems:

\begin{itemize}
  \item We explain GNU Taler, a design and implementation of a value-based
   payment system, discussing in-depth how to create a practical,
   privacy-preserving and secure (micro-)payment protocol that integrates
   nicely with the modern web.  Our value-based payment protocol can in
   principle operate on top of any existing register-based system.
  \item For register-based payment systems, we present a new Byzantine
    consensus protocol.  Consensus protocols are a key component of virtually
    all robust, distributed, register-based systems, as they facilitate
    agreement on a transaction leger. Our Byzantine set union consensus (BSC)
    protocol can be used to achieve consensus in a decentralized and robust
    manner that tolerates a fraction of actively malicious participants.  Our
    BSC protocol asymptotically speeds up the implementation of such
    transaction ledgers, compared to classic Byzantine consensus
   protocols.
\end{itemize}

GNU Taler is an official package of the GNU
project\footnote{\url{https://gnu.org/}}, and the BSC protocol was
implemented in the \textsc{CONSENSUS} subsystem of the GNUnet
framework.\footnote{\url{https://gnunet.org}} Our free software
implementations are freely available from the GNU mirrors.


\section{Design Goals for GNU Taler}

The design of payment systems shapes economies and societies
\cite{zandi2013impact,dalebrant2016monetary}.  Payment systems with high
transaction costs create an economic burden.  Predominantly cash-based
societies provide some degree of anonymity for their citizens, but can fail to
provide a sound foundation for taxation, facilitate corruption
\cite{singh2017does} and thus risk creating weak governments. On the other
hand, systems with too much surveillance eliminate personal freedom.

As the Internet has no standardized payment system, especially not one
that is capable of quickly, efficiently and securely settling small
transactions (so-called micropayments), the majority of content on the web is
financed by advertisements.  As a result, advertising (and by
implication, collecting data on users) has been a dominant business
model on the Internet.  This has not only resulted in a loss of
independence of publishers---who need to cater to the needs
of advertisers---but also in a situation where micro-targeted ads
are so wide-spread, that they have been suspected to have influenced
multiple major elections~\cite{persily2017election}.  Ads are also a
vector for malware \cite{provos2007ghost}.  Due to the prevalence of
ad blockers, ads are also not guaranteed to be a sustainable business
model.

In the world of online payments, credit cards and a sprawling number
of smaller, proprietary payment processors are currently dominant, and
market shares vary widely between different
countries~\cite{adyen2016global,paypers2016ecommerce}.  The resulting
fragmentation again increases social costs: online shops can either
choose to invest in implementing many proprietary protocols, or only
implement the most popular ones, thereby reinforcing the dominance of
a handful of proprietary payment systems.

Considering these and other social implications of payment systems, we
started the development of GNU Taler with a set of high-level design
goals that fit our social agenda.  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}



\section{Features of Value-based Payment Systems}\label{sec:intro:features}

There are many different possible features that have been proposed for
value-based (sometimes called token-based) payment systems in the past.  While we
will discuss existing work on e-cash in more detail in
Section~\ref{sec:related-work:e-cash}, we will begin by a brief
summary of the possible features that value-based payment systems
could provide, and clarify which high-level features we chose to adopt
for GNU Taler.

% EXPLAIN:  in traditional (online) e-cash, spending is never
% bound to a contract identifier

%\subsubsection*{Different signature schemes and zero-knowledge proofs}
%Since Chaum's original blind signature scheme based on RSA, many variations
%using other cryptographic primitives have been developed.  Some newer e-cash
%schemes do not use blind signatures, but rely on zero-knowledge proofs instead.
%
%In GNU Taler, we opt for an RSA-based blind signature scheme, due to the low
%complexity, relatively clear security assumptions and small number of
%communication rounds compared to other protocols.

\subsection{Offline vs Online Payments}

Anonymous digital cash schemes since Chaum~\cite{chaum1983blind} were frequently designed to allow
the merchant to be offline during the transaction, by providing a means to
deanonymize customers involved in double-spending, typically by encoding the
customer's identity into their coins in a way that makes it only possible to
decode the identity with two spending transcripts.

This approach is problematic in practice, as customers that restore a wallet
from backup might accidentally double-spend and would then face punishment for
it.  Enforcing punishment for double-spenders can be rather difficult as well,
since the double-spender might have signed up with a false identity or might
already have fled to another country, and a large number of merchants might already
have been defrauded with the same coins.

Should the issuer of e-cash be compromised, an attacker could issue coins that
fail to identify a culprit or even blame somebody else when they are
double-spent.  In an offline e-cash system, the detection of such an event is
greatly delayed compared to systems with online spending, which can immediately
detect when more coins are spent than were issued.

Thus, in GNU Taler, we decided that all coins must be immediately
deposited online during a purchase.  Only either a merchant or a customer
needs to be online, since one of the two can forward messages to the
payment service provider for the other.

\subsection{Change and Divisibility}

Customers  do not always have the right set of coins available to exactly cover
the amount to be paid to a merchant.  With physical cash, the store would
give the customer change.  For e-cash, the situation is more complex, as
the customer would have to make sure that the change has not already been
spent, does not violate their anonymity and the merchant does not have a
digital ``copy'' of the change tokens that the merchant can spend before the customer.  Note
that it would be unwise to always withdraw the correct amount of e-cash
directly before a purchase, as it creates a temporal correlation between the
non-anonymous withdrawal event and the spending event.

Most modern e-cash schemes instead deal with exact spending  by providing
\emph{divisibility} of coins, where the customer can decide to only spend part
of a coin.  A significant chunk of the e-cash literature has been concerned
with developing schemes that allow the individual, divided parts of a coin to
be unlinkable (thus preserving anonymity) and to optimize the storage costs for
wallets and the communication cost of withdrawals.

The current state of the art for divisible e-cash~\cite{pointcheval2017cut}
achieves constant-time withdrawal and wallet storage cost for coins that can be
split into an arbitrary but fixed (as a system parameter) number of pieces.  A
continuous ``chunk'' of the smallest pieces of a coin can be spent with
constant-time communication complexity.

While this sounds attractive in theory, these results are mostly of academic
interest, as the storage and/or computational complexity for the party that is
checking for double spending of coins remains enormous:  each smallest piece of
every coin needs to be recorded and checked individually.  When paying
$\$10.00$ with a coin that supports division into cent pieces, $1000$
individual coin pieces must be checked for double spending and recorded,
possibliy in compressed form to trade storage costs for more computation.

For GNU Taler, we use a rather simple and practical approach, made possible by
requiring participants to be online during spending:  coins can be fractionally
spent without having divisible, unlinkable parts. The remaining value on a coin
that was spend (and thus revealed) can be used to withdraw fresh, unlinkable
coins.  The protocol to obtain change takes additional measures to ensure that
it cannot be misused to facilitate untaxed transactions.  Giving change for
e-cash has been proposed before \cite{brickell1995trustee,tracz2001fair}, but
to the best of our knowledge, the idea of income-transparent change is novel.

\subsection{Anonymity Control}

Some proposed e-cash protocols contain mechanisms to allow selective
deanonymization of transactions for scenarios involving crime
\cite{sander1999escrow}, specifically blackmailing and tax evasion.

Unfortunately this does not really work as a countermeasure against
blackmailing in practice.  As noted in the paper that initially described such
a mechanism for blind signatures \cite{stadler1995fair}, a blackmailer could
simply request to be paid directly with plain, blindly signed coins, and
thereby completely circumvent the threat of revocable anonymity.

GNU Taler provides \emph{income transparency} as a measure against tax evasion.
We furthermore describe a different approach in a blackmailing scenario in
Section~\ref{sec:design:blackmailing}, which we believe is more practical in
dissuading blackmailers in practice.

\subsection{User Suspension}

Anonymous user suspension \cite{au2011electronic} has been proposed as
another mechanism to punish users suspected in illicit activities by
preventing then from making further transactions until the suspension is
lifted.  Anonymous suspension is based on transactions; the user
involved in a particular transaction is suspended, but their identity is not
revealed.

While the approach is interesting, it is not practical, as it requires
a single permanent key pair to be associated with each user.  If a
user claims they lost their private key and requests a new key pair,
their suspension would be effectively lifted. Suspending users from a
dominant payment system is also socially problematic, as excluding
them from most commercial activities would likely be a
disproportionate and cruel punishment.

\subsection{Transferability}

Transferability is a feature of certain e-cash systems that allows
transfer of e-cash between two parties without breaking anonymity
properties \cite{fuchsbauer2009transferable}.  Contemporary systems
that offer this type of disintermediation attract criminal
activity~\cite{richet2016extortion}.

GNU Taler specifically provides roughly the \emph{opposite} of this property,
namely \emph{income transparency}, to guarantee that e-cash is not easily
abused for tax evasion.  Mutually trusting users, however, can share ownership
of a coin.

\subsection{Atomic Swaps}

Atomic swaps (often called ``fair exchange'' in the e-cash literature) are a
feature of some e-cash systems that allows e-cash
to be exchanged against some service or (digital) product, with a trusted third
party ensuring that the payee receives the payment if and only if they correctly
provided the merchandise.

GNU Taler supports Camenisch-style atomic swaps~\cite{camenisch2007endorsed},
as explained in Section~\ref{sec:security:atomic-swaps}.

\subsection{Refunds}

GNU Taler allows merchants to provide refunds to customers during a limited
time after the coins for the payment were deposited.  The merchant signs a
statement that effectively allows the customer to reclaim a previously spent
coin.  Customers can request anonymous change for the reclaimed amount.

While this is a rather simple extension, we are not aware of any other e-cash
system that supports refunds.


\section{User Experience and Performance} \label{sec:intro:ux}

For adoption of a payment system, the user experience is critical. Thus,
before diving into {\em how} GNU Taler is implemented, we begin by 
showing how GNU Taler {\em looks} from the perspective of an end user in the
context of web payments, in a desktop browser (Chromium).

To use GNU Taler, the user must first install a browser extension
(Figure~\ref{fig:ux:install-prompt}).  Once installed, the user can
open a pop-up window by clicking on the Taler logo, to see the
initially empty wallet balance (Figure~\ref{fig:ux:installed}).

The customer logs into their online bank---a simple demo bank in our case--to
withdraw digital cash from their bank account into their wallet (Figures~%
\ref{fig:ux:bank-login} and~\ref{fig:ux:bank-profile}).  Our demo uses
\textsc{Kudos} as an imaginary currency.  Before the user is asked to confirm,
they are given the option to view details about or change the default exchange
provider, the GNU Taler payment service provider (Figure~\ref{fig:ux:select-exchange}).

With a real bank, a second factor (such as a mobile TAN) would now be requested
from the user.  Our demo instead asks the user to solve a simple CAPTCHA
(Figure~\ref{fig:ux:pin-tan}).  The amount withdrawn---minus withdrawal
fees---is now available as e-cash in the wallet (Figure~%
\ref{fig:ux:withdraw-done}).

The customer can now go to an online shop to spend their digital cash.  We've
implemented a shop that sells single chapters from Richard Stallman's essay
collection ``Free Software, Free Society'' \cite{stallman2002essays} (Figure~%
\ref{fig:ux:essay-landing}).  The user selects an essay, and is then
immediately presented with a confirmation page rendered by the wallet (Figure~\ref{fig:ux:essay-pay}).
After paying, the user can immediately read the article (Figure~\ref{fig:ux:essay-done}).

Our benchmarks, discussed in Chapter \ref{chapter:implementation} show that a
single machine can support around 1000 payments per second, and our
implementation is easily amenable to further scaling.

The extra computation required in the customer's wallet is in the order of a
few hundred milliseconds even on typical mobile or tablet devices, and thus
barely noticeable.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/wallet-install-prompt.png}
\caption{The user is prompted to install the wallet.}
\label{fig:ux:install-prompt}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/wallet-installed.png}
\caption{The wallet popup shows an empty balance.}
\label{fig:ux:installed}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/bank-login.png}
\caption{The bank asks for login details.}
\label{fig:ux:bank-login}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/bank-profile.png}
\caption{Account page of the demo bank.}
\label{fig:ux:bank-profile}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/withdraw-confirm.png}
\caption{Exchange selection dialog in the wallet.}
\label{fig:ux:select-exchange}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/pin-tan.png}
\caption{PIN/TAN dialog of the demo bank.}
\label{fig:ux:pin-tan}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/withdraw-done.png}
\caption{After a successful withdrawal, the balance is shown in the wallet.}
\label{fig:ux:withdraw-done}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/essay-landing.png}
\caption{Landing page of a store that sells essays.}
\label{fig:ux:essay-landing}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/essay-pay.png}
\caption[Payment prompt for an essay.]{Payment prompt for an essay.  Rendered by the wallet.}
\label{fig:ux:essay-pay}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=\textwidth]{taler-screenshots/essay-done.png}
\caption{Essay successfully purchased by the user.}
\label{fig:ux:essay-done}
\end{figure}

%\begin{figure}
%\begin{subfigure}{.5\textwidth}
%  \centering
%  \includegraphics[width=.8\linewidth]{taler-screenshots/wallet-installed.png}
%  \caption{1a}
%  \label{fig:sfig1}
%\end{subfigure}%
%\begin{subfigure}{.5\textwidth}
%  \centering
%  \includegraphics[width=.8\linewidth]{taler-screenshots/bank-login.png}
%  \caption{1b}
%  \label{fig:sfig2}
%\end{subfigure}
%\caption{plots of....}
%\label{fig:fig}
%\end{figure}

% FIXME: perf results

\section{The Technical Foundation: Anonymous E-Cash} \label{sec:intro:ecash}
GNU Taler is based on anonymous e-cash.  Anonymous e-cash was invented by David
Chaum in the 1980s \cite{chaum1983blind}.  The idea behind Chaumian e-cash is
both simple and ingenious, and can be best illustrated
with the carbon paper\footnote{%
  Carbon paper is a paper coated with pigment (originally carbon) on one side.
  When put face-down between two sheets of normal paper, the pressure from
  writing with a pen or typewriter on the first layer causes pigment to be
  deposited on the paper beneath, allowing a copy to be made.
} analogy:  A long, random serial number is generated, for example, by throwing
a die a few dozen times, and written on a piece of paper.  A carbon paper is
placed on top, with the pigmented side facing down, and both pieces of paper
are put into an opaque envelope.  The envelope is now sealed and brought to a
bank.  The bank draws a signature on the outside of the envelope, which presses
through to the piece of paper with the serial number.  In exchange for the
signed envelope, the bank deducts a fixed amount (say five dollars) from the
customer's bank account.  Under the (admittedly rather strong) assumption that
the bank's signature cannot be forged, the signed piece of paper with the serial
number is now an untraceable bank note worth five dollars, as the bank signed
it without seeing the serial number inside the envelope!  Since the signed
paper can be easily copied, merchants that accept it as payment must check the
bank's signature, call the bank and transmit the serial number.  The bank keeps
a register of all serial numbers that have been used as payment before.  If the
serial number is already in the bank's register, the bank informs the merchant
about the attempted double spending, and the merchant then rejects the payment.

The digital analogue of this process is called a \emph{blind signature}, where
the signer knows that it gave a digital signature, but does not know the
contents of the message that it signed.

In this document, we use \emph{coin} to refer to a token of value in an e-cash
system.  Note that the analogy of a coin does not always hold up, as certain
types of operations possible in some e-cash schemes, such as partial spending,
divisibility, etc., do not transfer to physical coins.


%\subsection{Security Properties}\label{sec:intro:security}

We have the following security and correctness properties for GNU Taler
(formally defined in Chapter~\ref{chapter:security}):
\begin{itemize}
  \item \emph{Anonymity} guarantees that transactions cannot be correlated with withdrawals or
    other transactions made by the same customer.
  \item \emph{Unforgeability} guarantees that users cannot spend more e-cash than they withdrew.
  \item \emph{Conservation} guarantees that customers do not lose money due to
    interrupted protocols or malicious merchants; they can always obtain
    anonymous change or a proof of successful spending.
  \item \emph{Income transparency} guarantees that mutually distrusting parties
    are unable to reliably transfer e-cash between them without the income of
    participants being visible to tax auditors.
\end{itemize}

While anonymity and unforgeability are common properties of e-cash, we are not
aware of any other treatments of income transparency and conservation.


\section{Distributed Ledgers} \label{sec:intro:blockchain}

The main purpose of blockchains, including those implementing
cryptocurrencies, is to maintain a distributed ledger that holds
state, together with rules on how this state can be updated.  The name
``blockchain'' derives from its structure: A list of updates
(``transactions'') is bundled into a so-called block, and each block
contains a hash of the previous block.  Cryptocurrencies use
blockchains to remember the amount of currency controlled by a
particular account ($\equiv$ private key).  Thus, while
cryptocurrencies use the term ``coin'' (creating potentially misleading associations
with cash), they actually realize a decentralized register-based
payment system with the blockchain storing the register\footnote{%
Anonymous cryotocurrencies such as ZeroCash \cite{bensasson2014zerocash}
have special accounts (called shielded addresses) that can
``hide'' their balance, and require the owner to prove in zero-knowledge that their balance is sufficient for a transaction.
As such, anonymous transactions in these systems (which are typically only a small subset of all transactions)
are closer to value-based systems.  However, currently only a small percentage ($\approx 5\%$) of
all funds in ZCash, the most widely used anonymous cryptocurrency, belong to shielded addresses (\url{https://explorer.zcha.in/statistics/value}).} using private
keys to authenticate account owners.

Cryptocurrencies based on blockchains gained immense popularity over
the last years on the promise of a universal, global and decentralized
payment system that is independent from country boundaries and
legislations.  In practice, however, current incarnations of these
technologies can only handle a handful of transactions, have high
transaction fees and are surprisingly centralized
\cite{beikverdi2015trend,bohme2015bitcoin}.  Bitcoin, the most popular
cryptocurrency, can handle around 3-7 transactions per second,
globally.  While there are various plans to make blockchains more
scalable~\cite{green2016bolt}, there is no concrete evidence that
any of them will work without further sacrificing % the existing advantages of
decentralization.


\subsection{Consensus in Decentralized Blockchains}

In decentralized blockchains, multiple parties must agree on the current state of
the ledger by agreeing on a ``head'' of the chain of blocks.  How to advance
this head to include new transactions is thus a critical design choice.

With proof-of-work blockchains such as Bitcoin, each block contains
the solution to a computationally expensive puzzle that is derived
from the contents of the block.  The block that, together with its
ancestors, contains the most expensive accumulated work (and respects
the rules of the blockchain with regards to what transactions are
valid) is considered the head of the chain.  All participants of the
network can ``mine'' a block by collecting transactions and trying to
solve the corresponding computational puzzle.  Successful miners are
rewarded with a mining reward and transaction fees. This type of
agreement on a ledger is also called ``Nakamoto Consensus'', after the
inventor of Bitcoin.  The result of the agreement is not final: if a
branch originating from an earlier block of the chain accumulates more
work, it becomes the canonical head.  While this type of consensus has
some attractive properties---there is no fixed set of members, and
remains secure as long as an adversary has less than 1/4 of
computational power \cite{eyal2018majority}---it consumes a huge amount of energy to provide
for computation of the proof-of-work puzzles.

After Bitcoin popularized the concept of blockchains, alternative consensus
mechanisms were proposed to replace or augment proof-of-work.  In
proof-of-stake blockchains, a single node is selected as a validator.  The
validator must provide a safety deposit (the ``stake''), and if any misbehavior
is detected, the safety deposit is destroyed.  If the validator behaves
correctly, they earn transaction fees and get back their safety deposit.
Currently proof-of-stake protocols are still in development, and often require
falling back to other consensus mechanisms in certain situations.

\subsection{Permissioned Blockchains}

Permissioned blockchains have a known, relatively small set of participants,
and can rely on more traditional and cheaper consensus algorithms.  When
resilience against actively malicious members is required, a so-called
Byzantine consensus protocol must be used.  Byzantine consensus protocols
typically agree on a single value at once.

In Chapter~\ref{chapter:consensus} we introduce a Byzantine consensus
algorithm that can be used to agree directly on a (super-)set of all
transaction that honest peers proposed.  This allows for
implementations of permissioned blockchains where transactions are
accumulated into blocks, and the transactions within a block are
agreed upon in a way that's asymptotically faster than agreeing on
every transaction sequentially.

This protocol could be used in the future to implement an efficient
and robust implementation of the register-based layer of a payment
system, with GNU Taler e-cash as the value-based layer above it.


\subsection{Blockchains and GNU Taler}

Blockchains today fail to satisfy most of our design goals for payment
systems.  While most blockchains are implemented as free software,
they often manage to both fail to adequately protect the privacy of
buyers {\em and} to enable the state to crack down on illegal
activities: With most non-permissioned blockchains, the transaction
history of all participants is publicly available, creating serious
privacy risks~\cite{meiklejohn2013fistful,jawaheri2018small}. At the same
time, as accounts are simply private keys, states have a hard time
tracking down users~\cite{luu2016challenge}. Design
variations that do offer reasonable privacy generally have even more
atrocious performance characteristics and create additional
traceability problems for law enforcement~\cite{bensasson2014zerocash}.
Additionally, blockchain-based cryptocurrencies suffer from usability
and performance problems.

With our BSC protocol, we focus on improving the performance of the
consensus protocol for permissioned blockchains.  Permissioned
blockchains can be given rules that enforce Know-Your-Customer (KYC)
and Anti-Money-Laundering (AML)
regulations~\cite{shrier2016blockchain}. When deployed in the
context of centrally-banked fiat currencies, such a permissioned
blockchain can then effectively recreate the semantics of a classical
distributed banking system.  As mentioned before, GNU Taler's
value-based protocol can be integrated with any kind of register-based
banking---including those based on blockchains---improving
performance and privacy for value-based transactions.

% block structure

\section{Key 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}

\section{Roadmap}

Chapter \ref{chapter:design} describes the high-level design of GNU Taler, and
compares it to payment systems found in the academic literature and real-world
usage.  Chapter \ref{chapter:security} first gives a gentle introduction to
provable security (which can be skipped by readers with a background in
cryptography), and then defines security properties for income-transparent,
anonymous e-cash.  The cryptographic protocols for GNU Taler are defined in
detail, and proofs are given that our protocols satisfy the security properties
defined earlier.  In Chapter \ref{chapter:implementation}, the implementation
of GNU Taler is described, and the performance and scalability is
evaluated.  Chapter \ref{chapter:consensus} is about the design, implementation
and evaluation of our Byzantine set union consensus protocol.  Chapter
\ref{chapter:future-work} discusses future work and missing pieces to deploy
GNU Taler in production.  Chapter \ref{chapter:conclusion} concludes with an
outlook on the potential impact and practical relevance of this work.