Hashing state machines

For hashing, the zkEVM utilizes two state machines: the Keccak state machine and the Poseidon state machine. The Keccak-256 hash function is used for seamless EVM compatibility, whereas Poseidon is best suited for the zkProver context because it is a STARK-friendly hash (SFH) function.

The sponge construction

By design, Keccak and Poseidon are both sponge constructions. A generic sponge construction is a simple iterated construction for building a function:

$$F: \mathbb{Z}^* \to \mathbb{Z}^l$$

with an input of variable-length and arbitrary output length based on a fixed-length permutation:

$$f: \mathbb{Z}^b \to \mathbb{Z}^b$$

operating on a fixed number $b$ of bits.

The array of $b$ bits that $f$ keeps transforming is called the state, and $b$ is called the width of the state.

The state array is split into two chunks, one with $r$ bits and the other with $c$ bits. The width $b = r + c$, where $r$ is called the bitrate (or simply rate) and $c$ is called the capacity.

Sponge construction phases

The elements that completely describe a single instance of a sponge construction are: the fixed-length permutation $f$, the padding rule pad, the bitrate value $r$, and the capacity $c$.

A schema of the sponge construction is shown in the below figure.

Initializing phase

The input string is either padded to reach the $r$-bit length (if it was shorter than $r$ bits) or split into $r$-bit long chunks, with the last one padded to reach the $r$-bit length (if it was longer than $r$ bits). A hash function-specific reversible padding rule is used.

The state of the hash function is initialized to a $b$-bit vector (or array) of zeros.

Absorbing phase

During this phase, the $r$-bit input blocks are XOR-ed sequentially with the first $r$ bits of the state, intermixed with permutation function $f$ applications. This process is repeated until all input blocks have been XOR-ed with the state.

Take note that the last $c$ bits, which correspond to the capacity value, do not absorb any external input.

Squeezing phase

The first $r$ bits of the state are returned as output blocks in this phase, intermixed with applications of the function $f$. The number of output blocks is entirely up to the user.

Keep in mind that the last $c$ bits, which correspond to the capacity value, are never output during this phase. Actually, if the output is longer than the specified length, it is truncated to the required size.