chap03-sec02.tex

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

\section{Instantiating $\mkhash$}\label{instantiation:mkhash}

In this section we describe the instantiation of $\mkhash$ with a compression function based on \mimc{}~\cite{albrecht2016mimc}. We firstly show how the compression function is constructed, and prove that this instantiation complies with the security requirements mentioned in~\cref{zeth-protocol:sec-req}

\subsection{\mimc{} Encryption}\label{instantiation:mkhash:mimc-encryption}

\mimc{} is a block cipher with a simple design, consisting of a number of rounds (denoted $\rounds$). During the $i$-th round, the message $\msg$ is mixed with the encryption key $\key{}$ and a randomly chosen constant $c[i]$, and a permutation function is applied to generate a new value of $\msg$. The permutation function consists of exponentiation with a carefully chosen exponent $\exponent{}$ (see~\cref{instantiation:mkhash:mimc-encryption:security}). Note that \rounds{} depends on the desired security level $\secpar$. We denote the encryption function by \mimcEnc{} and illustrate it in~\cref{instantiation:fig:mimc}.

\begin{figure*}[ht]
    \centering
    \procedure[linenumbering]{$\mimcEnc(\key, \msg, c, \exponent{}, \rounds)$}{
        \pcforeach\ i \in [\rounds]:\\
        \t \msg \gets {(\key\ \mathsf{OP}\ c[i]\ \mathsf{OP}\ \msg)}^\exponent{}\\
        \pcreturn (\msg\ \mathsf{OP}\ \key)
    }
    \caption{\mimc{} Encryption function.}\label{instantiation:fig:mimc}
\end{figure*}

\mimcEnc{} can be defined on both binary and prime fields, and as such the $\mathsf{OP}$ operation corresponds to either $\oplus$ or $+ \pmod{p}$~\cite{albrecht2016mimc, grassi2016mpc}.
For general prime $p$ (resp.~positive integer $n$), we denote by $\mimcPrime{p}$ (resp.~$\mimc{}_{2^n}$) the \mimcEnc{} function defined over \FFx{p} (resp.~\FFx{2^n}).

\subsubsection{Security parameters and analysis}\label{instantiation:mkhash:mimc-encryption:security}

In this document, we only consider \mimc{} defined over prime fields (in particular, the field $\FFx{\rCURVE}$ over which \zksnark~operates).

Since block ciphers are usually defined over the product space of keys and messages, we consider the variables $c$, \rounds{} and \exponent{} as fixed. We thereby consider an instantiation of $\mimc{}$ with signature
\begin{align*}
    \mimcPrime{\rCURVE} &: \FFx{\rCURVE} \times \FFx{\rCURVE} \to \FFx{\rCURVE}
\end{align*}

In the sections below, and as in ~\cite{albrecht2016mimc}, we will consider exponents of the form $\exponent{} = 2^t-1$ and $\exponent{} = 2^t+1$ where $\gcd(\exponent{}, \rCURVE-1) = 1$. We note that the term cancellation happening with exponents of the form $\exponent{} = 2^t+1$ does not immediatelly translate to the context where $\mimc{}$ is carried out over prime fields of large odd characteristic. In fact, in the case of $\FFx{\rCURVE}$, where $\rCURVE > \binom{\exponent}{\lfloor \exponent / 2 \rfloor}$, polynomials $(x + y)^{\exponent}$ are not sparse.
This comes from the \emph{Binomial Theorem}
\[
  (x + y)^\exponent = \sum_{i = 0}^{\exponent} \binom{\exponent}{i} x^{i}y^{\exponent - i}
\]
and the observation that if $\binom{\exponent}{i} < \rCURVE$ then $\binom{\exponent}{i} \bmod \rCURVE = \binom{\exponent}{i}$, hence ensuring that all the polynomial coefficients are greater than $0$, and that the polynomial is dense.

To achieve a security of $\secpar$, we require that $\rounds \geq \secpar \log_{\exponent}(2)$.
Importantly, since we use $\mimc{}$ over prime fields $\FFx{\rCURVE}$ which are large (where $\rCURVE$ is the prime characteristic of the scalar field of an elliptic curve group, such that $\ceil{\log_2(\rCURVE)} > \secpar$\footnote{Longer elements are needed in Elliptic Curve Cryptography (\ecc) to resist algebraic attacks such as Number Field Sieve (\acrnfs)-based attacks on discrete logs~\cite{DBLP:journals/siamdm/Gordon93} for instance}), then, picking $\rounds = \left\lceil \frac{\log_2 \rCURVE}{\log_2 \exponent{}} \right\rceil > \secpar \log_{\exponent}(2)$ provides a margin of safety on the number of rounds selected to instantiate $\mimc{}$ with desired security level $\secpar$.

We refer to the $\mimc{}$ paper~\cite[Section 4.2 and 5.1]{albrecht2016mimc} and to~\cref{appendix:mimc-security} for more details on the security analysis and attacks on the scheme in the different settings. Note that $\mimcPrime{\rCURVE}$ does not suffer from \emph{inversion subfield attacks} as there are no proper subfields of $\FFx{\rCURVE}$.

\subsection{\mimc{}-based compression function}\label{instantiation:mkhash:mimc-compressionf}

There exist two main techniques to construct a hash function from a block-cipher (or permutation): sponge functions~\cite{bertoni2007sponge} and iterated compression functions~\cite{black2002black}.

A Merkle tree is a binary tree of values of fixed size, where the values in each ``layer'' are generated by hashing pairs of values from the previous ``layer''. That is, we require a compression function $\mkhash$, which we construct via the Miyaguchi-Preneel scheme. (Miyaguchi-Preneel is more secure~\cite[$f_5$ function]{black2002black} than the more flexible Davies-Meyer construct~\cite[Section 3]{gazzoni2006maelstrom}, but this flexibility is not required in our case).

\subsubsection{Miyaguchi-Preneel compression construct}

Miyaguchi-Preneel (MP)~\cite[$f_3$ function]{black2002black} is a general scheme for constructing compression functions from block ciphers (see~\cref{preliminaries:definitions:hashcomp}). Given a block cipher \Enc, the corresponding compression function by \fMP{} is given in~\cref{instantiation:fig:mp-constructions}. The original construction is defined over binary fields, however \zeth~operates over prime fields. Hence, in the general discussion here we replace the bitwise addition operator $\oplus$ by modular addition in $\FFx{\rCURVE}$ (see~\cite{mp-security-ethsnarks}).

We denote by \mimcMP{} the compression function defined by the application of the Miyaguchi-Preneel construct over \mimc{}. Similarly, for general prime $p$ we denote by $\mimcMPPrime{p}$ (see~\cref{instantiation:fig:mimc-mp-constructions}) the compression function defined by application of the Miyaguchi-Preneel construct over $\mimcPrime{p}$.

\begin{figure*}[ht]
    \begin{minipage}[t]{0.50\textwidth}
        \procedure[linenumbering]{$\fMP{} (\key, \msg)$}{
            res \gets \Enc_\key(\msg) \\
            \pcreturn (res + \msg + \key) \pmod{\rCURVE}
        }
        \caption{\MP{} construct in $\FFx{\rCURVE}$.}\label{instantiation:fig:mp-constructions}
    \end{minipage}%
    \begin{minipage}[t]{0.50\textwidth}
        \procedure[linenumbering]{$\mimcMPPrime{\rCURVE}(\key, \msg)$}{
            res \gets \mimcPrime{\rCURVE}(\key, \msg) \\
            \pcreturn (res + \key + \msg) \pmod{\rCURVE}
        }
    \caption{$\mimcMPPrime{\rCURVE}$ construction.}\label{instantiation:fig:mimc-mp-constructions}
    \end{minipage}%
\end{figure*}

\subsection{An efficient instantiation of \mimc{} primitives}\label{instantiation:mkhash:efficient-instance}

To select appropriate instances of $\mimcPrime{\rCURVE}$ and $\mimcMPPrime{\rCURVE}$, we consider the cost (in terms of gas consumption and prover efficiency). For given $\exponent{}$ and $\rounds{}$, the final definition of $\mimcMPPrime{\rCURVE}$ is given in \cref{instantiation:fig:mimcp-construction} and \cref{instantiation:fig:mimcp-mp-construction}.

\newcommand{\initRoundConstants}{\algostyle{InitRoundConstants}}

\begin{figure*}[ht]
    \begin{minipage}[t]{0.5\textwidth}
        \centering
        \procedure[linenumbering]{$\mimcPrime{\rCURVE}(\key, \msg)$}{
            c \gets \initRoundConstants() \\
            \pcforeach i \in [\rounds]:\\
            \t \msg \gets {(\key + c[i] + \msg)}^\exponent{} \pmod{\rCURVE}\\
            \pcreturn (\msg + \key) \pmod{\rCURVE}
        }
    \end{minipage}%
    \begin{minipage}[t]{0.5\textwidth}
        \centering
        \procedure{$\initRoundConstants()$}{
            iv \gets \keccak{256} (\text{``clearmatics\_mt\_seed''}) \\
            c[0] \gets 0 \\
            c[1] \gets \keccak{256} (iv) \\
            \pcforeach i \in \range{2}{\rounds}:\\
            \t  c[i] \gets \keccak{256} (c[i-1])\\
            \pcreturn c = (c[0], \ldots, c[\rounds-1])
        }
    \end{minipage}%
    \caption{$\mimcPrime{\rCURVE}$ full construction}\label{instantiation:fig:mimcp-construction}
\end{figure*}

\begin{figure*}[ht]
    \centering
    \begin{minipage}[t]{0.5\textwidth}
        \procedure{$\mimcMPPrime{\rCURVE}(\key, \msg)$}{
            \pcreturn \mimcPrime{\rCURVE}(\key, \msg) + \msg + \key \pmod{\rCURVE}
        }
    \caption{\mimcMPPrime{\rCURVE} full construction}\label{instantiation:fig:mimcp-mp-construction}
    \end{minipage}%
\end{figure*}

\begin{remark}
    Note that \keccak{256} is the $256$-bit digest instance of the \keccak{} family that won the NIST SHA-3 competition~\cite{keccak-submission}. It is supported by the \evm via an opcode (see~\cite[Appendix G]{wood2014ethereum}), making it convenient for use in smart contracts.
\end{remark}

\begin{remark}
    To increase the security of the $\mathsf{\mkhash}$, different round constants for each level of the Merkle tree could be used.
\end{remark}

We define $\mkhash$ to be $\mimcMPPrime{}$ over $\FFx{\rCURVE}$. Thereby, for input values $m_0$ and $m_1$, $\mkhash : \FFx{\rCURVE} \times \FFx{\rCURVE} \to \FFx{\rCURVE}$ is defined by
\begin{equation}\label{instantiation:eq:mkhash-instantiation}
    \mkhash(\msg_0, \msg_1) = \mimcMPPrime{\rCURVE}(m_0, m_1)
\end{equation}

\newcommand{\constraints}{\varstyle{constraints}}

For specific values of $\rCURVE$ (such as $\rBN$ for $\BNCurve$ or $\rBLS$ for $\BLSCurve$), it remains to select concrete values of $\exponent{}$ and rounds, where $\rounds = \lceil \frac{\log_2 \rCURVE}{\log_2 \exponent{}} \rceil$).  These values influence the number of constraints in the arithmetic circuit (see~\cref{zeth-protocol:statement} for details of the statement) and the gas cost of Merkle tree operations on the contract (see~\cref{zeth-protocol:process-tx} for details of the specific operations).

In the arithmetic circuit, an invocation of $\mimcMPPrime{}$ requires $\rounds \cdot \mults$ constraints, where $\mults$ is the number of multiplications required for exponentiation. For exponents of the form $\exponent = 2^t - 1$, we have $\mults = 2 \cdot t - 2$, (using the \emph{square-and-multiply} algorithm~\cite{menezes1996handbook}), and for $\exponent = 2^t + 1$ we have $mults = t + 1$. Thus we expect that exponents of the latter form are more optimal. The implementation in the contract performs a very similar set of arithmetic operations (exponentiation in the field through a series of multiplications and modulo reductions), and so the cost is dominated by the same number $\rounds \cdot \mults$ as for the circuit.  Hence, values of $\exponent$ and $\rounds$ that are optimal for the circuit will also result in gas-efficient implementations in the contract.

For several concrete values of $\exponent{}$, the number of $\rounds$ required to attain the desired security level, along with the number of constraints, are shown in~\cref{table:mimc-exp-analysis}.

\definecolor{Gray}{gray}{0.9}
\begin{table}
  \centering
    \begin{minipage}[t]{0.50\textwidth}
        \centering
        \begin{tabular}{r c c c c}
            \toprule
            \multirow{2}{*}{$\exponent{}$} & \multicolumn{2}{c}{\BNCurve} & \multicolumn{2}{c}{\BLSCurve} \\ [0.5ex]
            & $\rounds$ & $\constraints$ & $\rounds$ & $\constraints$ \\ [0.5ex]
            \midrule
            \rowcolor{Gray}
            5 & 110 & 331 & & \\
            7 & 91 & 365 & & \\
            \rowcolor{Gray}
            17 & 65 & 316 & 62 & 311 \\
            31 & 52 & 417 & 51 & 409 \\
            127 & 37 & 445 & 37 & 445 \\
            \rowcolor{Gray}
            257 & 32 & 289 & 32 & 289 \\
            511 & 29 & 465 & & \\
            2047 & 24 & 481 & 23 & 461 \\
            8191 & 20 & 481 & 20 & 481 \\
            32676 & 17 & 477 & & \\
            \rowcolor{Gray}
            65537 & 16 & 273 & 16 & 273 \\
            131071 & 15 & 481 & 15 & 481 \\
            524287 & 14 & 505 & 14 & 505 \\
            \rowcolor{Gray}
            1048577 & 13 & 274 & 13 & 274 \\
            2097151 & 13 & 521 & & \\
            \bottomrule
        \end{tabular}
    \end{minipage}%
    \caption{Arithmetic constraints required to represent \mimcMP{} as an R1CS program, for different exponents $\exponent{}$ and curves. Grey (resp.~white) lines represent exponents of shape $2^t + 1$ (resp.~$2^t - 1$). Missing entries where $\gcd(\exponent{},\rCURVE - 1) \neq 1$}\label{table:mimc-exp-analysis}
\end{table}

For the case of \BNCurve~we set $\exponent{} = 17$ with $\rounds{} = 65$, to achieve a $254$-bit security level. For \BLSCurve~we set $\exponent{} = 17$ with $\rounds{} = 62$, to achieve $253$-bit security. These values are chosen such that they satisfy the requirement that $\gcd(\exponent{},\rCURVE - 1) = 1$, and give a balance between the number of constraints in the arithmetic circuit and the gas cost of hashing on the contract.

\subsection{Security requirements satisfaction}\label{instantiation:mkhash:security}

After presenting the state of the art of MiMC cryptanalysis, we present the security proof of \mimcMPPrime{} collision resistance.

\subsubsection{Cryptanalysis of $\mimc{}$ block cipher and primitives}\label{instantiation:mkhash:security:cryptanalysis}

\mimc{}'s security is increasingly being analysed since the primitive has gained traction in zero-knowledge and cryptocurrency communities for its succinct algebraic constraint representation. As of today, we do not know of any attacks breaking \mimc{} on prime fields on full rounds.

The first attack on \mimc{} was an interpolation attack~\cite{li2019improved} which targets a reduced-round version for a scenario in which the attacker has only limited memory.
An attack on Feistel-based \mimc{}~\cite{bonnetain2019collisions} was discovered shortly after, by using generic properties of the used Feistel construction (instead of exploiting properties of the primitive itself).
Additionally,~\cite{albrecht2019algebraic} proposes an attack based on Gr\"{o}bner basis. The authors state that by introducing a new intermediate variable in each round, the resulting multivariate system of equations is a Gr\"{o}bner basis. As such, the first step of a Gr\"{o}bner basis attack can be obtained for free. However, the following steps of the attack are so computationally demanding that the attack becomes infeasible in practice.
A recent work~\cite{DBLP:conf/asiacrypt/Eichlseder0LORS20} targets \mimc{} on binary fields, and achieves a full-round break of the scheme. While, the attack presented does not apply to prime fields, the authors note that it ``can be generalized to include ciphers over $\FFx{p}$'', and that only the lack of efficient distinguishers over prime fields precludes this.
Another attack from Beyne et al~\cite{cryptoeprint:2020:188} uses a low complexity distinguisher against full \mimc{} permutation leading to a practical collision attack on reduced round sponge-based \mimc{} hash defined with security of 128 bits.

\subsubsection{Security proof of \mimcMPPrime{} collision resistance}\label{instantiation:mkhash:security:colres-proof}
We now prove that this compression scheme satisfies all the security requirements listed in~\cref{zeth-protocol:sec-req}. To do so, we first assume that the round constants are pseudo-random, i.e.~that $\keccak{256}$ is a \prf{}.

\begin{lemma}
	\keccak{256} is a $\prf$ with $\lambda=128$.
\end{lemma}

The security of \mimcMPPrime{} derives from a more general result, i.e.~from modelling \mimcPrime{} as an ideal cipher (see~\cref{preliminaries:def:ICM}). More specifically, we show a security result for the \MP{} construction on \FFx{\rCURVE} by proving that, in the Ideal Cipher Model, the collision resistance advantage of any adversary is bounded by $\frac{q(q+1)}{\rCURVE}$, where $q$ is the number of different queries that the attacker makes to the oracle. This means that, assuming a maximum $q$ number of possible encryption/decryption queries, parameter $\rCURVE$ can be chosen to make the advantage small as needed and $\fMP$ considered collision resistant. Similar result applies to the ${2^n}$ case.

The instance of \mimc{} we use is modelled as an ideal cipher defined on field elements, for this reason we consider a variant of the ICM model where the keys, inputs and outputs are field elements in $\FFx{\rCURVE}$ and the block cipher scheme, with key $\key$, correspond to a family of $\rCURVE$ independent random permutations $f_{\key}: \FFx{\rCURVE} \times \FFx{\rCURVE} \to \FFx{\rCURVE}$.

In the proof, without loss of generality, we assume the following conventions for an adversary \adv{}:
\begin{itemize}
    \item the adversary asks distinct queries: i.e.~if \adv{} asks a query $\oracleEnc(\key,\msg)$ and this returns $y$, then \adv{} does not ask a subsequent query of $\oracleEnc(\key,\msg)$ or $\oracleDec(\key,y)$, and inversely;
    \item the adversary necessarily obtained the candidate collision from the oracle. This property follows suite from modelling \mimc{} as an ideal cipher.
\end{itemize}

\begin{lemma}\label{lemma:colrescomp}
    Let \fMP{} be the \MP{} compression function built on an ideal block-cipher \Enc{} on \FFx{\rCURVE}, the probability for an adversary \adv{} to find a collision is not greater than $q(q+1)/\rCURVE$ where $q$ is a (positive) number of distinct oracle queries.
\end{lemma}

The following proof has been adapted from~\cite[Lemma 3.3]{black2002black}\footnote{It states the collision resistance of a set of compression functions $f_1,,\ldots,,f_{12}$, denoted as \emph{group-1 compression functions} and showed in~\cite[Figure 3]{black2002black}. As mentioned above, Miyaguchi-Preneel corresponds to $f_3$ of that group. Since the proof of~\cite[Lemma 3.3]{black2002black} shows collision resistance of $f_1$, we slightly modified it to work for $f_3$.}.

\begin{proof}
    Fix $h_0\in\FFx{\rCURVE}$. Let \adv{} be an adversary attacking the compression function \fMP{}.
    Assume that \adv{} asks the oracles \oracleEnc{} and \oracleDec{} a total of \emph{distinct} $q$ queries. Let us denote the result of the $q$ queries and output of the attacker (candidate collision) as $\left ( (\key_1, \msg_1, y_1), \ldots , (\key_q, \msg_q, y_q), \text{out} \right )$.
    If \adv{} is successful it means that it outputs $(\key, \msg)$, $(\key', \msg')$ such that either $(\key, \msg) \neq (\key', \msg')$ and $\fMP(\key, \msg) = \fMP(\key', \msg')$ or $\fMP(\key, \msg) = h_0$.
    By the definition of \fMP, we have that $\Enc_\key(\msg) + \msg + \key = \Enc_{\key'}(\msg') + \msg' + \key'$ for the first case, or $\Enc_\key(\msg) + \msg + \key = h_0$ for the second.
    So either there are distinct $r, s \in [1,\ldots, q]$ such that $(\key_r, \msg_r, y_r) = (\key, \msg, \Enc_\key(\msg))$ and $(\key_s,\msg_s, y_s) = (\key',\msg', \Enc_{\key'}(\msg'))$ and $\Enc_{\key_r}(\msg_r) + \msg_r + \key_r = \Enc_{\key_s}(\msg_s) + \msg_s + \key_s$ or else there is an $r \in [1,\ldots, q]\ \suchthat\ (\key_r, \msg_r, y_r) = (\key, \msg, h_0)$ and $\Enc_{\key_r}(\msg_r) + \msg_r + \key_r = h_0$. We show that this event is unlikely.

    In fact, for each $i \in [1,\ldots, q]$, let $C_i$ be the event that either $y_i + \msg_i + \key_i = h_0$ or does exist $j \in [1,\ldots, i-1]\ \suchthat\ y_i + \msg_i + \key_i = y_j + \msg_j + \key_j$. When carrying out the simulation $y_i$ or $\msg_i$ was randomly selected from a set of at least $\rCURVE - (i-1)$ elements, so $\prob{C_i}\leq i / (\rCURVE-i)$. This means that for the collision advantage of \adv{}, \advCollMP it holds that $\advCollMP \leq \prob{C_1 \lor \cdots \lor C_q} \leq \sum_{i=1}^{q} \prob{C_i}$. For $q \leq \frac{\rCURVE}{2}$ this probability is bounded by $l \cdot \frac{q(q+1)}{\rCURVE}$. However, we allow only a polynomial number of queries, thus for $q = \poly$ this probability becomes $\frac{\poly}{\rCURVE}$, where $\rCURVE \approx 2^\secpar$.
\end{proof}

\begin{notebox}
   \cref{lemma:colrescomp} is applicable to our case by the strong assumption of \mimcPrime{\rCURVE} being an ideal cipher. In other words, the proof does not take into account any structural weakness or knowledge that an attacker is aware of. Any such additional information could make~\cref{lemma:colrescomp} invalid, and consequently could be used to break the collision resistance.
\end{notebox}

\begin{remark}
    Note that from~\cref{lemma:colrescomp} follows that the collision resistance security of the \zeth{} Merkle tree is $\log_2(\rCURVE/2)$ (around $127$ bits for $\rCURVE = \rBN$ or $\rBLS$).
\end{remark}

\begin{notebox}
    $\mimc{}$ has \emph{not} received as much cryptanalytic scrutiny as other ``older'' and more established hash functions. This is important to note since, for these type of primitives which are not provably secure, the amount of attacks received by a scheme is a great indicator of its security and robustness.
    A natural alternative to $\mimc{}$ here consists in using Pedersen hash which is provably collision resistant under the discrete-logarithm assumption.
\end{notebox}