From 895e24872de95acf255e0746b42f0661697e7f9a Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Sun, 12 Jul 2020 18:19:17 +0200 Subject: initial import of thesis-dold --- doc/system/taler/implementation.tex | 2198 +++++++++++++++++++++++++++++++++++ 1 file changed, 2198 insertions(+) create mode 100644 doc/system/taler/implementation.tex (limited to 'doc/system/taler/implementation.tex') diff --git a/doc/system/taler/implementation.tex b/doc/system/taler/implementation.tex new file mode 100644 index 000000000..4aa1679fc --- /dev/null +++ b/doc/system/taler/implementation.tex @@ -0,0 +1,2198 @@ +\chapter{Implementation of GNU Taler}\label{chapter:implementation} + +This chapter describes the implementation of GNU Taler in detail. Concrete +design decisions, protocol details and our reference implementation are +discussed. + +We implemented the GNU Taler protocol in the context of a payment system for +the web, as shown in Figure~\ref{fig:taler-arch}. The system was designed for +real-world usage with current web technologies and within existing +financial systems. + +The following technical goals and constraints influenced the design of the +concrete protocol and implementation: +\begin{itemize} + \item The implementation should allow payments in browsers with hardened + security settings. In particular, it must be possible to make a payment + without executing JavaScript on a merchant's website and without having to + store (session-)cookies or requiring a login. + \item Cryptographic evidence should be available to all parties in case of a + dispute. + \item In addition to the guarantees provided by the GNU Taler protocol, the + implementation must take care to not introduce additional threats to + security and privacy. Features that trade privacy for convenience should + be clearly communicated to the user, and the user must have the choice to + deactivate them. Integration with the web should minimize the potential + for additional user tracking. + \item The integration for merchants must be simple. In particular, merchants + should not have to write code involving cryptographic operations or have to + manage Taler-specific secrets in their own application processes. + \item The web integration must not be specific to a single browser platform, but + instead must be able to use the lowest common denominator of what is + currently available. User experience enhancements supported for only + specific platforms are possible, but fallbacks must be provided for other + platforms. + \item URLs should be clean, user-friendly and must have the expected + semantics when sharing them with others or revisiting them after a session + expired. + \item Multiple currencies must be supported. Conversion between + different currencies is out of scope. + \item The implementation should offer flexibility with regards to what + context or applications it can be used for. In particular, the + implementation must make it possible to provide plugins for different + underlying banking systems and provide hooks to deal with different + regulatory requirements. + \item The implementation must be robust against network failures and crash + faults, and recover as gracefully as possible from data loss. Operations + must be idempotent if possible, e.g., accidentally clicking a payment button twice should + only result in one payment, and refreshing a page should not lead to + failures in the payment process. + \item Authorization should be preferred to authentication. In particular, + there should be no situations in which the user must enter confidential + information on a page that cannot be clearly identified as secure. + \item No flickering or unnecessary redirects. To complete a payment, the + number of request, especially in the user's navigation context, should be + minimized. + \item While the implementation should integrate well with browsers, it must + be possible to request and make payments without a browser. This makes at + least part of the implementation completely independent of the extremely + complex browser standards, and makes Taler usable for machine-to-machine + payments. + %\item Backwards compatibility (with what?) +\end{itemize} + +We now recapitulate how a GNU Taler payment works, with some more details +specific to the implementation. + +By instructing their bank to send money to an exchange, the customer creates a +(non-anonymous) balance, called a \emph{reserve}, at the exchange. Once the +exchange has received and processed the bank transfer, the customer's +\emph{wallet} automatically \emph{drains} the reserve by withdrawing coins from +it until the reserve is empty. Withdrawing immediately before a purchase should +be avoided, as it decreases the customer's anonymity set by creating a +correlation between the non-anonymous withdrawal and the spending. + +To withdraw coins from the exchange, the customer's wallet authenticates itself +using an Ed25519 private key for the customer's reserve. The customer must +include the corresponding reserve public key in the payment instruction from +the customer's bank to the exchange's bank that funded their reserve. With a +bank that directly supports Taler on their online banking website, this process +is streamlined for the user, since the wallet automatically creates the key +pair for the reserve and adds the public key to the payment instruction. + + +While browsing a merchant's website, the website can signal the wallet to +request a payment from a user. The user is then asked to confirm or reject this +proposal. If the user accepts, the wallet spends coins with the merchant. The +merchant deposits coins received from the customer's wallet at the exchange. +Since bank transfers are usually costly, the exchange delays and aggregates +multiple deposits into a bigger wire transfer. This allows GNU Taler to be +used even for microtransactions of amounts smaller than usually handled by the +underlying banking system. + +\begin{figure} + \includegraphics[width=\columnwidth]{taler-arch-full.pdf} + \caption[Components of GNU Taler in the context of a banking system.]{The different components of the Taler system in the + context of a banking system providing money creation, + wire transfers and authentication. (Auditor omitted.)} + \label{fig:taler-arch-full} +\end{figure} + +As shown in Figure~\ref{fig:taler-arch-full}, the merchant is internally split +into multiple components. The implementation of the Taler protocol and +cryptographic operations is isolated into a separate component, called the +\emph{merchant backend}, which the merchant accesses through an API or software +development kit (SDK) in the programming language of their choice. + +Our implementations of the exchange (70,000 LOC) and merchant backend +(20,000 LOC) are written in C using PostgreSQL as the database and +libgcrypt for cryptographic operations. The \emph{wallet} (10,000 +LOC) is implemented in TypeScript as a cross-browser extension using +the WebExtensions API, which is available for a majority of widely +used browsers. It also uses libgcrypt (compiled to JavaScript) for +cryptographic operations as the required primitives are not yet +natively supported by web browsers. Sample merchant websites (1,000 +LOC) and an example bank (2,000 LOC) with tight Taler integration are +provided in Python. + +The code is available at \url{https://git.taler.net/} and a demo +is publicly available at \url{https://demo.taler.net/}. + +\section{Overview} + +We provide a high-level overview over the implementation, +before discussing the respective components in detail. + +\subsection{Taler APIs} +The components of Taler communicate over an HTTP-based, RESTful\footnote{ +Some REST purists might disagree, because the Taler APIs do not follow +all REST principles religiously. In particular, the HATEOAS principle is not followed. +} \cite{fielding2000architectural} +API. All request payloads and responses are JSON \cite{rfc8259} documents. + +Binary data (such as key material, signatures and hashes) is encoded as a +base32-crockford \cite{crockford_base32} string. Base32-crockford is a simple, +case-insensitive encoding of binary data into a subset of the ASCII alphabet +that encodes 5 bits per character. While this is not the most space-efficient +encoding, it is relatively resilient against human transcription errors. + +Financial amounts are treated as fixed-point decimal numbers. The +implementation internally uses a pair of integers $(v,f)$ with value part $0 +\le v \le 2^{52}$ and fractional part $0 \le f < 10^8$ to represent the amount +$a = v + f\cdot 10^{-8}$. This representation was chosen as the smallest +representable amount is equal to one Satoshi (the smallest representable amount +in Bitcoin), and the largest possible value part (besides being large enough +for typical financial applications) is still accurately representable in 64-bit +IEEE 754 floating point numbers. These constraints are useful as some +languages such as JavaScript\footnote{Big integers are currently in the process +of being added to the JavaScript language standard.} provide IEEE 753 floating +point numbers as the only numeric type. More importantly, fixed-point decimal +numbers allow exact representation of decimal values (say \EUR{0.10}), which +is not possible with floating point numbers but essential in financial applications. + +Signatures are made over custom binary representations of the respective +values, prefixed with a 64-bit tag consisting of the size of the message (32 +bits) and an integer tag (32 bits) uniquely identifying the purpose of the message. +To sign a free-form JSON object, a canonical representation as a string is +created by removing all white space and sorting objects' fields. + +In the future, more space-efficient representations (such as BSON\footnote{http://bsonspec.org/} or CBOR \cite{rfc7049}) +could be used. The representation can be negotiated between client and server +in a backwards-compatible way with the HTTP ``Accept'' header. + +% signatures! + +\subsection{Cryptographic Algorithms} +The following cryptographic primitives are used by Taler: +\begin{itemize} + \item SHA512 \cite{rfc4634} as a cryptographic hash function + \item Ed25519 \cite{bernstein2006curve25519} for non-blind signing operations + \item Curve25519 \cite{bernstein2006curve25519} for the refreshing operation + \item HKDF \cite{rfc5869} as a key derivation function for the refreshing operation + \item FDH-RSA blind signatures \cite{bellare2003onemore} +\end{itemize} + +We chose these primitives as they are simple, cheap enough and relatively well +studied. Note that other signature schemes that have the syntax and properties +described in Section~\ref{sec:crypto:instantiation}, such as +\cite{boldyreva2003threshold}, could be used instead of FDH-RSA. + +\subsection{Entities and Public Key Infrastructure} + +\begin{figure} + \includegraphics[width=\textwidth]{diagrams/taler-diagram-signatures.png} + \caption[Entities/PKI in Taler]{Entities/PKI in Taler. Solid arrows denote signatures, dotted arrows denote blind signatures.} +\end{figure} + +The public key infrastructure (PKI) used by Taler is orthogonal to the PKI used +by TLS \cite{rfc5246}. While TLS is used as the transport layer for Taler API +messages, we do not rely on TLS for authenticity or integrity of API queries +and responses. We do rely on TLS for the confidentiality of digital business +contracts and the authenticity, integrity and confidentiality of digital +product delivery. For the anonymity properties to hold, the customer must +access the merchant and exchange through an anonymity layer (approximated +by practical implementations like Tor \cite{dingledine2004tor}). + +In the case of merchants, we cannot use a trusted auditor or exchange as a +trust anchor, since merchants are not required to register within our PKI to +accept Taler payments. Here we rely on TLS instead: The merchant is required +to include their Taler-specific merchant public key in their TLS certificate. +If a merchant fails to do this, the wallet will show a warning when asking the +user to confirm a payment. + +\subsubsection{Auditor} +Auditors serve as trust anchors for Taler, and are identified by a single Ed25519 public key. +Wallet implementations come with a pre-defined list of trusted auditors, similar to the certificate +store of browsers or operating systems. + +\subsubsection{Exchange} +An exchange is identified by a long term Ed25519 master key and the exchange's +base URL. The master key is used as an offline signing key, typically stored +on an air-gapped machine. API requests to the exchange are made by appending +the name of the endpoint to the base URL. + +The exchange uses the master key to sign the following data offline: +\begin{itemize} + \item The exchange's online Ed25519 signing keys. The online signing keys + are used to sign API responses from the exchange. Each signing key has a + validity period. + \item The denominations offered by the exchange (explained further in Section~\ref{sec:implementation:denoms}). + \item The bank accounts supported by the exchange (for withdrawals and deposits) and associated fees. +\end{itemize} + +% FIXME: maybe put this later? +The \texttt{/keys} HTTP endpoint of the exchange is used by wallets +and merchants to obtain the exchange's signing keys, currently offered +denominations and other details. In order to reduce traffic, clients can also +request only signing keys and denominations that were created after a specific +time. The response to \texttt{/keys} is signed by a currently active signing +key, so that customers would have proof in case the exchange gave different sets of +denomination keys to different customers in an attempt to deanonymize them. + + +\begin{figure} + \begin{multicols}{2} + \lstinputlisting[language=C,basicstyle=\ttfamily\tiny,numbers=left]{taler/snippet-keys.txt} + \end{multicols} + \caption{Example response for /keys} +\end{figure} + + +\subsubsection{Coins and Denominations}\label{sec:implementation:denoms} +Denominations are the RSA public keys used to blindly sign coins of a fixed amount, together with information about their +validity and associated fees. The following information is signed by the exchanges master key for every denomination: +\begin{itemize} + \item The RSA public key. + \item The start date, after which coins of this denomination can be withdrawn and deposited. + \item The withdraw expiration date, after which coins cannot be withdrawn anymore, must be after the start date. + \item The deposit expiration date, after which coins cannot be deposited anymore, must be after the withdraw expiration date. + \item The legal expiration date, after which the exchange can delete all records about operations with coins of this denominations, + must be (typically quite a long time!) after the deposit expiration date. + \item The fees for a withdraw, deposit, refresh and refund operation with this coin, respectively. +\end{itemize} + +\begin{figure} + \centering + \includegraphics[width=0.7\textwidth]{diagrams/taler-diagram-denom-expiration.png} + \caption{A denomination's lifetime.} +\end{figure} + +An exchange can be audited by zero, one or multiple auditors. An auditor must +monitor all denominations currently offered by the exchange, and an audit of a +subset of denominations is not intended in the current design. To allow +customers of an exchange to confirm that it is audited properly, the auditor +signs an auditing request from the exchange, containing basic information about +the exchange as well as all keys offered during the auditing period. In +addition to the full auditing request, the auditor also signs an individual +certificate for each denomination individually, allowing clients of the +exchange to incrementally verify newly offered denominations. + +\subsubsection{Merchant} +The merchant has one Ed25519 key pair that is used to sign responses to the +customer and authenticate some requests to the exchange. Depending on the +legislation that applies to a particular GNU Taler deployment, merchants might +not need to establish an a priori relationship with the exchange, but instead +send their bank account information during or after the first deposit of a +payment from a customer. + +% FIXME: we never write here that the merchant accepts payments from all trusted auditors/exchanges +% automatically +% FIXME: citation for this? +% FIXME: are there jurisdictions where KYC would apply to the exchange's customer? +In some jurisdictions, exchanges are required to follow know-your-customer +(KYC) regulations and to verify the identity of merchants \cite{arner2018identity} using that particular +exchange for deposits. Typically, the identity of a merchant only has to be +verified if a merchant exceeds a certain threshold of transactions in a given +time span. As the KYC registration process can be costly to the exchange, this +requirement is somewhat at odds with merchants accepting payments from all +exchanges audited by a trusted auditor, since KYC registration needs to be done +at every exchange separately. It is, however, unavoidable to run a legally +compliant payment system. + +A merchant is typically configured with a set of trusted auditors and +exchanges, and consequently accepts payments with coins of denominations from a +trusted exchange and denominations audited by a trusted auditor. + +In order to make the deployment of Taler easier and more secure, the parts that +deal with the merchant's private key and cryptographic operations are isolated +into a separate service (the merchant backend) with a well-defined RESTful HTTP API. +This concept is similar to payment gateways used commonly for credit card +payments. The merchant backend can be deployed on-premise by the online shop, +or run by a third party provider that is fully trusted by the merchant. + +\subsubsection{Bank} +Since the banks are third parties that are not directly part of Taler, they do +not participate directly in Taler's PKI. + +\subsubsection{Customer} +Customers are not registered with an exchange, instead they use the private +keys of reserves that they own to authenticate with the exchange. The exchange +knows the reserve's public key from the subject/instruction data of the wire +transfer. Wire transfers that do not contain a valid public key are +automatically reversed. + + +\subsection{Payments} + +\newlength{\maxheight} +\setlength{\maxheight}{\heightof{\small W}} +\newcommand{\bffmt}[1]{% + \footnotesize + \centering + \raisebox{0pt}[\maxheight][0pt]{#1}% +} + +\begin{figure} +\centering +\begin{bytefield}[bitwidth=0.2em,bitheight=3ex,boxformatting=\bffmt]{128} + \bitheader{0,31,63,95,127} \\ + \bitbox{32}{size} & \bitbox{32}{purpose} & \bitbox{64}{timestamp} \\ + \wordbox{2}{merchant public key} \\ + \wordbox{4}{contract terms hash} \\ + \bitbox{64}{deposit deadline} & \bitbox{64}{refund deadline} \\ + \wordbox{4}{KYC / account info hash} +\end{bytefield} +\caption{The contract header that is signed by the merchant.} +\end{figure} + +\begin{figure} +\centering +\begin{bytefield}[bitwidth=0.2em,bitheight=3ex,boxformatting=\bffmt]{128} + \bitheader{0,31,63,95,127} \\ + \bitbox{32}{size} & \bitbox{32}{purpose} & \bitbox{64}{timestamp} \\ + \wordbox{4}{contract header hash} \\ + \wordbox{2}{coin public key} \\ + \bitbox[lrt]{128}{contributed amount} \\ + \bitbox[lrb]{64}{} & \bitbox[ltr]{64}{} \\ + \bitbox[lrb]{128}{deposit fee} \\ +\end{bytefield} +\caption{The deposit permission signed by the customer's wallet.} +\end{figure} + + +Payments in Taler are based on \emph{contract terms}, a JSON object that +describes the subject and modalities of a business transaction. The +cryptographic hash of such a contract terms object can be used as a globally +unique identifier for the business transaction. Merchants must sign the +contract terms before sending them to the customer, allowing a customer to +prove in case of a dispute the obligations of the merchant resulting from the +payment. + +Unless a third party needs to get involved in a dispute, it is sufficient (and +desirable for data minimization) that only the merchant and the customer know +the full content of the contract terms. The exchange, however, must still +know the parts of the contract terms that specify payment modalities, such as +the refund policy, micropayment aggregation deadline and the merchant's KYC +registration data (typically a hash to prove the KYC enrollment of the +merchant). + +Thus, the merchant's signature is made over the \emph{contract header}, +which contains the contract terms hash, as well as the payment modalities. + +In addition to the data provided by the merchant, the contract terms contain a +\emph{claim\_pub} field whose value is provided by the customer. +This field is an Ed25519 public key, and the customer can use the corresponding +private key to prove that they have indeed obtained the individual contract +terms from the merchant, and did not copy contract terms that the merchant gave +to another customer. Note that this key is not a permanent identity of the +customer, but should be freshly generated for each payment. + +The signed contract header is created by the merchant's backend from an +\emph{order}, which is the ``blueprint'' for the contract terms. The order is +generated by the merchant's frontend and contains a subset of the data +contained in the contract terms. Missing data (in particular the merchant's +bank account information, public key and accepted auditors/exchanges) and +the claim public key obtained from the customer is automatically added by the merchant +backend. This allows applications to process payments without having to +specify Taler-internal details. In fact, the smallest possible order only +needs to contain two fields: the amount to be paid and a human-readable +summary of the payment's subject. + +An order contains an \emph{order ID}, which is an identifier that is unique +within a given merchant and can be a human-friendly identifier such as a +booking number. If the order ID is not manually provided, it is automatically +filled in by the merchant backend. It can be used to refer to the payment +associated with the order without knowing the contract terms hash, which is +only available once the customer has provided their claim public key. + +To initiate a payment, the merchant sends the customer an \emph{unclaimed} +contract terms URL. The customer can download and thereby claim ownership of +the contract by appending their claim public key $p$ as a query parameter to the unclaimed +contract terms URL and making an HTTP \texttt{GET} request to the resulting URL. +The customer must then verify that the resulting contract terms are signed +correctly by the merchant and that the contract terms contain their claim public key $p$. +A malicious customer could try to claim other customers' contracts by guessing +contract term URLs and appending their own claim public key. For products that have +limited availability, the unclaimed contract URL must have enough entropy so +that malicious customers are not able to guess them and claim them before the +honest customer.\footnote{Note that this URL cannot be protected by a session +cookie, as it might be requested from a different session context than the +user's browser, namely in the wallet.} + +% FIXME: put this in a sidebox? +To give an example, an online shop for concert tickets might allow users to put +themselves on a waiting list, and will send them an email once a ticket +becomes available. The contract terms URL that allows the customer to purchase +the ticket (once they have visited a link in this email), should contain an +unguessable nonce, as otherwise an attacker might be able to predict the URL +and claim the contract for the concert ticket before the customer's wallet can. + +In order to settle the payment, the customer must sign a \emph{deposit +permission} for each coin that comprises the payment. The deposit permission +is a message signed by the coin's private key, containing +\begin{itemize} + \item the amount contributed by this coin to the payment, + \item the merchant's public key + \item the contract header together with the merchant's signature on it, + \item the time at which the deposit permission was signed. +\end{itemize} + +After constructing the deposit permissions for a contract, the customer sends +them to the merchant by doing an HTTP \texttt{POST} request to the +\texttt{pay\_url} indicated by the merchant in the contract terms. The +merchant individually \emph{deposits} each deposit permission with the +exchange. + +The merchant responds with a payment confirmation to the customer after it has +successfully deposited the customer's coins with the exchange. The payment +confirmation can be used by the customer to prove that they completed the +payment before the payment deadline indicated in the contract terms. + +Note that the depositing multiple coins with the exchange deliberately does not +have transactional semantics. Instead, each coin is deposited in an individual +transaction. This allows the exchange to be horizontally scaled (as discussed +in Section~\ref{sec:implementation-improvements}) more easily, as deposit +transaction might otherwise have to span multiple database shards. + +The lack of transactional semantics, however, means that it must be possible to +recover from partially completed payments. There are several cases: If one of +the coins that the customer submitted as payment to the merchant is invalid +(e.g., because the wallet's state was restored from a backup), the customer can +re-try the partially completed payment and provide a different coin instead. +If that is not possible or desired by the customer, the merchant may voluntarily give a +refund on the coins that have been previously deposited. The reference +implementation of the merchant backend offers refunds for partially completed +payments automatically. + +% FIXME: explain why! +If refunds were disabled for the payment, the merchant does not cooperate in +giving refunds for a partially completed payment, or becomes unresponsive after +partially depositing the customer's coin, the customer has two options: They +can either complete the deposits on the merchant's behalf, and then use the +deposit permissions to prove (either to the merchant or to a court) that they +completed the payment. + +% FIXME: put this in info box? +Another possibility would be to allow customers to request refunds for partially +completed payments themselves, directly from the exchange. +This requires that the merchant additionally +includes the amount to be paid for the contract in the contract header, as the +exchange needs to know that amount to decide if a payment with multiple coins +is complete. We do not implement this approach, since it implies that the +exchange always learns the exact prices of products that the merchant sells, as +opposed to just the merchant's total revenue. + +The customer could also reveal the contract terms to the exchange to prove that +a payment is incomplete, but this is undesirable for privacy reasons, as the +exchange should not learn about the full details of the business agreement +between customer and merchant. + +\subsection{Resource-based Web Payments} +In order to integrate natively with the concepts and architecture of the web, +Taler supports paying for a web resource in the form of a URL. In fact all +Taler contract terms contain a \emph{fulfillment URL}, which identifies the +resource that is being paid for. If the customer is not paying for a digital +product (such as an movie, song or article), the fulfillment URL can point to a +confirmation page that shows further information, such as a receipt for a +donation or shipment tracking information for a physical purchase. A +fulfillment URL does not necessarily refer to a single item, but could also +represent a collection such as a shopping basket. + +The following steps illustrate a typical payment with the online shop +\nolinkurl{alice-shop.example.com}. + +\newcommand{\contl}[0]{\mbox{\textcolor{blue}{$\hookrightarrow$}\space}} + +\lstdefinelanguage{none}{ + identifierstyle= +} +\lstdefinestyle{myhttp}{ + breaklines=true, + breakindent=3em, + escapechar=*, + postbreak=\contl, + basicstyle=\ttfamily, + showspaces=true, +} + +\begin{enumerate} + \item The user opens the shop's page and navigates to a paid resource, such + as \nolinkurl{https://alice-shop.example.com/essay-24.pdf}. + \item The shop sends a response with HTTP status ``402 Payment Required'' + with the headers (\contl marks a continued line) +\begin{lstlisting}[style=myhttp] +Taler-Contract-Url: https://alice-shop.example.com/*\break\contl*contract?product=essay-24.pdf +Taler-Resource-Url: https://alice-shop.example.com/*\break\contl*essay-24.pdf +\end{lstlisting} + \item Since the user's wallet does not yet contain contract terms with the + fulfillment URL \nolinkurl{https://alice-shop.example.com/esasy-24.pdf} + that matches the resources URL, it claims the contract by generating a + claim key pair $(s, p)$ and requesting the contract URL with the claim + public key $p$ as additional parameter: + \nolinkurl{https://alice-shop.example.com/contract?product=essay-24.pdf\&claim_pub=}$p$. + \item The wallet displays the contract terms to the customer and asks them to + accept or decline. If the customer accepted the contract, the wallet sends + a payment to the merchant. After the merchant received a valid payment, + it marks the corresponding order as paid. + \item The wallet constructs the extended fulfillment URL by adding the order + id from the contract as an additional parameter and navigates the browser + to the resulting URL + \nolinkurl{https://alice-shop.example.com/esasy-24.pdf?order\_id=...}. + \item The shop receives the request to the extended fulfillment URL and + checks if the payment corresponding to the order ID was completed. In case + the payment was successful, it serves the purchased content. +\end{enumerate} + +To avoid checking the status of the payment every time, the merchant can +instead set a session cookie (signed/encrypted by the merchant) in the user's +browser which indicates that \texttt{essay-24.pdf} has been purchased. + +The resource-based payment mechanism must also handle the situation where a +customer navigates again to a resource that they already paid for, without +directly navigating to the extended fulfillment URL. In case no session cookie +was set for the purchase or the cookie was deleted / has expired, the customer would +be prompted for a payment again. To avoid this, the wallet tries to find an +existing contract whose plain fulfillment URL matches the resource URL +specified in the merchant's HTTP 402 response. If such an existing payment was +found, the wallet instead redirects the user to the extended fulfillment URL +for this contract, instead of downloading the new contract terms and prompting +for payment. + +In the example given above, the URL that triggers the payment is the same as the fulfillment URL. +This may not always the case in practice. When the merchant backend is hosted by a third +party, say \nolinkurl{https://bob.example.com/}, the page that triggers the payment +even has a different origin, i.e., the scheme, host or port may differ \cite{rfc6454}. + +This cross-origin operation presents a potential privacy risk if not +implemented carefully. +To check whether a user has already paid for a particular +resource with URL $u$, an arbitrary website could send an HTTP 402 response with +the ``Taler-Resource-Url'' header set to $u$ and the ``Taler-Contract-Url'' +set to a URL pointing to the attacker's server. If the user paid for $u$, the +wallet will navigate to the extended fulfillment URL corresponding to $u$. +Otherwise, the wallet will try to download a contract from the URL given by the +attacker. In order to prevent this attack on privacy, the wallet must only +redirect to $u$ if the origin of the page responding with HTTP 402 is the same +origin as either the $u$ or the pay URL.\footnote{This type of countermeasure is well +known in browsers as the same origin policy, as also outlined in \cite{rfc6454}.} + +\subsubsection{Loose Browser Integration}\label{sec:loose-browser-integration} + +The payment process we just described does not directly work in browsers that do not +have native Taler integration, as the browser (or at least a browser extension) +would have to handle the HTTP status code 402 and handle the Taler-specific headers correctly. +We now define a fallback, which is transparently implemented in the reference merchant backend. + +In addition to indicating that a payment is required for a resource in the HTTP status code and header, +the merchant includes a fallback URL in the body of the ``402 Payment Required'' response. This URL must have the custom URL scheme +\texttt{taler}, and contains the contract terms URL (and other Taler-specific settings normally specified in headers) +as parameters. The above payment would include a link (labled, e.g., ``Pay with GNU Taler'') to the following URL, encoding +the same information as the headers: +\begin{lstlisting}[style=myhttp] +taler:pay?*\break\contl*contract_url=*\break\contl*https%3A%2F%2Falice-shop.example.com%2Fcontract%3Fproduct%3Dessay-24.pdf*\break\contl*&resource_url=*\break\contl*https%3A%2F%2Falice-shop.example.com%2Fessay-24.pdf +\end{lstlisting} + +This fallback can be disabled for requests from user agents that are known to +natively support GNU Taler. + +GNU Taler wallet applications register themselves as a handler for the +\texttt{taler} URI scheme, and thus following a \texttt{taler:pay} link opens +the dedicated wallet, even if GNU Taler is not supported by the browser or a +browser extension. Registration a custom protocol handler for a URI scheme is +possible on all modern platforms with web browsers that we are aware of. + +Note that wallets communicating with the merchant do so from a different +browsing context, and thus the merchant backend cannot rely on cookies that +were set in the customer's browser when using the shop page. + +We chose HTTP headers as the primary means of signaling to the wallet (instead +of relying on, e.g., a new content media type), as it allows the fallback content +to be an HTML page that can be rendered by all browsers. Furthermore, +current browser extension mechanism allow intercepting headers synchronously +before the rendering of the page is started, avoiding visible flickering caused by +intermediate page loads. + +\subsection{Session-bound Payments and Sharing} +As we described the payment protocol so far, an extended fulfillment URL +is +not bound to a browser session. When sharing an extended fulfillment +URL, another user would get access to the same content. This might be appropriate +for some types of fulfillment pages (such as a donation receipt), but is generally not +appropriate when digital content is sold. Even though it is trivial to share digital content +unless digital restrictions management (DRM) is employed, the ability to share +links might set the bar for sharing too low. + +While the validity of a fulfillment URL could be limited to a certain time, +browser session or IP address, this would be too restrictive for scenarios where +the user wants to purchase permanent access to the content. + +As a compromise, Taler provides \emph{session-bound} payments. For +session-bound payments, the seller's website assigns the user a random session +ID, for example, via a session cookie. The extended fulfillment URL for +session-bound payments is constructed by additionally specifying the URL +parameter \texttt{session\_sig}, which contains proof that the user completed +(or re-played) the payment under their current session ID. + +To initiate a session-bound payment, the HTTP 402 response must additionally +contain the ``Taler-Session-Id'' header, which will cause the wallet to +additionally obtain a signature on the session ID from the merchant's pay URL, +by additionally sending the session ID when executing (or re-playing) the +payment. +As an optimization, instead of re-playing the full payment, the wallet can also +send the session ID together with the payment receipt it obtained from the +completed payment with different session ID. + +Before serving paid content to the user, the merchant simply checks if the +session signature matches the assigned session and contract terms. To simplify +the implementation of the frontend, this signature check can be implemented as +a request to the GNU Taler backend. Using session signatures instead of storing +all completed session-bound payments in the merchant's database saves storage. + +While the coins used for the payment or the payment receipt could be shared +with other wallets, it is a higher barrier than just sharing a URL. Furthermore, the +merchant could restrict the rate at which new sessions can be created for the +same contract terms and restrict a session to one IP address, limiting sharing. + +For the situation where a user accesses a session-bound paid resource and +neither has a corresponding contract in their wallet nor does the merchant +provide a contract URL to buy access to the resource, the merchant can specify +an \emph{offer URL} in the ``Taler-Offer-Url'' header. If the wallet is not +able to take any other steps to complete the payment, it will redirect the user +to the offer URL. As the name suggests, the offer URL can point to a page with +alternative offers for the resource, or some other explanation as to why the +resource is not available anymore. + +\subsection{Embedded Content} +So far we only considered paying for a single, top-level resource, +namely the fulfillment URL. In practice, however, websites are composed of +many subresources such as embedded images and videos. + +We describe two techniques to ``paywall'' subresources behind a GNU Taler +payment. Many other approaches and variations are possible. +\begin{enumerate} + \item Visiting the fulfillment URL can set a session cookie. When a + subresource is requested, the server will check that the customer has the + correct session cookie set. + \item When serving the fulfillment page, the merchant can add an additional + authentication token to the URLs of subresources. When the subresource is + requested, the validity of the authentication token is checked. If the + merchant itself (instead of a Content Delivery Network that supports token + authentication) is serving the paid subresource, the order ID and session + signature can also be used as the authentication token. +\end{enumerate} + +It would technically be possible to allow contract terms to refer to multiple +resources that are being purchased by including a list or pattern that defines +a set of URLs. The browser would then automatically include information to +identify the completed payment in the request for the subresource. We +deliberately do not implement this approach, as it would require deeper +integration in the browser than possible on many platforms. If not restricted +carefully, this feature could also be used as an additional method to track the +user across the merchant's website. + +\subsection{Contract Terms} +The contract terms, only seen by the customer and the merchant (except when a tax audit of the merchant is requested) +contain the following information: +\begin{itemize} + \item The total amount to be paid, + \item the \texttt{pay\_url}, an HTTP endpoint that receives the payment, + \item the deadline until the merchant accepts the payment (repeated in the signed contract header), + \item the deadline for refunds (repeated in the signed contract header), + \item the claim public key provided by the customer, used to prove they have claimed the contract terms, + \item the order ID, which is a short, human-friendly identifier for the contract terms within + the merchant, + \item the \texttt{fulfillment\_url}, which identifies the resources that is being paid for, + \item a human-readable summary and product list, + \item the fees covered by the merchant (if the fees for the payment exceed this value, the + customer must explicitly pay the additional fees), + \item depending on the underlying payment system, KYC registration information + or other payment-related data that needs to be passed on to the exchange (repeated in the signed contract header), + \item the list of exchanges and auditors that the merchants accepts for the payment, + \item information about the merchant, including the merchant public key and contact information. +\end{itemize} + + +\subsection{Refunds} +By signing a \emph{refund permission}, the merchant can ``undo'' a deposit on a +coin, either fully or partially. The customer can then spend (or refresh) the +refunded value of the coin again. A refund is only possible before the refund +deadline (specified in the contract header). After the refund deadline has +passed (and before the deposit deadline) the exchange makes a bank transfer the +merchant with the aggregated value from deposits, a refund after this point +would require a bank transfer back from the merchant to the exchange. + +Each individual refund on each coin incurs fees; the +refund fee is subtracted from the amount given back to the customer and kept by +the exchange. + +Typically a refund serves either one of the following purposes: +\begin{itemize} + \item An automatic refund is given to the customer when a payment only + partially succeeded. This can happen when a customer's wallet accidentally + double-spends, which is possible even with non-malicious customers and caused by data + loss or delayed/failed synchronization between the same user's wallet on + multiple devices. In these cases, the user can choose to re-try the + payment with different, unspent coins (if available) or to ask for a refund + from the merchant. + \item A voluntary refund can be given at the discretion of the merchant, + for example, when the customer is not happy with their purchase. +\end{itemize} +Refunds require a signature by the merchant, but no consent from the customer. + +A customer is notified of a refund with the HTTP 402 Payment Required status +code and the ``Taler-Refund'' header. The value of the refund header is a +URL. An HTTP \texttt{GET} request on that URL will return a list of refund confirmations that the +merchant received from the exchange. + +\subsection{Tipping} +Tipping in Taler uses the ``withdraw loophole'' (see \ref{taler:design:tipping}) to allow the +merchant\footnote{We still use the term ``merchant'', since donations use the same software component +as the merchant, but ``donor'' would be more accurate.} to donate small amounts (without any associated contract terms or legal +obligations) into the user's wallet. + +To be able to give tips, the merchant must create a reserve with an exchange. The reserve private key +is used to sign blinded coins generated by the user that is being given the tip. + +The merchant triggers the wallet by returning an HTTP 402 Payment Required +response that includes the ``Taler-Tip'' header. The value of the tip header (called the +tip token) contains +\begin{itemize} + \item the amount of the tip, + \item the exchange to use, + \item a URL to redirect after processing the tip, + \item a deadline for picking up the tip, + \item a merchant-internal unique ID for the tip, and + \item the \emph{pickup URL} for the tip. +\end{itemize} +Upon receiving the tip token, the wallet creates coin planchets that sum up to at most +the amount specified in the tip token, with denominations offered by the exchange specified in the tip token. + +The list of planchets is then sent to the merchant via an HTTP \texttt{POST} +request to the tip-pickup URL. The merchant creates a withdrawal confirmation +signature for each planchet, using the private key of the tipping reserve, and +responds to the HTTP \texttt{POST} request with the resulting list of +signatures. The user then uses these signatures in the normal withdrawal +protocol with the exchange to obtain coins ``paid for'' by the merchant, but +anonymized and only spendable by the customer. + + +\section{Bank Integration} +In order to use Taler for real-world payments, it must be integrated with the +existing banking system. Banks can choose to tightly integrate with Taler and +offer the ability to withdraw coins on their website. Even existing banks can +be used to withdraw coins via a manual bank transfer to the exchange, with the +only requirement that the 52 character alphanumeric, case-insensitive encoding +of the reserve public key can be included in the transaction without +modification other than case folding and white space +normalization.\footnote{Some banking systems specify that the subject of the +can be changed, and provide an additional machine-readable ``instruction'' +field. } + +\subsection{Wire Method Identifiers}\label{implementation:wire-method-identifiers} +We introduce a new URI scheme \texttt{payto}, which is used in Taler to +identify target accounts across a wide variety of payment systems with uniform +syntax. + +In in its simplest form, a \texttt{payto} URI identifies one account of a particular payment system: + +\begin{center} + \texttt{'payto://' TYPE '/' ACCOUNT } +\end{center} + +When opening a \texttt{payto} URI, the default action is to open an application +that can handle payments with the given type of payment system, with the target +account pre-filled. In its extended form, a \texttt{payto} URL can also specify +additional information for a payment in the query parameters of the URI. + +In the generic syntax for URIs, the payment system type corresponds to the +authority, the account corresponds to the path, and additional parameters for +the payment correspond to the query parameters. Conforming to the generic URI +syntax makes parsing of \texttt{payto} URIs trivial with existing parsers. + +Formally, a \texttt{payto} URI is an encoding of a partially filled out pro +forma invoice. The full specification of the \texttt{payto} URI is RFC XXXX. % FIXME! + +In the implementation of Taler, \texttt{payto} URIs are used in various places: +\begin{enumerate} + \item The exchange lists the different ways it can accept money as \texttt{payto} URIs. + If the exchange uses payment methods that do not have tight Taler integration. + \item In order to withdraw money from an exchange that uses a bank account type that + does not typically have tight Taler integration, the wallet can generate a link and a QR code + that already contains the reserve public key. When scanning the QR code with a mobile device that + has an appropriate banking app installed, a bank transfer form can be pre-filled and the user only has to confirm the + transfer to the exchange. + \item The merchant specifies the account it wishes to be paid on as a \texttt{payto} URI, both in + the configuration of the merchant backend as well as in communication with the exchange. +\end{enumerate} + +A major advantage of encoding payment targets as URIs is that URI schemes can be registered +with an application on most platforms, and will be ``clickable'' in most applications and open the right +application when scanned as a QR code. This is especially useful for the first use case listed above; the other use cases +could be covered by defining a media type instead \cite{rfc6838}. + +% FIXME: put into side box +As an example, the following QR code would open a banking application that supports SEPA payments, +pre-filled with a 15\EUR{} donation to the bank account of GNUnet: + +\begin{center} +\qrcode[hyperlink,height=5em]{payto://sepa/DE67830654080004822650?amount=EUR:15} +\end{center} + +\subsection{Demo Bank} +For demonstration purposes and integration testing, we use our toy bank +implementation\footnote{\url{https://git.taler.net/bank.git}}, which might be +used in the future for regional currencies or accounting systems (e.g., for a +company cafeteria). The payment type identifier is \texttt{taler-bank}. The +authority part encodes the base URL of the bank, and the path must be the +decimal representation of a single integer between $1$ and $2^{52}$, denoting +the internal demo bank account number. + +\subsection{EBICS and SEPA} +The Electronic Banking Internet Communication Standard\footnote{\url{http://www.ebics.org}} (EBICS) is a standard +for communicating with banks, and is widely used in Germany, France and +Switzerland, which are part of the Single European Payment Area (SEPA). EBICS +itself is just a container format. A commonly supported payload for EBICS is +ISO 2022, which defines messages for banking-related business processes. + +Integration of GNU Taler with EBICS is currently under development, and would +allow Taler to be easily deployed in many European countries, provided that the +exchange provider can obtain the required banking license. + +\subsection{Blockchain Integration} +Blockchains such as Bitcoin could also be used as the underlying financial +system for GNU Taler, provided that merchants and customers trust the exchange to be honest. + +With blockchains that allow more complex smart contracts, the auditing +functionality could be implemented by the blockchain itself. In particular, +the exchange can be incentivized to operate correctly by requiring an initial +safety deposit to the auditing smart contract, which is distributed to +defrauded participants if misbehavior of the exchange is detected. + +\section{Exchange} + +\begin{figure} + \includegraphics[width=\textwidth]{diagrams/taler-diagram-exchange.png} + \caption{Architecture of the exchange reference implementation} +\end{figure} + +The exchange consists of three independent processes: +\begin{itemize} + \item The \texttt{taler-exchange-httpd} process handles HTTP requests from clients, + mainly merchants and wallets. + \item The \texttt{taler-exchange-wirewatch} process watches for wire transfers + to the exchange's bank account and updates reserves based on that. + \item The \texttt{taler-exchange-aggregator} process aggregates outgoing transactions + to merchants. +\end{itemize} +All three processes exchange data via the same database. Only +\texttt{taler-exchange-httpd} needs access to the exchanges online signing keys +and denomination keys. + +The database is accessed via a Taler-specific database abstraction layer. +Different databases can be supported via plugins; at the time of writing this, +only a PostgreSQL plugin has been implemented. + +Wire plugins are used as an abstraction to access the account layer that Taler +runs on. Specifically, the \textit{wirewatch} process uses the plugin to monitor +incoming transfers, and the aggregator process uses the wire plugin to make +wire transfers to merchants. + +The following APIs are offered by the exchange: +\begin{description} + \item[Announcing keys, bank accounts and other public information] The + exchange offers the list of denomination keys, signing keys, auditors, + supported bank accounts, revoked keys and other general information needed + to use the exchange's services via the \texttt{/keys} and \texttt{/wire} + APIs. + \item[Reserve status and withdrawal] After having wired money to the exchange, + the status of the reserve can be checked via the \texttt{/reserve/status} API. Since + the wire transfer usually takes some time to arrive at the exchange, wallets should periodically + poll this API, and initiate a withdrawal with \texttt{/reserve/withdraw} once the exchange received the funds. + \item[Deposits and tracking] Merchants transmit deposit permissions they have received from customers + to the exchange via the \texttt{/deposit} API. Since multiple deposits are aggregated into one wire transfer, + the merchant additionally can use the exchange's \texttt{/track/transfer} API that returns the list of deposits for an + identifier included in the wire transfer to the merchant, as well as the \texttt{/track/transaction} API to look up + which wire transfer included the payment for a given deposit. + \item[Refunds] The refund API (\texttt{/refund}) can ``undo'' a deposit if the merchant gave their signature, and the aggregation deadline + for the payment has not occurred yet. + \item[Emergency payback] The emergency payback API (\texttt{/payback}) allows customers to be compensated + for coins whose denomination key has been revoked. Customers must send either a full withdrawal transcript that + includes their private blinding factor, or a refresh transcript (of a refresh that had the revoked denominations as one of the targets) + that includes blinding factors. In the former case, the reserve is credited, in the latter case, the source coin of the + refresh is refunded and can be refreshed again. +\end{description} + +New denomination and signing keys are generated and signed with the exchange's master +secret key using the \texttt{taler-exchange-keyup} utility, according to a key schedule +defined in the exchange's configuration. This process should be done on an air-gapped +offline machine that has access to the exchange's master signing key. + +Generating new keys with \texttt{taler-exchange-keyup} also generates an +auditing request file, which the exchange should send its auditors. The auditors then +certify these keys with the \texttt{taler-auditor-sign} tool. + +\begin{figure} + \includegraphics[width=\textwidth]{diagrams/taler-diagram-keyup.png} + \caption{Data flow for updating the exchange's keys.} + \label{figure:keyup} +\end{figure} + +This process is illustrated in Figure~\ref{figure:keyup}. + +\section{Auditor} +The auditor consists of two processes that are regularly run and generate +auditing reports. Both processes access the exchange's database, either +directly (for exchange-internal auditing as part if its operational security) +or over a replica (in the case of external auditors). + +The \texttt{taler-wire-auditor} process checks that the incoming and outgoing +transfers recorded in the exchange's database match wire transfers of the +underlying bank account. To access the transaction history (typically recorded +by the bank), the wire auditor uses a wire plugin, with the same interface and +implementation as the exchange's wire plugins. + +The \texttt{taler-auditor} process generates a report with the following information: +\begin{itemize} + \item Do the operations stored in a reserve's history match the reserve's balance? + \item Did the exchange record outgoing transactions to the right merchant for + deposits after the deadline for the payment was reached? + \item Do operations recorded on coins (deposit, refresh, refund) match the remaining + value on the coin? + \item Do operations respect the expiration of denominations? + \item For a denomination, is the number of pairwise different coin public + keys recorded in deposit/refresh operations smaller or equal to the number + of blind signatures recorded in withdraw/refresh operations? + If this invariant is violated, the corresponding denomination must be revoked. + %\item Are signatures made by the exchange correct? (no, apparently we don't store signatures) + \item What is the income if the exchange from different fees? +\end{itemize} + +The operation of both auditor processes is incremental. There is a separate +database to checkpoint the auditing progress and to store intermediate results +for the incremental computation. Most database tables used by the exchange are +append-only: rows are only added but never removed or changed. Tables that +are destructively modified by the exchange only store cached computations based +on the append-only tables. Each append-only table has a monotonically +increasing row ID. Thus, the auditor's checkpoint simply consists of the set of +row IDs that were last seen. + +The auditor exposes a web server with the \texttt{taler-auditor-httpd} process. +Currently, it only shows a website that allows the customer to add the auditor +to the list of trusted auditors in their wallet. In future versions, the +auditor will also have HTTP endpoints that allow merchants to submit samples of +deposit confirmations, which will be checked against the deposit permissions in +the exchange's database to detect compromised signing keys or missing writes. +Furthermore, in deployments that require the merchant to register with the +exchange beforehand, the auditor also offers a list of exchanges it audits, so that +the merchant backend can automatically register with all exchanges it transitively trusts. + +\section{Merchant Backend} +\begin{figure} + \includegraphics[width=\textwidth]{diagrams/taler-diagram-merchant.png} + \caption{Architecture of the merchant reference implementation} +\end{figure} + +The Taler merchant backend is a component that abstracts away the details of +processing Taler payments and provides a simple HTTP API. The merchant backend +handles cryptographic operations (signature verification, signing), secret +management and communication with the exchange. + +The backend API\footnote{See \url{https://docs.taler.net/api/} for the full documentation} +is divided into two types of HTTP endpoints: +\begin{enumerate} + \item Functionality that is accessed internally by the merchant. These APIs typically + require authentication and/or are only accessible from within the private + network of the merchant. + \item Functionality that is exposed publicly on the Internet and accessed by the customer's wallet and browser. + % FIXME: talk about proxying +\end{enumerate} + +A typical merchant has a \emph{storefront} component that customers visit with +their browser, as well as a \emph{back office} component that allows the +merchant to view information about payments that customers made and that integrates +with other components such as order processing and shipping. + +\subsection{Processing payments}\label{sec:processing-payments} +To process a payment, the storefront first instructs the backend to create an +\emph{order}. The order contains information relevant to the purchase, and is +in fact a subset of the information contained in the contract terms. The +backend automatically adds missing information to the order details provided by +the storefront. The full contract terms can only be signed once the customer +provides the claim public key for the contract. + +Each order is uniquely identified by an order ID, which can be chosen by the +storefront or automatically generated by the backend. + +The order ID can be used to query the status of the payment. If the customer +did not pay for an order ID yet, the response from the backend includes a +payment redirect URL. The storefront can redirect the customer to this +payment redirect URL; visiting the URL will trigger the customer's +browser/wallet to prompt for a payment. + +To simplify the implementation of the storefront, the merchant backend can +serve a page to the customer's browser that triggers the payment via the HTTP +402 status code and the corresponding headers, and provides a fallback (in the +form of a \texttt{taler:pay} link) for loosely integrated browsers. +When checking the status of a payment that is not settled yet, the response from the merchant backend +will contains a payment redirect URL. The storefront redirects the browser to this URL, +which is served by the merchant backend and triggers the payment. + +The code snippet shown in Figure~\ref{fig:merchant-donations-code} implements +the core functionality of a merchant frontend that prompts the customer for a +donation (upon visiting \texttt{/donate} with the right query parameters) and +shows a donation receipt on the fulfillment page with URL \texttt{/receipt}. +The code snippet is written in Python and uses the Flask library\footnote{\url{http://flask.pocoo.org/}} to process HTTP requests. +The helper functions \texttt{backend\_post} +and \texttt{backend\_get} make an HTTP \texttt{POST}/\texttt{GET} request to the merchant backend, respectively, +with the given request body / query parameters. + +\begin{figure} +\lstinputlisting[language=Python,basicstyle=\footnotesize]{snippets/donations.py} +\caption[Code snippet for merchant frontend]{Code snippet with core functionality of a merchant frontend to accept donations.} +\label{fig:merchant-donations-code} +\end{figure} + + +\subsection{Back Office APIs} +The back office API allows the merchant to query information about the history +and status of payments, as well as correlate wire transfers to the merchant's +bank account with the respective GNU Taler payment. This API is necessary to +allow integration with other parts of the merchant's e-commerce infrastructure. + +%\subsection{Instances} +%Merchant instances allow one deployment of the merchant backend to host more +%than one logical merchant. + +\subsection{Example Merchant Frontends} +We implemented the following applications using the merchant backend API. + +\begin{description} + \item[Blog Merchant] The blog merchant's landing page has a list of article titles with a teaser. + When following the link to the article, the customer is asked to pay to view the article. + \item[Donations] The donations frontend allows the customer to select a project to donate to. + The fulfillment page shows a donation receipt. + \item[Codeless Payments] The codeless payment frontend is a prototype for a + user interface that allows merchants to sell products on their website + without having to write code to integrate with the merchant backend. + Instead, the merchant uses a web interface to manage products and their + available stock. The codeless payment frontend then creates an HTML snippet with a payment + button that the merchant can copy-and-paste integrate into their storefront. + \item[Survey] The survey frontend showcases the tipping functionality of GNU Taler. + The user fills out a survey and receives a tip for completing it. + \item[Back office] The example back-office application shows the history and + status of payments processed by the merchant. +\end{description} + +The code for these examples is available at \url{https://git.taler.net/} in the +repositories \texttt{blog}, \texttt{donations}, \texttt{codeless}, \texttt{survey} +and \texttt{backoffice} respectively. + +\section{Wallet} +\begin{figure} + \includegraphics[width=\textwidth]{diagrams/taler-diagram-wallet.png} + \caption{Architecture of the wallet reference implementation} +\end{figure} + +The wallet manages the customer's reserves and coins, lets the customer view +and pay for contracts from merchants. It can be seen in operation in +Section~\ref{sec:intro:ux}. + +The reference implementation of the GNU Taler wallet is written in the +TypeScript language against the WebExtension API% +\footnote{\url{https://developer.mozilla.org/en-US/docs/Mozilla/Add-ons/WebExtensions}}, a cross-browser mechanism for +browser extensions. The reference wallet is a ``tightly integrated'' wallet, as it directly hooks into +the browser to process responses with the HTTP status code ``402 Payment Required''. + +Many cryptographic operations needed to implement the wallet are not commonly +available in a browser environment. We cross-compile the GNU Taler utility +library written in C as well as its dependencies (such as libgcrypt) to asm.js +(and WebAssembly on supported platforms) using the LLVM-based emscripten +toolchain \cite{zakai2011emscripten}. + +Cryptographic operations run in an isolated process implemented as a +WebWorker.\footnote{\url{https://html.spec.whatwg.org/}} This design allows +the relatively slow cryptographic operations to run concurrently in the +background in multiple threads. Since the crypto WebWorkers are started on-demand, +the wallet only uses minimal resources when not actively used. + +\subsection{Optimizations}\label{sec:wallet-optimizations} +To improve the perceived performance of cryptographic operations, +the wallet optimistically creates signatures in the background +while the user is looking at the ``confirm payment'' dialog. If the user does +not accept the contract, these signatures are thrown away instead of being sent +to the merchant. This effectively hides the latency of the +most expensive cryptographic operations, as they are done while the user +consciously needs to make a decision on whether to proceed with a payment. + + +\subsection{Coin Selection} +The wallet hides the implementation details of fractionally spending different +denomination from the user, and automatically selects which denominations to +use for withdrawing a given amount, as well as which existing coins to +(partially) spend for a payment. + +Denominations for withdrawal are greedily selected, starting with the largest +denomination that fits into the remaining amount to withdraw. Coin selection +for spending proceeds similarly, but first checks if there is a single coin +that can be partially spent to cover the whole amount. After each payment, the +wallet automatically refreshes coins with a remaining amount large enough to be +refreshed. We discuss a simple simulation of the current coin selection algorithm +in Section~\ref{sec:coins-per-transaction}. + +A more advanced coin selection would also consider the fee structure of the +exchange, minimizing the number of coins as well as the fees incurred by the +various operations. The wallet could additionally learn typical amounts that +the user spends, and adjust withdrawn denominations accordingly to further +minimize costs. An opposing concern to the financial cost is the anonymity of +customers, which is improved when the spending behavior of wallets is as +similar as possible. + +% FIXME: what about anonymity effects of coin selection? + +\subsection{Wallet Detection} +When websites such as merchants or banks try to signal the Taler wallet---for example, +to request a payment or trigger reserve creation---it is possible that the +customer simply has no Taler wallet installed. To accommodate for this situation in a +user-friendly way, the HTTP response containing signaling to wallet should +contain as response body an HTML page with (1) a \texttt{taler:} link to +manually open loosely integrated wallets and (2) instructions on how to install +a Taler wallet if the user does not already have one. + +It might seem useful to dynamically update page content depending on whether +the Taler wallet is installed, for example, to hide or show a ``Pay with Taler'' +or ``Withdraw to Taler wallet'' option. This functionality cannot be provided +in general, as only the definitive presence of a wallet can be detected, but +not its absence when the wallet is only loosely integrated in the user's +browser via a handler for the \texttt{taler:} URI scheme. + +We nevertheless consider the ability to know whether a customer has definitely +installed a Taler wallet useful (if only for the user to confirm that the +installation was successful), and expose two APIs to query this. The first one +is JavaScript-based and allows to register a callback for the when +presence/absence of the wallet is detected. The second method works without +any JavaScript on the merchant's page, and uses CSS~\cite{sheets1998level} to dynamically show/hide +element on the page marked with the special \texttt{taler-installed-show} and +\texttt{taler-installed-hide} CSS classes, whose visibility is changed when +a wallet browser extension is loaded. + +Browser fingerprinting \cite{mulazzani2013fast} is a concern with any +additional APIs made available to websites, either by the browser itself or by +browser extensions. Since a website can simply try to trigger a payment to +determine whether a tightly integrated Taler wallet is installed, one bit of +additional fingerprinting information is already available through the usage of +Taler. The dynamic detection methods do not, however, expose any information +that is not already available to websites by signaling the wallet through HTTP +headers. + +\subsection{Backup and Synchronization} +While users can manually import and export the state of the wallet, at the time +of writing this, automatic backup and synchronization between wallets is not +implemented yet. We discuss the challenges with implementing backup and +synchronization in a privacy-preserving manner in +Chapter~\ref{sec:future-work-backup-sync}. + + +\subsection{Wallet Liquidation} +If a customer wishes to stop using GNU Taler, they can deposit the remaining +coins in their wallet back to their own bank account. We call this process +\emph{liquidation}. + +In deployments with relatively lenient KYC regulation, the normal deposit +functionality used by merchants is used for wallet liquidation. The wallet +simply acts as a merchant for one transaction, and asks the exchange to deposit +the coins into the customer's bank account. + +However in deployments with strict KYC regulations, the customer would first +have to register and complete a KYC registration procedure with the exchange. +To avoid this, liquidation can be implemented as a modified deposit, which +restricts the payment to the bank account that was used to create a reserve of +the customer. + +The exchange cannot verify that a coin that is being liquidated actually +originated the reserve that the customer claims it originated from, unless the +user reveals the protocol transcripts for withdrawal and refresh operations on +that coin, violating their privacy. Instead, each reserve tracks the amount +that was liquidated into it, and the exchange rejects a liquidation request if +the liquidated amount exceeds the amount that was put into the reserve. Note +that liquidation does not refill the funds of a reserve, but instead triggers a +bank transfer of the liquidated amount to the bank account that +created the reserve. + + +\subsection{Wallet Signaling} +We now define more precisely the algorithm that the wallet executes when a +website signals to that wallet that an operation related to payments should be +triggered, either by opening a \texttt{taler:pay} URL or by responding +with HTTP 402 and at least one Taler-specific header. + +% FIXME: need to specify what happens when gateway_origin="", for example when triggered +% via URL +The steps to process a payment trigger are as follows. The algorithm takes the +following parameters: \texttt{current\_url} (the URL of the page that +raises the 402 status or \texttt{null} if triggered by a \texttt{taler:pay} URL), +\texttt{contract\_url}, \texttt{resource\_url}, \texttt{session\_id}, +\texttt{offer\_url}, \texttt{refund\_url}, \texttt{tip\_token} (from the +``Taler-\dots'' headers or \emph{taler:pay} URL parameters respectively) +\begin{enumerate} + \item If \texttt{resource\_url} a non-empty string, set \texttt{target\_url} to \texttt{resource\_url}, + otherwise set \texttt{target\_url} to \texttt{current\_url}. + \item If \texttt{target\_url} is empty, stop. + \item If there is an existing payment $p$ whose + fulfillment URL equals \texttt{target\_url} and either \texttt{current\_url} is \texttt{null} + or \texttt{current\_url} has the same origin as + either the fulfillment URL or payment URL in the contract terms, then: + \begin{enumerate}[label*=\arabic*.] + \item If \texttt{session\_id} is non-empty and the last session ID for payment $p$ was recorded + in the wallet with session signature $sig$, construct a fulfillment instance URL from $sig$ + and the order ID of $p$. + \item Otherwise, construct an extended fulfillment URL from the order ID of $p$. + \item Navigate to the extended fulfillment URL constructed in the previous step and stop. + \end{enumerate} + \item If \texttt{contract\_url} is a non-empty URL, execute the steps for + processing a contract URL (with \texttt{session\_id}) and stop. + \item If \texttt{offer\_url} is a non-empty URL, navigate to it and stop. + \item If \texttt{refund\_url} is a non-empty URL, process the refund and stop. + \item If \texttt{tip\_url} is a non-empty URL, process the tip and stop. +\end{enumerate} + +For interactive web applications that request payments, such as games or single +page apps (SPAs), the payments initiated by navigating to a page with HTTP +status code 402 are not appropriate, since the state of the web application is +destroyed by the navigation. Instead the wallet can offer a JavaScript-based +API, exposed as a single function with a subset of the parameters of the +402-based payment: \texttt{contract\_url}, \texttt{resource\_url}, +\texttt{session\_id} \texttt{refund\_url}, \texttt{offer\_url}, +\texttt{tip\_token}. Instead of navigating away, the result of the operation +is returned as a JavaScript promise (either a payment receipt, refund +confirmation, tip success status or error). If user input is required (e.g., to +ask for a confirmation for a payment), the page's status must not be destroyed. +Instead, an overlay or separate tab/window displays the prompt to the user. +% FIXME: should be specify the full algorithm for JS payments? + +% FIXME talk about clickjacking + + + +\newcommand\inecc{\in \mathbb{Z}_{|\mathbb{E}|}} +\newcommand\inept{\in {\mathbb{E}}} +\newcommand\inrsa{\in \mathbb{Z}_{|\mathrm{dom}(\FDH_K)|}} + +\section{Cryptographic Protocols} + +\def\HKDF{\textrm{HKDF}} +\def\KDF{\textrm{KDF}} +\def\FDH{\textrm{FDH}} +\newcommand{\iseq}{\stackrel{?}{=}} +\newcommand{\iseqv}{\stackrel{?}{\equiv}} +\newcommand{\pccheck}{\mathbf{check}\ } + +In this section, we describe the main cryptographic protocols for Taler in more +detail. The more abstract, high-level protocols from +Section~\ref{sec:crypto:instantiation} are instantiated and and embedded in +concrete protocol diagrams that can hopefully serve as a reference for +implementors. + +For ease of presentation, we do not provide a bit-level description of the +cryptographic protocol. Some details from the implementation are left out, +such as fees, additional timestamps in messages and checks for the expiration +of denominations. Furthermore, we do not specify the exact responses in the +error cases, which in the actual implementation should include signatures that +could be used during a legal dispute. Similarly, the actual implementation +contains some additional signatures on messages sent that allow to prove to a +third party that a participant did not follow the protocol. + +As we are dealing with financial transactions, we explicitly describe whenever +entities need to safely write data to persistent storage. As long as the data +persists, the protocol can be safely resumed at any step. Persisting data is +cumulative, that is an additional persist operation does not erase the +previously stored information. + +The implementation also records additional entries in the exchange's database +that are needed for auditing. + +\subsection{Preliminaries} +In our protocol definitions, we write $\mathbf{check}\ \mathrm{COND}$ to abort +the protocol with an error if the condition $\mathrm{COND}$ is false. + +We use the following algorithms: +\begin{itemize} +\item $\algo{Ed25519.Keygen}() \mapsto \langle \V{sk}, \V{pk} \rangle$ + to generate an Ed25519 key pair. + \item $\algo{Ed25519.GetPub}(\V{sk}) \mapsto \V{pk}$ to derive the public key from + an Ed25519 public key. + \item $\algo{Ed25519.Sign}(\V{sk}, m) \mapsto \sigma$ to create a signature $\sigma$ + on message $m$ using secret key $\V{sk}$. + \item $\algo{Ed25519.Verify}(\V{pk}, \sigma, m) \mapsto b$ to check if $\sigma$ is + a valid signature from $\V{pk}$ on message $m$. + \item $\mathrm{HKDF}(n, k, s) \mapsto m$ is the HMAC-based key derivation function \cite{rfc5869}, + producing an output $m$ of $n$ bits from the input key material $k$ and salt $s$. +\end{itemize} + +We write $\mathbb{Z}^*_N$ for the multiplicative group of integers modulo $N$. +Given an $r \in \mathbb{Z}^*_N$, we write $r^{-1}$ for the multiplicative +inverse modulo $N$ of $r$. + +We write $H(m)$ for the SHA-512 hash of a bit string, +and $\FDH(N,m)$ for the full domain hash that maps the bit string $m$ to an element +of $\mathbb{Z}^*_N$. + +The expression $x \randsel X$ denotes uniform random selection of an element +$x$ from set $X$. We use $\algo{SelectSeeded}(s, X) \mapsto x$ for pseudo-random uniform +selection of an element $x$ from set $X$ and seed $s$. Here, the result is deterministic for fixed inputs $s$ and $X$. + +The exchange's denomination signing key pairs $\{\langle \V{skD}_i, \V{pkD}_i \rangle \}$ are RSA keys pairs, +and thus $\V{pkD}_i = \langle e_i, N_i \rangle$, $\V{skD_i} = d_i$. We write $D(\V{pkD}_i)$ for the +financial value of the denomination $\V{pkD}_i$. + +% FIXME: explain RSA keys of exchange + + +\subsection{Withdrawing} +The withdrawal protocol is defined in Figure~\ref{fig:withdraw-protocol}. +The following additional algorithms are used, which we only define informally here: +\begin{itemize} + \item $\algo{CreateBalance}(W_p, v) \mapsto \bot$ is used by the exchange, + and has the side-effect of creating a reserve record with balance $v$ + and reserve public key (effectively the identifier of the reserve) $W_p$. + \item $\algo{GetWithdrawR}(\rho) \mapsto \{\bot,\overline{\sigma}_C\}$ + is used by the exchange, and checks + if there is an existing withdraw request $\rho$. If the existing request + exists, the existing blind signature $\overline{\sigma}_C$ over + coin $C$ is returned. On a fresh request, $\bot$ is + returned. + \item $\algo{BalanceSufficient}(W_s,\V{pkD}_t) \mapsto b$ is used by the exchange, and + returns true if the balance in the reserve identified by $W_s$ is sufficient to + withdraw at least one coin if denomination $\V{pkD}_t$. + \item $\algo{DecreaseBalance}(W_s,\V{pkD}_t) \mapsto \bot$ is used by the exchange, and + decreases the amount left in the reserve identified by $W_s$ by the amount $D(\V{pkD}_t)$ + that the denomination $\V{pkD}_t$ represents. +\end{itemize} + +\begin{figure} +\centering +\fbox{% +\pseudocode[codesize=\small]{% +\textbf{Customer} \< \< \textbf{Exchange} \\ + \text{Knows } \{ \langle e_i,N_i \rangle \} = \{\V{pkD}_i\} \< \< \text{Knows } \{ \langle \V{skD}_i, \V{pkD}_i \rangle \} \pclb +\pcintertext[dotted]{Create Reserve} +\langle w_s, W_p \rangle \leftarrow \algo{Ed25519.Keygen}() \< \< \\ +\text{Persist reserve } \langle w_s,v \rangle \< \< \\ + \< \sendmessageright{top={Bank transfer}, bottom={(subject: $W_p$, amount: $v$)},style=dashed} \< \\ + \< \< \algo{CreateBalance}(W_p, v) \pclb +\pcintertext[dotted]{Prepare Withdraw} +\text{Choose $t$ with $\V{pkD}_t \in \{\V{pkD}_i\}$} \< \< \\ +\langle c_s, C_p \rangle \leftarrow \algo{Ed25519.Keygen}() \< \< \\ + r \randsel \mathbb{Z}^*_N \< \< \\ + \text{Persist planchet } \langle c_s, r \rangle \< \< \pclb +\pcintertext[dotted]{Execute Withdraw} +\overline{m} := \FDH(N_t, C_p) \cdot r^{e_t} \bmod N_t \< \< \\ +\rho_W := \langle \V{pkD}_t, \overline{m} \rangle \< \< \\ +\sigma_W := \algo{Ed25519.Sign}(w_s, \rho_W) \< \< \\ +\< \sendmessageright*{\rho := \langle W_p, \sigma_W, \rho_W \rangle} \< \\ + \< \< \pccheck \V{pkD}_t \in \{ \V{pkD}_i \} \\ +\< \< \pccheck \algo{Ed25519.Verify}(W_p,\rho_W,\sigma_W) \\ +\< \< x \leftarrow \algo{GetWithdraw}(\rho) \\ +\< \< \pcif x \iseq \bot \\ +\< \< \t \pccheck \algo{BalanceSufficient}(W_p,\V{pkD}_t) \\ +\< \< \t \algo{DecreaseBalance}(W_p, \V{pkD}_t) \\ +\< \< \t \text{Persist withdrawal $\rho$} \\ +\< \< \t \overline{\sigma}_C := (\overline{m})^{\V{skD}_t} \bmod N_t \\ +\< \< \pcelse \\ +\< \< \t \overline{\sigma}_C := x \\ +\< \sendmessageleft*{\overline{\sigma}_C} \< \\ +\sigma_C := r^{-1}\overline{\sigma}_C \< \< \\ +\pccheck \sigma_C^{e_t} \iseqv_{N_t} \FDH(N_t, C_p) \< \< \\ +\text{Persist coin $\langle \V{pkD}_t, c_s, C_p, \sigma_C \rangle$} \< \< \\ +} +} +\caption[Withdraw protocol diagram.]{Withdrawal protocol diagram.} +\label{fig:withdraw-protocol} +\end{figure} + +\subsection{Payment transactions} +The payment protocol is defined in two parts. First, the spend protocol in +Figure~\ref{fig:payment-spend} defines the interaction between a merchant and +a customer. The customer obtains the contract terms (as $\rho_P$) from the +merchant, and sends the merchant deposit permissions as a payment. The deposit protocol +in Figure~\ref{fig:payment-deposit} defines how subsequently the merchant sends the +deposit permissions to the exchange to detect double-spending and ultimately +to receive a bank transfer from the exchange. + +Note that in practice the customer can also execute the deposit +protocol on behalf of the merchant. This is useful in situations where +the customer has network connectivity but the merchant does not. It +also allows the customer to complete a payment before the payment +deadline if a merchant unexpectedly becomes unresponsive, allowing the +customer to later prove that they paid on time. + +We limit the description to one exchange here, but in practice, the merchant +communicates to the customer the exchanges that it supports, in addition to the +account information $A_M$ that might differ between exchanges. + +We use the following algorithms, defined informally here: +\begin{itemize} + \item $\algo{SelectPayCoins}(v, E_M) \mapsto \{ \langle \V{coin}_i, f_i \rangle \}$ selects + fresh coins (signed with denomination keys from exchange $E_M$) + to pay for the amount $v$. The result is a set of coins + together with the fraction of each coin that must be spent such that + the amounts contributed by all coins sum up to $v$. + \item $\algo{MarkDirty}(\V{coin}, f) \mapsto \bot$ subtracts the fraction $f$ from the + available amount left on a coin, and marks the coin as dirty (to trigger refreshing + in case $f$ is below the denomination value). Thus, assuming the coin has + any residual value, the customer's wallet will do a refresh on $\V{coin}$ + and not use it for further payments. This provides unlinkability of transactions + made with change arising from paying with fractions of a coin's denomination. + \item $\algo{Deposit}(E_M, D_i) \mapsto b$ executes the second part of the payment protocol + (i.e., the deposit) with exchange $E_M$, using deposit permission $D_i$. + \item $\algo{GetDeposit}(C_p, h) \mapsto \{\bot,\rho_{(D,i)}\}$ checks in the exchange's database + for an existing processed deposit permission on coin $C_p$ for the contract + identified by $h$. The algorithm returns the existing deposit permission $\rho_{(D,i)}$, or $\bot$ if a + matching deposit permission is not recorded. + \item $\algo{IsOverspending}(C_p, \V{pkD}, f) \mapsto b$ checks in the exchange's database + if there if at least the fraction $f$ of the coin $C_p$ of denomination $\V{pkD}$ is still available + for use, based on existing spend/withdraw records of the exchange. + \item $\algo{MarkFractionalSpend}(C_p, f) \mapsto \bot$ adds a spending + record to the exchanges database, indicating + that fraction $f$ of coin $C_p$ has been spent (in addition to + existing spending/refreshing records). + \item $\algo{ScheduleBankTransfer}(A_M, f, \V{pkD}, h_c) \mapsto \bot$ + schedules a bank transfer from the exchange to + the account identified by $A_M$, for subject $h_c$ and for the amount $f\cdot D(\V{pkD})$. + % NOTE: actual implementation avoids multiplication (messy!) and would + % simply require f \le D(\V{pkD})! +\end{itemize} + + +\begin{figure} +\centering +\fbox{% +\pseudocode[codesize=\footnotesize]{% +\textbf{Customer} \< \< \textbf{Merchant} \\ +\text{Knows } \V{pkM} \< \< \text{Knows } \langle \V{pkM}, \V{skM} \rangle \\ +\< \sendmessageright{top={Select product/service},style=dashed} \< \\ +\< \< \text{Determine:} \\ +\< \< \text{$\bullet$ } v \text{ (price) } \\ +\< \< \text{$\bullet$ } E_M \text{ (exchange) } \\ +\< \< \text{$\bullet$ } A_M \text{ (acct.) } \\ +\< \< \text{$\bullet$ } \V{info} \text{ (free-form details) } \\ +\< \sendmessageleft{top={Request payment},style=dashed} \< \\ +\langle p_s, P_p \rangle \leftarrow \algo{Ed25519.Keygen}() \< \< \\ +\text{Persist ownership identifier } p_s \< \< \\ +\< \sendmessageright*{P_p} \< \\ + \< \< \rho_P := \langle E_M, A_M, \V{pkM}, H(\langle v, \V{info}\rangle), P_p \rangle \\ +\< \< \sigma_P := \V{Ed25519.Sign}(\V{skM}, \rho_P) \\ +\< \sendmessageleft*{\rho_P, \sigma_P, v, \V{info}} \< \\ + \langle M, A_M, \V{pkM}, h', P_p' \rangle := \rho_P \< \< \\ +\pccheck \algo{Ed25519.Verify}(pkM, \sigma_P, \rho_P) \< \< \\ +\pccheck P_p' \iseq P_p \< \< \\ +\pccheck h' \iseq H(\langle v, \V{info} \rangle ) \< \< \\ +\V{cf} \leftarrow \algo{SelectPayCoins}(v, E_M) \< \< \\ +\pcfor \langle \V{coin_i,f_i} \rangle \in \V{cf} \< \< \\ +\t \algo{MarkDirty}(\V{coin}_i, f_i) \< \< \\ +\t \langle c_s, C_p, \V{pkD}, \sigma_C \rangle := \V{coin}_i \< \< \\ + \t \rho_{(D,i)} := \langle C_p, \V{pkD}, \sigma_C, f_i, H(\rho_P), A_M, \V{pkM} \rangle \< \< \\ +\t \sigma_{(D,i)} := \V{Ed25519.Sign}(c_s, \rho_{(D,i)}) \< \< \\ + \text{Persist } \langle \sigma_P, \V{cf}, \rho_P, \rho_{(D,i)}, \sigma_{(D,i)}, v, \V{info} \rangle \< \<\\ +\< \sendmessageright*{ \mathcal{D} := \{\langle \rho_{(D,i)}, \sigma_{(D,i)}\rangle \}} \< \\ +\< \< \pcfor D_i \in \mathcal{D} \\ +\< \< \t \pccheck \algo{Deposit}(E_M, D_i) \\ +} +} +\caption[Spend protocol diagram.]{Spend Protocol executed between customer and merchant for the purchase + of an article of price $v$ using coins from exchange $E_M$. The merchant has + provided his account details to the exchange under an identifier $A_M$. + The customer can identify themselves as the one who received the offer + using $p_s$. + %This prevents multiple customers from legitimately paying for the + %same article and potentially exhausting stocks. +} +\label{fig:payment-spend} +\end{figure} + +\begin{figure} +\centering +\fbox{% +\pseudocode[codesize=\small]{% +\textbf{Customer/Merchant} \< \< \textbf{Exchange} \\ +\text{Knows } \V{pkESig} \< \< \text{Knows } \V{skESig}, \V{pkESig}, \{ \V{pkD}_i \} \\ +\text{Knows } D_i = \langle \rho_{(D,i)}, \sigma_{(D,i)} \rangle \< \< \\ +\< \sendmessageright*{ D_i } \< \\ +\< \< \langle \rho_{(D,i)}, \sigma_{(D,i)} \rangle := D_i \\ + \< \< \langle C_p, \V{pkD}, \sigma_C, f_i, h, A_M, \V{pkM} \rangle := \rho_{(D,i)} \\ +\< \< \pccheck \V{pkD} \in \{ \V{pkD}_i \} \\ +\< \< \langle e, N \rangle := \V{pkD} \\ +\< \< \pccheck \algo{Ed25519.Verify}(C_p, \sigma_{(D,i)}, \rho_{(D,i)}) \\ +\< \< x \leftarrow \algo{GetDeposit}(C_p, h) \\ +\< \< \pcif x \iseq \bot \\ +\< \< \t \pccheck \sigma_C^{e} \iseqv_N \FDH(N, C_p) \\ +\< \< \t \pccheck \neg\algo{IsOverspending}(C_p, \V{pkD}, f) \\ +\< \< \t \text{Persist deposit-record } D_i \\ +\< \< \t \algo{MarkFractionalSpend}(C_p, f) \\ +\< \< \t \algo{ScheduleBankTransfer}(A_M, f, \V{pkD}, h_c) \\ +\< \< \pcelse \\ +\< \< \t \pccheck x \iseq \rho_{(D,i)} \\ +\< \< \sigma_{DC} \leftarrow \algo{Ed25519.Sign}(\V{pkESig}, \rho_{(D,i)}) \\ +\< \sendmessageleft*{ \sigma_{DC} } \< \\ +\pccheck \algo{Ed25519.Verify} \\{}\qquad(\V{pkESig}, \sigma_{DC}, \rho_{(D,i)}) \< \< \\ +} +} +\caption[Deposit protocol diagram.]{Deposit Protocol run for each deposited coin $D_i \in {\cal D}$ with the + exchange that signed the coin.} +\label{fig:payment-deposit} +\end{figure} + + +\subsection{Refreshing and Linking} +The refresh protocol is defined in Figures~\ref{fig:refresh-part1} and +\ref{fig:refresh-part2}. The refresh protocol allows the customer to +obtain change for the remaining fraction of the value of a coin. The +change is generated as a fresh coin that is unlinkable to the dirty +coin to anyone except for the owner of the dirty coin. + +A na\"ive implementation of a refresh protocol that just gives the customer a +new coin could be used for peer-to-peer transactions that hides income from tax +authorities. Thus, (with probability $(1-1/\kappa)$) the refresh protocol +records information that allows the owner of the original coin to obtain the +refreshed coin from the original coin via the linking protocol (illustrated in +Figure~\ref{fig:link}). + +We use the following algorithms, defined informally here: +\begin{itemize} + \item \algo{RefreshDerive} is defined in Figure~\ref{fig:refresh-derive}. + \item $\algo{GetOldRefresh}(\rho_{RC}) \mapsto \{\bot,\gamma\}$ returns the past + choice of $\gamma$ if $\rho_{RC}$ is a refresh commit message that has been seen before, + and $\bot$ otherwise. + \item $\algo{IsConsistentChallenge}(\rho_{RC}, \gamma) \mapsto \{ \bot,\top \}$ returns + $\top$ if no refresh-challenge has been persisted for the refresh operation by commitment + $\rho_{RC}$ or $\gamma$ is consistent with the persisted (and thus previously received) challenge; + returns $\bot$ otherwise. + \item $\algo{LookupLink}(C_p) \mapsto \{ \langle \rho_{L}^{(i)}, \sigma_L^{(i)}, + \overline{\sigma}_C^{(i)} \rangle \}$ looks up refresh records on coin with public key $C_p$ in + the exchange's database and returns the linking message $\rho_L^{(i)}$, linking + signature $\sigma_L^{(i)}$ and blinded signature $\overline{\sigma}_C^{(i)}$ for each refresh + record $i$. +\end{itemize} + + +\begin{figure} +\centering +\fbox{% +\procedure[codesize=\small]{$\algo{RefreshDerive}(s, \langle e, N \rangle, C_p)$}{% +t := \HKDF(256, s, \texttt{"t"}) \\ +T := \algo{Curve25519.GetPub}(t) \\ +x := \textrm{ECDH-EC}(t, C_p) \\ +r := \algo{SelectSeeded}(x, \mathbb{Z}^*_{N}) \\ +c_s := \HKDF(256, x, \texttt{"c"}) \\ +C_p := \algo{Ed25519.GetPub}(c_s) \\ +\overline{m} := r^{e}\cdot C_p \mod N \\ +\pcreturn \langle t, T, x, c_s, C_p, \overline{m} \rangle +} +} +\caption[RefreshDerive algorithm]{The RefreshDerive algorithm running with the seed $s$ on dirty coin $C_p$ to + generate a fresh coin to be later signed with denomination key $pkD := \langle e,N\rangle$.} +\label{fig:refresh-derive} +\end{figure} + + +\begin{figure} +\centerline{ +\fbox{% +\pseudocode[codesize=\footnotesize]{% +\textbf{Customer} \< \< \textbf{Exchange} \\ +\text{Knows } \{ \V{pkD}_i \} \< \< \text{Knows } \{\langle \V{skD}_i, \V{pkD}_i \rangle \} \\ +\text{Knows } \V{coin}_0 = \langle \V{pkD}_0, c_s^{(0)}, C_p^{(0)}, \sigma_{C}^{(0)} \rangle \< \< \\ +\text{Select } \langle N_t, e_t \rangle := \V{pkD}_t \in \{ \V{pkD}_i \} \< \< \\ +\pcfor i = 1,\dots,\kappa \< \< \\ +\t s_i \randsel \{0,1\}^{256} \< \< \\ +\t X_i := \algo{RefreshDerive}(s_i, \V{pkD}_t, C_p^{(0)}) \< \< \\ +\t (t_i, T_i, x_i, c_s^{(i)}, C_p^{(i)}, \overline{m}_i) := X_i \< \< \\ +h_T := H(T_1,\dots,T_\kappa) \< \< \\ +h_{\overline{m}} := H(\overline{m}_1,\dots,\overline{m}_\kappa) \< \< \\ +h_C := H(h_t, h_{\overline{m}}) \< \< \\ +\rho_{RC} := \langle h_C, \V{pkD}_t, \V{pkD}_0, C_p^{(0)}, \sigma_{C}^{(0)} \rangle \< \< \\ +\sigma_{RC} := \algo{Ed25519.Sign}(c_s^{(0)}, \rho_{RC}) \< \< \\ +\text{Persist refresh-request } \langle \rho_{RC}, \sigma_{RC} \rangle \< \< \\ +\< \sendmessageright*{ \rho_{RC}, \sigma_{RC} } \< \\ +\< \< (h_C, \V{pkD}_t, \V{pkD}_0, C_p^{(0)}, \sigma_{C}^{(0)}) := \rho_{RC} \\ +\< \< \pccheck \algo{Ed25519.Verify}(C_p^{(0)}, \sigma_{RC}, \rho_{RC}) \\ +\< \< x \leftarrow \algo{GetOldRefresh}(\rho_{RC}) \\ +\< \< \pcif x \iseq \bot \\ +\< \< \t v := D(\V{pkD}_t) \\ +\< \< \t \langle e_0, N_0 \rangle := \V{pkD}_0 \\ +\< \< \t \pccheck \neg\algo{IsOverspending}(C_p^{(0)}, \V{pkD}_0, v) \\ +\< \< \t \pccheck \V{pkD}_t \in \{ \V{pkD}_i \} \\ +\< \< \t \pccheck \FDH(N_0, C_p^{(0)}) \iseqv_{N_0} (\sigma_0^{(0)})^{e_0} \\ +\< \< \t \algo{MarkFractionalSpend}(C_p^{(0)}, v) \\ +\< \< \t \gamma \randsel \{1,\dots,\kappa\} \\ +\< \< \t \text{Persist refresh-record } \langle \rho_{RC},\gamma \rangle \\ +\< \< \pcelse \\ +\< \< \t \gamma := x \\ +\< \sendmessageleft*{ \gamma } \< \pclb +\pcintertext[dotted]{(Continued in Figure~\ref{fig:refresh-part2})} +}}} +\caption{Refresh Protocol (Commit Phase)} +\label{fig:refresh-part1} +\end{figure} + +\begin{figure} +\centerline{ +\fbox{% +\pseudocode[codesize=\footnotesize]{% +\textbf{Customer} \< \< \textbf{Exchange} \pclb +\pcintertext[dotted]{(Continuation of \ref{fig:refresh-part1})} \\ +\< \sendmessageleft*{ \gamma } \< \\ +\pccheck \algo{IsConsistentChallenge}(\rho_{RC}, \gamma) \< \< \\ +\text{Persist refresh-challenge $\langle \rho_{RC}, \gamma \rangle$} \< \< \\ +S := \langle s_1,\dots,s_{\gamma-1},s_{\gamma+1},\dots,s_\kappa \rangle \< \< \\ +\rho_{L} = \langle C_p^{(0)}, \V{pkD}_t, T_\gamma, \overline{m}_\gamma \rangle \< \< \\ +\rho_{RR} = \langle T_\gamma, \overline{m}_\gamma, S \rangle \< \< \\ +\sigma_{L} = \algo{Ed25519.Sign}(c_s^{(0)}, \rho_{L}) \< \< \\ +\< \sendmessageright*{ \rho_{RR}, \rho_{L}, \sigma_{L} } \< \\ +\< \< \langle T'_\gamma, \overline{m}'_\gamma, S \rangle := \rho_{RR} \\ +\< \< \langle s_1,\dots,s_{\gamma-1},s_{\gamma+1},\dots,s_\kappa \rangle ) := S \\ +\< \< \pccheck \algo{Ed25519.Verify}(C_p^{(0)}, \sigma_L, \rho_L) \\ +\< \< \pcfor i = 1,\dots,\gamma-1,\gamma+1,\dots,\kappa \\ +\< \< \t X_i := \algo{RefreshDerive}(s_i, \V{pkD}_t, C_p^{(0)}) \\ +\< \< \t \langle t_i, T_i, x_i, c_s^{(i)}, C_p^{(i)}, \overline{m}_i \rangle := X_i \\ +\< \< h_T' = H(T_1,\dots,T_{\gamma-1},T'_{\gamma},T_{\gamma+1},\dots,T_\kappa) \\ +\< \< h_{\overline{m}}' = H(\overline{m}_1,\dots,\overline{m}_{\gamma-1},\overline{m}'_{\gamma},\overline{m}_{\gamma+1},\dots,\overline{m}_\kappa) \\ +\< \< h_C' = H(h_T', h_{\overline{m}}') \\ +\< \< \pccheck h_C \iseq h_C' \\ +\< \< \overline{\sigma}_C^{(\gamma)} := \overline{m}^{skD_t} \\ +\< \sendmessageleft*{\overline{\sigma}_C^{(\gamma)}} \< \\ +\sigma_C^{(\gamma)} := r^{-1}\overline{\sigma}_C^{(\gamma)} \< \< \\ +\pccheck (\sigma_C^{(\gamma)})^{e_t} \iseqv_{N_t} C_p^{(\gamma)} \< \< \\ +\text{Persist coin $\langle \V{pkD}_t, c_s^{(\gamma)}, C_p^{(\gamma)}, \sigma_C^{(\gamma)} \rangle$} \< \< \\ +}}} +\caption{Refresh Protocol (Reveal Phase)} +\label{fig:refresh-part2} +\end{figure} + +\begin{figure} +\centering +\fbox{% +\pseudocode[codesize=\footnotesize]{% +\textbf{Customer} \< \< \textbf{Exchange} \\ +\text{Knows } \V{coin}_0 = \langle \V{pkD}_0, c_s^{(0)}, C_p^{(0)}, \sigma_{C}^{(0)} \rangle \< \< \\ +\< \sendmessageright*{C_p^{(0)}} \< \\ +\< \< L := \algo{LookupLink}(C_p^{(0)}) \\ +\< \sendmessageleft*{L} \< \\ +\pcfor \langle \rho_{L}^{(i)}, \overline{\sigma}_L^{(i)}, \sigma_C^{(i)} \rangle \in L \< \< \\ +\t \langle \hat{C}_p^{(i)}, \V{pkD}_t^{(i)}, T_\gamma^{(i)}, \overline{m}_\gamma^{(i)} \rangle := \rho_L^{(i)} \< \< \\ +\t \langle e_t^{(i)}, N_t^{(i)} \rangle := \V{pkD}_t^{(i)} \< \< \\ +\t \pccheck \hat{C}_p^{(i)} \iseq C_p^{(0)} \< \< \\ +\t \pccheck \algo{Ed25519.Verify}(C_p^{(0)}, \rho_{L}^{(i)}, \sigma_L^{(i)})\< \< \\ +\t x_i := \algo{ECDH}(c_s^{(0)}, T_\gamma^{(i)}) \< \< \\ +\t r_i := \algo{SelectSeeded}(x_i, \mathbb{Z}^*_{N_t}) \\ +\t c_s^{(i)} := \HKDF(256, x_i, \texttt{"c"}) \\ +\t C_p^{(i)} := \algo{Ed25519.GetPub}(c_s^{(i)}) \\ +\t \sigma_C^{(i)} := (r_i)^{-1} \cdot \overline{m}_\gamma^{(i)} \\ +\t \pccheck (\sigma_C^{(i)})^{e_t^{(i)}} \iseqv_{N_t^{(i)}} C_p^{(i)} \\ +\t \text{(Re-)obtain coin } \langle \V{pkD}_t^{(i)}, c_s^{(i)}, C_p^{(i)}, \sigma_C^{(i)} \rangle +} +} +\caption{Linking protocol} +\label{fig:link} +\end{figure} + +\clearpage + +\subsection{Refunds} +The refund protocol is defined in Figure~\ref{fig:refund}. The customer +requests from the merchant that a deposit should be ``reversed'', and if the +merchants allows the refund, it authorizes the exchange to apply the refund and +sends the refund confirmation back to the customer. Note that in practice, +refunds are only possible before the refund deadline, which is not considered +here. + +We use the following algorithms, defined informally here: +\begin{itemize} + \item $\algo{ShouldRefund}(\rho_P, m) \mapsto \{ \top, \bot \}$ is used by the merchant to + check whether a refund with reason $m$ should be given for the purchase identified by the + contract terms $\rho_P$. The decision is made according to the merchant's business rules. + \item $\algo{LookupDeposits}(\rho_P, m) \mapsto \{ \langle \rho_{(D,i)}, + \sigma_{(D,i)} \rangle \}$ is used by the merchant to retrieve deposit + permissions that were previously sent by the customer and already deposited + with the exchange. + \item $\algo{RefundDeposit}(C_p, h, f, \V{pkM})$ is used by the exchange to + modify its database. It (partially) reverses the amount $f$ of a deposit + of coin $C_p$ to the merchant $\V{pkM}$ for the contract identified by $h$. + The procedure is idempotent, and subsequent invocations with a larger $f$ + increase the refund. +\end{itemize} + +\begin{figure} +\centerline{ +\fbox{% +\pseudocode[codesize=\footnotesize]{% +\< \< \pclb +\pcintertext[dotted]{Request refund} \\ +\textbf{Customer} \< \< \textbf{Merchant} \\ +\text{Knows } \V{pkM}, \V{pkESig} \< \< \text{Knows } \langle \V{pkM}, \V{skM} \rangle, \V{pkESig} \\ +\< \sendmessageright{top={Ask for refund},bottom={(Payment $\rho_P$, reason $m$)},style=dashed} \< \\ +\< \< \pccheck \algo{ShouldRefund}(\rho_P,m) \pclb +\pcintertext[dotted]{Execute refund} \\ +\textbf{Exchange} \< \< \textbf{Merchant} \\ +\text{Knows } \langle \V{skESig}, \V{pkESig} \rangle \< \< \\ + \< \< \pcfor \langle \rho_{(D,i)}, \cdot \rangle \in \algo{LookupDeposits}(\rho_P) \\ + \< \< \t \rho_{(X,i)} := \langle \mathtt{"refund"}, \rho_D \rangle \\ + \< \< \t \sigma_{(X,i)} := \algo{Ed25519.Sign}(\V{skM}, \rho_{(X,i)}) \\ + \< \sendmessageleft*{X := \{ \rho_{(X,i)}, \sigma_{(X,i)} \} } \< \\ +\pcfor \langle \rho_{(X,i)}, \sigma_{(X,i)} \rangle \in X \< \< \\ +\t \pccheck \langle \mathtt{"refund"}, \rho_D \rangle := \rho_X \< \< \\ +\t \pccheck \langle C_p, \V{pkD}, \sigma_C, f, h, A_M, \V{pkM} \rangle := \rho_D \\ +\t \pccheck \algo{Ed25519.Verify}(\V{pkM}, \rho_X, \sigma_X) \< \< \\ +\t \algo{RefundDeposit}(C_p, h, f, \V{pkM}) \< \< \\ +\t \rho_{(XC,i)} := \langle \mathtt{"refunded"}, \rho_D \rangle \< \< \\ +\t \sigma_{(XC,i)} := \algo{Ed25519.Sign}(\V{skESig}, \rho_{(XC,i)}) \< \< \\ +\< \sendmessageright*{XC := \{ \rho_{(XC,i)}, \sigma_{(XC,i)} \} } \< \pclb +\pcintertext[dotted]{Confirm refund} \\ +\textbf{Customer} \< \< \textbf{Merchant} \\ +\< \sendmessageleft*{XC} \< \\ +\pcfor \langle \rho_{(XC,i)}, \sigma_{(XC,i)} \rangle \in XC \< \< \\ + \t \pccheck \algo{Ed25519.Verify}(\V{pkESig}, \rho_{(XC,i)}, \sigma_{(XC,i)}) \< \< \\ +} +} +} +\caption{Refund protocol} +\label{fig:refund} +\end{figure} + +\clearpage +\section{Experimental results} +We now evaluate the performance of the core components of the reference +implementation of GNU Taler. No separate benchmarks are provided for the +merchant backend, as the work done by the merchant per transaction is +relatively negligible compared to the work done by the exchange, and one exchange needs +to provide service many merchants and all of their customers. Thus, the exchange +is the bottleneck for the performance of the system. + +We provide a microbenchmark for the performance of cryptographic operations in +the wallet (Table~\ref{table:wallet-benchmark}. Even on a low-end smartphone +device, the most expensive cryptographic operations remain well under +$150ms$, a threshold for user-interface latency under which user happiness and +productivity is considered to be unaffected \cite{tolia2006quantifying}. + +\begin{table} + \centering + \begin{subtable}[t]{0.4\linewidth} + \centering{ + \begin{tabular}{lr} + \toprule + Operation & Time (ms) \\ + \midrule + eddsa create & 9.69 \\ + eddsa sign & 22.31 \\ + eddsa verify & 19.28 \\ + hash big & 0.05 \\ + hash small & 0.13 \\ + rsa 2048 blind & 3.35 \\ + rsa 2048 unblind & 4.94 \\ + rsa 2048 verify & 1.97 \\ + rsa 4096 blind & 10.38 \\ + rsa 4096 unblind & 16.13 \\ + rsa 4096 verify & 6.57 \\ + \bottomrule + \end{tabular}} + \caption{Wallet microbenchmark on a Laptop (Intel i7-4600U) with Firefox} + \end{subtable} + \qquad + \begin{subtable}[t]{0.4\linewidth} + \centering{ + \begin{tabular}{lr} + \toprule + Operation & Time (ms) \\ + \midrule + eddsa create & 34.80 \\ + eddsa sign & 78.55 \\ + eddsa verify & 72.50 \\ + hash big & 0.51 \\ + hash small & 1.37 \\ + rsa 2048 blind & 14.35 \\ + rsa 2048 unblind & 19.78 \\ + rsa 2048 verify & 9.10 \\ + rsa 4096 blind & 47.86 \\ + rsa 4096 unblind & 69.91 \\ + rsa 4096 verify & 29.02 \\ + \bottomrule + \end{tabular}} + \caption{Wallet microbenchmark on Android Moto G3 with Firefox} + \end{subtable} + \caption{Wallet microbenchmarks} + \label{table:wallet-benchmark} +\end{table} + + +We implemented a benchmarking tool that starts a single (multi-threaded) +exchange and a bank process for the taler-test wire transfer protocol. It then +generates workload on the exchange with a configurable number of concurrent +clients and operations. The benchmarking tool is able to run the exchange on a +different machine (via SSH\footnote{\url{https://www.openssh.com/}}) than the benchmark driver, mock bank and clients. +At the end, the benchmark outputs the number of deposited coins per second and +latency statistics. + +\subsection{Hardware Setup} +We used two server machines (\texttt{firefly} and \texttt{gv}) with the following +hardware specifications for our tests: +\begin{itemize} + \item \texttt{firefly} has a 96-core AMD EPYC 7451 CPU and 256GiB DDR4\@2667 MHz RAM. + \item \texttt{gv} has a 16-core Intel(R) Xeon X5550 (2.67GHz) CPU and 128GiB DDR3\@1333 MHz RAM. +\end{itemize} + +We used $2048$-bit RSA denomination keys for all of our exchange benchmarks. We +used a development version of the exchange (with git commit hash +5fbda29b76c24d\dots). PostgreSQL version 11.3 was used as the database. +As our server machines have only slower hard-disk drives instead of faster solid-state drives, +we ran the benchmarks with an in-memory database. + + +\subsection{Coins Per Transaction}\label{sec:coins-per-transaction} +The transaction rate is an important characteristic of a payment system. Since +GNU Taler internally operates on the level of coins instead of transactions, we +need to define what actually consititutes one transaction in our measurements. +This includes both how many coins are used per transaction on average, as well +as how often refresh operations are run. + +We ran a simple simulation to determine rather conservative upper bounds for +the parameters that characterize the average transaction. The source code for +the simulation can be found in Appendix \ref{appendix:coinsim}. + +In the simulation, thirteen denominations of values $2^0,\dots,2^{12}$ are +available. Customers repeatedly select a random value to be spent between $4$ and $5000$. +When customers do not have enough coins for a transaction, they withdraw a +uniform random amount between the minimum amount to complete the transaction +and $10000$. The denominations selected for withdrawal are chosen by greedy +selection of the largest possible denomination. When spending, the customer +first tries to use one coin, namely the smallest coin larger than the +requested amount. If no such coin exists in the customer's wallet, the +customer pays with multiple coins, spending smallest coins first. + +Choosing a random uniform amount for withdrawal could be considered +unrealistic, as customers in practice likely would select from a fixed list of +common withdrawal amounts, just like most ATMs operate. +Thus, we also implemented a variation of the simulation that withdraws a constant +amount of $1250$ (i.e., $1/4$ of the maximum transaction value) if it is sufficient +for the transaction, and the exact required amount otherwise. + +We obtained the following results for the number of average operations +executed for one ``business transaction'': + +\begin{table}[H] +\centering +\begin{tabular}{lSS} + \toprule + & {random withdraw} & {constant withdraw} \\ + \midrule + \#spend operations & 8.3 & 7.0 \\ + \#refresh operations & 1.3 & 0.51 \\ + \#refresh output coins & 4.2 & 3.62 \\ + \bottomrule +\end{tabular} +\end{table} + +Based on these results, we chose the parameters for our benchmark: for every +spend operation we run a refresh operation with probability $1/10$, where each +refresh operation produces $4$ output coins. In order to arrive at the +transaction rate, the rate of spend operations should be divided by $10$. + +Note that this is a rather conservative analysis. In practice, the coin +selection for withdrawal/spending can use more sophisticated optimization +algorithms, rather than using greedy selection. Furthermore, we expect that the +amounts paid in real-world transactions will have more predictable +distributions, and thus the offered denominations can be adjusted to typical +amounts. + +\subsubsection{Baseline Sequential Resource Usage} +To obtain a baseline for the resource usage of the exchange, we ran the benchmark on +\texttt{firefly} with a single client that executes sequential requests to +withdraw and spend $10000$ coins, with $10\%$ refresh probability. + +% FIXME: talk about TFO, compression and keep-alive + +Table~\ref{table:benchmark:ops-baseline} shows the time used for cryptographic +operations, together with the number of times they are executed by the clients +(plus the mock bank and benchmark setup) and exchange, respectively. Note that +while we measured the wall-clock time for these operations, the averages should +correspond to the actual CPU time required for the respective operations, as +the benchmark with one client runs significantly fewer processes/threads than +the number of available CPUs on our machine. + +The benchmark completed in $15.10$ minutes on $\texttt{firefly}$. We obtained the total CPU usage of +the benchmark testbed and exchange. The refresh operations are rather slow in comparison +to spends and deposits, as the benchmark with a refresh probability of $0\%$ only took $8.84$ +minutes to complete. + +\begin{table} + \centering + \begin{tabular}{lSSS} + \toprule + Operation & {Time/Op (\si{\micro\second})} & {Count (exchange)} & {Count (clients)} \\ + \midrule +ecdh eddsa & 1338.62 & 2430 & 3645 \\ +ecdhe key create & 1825.38 & 0 & 3645 \\ +ecdhe key get public & 1272.64 & 2430 & 4860 \\ +eddsa ecdh & 1301.78 & 0 & 4860 \\ +eddsa key create & 1896.27 & 0 & 12180 \\ +eddsa key get public & 1729.69 & 9720 & 80340 \\ +eddsa sign & 5182.33 & 13393 & 25608 \\ +eddsa verify & 3976.96 & 25586 & 25627 \\ +hash & 1.41 & 165608 & 169445 \\ +hash context finish & 0.28 & 1215 & 1227 \\ +hash context read & 0.81 & 25515 & 25655 \\ +hash context start & 11.38 & 1215 & 1227 \\ +hkdf & 40.61 & 65057 & 193506 \\ +rsa blind & 695.25 & 9720 & 31633 \\ +rsa private key get public & 5.30 & 0 & 40 \\ +rsa sign blinded & 5284.88 & 17053 & 0 \\ +rsa unblind & 1348.62 & 0 & 21898 \\ +rsa verify & 421.19 & 13393 & 29216 \\ + \bottomrule + \end{tabular} + \caption{Cryptographic operations in the benchmark with one client and $10000$ operations.} + \label{table:benchmark:ops-baseline} +\end{table} + + +\begin{table} + \centering + \begin{tabular}{lSSS} + \toprule + \textbf{Relation} & + {\textbf{Table (\si{\mebi\byte})}} & + {\textbf{Indexes (\si{\mebi\byte})}} & + {\textbf{Total (\si{\mebi\byte})}} \\ + \midrule + denominations & 0.02 & 0.03 & 0.05 \\ + reserves\_in & 0.01 & 0.08 & 0.09 \\ + reserves & 0.02 & 0.25 & 0.27 \\ + refresh\_commitments & 0.36 & 0.28 & 0.64 \\ + refresh\_transfer\_keys & 0.38 & 0.34 & 0.73 \\ + refresh\_revealed\_coins & 4.19 & 0.91 & 5.14 \\ + known\_coins & 7.37 & 0.70 & 8.07 \\ + deposits & 4.85 & 6.80 & 11.66 \\ + reserves\_out & 8.95 & 4.48 & 13.43 \\ + \midrule + \emph{Sum} & 26.14 & 13.88 & 40.02 \\ + \bottomrule + \end{tabular} + \caption{Space usage by database table for $10000$ deposits with $10\%$ refresh probability.} + \label{table:exchange-db-size} +\end{table} + +The size of the exchange's database after the experiment (starting from an empty database) +is shown in Table~\ref{table:exchange-db-size}. +We measured the size of tables and indexes using the \texttt{pg\_relation\_size} / +\texttt{pg\_indexes\_size} functions of PostgreSQL. + +We observe that even though the refresh operations account for about half of +the time taken by the benchmark, they contribute to only $\approx 16\%$ of the +database's size. The computational costs for refresh are higher than the +storage costs (compared to other operations), as the database stores only needs +to store one commitment, one transfer key and the blinded coins that are +actually signed. + +In our sequential baseline benchmark run, only one reserve was used to withdraw +coins, and thus the tables that store the reserves are very small. In +practice, information for multiple reserves would be tracked for each active +cutomers. + +The TCP/IP network traffic between the exchange, clients and the mock bank was +$\SI{57.95}{\mebi\byte}$, measured by the Linux kernel's statistics for +transmitted/received bytes on the relevant network interface. As expected, the +traffic is larger than the size of the database, since some data (such as +signatures) is only verified/generated and not stored in the database. + +\subsection{Transaction Rate and Scalability} +Figure~\ref{fig:benchmark-throughput} shows the mean time taken to process one +coin for different numbers of parallel clients. With increasing parallelism, +the throughput continues to rise roughly until after the number of parallel +clients saturates the number of available CPU cores (96). There is no +significant decrease in throughput even when the system is under rather high +load, as clients whose requests cannot be handled in parallel are either +waiting in the exchange's listen backlog or waiting in a retry timeout +(with randomized, truncated, exponential back-off) after being refused when the +exchange's listen backlog is full. + + +Figure~\ref{fig:benchmark-cpu} shows the CPU time (sum of user and system time) +of both the exchange and the whole benchmark testbed (including the exchange) +in relation to the wall-clock time the benchmark took to complete. +We can see that the gap between the wall-clock time and CPU time used by the +benchmark grows with an increase in the number of parallel clients. This can +be explained by the CPU usage of the database (whose CPU usage is not measured +as part of the benchmark). With a growing number of parallel transactions, the +database runs into an increasing number of failed commits due to read/write +conflicts, leading to retries of the corresponding transactions. + +To estimate the time taken up by cryptographic operations in the exchange, we +first measured a baseline with a single client, where the wall-clock time for +cryptographic operations is very close to the actual CPU time, as virtually no +context switching occurs. We then extrapolated these timings to experiment +runs with parallelism by counting the number of times each operation is +executed and multiplying with the baseline. As seen in the dot-and-dash line +in Figure~\ref{fig:benchmark-cpu}, by our extrapolation slightly more than half +of the time is spent in cryptographic routines. + +We furthermore observe in Figure~\ref{fig:benchmark-cpu} that under full load, +less than $1/3$ of the CPU time is spent by the exchange. A majority of the +CPU time in the benchmark is used by the simulation of clients. +As we did not have a machine available that is powerful enough to generate +traffic that can saturate a single exchange running on \texttt{firefly}, we +estimate the throughput that would be possible if the machine only ran the +exchange. The highest rate of spends was $780$ per second. Thus, the +theoretically achievable transaction rate on our single test machine (and a +dedicated machine for the database) would be $780 \cdot 3 / 10 = 234$ transactions +per second under the relatively pessimistic assumptions we made about what +consitutes a transaction. + +If a GNU Taler deployment was used to pay for items of fixed price (e.g., online +news articles), the overhead of multiple coins and refresh operations (which +accounts for $\approx 50\%$ of spent time as measured earlier) and multiple +coins per payment would vanish, giving an estimated maximum transaction rate of +$742 \cdot 2 = 1484$ transactions per second. + +\begin{figure} + \includegraphics[width=\textwidth]{plots/speed.pdf} + \caption[Coin throughput.]{Coin throughput in relation to number of parallel clients, with $1000$ coins per client per experiment run.} + \label{fig:benchmark-throughput} +\end{figure} + +\begin{figure} + \includegraphics[width=\textwidth]{plots/cpu.pdf} + \caption[Comparison of components' CPU usage for the benchmark.]{Comparison of real time, the CPU time for the exchange and the whole benchmark.} + \label{fig:benchmark-cpu} +\end{figure} + +\subsection{Latency} +We connected \texttt{firefly} and \texttt{gv} directly with a patch cable, and +introduced artificial network latency by configuring the Linux packet scheduler +with the \texttt{tc} tool. The goal of this experiment was to observe the +network latency characteristics of the implementation. Note that we do not consider +the overhead of TLS in our experiments, as we assume that TLS traffic is +already terminated before it reaches the exchange service, and exchanges can be +operated securely even without TLS. + +The comparison between no additional delay and a \SI{100}{\milli\second} delay +is shown in Table~\ref{table:latency}. TCP Fast Open~\cite{rfc7413} was +enabled on both \texttt{gv} and \texttt{firefly}. Since for all operations +except \texttt{/refresh/reveal}, both request and response fit into one TCP +segment, these operations complete within one round-trip time. This explains the +additional delay of $\approx \SI{200}{\milli\second}$ when the artificial delay +is introduced. Without TCP Fast Open, we would observe an extra round trip for +the SYN and SYN/ACK packages without any payload. The \texttt{/refresh/reveal} +operation takes an extra roundtrip due to the relatively large size of the +request (as show in Table~\ref{table:api-size}), which exceeds the MTU of 1500 +for the link between \texttt{gv} and \texttt{firefly}, and thus does not fit +into the first TCP Fast Open packet. + +Figure~\ref{fig:latencies} shows the latency for the exchange's HTTP endpoints +in relation to different network delays. As expected, the additional delay +grows linearly for a single client. We note that in larger benchmarks with +multiple parallel clients, the effect of additional delay would likely not just +be linear, due to timeouts raised by clients. + +\newcommand{\specialcell}[2][c]{% + \begin{tabular}[#1]{@{}c@{}}#2\end{tabular}} + +\begin{table} + \centering + \begin{tabular}{lSSSS} + \toprule + Endpoint & + {\specialcell[c]{Base latency\\(\si{\milli\second})}} & + {\specialcell[c]{Latency with\\\SI{100}{\milli\second} delay\\(\si{\milli\second})}} \\ + \midrule + \texttt{/keys} & 1.14 & 201.25 \\ + \texttt{/reserve/withdraw} & 22.68 & 222.46 \\ + \texttt{/deposit} & 22.36 & 223.22 \\ + \texttt{/refresh/melt} & 20.71 & 223.9 \\ + \texttt{/refresh/reveal} & 63.64 & 466.30 \\ + \bottomrule + \end{tabular} + \caption{Effects of \SI{100}{\milli\second} symmetric network delay on total latency.} + \label{table:latency} +\end{table} + +\begin{table} + \centering + \begin{tabular}{lSSSS} + \toprule + Endpoint & + {\specialcell[c]{Request size\\2048-bit RSA\\(\si{\kilo\byte})}} & + {\specialcell[c]{Response size\\2048-bit RSA\\(\si{\kilo\byte})}} & + {\specialcell[c]{Request size\\1024-bit RSA\\(\si{\kilo\byte})}} & + {\specialcell[c]{Response size\\1024-bit RSA\\(\si{\kilo\byte})}} \\ + \midrule + \texttt{/keys} & 0.14 & 3.75 & 0.14 & 3.43 \\ + \texttt{/reserve/withdraw} & 0.73 & 0.71 & 0.60 & 0.49 \\ + \texttt{/deposit} & 1.40 & 0.34 & 1.14 & 0.24 \\ + \texttt{/refresh/melt} & 1.06 & 0.35 & 0.85 & 0.35 \\ + \texttt{/refresh/reveal} & 1.67 & 2.11 & 1.16 & 1.23 \\ + \bottomrule + \end{tabular} + \caption[Request and response sizes for the exchange's API.]{Request and response sizes for the exchange's API. + In addition to the sizes for 2048-bit RSA keys (used throughout the benchmark), the sizes for 1024-bit RSA keys are also provided.} + \label{table:api-size} +\end{table} + +\begin{figure} + \includegraphics[width=\textwidth]{plots/latencies.pdf} + \caption[Effect of artificial network delay on exchange's latency.]{Effect of artificial network delay on exchange's latency.} + \label{fig:latencies} +\end{figure} + +% Missing benchmarks: +% overall Taler tx/s +% db io+tx/s +% If I have time: +% traffic/storage depending on key size? + + +\section{Current Limitations and Future Improvements}\label{sec:implementation-improvements} +Currently the auditor does not support taking samples of deposit confirmations that +merchants receive. The API and user interface to receive and process proofs +of misbehavior of the exchange/merchant generated by the wallet is not implemented yet. + +As a real-world deployment of electronic cash has rather high requirements for +the operational security, the usage of hardware security modules for generation +of signatures should be considered. Currently, a single process has access to +all key material. For a lower-cost improvement that decreases the performance +of the system, a threshold signature scheme could be used. + +The current implementation is focused on web payments. To use GNU Taler for +payments in brick-and-mortar stores, hardware wallets and smartphone apps for +devices with near-field-communication (NFC) must be developed. In some +scenarios, either the customer or the merchant might not have an Internet +connection, and this must be considered in the protocol design. In typical +western brick-and-mortar stores, it is currently more likely that the merchant +has Internet connectivity, and thus the protocol must allow operations of the +wallet (such as refreshing) to be securely routed over the merchant's +connection. In other scenarios, typically in developing countries, the +merchant (for example, a street vendor) might not have Internet connection. If +the vendor has a smartphone, the connection to the merchant can be routed +through the customer. In other cases, street vendors only have a ``dumb +phone'' that can receive text messages, and the payment goes through a provider +trusted by the merchant that sends text messages as confirmation for payments. +All these possibilities must be considered both from the perspective of the procotol and APIs +as well as the user experience. + +% FIXME: explain that exchange does threading + +Our experiments were only done with single exchange process and a single +database on the same machine. There are various ways to horizontally scale the +exchange: +\begin{itemize} + \item Multiple exchange processes can be run on multiple machines and access + the database that runs a separate machine. Requests are directed to the + machines running the exchange process via a load balancer. In this + scenario, the throughput of the database is likely to be the bottleneck. + \item To avoid having the database as a bottleneck, the contents can be + partitioned into shards. For this technique to be effective, data in the + shards should not have any dependencies in other shards. A natural way to + do sharding for the Taler exchange is to give each shard the sole + responsibility for a subset of all available denominations. + \item If the transaction volume on one denomination is too high to handle for + a single shard, transactions can be further partitioned based on the coin's + public key. Each would maintain the database of spent/refreshed coins for + a subset of all possible coin public keys. This approach has been + suggested for a centrally-banked cryprocurrency by Danezis and Meiklejohn + \cite{danezis2016rscoin}. +\end{itemize} + +% paranoid wallet (permissions!) + +% FIXME: I want to mention PADs for auditing/transparency somewhere, just +% because they're cool + + +% FIXME: coin locking not implemented! -- cgit v1.2.3