The Hashing State Machine
Sponge Construction
The sponge construction is a simple iterated construction for building a function
with variablelength input and arbitrary output length based on a fixedlength permutation $$ f: \mathbb{Z}^b \to \mathbb{Z}^b $$
operating on a fixed number \(b\) of bits. Here \(b\) is called the width. The array of \(b\) bits that \(f\) keeps transforming is called the state. The state array is split in two chunks of \(r\) and \(c\) bits respectively. We call \(r\) the bitrate (or rate) and \(c\) the capacity. We will understand later on the motivation for this splitting.
Let us describe how the sponge construction works:

(Init Phase) First of all, the input string is padded with a reversible padding rule, in order to achieve a length divisible by \(r\). Subsequently, it is cut into blocks of \(r\) bits. We also initialize the \(b\) bits of the state to zero.

(Absorbing Phase) In this phase, the \(r\)bit input blocks are XORed into the first \(r\) bits of the state, interleaved with applications of the function \(f\). We proceed until processing all blocks of \(r\)bits. Observe that the last \(c\) bits corresponding to the capacity value does not absorb any input from the outside.

(Squeezing Phase) In this phase, the first \(r\) bits of the state are returned as output blocks, interleaved with applications of the function \(f\). The number of output blocks is chosen at will by the user. Observe that the last \(c\) bits corresponding to the capacity value are never output during this phase. Actually, if the output exceeds the specified length, we will just truncate it in order to fit.
We depict an schema of the sponge construction in the Figure 1 below:
The elements that completely describe a single instance of a sponge construction are: the fixedlength permutation \(f\), the padding rule pad and the rate value \(r\).
zkEVM Specific Constructions
The zkEVM uses two different hash functions. The main reason to do so is because the Storage of the EVM uses KECCAK256 as the hash function used for constructing the corresponding Merkle Trees. However, for zkEVM internal hashes, a Poseidon hash will be used, in order to reduce the proving complexity. In this section, the specific instances of both hash functions will be defined:
KECCAK256
The EVM makes use of KECCAK256 hash function, which is constructed using KECCAK\([512]\) sponge construction. Let us, therefore, define the KECCAK\([c]\) sponge construction. This sponge operates with a width of \(1600\) bits and a rate of \(1600  c\). In the case of KECCAK\([512]\), the rate chunk is composed of \(1088\) bits (or equivalently, \(136\) bytes) and the capacity chunk has \(512\) bits (or equivalently, \(64\) bytes). The permutation used in KECCAK\([c]\) is KECCAK\(p[1600, 24]\) (See NIST SHA3 Standard). The last ingredient we need to define in order to completely specify the hash function is the padding rule. In KECCAK\([c]\), the padding pad10*1 is used. If we define \(j = (m2) \mod{r}\), where \(m\) is the length of the input in bits, then the padding we have to append to the original input message is
Thus, given an input bit string \(M\) and a output length \(d\), KECCAK\([c](M, d)\) outputs a \(d\) bit string following the previous sponge construction description.
It should be noted that this construction does not follow the FIPS202 based standard (a.k.a SHA3). According to the NIST specification,the SHA3 padding changed to
The difference is the additional \(01\) bits appended to the original message, which were not present in the orignal KECCAK specification.
Poseidon
Poseidon (See Poseidon Paper) is a hash function designed to minimize prover and verifier complexities when zeroknowledge proofs are generated and validated. The previously defined KECCAK256 cryptographic hash require large circuits as they are not tailored to finite fields used in ZK proof systems (actually, KECCAK256 works well in binary fields, and we will see later on that this fact introduces a lot of complexity in the constrain design). For this reason, zkEVM uses Poseidon hash as the main internal hash function.
More concretely, we will now specify the specific instance of Poseidon that zkEVM uses. We will work over the field \(\mathbb{F}_p\) where \(p = 2^{64}  2^{32} + 1\). The state width of the Poseidon permutation is of \(8\) field elements (observe that we are changing the paradigm, working with whole field elements instead of working bitwise) meanwhile we will work with a capacity of \(4\)field elements. The Poseidon Sbox layer that we will use is the \(7\)power SBox, i.e.
The Poseidon instance also requires to specify the number of full and partial rounds of the permutation. In our case, we will use
Only one squeezing iteration will be effectuated, with an output of the first \(4\) field elements of the state (which consists of approximately \(256\)bits, but no more than that).
The Round Constants and the MDS matrix are completely specified using the previous parameters.