path: root/taler/implementation.tex

% TODO: what about KYC?  integrate into entities?

% FIXME:  what about the merchant's bank account detail
% without merchant registration in the no-auditor scenario?
% What if the merchant didn't register yet with a particular
% exchange?

% closing fee and wire fee discussion

% auditor: both parts
% db: schema with schemaspy

% DONE:
% decide on whether to do the payment with header or just
% extended fulfillment URL
% => use extended fulfillment URL for compat and subresources

% FIXME:  explain flow over QR code somewhere, where the wallet first creates the denomination
% key pair

% FIXME: conceptual API operations that each component offers

\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 the existing
financial system.

% FIXME:  maybe analyze instead how the high-level goals are achieved?
% FIXME:  maybe split into goals for wallet, exchange and merchant?
The following goals 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. 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 util 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{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 prococol 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 represention was chosen as the smallest
represetable 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.  The later constraints is 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.

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 (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-compatble 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, solid arrows denote signatures, dotted arrows denote blind signatures.}
\end{figure}

% FIXME:  this is not entirely true, as claiming a contract via the nonce
% can be MitM'ed without TLS
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 such as 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{<base-url>/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 deanomymize 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}

% FIXME: phasing in and out auditors
% FIXME: unclear
An exchange can be audited by zero, one or multiple auditors.  An auditor signs
each of the denominations offered by the exchange individually, as this makes
it possible to check that denominations are verified individually, without
having to verify all denominations.  However, an auditor must also audit all
denominations offered by an exchange.

\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.  Merchants do not need
to establish an a priori relationship with the exchange, but instead send their
bank account information when depositing coins.

% 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 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 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}
Payments in Taler are based on \emph{contract terms}, a JSON object that
describes the subject and modalities of a payment.  The cryptographic hash of
such a contract terms object can be used as a globally unique identifier for
the payment.  Merchants must sign the contract terms before sending them to the
customer, allowing a customer to prove what the merchant promised to them
in exchange for a payment in case of a dispute.

Unless a third party needs to get involved in a dispute, it is sufficient (and
desireable 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 bank
account information in deployments where KYC-registration of merchants with the
exchange is not required.

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{contract\_client\_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 nonce 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.

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 nonce.

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 nonce $n$ as a query parameter to the unclaimed
contract terms URL and making an HTTP \emph{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 contains their nonce $n$.
A malicious customer could try to claim other customers' contracts by guessing
contract term URLs and appending their own nonce.  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.}

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 e-mail once a ticket
becomes available.  The contract terms URL that allows the customer to purchase
the ticket (once they've visited a link in this e-mail), 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 (signed by the merchant),
  \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 POST 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 servers.

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 can give a
refund on the coins that have been previously deposited.

If refunds are 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.  Alternatively, the can reveal the contract terms to the
exchange and ask the exchange directly for a refund on the payment, as the
revealed contract terms prove that the payment has not been completed.

\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 e.g. a shopping basket.

The following steps illustrate a typical payment with the shop
\nolinkurl{alice-shop.example.com}.

% FIXME:  rename fulfillment instance URI to "extended instance URL",
% use headers instead, say that the extended instance URL is only for legacy compat

\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 header \texttt{Taler-Contract-Url:
    /contract?product=essay-24.pdf}
  \item Since the user's wallet does not yet contain contract terms with the
    fulfillment URI \nolinkurl{https://alice-shop.example.com/esasy-24.pdf}, it
    claims the contract by generating a nonce and requesting the URL
    \nolinkurl{https://alice-shop.example.com/contract?product=essay-24.pdf\&nonce=NONCE}.
  \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 fulfillment instance URI 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 fulfillment instance URI 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 cookie in the user's browser which indicates that
\texttt{essay-42.pdf} has been purchased.

If the user returns to the plain fulfillment URI (and does not have a session
cookie set), the wallet will recognize that the resource has already been paid
for when receiving the HTTP 402 response from the shop.  In this case, the
wallet navigates to the fulfillment instance URL from an existing purchase.

\subsubsection{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 402 status code and handle the Taler-specific headers correctly.
We now define a fallback, which is transparently implemented in the reference merchant backend.

Instead of indicating that a payment is required for a resource in the HTTP status code and header,
the mechant included a fallback URL in the body of the 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 the URL \nolinkurl{taler:pay?contract\_url=\%2Fcontract\%3Fproduct\%3Dessay-24.pdf}.

\subsubsection{Multiple Origins}
% FIXME:  give illustrative example 

The initiation and processing of the payment must be possible from an origin
that differs from the shop's origin without compromising security of privacy.
The design discussed so far already allows the pay URL, fulfillment URL and
contract URL to be on different origins.  However, when a payment is triggered
from a page that differs from the fulfillment URL of the corresponding
resource, the detection mechanism of the wallet that searches for an existing
payment for that resource does not work; the user would be asked to repeat the
payment for something they already purchased.\footnote{
  Note that a 402 response can be given without offering a contract URL to the user,
  for example when a product could be purchased in the past, can still be viewed, but
  not purchased anymore.  Thus matching of an existing payment cannot rely on downloading
  the new contract.
}

To rectify this, the 402 response can specify an additional parameter, the
``Taler-Resource-Url'' header, which indicates the resource that is the
subject of the payment request.  Unless implemented carefully, this introduces
a privacy violation:  To check whether a user has paid for a particular
resource with URL $u$, an arbitrary website can send an HTTP 402 response with
the ``Taler-Resource-Url'' header set to $u$ and the ``Taler-Contract-Url''
set to an URL pointing to the attacker's server.  If the user paid for $u$, the
wallet will navigate to the fulfillment instance 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 URI.\footnote{This countermeasure is well
known in browsers as the same origin policy}

The resource URL can also be set to a random unique identifier to allow
recurring purchases of the same resource, disabling the wallet's lookup of
existing payments for the same resource.

\subsubsection{Payments for Subresources}
Sometimes subresources (such as embedded videos or images) on a website should
only be available to customers that have paid for them.  Contract terms
in GNU Taler only allow a single fulfillment URL.  To allow payments for subresources,
the following techniques are possible:

\begin{itemize}
  \item The page shown by the fulfillment URL can set a cookie,
    and the merchant can check for the presence of this cookie
    when serving ``pay-walled'' subresources.
  \item If a website must work without any session-cookies,
    the fulfillment page can extend the URLs of subresources with
    the additional parameters used in the extended fulfillment URL,
    and check the validity of these parameters when service the subresource.
\end{itemize}

While it would be technically possible to specify in the contract terms that it
covers other resources in addition to the fulfillment URL (specified as a list
of even as wildcards), this addition might be detrimental to the user's
privacy.  If a merchant specifies a wildcard that covers their whole website,
the browser would send the corresponding order ID on each visit to any site on
the merchant's domain, effectively providing an additional method for user
tracking.

\subsection{Session-bound Payments and Sharing}
As we described the payment protocol so far, an extended fulfillment URL (which
is only used for browsers that do not fully/natively integrate with Taler) is
not bound to a browser session.  When sharing an extended fulfillment instance
URL, another user would get access to the same content.  This is not
appropriate for digital content.  While it is trivial to share digital content
unless digital restriction 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 fulfillment instance URL is extended
with an additional parameter \texttt{session\_sig}, which contains proof that
the user completed the payment under their current session ID or has access to
the payment receipt in their wallet.

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,
either by executing (or re-playing)
the content or by showing the payment receipt together with the 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 Taler backend.  Using session signatures instead of storing
all completed session-bound payments in the merchant's database saves storage.

While the payment receipt could be shared with other wallets, it is a higher
barrier than sharing a URL.  Furthermore the merchant could restrict the rate
at which new session 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 URI 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{Privact Implications}
FIXME: discuss what happens with embedded content
% Especially of embedded content

\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 of the coin again.  A refund is only possible until the refund
deadline, which is specified in the contract terms and subsequently in the
deposit permission.  Each individual refund on each coin incurs fees; the
refund fee is subtracted from the amount given back to the customer and kept be
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, as 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. A HTTP GET 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{XXX}) to allow the
merchant to pay small amounts (without any associated contract terms or legal
obligations!) into the customer'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 (planchets) generated by the user that is being given the tip.

The merchant triggers giving a tip with a HTTP 402 response that has the ``X-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
  \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 from the tip token.

The list of planchets is then sent to the merchant via an HTTP POST 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
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.


% this is rather short, maybe put into table way earlier?
\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,
  \item the nonce used by the customer 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, (FIXME:  order ID should be explained earlier)
  \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, (FIXME: more detail)
  \item the deadline for refunds,
  \item the hashed bank account information of the merchant (needed by the wallet to sign the deposit permissions),
  \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{Wallet Signalling}
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} is non-empty, 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}
      \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

\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-redable ``instruction''
field.  }

\subsection{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
addition information for a payment in the request 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 (in the form of an IETF draft currently
at the time of writing) of the \texttt{payto} URI is in Appendix \ref{XXX}.

In the implementation of Taler, \texttt{payto} URIs are used in various places:
\begin{enumerate}
  \item The exchange lists the 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 he wishes to be paid on as a \texttt{payto} URI
\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.

\subsection{Demo Bank}
For demonstration purposes and integration testing we use our toy bank
implementation, 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{x-taler-bank}.  The authority part encodes the base URL of the bank,
and the path must be a single component with in integer between $1$ and $2^52$.

\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 communicate via the same database.  Only
\texttt{taler-exchange-httpd} needs access to the exchanges online signing keys
and denomination keys.i

The database is accessed via a Taler-specific database abstraction layer.
Different databases can be supported via plugins; currently only PostgreSQL is
supported as a database.

Wire plugins are used as an abstraction to access the account layer that Taler
runs on.  Specifically, the 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've 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 can ``undo'' a deposit if the merchant gave their signature, and the aggregation deadline
    for the payment has not occured 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}

Additional tools exist for generation of new keys according to a configurable
schedule, as well as to sign those keys offline by the exchange's master public
key.

\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?
  \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
increasind row ID.  Thus the auditor's checkpoint simply consists of the set of
row IDs that were last seen.

In future versions, the auditor will also have a \emph{taler-auditor-httpd}
process that allows 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.

\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 is divided into two types of HTTP endpoints: \begin{enumerate}
  \item Functionality that is accessed 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 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 integrates
with other components such as order processing and shipping.

\subsection{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 nonce 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 store front can redirect the customer to this
payment redirect URL; visiting the URL will trigger the customer's
browser/wallet to prompt for a payment.

% FIXME: maybe make this a diagram?
%The following example illustrates how a merchant uses the Taler merchant backend:
%\begin{enumerate}
%  \item 
%\end{enumerate}

%\subsection{Back Office APIs}
%The back office API allows the merchant to query information about previous and
%ongoing payments.

%\subsection{Instances}

\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]
  %\item[Back office]
\end{description}

\section{Wallet}

\begin{figure}
    \includegraphics[width=\textwidth]{diagrams/taler-diagram-wallet.png}
    \caption{Architecture of the wallet reference implementation}
\end{figure}

\subsection{Web Security}
The API exposed by the wallet could introduce security and privacy risks if not designed carefully.

The merchant can only trigger two actions:  GET requests and redirects

The presence of the Taler wallet itself leaks one bit of information that can be used in a finger print
of the user's browser.

\subsection{Implementation Details}
The reference implementation of the wallet is written in the TypeScript
language against the WebExtension API, a cross-browser mechanism for browser
extensions.

Many cryptographic operations needed to implement the wallet are not commonly
available in a browser environment.  We cross-compile the Taler utility library
as well as its dependencies to asm.js using the LLVM-based emscripten
toolchain.

Cryptographic operations run in an isolated process implemented as a WebWorker.

%TODO:  performance comparison for signature operations with the wallet
%and the native library

% TODO:  make diagram with the wallet components,
% indexeddb, crypto, etc.

% FIXME: write
%\subsection{Backup and Synchronization}

%\subsection{return-to-bank-account}

%\subsection{Coin Selection}
%... for withdrawin and paying, and how it influences fees paid and anonymity.

\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.  Effectively this corresponds to a concrete instantiation of the
protocols in Section \ref{sec:abstract-instantiation}.

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{Withdrawal Protocol}
\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$.  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=\small]{%
\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, 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, 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 \rangle \< \< \\
\t \sigma_{(D,i)} := \V{Ed25519.Sign}(c_s, \rho_{(D,i)}) \< \< \\
\text{Persist } \langle \sigma_P, cf, \rho_P, \rho_{(D,i)}, \sigma_{(D,i)}, 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 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 \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 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{The RefreshDerive algorithm running with the seed $s$ on dirty coin $C_p$ to
   generate a fresh coin signed with denomination key $pkD := \langle e,N\rangle$.}
\label{fig:refresh-derive}
\end{figure}


\begin{figure}
\centering
\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}
\centering
\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^{(0)}, T_\gamma^{(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
\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
neglegible to the work done by the exchange, and is thus not a bottleneck.

\subsection{Wallet}
We provide a microbenchmark for the performance of cryptographic operations in
the wallet (Table~\ref{table:wallet-benchmark)}.  Even on a low-end smartphone
devices, the most expensive cryptographic operations remains well under
$150ms$, a threshold for user-interface latency under which user happyiness and
productivity is considered to be unaffected \cite{tolia2006quantifying}.  When
signing multiple coins for a single payment, the total time required to
generate signatures can exceed $150ms$.  To provide a better user experience in
these cases, 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.  We believe that 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.


\begin{table}\label{table:wallet-benchmark}
  \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) G3 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}
\end{table}


\subsection{Exchange}
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) than the benchmark driver, mock bank and clients.
At the end, the benchmark outputs the number of deposited coins per second and
latency statistics.

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 denomination keys for all of our exchange benchmarks.

\subsubsection{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 transaction, 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 rather 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 randomly select a value to spend 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 using 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.

We obtained the following results:
\begin{itemize}
  \item $8.3$ spend operations and $1.3$ refresh operations are executed on
    average per transaction
  \item a refresh operation has on average $4.2$ output coins 
\end{itemize}

Thus for our benchmark, for every spend operation we run a refresh operation
with probability $1/10$, where each refresh operation produces $4$ output
coins.  When we specify the number transactions per second, we divide the
number of spend operations 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{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.

Table~\ref{table:benchmark:ops-baseline} shows the time used for cryptographic
operations, together with the number of times they are executed inside the the
client / mock bank 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 less processes/threads than the number of
available CPUs on our machine.

The benchmark completed in $17.14$ minutes. We obtained the total CPU usage of
the benchmark testbed and exchange.

The size of the database for $10000$ coins is $\SI{104.26}{\mebi\byte}$, including indices.
The TCP/IP network traffic between the exchange, clients and the mock bank
was $\SI{9.49}{\mebi\byte}$.

\begin{table}
  \centering
  \begin{tabular}{lSSS}
  \toprule
  Operation & {Time/Op ($\mu{}s$)} & {Count (exchange)} & {Count (clients)} \\
  \midrule
eddsa key create            & 1896.27   &  0      & 12180  \\ 
ecdhe key get public        & 1272.64   &  2430   & 4860   \\ 
rsa unblind                 & 1348.62   &  0      & 21898  \\ 
eddsa key get public        & 1729.69   &  9720   & 80340  \\ 
eddsa ecdh                  & 1301.78   &  0      & 4860   \\ 
rsa sign blinded            & 5284.88   &  17053  & 0      \\ 
rsa blind                   & 695.25   &  9720   & 31633  \\ 
hkdf                        & 40.61   &  65057  & 193506 \\ 
eddsa sign                  & 5182.33   &  13393  & 25608  \\ 
ecdh eddsa                  & 1338.62   &  2430   & 3645   \\ 
rsa verify                  & 421.19   &  13393  & 29216  \\ 
ecdhe key create            & 1825.38   &  0      & 3645   \\ 
rsa private key get public  & 5.30       &  0      & 40     \\ 
eddsa verify                & 3976.96   &  25586  & 25627  \\ 
hash                        & 1.41   &  165608 & 169445 \\ 
hash context start          & 11.38   &  1215   & 1227   \\ 
hash context read           & 0.81  &  25515  & 25655  \\ 
hash context finish         & 0.28  &  1215   & 1227   \\ 
  \bottomrule
  \end{tabular}
  \label{table:baseline-benchmark}
  \caption{Cryptographic operations in the benchmark with one client and $10000$ operations.}
\end{table}

\subsection{Transaction Rate and Scalability}
Figure~\ref{foo} shows the time taken to process one coin for different numbers of parallel clients.

\begin{figure}
  \includegraphics[width=\textwidth]{plots/speed.pdf}
  \caption{Average time per coin in relation to number of parallel clients, with $10000$ coins per run.}
  \label{fig:speed}
\end{figure}

\begin{figure}
  \includegraphics[width=\textwidth]{plots/cpu.pdf}
  \caption{Comparison of real time, the CPU time for the exchange and the whole benchmark.}
  \label{fig:speed}
\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.

\begin{table}
  \centering
  \begin{tabular}{lSS}
  \toprule
  Endpoint & {Base latency (ms)} & {Delay (100ms) latency (ms)} \\
  \midrule
  \texttt{/refresh/melt}     &  19.96  &    620.98   \\ 
  \texttt{/refresh/reveal}   &  82.87  &   684.41    \\
  \texttt{/keys}             &  0.95   &    401.21   \\ 
  \texttt{/reserve/withdraw} &  19.43  &    620.50   \\ 
  \texttt{/deposit}          &  19.66  &   620.96    \\
  \bottomrule
  \end{tabular}
  \label{table:baseline-benchmark}
  \caption{Effects of $100ms$ symmetric network delay on total latency.}
\end{table}

% Missing benchmarks:
% overall Taler tx/s
% db io+tx/s
% If I have time:
% traffic/storage depending on key size?

% FIXME: talk about guix and reproducibility?


\section{Current Limitations and Future Improvements}\label{sec:implementation-improvements}
Currently the auditor does not support taking samples of deposit confirmations that
merchants receive.  Furthermore 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 we 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 effectly, 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!