Paper 2023/1045

XHash: Efficient STARK-friendly Hash Function

Abstract

Zero-knowledge proofs are widely used in real-world applications for authentication, access control, blockchains, and cryptocurren- cies, to name a few. A core element in zero-knowledge proof systems is the underlying hash function, which plays a vital role in the effi- ciency of the proof system. While the traditional hash functions, such as SHA3 or BLAKE3 are efficient on CPU architectures, they perform poorly within zero-knowledge proof systems. This is pri- marily due to the requirement of these systems for hash functions that operate efficiently over finite fields of large prime order as well as binary fields. To address this challenge, a new paradigm called Arithmetization-Orientation has emerged. These designs are tai- lored to improve the efficiency of hashing within zero-knowledge proof systems while providing reliable security guarantees. In this work, we propose XHash, which is a high-performance hash function designed for ZK-STARKs and is inspired by the Mar- vellous design strategy. When using Algebraic Intermediate Repre- sentation, XHash outperforms Rescue and Poseidon as the most im- portant ZK-friendly hash functions for STARKs. Moreover, XHash has a competitive performance on CPU architectures with an av- erage speed of ≈ 3𝜇𝑠 for 2-to-1 hashing. Compared to RPO, which is the fastest hash function of the Marvellous family, XHash per- forms ≈ 2.5 times faster on CPU. From the security perspective, XHash inherits the security of the Marvellous design strategy, and we analyze its security against state-of-the-art algebraic attacks. Additionally, we propose a new type of security argument against algebraic attacks that relies on a single well-defined and reasonable conjecture of a novel type. Finally, we specify a standard version of XHash designed for Polygon Miden VM, with its AIR complexity being 504, compared to Rescue with an AIR complexity of 672, and Poseidon with an AIR complexity of 1176.

Note: Improve security arguments. Add a new coauthor to the paper.