Hash Functions

A background and overview and background on various hash functions related to and imperative to zero knowledge cryptography

What are hash functions?

Hash functions are functions that take in a an arbitrary input, often called a pre-image, and output a variable or fixed length string called a digest. They are often referred to as one way functions because while it is trivial to convert the pre-image to the digest it is computationally infeasible to reverse this process. This makes hashing functions ideal for data verification and storing sensitive data like passwords in a secure manner. Hash functions play an imperative role in zero knowledge cryptography

Pre-image (top) is converted to digest (bottom)

SHA-3 / Keccak-256

Secure hashing algorithm 3 (SHA-3) is a versatile function used for many cryptographic tools like digital signatures, MAC codes, and key derivation functions. SHA-3 is a subset of a cryptographic family called keccak. The Ethereum blockchain uses keccak-256 where the 256 bits stands for a 256 bit digest. While versatile this family of hasing functions falls short of the requirements necessary for SNARK applications. For zero knowledge cryptography entire new functions had to be implemented.

MiMC / MiMC Sponge

MiMC is a block cipher and hash function that came into existence in 2016. It was the first widely popular ZK friendly hashing function. It was inspired by a precursor called LowMC. Providing low multiplicative complexity, it is SNARK friendly and enables quick and efficient proving time. Many of the popular ZK libraries out there come with existing implementations of MiMC like gnark and circom. The original MiMC implementation has inspired many attempted improvements like GMiMC as well as spawning a new type of ZK friendly hashing function called Poseidon.

Poseidon

Poseidon is a low multiplicative complexity hash function that is based on a design strategy called Hades. It applies rounds on non-linear transformations to the input and rounds applying transformations to part of the input. The end result is decreased symmetry between the pre-image and digest to ensure it is exceedingly difficult to calculate. It is advantageous over MiMC by allowing for variable length hashes.

Pedersen Commitments

Commitments play a key role in zero knowledge cryptography. Commitments allow a user to choose a certain value to apply to a problem. While the value is known to them, it is not known to anyone else until the committee chooses to reveal a value. The value is chosen in a "commit phase" and then verified when made transparent in the aptly named reveal phase.