Paddingkkbit state machine
The 136byte output of the PaddingKK SM must first be translated to bits before it can be used as the KeccakF SM’s input. This is where the PaddingKKBit state machine comes into picture. One of the functions of the PaddingKKBit SM is to convert bytes to bits in both directions. And serves as a bridge between the bitwise operating KeccakF SM and the bytewise operating PaddingKK SM.
The PaddingKKBit SM is in charge of validating each action connected to the inputs and outputs of the KeccakF permutation blocks in addition to being a twoway bytestobits converter.
Design strategy¶
Here’s how this state machine facilitates operations between the PaddingKK SM and the KeccakF SM.
A block of 136 rows of bytes in the PaddingKK SM corresponds to \(\mathtt{1993}\) rows in the PaddingKKBit SM. The picture below, displays the correspondence, also shows three subdivisions of the \(\mathtt{1993}\) rows (corresponding to \(\mathtt{1224+512+256+1}\)).
First subdivision → It consists of \(\mathtt{9*136 = 1224}\) rows, where each of the \(\mathtt{136}\) byterows has been expanded into \(\mathtt{9}\) rows (i.e., \(\mathtt{8}\) rows for the \(\mathtt{8}\) bits plus \(\mathtt{1}\) row for the byte that represents the \(\mathtt{8}\) bits). The decomposition of the bytes into the 8 bits (with an extra row, just for the byte), is done for easy implementation in PIL. This subdivision of \(\mathtt{1224}\) rows represents the bitrate of the KECCAKF permutation. Therefore, a strategy to ensure that the bits are accurately and correctly provided, as input to the KECCAKF SM, needs to be derived.
Second subdivision → This consists of the \(\mathtt{512}\) rows, and represents the capacity inputbits in the \(\mathtt{1600}\)bit state of the KECCAKF SM. Within the KECCAKF state machine, unlike the bits in the first subdivision of \(\mathtt{1224}\) rows, the capacity bits are not affected by any exterior bits.
Third subdivision → It consists of \(\mathtt{256 + 1}\) rows represents the 256 bits of the intermediate hash value produced by the KECCAKF permutation. At the end of hashing each 1088 bits (136byte) string, this intermediate hash value actually coincides with the final hash of the KECCAK256 hash function. Each hash value, the final digest, is packed into eight 32bit registers at the final row of this subdivision.
Bytes to bits correspondence¶
This section elaborates how the PaddingKKBit SM handles the correspondence of bytes between state machines, and correct positioning of bits with respect to the powers of 2.
Starting with the first subdivision, the \(\mathtt{1224}\) rows related with the bit decomposition of each byte, the following registers are utilised:

The PaddingKKBit state machine has a column named \(\texttt{rBit}\), which records all the bits associated with the decomposition of each of the bytes of the PaddingKK SM.

In order to relate the byte to its bit decomposition between the two states machines, a register called \(\texttt{r8Id}\) is added in both state machines as a bittoparentbyte identifier.

Also, another register called \(\texttt{r8}\), is added for the sole purpose of sequentially constructing each byte from the bits.

A factor register \(\texttt{Fr8}\) is used to correctly place each bit in the parent, with respect to the powers of 2.

Therefore, each complete byte is recorded at the last row of such a 9row byte block of the \(\texttt{r8}\) register. This row is flagged with a “1” in the same row of another register called \(\texttt{latchR8}\). This ensures that \(\texttt{latchR8}\) is 0 in all rows except the last row of a 9row byte block.
Example: Representation of two bytes¶
Here’s an example of how two bytes, \(\mathtt{0xa1}\) and \(\mathtt{0xfe}\), from the PaddingKK SM look like in the PaddingKKBit SM. The horizontal lines mark the end of a byte block.
Note that \(\texttt{latchR8}\) is equal to 1 in the last row of each byte block, and this is the same row where the corresponding complete byte is found in the \(\texttt{r8}\) column.
The following constraint applies to the \(\texttt{r8}\) column,
It is very important for \(\mathtt{Fr8}\) to be “\(0\)” when \(\mathtt{latchR8}\) is “\(1\)”. If this is not the case, then there is no guarantee that the \(\mathtt{r8}\) register will reset to \(0\) in the next block.
It is also necessary to ensure that \(\mathtt{rBit}\) is binary, by using the next constraint,
Validating transitions of bits¶
The challenge of breaking down bytes into bits has been the main focus up to this point. Here, it is intended to verify the bit transitions following the KECCAKF operation, which is carried out for each block of 136 bytes. For this, a few columns are introduced.

\(\mathtt{sInBit}\): This register stores the input bit of the current KECCAKF permutation block.

\(\mathtt{sOutBit}\): This register stores the output bit of the current KECCAKF permutation block.

\(\mathtt{connected}\): The same idea as in the PaddingKK state machine applies here. The \(\mathtt{connected}\) register is constant within a block, and reflects that the output of the previous permutation KECCAKF is connected to the current one. That is, it indicates that the previous 136byte block belongs to the same string as the current block.

\(\mathtt{latchSOut}\): This register records “\(1\)” in the very last row of each of the \(\mathtt{1993}\)row block corresponding to a 136byte block of the PaddingKK SM, and \(0\) everywhere else.
Below figure depicts a schema of how to relate the above columns with the KECCAKF sponge construction.
Constraints for bit transitions¶
These constraints are needed to ensure correct transition between rows.
There is a need to make sure the \(\mathtt{connected}\) register is constant in each block. Hence, the following constraint should be added,
It is also mandatory to test whether \(\mathtt{connected}\) and \(\mathtt{sOutBit}\) are binary. For these two checks, the following equations are used,
The register \(\mathtt{sInBit}\) is actually computed from \(\mathtt{sOutBit}\), \(\mathtt{connected}\) and \(\mathtt{rBit}\) columns. Recall that, at the first block of the sponge function, the input bits to the KECCAKF permutation actually coincide with \(\mathtt{rBit}\). However, after the first block, an \(\text{XOR}\) of \(\mathtt{sOutBit}\) and \(\mathtt{rBit}\) must be performed, as seen in the above figure.
Therefore, \(\mathtt{sInBit}\) is computed using an auxiliary register \(\mathtt{aux\_sInBit}\) as follows,
A quick analysis of \(\mathbf{Eqn. 6}\) shows the following,

If \(\mathtt{connected}\) is \(0\), then \(\mathtt{sInBit}\) equals \(\texttt{rBit}\), which is precisely what needs to happen in the first KECCAKF permutation block.

But if \(\mathtt{connected}\) is \(1\), then \(\mathtt{sInBit}\) equals \(\mathtt{sOutBit − 2 \cdot sOutBit \cdot rBit + rBit}\), which is actually the \(\text{XOR}\) of \(\mathtt{sOutBit}\) and \(\mathtt{rBit}\).
Below table shows all the cases of the above computation.
Capacity connection in the 512 rows¶
The second subdivision of the PaddingKKBit SM’s \(\mathtt{1993}\)row block consists of the \(\mathtt{512}\) rows, corresponding to KECCAKF SM’s capacity bits. It is mandatory to ensure these capacity bits (the middle subdivision of each \(\mathtt{1993}\)row block) are not affected by any exterior bit.
First, a new register called \(\mathtt{rBitValid}\) is added, and it is defined such that it records \(1\) in each of the rows corresponding to the capacity bits, and \(0\) everywhere else. Hence, the following relationship is added.
This ensures that in each \(1993\)row block, \(\mathtt{rBit}\) is \(0\) everywhere in the rows corresponding to the capacity bits. This results in XORing \(\mathtt{sOutBit}\) with a \(0\). And thus, for the rows corresponding to the capacity bits, computing \(\mathtt{sInBit = sOutBit \bigoplus rBit}\), amounts to \(\mathtt{sInBit = sOutBit}\). Therefore, \(\mathbf{Eqn. 8}\) guarantees that the capacity bits are not modified by any exterior bits.
Output calculations in the (256 + 1) rows¶
Now, the last part of the PaddingKKBit SM is to keep track of the last subdivision of each \(1993\)row block. Recall that this third subdivision consists of \(256 + 1\) rows, and it is in charge of storing each bit of the intermediate hashes of the KECCAKF permutation blocks. The \(256\) bits of the KECCAKF permutation output are sequentially and cumulatively stored in eight 32bit registers \(\{\mathtt{sOut_i}\ 0 \leq i \leq 7 \}\). In a similar method used for the read operations in the PaddingKK SM, eight (8) factor columns \(\{\mathtt{FSOut_i} \ 0 \leq i \leq 7\}\) are used to ensure correct positioning (of each of the \(32\) bits in \(\mathtt{sOut_i}\)) with respect to powers of \(2\).
Example: Storing 256bit intermediate hash outputs¶
Consider the 256 bits, \(\mathtt{0b10110011\dots1010\dots11\dots1101\dots10101101}\), where “\(\)” separates every set of 32 bits. The table below displays how the \(256 + 1\) rows of a \(1993\)block are stored in the registers \(\{\mathtt{sOut_i}\ 0 \leq i \leq 7 \}\).
Observe how factors \(\{\mathtt{FSOut_i} \ 0 \leq i \leq 7\}\), in the above table, are used to construct the \(32\)bit registers \(\{\mathtt{sOut_i}\ 0 \leq \mathtt{i} \leq 7 \}\). Note that the last row contains the complete set of the \(256\) bits. These columns fulfil the following relations,
where \(0\leq \mathtt{i} \leq 7\).
The \(\mathtt{latchSOut}\) register ensures that \(\mathtt{sOutBit}\) is not constrained at the very beginning of each \(1993\)block, but only until the third subdivision is reached, where the \(\mathtt{FSOut_i}\) begin to attain nonzero values.
This concludes our design for creating the PaddingKKBit SM. What is left to be done is to connect both states machines and check the validity of the last hash.
PaddingKK SM and PaddingKKBit SM connection¶
This section describes how these two state machines, the PaddingKK SM and the PaddingKKBit SM, connect via Plookup.
First of all, observe that there’s a need to check whether the bytes received in one state machine are the same as those in the other. Also, corresponding sequential order of these bytes should be checked. The identifier register \(\mathtt{r8Id}\) is added in both states machines for the very reason. In addition, each byte should have the same value in \(\mathtt{connected}\) register. Hence, the following Plookup is added in the PaddingKK state machine,
The PaddingKK state machine has the \(\{\mathtt{hash_i}\}\) registers while the PaddingKKBit state machine has the \(\{\mathtt{sOut_i}\}\) registers, which must be related at some point during the execution. Yet, up this point, the order of the hashes has not been checked in any way. Hence, as previously done, an \(\mathtt{sOutId}\) register is added in both machines in order to identify each of these hashes.
In particular, \(\mathtt{sOutId}\) is an increasing sequence of integers which increases by one at each processed block. That is, in the PaddingKK state machine, \(\mathtt{sOutId}\) increases by one in each block of \(136\) rows, whilst in the PaddingKKBit state machine, it increases by one in each block of \(1993\) rows. This is because a single block of \(136\) rows in the PaddingKK SM corresponds to a single block of \(1993\) rows in the PaddingKKBit SM.
Hence, the following Plookup is added: