Poseidon Hash Function
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.
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.Poseidon is structured as a sequence of rounds, each of which applies substitution and permutation operations on the input data.

Multiple Iterations of the "Round Function": building block of Poseidon permutation
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 ARCsbox
for Smix
for M
We can defined the
round
function as the composition of these components. It takes [Field]
as input and returns [Field]
as output:round :: [Field] -> [Field]
round = mix . sbox . arc
Because
sbox
and arc
both actually takes the current round number as input, let's generalize round
a bit:round :: Int -> [Field] -> [Field]
round r = mix . sbox r . arc r
Suppose 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: round 2 (round 1 (round 0 initState))
foldl (\state r -> round r state) initState [0, 1, 2]
Let's evaluate the expression above step by step, and see how it actually works:
foldl (\state r -> round r state) initState [0, 1, 2]
=>
foldl (\state r -> round r state) (round 0 initState) [1, 2]
=>
foldl (\state r -> round r state) (round 1 (round 0 initState)) [2]
=>
round 2 (round 1 (round 0 initState))
If you want to know more about fold, here's a simple article explaining how it works under the hood.
Here's a detailed walk through of all components in the actual implementation of Poseidon.
hash :: [Field] -> Comp Field
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:
- 1.check if the message length is valid (i.e., not null and less than or equal to 6).
hash msg = do
when
(null msg || length msg > 6)
(error "Invalid message length")
- 2.initialize constants
t
,roundsP
,f
,p
,c
, andm
.
let t = length msg + 1
let roundsP = [56, 57, 56, 60, 60, 63, 64, 63]
let f = 8
let p = roundsP !! (t - 2)
let c = Constant.c ! (t - 2)
let m = Constant.m ! (t - 2)
- 3.Initialize the state with 0 as the first element and the message as the rest.
let initState = 0 : msg
- 4.Define the
round
function, which consists of three components:- 1."AddRoundConstants" as
arc
- 2."SubWords" as
sbox
- 3."MixLayer" as
mix
let round r = mix m . sbox f p r . arc c (r * t)
- 5.Use
foldlM
to apply theround
functionp
times on the initial state.
result <- foldlM (\state r -> reuse (round r state)) initState [0 .. f + p - 1]
- 6.Finally, return the first element of the final state as the hash value.
return $ head result
The
arc
function implements the "AddRoundConstants" component of the round function.arc :: Vector Field -> Int -> [Field] -> [Field]
arc c it state = mapI (\i x -> x + c ! (it + i)) state
The
arc
function takes 3 inputs:- A
Vector Field
of constants namedc
. - An integer
it
for selecting constants inc
. - A list of
Field
namedstate
.
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.sbox :: Int -> Int -> Int -> [Field] -> [Field]
sbox f p r state = mapI go state
where
go 0 x = fullSBox
go _ x = if r < f `div` 2 || r >= f `div` 2 + p then fullSBox x else x
-- Full S-box of x⁵
fullSBox x = x * x * x * x * x
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.mix :: Vector (Vector Field) -> [Field] -> [Field]
mix m state =
map
(\i -> sum (mapI (\j x -> x * (m ! i ! j)) state))
[0 .. length state - 1]
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 modified 3mo ago