Paper 2023/1025

Monolith: Circuit-Friendly Hash Functions with New Nonlinear Layers for Fast and Constant-Time Implementations

Lorenzo Grassi, Ponos Technology (Switzerland), Ruhr University Bochum (Germany)
Dmitry Khovratovich, Ethereum Foundation (Luxembourg), ABDK Consulting (Estonia)
Reinhard Lüftenegger, Graz University of Technology (Austria)
Christian Rechberger, Graz University of Technology (Austria)
Markus Schofnegger, Horizen Labs (United States)
Roman Walch, Graz University of Technology (Austria), TACEO (Austria)

Hash functions are a crucial component in incrementally verifiable computation (IVC) protocols and applications. Among those, recursive SNARKs and folding schemes require hash functions to be both fast in native CPU computations and compact in algebraic descriptions (constraints). However, neither SHA-2/3 nor newer algebraic constructions, such as Poseidon, achieve both requirements. In this work we overcome this problem in several steps. First, for certain prime field domains we propose a new design strategy called Kintsugi, which explains how to construct nonlinear layers of high algebraic degree which allow fast native implementations and at the same time also an efficient circuit description for zero-knowledge applications. Then we suggest another layer, based on the Feistel Type-3 scheme, and prove wide trail bounds for its combination with an MDS matrix. We propose a new permutation design named Monolith to be used as a sponge or compression function. It is the first arithmetization-oriented function with a native performance comparable to SHA3-256. At the same time, it outperforms Poseidon in a circuit using the Merkle tree prover in the Plonky2 framework. Contrary to previously proposed designs, Monolith also allows for efficient constant-time native implementations which mitigates the risk of side-channel attacks

Note: The updated version is a major rewrite improving the clarity of the paper. However, the Monolith construction, its specification and instances were not changed.

Available format(s)
Secret-key cryptography
Publication info
Hash FunctionsMonolithZero Knowledge
Contact author(s)
lorenzo grassi @ ruhr-uni-bochum de
khovratovich @ gmail com
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ tugraz at
markus schofnegger @ gmail com
walchroman @ gmail com
2024-02-14: last of 2 revisions
2023-07-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lorenzo Grassi and Dmitry Khovratovich and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger and Roman Walch},
      title = {Monolith: Circuit-Friendly Hash Functions with New Nonlinear Layers for Fast and Constant-Time Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1025},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.