% !TEX root = ../zeth-protocol-specification.tex

\chapter{Transaction non malleability}\label{appendix:trnm}

The transaction malleability problem for a \dapscheme~(\cref{preliminaries:dap}) is characterized by a game $\trnm$ involving a polynomial-time adversary \adv{} as described below.

\begin{definition}
Let \dapscheme~be a (candidate) Decentralized Anonymous Payment scheme.
\[
  \dapscheme = (\setup,\ \genadd,\ \sendtx,\ \verifytx,\ \receive)
\]
We say that \dapscheme~is $\trnm$ secure if, for every $\poly$-time adversary \adv~
\[
    \advantage{\trnm}{\dapscheme, \adv} < \negl,
\]
where $\advantage{\trnm}{\dapscheme ,\adv} = \prob{\trnm(\dapscheme, \adv, \secpar) = 1}$ is \adv’s advantage in the $\trnm$ experiment.
\end{definition}

Below, we adapt~\cite[Appendix C.2]{sasson2014zerocash} to our specific \dapscheme---\zeth.

We start by describing the $\trnm$ experiment.
Given a (candidate) \zeth~\dapscheme, adversary \adv, and security parameter \secpar, the (probabilistic) game $\trnm(\dapscheme, \adv, \secpar)$ consists of an interaction between \adv~and a challenger $\challenger$, terminating with a binary output by $\challenger$.

At the beginning of the game, $\challenger$ samples $\pparams \gets \setup(\secpar)$ and sends $\pparams$ to \adv. Next, $\challenger$ initializes a \dapscheme~oracle $\oracle{\dapscheme}$ with $\pparams$ and allows \adv~to issue queries to it~\cite[Appendix B]{zethpaper}.

At the end of the experiment, \adv~sends to $\challenger$ a $\mixer$ contract call transaction $\tx^*_\mix$, and $\challenger$ outputs 1 iff the following conditions hold. Letting $T$ be the set of transactions generated by $\oracle{\dapscheme}$ in response to $\sendtx$ queries, there exists $\tx_\mix \in T$ such that:
\begin{enumerate}
    \item $\tx_\mix$ was not inserted in \ledger~by \adv;
    \item $\tx^*_\mix.\data \neq \tx_\mix.\data$;
    \item $\verifytx(\pparams, \tx^*_\mix, \ledger') = 1$ where $\ledger'$ is the portion of the ledger $\ledger$ preceding $\tx_\mix$;
    \item a serial number revealed in $\tx^*_\mix$ is also revealed in $\tx_\mix$.
\end{enumerate}

\section{Transaction malleability attack on \zeth}

In this section we present the threat related to the transaction malleability attack on \zeth~and expose the solutions by \zerocash~\cite{sasson2014zerocash} and \zcash~\cite{zcashprotocol} that we adapted.

First, we start by assuming that none of the checks related to transaction malleability attack have been added in the protocol~\cref{chap:zeth-protocol}. As such, we assume that $\hsig$ and $\htags{}$ are not attributes of $\primInputDType$, $\pphi$ is not an attribute of $\auxInputDType$, and $\otssig$ and $\otsvk$ are not attributes of the $\mixInputDType$ data type anymore. As a consequence, all checks related to these attributes are removed from the protocol. Moreover, if $zn$ is an object of type $\zethNoteDType$, then $zn.\rrho$ is chosen at random. Finally, the $\npol$-relation used in \zeth, now denoted $\RELMAL$, becomes the following:

\begin{itemize}
    \item For each $i \in [\jsin]$:
    \begin{enumerate}
        \item $ \auxinputs.\jsins{i}.\znote.\apk = \blake{2s}{\taggedaddr \concat \pad{0}{\blakeCompLen}}$ \\ with $\taggedaddr$ defined in~\cref{instantiation:prf-comm-crh:prf}
        \item $\auxinputs.\jsins{i}.\nf{} = \blake{2s}{\taggednf \concat \auxinputs.\jsins{i}.\znote.\rho}$ \\ with $\taggednf$ defined in~\cref{instantiation:prf-comm-crh:prf}
        \item $\auxinputs.\jsins{i}.\cm{} = \blake{2s}{\auxinputs.\jsins{i}.\znote.\noter{} \concat \msg}$ \\ with $\msg = \auxinputs.\jsins{i}.\znote.\apk \concat \auxinputs.\jsins{i}.\znote.\rrho \concat \auxinputs.\jsins{i}.\znote.\notev$
        \item $(\auxinputs.\jsins{i}.\znote.\notev) \cdot (1 - e)  =  0$ is satisfied for the boolean value $e$ set such that if $\auxinputs.\jsins{i}.\znote.\notev > 0$ then $e = 1$.
        \item The Merkle root $\mkroot'$ obtained after checking the Merkle authentication path $\auxinputs.\jsins{i}.\mkpath$ of commitment $\auxinputs.\jsins{i}.\cm{}$, with $\mkhash{}$, is equal to $\priminputs.\mkroot$ if $e = 1$.
        \item $\priminputs.\nfs{i}$ \\ $= \indexedset{\pack{\slice{\auxinputs.\jsins{i}.\nf{}}{k \cdot \fieldBitCap}{(k+1) \cdot \fieldBitCap}}{\FFx{\rCURVE}}}{k \in [\floor{\prfNfOutLen/\fieldBitCap}]}$
    \end{enumerate}
    \item For each $j \in [\jsout]$:
    \begin{enumerate}
        \item $\priminputs.\cms{j} = \blake{2s}{\auxinputs.\znotes{j}.\noter{} \concat \msg}$ \\ with $\msg = \auxinputs.\znotes{j}.\apk \concat \auxinputs.\znotes{j}.\rrho \concat \auxinputs.\znotes{j}.\notev$
    \end{enumerate}
    \item $\priminputs.\resbits = \packResBits{\indexedset{\auxinputs.\jsins{i}.\nf{}}{i \in [\jsin]}, \auxinputs.\vin, \auxinputs.\vout}$
    \item Check that the ``\gls{joinsplit} is balanced'', i.e.~check that the \gls{joinsplit-eq} holds:
    \begin{align*}
        &\pack{\auxinputs.\vin}{\FFx{\rCURVE}} + \sum_{i \in [\jsin]} \pack{\auxinputs.\jsins{i}.\znote.\notev}{\FFx{\rCURVE}} \\
        & = \sum_{j \in [\jsout]} \pack{\auxinputs.\znotes{j}.\notev}{\FFx{\rCURVE}} + \pack{\auxinputs.\vout}{\FFx{\rCURVE}}
    \end{align*}
\end{itemize}

\subsection{The attack}

In order to win the game $\trnm$ on the weak \zeth~\dapscheme~above, an adversary $\adv$ intercepts a target transaction \zethTx~by passively listening to the network (remember that transactions are broadcasted to the \ethereum~network in order to be mined, see~\cref{preliminaries:ethereum:eth-tx:tx-life}), extracts the zk-proof and primary inputs from $\zethTx.\data$ and uses these extracted pieces of information in order to create a malicious transaction $\zethTx'$, where the ciphertexts are replaced by arbitrary data.
The adversary can then broadcast $\zethTx'$ to the network in order for it to be mined. If the malicious transaction gets mined before the legitimate one, the input notes become spent and the ciphertexts are undecryptable making the new notes unredeemable (by any \zeth~user!), since all attempts to decrypt the ciphertexts will fail (see~\cref{zeth-protocol:zeth-receive}).

\begin{figure}[H]
    \centering
        \procedure[linenumbering]{$\txmalgen(\sk_\ecdsa', \inp{\nonce}, \zethTx)$}{%
        p \gets \zethTx.\gasp + 1 \\
        l \gets \zethTx.\gasl + 1 \\
        \zdata' \gets \zethTx.\data \\
        \zdata'.\ciphers \sample \BB^{*} \\
        \rawTx \gets \{\nonce: \inp{\nonce}, \gasp: p, \gasl: l, \tto: \zethTx.\tto, \val: \zethTx.\val, \data: \zdata'\}; \\
        \sigma_\ecdsa \gets \ecdsasigscheme.\sig(\sk_{\ecdsa}', \keccak{256}(\rawTx)); \\
        \finalTx \gets \{ \rawTx, \sigv: \sigma_\ecdsa.\sigv', \sigr: \sigma_\ecdsa.\sigr', \sigs: \sigma_\ecdsa.\sigs' \}; \\
        \pcreturn\ \finalTx;
    }
    \caption{Transaction malleability attack function \txmalgen}\label{appendix:trnm:fig:txmalgen}
\end{figure}

As shown on~\cref{appendix:trnm:fig:txmalgen}, during the attack, the adversary extracts the proof and primary inputs from the honest transaction, and replaces the ciphertexts by some arbitrary information.
The attacker then formats this data into a transaction that calls the $\mix$ function of $\mixer$, and submits it to the network.
While the data fields ($\zethTx.\data$ and $\zethTx'.\data$) are different, the nullifiers revealed by both transactions are the same (i.e.~$\zethTx.\data.\zkproof = \zethTx'.\data.\zkproof$, and $\zethTx.\data.\priminputs = \zethTx'.\data.\priminputs$).
As a consequence, if the adversary makes sure that $\zethTx'$ satisfies all the checks of \ethVerifyTx{}~(\cref{preliminaries:ethereum:eth-tx:tx-validity}), he can ensure that $\zethVerifyTx(\zethTx')$ will return the same value as $\zethVerifyTx(\zethTx)$.
Furthermore, if $\zethTx'.\gasp > \zethTx.\gasp$, then the adversary maximizes his chances of having his transaction mined first~(\cref{preliminaries:ethereum:eth-tx:tx-life}), and so maximizes the chances for the malleability attack to be successful; leading to lost funds on \mixer.

\begin{remark}\label{appendix:trnm:resign-tx-attack}
  Note that, although not directly contained within the $\data$ field of a \mixer{} call transaction, the $\ethereum{}$ address $\eparty{S}.\addr$ of the transaction sender is also used by the \mixer{} call (this is either the calling contract's address, or the transaction signer's address recovered as described in~\cref{preliminaries:recovering-msg-sender}). In particular, the balance of this $\ethereum{}$ address is incremented by the value $\vout$ by successful \mix{} calls.
  If we again assume the absence of the malleability checks, an attacker could re-sign any $\mixer$ call transaction with a key under his control, rebroadcast it as described above, and (with some reasonable probability) become the recipient of any public output value $\vout$.
\end{remark}

\begin{remark}
  We note that the attack described above cannot be prevented by merely substituting a malleable $\groth$ zk-SNARK by a simulation-extractable one like e.g.~\cite{groth2017simulation}. This comes since the attack does not utilise malleability of the proof system, but malleability of data that are broadcasted along with the zk-proof.
\end{remark}

\section{Solutions to address the transaction malleability attack}

\subsection{\zerocash~solution}\label{appendix:trnm:ssec:zerocash-trnm}
The idea of the solution presented in~\cite{sasson2014zerocash} is to use a one-time \sufcma{} digital signature and bind its verification key with the zk-proof primary inputs to prevent an adversary from corrupting part of a transaction's data.

Specifically, to transact via \zeth, the user first samples a key pair (\sk, \vk) for a one-time signature scheme. He then computes the hash $\hsig = \crh(\vk)$, where \crh{} is a collision resistant hash function, see~\cite{sasson2014zerocash}, and derives a value $\htag{i} = \prfpk{\ask_{i}}{\hsig}$, for each input note (i.e.~$i \in [\jsin]$), which acts as a \mmac{} binding \hsig~to the address spending key of a note ($\ask_{i}$).

The user then generates the zk-proof with the additional statement that the values $\indexedset{\htag{i}}{i \in [\jsin]}$ are computed correctly. He finally uses \sk~to sign every value associated with the operation, thus obtaining a signature, which is included, along with the signature verification key \vk, in the transaction.
To verify a transaction on the $\dapscheme$, it is necessary to verify that
\begin{itemize}
  \item the primary inputs are correctly formatted,
  \item the Merkle root corresponds to one of the previous states of the Merkle tree,
  \item the nullifiers have not been declared in a previous transaction,
  \item the \hsig~is correctly computed from \vk,~and
  \item both the zk-proof and the one-time signature verifications pass successfully.
\end{itemize}

Now, an adversary trying to carry out the aforementioned attack has to either change the ciphertexts or the encryption key. Nevertheless, doing so should lead to the one-time signature verification to fail or should yield an attack that breaks the \ufcma~property of the one-time signature (as this corresponds to creating a forgery on a different message, not changing the signature). Thereby, the adversary also has to modify the signature, however he does not know the one-time signing key used by the creator of the targeted transaction. As such, the adversary needs to use another signing key pair, however this leads to the check verifying that \hsig~is correctly computed to fail. If the adversary attempts to change \hsig, the zk-proof verification fails as the $\npol$-statement has changed. Hence, any attempt to carry out a malleability attack results in the violation of at least one check in the verification of the transaction on the $\dapscheme$. The solution presented effectively solves the transaction-malleability attack initially described.

\begin{remark}
    The one-timeness property of the signature scheme was required in \zerocash~to retain anonymity. It also makes analysing non-adaptive adversary sufficient. As $\ethereum{}$ transaction senders need to pay the gas cost associated with their transactions, the senders are not anonymous. This said, making sure that \zeth~is designed with anonymity in mind is worth the effort in order to minimize information leakages and be ready if/when \ethereum~incorporates protocol changes that enable anonymous transactions.
\end{remark}

\subsection{\zcash's solution}\label{appendix:trnm:ssec:zcash-trnm}

In addition to the changes aforementioned, \zcash's solution~\cite{zcashprotocol} also consists of:
\begin{itemize}
    \item Redefining the variable \hsig~as,
    \[
        \hsig = \crh(\randomSeed, \indexedset{\nf{i}}{i \in [\jsin]}, \vk)
    \]
    for some random seed \randomSeed.
\item Defining a new random variable $\pphi$ and using it with \hsig, as key and input of a \prf~respectively, to compute the identifier of each output notes $\rho_j$ ($j \in [\jsout]$) and ensure their uniqueness (with overwhelming probability).
\end{itemize}
These changes were made to prevent the Faerie Gold attack~\cite[Section 8.4]{zcashprotocol}, as well as to prevent linkability: if \hsig~were repeated in two transactions, the circuit would leak, via $\indexedset{\htag{i}}{i \in [\jsin]}$, the fact that the input notes in both transactions were spent with the same $\ask_{i}$ (if that were the case).

More particularly, using the input notes' nullifiers to derive \hsig~ensures that \hsig~is unique with overwhelming probability for all \emph{accepted} transaction.
Furthermore, using \randomSeed~ensures the uniqueness of \hsig~for transactions \emph{in transit} (as before validation there may be several in transit transactions with the same set of nullifiers).

\subsection{Solution on \ethereum}\label{appendix:trnm:preliminaries:ethereum-trnm}

As described in the $\ethereum{}$ yellow paper~\cite[Appendix F]{ethyellowpaper}, $\ethereum{}$ transactions are \ecdsa~signed. Further, as described in~\cref{zeth-protocol:mix-inp}, the one-time signature used to sign the \mix{} data also signs the $\ethereum{}$ address used to sign the transaction. As such, any modification to the transaction object will result in a new transaction hash, and any attempt to sign the transaction with a different \ecdsa~key will be rejected by the \mixer{} contract (see~\cref{zeth-protocol:process-tx}). We thereby conclude that the one-time signature used to sign the transaction data does not need to be \sufcma, but \emph{only needs to achieve \ufcma}.

Specifically, carrying out any change on the one-time signature will change the \ethereum~transaction data and result in a failure to verify the \ecdsa~signature of the \ethereum~transaction. To obtain a new valid signature on this transaction, the adversary needs to break the \ufcma~property of the \ecdsa~signature scheme or use another \ecdsa~keypair to sign the transaction. In the last case, the one-time signature will no longer be valid.

Note that including the $\ethereum{}$ transaction sender in the data to be signed by the one-time signature scheme also addresses the possible attack described in~\cref{appendix:trnm:resign-tx-attack}. An attacker trying to resign the same $\ethereum{}$ transaction with a different key will cause \mixer{} to reject the transaction when the one-time signature is checked.

\begin{remark}
    We note that the transaction malleability issue can also be addressed in another way. In fact, one could use the \ecdsa~signatures on \ethereum~transactions to fix all inputs and ciphertexts, and then tie the sender of the \ethereum~transaction to the zk-snark by putting the sender address $\eparty{S}.\addr$ in $\hsig$. In other words, it is also possible to define $hsig$ as:
    \[
        \hsig = \crh(\indexedset{\nf{i}}{i \in [\jsin]}, \eparty{S}.\addr)
    \]
    As such, if an attacker extracts the ciphertexts of a \zethTx~transaction in order to craft another malicious transaction \zethTx', the key-pair used to sign \zethTx' differs from the one used to sign \zethTx, which changes the transaction sender address recovered on \mixer. As a consequence, the check on $\hsig$ would fail on the $\mixer$, invalidating the transaction, and preventing the attack.

    While such a solution would avoid the need to generate one-time signing keys and could avoid a signature check in the \mixer, it would also require every \zeth~user to have an $\ethereum{}$ account. Doing so, would be a major hindrance toward the design of mechanisms aiming to provide anonymity to \zeth~transactions initiators. In fact, the addressing scheme used in \zeth~along with the solution to the malleability introduced in \zcash~makes it possible to generate raw \zeth~transactions without having an $\ethereum{}$ account. These raw transactions could then be broadcasted -- to a set of $\ethereum{}$ user nodes -- on an anonymous p2p network, before being finalized and submitted to the $\ethereum{}$ network by $\ethereum{}$ users who would be rewarded according to an incentive structure. While such a protocol is outside of the scope of this document, it shows that defining $\hsig$ using the senders address alters the flexibility of \zeth; hence this solution has not been favoured.
\end{remark}
