## Preamble

```
CAP: 0075
Title: Cryptographic Primitives for Poseidon/Poseidon2 Hash Functions
Working Group:
    Owner: Jay Geng <@jayz22>
    Authors: Jay Geng <@jayz22>
    Consulted: Antonio <@Fantoni0>, Yan <@ymcrcat>, Tomer Weller <@tomerweller>
Status: Final
Created: 2025-10-08
Discussion: https://github.com/orgs/stellar/discussions/1780
Protocol version: 25
```

## Simple Summary

This CAP proposes host functions for Poseidon and Poseidon2 permutation primitives.

## Working Group

TBD

## Motivation

Poseidon is a family of hash functions designed specifically for efficient zero-knowledge proof systems, due to its operations being native to the prime fields. Even though proofs are generated off-chain (and proof verification does not require rehashing), having consistent hash functions in the contract logic with the prove-system choice is crucial. Supporting Poseidon as host functions in Soroban can facilitate adoption of ZK applications and interoperability with other ecosystems.


### Goals Alignment

This CAP is aligned with the following Stellar Network Goals:

- The Stellar Network should make it easy for developers of Stellar projects to create highly usable products
- The Stellar Network should facilitate simplicity and interoperability with other protocols and networks

## Abstract

This CAP adds two host functions implementing the Poseidon and Poseidon2 permutation primitives. These primitives operate on field elements from BLS12-381 Fr or BN254 Fr scalar fields. The permutation functions accept configurable parameters, allowing developers to construct hash functions tailored to specific use cases, thus maintaining interoperability with other ZK systems.

## Specification

### New host functions

Two new functions with export names `p` and `q` in the crypto module (`c`) are added to the Soroban environment's exported interface.

```json
{
   "export": "p",
   "name": "poseidon_permutation",
   "args": [
      { "name": "input", "type": "VecObject" },
      { "name": "field", "type": "Symbol" },
      { "name": "t", "type": "U32Val" },
      { "name": "d", "type": "U32Val" },
      { "name": "rounds_f", "type": "U32Val" },
      { "name": "rounds_p", "type": "U32Val" },
      { "name": "mds", "type": "VecObject" },
      { "name": "round_constants", "type": "VecObject" }
   ],
   "return": "VecObject",
   "docs": "Performs Poseidon permutation on input vector. `input`: vector of field elements (length `t`). `field`: `BLS12_381` or `BN254`. `t`: state size. `d`: S-box degree (5 for `BLS12_381`/`BN254`). `rounds_f`: number of full rounds (must be even). `rounds_p`: number of partial rounds. `mds`: `t`-by-`t` MDS matrix as `Vec<Vec<Scalar>>`. `round_constants`: (`rounds_f` + `rounds_p`)-by-`t` round constants matrix as `Vec<Vec<Scalar>>`. Returns output vector after permutation.",
   "min_supported_protocol": 25
},
{
   "export": "q",
   "name": "poseidon2_permutation",
   "args": [
      { "name": "input", "type": "VecObject" },
      { "name": "field", "type": "Symbol" },
      { "name": "t", "type": "U32Val" },
      { "name": "d", "type": "U32Val" },
      { "name": "rounds_f", "type": "U32Val" },
      { "name": "rounds_p", "type": "U32Val" },
      { "name": "mat_internal_diag_m_1", "type": "VecObject" },
      { "name": "round_constants", "type": "VecObject" }
   ],
   "return": "VecObject",
   "docs": "Performs Poseidon2 permutation on input vector. `input`: vector of field elements (length `t`). `field`: `BLS12_381` or `BN254`. `t`: state size. `d`: S-box degree (3, 5, 7, or 11). `rounds_f`: number of full rounds (must be even). `rounds_p`: number of partial rounds. `mat_internal_diag_m_1`: internal matrix diagonal minus 1 as `Vec<Scalar>` (length `t`). `round_constants`: (`rounds_f` + `rounds_p`)-by-`t` round constants matrix as `Vec<Vec<Scalar>>`. Returns output vector after permutation.",
   "min_supported_protocol": 25
}
```

### XDR changes

```diff mddiffcheck.ignore=true
diff --git a/Stellar-contract-config-setting.x b/Stellar-contract-config-setting.x
--- a/Stellar-contract-config-setting.x
+++ b/Stellar-contract-config-setting.x
@@ -281,7 +281,17 @@ enum ContractCostType {
     // Cost of performing BN254 pairing operation
     Bn254Pairing = 78,
     // Cost of converting a BN254 scalar element from U256
-    Bn254FrFromU256 = 79
+    Bn254FrFromU256 = 79,
+    // Cost of converting a BN254 scalar element to U256
+    Bn254FrToU256 = 80,
+    // // Cost of performing BN254 scalar element addition/subtraction
+    Bn254FrAddSub = 81,
+    // Cost of performing BN254 scalar element multiplication
+    Bn254FrMul = 82,
+    // Cost of performing BN254 scalar element exponentiation
+    Bn254FrPow = 83,
+     // Cost of performing BN254 scalar element inversion
+    Bn254FrInv = 84
 };
```

### Semantics

#### Field Selection

The `field` parameter is a `Symbol` that selects the scalar field:
- `BLS12_381`: BLS12-381 Fr (scalar field order `r` = `0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001`)
- `BN254`: BN254 Fr (scalar field order `r` = `0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001`)

Scalar field elements are represented as `U256Val` objects as specified in CAP-0059.

#### Permutation Parameters

Both Poseidon and Poseidon2 are based on the HADES design strategy, which alternates between full rounds and partial rounds:

- `t`: State size. The internal state contains `t` field elements. Common values are 2, 3, or 4 depending on the use case (e.g., binary tree hashing uses t=3). Poseidon does not restrict the state size. Poseidon2 supports state sizes of 2, 3, 4, 8, 12, 16, 20, or 24.

- `d`: S-box degree. The S-box is defined as S(x) = x^d. Only d=5 is supported, which is the standard choice for both BLS12-381 and BN254.

- `rounds_f`: Number of full rounds. Must be even. In full rounds, the S-box is applied to all `t` state elements.

- `rounds_p`: Number of partial rounds. In partial rounds, the S-box is applied to only one state element.

The total number of rounds is `rounds_f + rounds_p`.

#### Matrix Parameters

**Poseidon** uses an MDS (Maximum Distance Separable) matrix for the linear layer:

- `mds`: A `t`-by-`t` MDS matrix represented as `Vec<Vec<Scalar>>`. The matrix is typically a Cauchy matrix. During each round, the state vector is multiplied by this matrix.

**Poseidon2** uses an optimized internal linear layer:

- `mat_internal_diag_m_1`: Internal matrix diagonal minus 1, represented as `Vec<Scalar>` of length `t`. Poseidon2 replaces the MDS matrix in partial rounds with a more efficient construction that reduces the number of field multiplications.

#### Round Constants

- `round_constants`: A matrix of size `(rounds_f + rounds_p)` by `t`, represented as `Vec<Vec<Scalar>>`. Each round adds a different constant to each state element.

#### Input and Output

- `input`: Vector of `t` field elements representing the initial state. Elements are `U256Val` objects.

- Return value: Vector of `t` field elements representing the output state after applying the permutation.

#### Error Conditions

The host function will trap if:
- `input` vector length does not equal `t`
-  (Poseidon2 only) `t` is not one of 2, 3, 4, 8, 12, 16, 20, or 24
- `d` is not 5
- `rounds_f` is not even
- `mds` matrix is not `t` by `t` (Poseidon only)
- `mat_internal_diag_m_1` vector length does not equal `t` (Poseidon2 only)
- `round_constants` matrix dimensions are not `(rounds_f + rounds_p)` by `t`
- `field` is neither `BLS12_381` nor `BN254`

#### Cost Metering

The new cost types `Bn254FrToU256`, `Bn254FrAddSub`, `Bn254FrMul`, `Bn254FrPow`, and `Bn254FrInv`, together with the existing `Bn254FrFromU256`, meter BN254 scalar field operations. For BLS12-381 operations, existing cost types from CAP-0059 are used.

The permutation cost is dominated by field multiplications. The cost scales linearly with the number of rounds and quadratically with the state size `t` due to matrix operations.

## Design Rationale

### Permutation Primitives vs. Hash Functions

Poseidon is a family of hash functions built using the sponge construction. The sponge construction consists of two phases:

1. **Absorb**: Input data is absorbed into the state, followed by applying the permutation
2. **Squeeze**: Output is extracted from the state after final permutation

The permutation function $\pi$ is the core cryptographic primitive that provides the one-way and collision-resistant properties.

This CAP exposes the permutation primitives rather than complete hash functions for the following reasons:

**Flexibility**: Different applications require different configurations. For Merkle tree hashing in a binary tree, the rate r=2 and capacity c=1 (state size t=3). For Merkle trees with higher arity or different use cases, different parameters are required. By exposing the permutation, developers can construct hash functions with arbitrary input sizes and security parameters.

**Interoperability**: Different ZK systems use different parameter sets generated according to their security requirements. Exposing the permutation allows Soroban contracts to maintain compatibility with external systems without requiring multiple specialized hash function variants.

**Reduced maintenance surface**: The permutation contains all cryptographic complexity. The sponge construction is a simple state machine that can be efficiently implemented in the SDK guest code. This minimizes the host function surface area that requires cryptographic review.

**Composability**: The Poseidon papers describe multiple constructions beyond basic hashing, including compression functions and variable-length hashing modes. Permutation primitives enable all these constructions without requiring additional host functions.

Example SDK usage for a 2-to-1 hash (pseudo-code):

```rust
pub fn poseidon2_hash_two(input1: Fr, input2: Fr) -> Fr {
    // Initialize state with capacity
    let mut state = vec![Fr::zero(); 3];

    // Absorb inputs
    state[1] = input1;
    state[2] = input2;

    // Apply permutation
    state = poseidon2_permutation(
        state,
        field_type,
        params.t,
        params.d,
        params.rounds_f,
        params.rounds_p,
        params.mat_internal_diag_m_1,
        params.round_constants
    );

    // Squeeze output
    state[0]
}
```

### Parameter Selection

Parameter selection (state size, rounds, matrices, constants) must follow the security analysis in the Poseidon and Poseidon2 papers. The original papers provide reference scripts for generating secure parameter sets. Users are responsible for selecting parameters appropriate to their security level and use case.

Common parameter sets have been published by the Poseidon authors and adopted by various ZK systems. Developers should use established parameter sets when interoperability with existing systems is required.

## Protocol Upgrade Transition

### Backwards Incompatibilities

This CAP does not introduce backward incompatibilities. The new host functions are only available in protocol version 25 and later.

## Security Concerns

### Cryptographic Correctness

The security of Poseidon relies on the correctness of the permutation implementation. Implementation must be carefully vetted and verified against official test vectors. Any deviation from the specification could compromise the desired hash properties.

### Parameter Validation

The host function performs minimal parameter validation (vector lengths, supported S-box degree and state sizes). Scalar inputs are not range-checked: `U256Val` values greater than or equal to the field order are reduced modulo `r`. It does not validate whether the provided parameters (rounds, matrices, constants) constitute a secure configuration. Users are responsible for selecting cryptographically sound parameters.

Insecure parameter selection could result in weakened hash functions vulnerable to collision attacks or preimage attacks. Users should use parameter sets generated according to the methodologies described in the Poseidon and Poseidon2 papers or use widely-adopted standard parameter sets. To mitigate such risk, we will provide presets of securely generated parameters used in production in existing production proof systems (e.g. circom, Noir).

### Denial of Service

The permutation cost scales with the number of rounds and state size. Improper metering could allow attackers to consume excessive resources. The metering implementation must accurately measure the cost of all field operations within the permutation.

The host function does not impose upper bounds on parameter values (beyond vector length consistency). Resource limits are enforced through the standard Soroban metering framework as specified in CAP-0046-10.

## Test Cases

Test vectors will be sourced from:

1. **HorizenLabs Poseidon2 implementation** (https://github.com/HorizenLabs/poseidon2): Provides reference test vectors for Poseidon2 with multiple field types and parameter configurations.

2. **Original Poseidon implementation** (https://extgit.isec.tugraz.at/krypto/hadeshash/): Reference implementation from the original Poseidon paper authors.

## Implementation

Draft implementation: https://github.com/stellar/rs-soroban-env/pull/1608