# Review on Monolith Hash Function

Assessing hash functions significantly slows down many SNARK proving systems. Although it is feasible to employ standard hash functions like SHA-2 or SHA-3 families, relying on these conventional hash functions typically leads to fast calculation but unfortunately very costly proof creation. Zero-knowledge (ZK) proofs are cryptographic mechanisms that allow one party to prove to another party that they possess certain information without revealing the content of that information. In the context of blockchain, while there may not be private data to hide, they are still highly relevant due to their significant contributions to improving scalability. These proofs rely on hash functions that transform input data of any size into a fixed-length string of characters. While a variety of hash functions exist in real-life, ongoing research focuses on developing novel ones specifically modified for ZK proofs. Hash functions that are arithmetization-oriented or circuit-friendly are specifically designed for computational integrity applications, with a focus on their efficient integration into the unique mathematical frameworks of zero-knowledge proofs, which is often referred to as "circuit-friendliness". Examples of such hash functions include Poseidon, MiMC/GMiMC, Friday, Rescue, Neptune, Anemoi, and Griffin. The Poseidon hash function has already been widely adopted in various ZK frameworks and projects. Its structure is optimized for efficient data processing and seamless integration within ZK proof systems, making it a benchmark for other hash functions in the ZK space.

# Lookup based Hash Functions

Recent developments in lookup-based primitives, such as Reinforced Concrete and Monolith, enable efficient evaluation of functions like f(x) = y within a circuit, provided that x and y have a limited range of distinct values (for instance, up to 256 values is acceptable). Introduced in 2021, Reinforced Concrete was the earliest hash function to adopt this methodology, quickly becoming the fastest option for a specific proving system. However, its use was not efficient in other types of proving systems. This limitation was addressed by the Tip5 hash function which enhanced performance in proving systems where Reinforced Concrete was previously ineffective. In this type of hash function, the function f can be effectively represented as a compact lookup table, wherein each distinct input value corresponds to a predefined output or result. In software, this mechanism can be implemented efficiently through memory access to various addresses.

# Monolith

Monolith works well in both regular software and ZK proofs. They can be used in two ways: like a processor to handle data and turn it into a code, or like a compression tool to shrink data down. Monolith is the first of its kind to be just as fast as a common hash function called SHA3-256. In certain situations, it is even faster than another function called Poseidon. Monolith always takes the same amount of time to run no matter the data, making it resistant to side-channel attacks that try to leak information by measuring how long things take. In summary, Monolith has the following features:

* Lookup-based approach: Monolith leverages a technique called “lookup arguments” to speed up computations. This allows for efficient software implementation while maintaining circuit-friendliness.
* Fast software implementation: Monolith is faster than other circuit-friendly hash functions and even surpasses the popular SHA3 function in some cases.
* Constant-time implementation: Monolith avoids side-channel attacks, a security concern for some other hash functions.
* Circuit-friendly: Monolith is well-suited for implementation in ZK proofs due to its low degree and efficient arithmetizations approaches.

## Construction of Monolith

Monolith natively contains 31-bit and 64-bit prime fields in which arithmetic operations such as additions and multiplications are significantly efficient. More concretely,
Monolith relies on prime fields F_p, with two options for the variable p, specifically

$p_{Goldilocks} = 2^{64} – 2^{32} + 1$ and $p_{Mersenne} = 2^31 - 1$.

The permutation Monolith-64 is defined over $p_{Goldilocks}$ with the state consisting of t = 8 or t = 12 elements. The permutation Monolith-31 is defined over p_Mersenne with the state consisting of t = 16 or t = 24 elements. Monolith supports sponge modes and a 2-to-1 compression function which it takes t $\mathbb F_p$ elements as input and produces t/2 $\mathbb F_p$ elements as output. This compression function can be used in Merkle trees and has recently also been applied in similar constructions, including Anemoi Griffin, and Poseidon2.


The Monolith permutation is defined as

$Monolith(·) = R_R∘ · · · ∘R_2 ∘ R_1 ∘ Concrete(·)$

where $R$ is the number of rounds and $R_i$ over $\mathbb F_p^t$ are defined as

$R_i (·) = c^i + Concrete ∘ Bricks ∘ Bars(·),∀i ∈ {1,2,...,R}$.

where Concrete is a linear operation, Bars and Bricks are nonlinear operations over $F_p^t, c^1, . . ., c^(r-1) ∈ F_p^t$ are pseudo-random round constants, and $c^r = 0$. Note that a single Concrete operation is applied before the first round.

The Bars layer is defined as

$Bars(x_1,x_2,...,x_t)∶= Bar(x_1) || · · ·|| Bar(x_u )|┤| x_u+1 || · · · || x_t$

for a t-element state, where u ∈ {1,...,t} denotes the number of Bar applications in a single round.


# Performance Comparison

We conduct comparisons with Tip5, which has a set state size of t = 16, and with Tip4′, an enhanced version of Tip5 optimized for a state size of t = 12. Comparisons also include Reinforced Concrete, implemented with the scalar field of the BN254 curve, as well as with the SHA3-256 and SHA-256 algorithms.


In our analysis, we compared Monolith-31 against Poseidon and Poseidon2 using the Mersenne prime field with state sizes t = 16 and t = 24, encompassing both sponge and compression modes, as well as constant time implementations. Monolith-64 emerged as significantly faster than other arithmetization-oriented hash functions, with Poseidon2 trailing by a factor of 7.3 for t = 8. In the realm of lookup table-based designs, Tip4′ was outperformed by Monolith in compression mode by a factor of 1.9, and by 36 ns for the same state size of t = 12. Interestingly, the speed differential between arithmetization-friendly hash functions and conventional ones has narrowed, with SHA3-256 lagging behind Monolith-64 for t = 8 and only edging out by 21 ns in sponge mode for t = 12. For the 31-bit Mersenne prime field, Monolith-31 showcases robust speed at 210 ns for t = 16, outpacing Tip5 with the same state size in the larger 64-bit prime field. A performance dip for t = 24 in Monolith-31 is attributed to a 32×32 circular MDS matrix used in the Concrete layer, facilitating radix-2 FFT implementation. This performance challenge is not unique to Monolith-31, as other designs like Tip5 also depend on MDS matrices and face similar issues. Nonetheless, Monolith-31 remains quicker than its nearest rival, Poseidon2, by 300 ns for the same field and state size.

Monolith distinguishes itself from other lookup-based designs by not depending on lookup tables, and its architecture supports constant-time implementations without substantial performance detriment. The binary χ-like layer in Monolith is effectively executed through a vectorized approach, avoiding the need for explicit composition or decomposition. This contrasts with the added computational demand in Reinforced Concrete, Tip5, and Tip4′ due to their reliance on expanded lookup tables. Therefore, Monolith's transition to constant-time operations mainly involves accommodating constant-time arithmetic in the prime field.


Implementing a constant-time reduction causes a minor deceleration in our comparative analysis. Nevertheless, the achieved execution times remain notably quicker than the non-constant-time performances of other circuit-compatible hash functions like Poseidon, Griffin, and Tip4′, particularly for state sizes t = 8 and t = 12. Additionally, when operating in compression mode, a constant-time Monolith-64 still outpaces SHA3-256 for t = 8, despite the differing security margins between the two frameworks.

# References

1. Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger, and Roman Walch. 2022. Reinforced Concrete: A Fast Hash Function for Verifiable Computation. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22). Association for Computing Machinery, New York, NY, USA, 1323–1335. https://doi.org/10.1145/3548606.3560686
1. Grassi, L., Khovratovich, D., L¨uftenegger, R., Rechberger, C., Schofnegger, M., Walch, R.: Hash functions monolith for zk applications: May the speed of sha-3 be with you. Cryptology ePrint Archive, Paper 2023/1025 (2023), https://eprint.iacr.org/2023/1025
1. Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: A new hash function for zero-knowledge proof systems. Cryptology ePrint Archive, Paper 2019/458 (2019), https://eprint. iacr.org/2019/458, https://eprint.iacr.org/2019/458
1. Grassi, L., Khovratovich, D., Schofnegger, M.: Poseidon2: A faster version of the poseidon hash function. Cryptology ePrint Archive, Paper 2023/323 (2023), https://eprint.iacr.org/2023/323
1. Alan Szepieniec, Alexander Lemmens, Jan Ferdinand Sauer, Bobbin Threadbare, and Al-Kindi. The Tip5 Hash Function for Recursive STARKs. Cryptology ePrint Archive, Paper 2023/107. https: //eprint.iacr.org/2023/107. 2023 (cit. on pp. 3, 5, 17, 26).
1. Robin Salen. Two additional instantiations from the Tip5 hash function construction. https://toposware.com/paper_tip5.pdf. 2023 (cit. on p. 26).