diff options
Diffstat (limited to 'doc/system/taler')
-rw-r--r-- | doc/system/taler/blockchain-accountability.tex | 1 | ||||
-rw-r--r-- | doc/system/taler/design.tex | 1286 | ||||
-rw-r--r-- | doc/system/taler/implementation.tex | 2198 | ||||
-rw-r--r-- | doc/system/taler/security.tex | 1729 | ||||
-rw-r--r-- | doc/system/taler/snippet-keys.txt | 62 |
5 files changed, 5276 insertions, 0 deletions
diff --git a/doc/system/taler/blockchain-accountability.tex b/doc/system/taler/blockchain-accountability.tex new file mode 100644 index 000000000..3c72a24a6 --- /dev/null +++ b/doc/system/taler/blockchain-accountability.tex @@ -0,0 +1 @@ +\chapter{Exchange-accountable e-cash} diff --git a/doc/system/taler/design.tex b/doc/system/taler/design.tex new file mode 100644 index 000000000..8ee3ff3c9 --- /dev/null +++ b/doc/system/taler/design.tex @@ -0,0 +1,1286 @@ + +% FIXME: maybe move things around a bit, structure it better into +% sections and subsections? + +% FIXME: talk about amounts and anonymity + + +\chapter{GNU Taler, an Income-Transparent Anonymous E-Cash System}\label{chapter:design} + +This chapter gives a high-level overview of the design of GNU Taler, based on +the requirements discussed in Chapter~\ref{chapter:introduction}. The +cryptographic protocols and security properties are described and analyzed in detail in +Chapter~\ref{chapter:security}. A complete implementation with focus on of Web +payments is discussed in Chapter~\ref{chapter:implementation}. + + +\section{Design of GNU Taler} + +GNU Taler is based on the idea of Chaumian e-cash \cite{chaum1983blind}, with +some differences and additions explained in the following sections. Other +variants and extensions of anonymous e-cash and blind signatures are discussed in +Section~\ref{sec:related-work:e-cash}. + + +\subsection{Entities and Trust Model} +GNU Taler consists of the following entities (see \ref{fig:taler-arch}): +\begin{itemize} + \item The \emph{exchanges} serve as payment service provider for a + financial transaction between a customer and a merchant. They hold bank money + in escrow in exchange for anonymous digital \emph{coins}. + \item The \emph{customers} keep e-cash in their electronic \emph{wallets}. + \item The \emph{merchants} accept digital coins in exchange for digital or physical + goods and services. The digital coins can be deposited with the exchange, + in exchange for bank money. + \item The \emph{banks} receive wire transfer instructions from customers + and exchanges. A customer, merchant and exchange involved in one + GNU Taler payment do not need to have accounts with the same bank, + as long as wire transfers can be made between the respective banks. + \item The \emph{auditors}, typically run by trusted financial regulators, + monitor the behavior of exchanges to assure customers and merchants that + exchanges operate correctly. +\end{itemize} + +\begin{figure} + \begin{center} + \begin{tikzpicture} + \tikzstyle{def} = [node distance= 5em and 6.5em, inner sep=1em, outer sep=.3em]; + \node (origin) at (0,0) {}; + \node (exchange) [def,above=of origin,draw]{Exchange}; + \node (customer) [def, draw, below left=of origin] {Customer}; + \node (merchant) [def, draw, below right=of origin] {Merchant}; + \node (auditor) [def, draw, above right=of origin]{Auditor}; + + \tikzstyle{C} = [color=black, line width=1pt] + + \draw [<-, C] (customer) -- (exchange) node [midway, above, sloped] (TextNode) {withdraw coins}; + \draw [<-, C] (exchange) -- (merchant) node [midway, above, sloped] (TextNode) {deposit coins}; + \draw [<-, C] (merchant) -- (customer) node [midway, above, sloped] (TextNode) {spend coins}; + \draw [<-, C] (exchange) -- (auditor) node [midway, above, sloped] (TextNode) {verify}; + + \end{tikzpicture} + \end{center} + \caption[High-level overview of GNU Taler components.]{High-level overview of the different components of GNU Taler, banks are omitted.} + \label{fig:taler-arch} +\end{figure} + +In GNU Taler, the exchanges can be separate entities from the banks. This fosters +competition between exchanges, and allows Taler to be deployed in an +environment with legacy banks that do not support Taler directly. + +If a customer wants to pay a merchant, the customer needs to hold coins at an +exchange that the merchant trusts. To make the selection of trusted exchanges +simpler, merchants and customers can choose to automatically trust all +exchanges audited by a certain auditor. + +The exchange is trusted to hold funds of its customers in escrow and to make +payments to merchants when digital coins are deposited. Customer and merchant +can have assurances about the exchange's liquidity and operation though the +auditor, which would typically be run by financial regulators or other trusted +third parties. + +\subsection{System Assumptions} + +We assume that an anonymous, bi-directional communication channel\footnote{% +An anonymization layer like Tor \cite{dingledine2004tor} can provide a +practical approximation of such a communication channel, but does not provide +perfect anonymity \cite{johnson2013users}. +} is used for +all communication between the customer and the merchant, as well as for +obtaining unlinkable change for partially spent coins from the exchange and for +retrieving the exchange's public keys used in verifying and blindly signing +coins. The withdrawal protocol, on the other hand, does not require an +anonymous channel to preserve the anonymity of electronic coins. + +During withdrawal, the exchange knows the identity of the withdrawing customer, +as there are laws, or bank policies, that limit the amount of cash that an +individual customer can withdraw in a given time +period~\cite{france2015cash,greece2015cash}. GNU Taler is thus only anonymous with +respect to \emph{payments}. While the exchange does know their customer (KYC), +it is unable to link the known identity of the customer that withdrew anonymous +digital coins to the \emph{purchase} performed later at the merchant. + +While customers can make untraceable digital cash payments, the exchange will +always learn the merchants' identity, which is necessary to credit their +accounts. This information can also be used for taxation, and GNU Taler +deliberately exposes these events as anchors for tax audits on merchants' +income. Note that while GNU Taler \emph{enables} taxation, it does not +\emph{implement} any automatic taxation. + +GNU Taler assumes that each participant has full control over their +system% +\footnote{% + Full control goes both ways: it gives the customer the freedom to run their own software, + but also means that the behavior of fraudulent customers cannot be restricted by + simpler technical means such as keeping balances on tamper-proof smart cards, + and thus can lead to an overall more complex system. +}. We assume the contact information of the exchange is known to +both customer and merchant from the start, and the customer +can authenticate the merchant, for example, by using X.509 +certificates~\cite{rfc6818}. A GNU Taler merchant is expected to deliver +the service or goods to the customer upon receiving payment. The +customer can seek legal relief to achieve this, as the customer +receives cryptographic evidence of the contract and the associated +payment. + +% FIXME: who needs to be trusted for anonymity? + + +\subsection{Reserves} +A \emph{reserve} refers to a customer's non-anonymous funds at an exchange, +identified by a reserve public key. Suppose a customer wants to convert money +into anonymized digital coins. To do that, the customer first creates a +reserve private/public key pair, and then transfers money via their bank to the +exchange. The wire transfer instruction to the bank must include the reserve +public key. To withdraw coins from a reserve, the customer authenticates +themselves using the corresponding reserve private key. + +Typically, each wire transfer is made with a fresh reserve public key and thus +creates a new reserve, but making another wire transfer with the same reserve +public key simply adds funds to the existing reserve. Even after all funds +have been withdrawn from a reserve, customers should keep the reserve key pair +until all coins from the corresponding reserve have been spent, as in the event +of a denomination key revocation (see Section \ref{sec:revocation-payback}) the +customer needs this key to recover coins of revoked denominations. + +The exchange automatically transfers back to the customer's bank account any +funds that have been left in a reserve for an extended amount of time, allowing +customers that lost their reserve private key to eventually recover their +funds. If a wire transfer to the exchange does not include a valid reserve public key, +the exchange transfers the money back to the sender. + +% FIXME: this really needs a diagram + +Instead of requiring the customer to manually generate reserve key pairs and +copy them onto a wire transfer form, banks can offer tight integration with the +GNU Taler wallet software. In this scenario, the bank's website or banking app +provides a ``withdraw to GNU Taler wallet'' action. After selecting this +action, the user is asked to choose the amount to withdraw from their bank +account into the wallet. The bank then instructs the GNU Taler wallet software +to create record of the corresponding reserve; this request contains the anticipated amount, the +reserve key pair and the URL of the exchange to be used. When invoked by the +bank, the wallet asks the customer to select an exchange and to confirm the +reserve creation. The exchange chosen by the customer must support the wire +transfer method used by the bank, which will be automatically checked by the +wallet. Typically, an exchange is already selected by default, as banks can +suggest a default exchange provider to the wallet, and additionally wallets +have a pre-defined list of trusted exchange providers. Subsequently, the wallet +hands the reserve public key and the bank account information of the selected +exchange back to the bank. The bank---typically after asking for a second authentication +factor from the customer---will then trigger a wire transfer to the exchange with +the information obtained from the wallet. + +When the customer's bank does not offer tight integration with GNU Taler, the +customer can still manually instruct their wallet to create a reserve. The public +key must then be included in a bank transaction to the exchange. When the +customer's banking app supports pre-filling wire transfer details from a URL or +a QR code, the wallet can generate such a URL or QR code that includes the +pre-filled bank account details of the exchange as well as the reserve public +key. The customer clicks on this link or scans the QR code to invoke their +banking app with pre-filled transaction details. Since there currently is no +standardized format for pre-filled wire transfer details, we are proposing the +\texttt{payto://} URI format explained in +Section~\ref{implementation:wire-method-identifiers}, currently under review +for acceptance as an IETF Internet Standard. + + +% FIXME: withdrawal strategy, coin selection + +\subsection{Coins and Denominations} +Unlike plain Chaumian e-cash, where a coin just contains a serial number, a +\emph{coin} in Taler is a public/private key pair where the private key is only +known to the owner of the coin. + +A coin derives its financial value from a blind signature on the coin's +public key. The exchange has multiple \emph{denomination key} pairs available +for blind-signing coins of different financial values. Other approaches for representing +different denominations are discussed in Section~\ref{design:related-different-denominations}. + +Denomination keys have an expiration date, before which any coins signed with +it must be spent or exchanged into newer coins using the refresh protocol +explained in Section \ref{sec:design-refresh}. This allows the exchange to +eventually discard records of old transactions, thus limiting the records that +the exchange must retain and search to detect double-spending attempts. If a +denomination's private key were to be compromised, the exchange can detect this +once more coins are redeemed than the total that was signed into existence +using that denomination key. Should such an incident occur, the exchange can allow authentic +customers to redeem their unspent coins that were signed with the compromised +private key, while refusing further deposits involving coins signed by the +compromised denomination key (see Section~\ref{sec:revocation-payback}). As a result, the +financial damage of losing a private signing key is limited to at most the +amount originally signed with that key, and denomination key rotation can be +used to bound that risk. + +To prevent the exchange from deanonymizing users by signing each coin with a +fresh denomination key, exchanges publicly announce their denomination keys +in advance with validity periods that imply sufficiently strong anonymity sets. +These announcements are expected to be signed with an offline long-term +private \emph{master signing key} of the exchange and the auditor. +Customers should obtain these announcements using an anonymous +communication channel. + +After a coin is issued, the customer is the only entity that knows the +private key of the coin, making them the \emph{owner} of the coin. Due +to the use of blind signatures, the exchange does not learn the +public key during the withdrawal process. If the private key is +shared with others, they become co-owners of the coin. Knowledge of +the private key of the coin and the signature over the coin's public +key by an exchange's denomination key enables spending the +coin. + +\subsection{Partial Spending and Unlinkable Change} + +Customers are not required to have exact change ready when making a payment. +In fact, it should be encouraged to withdraw a larger amount of e-cash +beforehand, as this blurs the correlation between the non-anonymous withdrawal +event and the anonymous spending event, increasing the anonymity set. + +A customer spends a coin at a merchant by cryptographically signing a +\emph{deposit permission} with the coin's private key. A deposit permission +contains the hash of the \emph{contract terms}, i.e., the details of the +purchase agreement between the customer and merchant. Coins can be +\emph{partially} spent, and a deposit permission specifies the fraction of the +coin's value to be paid to the merchant. As digital coins are trivial to copy, +the merchant must immediately deposit them with the exchange, in order to get a +deposit confirmation or an error that indicates double spending. + +When a coin is used in a completed or attempted/aborted payment, the coin's +public key is revealed to the merchant/exchange, and further payments with the +remaining amount would be linkable to the first spending event. To obtain +unlinkable change for a partially spent (or otherwise revealed coin), GNU Taler +introduces a \emph{refresh protocol}. The refresh protocol allows the customer +to obtain new coins for the remaining amount on a coin. The old coin is marked +as spent after it has been refreshed into new coins. Using blind signatures to +withdraw the refreshed coins makes them unlinkable from the old coin. + +% FIXME: talk about logarithmic time, simulation + +\subsection{Refreshing and Taxability}\label{sec:design-refresh} +% FIXME: maybe put section on how to avoid withdraw loophole here! +One goal of GNU Taler is to make merchants' income transparent to state auditors, +so that income can be taxed appropriately. Naively implemented, however, a simple +refresh protocol could be used to evade taxes: the payee of an untaxed +transaction would generate the private keys for the coins that result from +refreshing a (partially spent) old coin, and send the corresponding public keys +to the payer. The payer would execute the refresh protocol, provide the +payee's coin public keys for blind signing, and provide the signatures to the +payee, who would now have exclusive control over the coins. + +To remedy this, the refresh protocol introduces a \emph{link threat}: coins are +refreshed in such a way that the owner of the old coin can always obtain the +private key and exchange's signature on the new coins resulting from refreshes, +using a separate \emph{linking protocol}. This introduces a threat to +merchants that try to obtain untaxed income. Until the coins are finally +deposited at the exchange, the customer can always re-gain ownership of them +and could deposit them before the merchant gets a chance to do so. This +disincentivizes the circulation of unreported income among untrusted parties in +the system. + +In our implementation of the refresh and linking protocols, there is a +non-negligible success chance ($\frac{1}{\kappa}$, depending on system parameter +$\kappa$, typically $\ge 3$) for attempts to cheat during the refresh protocol, +resulting in refreshed coins that cannot be recovered from the old coin via the +linking protocol. Cheating during refresh, however, is still not +\emph{profitable}, as an unsuccessful attempt results in completely losing the +amount that was intended to be refreshed. + +% FIXME: mention that we don't want to use DRM/HSMs for this + +For purposes of anti-money-laundering and taxation, a more detailed audit of +the merchant's transactions can be desirable. A government tax authority can +request the merchant to reveal the business agreement details that match the +contract terms hash recorded with the exchange. If a merchant is not able to +provide theses values, they can be subjected to financial penalties by the +state in relation to the amount transferred by the traditional currency +transfer. + +\subsection{Transactions vs. Sharing} + +Sharing---in contrast to a transaction---happens when mutually trusted parties +simultaneously have access to the private keys and signatures on coins. +Sharing is not considered a transaction, as subsequently both parties have equal control +over the funds. A useful application for sharing are peer-to-peer payments +between mutually trusting parties, such as families and friends. + +\subsection{Aggregation} +For each payment, the merchant can specify a deadline before which the exchange +must issue a wire transfer to the merchant's bank account. Before this +deadline occurs, multiple payments from deposited coins to the same merchant +can be \emph{aggregated} into one bigger payment. This reduces transaction +costs from underlying banking systems, which often charge a fixed fee per +transaction. To incentivize merchants to choose a longer wire transfer +deadline, the exchange can charge the merchant a fee per aggregated wire +transfer. + + +\subsection{Refunds} +The aggregation period also opens the opportunity for cheap \emph{refunds}. If +a customer is not happy with their product, the merchant can instruct the +exchange to give the customer a refund before the wire transfer deadline has +occurred. This effectively ``undoes'' the deposit of the coin, and restores the +available amount left on it. The refresh protocol is then used by the customer +on the coins involved in a refund, so that payments remain unlinkable. + + +% FIXME: mention EU customer laws / 14 weeks? + +\subsection{Fees} +In order to subsidize the operation of the exchange and enable a sustainable +business model, the exchange can charge fees for most operations. For +withdrawal, refreshing, deposit and refunds, the fee is dependent on the denomination, +as different denominations might have different key sizes, security and storage +requirements. + +Most payment systems hide fees from the customer by putting them to the merchant. +This is also possible with Taler. As different exchanges (and denominations) +can charge different fees, the merchant can specify a maximum amount of fees it +is willing to cover. Fees exceeding this amount must be explicitly paid by the +customer. + +Another consideration for fees is the prevention of denial-of-service attacks. +To make ``useless'' operations, such as repeated refreshing on coins +(causing the exchange to use relatively expensive storage), unattractive to an +adversary, these operations must charge a fee. Again, for every refresh +following a payment, the merchant can cover the costs up to a limit set by the +merchant, effectively hiding the fees from the customer. + +Yet another type of fee are the \emph{wire transfer fees}, which are charged +by the exchange for every wire transfer to a merchant in order to compensate for +the cost of making a transaction in the underlying bank system. The wire +transfer fees encourage merchants to choose longer aggregation periods, as the +fee is charged per transaction and independant of the amount. + +Merchants can also specify the maximum wire fee they are willing to cover for +customers, along with an \emph{amortization rate} for the wire fees. In case +the wire fees for a payment exceed the merchant's chosen maximum, the customer +must additionally pay the excess fee divided by the amortization rate. The +merchant should set amortization rate to the expected number of transactions +per wire transfer aggregation window. This allows the merchant to adjust +the total expected amount that it needs to pay for wire fees. + + +\subsection{The Withdraw Loophole and Tipping}\label{taler:design:tipping} +The withdraw protocol can be (ab)used to illicitly transfer money, when the +receiver generates the coin's secret key, and gives the public key to the party +executing the withdraw protocol. We call this the ``withdraw loophole''. This +is only possible for one ``hop'', as money can still not circulate among +mutually distrusted parties, due to the properties of the refresh protocol. + +A ``benevolent'' use of the withdraw loophole is \emph{tipping}, where merchants give +small rewards to customers (for example, for filling out a survey or installing +an application), without any contractual obligations or digitally signed +agreement. + +% FIXME: argue that this can't be done on scale for money laundering + +\subsubsection{Fixing the Withdraw Loophole}\label{taler:design:fixing-withdraw-loophole} + +In order to discourage the usage of the withdraw loophole for untaxed payments, +the following approach would be possible: Normal withdraw operations and +unregistered reserves are disabled, except for special tip reserves that are +registered by the merchant as part of a tipping campaign. Customers are +required to pre-register at the exchange and obtain a special withdraw key pair +against a small safety deposit. Customer obtain new coins via a refresh +operation from the withdraw key to a new coin. If customers want to abuse +Taler for untaxed payments, they either need to risk losing money by lying +during the execution of the refresh protocol, or share their reserve private +key with the payee. In order to discourage the latter, the exchanges gives the +safety deposit to the first participant who reports the corresponding private +key as being used in an illicit transaction, and requires a new safety deposit +before the customer is allowed to withdraw again. + +However since the withdraw loophole allows only one additional ``payment'' (without any +cryptographic evidence that can be used in disputes) before the coin must be deposited, +these additional mitigations might not even be justified considering their additional cost. + + +\section{Auditing} +The auditor is a component of GNU Taler which would typically be deployed by a +financial regulator, fulfilling the following functionality: +\begin{itemize} + \item It regularly examines the exchange's database and + bank transaction history to detect discrepancies. + \item It accepts samples of certain protocol responses that merchants + received from an audited exchange, to verify that what the exchange signed + corresponds to what it stored in its database. + \item It certifies exchanges that fulfill the operational and financial requirements + demanded by regulators. + \item It regularly runs anonymous checks to ensure that the required protocol + endpoints of the exchange are available. + \item In some deployment scenarios, merchants need to pre-register with exchanges to fulfill know-your-customer (KYC) requirements. + The auditor provides a list of certified exchanges to merchants, + to which the merchant then can automatically KYC-register. + \item It provides customers with an interface to submit cryptographic proof that an exchange + misbehaved. If a customer claims that the exchange denies service, it can execute a request on + behalf of the customer. +\end{itemize} + +%An exchange operator would typically run their own instance of the auditor software, +%to ensure correct operation. + +% FIXME: live auditing + +% FIXME: discuss indian merchant scenario + +\subsection{Exchange Compromise Modes} +The exchange is an attractive target for hackers and insider threats. We now +discuss different ways that the exchange can be compromised, how to reduce the +likelihood of such a compromise, and how to detect and react to such an event +if it happens. + +\subsubsection{Compromise of Denomination Keys and Revocation}\label{sec:revocation-payback} +When a denomination key pair is compromised, an attacker can ``print money'' by +using it to sign coins of that denomination. An exchange (or its auditor) can +detect this when the number of deposits for a certain denomination exceed the +number of withdrawals for that same denomination. + +We allow the exchange to revoke denomination keys, and wallets periodically +check for such revocations. We call a coin of a revoked denomination a revoked +coin. If a denomination key has been revoked, the wallets use the +\emph{payback} protocol to recover funds from coins of revoked denominations. +Once a denomination is revoked, new coins of this denomination can't be +withdrawn or used as the target denomination for a refresh operation. A revoked +coin cannot be spent, and can only be refreshed if its public key was recorded +in the exchange's database (as spending/refresh operations) before it was +revoked. + +The following cases are possible for payback: +\begin{enumerate} + \item The revoked coin has never been seen by the exchange before, but the + customer can prove via a withdraw protocol transcript and blinding factor + that the coin resulted from a legitimate withdrawal from a reserve. In + this case, the exchange credits the reserve that was used to withdraw the + coin with the value of the revoked coin. + \item The coin has been partially spent. In this case, the exchange allows + the remaining amount on the coin to be refreshed into fresh coins of + non-revoked denominations. + \item The revoked coin $C_R$ has never been seen by the exchange before, was + obtained via the refresh protocol, and the exchange has an existing record + of either a deposit or refresh for the ancestor coin $C_A$ that was + refreshed into the revoked coin $C_R$. If the customer can prove this by + showing a corresponding refresh protocol transcript and blinding factors, the exchange credits + the remaining value of $C_R$ on $C_A$. It is explicitly permitted for $C_A$ + to be revoked as well. The customer can then obtain back their funds by + refreshing $C_A$. +\end{enumerate} + +These rules limit the maximum financial damage that the exchange can incur from +a compromised denomination key $D$ to $2nv$, with $n$ being the +maximum number of $D$-coins simultaneously in circulation and $v$ the financial +value of a single $D$-coin. Say denomination $D$ was withdrawn by +legitimate users $n$ times. As soon as the exchange sees more +than $n$ pairwise different $D$-coins, it must immediately +revoke $D$. An attacker can thus at most gain $nv$ by either +refreshing into other non-revoked denominations or spending the forged $D$-coins. +The legitimate users can then request a payback for their coins, resulting in +a total financial damage of at most $2nv$. + +With one rare exception, the payback protocol does not negatively impact the +anonymity of customers. We show this by looking at the three different cases +for payback on a revoked coin. Specifically, in case (1), the coin obtained +from the credited reserve is blindly signed, in case (2) the refresh protocol +guarantees unlinkability of the non-revoked change, and in case (3) the revoked +coin $C_R$ is assumed to be fresh. If $C_R$ from case (3) has been seen by a +merchant before in an aborted/unfinished transaction, this transaction would be +linkable to transactions on $C_A$. Thus, anonymity is not preserved when an +aborted transaction coincides with revoked denomination, which should be rare +in practice. + +Unlike most other operations, the +payback protocol does not incur any transaction fees. The primary use of the +protocol is to limit the financial loss in cases where an audit reveals that +the exchange's private keys were compromised, and to automatically pay back +balances held in a customers' wallet if an exchange ever goes out of business. + +To limit the damage of a compromise, the exchange can employ a hardware +security module that contains the denomination secret keys, and is +pre-programmed with a limit on the number of signatures it can produce. This +might be mandated by certain auditors, who will also audit the operational +security of an exchange as part of the certification process. + +\subsubsection{Compromise of Signing Keys} +When a signing key is compromised, the attacker can pretend to be a +merchant and forge deposit confirmations. To forge a deposit +confirmation, the attacker also needs to get a customer to sign a +contract from the adversary (which should include the adversary's +banking details) with a valid coin. The attack here is that the +customer is allowed to have spent the coin already. Thus, a deposit of +the resulting deposit permission would result in a rejection from the +exchange due to double spending. By forging the deposit confirmation +using the compromised signing key, the attacker can thus claim in +court that they properly deposited the coin first and demand payment +from the exchange. + +We note that indeed an evil exchange could simply fail to record +deposit permissions in its database and then fail to execute them. +Thus, given a merchant presenting a deposit confirmation, we need +a way to establish whether this is a case of an evil exchange that +should be compelled to pay, or a case of a compromised signing key +and where payouts (and thus financial damage to the exchange) +can legitimately be limited. + +To limit the financial damage of a compromised signing key, merchants +must be required to work with auditors to perform a +\emph{probabilistic deposit auditing} of the exchange. Here, the goal +is to help detect the compromise of a signing key by making sure that +the exchange does indeed properly record deposit confirmations. +However, double-checking with the auditor if every deposit +confirmation is recorded in the exchange's database would be too +expensive and time-consuming. Fortunately, a probabilistic method +where merchants only send a small fraction of their deposit +confirmations to the auditor suffices. Then, if the auditor sees a +deposit confirmation that is not recorded in the exchange's database +(possibly after performing the next synchronization with the +exchange's database), it signals the exchange that the signing key has +been compromised. + +At this point, the signing key must be revoked and the exchange will +be required to investigate the security of its systems and address the +issue before resuming normal operations. +% +%If the exchange had separate short-term signing keys just for signing deposit +%confirmations, it could also employ hardware security modules with a counter, +%and check if the value of the counter matches matches the deposit confirmations +%recorded in the database. + +Still, at this point various actors (including the attacker) could still +step forward with deposit confirmations signed by the revoked key and +claim that the exchange owes them for their deposits. Simply revoking +a signing key cannot lift the exchange's payment obligations, and the +attacker could have signed an unlimited number of such deposit confirmations +with the compromised key. However, in contrast to honest merchants, the +attacker will not have participated {\em proportionally} in the auditor's +probabilistic deposit auditing scheme for those deposit confirmations: +in that case, the key compromise would have been detected and the key +revoked. + +The exchange must still pay all deposit permissions it signed for +coins that were not double-spent. However, for all coins where +multiple merchants claim that they have a deposit confirmation, the +exchange will pay the merchants proportionate to the fraction of the +coins that they reported to the auditor as part of probabilistic +deposit auditing. For example, if 1\% of deposits must be reported to +the auditor according to the protocol, a merchant might be paid at +most say 100+X times the number of reported deposits where $X>0$ +serves to ensure proper payout despite the probabilistic nature of the +reporting. As a result, honest merchants have an {\em incentive} to +correctly report the deposit confirmations to the auditor. + +Given this scheme, the attacker can only report a small number of +deposit confirmations to the auditor before triggering the signing key +compromise detection. Suppose again that 1\% of deposit confirmations +are reported by honest merchants, then the attacker can only expect to +submit 100 deposit permissions created by the compromised signing key +before being detected. The attacker's expected financial benefit from +the key compromise would then be the value of $(100+X) \cdot 100$ +deposit permissions. + +Thus, the financial benefit to the attacker can be limited by +probabilistic deposit auditing, and honest merchants have proper +incentives to participate in the process. + +\subsubsection{Compromise of the Database} +If an adversary would be able to modify the exchange, this would be detected +rather quickly by the auditor, provided that the database has appropriate +integrity mechanisms. An attacker could also prevent database updates to block +the recording of spend operations, and then double spend. This is effectively +equivalent to the compromise of signing keys, and can be detected with the same +strategies. + +\subsubsection{Compromise of the Master Key} +If the master key was compromised, an attacker could de-anonymize customers by +announcing different sets of denomination keys to each of them. If the +exchange was audited, this would be detected quickly, as these denominations +will not be signed by auditors. + +\subsection{Cryptographic Proof} + +We use the term ``proof'' in many places as the protocol provides cryptographic +proofs of which parties behave correctly or incorrectly. However, +as~\cite{fc2014murdoch} point out, in practice financial systems need to +provide evidence that holds up in courts. Taler's implementation is designed +to export evidence and upholds the core principles described +in~\cite{fc2014murdoch}. In particular, in providing the cryptographic proofs +as evidence none of the participants have to disclose their core secrets. + +\subsection{Perfect Crime Scenarios}\label{sec:design:blackmailing} +GNU Taler can be slightly modified to thwart blackmailing or kidnapping +attempts by criminals who intend to use the anonymity properties of the system +and demand to be paid ransom in anonymous e-cash. + +Our modification incurs a slight penalty on the latency for customers during normal use and +requires slightly more data to be stored in the exchange's database, and thus +should only be used in deployments where resistance against perfect crime +scenarios is necessary. A payment system for a school cafeteria likely does +not need these extra measures. + +The following modifications are made: +\begin{enumerate} + \item Coins can now only be used in either a transaction or in a refresh operations, not a mix of both. + Effectively, the customer's wallet then needs to use the refresh protocol to prepare exact change + before a transaction is made, and that transaction is made with exact change. + + This change is necessary to preserve anonymity in face of the second modification, but increases + storage requirements and latency. + \item The payback protocol is changed so that a coin obtained + via refreshing must be recovered differently when revoked: to recover a revoked coin + obtained via refreshing, the customer needs to show the transcripts for the + chain of all refresh operations and the initial withdrawal operation + (including the blinding factor). Refreshes on revoked coins are not + allowed anymore. +\end{enumerate} + +After an attacker has been paid ransom, the exchange simply revokes all currently offered denominations +and registers a new set of denomination with the auditor. +Reserves used to pay the attacker are marked as blocked in the exchange's +database. Normal users can use the payback protocol to obtain back the money +they've previously had in revoked denominations. The attacker can try to +recover funds via the (now modified) payback protocol, but this attempt will +not be successful, as the initial reserve is blocked. The criminal could also +try to spend the e-cash anonymously before it is revoked, but this is likely +difficult for large amounts, and furthermore due to income transparency all +transactions made between the payment of the ransom and the revocation can be +traced back to merchants that might be complicit in laundering the ransom +payment. + +Honest customers can always use the payback protocol to transfer the funds to +the initial reserve. Due to modification (1), unlinkability of transactions is +not affected, as only coins that were purely used for refreshing can now be +correlated. + +We believe that our approach is more practical than the approaches based on +tracing, since in a scheme with tracing, the attacker can always ask for a +plain blind signature. With our approach, the attacker will always lose funds +that they cannot immediately spend. Unfortunately our approach is limited to a +kidnapping scenario, and not applicable in those blackmail scenarios where the +attacker can do damage after they find out that their funds have been erased. + +\section{Related Work} +% FIXME: Stuff to review/include: +% Blindly Signed Contracts: Anonymous On-Blockchain and Off-Blockchain Bitcoin Transactions +% zcash taxability stuff + +\subsection{Anonymous E-Cash}\label{sec:related-work:e-cash} + +Chaum's seminal paper \cite{chaum1983blind} introduced blind signatures and +demonstrated how to use them for online e-cash. Later work +\cite{chaum1989efficient,chaum1990untraceable} introduced offline spending, where additional +information is encoded into coins in such a way that double spending reveals +the culprit's identity. + +Okamoto \cite{okamoto1995efficient} introduced the first efficient offline +e-cash scheme with divisibility, a feature that allows a single coin to be +spent in parts. With Okamoto's protocol, different spending operations that +used parts of the same coin were linkable. An unlinkable version of +divisible e-cash was first presented by Canard~\cite{canard2007divisible}. + +Camenisch's compact e-cash \cite{camenisch2005compact} allows wallets with $2^\ell$ coins to be stored +and withdrawn with storage, computation and computational costs in $\mathcal{O}(\ell)$. +Each coin in the wallet, however, still needs to be spent separately. + +The protocol that can currently be considered the state-of-the-art for efficient +offline e-cash was introduced by Pointcheval et al. \cite{pointcheval2017cut}. +It allows constant-time withdrawal of a divisible coin, and constant-time +spending of a continuous ``chunk'' of a coin. While the pre-determined number +of divisions of a coin is independent from the storage, bandwidth and +computational complexity of the wallet, the exchange needs to check for +double-spending at the finest granularity. Thus, highly divisible coins incur +large storage and computational costs for the exchange. + +An e-cash system with multiple denominations with different financial values +was proposed by Canard and Gouget~\cite{canard2006handy} in the context of a divisible +coupon system. + +One of the earliest mentions of an explicit change protocol can be found in +\cite{brickell1995trustee}. Ian Goldberg's HINDE system is another design that +allows the merchant to provide change, but the mechanism could be abused to +hide income from taxation.\footnote{Description based on personal +communication. HINDE was never published, but supposedly publicly discussed at +Financial Crypto '98.} Another online e-cash protocol with change was proposed +by Tracz \cite{tracz2001fair}. The use of an anonymous change protocol (called +a ``refund'' in their context) for fractional payments has also been suggested +for a public transit fees payment system \cite{rupp2013p4r}. Change protocols +for offline e-cash were recently proposed \cite{batten2018offline}. To the +best of our knowledge, no change protocol with protections against tax evasion +has been proposed so far, and all change protocols suggested so far can be +(ab)used to make a payment into another wallet. + +Transferable e-cash allows the transfer of funds between customers without +using the exchange as in intermediary \cite{fuchsbauer2009transferable}. + +Chaum also proposed wallets with observers \cite{chaum1992wallet} as a +mechanism against double spending. The observer is a tamper-proof hardware +security module that prevents double-spending, while at the same time being +unable to de-anonymize the user. + +Various works propose mechanisms to selectively de-anonymize customers or +transactions that are suspected of criminal activities +\cite{stadler1995fair,davida1997anonymity}. Another approach suspends +customers that were involved in a particular transaction, while keeping the +customer anonymous \cite{au2011electronic}. + +One of the first formal treatments of the provable security of e-cash was given +in \cite{damgaard2007proof}. The first complete security definition for blind +signatures was given by Pointcheval \cite{pointcheval1996provably} and applied +to RSA signatures later \cite{pointcheval2000security}. While the security +proof of RSA signatures requires the random oracle model, many blind signature +schemes are provably secure in the standard model +\cite{izabachene2013divisible,pointcheval2017cut}. While most literature +provides only ``human-verified'' security arguments, the security of a simple +e-cash scheme has been successfully modeled in +ProVerif~\cite{dreier2015formal}, albeit only in the symbolic model. + +\subsubsection{Implementations} +DigiCash was the first commercial implementation of Chaum's e-cash. It +ultimately failed to be widely adopted, and the company filed for bankruptcy in +1998. Some details of the implementation are available +\cite{schoenmakers1997security}. In addition to Chaum's infamously paranoid +management style \cite{next1999digicash}, reasons for DigiCash's failure could +have been the following: + +\begin{itemize} + \item DigiCash did not allow account-less operations. To use DigiCash, + customers had to sign up with a bank that natively supports DigiCash. + \item DigiCash did not support change or partial spending, negating a lot of + the convenience and security of e-cash by requiring frequent withdrawals + from the customer's bank account. + \item The technology used by DigiCash was protected by patents, + which stifled innovation from competitors. + \item Chaum's published design does not clearly limit the financial damage an + exchange might suffer from the disclosure of its private online signing key. +\end{itemize} + +To our knowledge, the only publicly available effort to implement anonymous +e-cash is Opencoin~\cite{dent2008extensions}. However, Opencoin is neither +actively developed nor used, and it is not clear to what degree the +implementation is even complete. Only a partial description of the Opencoin +protocol is available to date. + + +\subsubsection{Representing Denominations}\label{design:related-different-denominations} + +For GNU Taler, we chose to represent denominations of different values by a +different public key for every denomination, together with a mapping from +public key to financial value and auxiliary information about fees and +expiration dates. This approach has the advantage that coins of higher denominations +can be signed by denominations with a larger key size. + +Schoenmakers~\cite{schoenmakers1997security} proposes an optimized +implementation of multiple denomination that specifically works with RSA keys, +which encodes the denomination in the public exponent $e$ of the RSA public +key, while the modulus $N$ stays the same for all denominations. An advantage +of this scheme is the reduced size of the public keys for a set of +denominations. As this encoding is specific to RSA, it would be difficult for +future versions of this protocol to switch to different blind signature +primitives. More importantly, factoring $N$ would lead to a compromise of all +denominations instead of just one. + +Partially blind signatures can be used to represent multiple denominations +by blindly signing the coin's serial number and including the financial value of the coin +in the common information seen by both the signer and signee \cite{abe2000provably}. + +The compact e-cash scheme of Märtens~\cite{maertens2015practical} allows +constant-time withdrawal of wallets with an arbitrary number of coins, as long +as the number of coins is smaller than some system parameter. This approach +effectively dispenses with the need to have different denominations. + + +\subsubsection{Comparison} + +\newcommand\YES{\ding{51}} % {\checkmark} +\newcommand\NO{\ding{55}} + +\newcommand*\rot{\multicolumn{1}{R{45}{1em}}}% no optional argument here, please! +%\newcommand*\rot{}% no optional argument here, please! + + +\newcolumntype{H}{>{\setbox0=\hbox\bgroup}c<{\egroup}@{}} + +\newcolumntype{R}[2]{% + >{\adjustbox{angle=#1,lap=\width-(#2)}\bgroup}% + l% + <{\egroup}% +} + +{\footnotesize +\begin{tabular}{r|ccccccccccc} +& +\rot{Year} & +\rot{Implementation} & +% +\rot{Offline spending} & +\rot{Safe aborts/backups} & +\rot{Key expiration} & +% +\rot{Income transparency} & +% +% \rot{Withdrawal cost} & \rot{Deposit cost} & +\rot{No trusted setup} & +\rot{Storage for wallet} & +\rot{Storage for exchange} & +% +\rot{Change/Divisibility} & +\rot{Receipts \& Refunds} +\\ \hline +Chaum \cite{chaum1983blind} +& 1983 & P +& \NO & \NO & ? +& ? +% & $\log n$ & $\log n$ +& \YES & $\log n$ & $\log n$ +& \NO & \NO +\\ +DigiCash \cite{schoenmakers1997security} +& 1990 & P +& \NO & \YES & \YES +& \NO +& \YES & $\log n$ & $\log n$ +& \NO & \NO +\\ +Offline Chaum \cite{chaum1990untraceable} +& 1990 & ? +& \YES & \NO & ? +& ? +& \YES & $\log n$ & $\log n$ +& \NO & \NO +\\ +Tracz \cite{tracz2001fair} % HINDE +& 2001 & E +& \NO & \YES & ? +& \NO +& \YES & $\log n$ & $\log n$ +& Onl. & \NO +\\ +Compact \cite{camenisch2005compact} +& 2005 & \NO +& \YES & \NO & ? +& ? +& \YES & $\log n$ & $n$ % We're guessing trustless anonymity because not trusted setup +& Off. & \NO +% \\ +% Martens \cite{maertens2015} +% & 2015 & \NO +% & \NO & \NO & %? +% & \NO & S & \NO +% % & $\log n$ & $\log n$ +% & \YES & \NO & W % We're guessing trustless anonymity because not trusted setup +% & OFF & \NO +\\ +Divisible \cite{pointcheval2017cut} +& 2017 & \NO +& \YES & \NO & ? +& ? +& \NO & $1$ & $n$ +& Off. & \NO +\\ +GNU Taler +& 2017 & FS +& \NO & \YES & \YES +& \YES +% & $\log n$ & $\log n$ +& \YES & $\log n$ & $\log n$ +& Onl. & \YES +\\ \hline +\end{tabular} +} + + +\begin{itemize} + \item \textbf{Implementation.} + Is there an implementation? Is it proprietary (P), experimental (E), or free software (FS). + \item \textbf{Offline Spending} + Can spending happen offline with delayed detection of double spenders, or + is double spending detected immediately during spending? + \item \textbf{Safe abort/backup.} + Is anonymity preserved in the presence of interrupted operations + or restoration from backups? Inherently conflicts with offline double + spending detection in all approaches that we are aware of. + We specify ``\YES'' also for schemes that do not explicitly treat aborts/backup, + but would allow a safe implementation when aborts/backups happen. + \item \textbf{Key expiration.} + We specify ``?'' for schemes that do not explicitly discuss key expiration, + but do not fundamentally conflict with the concept. + \item \textbf{Income transparency.} + We specify ``\YES'' if income transparency is supported, ``\NO'' if some feature of + the scheme conflicts with income transparency and ``?'' if it might be possible + to add income transparency. + \item \textbf{No trusted setup.} + In a trusted setup, some parameters and cryptographic keys are generated + by a trusted third party. A compromise of the trusted setup phase can mean loss + of anonymity. + \item \textbf{Storage for wallet/exchange.} + The expected storage for coins adding up to arbitrary value $n$ is specified, + with some reasonable upper bound for $n$. + \item \textbf{Change/Divisibility.} + Can customers pay without possessing exact change? If so, is it handled + by giving change online (Onl.) or by divisible coins that support offline + operation (Off.)? + \item \textbf{Receipts \& Refunds.} + The customer either can prove that they payed for + a contract, or they can get their (unlinkable) money back. + Also merchants can issue refunds for completed transactions. + These operations must not introduce linkability or otherwise + compromise the customer's anonymity. +\end{itemize} + + +\subsection{Blockchains} +The term ``blockchain'' refers to a wide variety of protocols and systems concerned with +maintaining a ledger---typically involving financial transactions---in a +distributed and decentralized manner.\footnote{Even though there is a centralization tendency +from various sources in practice \cite{walch2019deconstructing}.} + +The first and most prominent system that would be categorized as a +``blockchain'' today\footnote{The paper that introduces Bitcoin does not +mention the term ``blockchain''} is Bitcoin \cite{nakamoto2008bitcoin}, +published by an individual or group under the alias ``Satoshi Nakamoto''. The +document timestamping service described in \cite{haber1990time} could be seen +as an even earlier blockchain that predates Bitcoin by about 13 +years and is still in use today. + +As the name implies, blockchains are made up of a chain of blocks, each block +containing updates to the ledger and the hash code of its predecessor block. The +chain terminates in a ``genesis block'' that determines the initial state of +the ledger. + +Some of the most important decisions for the design of blockchains are the following: +\begin{itemize} + \item The \emph{consensus mechanism}, which determines how the participants + agree on the current state of the ledger. + + In the simplest possible blockchain, a trusted authority would validate + transactions and publish new blocks as the head of the chain. In order to + increase fault tolerance, multiple trusted authorities can use Byzantine + consensus to agree on transactions. With classical Byzantine consensus + protocols, this makes the system robust with a malicious minority of up to + $1/3$ of nodes. While fast and appropriate for some applications, + classical Byzantine consensus only works with a known set of participants + and does not scale well to many nodes. + + Bitcoin instead uses Proof-of-Work (PoW) consensus, where the head of the + chain that determines the current ledger state is chosen as the block that + provably took the most ``work'' to construct, including the accumulated + work of ancestor blocks. The work consists of finding a hash preimage $n + \Vert c$, where $c$ are the contents of the block and $n$ is a nonce, such + that the hash $H(n \Vert c)$ ends with a certain number of zeroes (as + determined by the difficulty derived from previous blocks). Under the + random oracle, the only way to find such a nonce is by trial-and-error. + This nonce proves to a verifier that the creator of the block spent + computational resources to construct it, and the correctness is easily + verified by computing $H(n \Vert c)$. The creator of a block is rewarded + with a mining reward and transaction fees for transactions within the + block. + + PoW consensus is not final: an adversary with enough computational power + can create an alternate chain branching off an earlier block. Once this + alternative, longer chain is published, the state represented by the + earlier branch is discarded. This creates a potential for financial fraud, + where an earlier transaction is reversed by publishing an alternate history + that does not contain it. While it was originally believed that PoW + consensus process is resistant against attackers that have less than a + $51\%$ majority of computational power, closer analysis has shown that a + $21\%$ majority sufficies \cite{eyal2018majority}. + + A major advantage of PoW consensus is that the participants need not be + known beforehand, and that Sybil attacks are impossible since consensus + decisions are only dependent on the available computational power, and not + on the number of participants. + + In practice, PoW consensus is rather slow: Bitcoin can currently support + 3-7 transactions per second on a global scale. Some efforts have been made + to improve Bitcoin's efficiency \cite{eyal2016bitcoin,vukolic2015quest}, + but overall PoW consensus needs to balance speed against security. + + Proof-of-Stake (PoS) is a different type of consensus protocol for + blockchains, which intends to securely reach consensus without depleting + scarce resources such as energy for computation + \cite{bentov2016cryptocurrencies,kwon2014tendermint}. Blocks are created + by randomly selected validators, which obtain a reward for serving as a + validator. To avoid Sybil attacks and create economic incentives for good + behavior, the probability to get selected as a validator is proportional to + one's wealth on the respective blockchain. Realizing PoS has some + practical challenges with respect to economic incentives: As blocks do not + take work to create, validators can potentially benefit from creating + forks, instead of validating on just one chain. + + Algorand \cite{gilad2017algorand} avoids some of the problems with PoW + consensus by combining some of the ideas of PoW with classical Byzantine + consensus protocols. Their proposed system does not have any incentives + for validators. + + Avalance \cite{rocket2018snowflake} has been proposed as a scalable + Byzantine Consensus algorithm for use with blockchains. It is based on a + gossip protocol and is only shown to work in the synchronous model. + + \item Membership and visibility. Blockchains such as Bitcoin or Ethereum with + public membership and public visibility are called \emph{permissionless blockchains}. + Opposed to that, \emph{permissioned} blockchains have been proposed for usage in + banking, health and asset tracking applications \cite{androulaki2018hyperledger}. + + \item Monetary policy and wealth accumulation. + Blockchains that are used as cryptocurrencies come with their own monetary + policy. In the case of Bitcoin, the currency supply is limited, and due to + difficulty increase in mining the currency is deflationary. Other + cryptocurrencies such as duniter\footnote{See + \url{https://duniter.org/}.} have been proposed with built-in rules for + inflation, and a basic income mechanism for participants. + + \item Expressivity of transactions. Transactions in Bitcoin are small programs + in a stack-based programming language that are guaranteed to terminate. + Ethereum \cite{wood2014ethereum} takes this idea further and allows smart contracts with + Turing-complete computation and access to external oracles. + + \item Governance. Blockchain governance \cite{reijers2016governance,levy2017book} is a + topic that received relatively little attention so far. As blockchains + interact with existing legal and social systems across national borders, + different sources of ``truth'' must be reconciled. + + Furthermore, consensus is not just internal to the operation of + blockchains, but also external in the development of the technology. + Currently small groups of developers create the rules for the operation of + blockchains, and likewise have the power to change them. There is + currently very little research on social and technological processes to + find a ``meta-consensus'' on the rules that govern such systems, and how + these rules can be adapted and changed in a consensus process. + + \item Anonymity and Zero-Knowledge Proofs. Bitcoin transactions are only + pseudoymous, the full transaction history is publicly available and leads + to reduced anonymity in practice \cite{reid2013analysis}. Tumblers + \cite{bonneau2014mixcoin,heilman2017tumblebit} are an approach to increase + the anonymity in Bitcoin-style cryptocurrencies by creating additional + transactions to cover up the real owner and sources of funds. While newer tumblers + such as TumbleBit \cite{heilman2017tumblebit} provide rather strong security guarantees, + mixing incurs transaction costs. + + Some cryptocurrencies have direct support for anonymous transactions + \cite{sun2017ringct}. ZeroCash \cite{bensasson2014zerocash} uses + zero-knowledge proofs to hide the sender, receiver and amount of a + transaction. While ZeroCash currently relies on a trusted setup for + unforgeability of its currency, more recent proposals dispense with that + requirement \cite{ben2018scalable,wahby2018doubly}. As the anonymity + provided by ZeroCash facilitates tax evasion and use in other crimes, an + additional, optional layer for privacy-preserving policy for taxation, + spending limits and identity escrow has been proposed + \cite{garman2016accountable}. +\end{itemize} + +Practical guidance on what kind of blockchain is appropriate for an +application, and if a blockchain is required in the first place, can be found +in \cite{wust2017you}. + + +\subsection{Approaches to Micropayments} +Micropayments refer to payments of very small value. Microtransactions would +not be feasible in traditional payment systems due to high transaction costs, +which might even exceed that value that is to be transferred. + +\subsubsection{Peppercoin} + +Peppercoin~\cite{rivest2004peppercoin} is a microdonation protocol. +The main idea of the protocol is to reduce transaction costs by +minimizing the number of transactions that are processed directly by +the exchange. Instead of always paying, the customer ``gambles'' with the +merchant for each microdonation. Only if the merchant wins, the +microdonation is upgraded to a macropayment to be deposited at the +exchange. Peppercoin does not provide customer-anonymity. The proposed +statistical method by which exchanges detect fraudulent cooperation between +customers and merchants at the expense of the exchange not only creates +legal risks for the exchange, but would also require that the exchange learns +about microdonations where the merchant did not get upgraded to a +macropayment. It is therefore unclear how Peppercoin would actually +reduce the computational burden on the exchange. + +\subsubsection{Tick Payments} +% FIXME: also works off-line +Tick payments were proposed by Pedersen \cite{pedersen1996electronic} as a +general technique to amortize the cost for small, recurring payments to the +same payee. The payer first makes an up-front deposit as one larger payment +that involves the payment processor. To make a micropayment, the payer sends a +message to the payee that authorizes the payee to claim a fraction of this +deposit. Each further micropayment simply increases the fraction of the +deposit that can be claimed, and only requires communication between payer and +payee. The payee only needs to show the last message received from the payer +to the payment processor in order to receive the accumulated amounts received +through tick payments. + +\subsubsection{Payment Channels and Lightning Network} +The Lightning Network \cite{poon2016bitcoin} is a proposed payment system that +is meant to run on top of Bitcoin and enable faster, cheaper +(micro-)transactions. It is based on establishing \emph{payment channels} +between Bitcoin nodes. A payment channel is essentially a tick payment where +the deposit and settlement happens on a blockchain. The goal of the +Lightning network is to route a payment between two arbitrary nodes by finding a +path that connects the two routes through payment channels. The protocol is +designed in such a way that a node on the path between the initial sender and +final receiver can only receive a payment on a payment channel if it correctly +forwards it to the next node. + +Experimental deployments of the Lightning network recently suffered heavily +from denial-of-service attacks. % FIXME: citation needed! + +BOLT \cite{green2016bolt} is an anonymous payment channel for ZeroCash, and is +intended to be used as a building block for a second-layer payment protocol +like the Lightning Network. + +\subsubsection{Side-chains} +% FIXME: what about polkadot? +Side-chains are an alternative approach to improve the scalability of +blockchains, intended to be useful in conjunction with arbitrary smart +contracts. The approach currently developed by the Ethereum project is +described in the Plasma white paper \cite{poon2017plasma}. Side-chains are +separate blockchains, possibly with different rules and even consensus +protocols than the main chain. Side-chains operate in parallel to the main +Ethereum chain, and regularly publish ``pointers'' to the current head of the +sidechain on the main chain. Funds can be moved from the main chain to the +side-chain, and subsequently be moved off the side-chain by performing an +``exit'', during which the main chain verifies claims to funds on the +side-chain according to the side-chain's rules. + +At the time of writing, Plasma is not yet implemented. Potential problems with +Plasma include the high costs of exits, lack of access to data needed to verify +exit claims, and associated potential for denial-of-service attacks. + + +%\subsection{Other Payment Systems} + +%\subsubsection{Credit Card Payments} + +\subsection{Walled Garden Payment Systems} + +Walled garden payment systems offer ease of use by processing payments using a +trusted payment service provider. Here, the customer authenticates to the +trusted service, and instructs the payment provider to execute a transaction on +their behalf. In these payment systems, the provider basically acts like a +bank with accounts carrying balances for the various users. In contrast to +traditional banking systems, both customers and merchants are forced to have an +account with the same provider. Each user must take the effort to establish +his identity with a service provider to create an account. Merchants and +customers obtain the best interoperability in return for their account creation +efforts if they start with the biggest providers. As a result, there are a few +dominating walled garden providers, with AliPay, ApplePay, GooglePay, +SamsungPay and PayPal being the current oligopoly. +%In this paper, we +%will use PayPal as a representative example for our discussion of these payment +%systems. + +As with card payment systems, these oligopolies are politically +dangerous~\cite{crinkey2011rundle}, and the lack of competition +can result in excessive profit taking that may require political +solutions~\cite{guardian2015cap} to the resulting market + failure. The use of non-standard proprietary interfaces to +the payment processing service of these providers serves to reinforce +the customer lock-in. + +%TODO: discuss popularity/abundance of digital wallets in other countries (India!) +%and different requirements (connectivity) + +%\subsubsection{Ripple} + +\subsection{Web Integration} + +Finally, we will discuss software solutions to web payments. We +consider other types of payments, including general payments and in +particular hardware solutions as out of scope for this thesis. + +\subsubsection{Web Payments API} +The Web Payments API\footnote{See \url{https://www.w3.org/TR/payment-request/}} +is a JavaScript API offered by browsers, and currently still under development. +It allows merchant to offer a uniform checkout experience across different +payment systems. Unlike GNU Taler, the Web Payments API is only concerned with +aspects of the checkout process, such as display of a payment request, +selection of a shipping address and selection of a payment method. + +Currently only basic-card is supported across popular browsers. + +The Payment Handler API\footnote{See +\url{https://www.w3.org/TR/payment-handler/}} supports the registration of +user-defined payment method handlers. Unfortunately the only way to add +payment method handlers is via an HTTPS URL. This leaks all information to the +payment service provider and precludes the implementation of privacy-preserving +payment system handlers. + +In order to integrate Taler as a payment method, browsers would need to either +offer Taler as a native, built-in payment method or allow an extension to +register web payment handlers. + + +The Web Payments Working Group discontinued work on a HTTP-based API for +machine-to-machine payments.\footnote{See +\url{https://www.w3.org/TR/webpayments-http-api/}.} + +\subsubsection{Payment Pointers} +Payment pointers are a proposed standard syntax for accounts that are able to +receive payments. Unlike \texttt{payto://} URIs ( discussed in +Section~\ref{implementation:wire-method-identifiers}), payment pointers do not +follow the generic URI syntax and only specify a \emph{pointer} to the +receiver's bank account in form of a HTTPS URI. Payment pointers do not +specify any mechanism for the payment, but instead direct the user's browser to +a website to carry out the payment. + +\subsubsection{3-D Secure} +3-D Secure is a complex and widely deployed protocol that is intended to add an +additional security layer on top of credit and debit card transactions. + +The 3-D Secure protocol requires the use of inline frames on the HTML page of +the merchant for extended verification/authentication of the user. This makes +it hard or sometimes -- such as when using a mobile browser -- even impossible +to tell whether the inline frame is legitimate or an attempt to steal +information from the user. + +Traditionally, merchants bear most of the financial risk, and a key +``feature'' of the 3DS process compared to traditional card payments +is to shift dispute {\em liability} to the issuer of the card---who +may then try to shift it to the customer \cite[\S2.4]{3DSsucks}. +% +% online vs offline vs swipe vs chip vs NFC ??? +% extended verification +% +Even in cases where the issuer or the merchant remain legally first in +line for liabilities, there are still risks customers incur from the +card dispute procedures, such as neither them nor the payment +processor noticing fraudulent transactions, or them noticing +fraudulent transactions past the {\em deadline} until which their bank +would reimburse them. The customer also typically only has a +merchant-generated comment and the amount paid in their credit card +statement as a proof for the transaction. Thus, the use of credit +cards online does not generate any cryptographically {\em verifiable} +electronic receipts for the customer, which theoretically enables +malicious merchants to later change the terms of the contract. + +Beyond these primary issues, customers face secondary risks of +identity theft from the personal details exposed by the authentication +procedures. In this case, even if the financial damages are ultimately +covered by the bank, the customer always has to deal with the procedure +of {\em notifying} the bank in the first place. As a result, +customers must remain wary about using their cards, which limits their +online shopping~\cite[p. 50]{ibi2014}. + +\subsubsection{Other Proprietary Payment APIs} +The Electronic Payment Standard URI scheme \texttt{epspayment:} is a +proprietary/unregistered URI scheme used by predominantly Austrian banks and +merchants to trigger payments from within websites on mobile devices. +Merchants can register an invoice with a central server. The user's banking +app is associated with the \texttt{epspayment} URI scheme and will open to +settle the invoice. It lies conceptually between \texttt{payto://} and +\texttt{taler:pay} (see Section~\ref{sec:loose-browser-integration}). A +technical problem of \texttt{epspayment} is that when a user has multiple bank +accounts at different banks that support \texttt{epspayment}, some platforms +decide non-deterministically and without asking the user which application to +launch. Thus, a user with two banking applications on their phone can often not +chose which bank account is used for the payment. If \texttt{payto} were +widely supported, the problem of registering/choosing bank accounts for payment +methods could be centrally addressed by the browser / operating system. + +PayPal is a very popular, completely proprietary payment system provider. Its offer-based +API is similar in the level of abstraction to Taler's reference merchant backend API. + +LaterPay is a proprietary payment system for online content as well as +donations. It offers similar functionality to session-bound payments in Taler. +LaterPay does not provide any anonymity. + + +% FIXME: mention these +% Stripe +% paydirekt +% mention this somewhere: https://www.focus.de/finanzen/banken/paydirekt-so-reagieren-kunden-auf-die-sparkassen-plaene_id_7511393.html +% but not in this section. good argument for anonymity 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{<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 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! diff --git a/doc/system/taler/security.tex b/doc/system/taler/security.tex new file mode 100644 index 000000000..99c8e0520 --- /dev/null +++ b/doc/system/taler/security.tex @@ -0,0 +1,1729 @@ +\chapter{Security of Income-Transparent Anonymous E-Cash}\label{chapter:security} + +\def\Z{\mathbb{Z}} + +\def\mathperiod{.} +\def\mathcomma{,} + +\newcommand*\ST[5]% +{\left#1\,#4\vphantom{#5} \;\right#2 \left. #5 \vphantom{#4}\,\right#3} + +% uniform random selection from set +\newcommand{\randsel}[0]{\ensuremath{\xleftarrow{\text{\$}}}} + +\newcommand{\Exp}[1]{\ensuremath{E\left[#1\right]}} + +% oracles +\newcommand{\ora}[1]{\ensuremath{\mathcal{O}\mathsf{#1}}} +% oracle set +\newcommand{\oraSet}[1]{\ensuremath{\mathcal{O}\textsc{#1}}} +% algorithm +\newcommand{\algo}[1]{\ensuremath{\mathsf{#1}}} +% party +\newcommand{\prt}[1]{\ensuremath{\mathcal{#1}}} +% long-form variable +\let\V\relax % clashes with siunitx volt +\newcommand{\V}[1]{\ensuremath{\mathsf{#1}}} + +% probability with square brackets of the right size +\newcommand{\Prb}[1]{\ensuremath{\Pr\left [#1 \right ]}} + +\newcommand{\mycomment}[1]{~\\ {\small \textcolor{blue}{({#1})}}} + +\theoremstyle{definition} +\newtheorem{definition}{Definition}[section] +\theoremstyle{corollary} +\newtheorem{corollary}{Corollary}[section] + + +%%%%%%%%% +% TODOS +%%%%%%%% +% +% * our theorems don't really mention the security parameters "in the output", +% shouldn't we be able to talk about the bounds of the reduction? + +We so far discussed Taler's protocols and security properties only informally. +In this chapter, we model a slightly simplified version of the system that we +have implemented (see Chapter~\ref{chapter:implementation}), make our desired +security properties more precise, and prove that our protocol instantiation +satisfies those properties. + +\section{Introduction to Provable Security} +Provable security +\cite{goldwasser1982probabilistic,pointcheval2005provable,shoup2004sequences,coron2000exact} is a common +approach for constructing formal arguments that support the security of a cryptographic +protocol with respect to specific security properties and underlying +assumptions on cryptographic primitives. + +The adversary we consider is computationally bounded, i.e., the run time is +typically restricted to be polynomial in the security parameters (such as key +length) of the protocol. + +Contrary to what the name might suggest, a protocol that is ``provably secure'' +is not necessarily secure in practice +\cite{koblitz2007another,damgaard2007proof}. Instead, provable security +results are typically based on reductions of the form \emph{``if there is an +effective adversary~$\mathcal{A}$ against my protocol $P$, then I can use +$\mathcal{A}$ to construct an effective adversary~$\mathcal{A}'$ against +$Q$''} where $Q$ is a protocol or primitive that is assumed to be secure or a +computational problem that is assumed to be hard. The practical value of a +security proof depends on various factors: +\begin{itemize} + \item How well-studied is $Q$? Some branches of cryptography, for example, + some pairing-based constructions, rely on rather complex and exotic + underlying problems that are assumed to be hard (but might not be) + \cite{koblitz2010brave}. + \item How tight is the reduction of $Q$ to $P$? A security proof may only + show that if $P$ can be solved in time $T$, the underlying problem $Q$ can + be solved (using the hypothetical $\mathcal{A}$) in time, e.g., $f(T) = T^2$. + In practice, this might mean that for $P$ to be secure, it needs to be deployed + with a much larger key size or security parameter than $Q$ to be secure. + \item What other assumptions are used in the reduction? A common and useful but + somewhat controversial + assumption is the Random Oracle Model (ROM) \cite{bellare1993random}, where + the usage of hash functions in a protocol is replaced with queries to a + black box (called the Random Oracle), which is effectively a trusted third + party that returns a truly random value for each input. Subsequent queries + to the Random Oracle with the same value return the same result. While + many consider ROM a practical assumption + \cite{koblitz2015random,bellare1993random}, it has been shown that there + exist carefully constructed protocols that are secure under the ROM, but + are insecure with any concrete hash function \cite{canetti2004random}. It + is an open question whether this result carries over to practical + protocols, or just certain classes of artificially constructed protocols of + theoretical interest. +\end{itemize} +Furthermore, a provably secure protocol does not always lend itself easily to a secure +implementation, since side channels and fault injection attacks \cite{hsueh1997fault,lomne2011side} are +usually not modeled. Finally, the security properties stated might +not be sufficient or complete for the application. + +For our purposes, we focus on game-based provable security +\cite{bellare2006code,pointcheval2005provable,shoup2004sequences,guo2018introduction} +as opposed to simulation-based provable security \cite{goldwasser1989knowledge,lindell2017simulate}, +which is another approach to provable security typically used for +zero-knowledge proofs and secure multiparty computation protocols. + +\subsection{Algorithms, Oracles and Games} +In order to analyze the security of a protocol, the protocol and its desired +security properties against an adversary with specific capabilities must first +be modeled formally. This part is independent of a concrete instantiation of +the protocol; the protocol is only described on a syntactic level. + +The possible operations of a protocol (i.e., the protocol syntax) are abstractly +defined as the signatures of \emph{algorithms}. Later, the protocol will be +instantiated by providing a concrete implementation (formally a program for a +probabilistic Turing machine) of each algorithm. A typical public key signature +scheme, for example, might consist of the following algorithms: +\begin{itemize} + \item $\algo{KeyGen}(1^\lambda) \mapsto (\V{sk}, \V{pk})$, a probabilistic algorithm + which on input $1^\lambda$ generates a fresh key pair consisting of secret key $\V{sk}$ of length $\lambda$ and + and the corresponding public key $\V{pk}$. Note that $1^\lambda$ is the unary representation of $\lambda$.\footnote{% + This formality ensures that the size of the input of the Turing machine program implementing the algorithm will + be as least as big as the security parameter. Otherwise the run-time complexity cannot be directly expressed + in relation to the size of the input tape.} + \item $\algo{Sign}(\V{sk}, m) \mapsto \sigma$, an algorithm + that signs the bit string $m$ with secret key $\V{sk}$ to output the signature $\sigma$. + \item $\algo{Verify}(\V{pk}, \sigma, m) \mapsto b$, an algorithm + that determines whether $\sigma$ is a valid signature on $m$ made with the secret key corresponding to the + public key $\V{pk}$. It outputs the flag $b \in \{0, 1\}$ to indicate whether the signature + was valid (return value $1$) or invalid (return value $0$). +\end{itemize} +The abstract syntax could be instantiated with various concrete signature protocols. + +In addition to the computational power given to the adversary, the capabilities +of the adversary are defined via oracles. The oracles can be thought of as the +API\footnote{In the modern sense of application programming interface (API), +where some system exposes a service with well-defined semantics.} that is given +to the adversary and allows the adversary to interact with the environment it +is running in. Unlike the algorithms, which the adversary has free access to, +the access to oracles is often restricted, and oracles can keep state that is +not accessible directly to the adversary. Oracles typically allow the +adversary to access information that it normally would not have direct access +to, or to trigger operations in the environment running the protocol. + +Formally, oracles are an extension to the Turing machine that runs the +adversary, which allow the adversary to submit queries to interact with the +environment that is running the protocol. + + +For a signature scheme, the adversary could be given access to an \ora{Sign} +oracle, which the adversary uses to make the system produce signatures, with +secret keys that the adversary does not have direct access to. Different +definitions of \ora{Sign} lead to different capabilities of the adversary and +thus to different security properties later on: +\begin{itemize} + \item If the signing oracle $\ora{Sign}(m)$ is defined to take a message $m$ and return + a signature $\sigma$ on that message, the adversary gains the power to do chosen message attacks. + \item If $\ora{Sign}(\cdot)$ was defined to return a pair $(\sigma, m)$ of a signature $\sigma$ + on a random message $m$, the power of the adversary would be reduced to a known message attack. +\end{itemize} + +While oracles are used to describe the possible interactions with a system, it +is more convenient to describe complex, multi-round interactions involving +multiple parties as a special form of an algorithm, called an \emph{interactive +protocol}, that takes the identifiers of communicating parties and their +(private) inputs as a parameter, and orchestrates the interaction between them. +The adversary will then have an oracle to start an instance of that particular +interactive protocol and (if desired by the security property being modeled) +the ability to drop, modify or inject messages in the interaction. The +typically more cumbersome alternative would be to introduce one algorithm and +oracle for every individual interaction step. + +Security properties are defined via \emph{games}, which are experiments that +challenge the adversary to act in a way that would break the desired security +property. Games usually consist multiple phases, starting with the setup phase +where the challenger generates the parameters (such as encryption keys) for the +game. In the subsequent query/response phase, the adversary is given some of +the parameters (typically including public keys but excluding secrets) from the +setup phase, and runs with access to oracles. The challenger\footnote{ The +challenger is conceptually the party or environment that runs the +game/experiment.} answers oracle queries during that phase. After the +adversary's program terminates, the challenger invokes the adversary again with +a challenge. The adversary must now compute a final response to the +challenger, sometimes with access to oracles. Depending on the answer, the +challenger decides if the adversary wins the game or not, i.e., the game returns +$0$ if the adversary loses and $1$ if the adversary wins. + +A game for the existential unforgeability of signatures could be formulated like this: + +\bigskip +\noindent $\mathit{Exp}_{\prt{A}}^{EUF}(1^\lambda)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $(\V{sk}, \V{pk}) \leftarrow \algo{KeyGen}(1^\lambda)$ + \item $(\sigma, m) \leftarrow \prt{A}^{\ora{Sign(\cdot)}}(\V{pk})$ + + (Run the adversary with input $\V{pk}$ and access to the $\ora{Sign}$ oracle.) + \item If the adversary has called $\ora{Sign}(\cdot)$ with $m$ as argument, + return $0$. + \item Return $\algo{Verify}(\V{pk}, \sigma, m)$. +\end{enumerate} +Here the adversary is run once, with access to the signing oracle. Depending +on which definition of $\ora{Sign}$ is chosen, the game models existential +unforgeability under chosen message attack (EUF-CMA) or existential +unforgeability under known message attack (EUF-KMA) + +The following modification to the game would model selective unforgeability +(SUF-CMA / SUF-KMA): + +\bigskip +\noindent $\mathit{Exp}_{\prt{A}}^{SUF}(1^\lambda)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $m \leftarrow \prt{A}()$ + \item $(\V{sk}, \V{pk}) \leftarrow \algo{KeyGen}(1^\lambda)$ + \item $\sigma \leftarrow \prt{A}^{\ora{Sign(\cdot)}}(\V{pk}, m)$ + \item If the adversary has called $\ora{Sign}(\cdot)$ with $m$ as argument, + return $0$. + \item Return $\algo{Verify}(\V{pk}, \sigma, m)$. +\end{enumerate} +Here the adversary has to choose a message to forge a signature for before +knowing the message verification key. + +After having defined the game, we can now define a security property based on +the probability of the adversary winning the game: we say that a signature +scheme is secure against existential unforgeability attacks if for every +adversary~\prt{A} (i.e., a polynomial-time probabilistic Turing machine +program), the success probability +\begin{equation*} + \Prb{\mathit{Exp}_{\prt{A}}^{EUF}(1^\lambda) = 1 } +\end{equation*} +of \prt{A} in the EUF game is \emph{negligible} (i.e., grows less fast with +$\lambda$ than the inverse of any polynomial in $\lambda$). + +Note that the EUF and SUF games are related in the following way: an adversary +against the SUF game can be easily transformed into an adversary against the +EUF game, while the converse does not necessarily hold. + +Often security properties are defined in terms of the \emph{advantage} of the +adversary. The advantage is a measure of how likely the adversary is to win +against the real cryptographic protocol, compared to a perfectly secure version +of the protocol. For example, let $\mathit{Exp}_{\prt{A}}^{BIT}()$ be a game +where the adversary has to guess the next bit in the output of a pseudo-random number +generator (PRNG). The idealized functionality would be a real random number generator, +where the adversary's chance of a correct guess is $1/2$. Thus, the adversary's advantage is +\begin{equation*} + \left|\Prb{\mathit{Exp}_{\prt{A}}^{BIT}()} - 1/2\right|. +\end{equation*} +Note that the definition of advantage depends on the game. The above +definition, for example, would not work if the adversary had a way to +``voluntarily'' lose the game by querying an oracle in a forbidden way + + +\subsection{Assumptions, Reductions and Game Hopping} +The goal of a security proof is to transform an attacker against +the protocol under consideration into an attacker against the security +of an underlying assumption. Typical examples for common assumptions might be: +\begin{itemize} + \item the difficulty of the decisional/computational Diffie--Hellman problem (nicely described by~\cite{boneh1998decision}) + \item existential unforgeability under chosen message attack (EUF-CMA) of a signature scheme \cite{goldwasser1988digital} + \item indistinguishability against chosen-plaintext attacks (IND-CPA) of a symmetric + encryption algorithm \cite{bellare1998relations} +\end{itemize} + +To construct a reduction from an adversary \prt{A} against $P$ to an adversary +against $Q$, it is necessary to specify a program $R$ that both interacts as an +adversary with the challenger for $Q$, but at the same time acts as a +challenger for the adversary against $P$. Most importantly, $R$ can chose how +to respond to oracle queries from the adversary, as long as $R$ faithfully +simulates a challenger for $P$. The reduction must be efficient, i.e., $R$ must +still be a polynomial-time algorithm. + +A well-known example for a non-trivial reduction proof is the security proof of +FDH-RSA signatures \cite{coron2000exact}. +% FIXME: I think there's better reference, pointcheval maybe? + +In practice, reduction proofs are often complex and hard to verify. +Game hopping has become a popular technique to manage the complexity of +security proofs. The idea behind game hopping proofs is to make a sequence of +small modifications starting from initial game, until you arrive at a game +where the success probability for the adversary becomes obvious, for example, +because the winning state for the adversary becomes unreachable in the code +that defines the final game, or because all values the adversary can observe to +make a decision are drawn from a truly random and uniform distribution. Each +hop modifies the game in a way such that the success probability of game +$\mathbb{G}_n$ and game $\mathbb{G}_{n+1}$ is negligibly close. + +Useful techniques for hops are, for example: +\begin{itemize} + \item Bridging hops, where the game is syntactically changed but remains + semantically equivalent, i.e., $\Prb{\mathbb{G}_n = 1} = \Prb{\mathbb{G}_n = 1}$. + \item Indistinguishability hops, where some distribution is changed in a way that + an adversary that could distinguish between two adjacent games could be turned + into an adversary that distinguishes the two distributions. If the success probability + to distinguish between those two distributions is $\epsilon$, then + $\left|\Prb{\mathbb{G}_n = 1} - \Prb{\mathbb{G}_n = 1}\right| \le \epsilon$ + \item Hops based on small failure events. Here adjacent games proceed + identically, until in one of the games a detectable failure event $F$ (such + as an adversary visibly forging a signature) occurs. Both games most proceed + the same if $F$ does not occur. Then it is easy to show \cite{shoup2004sequences} + that $\left|\Prb{\mathbb{G}_n = 1} - \Prb{\mathbb{G}_n = 1}\right| \le \Prb{F}$ +\end{itemize} + +A tutorial introduction to game hopping is given by Shoup \cite{shoup2004sequences}, while a more formal +treatment with a focus on ``games as code'' can be found in \cite{bellare2006code}. A +version of the FDH-RSA security proof based on game hopping was generated with an +automated theorem prover by Blanchet and Pointcheval \cite{blanchet2006automated}. + +% restore-from-backup + +% TODO: +% - note about double spending vs overspending + +\subsection{Notation} +We prefix public and secret keys with $\V{pk}$ and $\V{sk}$, and write $x +\randsel S$ to randomly select an element $x$ from the set $S$ with uniform +probability. + +\section{Model and Syntax for Taler} + +We consider a payment system with a single, static exchange and multiple, +dynamically created customers and merchants. The subset of the full Taler +protocol that we model includes withdrawing digital coins, spending them with +merchants and subsequently depositing them at the exchange, as well as +obtaining unlinkable change for partially spent coins with an online +``refresh'' protocol. + +The exchange offers digital coins in multiple denominations, and every +denomination has an associated financial value; this mapping is not chosen by +the adversary but is a system parameter. We mostly ignore the denomination +values here, including their impact on anonymity, in keeping with existing +literature \cite{camenisch2007endorsed,pointcheval2017cut}. For anonymity, we +believe this amounts to assuming that all customers have similar financial +behavior. We note logarithmic storage, computation and bandwidth demands +denominations distributed by powers of a fixed constant, like two. + +We do not model fees taken by the exchange. Reserves\footnote{% + ``Reserve'' is Taler's terminology for funds submitted to the exchange that + can be converted to digital coins. +} +are also omitted. +Instead of maintaining a reserve balance, withdrawals of different +denominations are tracked, effectively assuming every customer has unlimited funds. + +Coins can be partially spent by specifying a fraction $0 < f \le 1$ of the +total value associated with the coin's denomination. Unlinkable change below +the smallest denomination cannot be given. In +practice the unspendable, residual value should be seen as an additional fee +charged by the exchange. + +Spending multiple coins is modeled non-atomically: to spend (fractions +of) multiple coins, they must be spent one-by-one. The individual +spend/deposit operations are correlated by a unique identifier for the +transaction. In practice, this identifier is the hash $\V{transactionId} = +H(\V{contractTerms})$ of the contract terms\footnote{The contract terms +are a digital representation of an individual offer for a certain product or service the merchant sells +for a certain price.}. Contract terms include a nonce to make them +unique, that merchant and customer agreed upon. Note that this transaction +identifier and the correlation between multiple spend operations for one +payment need not be disclosed to the exchange (it might, however, be necessary +to reveal during a detailed tax audit of the merchant): When spending the $i$-th coin +for the transaction with the identifier $\V{transactionId}$, messages to the +exchange would only contain $H(i \Vert \V{transactionId})$. This is preferable +for merchants that might not want to disclose to the exchange the individual +prices of products they sell to customers, but only the total transaction +volume over time. For simplicity, we do not include this extra feature in our +model. + +Our system model tracks the total amount ($\equiv$ financial value) of coins +withdrawn by each customer. +Customers are identified by their public key $\V{pkCustomer}$. Every +customer's wallet keeps track of the following data: +\begin{itemize} + \item $\V{wallet}[\V{pkCustomer}]$ contains sets of the customer's coin records, + which individually consist of the coin key pair, denomination and exchange's signature. + \item $\V{acceptedContracts}[\V{pkCustomer}]$ contains the sets of + transaction identifiers accepted by the customer during spending + operations, together with coins spent for it and their contributions $0 < f + \le 1$. + \item $\V{withdrawIds}[\V{pkCustomer}]$ contains the withdraw identifiers of + all withdraw operations that were created for this customer. + \item $\V{refreshIds}[\V{pkCustomer}]$ contains the refresh identifiers of + all refresh operations that were created for this customer. +\end{itemize} + + +The exchange in our model keeps track of the following data: +\begin{itemize} + \item $\V{withdrawn}[\V{pkCustomer}]$ contains the total amount withdrawn by + each customer, i.e., the sum of the financial value of the denominations for + all coins that were withdrawn by $\V{pkCustomer}$. + \item The overspending database of the exchange is modeled by + $\V{deposited}[\V{pkCoin}]$ and $\V{refreshed}[\V{pkCoin}]$, which record + deposit and refresh operations respectively on each coin. Note that since + partial deposits and multiple refreshes to smaller denominations are + possible, one deposit and multiple refresh operations can be recorded for a + single coin. +\end{itemize} + +We say that a coin is \emph{fresh} if it appears in neither the $\V{deposited}$ +or $\V{refreshed}$ lists nor in $\V{acceptedContracts}$. We say that a coin is +being $\V{overspent}$ if recording an operation in $\V{deposited}$ or +$\V{refreshed}$ would cause the total spent value from both lists to exceed +the value of the coin's denomination. +Note that the adversary does not have direct read or write access to these +values; instead the adversary needs to use the oracles (defined later) to +interact with the system. + +We parameterize our system with two security parameters: The general security +parameter $\lambda$, and the refresh security parameter $\kappa$. While +$\lambda$ determines the length of keys and thus the security level, using a +larger $\kappa$ will only decrease the success chance of malicious merchants +conspiring with customers to obtain unreported (and thus untaxable) income. + +\subsection{Algorithms}\label{sec:security-taler-syntax} + +The Taler e-cash scheme is modeled by the following probabilistic\footnote{Our +Taler instantiations are not necessarily probabilistic (except, e.g., key +generation), but we do not want to prohibit this for other instantiations} +polynomial-time algorithms and interactive protocols. The notation $P(X_1,\dots,X_n)$ +stands for a party $P \in \{\prt{E}, \prt{C}, \prt{M}\}$ (Exchange, Customer +and Merchant respectively) in an interactive protocol, with $X_1,\dots,X_n$ +being the (possibly private) inputs contributed by the party to the protocol. +Interactive protocols can access the state maintained by party $P$. + +While the adversary can freely execute the interactive protocols by creating +their own parties, the adversary is not given direct access to the private data +of parties maintained by the challenger in the security games we define later. + +\begin{itemize} + \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D}) \mapsto (\V{sksE}, \V{pksE})$: + Algorithm executed to generate keys for the exchange, with general security + parameter $\lambda$ and refresh security parameter $\kappa$, both given as + unary numbers. The denomination specification $\mathfrak{D} = d_1,\dots,d_n$ is a + finite sequence of positive rational numbers that defines the financial + value of each generated denomination key pair. We henceforth use $\mathfrak{D}$ to + refer to some appropriate denomination specification, but our analysis is + independent of a particular choice of $\mathfrak{D}$. + + The algorithm generates the exchange's master signing key pair + $(\V{skESig}, \V{pkESig})$ and denomination secret and public keys + $(\V{skD}_1, \dots, \V{skD}_n), (\V{pkD}_1, \dots, \V{pkD}_n)$. We write + $D(\V{pkD}_i)$, where $D : \{\V{pkD}_i\} \rightarrow \mathfrak{D}$ to look + up the financial value of denomination $\V{pkD_i}$. + + We collectively refer to the exchange's secrets by $\V{sksE}$ and to the exchange's + public keys together with $\mathfrak{D}$ by $\V{pksE}$. + + \item $\algo{CustomerKeygen}(1^\lambda,1^\kappa) \mapsto (\V{skCustomer}, \V{pkCustomer})$: + Key generation algorithm for customers with security parameters $\lambda$ + and $\kappa$. + + \item $\algo{MerchantKeygen}(1^\lambda,1^\kappa) \mapsto (\V{skMerchant}, + \V{pkMerchant})$: Key generation algorithm for merchants. Typically the + same as \algo{CustomerKeygen}. + + \item $\algo{WithdrawRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), + \prt{C}(\V{skCustomer}, \V{pksE}, \V{pkD})) \mapsto (\mathcal{T}_{WR}, + \V{wid})$: Interactive protocol between the exchange and a customer that + initiates withdrawing a single coin of a particular denomination. + + The customer obtains a withdraw identifier $\V{wid}$ from the protocol + execution and stores it in $\V{withdrawIds}[\V{pkCustomer}]$. + + The \algo{WithdrawRequest} protocol only initiates a withdrawal. The coin + is only obtained and stored in the customer's wallet by executing the + \algo{WithdrawPickup} protocol on the withdraw identifier \V{wid}. + + The customer and exchange persistently store additional state (if required + by the instantiation) such that the customer can use + $\algo{WithdrawPickup}$ to complete withdrawal or to complete a previously + interrupted or unfinished withdrawal. + + Returns a protocol transcript $\mathcal{T}_{WR}$ of all messages exchanged + between the exchange and customer, as well as the withdraw identifier + \V{wid}. + + \item $\algo{WithdrawPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), + \prt{C}(\V{skCustomer}, \V{pksE}, \V{wid})) \mapsto (\mathcal{T}_{WP}, + \V{coin})$: Interactive protocol between the exchange and a customer to + obtain the coin from a withdraw operation started with + $\algo{WithdrawRequest}$, identified by the withdraw identifier $\V{wid}$. + + The first time $\algo{WithdrawPickup}$ is run with a particular withdraw + identifier $\V{wid}$, the exchange increments + $\V{withdrawn}[\V{pkCustomer}]$ by $D(\V{pkD})$, where $\V{pkD}$ is the + denomination requested in the corresponding $\algo{WithdrawRequest}$ + execution. How exactly $\V{pkD}$ is restored depends on the particular instantiation. + + The resulting coin + \[ \V{coin} = (\V{skCoin}, \V{pkCoin}, \V{pkD}, \V{coinCert}), \] + consisting of secret key $\V{skCoin}$, public key + $\V{pkCoin}$, denomination public key $\V{pkD}$ and certificate $\V{coinCert}$ from the exchange, is stored + in the customers wallet $\V{wallet}[\V{pkCustomer}]$. + + Executing the $\algo{WithdrawPickup}$ protocol multiple times with the same + customer and the same withdraw identifier does not result in any change of + the customer's withdraw balance $\V{withdrawn}[\V{pkCustomer}]$, + and results in (re-)adding the same coin to the customer's wallet. + + Returns a protocol transcript $\mathcal{T}_{WP}$ of all messages exchanged + between the exchange and customer. + + \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant}) \mapsto \V{depositPermission}$: + Algorithm to produce and sign a deposit permission \V{depositPermission} + for a coin under a particular transaction identifier. The fraction $0 < f \le 1$ determines the + fraction of the coin's initial value that will be spent. + + The contents of the deposit permission depend on the instantiation, but it + must be possible to derive the public coin identifier $\V{pkCoin}$ from + them. + + \item $\algo{Deposit}(\prt{E}(\V{sksE}, \V{pkMerchant}), \prt{M}(\V{skMerchant}, \V{pksE}, \V{depositPermission})) \mapsto \mathcal{T}_D$: + Interactive protocol between the exchange and a merchant. + + From the deposit permission we obtain the $\V{pkCoin}$ of the coin to be + deposited. If $\V{pkCoin}$ is being overspent, the protocol is aborted with + an error message to the merchant. + + On success, we add $\V{depositPermission}$ to $\V{deposited}[\V{pkCoin}]$. + + Returns a protocol transcript $\mathcal{T}_D$ of all messages exchanged + between the exchange and merchant. + + \item $\algo{RefreshRequest}(\prt{E}(\V{sksE}), \prt{C}(\V{pkCustomer}, \V{pksE}, \V{coin}_0, \V{pkD}_u)) + \rightarrow (\mathcal{T}_{RR}, \V{rid})$ + Interactive protocol between exchange and customer that initiates a refresh + of $\V{coin}_0$. Together with $\algo{RefreshPickup}$, it allows the + customer to convert $D(\V{pkD}_u)$ of the remaining value on coin \[ + \V{coin}_0 = (\V{skCoin}_0, \V{pkCoin}_0, \V{pkD}_0, \V{coinCert}_0) \] + into a new, unlinkable coin $\V{coin}_u$ of denomination $\V{pkD}_u$. + + Multiple refreshes on the same coin are allowed, but each run subtracts the + respective financial value of $\V{coin}_u$ from the remaining value of + $\V{coin}_0$. + + The customer only records the refresh operation identifier $\V{rid}$ in + $\V{refreshIds}[\V{pkCustomer}]$, but does not yet obtain the new coin. To + obtain the new coin, \algo{RefreshPickup} must be used. + + Returns the protocol transcript $\mathcal{T}_{RR}$ and a refresh identifier $\V{rid}$. + + \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), + \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid})) \rightarrow (\mathcal{T}_{RP}, \V{coin}_u)$: + Interactive protocol between exchange and customer to obtain the new coin + for a refresh operation previously started with \algo{RefreshRequest}, + identified by the refresh identifier $\V{rid}$. + + The exchange learns the target denomination $\V{pkD}_u$ and signed + source coin $(\V{pkCoin}_0, \V{pkD}_0, \V{coinCert}_0)$. If the source + coin is invalid, the exchange aborts the protocol. + + The first time \algo{RefreshPickup} is run for a particular refresh + identifier, the exchange records a refresh operation of value + $D(\V{pkD}_u)$ in $\V{refreshed}[\V{pkCoin}_0]$. If $\V{pkCoin}_0$ is + being overspent, the refresh operation is not recorded in + $\V{refreshed}[\V{pkCoin}_0]$, the exchange sends the customer the protocol + transcript of the previous deposits and refreshes and aborts the protocol. + + If the customer \prt{C} plays honestly in \algo{RefreshRequest} and + \V{RefreshPickup}, the unlinkable coin $\V{coin}_u$ they obtain as change + will be stored in their wallet $\V{wallet}[\V{pkCustomer}]$. If \prt{C} is + caught playing dishonestly, the \algo{RefreshPickup} protocol aborts. + + An honest customer must be able to repeat a \algo{RefreshPickup} with the + same $\V{rid}$ multiple times and (re-)obtain the same coin, even if + previous $\algo{RefreshPickup}$ executions were aborted. + + Returns a protocol transcript $\mathcal{T}_{RP}$. + + \item $\algo{Link}(\prt{E}(\V{sksE}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0)) \rightarrow (\mathcal{T}, (\V{coin}_1, \dots, \V{coin}_n))$: + Interactive protocol between exchange and customer. If $\V{coin}_0$ is a + coin that was refreshed, the customer can recompute all the coins obtained + from previous refreshes on $\V{coin}_0$, with data obtained from the + exchange during the protocol. These coins are added to the customer's + wallet $\V{wallet}[\V{pkCustomer}]$ and returned together with the protocol + transcript. + +\end{itemize} + +\subsection{Oracles} +We now specify how the adversary can interact with the system by defining +oracles. Oracles are queried by the adversary, and upon a query the challenger +will act according to the oracle's specification. Note that the adversary for +the different security games is run with specific oracles, and does not +necessarily have access to all oracles simultaneously. + +We refer to customers in the parameters to an oracle query simply by their +public key. The adversary needs the ability to refer to coins to trigger +operations such as spending and refresh, but to model anonymity we cannot give +the adversary access to the coins' public keys directly. Therefore we allow +the adversary to use the (successful) transcripts of the withdraw, refresh and +link protocols to indirectly refer to coins. We refer to this as a coin handle +$\mathcal{H}$. Since the execution of a link protocol results in a transcript +$\mathcal{T}$ that can contain multiple coins, the adversary needs to select a +particular coin from the transcript via the index $i$ as $\mathcal{H} = +(\mathcal{T}, i)$. The respective oracle tries to find the coin that resulted +from the transcript given by the adversary. If the transcript has not been +seen before in the execution of a link, refresh or withdraw protocol; or the +index for a link transcript is invalid, the oracle returns an error to the +adversary. + +In oracles that trigger the execution of one of the interactive protocols +defined in Section \ref{sec:security-taler-syntax}, we give the adversary the +ability to actively control the communication channels between the exchange, +customers and merchants; i.e., the adversary can effectively record, drop, +modify and inject messages during the execution of the interactive protocol. +Note that this allows the adversary to leave the execution of an interactive +protocol in an unfinished state, where one or more parties are still waiting +for messages. We use $\mathcal{I}$ to refer to a handle to interactive +protocols where the adversary can send and receive messages. + +\begin{itemize} + \item $\ora{AddCustomer}() \mapsto \V{pkCustomer}$: + Generates a key pair $(\V{skCustomer}, \V{pkCustomer})$ using the + \algo{CustomerKeygen} algorithm, and sets + \begin{align*} + \V{withdrawn}[\V{pkCustomer}] &:= 0\\ + \V{acceptedContracts}[\V{pkCustomer}] &:= \{ \}\\ + \V{wallet}[\V{pkCustomer}] &:= \{\} \\ + \V{withdrawIds}[\V{pkCustomer}] &:= \{\} \\ + \V{refreshIds}[\V{pkCustomer}] &:= \{\}. + \end{align*} + Returns the public key of the newly created customer. + + \item $\ora{AddMerchant}() \mapsto \V{pkMerchant}$: + Generate a key pair $(\V{skMerchant}, \V{pkMerchant})$ using the + \algo{MerchantKeygen} algorithm. + + Returns the public key of the newly created merchant. + + \item $\ora{SendMessage}(\mathcal{I}, P_1, P_2, m) \mapsto ()$: + Send message $m$ on the channel from party $P_1$ to party $P_2$ in the + execution of interactive protocol $\mathcal{I}$. The oracle does not have + a return value. + + \item $\ora{ReceiveMessage}(\mathcal{I}, P_1, P_2) \mapsto m$: + Read message $m$ in the channel from party $P_1$ to party $P_2$ in the execution + of interactive protocol $\mathcal{I}$. If no message is queued in the channel, + return $m = \bot$. + + \item $\ora{WithdrawRequest}(\V{pkCustomer}, \V{pkD}) \mapsto \mathcal{I}$: + Triggers the execution of the \algo{WithdrawRequest} protocol. the + adversary full control of the communication channels between customer and + exchange. + + \item $\ora{WithdrawPickup}(\V{pkCustomer}, \V{pkD}, \mathcal{T}) \mapsto \mathcal{I}$: + Triggers the execution of the \algo{WithdrawPickup} protocol, additionally giving + the adversary full control of the communication channels between customer and exchange. + + The customer and withdraw identifier $\V{wid}$ are obtained from the \algo{WithdrawRequest} transcript $\mathcal{T}$. + + \item $\ora{RefreshRequest}(\mathcal{H}, \V{pkD}) \mapsto \mathcal{I}$: Triggers the execution of the + \algo{RefreshRequest} protocol with the coin identified by coin handle + $\mathcal{H}$, additionally giving the adversary full control over the communication channels + between customer and exchange. + + \item $\ora{RefreshPickup}(\mathcal{T}) \mapsto \mathcal{I}$: + Triggers the execution of the \algo{RefreshPickup} protocol, where the customer and refresh identifier $\V{rid}$ + are obtained from the $\algo{RefreshRequest}$ protocol transcript $\mathcal{T}$. + + Additionally gives the adversary full control over the communication channels + between customer and exchange. + + \item $\ora{Link}(\mathcal{H}) \mapsto \mathcal{I}$: Triggers the execution of the + \algo{Link} protocol for the coin referenced by handle $\mathcal{H}$, + additionally giving the adversary full control over the communication channels + between customer and exchange. + + \item $\ora{Spend}(\V{transactionId}, \V{pkCustomer}, \mathcal{H}, \V{pkMerchant}) \mapsto \V{depositPermission}$: + Makes a customer sign a deposit permission over a coin identified by handle + $\mathcal{H}$. Returns the deposit permission on success, or $\bot$ if $\mathcal{H}$ + is not a coin handle that identifies a coin. + + Note that $\ora{Spend}$ can be used to generate deposit permissions that, + when deposited, would result in an error due to overspending + + Adds $(\V{transactionId}, \V{depositPermission})$ to $\V{acceptedContracts}[\V{pkCustomer}]$. + + \item $\ora{Share}(\mathcal{H}, \V{pkCustomer}) \mapsto ()$: + Shares a coin (identified by handle $\mathcal{H}$) with the customer + identified by $\V{pkCustomer}$, i.e., puts the coin identified by $\mathcal{H}$ + into $\V{wallet}[\V{pkCustomer}]$. Intended to be used by the adversary in attempts to + violate income transparency. Does not have a return value. + + Note that this trivially violates anonymity (by sharing with a corrupted customer), thus the usage must + be restricted in some games. + + % the share oracle is the reason why we don't need a second withdraw oracle + + \item $\ora{CorruptCustomer}(\V{pkCustomer})\mapsto + \newline{}\qquad (\V{skCustomer}, \V{wallet}[\V{pkCustomer}],\V{acceptedContracts}[\V{pkCustomer}], + \newline{}\qquad \phantom{(}\V{refreshIds}[\V{pkCustomer}], \V{withdrawIds}[\V{pkCustomer}])$: + + Used by the adversary to corrupt a customer, giving the adversary access to + the customer's secret key, wallet, withdraw/refresh identifiers and accepted contracts. + + Permanently marks the customer as corrupted. There is nothing ``special'' + about corrupted customers, other than that the adversary has used + \ora{CorruptCustomer} on them in the past. The adversary cannot modify + corrupted customer's wallets directly, and must use the oracle again to + obtain an updated view on the corrupted customer's private data. + + \item $\ora{Deposit}(\V{depositPermission}) \mapsto \mathcal{I}$: + Triggers the execution of the \algo{Deposit} protocol, additionally giving + the adversary full control over the communication channels between merchant and exchange. + + Returns an error if the deposit permission is addressed to a merchant that was not registered + with $\ora{AddMerchant}$. + + This oracle does not give the adversary new information, but is used to + model the situation where there might be multiple conflicting deposit + permissions generated via $\algo{Spend}$, but only a limited number can be + deposited. +\end{itemize} + +We write \oraSet{Taler} for the set of all the oracles we just defined, +and $\oraSet{NoShare} := \oraSet{Taler} - \ora{Share}$ for all oracles except +the share oracle. + +The exchange does not need to be corrupted with an oracle. A corrupted exchange +is modeled by giving the adversary the appropriate oracles and the exchange +secret key from the exchange key generation. + +If the adversary determines the exchange's secret key during the setup, +invoking \ora{WithdrawRequest}, \ora{WithdrawPickup}, \ora{RefreshRequest}, +\ora{RefreshPickup} or \ora{Link} can be seen as the adversary playing the +exchange. Since the adversary is an active man-in-the-middle in these oracles, +it can drop messages to the simulated exchange and make up its own response. +If the adversary calls these oracles with a corrupted customer, the adversary +plays as the customer. + +%\begin{mdframed} +%The difference between algorithms and interactive protocols +%is that the ``pure'' algorithms only deal with data, while the interactive protocols +%take ``handles'' to parties that are communicating in the protocol. The adversary can +%always execute algorithms that don't depend on handles to communication partners. +%However the adversary can't run the interactive protocols directly, instead it must +%rely on the interaction oracles for it. Different interaction oracles might allow the +%adversary to play different roles in the same interactive protocol. +% +%While most algorithms in Taler are not probabilistic, we still say that they are, since +%somebody else might come up with an instantiation of Taler that uses probabilistic algorithms, +%and then the games should still apply. +% +% +%While we do have a \algo{Deposit} protocol that's used in some of the games, having a deposit oracle is not necessary +%since it does not give the adversary any additional power. +%\end{mdframed} + +\section{Games} + +We now define four security games (anonymity, conservation, unforgeability and +income transparency) that are later used to define the security properties for +Taler. Similar to \cite{bellare2006code} we assume that the game and adversary +terminate in finite time, and thus random choices made by the challenger and +adversary can be taken from a finite sample space. + +All games except income transpacency return $1$ to indicate that the adversary +has won and $0$ to indicate that the adversary has lost. The income +transparency game returns $0$ if the adversary has lost, and a positive +``laundering ratio'' if the adversary won. + +\subsection{Anonymity} +Intuitively, an adversary~$\prt{A}$ (controlling the exchange and merchants) wins the +anonymity game if they have a non-negligible advantage in correlating spending operations +with the withdrawal or refresh operations that created a coin used in the +spending operation. + +Let $b$ be the bit that will determine the mapping between customers and spend +operations, which the adversary must guess. + +We define a helper procedure +\begin{equation*} + \algo{Refresh}(\prt{E}(\V{sksE}), \prt{C}(\V{pkCustomer}, \V{pksE}, \V{coin}_0)) \mapsto \mathfrak{R} +\end{equation*} +that refreshes the whole remaining amount on $\V{coin}_0$ with repeated application of $\algo{RefreshRequest}$ +and $\algo{RefreshPickup}$ using the smallest possible set of target denominations, and returns all protocol transcripts +in $\mathfrak{R}$. + +\begin{mdframed} +\small +\noindent $\mathit{Exp}_{\prt{A}}^{anon}(1^\lambda, 1^\kappa, b)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $(\V{sksE}, \V{pksE}, \V{skM}, \V{pkM}) \leftarrow {\prt{A}}()$ + \item $(\V{pkCustomer}_0, \V{pkCustomer}_1, \V{transactionId}_0, \V{transactionId}_1, f) \leftarrow {\prt{A}}^{\oraSet{NoShare}}()$ + \item Select distinct fresh coins + \begin{align*} + \V{coin}_0 &\in \V{wallet}[\V{pkCustomer}_0]\\ + \V{coin}_1 &\in \V{wallet}[\V{pkCustomer}_1] + \end{align*} + Return $0$ if either $\V{pkCustomer}_0$ or $\V{pkCustomer}_1$ are not registered customers with sufficient fresh coins. + \item For $i \in \{0,1\}$ run + \begin{align*} + &\V{dp_i} \leftarrow \algo{Spend}(\V{transactionId}_i, f, \V{coin}_{i-b}, \V{pkM}) \\ + &\algo{Deposit}(\prt{A}(), \prt{M}(\V{skM}, \V{pksE}, \V{dp}_i)) \\ + &\mathfrak{R}_i \leftarrow \algo{Refresh}(\prt{A}(), \prt{C}(\V{pkCustomer}_i, \V{pksE}, \V{coin}_{i-b})) + \end{align*} + \item $b' \leftarrow {\cal A}^{\oraSet{NoShare}}(\mathfrak{R}_0, \mathfrak{R}_1)$ \\ + \item Return $0$ if $\ora{Spend}$ was used by the adversary on the coin handles + for $\V{coin}_0$ or $\V{coin}_1$ or $\ora{CorruptCustomer}$ was used on $\V{pkCustomer}_0$ or $\V{pkCustomer}_1$. + \item If $b = b'$ return $1$, otherwise return $0$. +\end{enumerate} +\end{mdframed} + +Note that unlike some other anonymity games defined in the literature (such as +\cite{pointcheval2017cut}), our anonymity game always lets both customers spend +in order to avoid having to hide the missing coin in one customer's wallet +from the adversary. + +\subsection{Conservation} +The adversary wins the conservation game if it can bring an honest customer in a +situation where the spendable financial value left in the user's wallet plus +the value spent for transactions known to the customer is less than the value +withdrawn by the same customer through by the exchange. + +In practice, this property is necessary to guarantee that aborted or partially +completed withdrawals, payments or refreshes, as well as other (transient) +misbehavior from the exchange or merchant do not result in the customer losing +money. + +\begin{mdframed} +\small +\noindent $\mathit{Exp}_{\cal A}^{conserv}(1^\lambda, 1^\kappa)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $(\V{sksE}, \V{pksE}) \leftarrow \mathrm{ExchangeKeygen}(1^\lambda, 1^\kappa, M)$ + \item $\V{pkCustomer} \leftarrow {\cal A}^{\oraSet{NoShare}}(\V{pksE})$ + \item Return $0$ if $\V{pkCustomer}$ is a corrupted user. + \item \label{game:conserv:run} Run $\algo{WithdrawPickup}$ for each withdraw identifier $\V{wid}$ + and $\algo{RefreshPickup}$ for each refresh identifier $\V{rid}$ that the user + has recorded in $\V{withdrawIds}$ and $\V{refreshIds}$. Run $\algo{Deposit}$ + for all deposit permissions in $\V{acceptedContracts}$. + \item Let $v_{C}$ be the total financial value left on valid coins in $\V{wallet}[\V{pkCustomer}]$, + i.e., the denominated values minus the spend/refresh operations recorded in the exchange's database. + Let $v_{S}$ be the total financial value of contracts in $\V{acceptedContracts}[\V{pkCustomer}]$. + \item Return $1$ if $\V{withdrawn}[\V{pkCustomer}] > v_{C} + v_{S}$. +\end{enumerate} +\end{mdframed} + + +Hence we ensure that: +\begin{itemize} + \item if a coin was spent, it was spent for a contract that the customer + knows about, i.e., in practice the customer could prove that they ``own'' what they + paid for, + \item if a coin was refreshed, the customer ``owns'' the resulting coins, + even if the operation was aborted, and + \item if the customer withdraws, they can always obtain a coin whenever the + exchange accounted for a withdrawal, even when protocol executions are + intermittently aborted. +\end{itemize} + +Note that we do not give the adversary access to the \ora{Share} oracle, since +that would trivially allow the adversary to win the conservation game. In +practice, conservation only holds for customers that do not share coins with +parties that they do not fully trust. + +\subsection{Unforgeability} + +Intuitively, adversarial customers win if they can obtain more valid coins than +they legitimately withdraw. + +\begin{mdframed} +\small +\noindent $\mathit{Exp}_{\cal A}^{forge}(1^\lambda, 1^\kappa)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ + \item $(C_0, \dots, C_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$ + \item Return $0$ if any $C_i$ is not of the form $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \V{coinCert})$ + or any $\V{coinCert}$ is not a valid signature by $\V{pkD}$ on the respective $\V{pkCoin}$. + \item Return $1$ if the sum of the unspent value of valid coins in $C_0 + \dots, C_\ell$ exceeds the amount withdrawn by corrupted + customers, return $0$ otherwise. +\end{enumerate} +\end{mdframed} + + +\subsection{Income Transparency} + +Intuitively, the adversary wins if coins are in exclusive control of corrupted +customers, but the exchange has no record of withdrawal or spending for them. +This presumes that the adversary cannot delete from non-corrupted customer's +wallets, even though it can use oracles to force protocol interactions of +non-corrupted customers. + +For practical e-cash systems, income transparency disincentivizes the emergence +of ``black markets'' among mutually distrusting customers, where currency +circulates without the transactions being visible. This is in contrast to some +other proposed e-cash systems and cryptocurrencies, where disintermediation is +an explicit goal. The Link protocol introduces the threat of losing exclusive +control of coins (despite having the option to refresh them) that were received +without being visible as income to the exchange. + +\begin{mdframed} +\small +\noindent $\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)$: +\vspace{-0.5\topsep} +\begin{enumerate} + \setlength\itemsep{0em} + \item $(skE, pkE) \leftarrow \mathrm{ExchangeKeygen}()$ + \item $(\V{coin}_1, \dots, \V{coin}_\ell) \leftarrow \mathcal{A}^{\oraSet{All}}(pkExchange)$ + + (The $\V{coin}_i$ must be coins, including secret key and signature by the + denomination, for the adversary to win. However these coins need not be + present in any honest or corrupted customer's wallet.) + \item\label{game:income:spend} Augment the wallets of all non-corrupted customers with their + transitive closure using the \algo{Link} protocol. + Mark all remaining value on coins in wallets of non-corrupted customers as + spent in the exchange's database. + \item Let $L$ denote the sum of unspent value on valid coins in $(\V{coin}_1, \dots\, \V{coin}_\ell)$, + after accounting for the previous update of the exchange's database. + Also let $w'$ be the sum of coins withdrawn by corrupted customers. + Then $p := L - w'$ gives the adversary's untaxed income. + \item Let $w$ be the sum of coins withdrawn by non-corrupted customers, and + $s$ be the value marked as spent by non-corrupted customers, so that + $b := w - s$ gives the coins lost during refresh, that is the losses incurred attempting to hide income. + \item If $b+p \ne 0$, return $\frac{p}{b + p}$, i.e., the laundering ratio for attempting to obtain untaxed income. Otherwise return $0$. +\end{enumerate} +\end{mdframed} + +\section{Security Definitions}\label{sec:security-properties} +We now give security definitions based upon the games defined in the previous +section. Recall that $\lambda$ is the general security parameter, and $\kappa$ is the +security parameter for income transparency. A polynomial-time adversary is implied to +be polynimial in $\lambda+\kappa$. + +\begin{definition}[Anonymity] + We say that an e-cash scheme satisfies \emph{anonymity} if the success + probability $\Prb{b \randsel \{0,1\}: \mathit{Exp}_{\cal A}^{anon}(1^\lambda, + 1^\kappa, b) = 1}$ of the anonymity game is negligibly close to $1/2$ for any + polynomial-time adversary~$\mathcal{A}$. +\end{definition} + +\begin{definition}[Conservation] + We say that an e-cash scheme satisfies \emph{conservation} if + the success probability $\Prb{\mathit{Exp}_{\cal A}^{conserv}(1^\lambda, 1^\kappa) = 1}$ + of the conservation game is negligible for any polynomial-time adversary~$\mathcal{A}$. +\end{definition} + +\begin{definition}[Unforgeability] + We say that an e-cash scheme satisfies \emph{unforgeability} if the success + probability $\Prb{\mathit{Exp}_{\cal A}^{forge}(1^\lambda, 1^\kappa) = 1}$ of + the unforgeability game is negligible for any polynomial-time adversary + $\mathcal{A}$. +\end{definition} + +\begin{definition}[Strong Income Transparency] + We say that an e-cash scheme satisfies \emph{strong income transparency} if + the success probability $\Prb{\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa) \ne 0}$ + for the income transparency game is negligible for any polynomial-time adversary~$\mathcal{A}$. +\end{definition} +The adversary is said to win one execution of the strong income transparency +game if the game's return value is non-zero, i.e., there was at least one +successful attempt to obtain untaxed income. + + +\begin{definition}[Weak Income Transparency] + We say that an e-cash scheme satisfies \emph{weak income transparency} + if, for any polynomial-time adversary~$\mathcal{A}$, + the return value of the income transparency game satisfies + \begin{equation}\label{eq:income-transparency-expectation} + E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {\frac{1}{\kappa}} \mathperiod + \end{equation} + In (\ref{eq:income-transparency-expectation}), the expectation runs over + any probability space used by the adversary and challenger. +\end{definition} + +For some instantiations, e.g., ones based on zero-knowledge proofs, $\kappa$ +might be a security parameter in the traditional sense. However for an e-cash +scheme to be useful in practice, the adversary does not need to have only +negligible success probability to win the income transparency game. It +suffices that the financial losses of the adversary in the game are a +deterrent, after all our purpose of the game is to characterize tax evasion. + +Taler does not fulfill strong income transparency, since for Taler $\kappa$ must +be a small cut-and-choose parameter, as the complexity of our cut-and-choose +protocol grows linearly with $\kappa$. Instead we show that Taler satisfies +weak income transparency, which is a statement about the adversary's financial +loss when winning the game instead of the winning probability. The +return-on-investment (represented by the game's return value) is bounded by +$1/\kappa$. + +We still characterize strong income transparency, since it might be useful +for other instantiations that provide more absolute guarantees. + +\section{Instantiation} +We give an instantiation of our protocol syntax that is generic over +a blind signature scheme, a signature scheme, a combined signature scheme / key +exchange, a collision-resistant hash function and a pseudo-random function family (PRF). + +\subsection{Generic Instantiation}\label{sec:crypto:instantiation} +Let $\textsc{BlindSign}$ be a blind signature scheme with the following syntax, where the party $\mathcal{S}$ +is the signer and $\mathcal{R}$ is the signature requester: +\begin{itemize} + \item $\algo{KeyGen}_{BS}(1^\lambda) \mapsto (\V{sk}, \V{pk})$ is the key generation algorithm + for the signer of the blind signature protocol. + \item $\algo{Blind}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\V{pk}, m)) \mapsto (\overline{m}, r)$ is a possibly interactive protocol + to blind a message $m$ that is to be signed later. The result is a blinded message $\overline{m}$ and + a residual $r$ that allows to unblind a blinded signature on $m$ made by $\V{sk}$. + \item $\algo{Sign}_{BS}(\mathcal{S}(\V{sk}), \mathcal{R}(\overline{m})) \mapsto + \overline{\sigma}$ is an algorithm to sign a blinded message $\overline{m}$. + The result $\overline{\sigma}$ is a blinded signature that must be unblinded + using the $r$ returned from the corresponding blinding operation before + verification. + \item $\algo{UnblindSig}_{BS}(r, m, \overline{\sigma}) \mapsto \sigma$ + is an algorithm to unblind a blinded signature. + \item $\algo{Verify}_{BS}(\V{pk}, m, \sigma) \mapsto b$ is an algorithm to + check the validity of an unblinded blind signature. Returns $1$ if the + signature $\sigma$ was valid for $m$ and $0$ otherwise. +\end{itemize} + +Note that this syntax excludes some blind signature protocols, such as those +with interactive/probabilistic verification or those without a ``blinding +factor'', where the $\algo{Blind}_{BS}$ and $\algo{Sign}_{BS}$ and +$\algo{UnblindSig}_{BS}$ would be merged into one interactive signing protocol. +Such blind signature protocols have already been used to construct e-cash +\cite{camenisch2005compact}. + +We require the following two security properties for $\textsc{BlindSign}$: +\begin{itemize} + \item \emph{blindness}: It should be computationally infeasible for a + malicious signer to decide which of two messages has been signed first + in two executions with an honest user. The corresponding game can be defined as + in Abe and Okamoto \cite{abe2000provably}, with the additional enhancement + that the adversary generates the signing key \cite{schroder2017security}. + \item \emph{unforgeability}: An adversary that requests $k$ signatures with $\algo{Sign}_{BS}$ + is unable to produce $k+1$ valid signatures with non-negligible probability. +\end{itemize} +For more generalized notions of the security of blind signatures see, e.g., +\cite{fischlin2009security,schroder2017security}. + +Let $\textsc{CoinSignKx}$ be combination of a signature scheme and key exchange protocol: + +\begin{itemize} + \item $\algo{KeyGenSec}_{CSK}(1^\lambda) \mapsto \V{sk}$ is a secret key generation algorithm. + \item $\algo{KeyGenPub}_{CSK}(\V{sk}) \mapsto \V{pk}$ produces the corresponding public key. + \item $\algo{Sign}_{CSK}(\V{sk}, m) \mapsto \sigma$ produces a signature $\sigma$ over message $m$. + \item $\algo{Verify}_{CSK}(\V{pk}, m, \sigma) \mapsto b$ is a signature verification algorithm. + Returns $1$ if the signature $\sigma$ is a valid signature on $m$ by $\V{pk}$, and $0$ otherwise. + \item $\algo{Kx}_{CSK}(\V{sk}_1, \V{pk}_2) \mapsto x$ is a key exchange algorithm that computes + the shared secret $x$ from secret key $\V{sk}_1$ and public key $\V{pk}_2$. +\end{itemize} + +We occasionally need these key generation algorithms separately, but +we usually combine them into $\algo{KeyGen}_{CSK}(1^\lambda) \mapsto (\V{sk}, \V{pk})$. + +We require the following security properties to hold for $\textsc{CoinSignKx}$: +\begin{itemize} + \item \emph{unforgeability}: The signature scheme $(\algo{KeyGen}_{CSK}, \algo{Sign}_{CSK}, \algo{Verify}_{CSK})$ + must satisfy existential unforgeability under chosen message attacks (EUF-CMA). + + \item \emph{key exchange completeness}: + Any probabilistic polynomial-time adversary has only negligible chance to find + a degenerate key pair $(\V{sk}_A, \V{pk}_A)$ such that for some + honestly generated key pair + $(\V{sk}_B, \V{pk}_B) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ + the key exchange fails, that is + $\algo{Kex}_{CSK}(\V{sk}_A, \V{pk}_B) \neq \algo{Kex}_{CSK}(\V{sk}_B, \V{pk}_A)$, + while the adversary can still produce a pair $(m, \sigma)$ such that $\algo{Verify}_{BS}(\V{pk}_A, m, \sigma) = 1$. + + \item \emph{key exchange security}: The output of $\algo{Kx}_{CSK}$ must be computationally + indistinguishable from a random shared secret of the same length, for inputs that have been + generated with $\algo{KeyGen}_{CSK}$. +\end{itemize} + +Let $\textsc{Sign} = (\algo{KeyGen}_{S}, \algo{Sign}_{S}, \algo{Verify}_{S})$ be a signature +scheme that satisfies selective unforgeability under chosen message attacks (SUF-CMA). + +Let $\V{PRF}$ be a pseudo-random function family and $H : \{0,1\}^* \rightarrow \{0,1\}^\lambda$ +a collision-resistant hash function. + +Using these primitives, we now instantiate the syntax of our income-transparent e-cash scheme: + +\begin{itemize} + \item $\algo{ExchangeKeygen}(1^{\lambda}, 1^{\kappa}, \mathfrak{D})$: + + Generate the exchange's signing key pair $\V{skESig} \leftarrow \algo{KeyGen}_{S}(1^\lambda)$. + + For each element in the sequence $\mathfrak{D} = d_1,\dots,d_n$, generate + denomination key pair $(\V{skD}_i, \V{pkD}_i) \leftarrow \algo{KeyGen}_{BS}(1^\lambda)$. + \item $\algo{CustomerKeygen}(1^\lambda,1^\kappa)$: + Return key pair $\algo{KeyGen}_S(1^\lambda)$. + \item $\algo{MerchantKeygen}(1^\lambda,1^\kappa)$: + Return key pair $\algo{KeyGen}_S(1^\lambda)$. + + \item $\algo{WithdrawRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{pkD}))$: + + Let $\V{skD}$ be the exchange's denomination secret key corresponding to $\V{pkD}$. + + \begin{enumerate} + \item \prt{C} generates coin key pair $(\V{skCoin}, \V{pkCoin}) \leftarrow \algo{KeyGen}_{CSK}(1^\lambda)$ + \item \prt{C} runs $(\overline{m}, r) \leftarrow \algo{Blind}_{CSK}(\mathcal{E}(\V{skCoin}), \mathcal{C}(m))$ with the exchange + \end{enumerate} + + The withdraw identifier is then + \begin{equation*} + \V{wid} := (\V{skCoin}, \V{pkCoin}, \overline{m}, r) + \end{equation*} + + + \item $\algo{WithdrawPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{wid}))$: + + The customer looks up $\V{skCoin}$, $\V{pkCoin}$, \V{pkD} $\overline{m}$ + and $r$ via the withdraw identifier $\V{wid}$. + + \begin{enumerate} + \item \prt{C} runs $\overline{\sigma} \leftarrow \algo{Sign}_{BS}(\mathcal{E}(\V{skD}), \mathcal{C}(\overline{m}))$ with the exchange + \item \prt{C} unblinds the signature $\sigma \leftarrow \algo{UnblindSig}_{BS}(\overline{\sigma}, r, \overline{m})$ + and stores the coin $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \sigma)$ in their wallet. + \end{enumerate} + + \item $\algo{Spend}(\V{transactionId}, f, \V{coin}, \V{pkMerchant})$: + Let $(\V{skCoin}, \V{pkCoin}, \V{pkD}, \sigma_C) := \V{coin}$. + The deposit permission is computed as + \begin{equation*} + \V{depositPermission} := (\V{pkCoin}, \sigma_D, m), + \end{equation*} + where + \begin{align*} + m &:= (\V{pkCoin}, \V{pkD}, \V{sigma}_C, \V{transactionId}, f, \V{pkMerchant}) \\ + \sigma_D &\leftarrow \algo{Sign}_{CSK}(\V{skCoin}, m). + \end{align*} + + \item $\algo{Deposit}(\prt{E}(\V{sksE}, \V{pkMerchant}), \prt{M}(\V{skMerchant}, \V{pksE}, \V{depositPermission}))$: + The merchant sends \V{depositPermission} to the exchange. + + The exchange checks that the deposit permission is well-formed and sets + \begin{align*} + (\V{pkCoin}, \V{pkD}, \sigma_C, \sigma_D, \V{transactionId}, f, \V{pkMerchant})) &:= \V{depositPermission} + \end{align*} + + The exchange checks the signature on the deposit permission and the validity of the coin with + \begin{align*} + b_1 := \algo{Verify}_{CSK}(\V{pkCoin}, \sigma_D, m) \\ + b_2 := \algo{Verify}_{BS}(\V{pkD}, \sigma_C, \V{pkCoin}) + \end{align*} + and aborts of $b_1 = 0$ or $b_2=0$. + + The exchange aborts if spending $f$ would result in overspending + $\V{pkCoin}$ based on existing deposit/refresh records, and otherwise marks + $\V{pkCoin}$ as spent for $D(\V{pkD})$. + + \item $\algo{RefreshRequest}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0, \V{pkD}_u))$: + + Let $\V{skD}_u$ be the secret key corresponding to $\V{pkD}_u$. + + We write + \[ \algo{Blind}^*_{BS}(\mathcal{S}(\V{sk}, \V{skESig}), \mathcal{R}(R, \V{skR}, \V{pk}, m)) \mapsto (\overline{m}, r, \mathcal{T}_{B*}) \] + for a modified version of $\algo{Blind}_{BS}$ where the signature requester + $\mathcal{R}$ takes all randomness from the sequence + $\left(\V{PRF}(R,\texttt{"blind"}\Vert n)\right)_{n>0}$, the messages from + the exchange are recorded in transcript $\mathcal{T}_{B*}$, all + messages sent by $\mathcal{R}$ are signed with $\V{skR}$ and all messages sent by $\mathcal{S}$ + are signed with $\V{skESig}$. + + Furthermore, we write \[ \algo{KeyGen}^*_{CSK}(R, 1^\lambda) \mapsto + (\V{sk}, \V{pk}) \] for a modified version of the key generation algorithm + that takes randomness from the sequence $\left(\V{PRF}(R,\texttt{"key"}\Vert + n)\right)_{n>0}$. + + For each $i\in \{1,\dots,\kappa \}$, the customer + \begin{enumerate} + \item generates seed $s_i \randsel \{1, \dots, 1^\lambda\}$ + \item generates transfer key pair $(t_i, T_i) \leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)$ + \item computes transfer secret $x_i \leftarrow \algo{Kx}(t_i, \V{pkCoin}_0)$ + \item computes coin key pair $(\V{skCoin}_i, \V{pkCoin}_i) \leftarrow + \algo{KeyGen}^*_{CSK}(x_i, 1^\lambda)$ + \item and executes the modified blinding protocol + \[ + (\overline{m}_i, r_i, \mathcal{T}_{(B*,i)}) \leftarrow + \algo{Blind}^*_{BS}(\mathcal{E}(\V{skD_u}), \mathcal{C}(x_i, \V{skCoin}_0, \V{pkD}_u, \V{pkCoin}_i)) + \] + with the exchange. + \end{enumerate} + + The customer stores the refresh identifier + \begin{equation} + \V{rid} := (\V{coin}_0, \V{pkD}_u, \{ s_i \}, \{ \overline{m}_i \}, \{r_i\}, \{\mathcal{T}_{(B*,i)}\} ). + \end{equation} + + \item $\algo{RefreshPickup}(\prt{E}(\V{sksE}, \V{pkCustomer}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{rid})) \rightarrow \mathcal{T}$: + The customer looks up the refresh identifier $\V{rid}$ and recomputes the transfer key pairs, + transfer secrets and new coin key pairs. + + Then customer sends the commitment $\pi_1 = (\V{pkCoin}_0, \V{pkD}_u, h_C)$ together with signature $\V{sig}_1 + \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, \pi_1)$ to the exchange, where + \begin{align*} + h_T &:= H(T_1, \dots, T_\kappa)\\ + h_{\overline{m}} &:= H(\overline{m}_1, \dots, \overline{m}_\kappa)\\ + h_C &:= H(h_T \Vert h_{\overline{m}}) + \end{align*} + + The exchange checks the signature $\V{sig}_1$, and aborts if invalid. Otherwise, + depending on the commitment: + \begin{enumerate} + \item If the exchange did not see $\pi_1$ before, it marks $\V{pkCoin}_0$ + as spent for $D(\V{pkD}_u)$, chooses a uniform random $0 \le \gamma < \kappa$, stores it, + and sends this choice in a signed message $(\gamma, \V{sig}_2)$ to the customer, + where $\V{sig}_2 \leftarrow \algo{Sign}_{S}(\V{skESig}, \gamma)$. + \item Otherwise, the exchange sends back the same $\pi_2$ as it sent for the last + equivalent $\pi_1$. + \end{enumerate} + + The customer checks if $\pi_2$ differs from a previously received $\pi_2'$ for the same + request $\pi_1$, and aborts if such a conflicting response was found. + Otherwise, the customer in response to $\pi_2$ sends the reveal message + \begin{equation*} + \pi_3 = T_\gamma, \overline{m}_\gamma, + (s_1, \dots, s_{\gamma-1}, s_{\gamma+1}, \dots, s_\kappa) + \end{equation*} + and signature + \begin{equation*} + \V{sig}_{3'} \leftarrow \algo{Sign}_{CSK}(\V{skCoin}_0, (\V{pkCoin}_0, + \V{pkD}_u, \mathcal{T}_{(B*,\gamma)}, T_\gamma, \overline{m}_\gamma)) + \end{equation*} to the exchange. Note that $\V{sig}_{3'}$ is not a signature + over the full reveal message, but is primarily used in the linking protocol for + checks by the customer. + + The exchange checks the signature $\V{sig}_{3'}$ and then computes for $i \ne \gamma$: + \begin{align*} + (t_i', T_i') &\leftarrow \algo{KeyGen}^*_{CSK}(s_i, 1^\lambda)\\ + x_i' &\leftarrow \algo{Kx}(t_i, \V{pkCoin}_0)\\ + (\V{skCoin}_i', \V{pkCoin}_i') &\leftarrow + \algo{KeyGen}^*_{CSK}(x_i', 1^\lambda) \\ + h_T' &:= H(T'_1, \dots, T_{\gamma-1}', T_\gamma, T_{\gamma+1}', \dots, T_\kappa') + \end{align*} + and simulates the blinding protocol with recorded transcripts (without signing each message, + as indicated by the dot ($\cdot$) instead of a signing secret key), obtaining + \begin{align*} + (\overline{m}_i', r_i', \mathcal{T}_i) &\leftarrow + \algo{Blind}^*_{BS}(\mathcal{S}(\V{skD}_u), \mathcal{R}(x_i', \cdot, \V{pkD}_u, \V{skCoin}'_i))\\ + \end{align*} + and finally + \begin{align*} + 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' \Vert h_{\overline{m}}'). + \end{align*} + + Now the exchange checks if $h_C = h_C'$, and aborts the protocol if the check fails. + Otherwise, the exchange sends a message back to $\prt{C}$ that the commitment verification succeeded and includes + the signature + \begin{equation*} + \overline{\sigma}_\gamma := \algo{Sign}_{BS}(\mathcal{E}(\V{skD}_u), \mathcal{C}(\overline{m}_\gamma)). + \end{equation*} + + As a last step, the customer obtains the signature $\sigma_\gamma$ on the new coin's public key $\V{pkCoin}_u$ with + \begin{equation*} + \sigma_\gamma := \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma). + \end{equation*} + + Thus, the new, unlinkable coin is $\V{coin}_u := (\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$. + + \item $\algo{Link}(\prt{E}(\V{sksE}), \prt{C}(\V{skCustomer}, \V{pksE}, \V{coin}_0))$: + The customer sends the public key $\V{pkCoin}_0$ of $\V{coin}_0$ to the exchange. + + For each completed refresh on $\V{pkCoin}_0$ recorded in the exchange's + database, the exchange sends the following data back to the customer: the + signed commit message $(\V{sig}_1, \pi_1)$, the transfer public key + $T_\gamma$, the signature $\V{sig}_{3'}$, the blinded signature $\overline{\sigma}_\gamma$, and the + transcript $\mathcal{T}_{(B*,\gamma)}$ of the customer's and exchange's messages + during the $\algo{Blind}^*_{BS}$ protocol execution. + + The following logic is repeated by the customer for each response: + \begin{enumerate} + \item Verify the signatures (both from $\V{pkESig}$ and $\V{pkCoin}_0$) on the transcript $\mathcal{T}_{(B*,\gamma)}$, + abort otherwise. + \item Verify that $\V{sig}_1$ is a valid signature on $\pi_1$ by $\V{pkCoin}_0$, abort otherwise. + \item Re-compute the transfer secret and the new coin's key pair as + \begin{align*} + x_\gamma &\leftarrow \algo{Kx}_{CSK}(\V{skCoin}_0, T_\gamma)\\ + (\V{skCoin}_\gamma, \V{pkCoin}_\gamma) &\leftarrow \algo{KeyGen}_{CSK}^*(x_\gamma, 1^\lambda). + \end{align*} + \item Simulate the blinding protocol with the message transcript received from the exchange to obtain + $(\overline{m}_\gamma, r_\gamma)$. + \item Check that $\algo{Verify}_{CSK}(\V{pkCoin}_0, + \V{pkD}_u, \V{skCoin}_0,(\mathcal{T}_{(B*,\gamma)}, \overline{m}_\gamma), \V{sig}_{3'})$ + indicates a valid signature, abort otherwise. + \item Unblind the signature to obtain $\sigma_\gamma \leftarrow \algo{UnblindSig}(r_\gamma, \V{pkCoin}_\gamma, \overline{\sigma}_\gamma)$ + \item (Re-)add the coin $(\V{skCoin}_\gamma, \V{pkCoin}_\gamma, \V{pkD}_u, \sigma_\gamma)$ to the customer's wallet. + \end{enumerate} + +\end{itemize} + +\subsection{Concrete Instantiation} +We now give a concrete instantiation that is used in the implementation +of GNU Taler for the schemes \textsc{BlindSign}, \textsc{CoinSignKx} and \textsc{Sign}. + +For \textsc{BlindSign}, we use RSA-FDH blind signatures +\cite{chaum1983blind,bellare1996exact}. From the information-theoretic +security of blinding, the computational blindness property follows directly. For +the unforgeability property, we additionally rely on the RSA-KTI assumption as +discussed in \cite{bellare2003onemore}. Note that since the blinding step in +RSA blind signatures is non-interactive, storage and verification of the +transcript is omitted in refresh and link. + +We instantiate \textsc{CoinSignKx} with signatures and key exchange operations +on elliptic curves in Edwards form, where the same key is used for signatures +and the Diffie--Hellman key exchange operations. In practice, we use Ed25519 +\cite{bernstein2012high} / Curve25519 \cite{bernstein2006curve25519} for +$\lambda=256$. We caution that some other elliptic curve key exchange +implementation might not satisfy the completeness property that we require, due +to the lack of complete addition laws. + +For \textsc{Sign}, we use elliptic-curve signatures, concretely Ed25519. For +the collision-resistant hash function $H$ we use SHA-512 \cite{rfc4634} and +HKDF \cite{rfc5869} as a PRF. + +%In Taler's refresh, we avoid key exchange failures entirely because the +%Edwards addition law is complete abelian group operation on the curve, +%and the signature scheme verifies that the point lies on the curve. +%% https://safecurves.cr.yp.to/refs.html#2007/bernstein-newelliptic +%% https://safecurves.cr.yp.to/complete.html +%We warn however that Weierstrass curves have incomplete addition formulas +%that permit an adversarial merchant to pick transfer keys that yields failures. +%There are further implementation mistakes that might enable collaborative +%key exchange failures, like if the exchange does not enforce the transfer +%private key being a multiple of the cofactor. +% +%In this vein, almost all post-quantum key exchanges suffer from key exchange +%failures that permit invalid key attacks against non-ephemeral keys. +%All these schemes support only one ephemeral party by revealing the +%ephemeral party's private key to the non-ephemeral party, +% ala the Fujisaki-Okamoto transform~\cite{fujisaki-okamoto} or similar. +%We cannot reveal the old coin's private key to the exchange when +%verifying the transfer private keys though, which +% complicates verifying honest key generation of the old coin's key. + + +\section{Proofs} +%\begin{mdframed} +% Currently the proofs don't have any explicit tightess bounds. +% Because we don't know where to ``inject'' the value that we get from the challenger when carrying out +% a reduction, we need to randomly guess in which coin/signature we should ``hijack'' our challenge value. +% Thus for the proofs to work fully formally, we need to bound the total number of oracle invocations, +% and our exact bound for the tightness of the reduction depends on this limit. +%\end{mdframed} + +We now give proofs for the security properties defined in Section \ref{sec:security-properties} +with the generic instantiation of Taler. + +\subsection{Anonymity} + +\begin{theorem} + Assuming + \begin{itemize} + \item the blindness of \textsc{BlindSign}, + \item the unforgeability and key exchange security of \textsc{CoinSignKx}, and + \item the collision resistance of $H$, + \end{itemize} + our instantiation satisfies anonymity. +\end{theorem} + +\begin{proof} + We give a proof via a sequence of games $\mathbb{G}_0(b), \mathbb{G}_1(b), + \mathbb{G}_2(b)$, where $\mathbb{G}_0(b)$ is the original anonymity game + $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, 1^\kappa, b)$. We show that the + adversary can distinguish between subsequent games with only negligible + probability. Let $\epsilon_{HC}$ and $\epsilon_{KX}$ be the advantage of an + adversary for finding hash collisions and for breaking the security of the + key exchange, respectively. + + We define $\mathbb{G}_1$ by replacing the link oracle \ora{Link} with a + modified version that behaves the same as \ora{Link}, unless the adversary + responds with link data that did not occur in the transcript of a successful + refresh operation, but despite of that still passes the customer's + verification. In that case, the game is aborted instead. + + Observe that in case this failure event happens, the adversary must have forged a + signature on $\V{sig}_{3}$ on values not signed by the customer, yielding + an existential forgery. Thus, $\left| \Prb{\mathbb{G}_0 = 1} - \Prb{\mathbb{G}_1 = 1} + \right|$ is negligible. + + In $\mathbb{G}_2$, the refresh oracle is modified so that the customer + responds with value drawn from a uniform random distribution $D_1$ for the + $\gamma$-th commitment instead of using the key exchange function. We must + handle the fact that $\gamma$ is chosen by the adversary after seeing the + commitments, so the challenger first makes a guess $\gamma^*$ and replaces + only the $\gamma^*$-th commitment with a uniform random value. If the + $\gamma$ chosen by the adversary does not match $\gamma^*$, then the + challenger rewinds \prt{A} to the point where the refresh oracle was called. + Note that we only replace the one commitment that + will not be opened to the adversary later. + + Since $\kappa \ll \lambda$ and the security property of $\algo{Kx}$ + guarantees that the adversary cannot distinguish the result of a key exchange + from randomness, the runtime complexity of the challenger still stays + polynomial in $\lambda$. An adversary that could with high probability + choose a $\gamma$ that would cause a rewind, could also distinguish + randomness from the output of $\algo{Kx}$. + + %\mycomment{Tighness bound also missing} + + We now show that $\left| \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} + \right| \le \epsilon_{KX}$ by defining a distinguishing game $\mathbb{G}_{1 + \sim 2}$ for the key exchange as follows: + + \bigskip + \noindent $\mathbb{G}_{1 \sim 2}(b)$: + \vspace{-0.5\topsep} + \begin{enumerate} + \setlength\itemsep{0em} + \item If $b=0$, set + \[ + D_0 := \{ (A, B, \V{Kex}(a, B)) \mid (a, A) \leftarrow \V{KeyGen}(1^\lambda),(b, B) \leftarrow \V{KeyGen}(1^\lambda) \}. + \] + Otherwise, set + \[ + D_1 := \{ (A, B, C) \mid (a, A) \leftarrow \V{KeyGen}(1^\lambda), + (b, B) \leftarrow \V{KeyGen}(1^\lambda), + C \randsel \{1,\dots,2^\lambda\} \}. + \] + + \item Return $\mathit{Exp'}_{\cal A}^{anon}(b, D_b)$ + + (Modified anonymity game where the $\gamma$-th commitment in the + refresh oracle is drawn uniformly from $D_b$ (using rewinding). Technically, we need to + draw from $D_b$ on withdraw for the coin secret key, write it to a table, look it up on refresh and + use the matching tuple, so that with $b=0$ we perfectly simulate $\mathbb{G}_1$.) + \end{enumerate} + + Depending on the coin flip $b$, we either simulate + $\mathbb{G}_1$ or $\mathbb{G}_2$ perfectly for our adversary~$\mathcal{A}$ + against $\mathbb{G}_1$. At the same time $b$ determines whether \prt{A} + receives the result of the key exchange or real randomness. Thus, $\left| + \Prb{\mathbb{G}_1 = 1} - \Prb{\mathbb{G}_2 = 1} \right| = \epsilon_{KX}$ is + exactly the advantage of $\mathbb{G}_{1 \sim 2}$. + + We observe in $\mathbb{G}_2$ that as $x_\gamma$ is uniform random and not + learned by the adversary, the generation of $(\V{skCoin}_\gamma, + \V{pkCoin}_\gamma)$ and the execution of the blinding protocol is equivalent (under the PRF assumption) + to using the randomized algorithms + $\algo{KeyGen}_{CSK}$ and $\algo{Blind}_{BS}$. + + By the blindness of the $\textsc{BlindSign}$ scheme, the adversary is not + able to distinguish blinded values from randomness. Thus, the adversary is + unable to correlate a $\algo{Sign}_{BS}$ operation in refresh or withdraw + with the unblinded value observed during $\algo{Deposit}$. + + We conclude the success probability for $\mathbb{G}_2$ must be $1/2$ and + hence the success probability for $\mathit{Exp}_{\cal A}^{anon}(1^\lambda, + \kappa, b)$ is at most $1/2 + \epsilon(\lambda)$, where $\epsilon$ is a + negligible function. +\end{proof} +% RSA ratios vs CDH in BLS below + +\subsection{Conservation} + +\begin{theorem} + Assuming existential unforgeability (EUF-CMA) of \textsc{CoinSignKx}, our instantiation satisfies conservation. +\end{theorem} + +\begin{proof} + +% FIXME: argue that reduction is tight when you have malleability + In honest executions, we have $\V{withdrawn}[\V{pkCustomer}] = v_C + v_S$, i.e., + the coins withdrawn add up to the coins still available and the coins spent + for known transactions. + + In order to win the conservation game, the adversary must increase + $\V{withdrawn}[\V{pkCustomer}]$ or decrease $v_C$ or $v_S$. An adversary can + abort withdraw operations, thus causing $\V{withdrawn}[\V{pkCustomer}]$ to increase, + while the customer does not obtain any coins. However, in step + \ref{game:conserv:run}, the customer obtains coins from interrupted withdraw + operations. Similarly, for the refresh protocol, aborted \algo{RefreshRequest} / \algo{RefreshPickup} + operations that result in a coin's remaining value being reduced are completed + in step \ref{game:conserv:run}. + + Thus, the only remaining option for the adversary is to decrease $v_C$ or $v_S$ + with the $\ora{RefreshPickup}$ and $\ora{Deposit}$ oracles, respectively. + + Since the exchange verifies signatures made by the secret key of the coin + that is being spent/refreshed, the adversary must forge this signature or have + access to the coin's secret key. As we do not give the adversary access to + the sharing oracle, it does not have direct access to any of the honest + customer's coin secret keys. + + Thus, the adversary must either compute the coin's secret key from observing + the coin's public key (e.g., during a partial deposit operation), or forge + signatures directly. Both possibilities allow us to carry out a reduction + against the unforgeability property of the $\textsc{CoinSignKx}$ scheme, by + injecting the challenger's public key into one of the coins. + +\end{proof} + +\subsection{Unforgeability} + +\begin{theorem} +Assuming the unforgeability of \textsc{BlindSign}, our instantiation satisfies {unforgeability}. +\end{theorem} + +\begin{proof} +The adversary must have produced at least one coin that was not blindly +signed by the exchange. +In order to carry out a reduction from this adversary to a blind signature +forgery, we inject the challenger's public key into one randomly chosen +denomination. Since we do not have access to the corresponding secret key +of the challenger, signing operations for this denomination are replaced +with calls to the challenger's signing oracle in \ora{WithdrawPickup} and +\ora{RefreshPickup}. For $n$ denominations, an adversary against the +unforgeability game would produce a blind signature forgery with probability $1/n$. +\end{proof} + +%TODO: RSA-KTI + +\subsection{Income Transparency} +\begin{theorem} + Assuming + \begin{itemize} + \item the unforgeability of \textsc{BlindSign}, + \item the key exchange completeness of \textsc{CoinSignKx}, + \item the pseudo-random function property of \V{PRF}, and + \item the collision resistance of $H$, + \end{itemize} + our instantiation satisfies {weak income transparency}. +\end{theorem} + +\begin{proof} + We consider the directed forest on coins induced by the refresh protocol. + It follows from unforgeability that any coin must originate from some + customer's withdraw in this graph. + We may assume that all $\V{coin}_1, \dots, \V{coin}_l$ originate from + non-corrupted users, for some $l \leq \ell$. % So $\ell \leq w + |X|$. + + For any $i \leq l$, there is a final refresh operation $R_i$ in which + a non-corrupted user could obtain the coin $C'$ consumed in the refresh + via the linking protocol, but no non-corrupted user could obtain the + coin provided by the refresh, as otherwise $\V{coin}_i$ gets marked as + spent in step step \ref{game:income:spend}. + Set $F := \{ R_i \mid i \leq l \}$. + + During each $R_i \in F$, our adversary must have submitted a blinded + coin and transfer public key for which the linking protocol fails to + produce the resulting coin correctly, otherwise the coin would have + been spent in step \ref{game:income:spend}. In this case, we consider + several non-exclusive cases + \begin{enumerate} + \item the execution of the refresh protocol is incomplete, + \item the commitment for the $\gamma$-th blinded coin and transfer + public key is dishonest, + \item a commitment for a blinded coin and transfer public key other + than the $\gamma$-th is dishonest, + \end{enumerate} + + We show these to be exhaustive by assuming their converses all hold: As the + commitment is signed by $\V{skCoin}_0$, our key exchange completeness + assumption of $\textsc{CoinSignKx}$ applies to the coin public key. + Any revealed values must match our honestly computed commitments, + as otherwise a collision in $H$ would have been found. + We assumed + the revealed $\gamma$-th transfer public key is honest. Hence our key + exchange completeness assumption of $\textsc{CoinSignKx}$ yields + $\algo{Kex}_{CSK}(t,C') = \algo{Kex}_{CSK}(c',T)$ where $T = + \algo{KeyGenPub}_{CSK}(t)$ is the transfer key, thus the customer obtains the + correct transfer secret. We assumed the refresh concluded and all + submissions besides the $\gamma$-th were honest, so the exchange correctly + reveals the signed blinded coin. We assumed the $\gamma$-th blinded coin is + correct too, so customer now re-compute the new coin correctly, violating + $R_i \in F$. + + We shall prove + \begin{equation}\label{eq:income-transparency-proof} + \Exp{{\frac{p}{b + p}} \middle| F \neq \emptyset} = {\frac{1}{\kappa}} + \end{equation} + where the expectation runs over + any probability space used by the adversary and challenger. + + We shall now consider executions of the income transparency game with an + optimal adversary with respect to maximizing $\frac{p}{b + p}$. Note that this + is permissible since we are not carring out a reduction, but are interested + in the expectation of the game's return value. + + As a reminder, if a refresh operation is initiated using a false commitment + that is detected by the exchange, then the new coin cannot be obtained, and + contributes to the lost coins $b := w - s$ instead of the winnings $p := L - + w'$. We also note $b + p$ gives the value of + refreshes attempted with false commitments. As these are non-negative, + $\frac{p}{b + p}$ is undefined if and only if $p = 0$ and $b = 0$, which happens if and + only if the adversary does not use false commitments, i.e., $F = \emptyset$. + + We may now assume for optimality that $\mathcal{A}$ submits a false + commitment for at most one choice of $\gamma$ in any $R_i \in F$, as + otherwise the refresh always fails. Furthermore, for an optimal adversary we + can exclude refreshes in $F$ that are incomplete, but that would be possible + to complete successfully, as completing such a refresh would only increase the + adversaries winnings. + + We emphasize that an adversary that loses an $R_i$ loses the coin that would + have resulted from it completely, while an optimal adversary who wins an + $R_i$ should not gamble again. Indeed, an adversary has no reason to touch + its winnings from an $R_i$. + +% There is no way to influence $p$ or $b$ through withdrawals or spends +% by corrupted users of course. In principle, one could decrease $b$ by +% sharing from a corrupted user to a non-corrupted users, +% but we may assume this does not occur either, again by optimality. + + For any $R_i$, there are $\kappa$ game runs identical up through the + commitment phase of $R_i$ and exhibiting different outcomes based on the + challenger's random choice of $\gamma$. + If $v_i$ is the financial value of the coin resulting from refresh operation + $R_i$ then one of the possible runs adds $v_i$ to $p$, while the remaining + $\kappa-1$ runs add $v_i$ to $b$. + + We define $p_i$ and $b_i$ to be these contributions summed over the $\kappa$ possible + runs, i.e., + \begin{align*} + p_i &:= v_i\\ + b_i &= (\kappa - 1)v_i + \end{align*} + The adversary will succeed in $1/\kappa$ runs ($p_i=v$) and loses in + $(\kappa-1)/\kappa$ runs ($p_i=0$). Hence: + \begin{align*} + \Exp{{\frac{p}{b + p}} \middle| F \neq \emptyset} + &= \frac{1}{|F|} \sum_{R_i\in F} {p_i \over b_i + p_i} \\ + &= \frac{1}{\kappa |F|} \sum_{R_i\in F} {\frac{v_i}{0 + v_i}} + \frac{\kappa-1}{\kappa |F|} \sum_{R_i \in F} {\frac{0}{v_i + 0}} \\ + &= {\frac{1}{\kappa}}, + \end{align*} + which yields the equality (\ref{eq:income-transparency-proof}). + +As for $F = \emptyset$, the return value of the game must be $0$, we conclude +\begin{equation*} + E\left[\mathit{Exp}_{\cal A}^{income}(1^\lambda, 1^\kappa)\right] \le {\frac{1}{\kappa}}. +\end{equation*} + +\end{proof} + +\section{Discussion} + +\subsection{Limitations} +Not all features of our implementation are part of the security model and proofs. +In particular, the following features are left out of the formal discussion: + +\begin{itemize} + \item Reserves. In our formal model, we effectively assume that every customer has access + to exactly one unlimited reserve. + \item Offline and online keys. In our implementation, the exchange + has one offline master signing key, and online signing keys with + a shorter live span. + \item Refunds allow merchants to effectively ``undo'' a deposit operation + before the exchange settles the transaction with the merchant. This simple + extension preserves unlinkability of payments through refresh. + %\item Indian merchant scenario. In some markets (such as India), it is more + % likely for the customer to have Internet access (via smart phones) than for + % merchants, who in the case of street vendors often have simple phones + % without Internet access or support for apps. To use Taler in this case, + % it must be possible + \item Timeouts. In practice, a merchant gives the customer a deadline until + which the payment for a contract must have been completed, potentially by + using multiple coins. + + If a customer is unable to complete a payment (e.g., because they notice + that their coins are already spent after a restore from backup), a refund + for this partial payment can be requested from the merchant. + + Should the merchant become unavailable after a partially completed payment, + there are two possibilities: Either the customer can deposit the coins on + behalf of the merchant to obtain proof of their on-time payment, which can + be used in a later arbitration if necessary. Alternatively, the customer + can ask the exchange to undo the partial payments, though this requires the + exchange to know (or learn from the customer) the exact amount to be payed + for the contract. + + %A complication in practice is that merchants may not want to reveal their + %full bank account information to the customer, but this information is + %necessary for the exchange to process the deposit, since we do not require + %merchants to register beforehand the exchange (as the merchant might + %support all exchanges audited by a specific auditor). We discuss a protocol + %extension that allows customers to deposit coins on behalf of merchants + %in~\ref{XXX}. + + \item The fees incurred for operations, the protocols for backup and + synchronization as well as other possible extensions like tick payments are + not formally modeled. + + %\item FIXME: auditor +\end{itemize} + +We note that customer tipping (see \ref{taler:design:tipping}) basically amounts to an execution +of the \algo{Withdraw} protocol where the party that generates the coin keys +and blinding factors (in that case the merchant's customer) is different from +the party that signs the withdraw request (the merchant with a ``customer'' key +pair tied to the merchant's bank account). While this is desirable in some +cases, we discussed in \ref{taler:design:fixing-withdraw-loophole} how this ``loophole'' for a one-hop untaxed +payment could be avoided. + +\subsection{Other Properties} + +\subsubsection{Exculpability} +Exculpability is a property of offline e-cash which guarantees that honest users +cannot be falsely blamed for misbehavior such as double spending. For online +e-cash it is not necessary, since coins are spent online with the exchange. In +practice, even offline e-cash systems that provide exculpability are often +undesirable, since hardware failures can result in unintentional overspending +by honest users. If a device crashes after an offline coin has been sent to +the merchant but before the write operation has been permanently recorded on +the user's device (e.g., because it was not yet flushed from the cache to a +hard drive), the next payment will cause a double spend, resulting in anonymity +loss and a penalty for the customer. + +% FIXME: move this to design or implementation +\subsubsection{Fair Exchange}\label{sec:security:atomic-swaps} + +% FIXME: we should mention "atomic swap" here + +The Endorsed E-Cash system by Camenisch et al. \cite{camenisch2007endorsed} +allows for fair exchange---sometimes called atomic swap in the context of +cryptocurrencies---of online or offline e-cash against digital goods. The +online version of Camenisch's protocol does not protect the customer against +loss of anonymity from linkability of aborted fair exchanges. + +Taler's refresh protocol can be used for fair exchange of online e-cash against +digital goods, without any loss of anonymity due to linkability of aborted +transactions, with the following small extension: The customer asks the +exchange to \emph{lock coins to a merchant} until a timeout. Until the timeout +occurs, the exchange provides the merchant with a guarantee that these coins can +only be spent with this specific merchant, or not at all. The +fair exchange exchanges the merchant's digital goods against the customer's +deposit permissions for the locked coins. On aborted fair exchanges, +the customer refreshes to obtain unlinkable coins. + diff --git a/doc/system/taler/snippet-keys.txt b/doc/system/taler/snippet-keys.txt new file mode 100644 index 000000000..b05c79524 --- /dev/null +++ b/doc/system/taler/snippet-keys.txt @@ -0,0 +1,62 @@ +{ + "version": "2:0:0", + "master_public_key": "CQQZ...", + "reserve_closing_delay": "/Delay(2419200)/", + "signkeys": [ + { + "stamp_start": "/Date(1522223035)/", + "stamp_expire": "/Date(1533109435)/", + "stamp_end": "/Date(1585295035)/", + "master_sig": "842D...", + "key": "05XW..." + } + ], + "payback": [], + "denoms": [ + { + "master_sig": "BHG5...", + "stamp_start": "/Date(1500450235)/", + "stamp_expire_withdraw": "/Date(1595058235)/", + "stamp_expire_deposit": "/Date(1658130235)/", + "stamp_expire_legal": "/Date(1815810235)/", + "denom_pub": "51RD...", + "value": "TESTKUDOS:10", + "fee_withdraw": "TESTKUDOS:0.01", + "fee_deposit": "TESTKUDOS:0.01", + "fee_refresh": "TESTKUDOS:0.01", + "fee_refund": "TESTKUDOS:0.01" + }, + { + "master_sig": "QT0T...", + "stamp_start": "/Date(1500450235)/", + "stamp_expire_withdraw": "/Date(1595058235)/", + "stamp_expire_deposit": "/Date(1658130235)/", + "stamp_expire_legal": "/Date(1815810235)/", + "denom_pub": "51R7", + "value": "TESTKUDOS:0.1", + "fee_withdraw": "TESTKUDOS:0.01", + "fee_deposit": "TESTKUDOS:0.01", + "fee_refresh": "TESTKUDOS:0.01", + "fee_refund": "TESTKUDOS:0.01" + }, + ], + "auditors": [ + { + "denomination_keys": [ + { + "denom_pub_h": "RNTQ...", + "auditor_sig": "6SC2..." + }, + { + "denom_pub_h": "CP6B...", + "auditor_sig": "0GSE..." + } + ], + "auditor_url": "https://auditor.test.taler.net/", + "auditor_pub": "BW9DC..." + } + ], + "list_issue_date": "/Date(1530196508)/", + "eddsa_pub": "05XW...", + "eddsa_sig": "RXCD..." +} |