\section{Remediation of the Withdraw Loophole}
The withdraw loophole allows untaxed and untraceable payments by "misusing" the withdraw protocol.
It allows withdraw operations where owner of the resulting coins isn't the owner of the reserve that the coins where withdrawn from.
It is used for tipping and can therefore be seen as a feature.

Using the withdraw loophole for payments is illustrated in figure \ref{fig:withdraw-loophole-exploit}.
Note that we omitted the parts leading up to the coin creation (contract, agreement of price, number of coins and their denominations).
This is how it works on a high level:
\begin{enumerate}
    \item The malicous merchant generates and blinds coins, which are then transmitted to the customer
    \item The customer authorizes the withdraw from his reserve by signing the blinded coins with the private key of his reserve, thus generating withdraw confirmations.
    \item The withdraw confirmations are transmitted to the exchange, which generates the signatures and returns them to the malicous merchant.
    \item The malicous merchant unblinds the signatures.
    He is now in possession of the coin, thus the payment is completed.
\end{enumerate}

\begin{figure}[h]
    \begin{equation*}
        \begin{array}{ l c l}
            % preliminaries
            \text{Customer} &  & \text{malicous Merchant}
            \\ \text{knows:} & & \text{knows:}
            \\ \text{reserve keys } w_s, W_p
            \\ \text{denomination public key } D_p = \langle e, N \rangle & & \text{denomination public key } D_p = \langle e, N \rangle
            \\
            % generate coin
            \\ & & \text{generate coin key pair:}
            \\ & & c_s, C_p \leftarrow \text{Ed25519.KeyGen}()
            % blind
            \\ & & \text{blind:}
            \\ & & r \leftarrow random \in \mathbb{Z}_N^*
            \\ & & m' := \text{FDH}(N, C_p)*r^{e} \mod N
            % sing with reserve sk
            \\ & \xleftarrow[\rule{2cm}{0pt}]{m'}
            \\ \text{sign with reserve private key:}            
            \\ \rho_W := \langle D_p, m' \rangle
            \\ \sigma_W := \text{Ed25519.Sign}(w_s, \rho_W)
            \\ & \xrightarrow[\rule{2cm}{0pt}]{ \langle W_p, \sigma_W, \rho_W \rangle }
            \\
            % TODO add some kind of separator
            \hline
            \\
            \text{malicous Merchant} &  & \text{Exchange}
            \\\text{knows:} & & \text{knows:}
            \\& & \text{reserve public key } W_p
            \\ \text{denomination public key } D_p = \langle e, N \rangle & & \text{denomination keys } d_s, D_p
            \\
            \\ & \xrightarrow[\rule{2cm}{0pt}]{ \langle W_p, \sigma_W, \rho_W \rangle }
            \\ & & \langle D_p, m' \rangle := \rho_W
            \\ & & \text{verify if } D_p \text{ is valid}
            \\ & & \textbf{check } \text{Ed25519.Verify}(W_p, \rho_W, \sigma_W)
            \\ & & \text{decrease balance if sufficient}
            \\ & & \text{sign:}
            \\ & & \sigma'_c := (m')^{d_s} \mod N
            \\ & \xleftarrow[\rule{2cm}{0pt}]{\sigma'_c}
            \\ \text{unblind:}
            \\ \sigma_c := \sigma'_c*r^{-1}
            \\ \text{verify signature:}
            \\ \textbf{check if } \sigma_c = \text{FDH}(N, C_p)
            \\
            \\ \text{resulting coin: } \langle c_s, C_p, \sigma_c, D_p \rangle
        \end{array}
    \end{equation*}
    \caption{untaxed payment using withdraw loophole}
    \label{fig:withdraw-loophole-exploit}
\end{figure}

\subsection{Requirements For A Possible Solution}
A viable solution has to fix the withdraw loophole, while still providing a solution for tipping. In addition, Taler's security properties must not be weakened.

The underlying problem that has to be solved is to check that the person withdrawing a coin is also the owner of the reserve used in the withdraw.
This has to be solved in a way that prevents the customer and malicious merchant to work together.

% Requirements For A Perfect Solution}
% minimal adjustments to Taler
% Commitment to sk of Reserve -> constructed by customer (key owner)
% commitment to sk of coin
%   how do we ensure that the customer is key owner? -> combine with reserve sk
%   how do we verify? problems with blinding
%   how do we ensure that the coin in the commitment is the coin that is signed?
% exchange must not learn anything about coin to prevent linking of withdraw and transaction

\subsection{Discussed Solution}
For our proposed solution, a few adjustments to Taler have to be made:
\begin{itemize}
    \item The withdraw confirmation must include a commitment to the public key.
    This commitment must be constructed in a way that requires the customer to know the public key.
    The exception to this are special tipping reserves (to preserve the tipping feature).
    \item Cut-and-choose is added to the withdraw protocol.
    This means that the customer has to generate the coin and withdraw confirmation $ k $ times.
    The exchange will then choose one of the $ k $ sessions.
    The customer has to reveal the coin public key, blinding secret and commitment for all sessions except the chosen one.
    If the customer isn't able to deliver, the reserve is locked for future withdraws until the other sessions are delivered.
    Cut-and-choose is introduced to verify whether the customer honestly created the commitment and used the same coin public key for the signature creation and the commitment.
    If the reserve is a special tip reserve (which has to be registered), this check is omitted.
    \item An additional protocol is created that transfers the remaining value of a coin back to the reserve if anyone is able to reveal the commitment from the withdrawal.
    The adjustments described up to this point lead to the customer knowing all the necessary values for using this protocol.
    Besides the customer, no one must be able to reproduce the commitment, except in case of a reserve key compromise.
    \item Reserves are limited (usually only one, unless justified) and bound to a customer (KYC).
    % this goes further than fixing the loophole. It prevents people from creating new reserves that are then to be transfered
    % TODO check if there are disadvantages to this, especially regarding privacy
    \item For a coin to be refreshable, it must have been seen by the exchange before, meaning that it had to be used for a payment.
    The purpose of this is to prevent a malicious merchant to simply refresh a coin after withdraw to prevent the customer from reverting the withdraw.
    \item For any coin used in a payment, the subtracted value must be higher that a certain threshold (set globally or per denomination).
    For example, if the threshold is $ 10\% $, at least CHF 10 of a 100 CHF coin must be used for a payment.
    The goal of this change is to prevent a malicious merchant from buying a very cheap article to be able to refresh the coin.
\end{itemize}

The commitment has to fulfill the following properties:
\begin{enumerate}
    \item It has to be constructed using the reserve private key and must be verifiable using the corresponding public key.
    \item It has to include the coin public key.
    \item It has to be constructed in a way that ensures that the customer has knowledge of the coin public key.
    \item Everyone with knowledge of the two keys must be able to recreate it.
\end{enumerate}

A possible commitment that partially satisfies the properties can be constructed by hashing a signature of the coin's public key:
\begin{equation*}
    H( \text{Ed25519.Sign} (w_w, C_p) )
\end{equation*}
Note that the PureEdDSA variant of Ed25519 has to be used for this.
This variant doesn't hash the message before signing (see \cite{rfc8032} for further details).\\
It is still possible for a customer and a malicious merchant to construct the commitment without the customer gaining knowledge of the coin public key.
However, the customer has to share one half of the hash of the reserve private key (which is practically one half of the private key, refer to section \ref{sec:eddsa-signature-creation} for details about EdDSA signature creation).

% was passiert wenn im Verhör und gezwungen wird, Keys herauszurücken?

There is one drawback to this solution:
In case of a reserve key compromise, coins generated by withdraw operation (not refreshed ones) can be linked to withdraw operations, thus revealing relationships between reserves and payments.
This is because an adversary (exchange or auditor) in possession of a reserve private key and coin public keys can calculate $ \text{H(Ed25519.Sign}(w_s, C_p)) $ and check in the database if there is a corresponding withdraw operation, thus linking reserve and coin.

\subsubsection{Discussion}
This is not perfect solution.
It is designed to make untaxed payments using the withdraw loophole less attractive to use for merchants.
If accepted, it should only be used in deployments where the withdraw loophole has to be prohibited.\\
The proposed modifications achieve that a malicious merchant, who wants to perform payments using the withdraw loophole, has to accept one of these drawbacks:
\begin{itemize}
    \item He has to accept that the customer is able to revert the payment.
    \item He has to spend the coins fully.\\
    If he is registered as a merchant at an exchange, he can perform payments to himself to launder the money.
    Here, Talers \ac{AML} capabilities come into play.\\
    The other possibility is to buy goods at other merchants.
    These goods then have to be liquidated, which requires effort.
    This wouldn't be a problem (for the malicous merchant) if cryptocurrency can be bought using Taler.
    \item He has to spend the coins partially to be able to refresh them (thus preventing payment reversion by the customer).
    The goods that were bought using the coin fraction then would have to be liquidated (see previous point).
    \item He has to add the threshold value that is lost in order to refresh the coin into the price for payments.
\end{itemize}

The commitment added to the withdrawal weakens the privacy of coins.
Blinding guarantees everlasting privacy, which would be neutralized by the commitment.

The added cut-and-choose makes withdrawing more intensive, which leads to increased infrastructure requirements (and therefore costs).

The added threshold makes coin spending less flexible.
Wallets either have to contain more coins to guarantee that there is always a coin (or multiple) available to guarantee a payment without violating the threshold limitations.
The other variant is that wallets refrain from withdrawing coins with big(ger) denominations, which leads to bigger sums of coins used per payment.

This discussed solution is submitted to the Taler team as a part of the thesis documentation, upon which they can review the protocol changes and decide whether to pursue further.
Therefore, the solution will not be implemented during this thesis.
