Poseidon Hash Function
Last updated
Last updated
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.
to the code of Poseidon in Keelung.
Poseidon is structured as a sequence of rounds, each of which applies substitution and permutation operations on the input data.
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:
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:
Let's evaluate the expression above step by step, and see how it actually works:
Here's a detailed walk through of all components in the actual implementation of Poseidon.
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.
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.
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.
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.
We can construct this expression using the function:
If you want to know more about fold, explaining how it works under the hood.