International Association
for Cryptologic Research

In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions, i.e., EVM is a **state** machine. In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses. In this note we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive k-to-1 compression mode of operation, both by Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. We demonstrate that with $14$ gates ($\approx1$ gate per round in a 12-round Amenoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations often would require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK. Our implementation can be found in $\mathtt{noah}$, a library for modern privacy tokens: https://github.com/FindoraNetwork/noah