Paper 2022/1487

An efficient verifiable state for zk-EVM and beyond from the Anemoi hash function

Jianwei Liu, Discreet Labs
Harshad Patil, Discreet Labs
Akhil Sai Peddireddy, Discreet Labs
Kevin Singh, Discreet Labs
Haifeng Sun, Discreet Labs
Huachuang Sun, Discreet Labs
Weikeng Chen, Discreet Labs
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 mode of operation, 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 would often 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

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
SNARK-friendly hash function Zerocash authentication zk-SNARK
Contact author(s)
crypto @ findora org
History
2022-11-04: last of 4 revisions
2022-10-29: received
See all versions
Short URL
https://ia.cr/2022/1487
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1487,
      author = {Jianwei Liu and Harshad Patil and Akhil Sai Peddireddy and Kevin Singh and Haifeng Sun and Huachuang Sun and Weikeng Chen},
      title = {An efficient verifiable state for zk-EVM and beyond from the Anemoi hash function},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1487},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1487}},
      url = {https://eprint.iacr.org/2022/1487}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.