Module internal 

Partial (internal) round layers for the Poseidon1 permutation.

Overview

Partial rounds apply the S-box only to state[0], leaving the other t-1 elements unchanged through the nonlinear layer. This is the key efficiency insight of the Poseidon1 design: partial rounds are much cheaper than full rounds, yet they efficiently increase the algebraic degree to resist interpolation and Gröbner basis attacks.

Sparse Matrix Optimization

In the textbook formulation, each partial round still multiplies by the full dense MDS matrix M (cost O(t^2)). The Poseidon1 paper (Appendix B) factors M into a product of sparse matrices, one per round. Each sparse matrix S_r has the structure:

  S_r = ┌─────────┬───────────┐
        │ mds_0_0 │  ŵ_r      │    <- first row
        ├─────────┼───────────┤
        │  v_r    │    I      │    <- identity block
        └─────────┴───────────┘

where the top-left entry is a scalar, the first row holds a (t-1)-vector, the first column holds a (t-1)-vector, and the bottom-right block is the (t-1)x(t-1) identity.

Multiplying by S_r costs only O(t) operations instead of O(t^2). Over RP partial rounds, this saves O(RP * t^2) -> O(RP * t).

Optimized Partial Round Structure

After this transformation, the RP partial rounds become:

  1. Add first_round_constants (full WIDTH-vector)
  2. Multiply by m_i (dense transition matrix, applied once)
  3. For each of RP rounds:
     a. S-box on state[0]:  state[0] = state[0]^D
     b. Add scalar constant to state[0] (all rounds except the last)
     c. Sparse matrix multiply via cheap_matmul

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

Structs

PartialRoundConstants

Pre-computed constants for the RP partial (internal) rounds.

Traits

PartialRoundLayer

The partial (internal) round layer of the Poseidon1 permutation.

PartialRoundLayerConstructor

Construct a partial round layer from pre-computed constants.

Functions

cheap_matmul

Sparse matrix-vector multiplication in O(WIDTH) operations.

partial_permute_state

Generic implementation of the partial round permutation.

textbook_partial_permute_state

Textbook partial round permutation with forward-substituted scalar constants.