diff options
| -rw-r--r-- | doc/paper/taler.tex | 534 |
1 files changed, 288 insertions, 246 deletions
diff --git a/doc/paper/taler.tex b/doc/paper/taler.tex index aaeb72b25..4a4f741a3 100644 --- a/doc/paper/taler.tex +++ b/doc/paper/taler.tex @@ -78,7 +78,7 @@ %Conference \acmConference[WOODSTOCK'97]{ACM Woodstock conference}{July 1997}{El - Paso, Texas USA} + Paso, Texas USA} \acmYear{1997} \copyrightyear{2016} @@ -97,8 +97,8 @@ %\affiliation{% % \institution{Institute for Clarity in Documentation} % \streetaddress{P.O. Box 1212} -% \city{Dublin} -% \state{Ohio} +% \city{Dublin} +% \state{Ohio} % \postcode{43017-6221} %} %\email{trovato@corporation.com} @@ -137,7 +137,7 @@ citizen's needs for private economic activity. % % The code below should be generated by the tool at % http://dl.acm.org/ccs.cfm -% Please copy and paste the code instead of the example below. +% Please copy and paste the code instead of the example below. % \begin{CCSXML} <ccs2012> @@ -161,7 +161,7 @@ citizen's needs for private economic activity. <concept_desc>Networks~Network reliability</concept_desc> <concept_significance>100</concept_significance> </concept> -</ccs2012> +</ccs2012> \end{CCSXML} \ccsdesc[500]{Computer systems organization~Embedded systems} @@ -306,13 +306,13 @@ blockchain's decentralized nature to escape anti-money laundering regulation~\cite{molander1998cyberpayments} as they provide anonymous, disintermediated transactions. -%GreenCoinX\footnote{\url{https://www.greencoinx.com/}} is a more -%recent AltCoin where the company promises to identify the owner of -%each coin via e-mail addresses and phone numbers. While it is unclear -%from their technical description how this identification would be -%enforced against a determined adversary, the resulting payment system -%would also merely impose a financial panopticon on a Bitcoin-style -%money supply and transaction model. +GreenCoinX\footnote{\url{https://www.greencoinx.com/}} is a more +recent AltCoin where the company promises to identify the owner of +each coin via e-mail addresses and phone numbers. While it is unclear +from their technical description how this identification would be +enforced against a determined adversary, the resulting payment system +would also merely impose a financial panopticon on a Bitcoin-style +money supply and transaction model. %\subsection{Chaum-style electronic cash} @@ -1165,42 +1165,277 @@ certification process. %destroying the link between the refunded or aborted transaction and %the new coin. +\section{Correctness} + +\subsection{Taxability arguments} + +We assume the exchange operates honestly when discussing taxability. +We feel this assumption is warranted mostly because a Taler exchange +requires licenses to operate as a financial institution, which it +risks loosing if it knowingly facilitates tax evasion. +We also expect an auditor monitors the exchange similarly to how +government regulators monitor financial institutions. +In fact, our auditor software component gives the auditor read access +to the exchange's database, and carries out test operations anonymously, +which expands its power over conventional auditors. + +\begin{proposition} +Assuming the exchange operates the refresh protocol honestly, +a customer operating the refresh protocol dishonestly expects to +loose $1 - {1 \over \kappa}$ of the value of their coins. +\end{proposition} + +\begin{proof} +An honest exchange keeps any funds being refreshed if the reveal +phase is never carried out, does not match the commitment, or shows +an incorrect commitment. As a result, a customer dishonestly +refreshing a coin looses their money if they have more than one +dishonest commitment. If they make exactly one dishonest +commitment, they have a $1 \over \kappa$ chance of their +dishonest commitment being selected for the refresh. +\end{proof} + +We say a coin $C$ is {\em controlled} by a user if the user's wallet knows +its secret scalar $c_s$, the signature $S$ of the appropriate denomination +key on its public key $C_s$, and the residual value of the coin. + +We assume the wallet cannot loose knowledge of a particular coin's +key material, and the wallet can query the exchange to learn the +residual value of the coin, so a wallet cannot loose control of +a coin. A wallet may loose the monetary value associated with a coin +if another wallet spends it however. + +We say a user Alice {\em owns} a coin $C$ if only Alice's wallets can +gain control of $C$ using standard interactions with the exchange. +In other words, ownership means exclusive control not just in the +present, but in the future even if another user interacts with the +exchange. + +\begin{theorem} +Let $C$ denote a coin controlled by users Alice and Bob. +Suppose Bob creates a coin $C'$ from $C$ following the refresh protocol. +Assuming the exchange and Bob operated the refresh protocol correctly, +and that the exchange continues to operate the linking protocol +(\S\ref{subsec:linking}) correctly, +then Alice can gain control of $C'$ using the linking protocol. +\end{theorem} + +\begin{proof} +Alice may run the linking protocol to obtain all transfer keys $T^i$, +bindings $B^i$ associated to $C$, and those coins denominations, +including the $T'$ for $C'$. + +We assumed both the exchange and Bob operated the refresh protocol +correctly, so now $c_s T'$ is the seed from which $C'$ was generated. +Alice rederives both $c_s$ and the blinding factor to unblind the +denomination key signature on $C'$. Alice finally asks the exchange +for the residual value on $C'$ and runs the linking protocol to +determine if it was refreshed too. +\end{proof} + +\begin{corollary} + Abusing the refresh protocol to transfer ownership has an + expected loss of $1 - \frac{1}{\kappa}$ of the transaction value. +\end{corollary} + + +\subsection{Privacy arguments} + +The {\em linking problem} for blind signature is, +if given coin creation transcripts and possibly fewer +coin deposit transcripts for coins from the creation transcripts, +then produce a corresponding creation and deposit transcript. + +We say an adversary {\em links} coins if it has a non-negligible +advantage in solving the linking problem, when given the private +keys of the exchange. + +In Taler, there are two forms of coin creation transcripts, +withdrawal and refresh. + +\begin{lemma} +If there are no refresh operations, any adversary with an +advantage in linking coins is polynomially equivalent to an +adversary with the same advantage in recognizing blinding factors. +\end{lemma} + +\begin{proof} +Let $n$ denote the RSA modulus of the denomination key. +Also let $d$ and $e$ denote the private and public exponents, respectively. +In effect, coin withdrawal transcripts consist of numbers +$b m^d \mod n$ where $m$ is the FDH of the coin's public key +and $b$ is the blinding factor, while coin deposits transcripts +consist of only $m^d \mod n$. + +Of course, if the adversary can link coins then they can compute +the blinding factors as $b m^d / m^d \mod n$. Conversely, if the +adversary can recognize blinding factors then they link coins after +first computing $b_{i,j} = b_i m_i^d / m_j^d \mod n$ for all $i,j$. +\end{proof} + +We now know the following because Taler uses SHA512 adopted to be + a FDH to be the blinding factor. + +\begin{corollary} +Assuming no refresh operation, +any adversary with an advantage for linking Taler coins gives +rise to an adversary with an advantage for recognizing SHA512 output. +\end{corollary} + +We will now consider the impact of the refresh operation. For the +sake of the argument, we will first consider an earlier +encryption-based version of the protocol in which refresh operated +consisted of $\kappa$ normal coin withdrawals where the commitment +consisted of the blinding factors and private keys of the fresh coins +encrypted using the secret $t^{(i)} C_s$ where $C_s = c_s G$ of the +dirty coin $C$ being refreshed and $T^{(i)} = t^{(i)} G$ is the +transfer key.\footnote{We abandoned that version as it required + slightly more storage space and the additional encryption + primitive.} + +\begin{proposition} +Assuming the encryption used is semantically (IND-CPA) secure, and +that the independence of $c_s$, $t$, and the new coins' key materials, +then any probabilistic polynomial time (PPT) adversary with an +advantage for linking Taler coins gives rise to an adversary with + an advantage for recognizing SHA512 output. +\end{proposition} + +In fact, the exchange can launch an chosen cphertext attack against +the customer by providing different ciphertexts. Yet, the resulting +plaintext is implicitly authenticated becuase after decryption +the customer unblinds and checks the signature by the denomination +key. + +If this check does not check out, then the wallet must abandon +this coin and report the exchange's fraudulent activity. + +% TODO: Is independence here too strong? + +We may now remove the encrpytion by appealing to the random oracle +model~\cite{BR-RandomOracles}. + +\begin{lemma}[\cite{??}] +Consider a protocol that commits to random data by encrypting it +using a secret derived from a Diffe-Hellman key exchange. +In the random oracle model, we may replace this encryption with +a hash function which derives the random data by applying hash +functions to the same secret. +\end{lemma} +% TODO: IND-CPA again? Anything else? + +\begin{proof} +We work with the usual instantiation of the random oracle model as +returning a random string and placing it into a database for future +queries. + +We take the random number generator that drives one random oracle $R$ +to be the random number generator used to produce the random data +that we encrypt in the old encryption based version of Taler. +Now our random oracle scheme with $R$ gives the same result as our +scheme that encrypts random data, so the encryption becomes +superfluous and may be omitted. +\end{proof} + +We may now conclude that Taler remains unlinkable even with the refresh protocol. + +\begin{theorem} +In the random oracle model, any PPT adversary with an advantage +in linking Taler coins has an advantage in breaking elliptic curve +Diffie-Hellman key exchange on Curve25519. +\end{theorem} + +We do not distinguish between information known by the exchange and +information known by the merchant in the above. As a result, this +proves that out linking protocol \S\ref{subsec:linking} does not +degrade privacy. We note that the exchange could lie in the linking +protocol about the transfer public key to generate coins that it can +link (at a financial loss to the exchange that it would have to square +with its auditor). However, in the normal course of payments the link +protocol is never used. + +\subsection{Exculpability arguments} + +\begin{lemma} +The exchange can detect and prove double-spending. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +Merchants and customers can verify double-spending proofs. +\end{lemma} + +\begin{proof} +\end{proof} + + +\begin{lemma} +Customers can either obtain proof-of-payment or their money back. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +If a customer paid for a contract, they can prove it. +\end{lemma} + +\begin{proof} +\end{proof} + +\begin{lemma} +The merchant can issue refunds, and only to the original customer. +\end{lemma} + +\begin{proof} +\end{proof} + + + +\begin{theorem} + The protocol prevents double-spending and provides exculpability. +\end{theorem} + + + +\section{Implementation} \section{Experimental results} -%\begin{figure}[b!] -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{bw_in.png} -% \caption{Incoming traffic at the exchange, in bytes per 5 minutes.} -% \label{fig:in} -% \end{subfigure}\hfill -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{bw_out.png} -% \caption{Outgoing traffic from the exchange, in bytes per 5 minutes.} -% \label{fig:out} -% \end{subfigure} -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{db_read.png} -% \caption{DB read operations per second.} -% \label{fig:read} -% \end{subfigure} -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{db_write.png} -% \caption{DB write operations per second.} -% \label{fig:write} -% \end{subfigure} -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{cpu_balance.png} -% \caption{CPU credit balance. Hitting a balance of 0 shows the CPU is -% the limiting factor.} -% \label{fig:cpu} -% \end{subfigure}\hfill -% \begin{subfigure}{0.45\columnwidth} -% \includegraphics[width=\columnwidth]{cpu_usage.png} -% \caption{CPU utilization. The t2.micro instance is allowed to use 10\% of -% one CPU.} -% \label{fig:usage} -% \end{subfigure} +\begin{figure}[b!] + \includegraphics[width=\columnwidth]{bw_in.png} + \caption{Incoming traffic at the exchange, in bytes per 5 minutes.} + \label{fig:in} +\end{figure}\hfill + \begin{figure}[b!] + \includegraphics[width=\columnwidth]{bw_out.png} + \caption{Outgoing traffic from the exchange, in bytes per 5 minutes.} + \label{fig:out} + \end{figure} + \begin{figure}[b!] + \includegraphics[width=\columnwidth]{db_read.png} + \caption{DB read operations per second.} + \label{fig:read} + \end{figure} + \begin{figure}[b!] + \includegraphics[width=\columnwidth]{db_write.png} + \caption{DB write operations per second.} + \label{fig:write} + \end{figure} + \begin{figure}[b!] + \includegraphics[width=\columnwidth]{cpu_balance.png} + \caption{CPU credit balance. Hitting a balance of 0 shows the CPU is + the limiting factor.} + \label{fig:cpu} + \end{figure} + \begin{figure}[b!] + \includegraphics[width=\columnwidth]{cpu_usage.png} + \caption{CPU utilization. The t2.micro instance is allowed to use 10\% of + one CPU.} + \label{fig:usage} + \end{figure} % \caption{Selected EC2 performance monitors for the experiment in the EC2 % (after several hours, once the system was ``warm'').} % \label{fig:ec2} @@ -1215,23 +1450,23 @@ FDH operations we used~\cite{rfc5869} with SHA-512 as XTR and SHA-256 for PRF as suggested in~\cite{rfc5869}. Using 16 concurrent clients performing withdraw, deposit and refresh operations we then pushed the t2.micro instance to the resource limit -%(Figure~\ref{fig:cpu}) +(Figure~\ref{fig:cpu}) from a network with $\approx$ 160 ms latency to the EC2 instance. At that point, the instance managed about 8 HTTP requests per second, which roughly corresponds to one full business transaction (as a full business transaction is expected to involve withdrawing and depositing several coins). The network traffic was modest at approximately 50 kbit/sec from the exchange -%(Figure~\ref{fig:out}) +(Figure~\ref{fig:out}) and 160 kbit/sec to the exchange. -%(Figure~\ref{fig:in}). +(Figure~\ref{fig:in}). At network latencies above 10 ms, the delay for executing a transaction is dominated by the network latency, as local processing virtually always takes less than 10 ms. Database transactions are dominated by writes% -%(Figure~\ref{fig:read} vs. Figure~\ref{fig:write}) -, as Taler mostly needs to log +(Figure~\ref{fig:read} vs. Figure~\ref{fig:write}), as +Taler mostly needs to log transactions and occasionally needs to read to guard against double-spending. Given a database capacity of 2 TB---which should suffice for more than one year of full transaction logs---the @@ -1415,8 +1650,8 @@ data being persisted are represented in between $\langle\rangle$. \item[$H()$]{Hash function} \item[$p$]{Payment details of a merchant (i.e. wire transfer details for a bank transfer)} \item[$r$]{Random nonce} - \item[${\cal A}$]{Complete contract signed by the merchant} - \item[${\cal D}$]{Deposit permission, signing over a certain amount of coin to the merchant as payment and to signify acceptance of a particular contract} + \item[${\mathcal A}$]{Complete contract signed by the merchant} + \item[${\mathcal D}$]{Deposit permission, signing over a certain amount of coin to the merchant as payment and to signify acceptance of a particular contract} \item[$\kappa$]{Security parameter $\ge 3$} \item[$i$]{Index over cut-and-choose set, $i \in \{1,\ldots,\kappa\}$} \item[$\gamma$]{Selected index in cut-and-choose protocol, $\gamma \in \{1,\ldots,\kappa\}$} @@ -1436,7 +1671,7 @@ data being persisted are represented in between $\langle\rangle$. % \item[$E_{L^{(i)}}()$]{Symmetric encryption using key $L^{(i)}$} % \item[$E^{(i)}$]{$i$-th encryption of the private information $(c_s^{(i)}, b_i)$} % \item[$\vec{E}$]{Vector of $E^{(i)}$} - \item[$\cal{R}$]{Tuple of revealed vectors in cut-and-choose protocol, + \item[$\mathcal{R}$]{Tuple of revealed vectors in cut-and-choose protocol, where the vectors exclude the selected index $\gamma$} \item[$\overline{L^{(i)}}$]{Link secrets derived by the verifier from DH} \item[$\overline{B^{(i)}}$]{Blinded values derived by the verifier} @@ -1446,198 +1681,6 @@ data being persisted are represented in between $\langle\rangle$. \item[$\overline{C^{(i)}_p}$]{Public coin keys computed from $\overline{c_s^{(i)}}$ by the verifier} \end{description} -\newpage -\section{Taxability arguments} - -We assume the exchange operates honestly when discussing taxability. -We feel this assumption is warranted mostly because a Taler exchange -requires licenses to operate as a financial institution, which it -risks loosing if it knowingly facilitates tax evasion. -We also expect an auditor monitors the exchange similarly to how -government regulators monitor financial institutions. -In fact, our auditor software component gives the auditor read access -to the exchange's database, and carries out test operations anonymously, -which expands its power over conventional auditors. - -\begin{proposition} -Assuming the exchange operates the refresh protocol honestly, -a customer operating the refresh protocol dishonestly expects to -loose $1 - {1 \over \kappa}$ of the value of their coins. -\end{proposition} - -\begin{proof} -An honest exchange keeps any funds being refreshed if the reveal -phase is never carried out, does not match the commitment, or shows -an incorrect commitment. As a result, a customer dishonestly -refreshing a coin looses their money if they have more than one -dishonest commitment. If they make exactly one dishonest -commitment, they have a $1 \over \kappa$ chance of their -dishonest commitment being selected for the refresh. -\end{proof} - -We say a coin $C$ is {\em controlled} by a user if the user's wallet knows -its secret scalar $c_s$, the signature $S$ of the appropriate denomination -key on its public key $C_s$, and the residual value of the coin. - -We assume the wallet cannot loose knowledge of a particular coin's -key material, and the wallet can query the exchange to learn the -residual value of the coin, so a wallet cannot loose control of -a coin. A wallet may loose the monetary value associated with a coin -if another wallet spends it however. - -We say a user Alice {\em owns} a coin $C$ if only Alice's wallets can -gain control of $C$ using standard interactions with the exchange. -In other words, ownership means exclusive control not just in the -present, but in the future even if another user interacts with the -exchange. - -\begin{theorem} -Let $C$ denote a coin controlled by users Alice and Bob. -Suppose Bob creates a coin $C'$ from $C$ following the refresh protocol. -Assuming the exchange and Bob operated the refresh protocol correctly, -and that the exchange continues to operate the linking protocol -(\S\ref{subsec:linking}) correctly, -then Alice can gain control of $C'$ using the linking protocol. -\end{theorem} - -\begin{proof} -Alice may run the linking protocol to obtain all transfer keys $T^i$, -bindings $B^i$ associated to $C$, and those coins denominations, -including the $T'$ for $C'$. - -We assumed both the exchange and Bob operated the refresh protocol -correctly, so now $c_s T'$ is the seed from which $C'$ was generated. -Alice rederives both $c_s$ and the blinding factor to unblind the -denomination key signature on $C'$. Alice finally asks the exchange -for the residual value on $C'$ and runs the linking protocol to -determine if it was refreshed too. -\end{proof} - -\begin{corollary} - Abusing the refresh protocol to transfer ownership has an - expected loss of $1 - \frac{1}{\kappa}$ of the transaction value. -\end{corollary} - - -\section{Privacy arguments} - -The {\em linking problem} for blind signature is, -if given coin creation transcripts and possibly fewer -coin deposit transcripts for coins from the creation transcripts, -then produce a corresponding creation and deposit transcript. - -We say an adversary {\em links} coins if it has a non-negligible -advantage in solving the linking problem, when given the private -keys of the exchange. - -In Taler, there are two forms of coin creation transcripts, -withdrawal and refresh. - -\begin{lemma} -If there are no refresh operations, any adversary with an -advantage in linking coins is polynomially equivalent to an -adversary with the same advantage in recognizing blinding factors. -\end{lemma} - -\begin{proof} -Let $n$ denote the RSA modulus of the denomination key. -Also let $d$ and $e$ denote the private and public exponents, respectively. -In effect, coin withdrawal transcripts consist of numbers -$b m^d \mod n$ where $m$ is the FDH of the coin's public key -and $b$ is the blinding factor, while coin deposits transcripts -consist of only $m^d \mod n$. - -Of course, if the adversary can link coins then they can compute -the blinding factors as $b m^d / m^d \mod n$. Conversely, if the -adversary can recognize blinding factors then they link coins after -first computing $b_{i,j} = b_i m_i^d / m_j^d \mod n$ for all $i,j$. -\end{proof} - -We now know the following because Taler uses SHA512 adopted to be - a FDH to be the blinding factor. - -\begin{corollary} -Assuming no refresh operation, -any adversary with an advantage for linking Taler coins gives -rise to an adversary with an advantage for recognizing SHA512 output. -\end{corollary} - -We will now consider the impact of the refresh operation. For the -sake of the argument, we will first consider an earlier -encryption-based version of the protocol in which refresh operated -consisted of $\kappa$ normal coin withdrawals where the commitment -consisted of the blinding factors and private keys of the fresh coins -encrypted using the secret $t^{(i)} C_s$ where $C_s = c_s G$ of the -dirty coin $C$ being refreshed and $T^{(i)} = t^{(i)} G$ is the -transfer key.\footnote{We abandoned that version as it required - slightly more storage space and the additional encryption - primitive.} - -\begin{proposition} -Assuming the encryption used is semantically (IND-CPA) secure, and -that the independence of $c_s$, $t$, and the new coins' key materials, -then any probabilistic polynomial time (PPT) adversary with an -advantage for linking Taler coins gives rise to an adversary with - an advantage for recognizing SHA512 output. -\end{proposition} - -In fact, the exchange can launch an chosen cphertext attack against -the customer by providing different ciphertexts. Yet, the resulting -plaintext is implicitly authenticated becuase after decryption -the customer unblinds and checks the signature by the denomination -key. - -If this check does not check out, then the wallet must abandon -this coin and report the exchange's fraudulent activity. - -% TODO: Is independence here too strong? - -We may now remove the encrpytion by appealing to the random oracle -model~\cite{BR-RandomOracles}. - -\begin{lemma}[\cite{??}] -Consider a protocol that commits to random data by encrypting it -using a secret derived from a Diffe-Hellman key exchange. -In the random oracle model, we may replace this encryption with -a hash function which derives the random data by applying hash -functions to the same secret. -\end{lemma} -% TODO: IND-CPA again? Anything else? - -\begin{proof} -We work with the usual instantiation of the random oracle model as -returning a random string and placing it into a database for future -queries. - -We take the random number generator that drives one random oracle $R$ -to be the random number generator used to produce the random data -that we encrypt in the old encryption based version of Taler. -Now our random oracle scheme with $R$ gives the same result as our -scheme that encrypts random data, so the encryption becomes -superfluous and may be omitted. -\end{proof} - -We may now conclude that Taler remains unlinkable even with the refresh protocol. - -\begin{theorem} -In the random oracle model, any PPT adversary with an advantage -in linking Taler coins has an advantage in breaking elliptic curve -Diffie-Hellman key exchange on Curve25519. -\end{theorem} - -We do not distinguish between information known by the exchange and -information known by the merchant in the above. As a result, this -proves that out linking protocol \S\ref{subsec:linking} does not -degrade privacy. We note that the exchange could lie in the linking -protocol about the transfer public key to generate coins that it can -link (at a financial loss to the exchange that it would have to square -with its auditor). However, in the normal course of payments the link -protocol is never used. Furthermore, if a customer needs to recover -control over a coin using the linking protocol, they can use the -refresh protocol on the result to again obtain an unlinkable coin. - - - \end{document} @@ -1956,4 +1999,3 @@ provides a payment system with the following key properties: The payment system handles both small and large payments in an efficient and reliable manner. \end{description} - |