SNARK-friendly one-way compression functions

Question

I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations:

1. SHA256-compression is highly inefficient for SNARKs
2. The Pedersen hash function is efficient, but has an upper input limit of 32 bytes and outputs 32 bytes
3. A Merkle-tree implementation requires a hash function that accepts an input 64 bytes (the 32-byte outputs of two hashes).

Hence I'm looking for a way to securely and efficiently combine two 32-byte values into one 32-byte value.

I'm considering the MiMC hash function for this purpose but it seems like overkill for this purpose; I am already hashing data using Pedersen. Perhaps MiMC with fewer rounds would work well, but perhaps there's a better way to do it.

Answer 1

If you just need one-wayness (and not e.g. collision-resistance), want a compression function, and have 64 bytes of inputs, then there is a chance that you are exactly in the regime where Goldreich's one-way function, with proper choices of parameters, is unbeatable.

Concretely:

• Pick once for all (and store) 256 uniformly random size-5 subsets of $[1,512]$. Denote them $(S_i)_{i \leq 256}$.
• Define the following compression function $f$: on input $x \in \{0,1\}^{512}$, compute each of the 256 bits $y_i$ of the output as $P(x[S_i])$, where $x[S_i]$ denotes the subset of five bits of $x$ indexed by $S_i$, and $P$ denotes the predicate:

$P : (x_1,x_2,x_3,x_4,x_5) \rightarrow x_1 \oplus x_2 \oplus x_3 \oplus x_4\cdot x_5$.

Goldreich's function was thoroughly studied in the last 20 years (see the introduction of my paper for an overview). It's security is still far from perfectly understood, but essentially, the security decreases strongly when you look for a very long output. When you actually want a compression function and have a 512-bit input, I believe it should guarantee a clearly sufficient level of security.

As a bonus, observe that this is a completely parallelizable function: all output bits can be computed in parallel.

(of course, there are several other alternatives with low number of multiplications, or small circuit depth, but I think the above looks like a very good choice).