Crate p3_poseidon1 

The Poseidon1 permutation.

Overview

Poseidon1 is a cryptographic hash function designed for efficient verification inside zero-knowledge proof systems (SNARKs, STARKs, etc). It operates natively over prime fields, avoiding the overhead of bit-decomposition required by traditional hashes like SHA-256 or Keccak.

This crate provides Poseidon1, an optimized implementation that uses the sparse matrix decomposition from the original paper (Appendix B) to factor the dense MDS matrix into sparse components. This reduces the cost of each partial round from O(t^2) to O(t), where t = WIDTH is the state width.

Round Structure

Poseidon1 alternates between two types of rounds:

  ┌──────────────────┐   ┌───────────────────┐   ┌──────────────────┐
  │ RF/2 full rounds │ → │ RP partial rounds │ → │ RF/2 full rounds │
  │ (S-box on all)   │   │ (S-box on s[0])   │   │ (S-box on all)   │
  └──────────────────┘   └───────────────────┘   └──────────────────┘

• Full rounds (RF total, split equally): apply the S-box x^D to every state element, then multiply by the dense MDS matrix. These provide resistance against statistical attacks (differential, linear, rebound).

• Partial rounds (RP total): apply the S-box only to state[0], then multiply by a sparse matrix derived from the MDS factorization. These efficiently increase the algebraic degree to resist interpolation and Gröbner basis attacks.

Each round follows the sequence: AddRoundConstants → S-box → MixLayer.

References

• Grassi et al., “Poseidon1: A New Hash Function for Zero-Knowledge Proof Systems”, USENIX Security 2021. https://eprint.iacr.org/2019/458
• HorizenLabs reference implementation: https://github.com/HorizenLabs/poseidon2

Re-exports

pub use external::*;

pub use generic::*;

pub use internal::*;

Modules

external

Full (external) round layers for the Poseidon1 permutation.

generic

Generic implementations of Poseidon1 linear layers.

internal

Partial (internal) round layers for the Poseidon1 permutation.

utils

Equivalent matrix decomposition for efficient partial rounds.

Structs

Poseidon1

The optimized Poseidon1 permutation.

Poseidon1Constants

Raw Poseidon1 parameters before the sparse matrix optimization.