## 1. Overview
Current hash functions (e.g., SHA, KECCAK) are defined by numerous bitwise operations, enabling quick computational results with computers. However, representing all bitwise operations of a hash function using arithmetic operations requires a significant number of constraints, which consequently enlarges the zero-knowledge proof circuit related to the input-output relationship of the hash function. For instance, let's consider the bit shift operation relation.

$$
\color{#DAA7AA}{11_{(2)}} <<1=\color{#DAA7AA}{110_{(2)}}
$$
To demonstrate constraints for this bitwise operation using arithmetic operations, assuming the individual binary digits of $\color{#DAA7AA}{11_{(2)}}$ are sequentially denoted as $\color{#DAA7AA}{a_1,a_0}$ and those of $\color{#DAA7AA}{110_{(2)}}$ as $\color{#DAA7AA}{b_2,b_1, b_0}$, the following conditions should be satisfied:

$$
\begin{matrix}
\color{#DAA7AA}{a_1}\times2^1 + \color{#DAA7AA}{a_0}\times2^0 = \color{#DAA7AA}a
\\ \quad \\ \color{#DAA7AA}{b_2}\times2^2 + \color{#DAA7AA}{b_1}\times2^1 + \color{#DAA7AA}{b_0}\times2^0 = \color{#DAA7AA}b
\\ \quad \\ \color{#DAA7AA}{a_i}(1-\color{#DAA7AA}{a_i})=0\ \ \ where\ \ i=0,1
\\ \quad \\ \color{#DAA7AA}{b_j}(1-\color{#DAA7AA}{b_j})=0\ \ \ where\ \ j=0,1,2
\\ \quad \\ \color{#DAA7AA}a\times 2 = \color{#DAA7AA}b
\end{matrix}
$$

In contrast, when considering a prime field $F_p$ defined over an arbitrary large prime number $p$, the following represents the same operation:

$$
\color{#DAA7AA}3\times 2= \color{#DAA7AA}6
$$

Therefore, for $\color{#DAA7AA}{a=3, b=6}$, it's sufficient to demonstrate that the equation:

$$
\color{#DAA7AA}a\times 2 = \color{#DAA7AA}b
$$

holds true. (This example is given for clarity; the actual constraints for bit operations and their corresponding arithmetic operations can vary based on the context or implementation.)

Most traditional hash functions are constructed from bit operations. To represent these using arithmetic operations, numerous constraints are required. However, the Poseidon hash has been designed to address this issue by basing its operations on those in the prime field. That is, unlike hash functions that use conventional bit operations, its internal operations are natively defined with arithmetic operations like $+, \times$, making it expressible with relatively fewer arithmetic constraints.

$\quad$

## 2. Architecture
### Notations & Definitions

- **Rate\($r$\)**: Corresponds to the length of the data block and refers to the throughput at which data is divided and processed in chunks of 'rate'.
- **Capacity\($c$\)**: Denotes the level of security; a higher value signifies enhanced security, albeit potentially at the cost of processing speed.
- **Padding**: If the input data is not an exact multiple of the rate, this method is used to fill in the data.
- **Permutation($P$)**: This is the process of mixing data divided into fixed-length blocks. $P$ in the figure represents the permutation function, taking a fixed-size input to produce an output of the same size.
- **Round**: In the sponge structure, the permutation is repeatedly applied across multiple rounds. This term refers to the number of such rounds.
- **State**: Intermediate computational results that get updated as each round in the permutation process is executed. The length of the state $t$ is calculated as $t = r + c$ and its value alters as it progresses through rounds.

$\quad$

### Sponge Structure

In cryptography, the Sponge structure is employed when designing hash functions. It's adept at taking inputs of arbitrary lengths and churning out outputs of either fixed or variable lengths. This structure is generally defined by two primary algorithms: Absorbing and Squeezing.
$\quad$
- **Absorbing**: In the context of the Sponge structure, this refers to the process of accumulating the input data into the internal state of the Sponge function.
- **Squeezing**: This delineates the step where output data is extracted from the internal state of the Sponge function.
$\quad$
The Poseidon hash function is structured around the Sponge paradigm, carrying out permutations over several rounds. As depicted in the following diagram, the message is partitioned into size $r$ and added at each permutation stage, orchestrating the desired computations.


Each stage involves the following processes:

- **Initialization**: The internal state is initialized with $N$ zero values, expressed as $I=0^r||0^c$.
- **Absorbing**: The input data is partitioned into blocks of length $r$. For instance, if the input data length is $4r - 1$, it's padded to achieve a length of $4r$, resulting in four blocks: $(m_1||m_2||m_3||m_4)$. The initial state's $0^r$ is summed with the first data block. This summation is then concatenated with the remaining $0^c$ of the initial state and permutated. The outcome of this permutation becomes the state for the next round, and the procedure is reiterated for subsequent data blocks.
- **Squeezing**: Portions of the internal state are extracted and permutation is applied until the desired hash length is attained. To fetch the hash output, $h_1$ is extracted from the final permutation, followed by another permutation to extract $h_2$. The final output becomes $(h_1||h_2)$.
$\quad$

For a clearer perspective, let's consider an example with $r=4$ and $c=1$. Here, $r$ signifies the unit to split a long message into chunks, and the length of the state is $r+c=5$. While the state value is updated after each round, its count remains consistent.

1. **Initial Setup**: Assume the initial values are $[0, 0, 0, 0, 0]$ and the message is $[3, 7, 1, 2, 3, 2, 1, 5]$.
2. **Message Block Splitting**: The given message is divided into chunks of size $r$, resulting in $[3, 7, 1, 2]$ and $[3, 2, 1, 5]$.
3. **First Round**: Summing the initial values with the first block, we get $[0, 3, 7, 1, 2]$, then apply the permutation operation. Let's assume the outcome of this permutation is $[8, 5, 13, 2, 4]$.
4. **Second Round**: The outcome of the first round is combined with the second message block, resulting in $[8, 8, 15, 3, 9]$. Applying the permutation operation once more, let's presume the outcome is $[9, 16, 11, 3, 10]$.
5. **Hash Value Output**: A permutation is applied once more. Assuming the result after this third permutation is $[13, 16, 12, 9, 20]$, the hash output derived from the second round's first value combined with the last permutation's first value is $[9,13]$.

$\quad$

### Permutation

The permutation used in Poseidon hash undergoes multiple rounds, with the number of rounds varying depending on the parameters. The rounds constituting the permutation can be categorized into full and partial rounds. The operation process for the permutation, as illustrated in research papers, is as follows:


- $R_f$: Number of full round iterations
- $R_P$: Number of partial round iterations

Each round comprises three operations:

- $ARC(\cdot)$: Addition of round constants (AddRoundConstant)
- $S$: s-box (non-linear operation)
- $M(\cdot)$: Matrix multiplication using Maximum Distance Separable (MDS) matrix

$\quad$
#### 1) Full / Partial Rounds

The rounds that make up the Permutation can be divided into two types: full and partial rounds. Although the overall flow of operations is similar, the way the s-box operation is applied varies slightly.
$\quad$
- Full Round
<img src="https://hackmd.io/_uploads/HyAYvU8zp.png" style="background-color: #FFFFFF; padding-left: 15px;padding-right: 15px;padding-bottom: 15px;">
$\quad$
- Partial Round
<img src="https://hackmd.io/_uploads/H1ErYLIf6.png" style="background-color: #FFFFFF; padding-left: 15px;padding-right: 15px;padding-bottom: 15px;">
$\quad$
$\quad$
Each input and output during these rounds is referred to as a state. As seen in the figure, during a partial round, only a subset of states undergo the s-box operation. This allows for a faster and more efficient computation with fewer resources. One might wonder: why not configure all rounds as partial rounds to gain better efficiency? Although full rounds do entail more computational cost as the s-box operation is applied to all states, they play a crucial role. They ensure that every state undergoes complex rearrangements and transformations, guarding against statistical attacks on certain inputs. On the flip side, the question arises: is it safe to configure only a few rounds as partial? However, even partial rounds have the capability to guard against algebraic attacks.

Statistical Attack: An assault on a cryptographic algorithm that seeks patterns in its output statistics to guess original data or keys. Frequency analysis and differential attacks fall under this category.
Algebraic Attack: An attack leveraging the algebraic properties of a crypto system. This entails analyzing the cipher through polynomials or equations.
In conclusion, an appropriate mix of partial and full rounds can strike a balance between security requirements and performance in specific application contexts.

#### 2) Adding Round Constants (AddRoundConstant)

Round constants are generated by the Grain LFSR. Depending on desired parameters, these constants can be pre-computed and used as needed.

#### 3) s-box (non-linear operation)

The non-linear operation s-box is defined as $x^\alpha$ where $\alpha$ is the smallest integer greater than or equal to 3, satisfying $(\alpha, p-1)=1$. The paper uses $x^3$ and $x^5$ as examples.

#### 4) MDS (Maximum Distance Separable) Matrix Multiplication

The MDS matrix is widely used in block cipher and hash function designs. Within finite fields, it guarantees maximal diffusion effects for inputs. For a given $p$ and $N$ where the Poseidon hash is defined in the prime field $F_p^N$, if $2N+1 \leq p$, the existence of such an MDS matrix is ensured.
$\quad$
## 3. Round Number Configuration

In the Poseidon hash function, the number of rounds can vary depending on the desired security level and width. The paper provides examples of round numbers, including 'security margin', based on these considerations:

| Security Level / Width | Full Rounds $R_f$ | Partial Rounds $R_p$ |
|:----------------------:|:--------------------:|:-----------------------:|
| $128$ / $3$ | $8$ | $57$ |
| $128$ / $5$ | $8$ | $60$ |
| $80$ / $3$ | $8$ | $33$ |
| $80$ / $$ | $8$ | $35$ |
| $256$ / $6$ | $8$ | $120$ |
| $256$ / $10$ | $8$ | $120$ |

Selecting parameters like these must be contextually based on the security requirements of the application environment where the Poseidon hash function is employed. The hash result must be sufficiently random and unpredictable.

$\quad$

## 4. Conclusion

The essential elements of the Poseidon hash design include:

- Adoption of a non-linear operation in the form of $x^5$ (similar to the MiMC function) as the s-box operation.
- In the permutation's partial rounds, applying intricate non-linear operations to only a subset of the state reduces computational complexity. Yet, by positioning full rounds at the beginning and end, it maintains robust cryptographic security.

With these strategies, an efficient hash function is designed for use in cryptographic algorithms that are optimized for arithmetic operations and sensitive to operational complexity, such as zero-knowledge proofs. In practice, numerous projects employing zero-knowledge proofs utilize the Poseidon hash function to design their circuits. In the following article, we'll delve into how such hash functions are crafted, accompanied by actual code examples.