Welcome to the resource topic for 2022/1487
Title:
An efficient verifiable state for zk-EVM and beyond from the Anemoi hash function
Authors: Jianwei Liu, Harshad Patil, Akhil Sai Peddireddy, Kevin Singh, Haifeng Sun, Huachuang Sun, Weikeng Chen
Abstract: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: GitHub - FindoraNetwork/noah: Noah is a library that provide tools to create and verify public transaction with confidential data.
ePrint: https://eprint.iacr.org/2022/1487
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .