GitHub | 𝕏

Acknowledgments

Special thanks to Marco Besier, Emile , and 0x18a6 for reviewing the blog and providing valuable feedback. Your comments helped improve its clarity and accuracy.

<aside> 🧭

In this blog, you will learn:

• What a sponge construction is (state, rate, capacity, padding, squeeze).
• The difference between Poseidon Hash and the Poseidon permutation (π).
• How a message is absorbed and how outputs are squeezed (with a concrete example).
• How the Poseidon permutation is built from Hades rounds: ARC → S-Box → MDS.
• How full vs. partial rounds balance security and efficiency.
• Where MDS matrices and round constants come from (Cauchy construction + Grain LFSR).
• How the S-Box exponent $\alpha$ must satisfy $gcd(\alpha, p - 1) = 1$.
• How round numbers are chosen using security formulas.
• What an overwrite sponge is and how it differs from normal sponge absorption.
• What feed-forward construction is and how it differs from sponge hashing.
• How feed-forward can replace sponge construction for fixed-size compression. </aside>

Poseidon Hash (Sponge Construction)

Before going deeper, it is important to separate two things:

<aside> 🧽

Poseidon Hash ≠ Poseidon Permutation.

• Poseidon permutation (π): the internal state-mixing function.
• Poseidon hash: a sponge construction that repeatedly applies π. </aside>

So:

$$ Poseidon \, Hash = Sponge \, construction + Poseidon \, permutation \, π $$

The permutation itself is not the full hash. It is the function used inside the hash.

Sponge Construction Basics

Sponge-based hash function has 4 main components:

1. State memory (S)

   • Bitrate (R): size r (rate) how much data you can absorb per round. The initial state starts as all zeros.
   • Capacity (C): size c security margin.
   • Total state size: S = r + c.

2. Permutation / compression function $Poseidon^π$ $( f )$

   • Takes the full state S as input and outputs a state of the same length.
   • The state S is updated each time it is processed by $f$.

3. Padding function

   • Pads the message M so its length becomes a multiple of the bitrate r.

4. Squeeze phase (output generation)

   • Output is produced by reading r from the state at a time.
   • Between output blocks, apply $f$ again.
   • Final digest: Z = Z0 || Z1 || ... and truncate to the required length if needed.

   

   Poseidon Hash as a Sponge

   Now let’s see how Poseidon uses the sponge construction.

   Assume:

   $$ t = 3 \\ r = 2 \\ c = 1 $$

   So the state is:

   $$ [x₀, x₁ | x₂] $$

   ---

   1. Message Input

   Assume we want to hash:

   $$ m = [5, 7, 9] $$

   Since the rate is $r = 2$ we split the message into chunks of 2 elements:

   $$ m₁ = [5, 7] \\ m₂ = [9, pad] $$

   The second chunk needs padding because it only has one element.

   ---

   2. Initial State

   The sponge starts from the all-zero state:

   $$ S₀ = [0, 0 | 0] $$

   ---

   3. Absorb First Chunk

   First chunk:

   $$ m₁ = [5, 7] $$

   Add it into the rate part:

   $$ [0, 0 | 0] + [5, 7 | 0]

   [5, 7 | 0] $$

   Then apply the full Poseidon permutation:

   $$ π([5, 7 | 0]) = [a, b | cap₁] $$

   Important:

   $$ π = full \, Poseidon \, permutation $$

   It is not one round. It contains many internal Hades rounds.

   ---

   4. Absorb Second Chunk

   Second chunk:

   $$ m₂ = [9, pad] $$

   Current state:

   $$ [a, b | cap₁] $$

   Absorb the second chunk into the rate part:

   $$ [a, b | cap₁] + [9, pad | 0]

   [a + 9, b + pad | cap₁] $$

   Then apply the full Poseidon permutation again:

   $$ π([a + 9, b + pad | cap₁]) = [h₀, h₁ | cap₂] $$

   ---

   5. Squeeze Output

   The output is taken from the rate part:

   $$ [h₀, h₁] $$

   If we need one hash element:

   $$ hash = h₀ $$

   If we need two output elements:

   $$ hash = [h₀, h₁] $$

   If we need more output elements than the rate allows, we apply the permutation again and keep reading from the rate part.

   This is called squeezing.

   ---

   Sponge Flow Summary

   

Meaning of $I_c \oplus m_1$

Many descriptions write:

$$ I_c \oplus m_1 $$