From baa36258d017b9f681a0ec38de30ae857bf49cc6 Mon Sep 17 00:00:00 2001
From: Florian Dold <florian.dold@gmail.com>
Date: Sun, 26 Aug 2018 04:05:31 +0200
Subject: mostly intro

---
 introduction.tex | 389 ++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 340 insertions(+), 49 deletions(-)

(limited to 'introduction.tex')

diff --git a/introduction.tex b/introduction.tex
index 293e674..ed1c7ad 100644
--- a/introduction.tex
+++ b/introduction.tex
@@ -1,68 +1,335 @@
 \chapter{Introduction}\label{chapter:introduction}
+The design of payment systems shapes economies and societies.  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 design of payment systems shapes economies and societies.  Strong,
-developed nation states have adopted highly transparent payment systems, such
-as the MasterCard and VisaCard credit card schemes and computerized bank
-transactions such as SWIFT.  These systems enable mass surveillance by both
-governments and private companies.  Aspects of this surveillance sometimes
-benefit society by providing information about tax evasion or crimes like
-extortion.
+Cryptocurrencies based on Blockchains gained immense popularity over the last
+years, and promise 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, and are suprisingly 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, there is no concrete
+evidence that any of them will work without sacrificing the existing advantages
+of decentralization.
 
-At the other extreme, weaker developing nation states have economic
-activity based largely on coins, paper money or even barter.  Here,
-the state is often unable to effectively monitor or tax economic
-activity, and this limits the ability of the state to shape the
-society.
+As the Internet has no standardized payment system, especially not one that is
+capable of instantly, efficiently and securely settling small transactions
+(so-called micropayments), most content on the Web is financed by
+advertisments.  This has not only resulted in a loss of independence of content
+providers, 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.  Ads are also a vector
+for malware \cite{provos2007ghost}.  Due to the prevalence of ad blockers, ads
+are not guaranteed to be a sustainable business model.
 
-% account vs register based
+Especially if a payment system is to be used for microtransactions for online
+content, the privacy of buyers becomes important, as 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.  With most Blockchains, the transaction
+history of all participants is publicly available.
 
-Payment systems shape our society.
+This thesis is about the design, implementation and security analysis of a
+privacy-friendly payment system that is designed to be practical for usage as
+an online (micro-)payment method, and at the same socially and ethically
+responsible.  The implementation is part of the GNU
+project\footnote{\url{http://gnu.org/}}, and called GNU Taler.
 
-Mention GDPR, data minimization
+Payment systems can generally be divided in 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 cappucchino 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, while register-based systems provide more security to customers and
+cannot be as easily used for illicit activities.
 
-blockchain + e-cash/taler as full-stack payment system that can be deployed by everybody
+With GNU Taler, we primarily focus on the token-based payment system,
+operating on top of an existing register-based system.
 
-% FIXME:  say that one payment system is not enough, coffee example
-
-% FIXME:  say why it's "GNU Taler", GNU project context
+We also discuss one component that is needed to efficiently maintain the
+transaction ledger for a register-based system in a decentralized and robust
+manner, namely a Byzantine consensus protocol.  The variation of Byzantine
+consensus, called Byzantine set union consensus (BSC), can be used (among other
+applications we discuss) to asymptotically speed up the implementation of such
+transaction ledgers, compared to classic Byzantine consensus protocols.
 
-% FIXME: demo walk-through of GNU Taler as user
 
-% FIXME:  give the whole blind sigatures as carbon paper signing analogy
+% FIXME:  I could include payment system stacks and other properties of payment systems here
 
-% FIXME: dependency graph between chapters
+% blockchain + e-cash/taler as full-stack payment system that can be deployed by everybody
 
-\section{Requirement for Payment Systems}
-(Discuss different requirements, stress that payment systems are typically
-used as stacks of multiple systems, and that no one size fits all)
+% FIXME:  say that one payment system is not enough, coffee example
 
-\section{Existing Payment Systems}
-Or:  Why another payment system?
+% FIXME: demo walk-through of GNU Taler as user
+% FIXME: gives some of the results achieved later
+% FIXME: mention the 4 security properties
 
 \section{Design Goals for GNU Taler}
+The following are the high-level design goals for our payment system.  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
 \begin{enumerate}
-  \item \textbf{GNU Taler must be implemented as free software.}
-  \item \textbf{GNU Taler must protect the privacy of buyers.}
+  \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{stallman2002free} 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 run out of business.  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 platform, and user-hostile
+    features such as tracking or telemetry can be removed from wallet software.
+
+    We furthermore note that this rules out the mandatory usage of specialized
+    hardware such as smartcards 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}
+
+    Ideally, privacy is guaranteed via technical measures, as opposed to mere
+    policies.  Especially with micropayments for online content, a
+    disproportionate of rather private data about buyers would be revealed, if
+    the payment system does not have privacy protections.
+
+    In legislations with data protection regulations (such as the recently introduced GDPR in Europe),
+    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 or theft
+    of credit card information.
+
   \item \textbf{GNU Taler must enable the state to tax income and crack down on
     illegal business activities.}
+
+    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.}
-  \item \textbf{GNU Taler must prevent payment fraud.}
+
+    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 useable for non-expert customers.  Usability also
+    applies to the integration with mechants, 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.}
+
+    This rules out the use of approaches such as proof-of-work.  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 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{Making a Payment with GNU Taler}
+\section{User Experience and Performance}
+We now show how GNU Taler works 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 \ref{fig:ux:select-exchange}.
+
+With a real bank, a second factor (such as a mobile TAN) would now 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{fix: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 chapter 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{fix: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 hundered 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 promoted to install the wallet.}
+\label{fig:ux:install}
+\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 bank.}
+\label{fig:ux:bank-profile}
+\end{figure}
+
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/withdraw-confirm.png}
+\caption{Account page of the bank.}
+\label{fig:ux:select-exchange}
+\end{figure}
 
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/pin-tan.png}
+\caption{Account page of the bank.}
+\label{fig:ux:pin-tan}
+\end{figure}
 
-\section{Features of E-Cash}
-This section discusses our requirements for a privacy-preserving e-cash system.
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/withdraw-done.png}
+\caption{Account page of the bank.}
+\label{fig:ux:pin-tan}
+\end{figure}
 
-\subsection{Change and Divisibility}
-\subsection{Offline Payments}
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/essay-landing.png}
+\caption{Account page of the bank.}
+\label{fig:ux:essay-landing}
+\end{figure}
+
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/essay-pay.png}
+\caption{Account page of the bank.}
+\label{fig:ux:essay-landing}
+\end{figure}
+
+\begin{figure}
+\centering
+\includegraphics[width=\textwidth]{taler-screenshots/essay-done.png}
+\caption{Account page of the bank.}
+\label{fig:ux:essay-landing}
+\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 Foundation of GNU Taler: Anonymous E-Cash}
+
+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 can't 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 value
+that it signed.
+
+\subsection{E-Cash Variations}
+We now give an overview on existing variations of Chaum's original protocol in the context
+of our design goals.
+
+\paragraph{Signatures vs Zero Knowledge}
+\paragraph{Change and Divisibility}
+\paragraph{Offline vs Online Payments}
 Anonymous digital cash schemes since Chaum were frequently designed
 to allow the merchant to be offline during the transaction,
 by providing a means to deanonymize customers involved in
@@ -73,38 +340,62 @@ unreliable proposition.  Worse, there are unacceptable risks that
 a customer may accidentally deanonymize herself, for example by
 double-spending a coin after restoring from backup.
 
-\subsection{Income Transparency}
-\subsection{Traceability and Anonymity Control}
-\subsection{Refunds}
-\subsection{Tipping}
-\subsection{Transferability}
-\subsection{User Suspension}
+\paragraph{Traceability and Anonymity Control}
+\paragraph{Transferability}
+\paragraph{User Suspension}
 Electronic Cash with Anonymous User Suspension
-\subsection{Recoverability}
+\paragraph{Recoverability}
 (Ecash vs off-line recovery)
 
 FIXME:  discuss ways to handle extortion / perfect crime / kidnapping
-\subsection{Atomic Swaps}
+\paragraph{Atomic Swaps}
+
+\paragraph{Refunds}
+\paragraph{Tipping}
+\paragraph{Income Transparency}
 
 \section{Contributions}
 
 \begin{itemize}
-  \item we design, implement and analyze an efficient byzantine consensus
-    protocol on set structures that allows the optimized implementation of
+  \item we design, implement and analyze an efficient Byzantine consensus
+    protocol on set structures that allows an optimized implementation of
     permissioned blockchains
-  \item Notion of income transparency, with an instantiation in chaum-style
+  \item Notion of income transparency, with an instantiation in Chaum-style
     e-cash and proofs
   \item consideration of practical aspects including aborts, network failures,
     refunds, multi-coin payments, faults from synchronization and their effects
     on anonymity; showing the necessity of a refresh operation
   \item seamless/native integration of e-cash into web architecture, discussion
     of pitfalls / security and privacy problems
-  \item implementation of Taler with performance evaluation
+  \item implementation of GNU Taler with performance evaluation
 \end{itemize}
 
-Thesis statement: Permissioned blockchains and income-transparent e-cash can be used to implement a complete (?) payment system that is efficient (?), socially responsible (in the sense of taxes), usable (has practical implementation, web integration, ...) and provides anonymity to customers.
-
 
 \section{Roadmap}
 
+Our overall thesis statement is the following:
+\begin{quote}
+  New networking and cryptograpy protocols can substantially improve electronic
+  online payment systems.  Specifically, the GNU Taler protocol provides income
+  transparency and conservation of balance in the presents of protocol aborts
+  and certain faults, and an auditor component can be used to increase the
+  robustness of the system against insider and outsider attacks.  Furthermore,
+  Byzantine Set Union Consensus can be used as a building block for a secure
+  and asymptotically efficient transaction ledger.
+\end{quote}
+
+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 in detail, 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.
 
-- 
cgit v1.2.3

