Monolith Hash¶
Warning
This doc is not verified
References:
- Monolith Paper
- Monolith Hash Presentation in ZK summit
- How to choose ZK-friendly hash
- Introduce Monolith
Overview¶
Monolith is a family of hash functions optimized for zero-knowledge protocols.
Monolith permutation comprises multiple round functions. A single round function is defined as illustrated below
One round is divided into:
- \(\text{Bricks}\): a non-linear layer constructed from a quadratic Feistel Type-3
- \(\text{Concrete}\): an affine layer achieved through multiplication with a circulant MDS matrix
- \(\text{Bars}\): a binary non-linear layer based on Kintsugi strategy, implementing the lookup-based behavior.
The components \(\text{Bricks}\) and \(\text{Concrete}\) are responsible for the security against statistical attacks, while \(\text{Bars}\) provides high security against algebraic attacks. Anticipating improvements, we set the number of rounds uniformly to 6.
Specification¶
Monolith uses prime fields \(\mathbb{F}_p\) with two options for \(p\), namely:
\(p_{\text{Goldilocks}} = 2^{64} - 2^{32} + 1\) and \(p_{\text{Mersenne}} = 2^{31} - 1\)
The parameters used for Monolith are shown in the table below:
| Name | \(p\) | Security | Round \(N\) | \(t\) (2-to-1) | Width \(t\) (Sponge) | # Bar \(u\) |
|---|---|---|---|---|---|---|
| \(\text{Monolith-64}\) | \(2^{64} - 2^{32} + 1\) | 128 | 6 | 8 | 12 | 4 |
| \(\text{Monolith-31}\) | \(2^{31} - 1\) | 128 | 6 | 16 | 24 | 8 |
Modes of Operation¶
Monolith supports sponge modes for slightly larger state size and a 2-to-1 compression function for smaller state size (e.g., for Merkle tree with fixed depth).
Permuatation Structure¶
The Monolith permutation is defined as:
where \(N\) is the number of rounds and \(R_i\) over \(\mathbb{F}_p^t\) are defined as
where \(c^{(i)}\) are pseudo-random round constants, excluding \(c^{(N)} = 0\).
Note
A single \(\text{Concrete}\) operation is applied before the first round.
Bars Layer¶
The \(\text{Bars}\) layers is defined as:
for a \(t\) - element state, where:
- \(u \in \lbrace 1, \ldots, t \rbrace\): number of \(\text{Bar}\) operations are applied in each round
- \(u\) such that: \(u \cdot \log_2 p \approx 256\), i.e., the nonlinear part occupies around 256 bits of the state.
Each \(\text{Bar}\) is defined as:
where \(C\), \(S\), and \(D\) are the operations defined in kintsugi strategy.
Note
You should read the kintsugi strategy before proceeding to the section below to fully understand the underlying mathematics.
In the following, we describe them individually for \(\text{Monolith-64}\) and \(\text{Monolith-31}\) with parameters taken from the table above corresponding to each type.
\(\text{Bars}\) For \(\text{Monolith-64}\)¶
For \(D\) operation, we use a decomposition into 8-bit values such that:
The composition \(C\) is the inverse operation of the decomposition \(D\).
For \(S\) operation, we set \(s=8\), then all \(S_i\) over \(\mathbb{F}^8_2\) are defined as:
where \(\lll\) is a circular shift (we interpret an integer as a big-endian 8-bit string) and \(\bar{y}\) is the bitwise negation.
\(\text{Bars}\) For \(\text{Monolith-31}\)¶
The decomposition \(D\) is given by:
where \(x'_4 \in \mathbb{Z}^7_2\) and \(x'_3, x'_2, x'_1 \in \mathbb{Z}^8_2\).
The composition \(C\) is the inverse of \(D\).
For \(S\) operation, we set \(s=4\) using \(\lbrace 8, 7 \rbrace\) - bit lookup tables.
Then for \(y \in \mathbb{F}_2^8\) and \(y' \in \mathbb{F}_2^7\), the S- boxes are defined as:
and
Bricks¶
The component \(\text{Bricks}\) is defined as:
\(\text{Bricks}\) is selected to minimize multiplications by using the square map \(x \mapsto x^2\), reducing computational overhead and requiring only degree-2 constraints, a significant advantage over competitors like Poseidon, Rescue, and Tip5.
Concrete Layer¶
The \(\text{Concrete}\) layer is defined as:
where \(M \in \mathbb{F}^{t \times t}_p\) is an MDS matrix.
For \(\text{Monolith-64}\):
- For \(t=8\) then \(M = circ(23, 8, 13, 10, 7, 6, 21, 8)\)
- For \(t=12\) then \(M = circ(7, 23, 8, 26, 13, 10, 9, 7, 6, 22, 21, 8)\).
These matrices have the unique advantage of having small elements in the time and frequecy domain, allowing for especially fast native performance.
For \(\text{Monolith-31}\):
- For \(t=16\), \(M\) is the \(16 \times 16\) matrix from Tip5, i.e.,
- For \(t=24\), \(M\) is a \(24 \times 24\) submatrix of the defined \(32 \times 32\) circulant MDS matrix:
Application¶
You should use Monolith if ZK proof system:
- Supports lookup argument
- Operates natively with a small prime field.
Performance¶
In the following figure, we have the analysis of Monolith’s plain performance
Monolith is significantly faster than other ZK-friendly hash functions, especially \(\text{Monolith-64}\) in compression mode.
In the figure below, Monolith’s circuit efficiency is evident due to its native degree of only 2, allowing various trade-offs in circuit design.
Implementation¶
Here are some implementations of this hash:
Conclusion¶
Therefore, here are some properties that make Monolith hash as fast as SHA-3 and the fastest ZK-friendly hash
- Improve the S-box function that is defined by:
- Splitting a field element into smaller bit arrays.
- Then applied Daemen’s χ function and similar ones into these arrays, which can be parallelized with fast vector instructions and implemented as lookup table in circuits.
- Finally, the outputs are reassembled into a field element without overflow or collision, asserting minimal circuit overhead.
- Using a Feistel Type-3 function together with an MDS layer:
- Use faster squaring operations (i.e., \(x^2\)) instead of more expensive (as \(d\) must be coprime with \(p - 1\)) power function over \(\mathbb{F}_p\)