Poseidon: A New Hash Function for Zero-Knowledge Proof Systems

Authors: 

Lorenzo Grassi, Radboud University Nijmegen; Dmitry Khovratovich, Ethereum Foundation and Dusk Network; Christian Rechberger, IAIK, Graz University of Technology; Arnab Roy, University of Klagenfurt; Markus Schofnegger, IAIK, Graz University of Technology

Abstract: 

The area of practical computational integrity proof systems, like SNARKs, STARKs, Bulletproofs, is seeing a very dynamic development with several constructions having appeared recently with improved properties and relaxed setup requirements. Many use cases of such systems involve, often as their most expensive part, proving the knowledge of a preimage under a certain cryptographic hash function, which is expressed as a circuit over a large prime field. A notable example is a zero-knowledge proof of coin ownership in the Zcash cryptocurrency, where the inadequacy of the SHA-256 hash function for such a circuit caused a huge computational penalty.

In this paper, we present a modular framework and concrete instances of cryptographic hash functions which work natively with GF(p) objects. Our hash function Poseidon uses up to 8x fewer constraints per message bit than Pedersen Hash.

Our construction is not only expressed compactly as a circuit, but can also be tailored for various proof systems using specially crafted polynomials, thus bringing another boost in performance. We demonstrate this by implementing a 1-out-of-a-billion membership proof with Merkle trees in less than a second by using Bulletproofs.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {263850,
author = {Lorenzo Grassi and Dmitry Khovratovich and Christian Rechberger and Arnab Roy and Markus Schofnegger},
title = {Poseidon: A New Hash Function for {Zero-Knowledge} Proof Systems},
booktitle = {30th USENIX Security Symposium (USENIX Security 21)},
year = {2021},
isbn = {978-1-939133-24-3},
pages = {519--535},
url = {https://www.usenix.org/conference/usenixsecurity21/presentation/grassi},
publisher = {USENIX Association},
month = aug
}

Presentation Video