# Bits2Field state machine

The Bits2Field state machine is one of the auxiliary state machines used specifically for parallelizing the implementation of KECCAK-F SM. Its source code is available here.

The Bits2Field state machine ensures correct packing of $$\mathtt{44}$$ bits from $$\mathtt{44}$$ different $$\mathtt{1600}$$-row blocks of the Padding-KK-Bit SM into a single field element. Therefore, it operates like a (44-bits-to-1-field-element) multiplexer between the Padding-KK-Bit SM and the Keccak-F SM.

In simpler terms, it takes bits from $$\mathtt{44}$$ different blocks, places them into the first 44 bit-positions of a single field element, whereupon the KECCAK-F circuit runs. The name Bits2Field state machine refers to the process of taking $$44$$ bits from $$44$$ different blocks of the Padding-KK-Bit SM and inserting them into a single field element.

Although the KECCAK-F SM is a binary circuit, instead of executing on a bit-by-bit basis, it is implemented to execute KECCAK-F operations on a 44bits-by-44bits basis. This is tantamount to running $$\mathtt{44}$$ KECCAK-F hashing circuits in parallel.

The figure below depicts a simplified multiplexing process.

## Mapping 44 Bits To A 64-bit Field Element¶

Suppose operations are carried out in a field $$\mathbb{F}_p$$ of $$\mathtt{64}$$-bit numbers. The smallest field used in the zkProver is the Goldilocks Field $$\mathbb{F}_p$$ where $$p = 2^{64} - 2^{32}+1$$.

After multiplexing, the 44 bits are loaded into the first 44 least significant bit-positions of the field element as depicted in the figure below.

A field element as an input to the KECCAK-F circuit is of the form,

$\mathtt{0b}\mathtt{0000\ 0000\ 0000\ 0000\ 0000}\ \mathtt{X}_1 \mathtt{X}_2 \mathtt{X}_3 \mathtt{X}_4\ \mathtt{X}_5 \mathtt{X}_6 \mathtt{X}_7 \mathtt{X}_8\ \dots \mathtt{X}_{43} \mathtt{X}_{44} \text{ }$

and it is composed of 20 zeroes and 44 meaningful bits related to the committed polynomials.

Given the capacity of $$2^{23}$$ in terms of the state machine evaluations (i.e., the degree of polynomials) and the KECCAK-F’s $$\texttt{SlotSize} = 155286$$, one obtains $$2^{23} / 155286 = 54.020375307$$ KECCAK-F slots.

Therefore, a total of $$54$$ slots $$\times$$ $$44$$ blocks $$= 2376$$ Keccak blocks can be processed.

This is a big improvement from the previous $$477$$ blocks of the 9bits-to-1field element multiplexing (i.e., $$53 \times 9 = 477$$).

## The Bits2Field PIL Code¶

The Bits2Field executor executes the multiplexing of forty-four $$\mathtt{1600}$$-bit blocks into $$\mathtt{1600}$$ field elements, where each is a $$\mathtt{N}$$-bit field element. For reference, see the above figure where $$\mathtt{N = 64}$$.

The question here is how to identify each of the original 9 bits of the field element to track their corresponding resultant $$\mathtt{XOR}$$ values or $$\mathtt{ANDP}$$ values?

Note that every bit $$\mathtt{b_{i,j}}$$ from the $$\mathtt{i}$$-th $$\mathtt{1600}$$-bit block is placed at the $$\mathtt{2^{i}}$$-th position of the $$\mathtt{N}$$-bit field element.

The PIL code therefore uses factors denoted by $$\mathtt{Factor}$$, such that $$\mathtt{Factor \in \{ 1, 2, 4, \dots , 2^{43} \}}$$, and a $$\mathtt{Fieldlatch}$$ after running through forty-four $$\mathtt{1600}$$-bit blocks.

Suppose $$\mathtt{N = 64}$$. Then the 44 least significant bits of the $$\mathtt{64}$$-bit field element looks like this:

$\mathtt{field44 = X_1 \cdot 2^{43} + X_{2}*{2}^{42} + X_{3}*{2}^{41} + \dots + X_{42}*{2}^2 + X_{43}*2 + X_{44}}.$

The constraint checked is therefore,

$\mathtt{field44' = (1-Fieldlatch)*field44 + bit*Factor}$

The accumulated field element at the end of the execution (every forty-fourth row of the execution trace) is checked against the KECCAK-F input $$\mathtt{KeccakF.a}$$ with the boundary constraint,

$\mathtt{Fieldlatch*(field44 - KeccakF.a) = 0}$

The PIL code is given below.

% "bits2field.pil"

include "keccakf.pil";

namespace Bits2Field(%N);
pol constant FieldLatch;  // [0:44,1]
pol constant Factor;  // 1,2,4,8,...,2**43

pol commit bit;
pol commit field44;

field44' = (1-FieldLatch)*field44 + bit*Factor;
bit *(1-bit) = 0;

FieldLatch*(field44 - KeccakF.a44) = 0;