\chapter{Introduction}\label{chapter:introduction} New networking and cryptographic protocols can substantially improve electronic online payment systems. This book 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 book explains 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. GNU Taler is an official package of the GNU project\footnote{\url{https://gnu.org/}}. Our free software implementation is 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{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: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.