# Poseidon Hash Function

## Introduction

Poseidon is a cryptographic hash function designed specifically for use in zero-knowledge proof systems, such as R1CS and PLONK. It offers improved performance compared to other existing hash functions, by a factor of up to 40 times. The function uses a substitution-permutation network design, a well-known design in symmetric cryptography, and supports varying finite field sizes, making it a versatile option for a variety of zero-knowledge proof applications.

## About this tutorial

In this tutorial, our goal is to demonstrate the implementation of Poseidon in Keelung. We will showcase how to use `fold`

, a commonly used method in functional programming, to repeatedly apply an action on the state and produce the desired result.

Here's the link to the code of Poseidon in Keelung.

## Overview

Poseidon is structured as a sequence of **rounds**, each of which applies substitution and permutation operations on the input data.

### Round

As shown in the diagram above, each round consists of three components. Suppose that we have defined Haskell functions for each of these components:

`arc`

for*ARC*`sbox`

for*S*`mix`

for*M*

We can defined the `round`

function as the composition of these components. It takes `[Field]`

as input and returns `[Field]`

as output:

Because `sbox`

and `arc`

both actually takes the current round number as input, let's generalize `round`

a bit:

### Apply `round`

multiple times

`round`

multiple timesSuppose we have to apply the `round`

function 3 times on an input data `initState`

, each time with the current round number. The resulting output would be expressed as:

We can construct this expression using the foldl function:

Let's evaluate the expression above step by step, and see how it actually works:

If you want to know more about fold, here's a simple article explaining how it works under the hood.

## Components

Here's a detailed walk through of all components in the actual implementation of Poseidon.

### Main function `hash`

`hash`

Let's look at the main function `hash`

first. It takes as input a message `msg`

, represented as a list of `Field`

values, and returns a `Field`

as the hashed result.

The function performs the following steps:

check if the message length is valid (i.e., not null and less than or equal to 6).

initialize constants

`t`

,`roundsP`

,`f`

,`p`

,`c`

, and`m`

.

Initialize the state with 0 as the first element and the message as the rest.

Define the

`round`

function, which consists of three components:*"AddRoundConstants"*as`arc`

*"SubWords"*as`sbox`

*"MixLayer"*as`mix`

Use

`foldlM`

to apply the`round`

function`p`

times on the initial state.

Finally, return the first element of the final state as the hash value.

*AddRoundConstants* `arc`

*AddRoundConstants*

`arc`

The `arc`

function implements the "AddRoundConstants" component of the round function.

The `arc`

function takes 3 inputs:

A

`Vector Field`

of constants named`c`

.An integer

`it`

for selecting constants in`c`

.A list of

`Field`

named`state`

.

It returns a new list of `Field`

by adding `c ! (it + i)`

to each element `x`

of the input list `state`

at index `i`

, using the `mapI`

function.

*SubWords* `sbox`

*SubWords*

`sbox`

`fullSBox`

takes an element `x`

from the `state`

list and computes `x⁵`

as output.

Depending on the round number `r`

and other parameters like `p`

and `r`

, `sbox`

applies `fullSBox`

on each element `x`

of the `state`

list.

*MixLater* `mix`

*MixLater*

`mix`

It takes two inputs, a matrix `m`

of field elements, and a state represented as a list of field elements. The function calculates the dot product of each row of the matrix with the state and returns the result as a new list of field elements.

The calculation is performed using the `map`

and `sum`

functions. The `map`

function maps each element of the state to its dot product with a row of the matrix. The `sum`

function takes the sum of these dot products to obtain the final result.

The length of the resulting list is equal to the number of rows in the matrix, which is equivalent to the length of the state.

Last updated