Poseidon on PolkaVM

Poseidon is a cryptographic hash function designed specifically for zero-knowledge proof systems (like zk-SNARKs and zk-STARKs), where it needs to be efficient to compute inside arithmetic circuits. It works by processing input data through multiple rounds of substitution-permutation network (SPN) operations over a finite field, using only addition, multiplication, and power functions with small exponents (typically $x^5$ or $x^3$).

Unlike traditional hash functions (SHA-256, Blake2) that use bitwise operations and modular arithmetic—operations expensive to represent in circuits—Poseidon's arithmetic-friendly design minimizes the number of constraints needed in zk-proofs.

Core Structure

The hash consists of three main operations:

1. AddRoundConstants — adding fixed field elements
2. S-Boxes — applying the power function to a subset of state elements
3. MixLayer — multiplying the state by an MDS matrix for diffusion

By carefully balancing full rounds (S-Boxes applied to all elements) with partial rounds (S-Boxes applied to just one element), Poseidon achieves both security and circuit efficiency, making it the go-to choice for hashing in modern blockchain scaling solutions and privacy protocols.

Poseidon White paper - POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems

The solidity implementation was not working for PolkaVM and Kusama Assethub so we decided to port it to PolkaVM.

Repo:

https://codeberg.org/KusamaShield/PoseidonPolkaVM

Call the poseidon hasher on-chain:

cast call 0x1d165f6fE5A30422E0E2140e91C8A9B800380637 "hash(uint256[2]):(uint256)" "[123,456]" --rpc-url https://eth-rpc-testnet.polkadot.io

19620391833206800292073497099357851348339828238212863168390691880932172496143

Use:

Kusama Shield utilize Poseidon in it's on-chain merkle tree.

Compatibility:

PoseidonPolkaVM is compatible with:

• Circom
  https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom
• Light-Poseidon
  https://www.npmjs.com/package/poseidon-lite
• Solidity
  Example usecase:
  https://codeberg.org/KusamaShield/Solidity_helpers/src/branch/main/contracts/paseo/InternalLeanIMT.sol

Making it easy to integrate into your smart contract zk logic on Kusama Assethub.

How Poseidon Works in PoseidonPolkaVM

This document explains the Poseidon hash function as implemented in this repository — a PolkaVM-compatible, Solidity-friendly port built on the BN254 scalar field with Montgomery arithmetic.

Table of Contents

• Overview
• The BN254 Finite Field
• Montgomery Form Arithmetic
• The Poseidon Permutation
  • State Initialization
  • Add Round Constants (ARK)
  • S-box Layer
  • MDS Matrix Multiplication
  • Full Rounds vs Partial Rounds
• Parameters
• Solidity / PolkaVM Interface
• Lean Indexed Merkle Tree
• Test Vectors

Overview

Poseidon is a cryptographic hash function designed specifically for zero-knowledge proof systems. Unlike general-purpose hash functions (SHA-256, Keccak), Poseidon operates natively over prime fields, making it extremely efficient inside arithmetic circuits (SNARKs, STARKs).

This implementation:

• Targets the BN254 scalar field (the same field used by Ethereum's ecPairing precompile and Circom/Groth16).
• Uses arity 2: it takes two field elements as input and produces one field element as output.
• Is fully compatible with CircomZK / Solidity Poseidon libraries (same constants, same outputs).
• Runs on PolkaVM (Polkadot's RISC-V based virtual machine) as a smart contract.

Reference: Poseidon: A New Hash Function for Zero-Knowledge Proof Systems (2019)

The BN254 Finite Field

All arithmetic happens in the scalar field of the BN254 (alt_bn128) elliptic curve. This is the field of integers modulo the prime:

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

In hex:

p = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001

A field element is represented as four 64-bit limbs (little-endian):

#![allow(unused)]
fn main() {
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Fr([u64; 4]);  // 256-bit field element
}

All operations (addition, multiplication) produce results in the range [0, p-1].

Montgomery Form Arithmetic

Direct modular arithmetic requires expensive division for every reduction step. This implementation avoids that by using Montgomery form, where every field element a is stored as:

a_mont = a * R mod p     where R = 2^256

Why Montgomery Form?

The key insight is that Montgomery multiplication computes:

MontMul(a_mont, b_mont) = a_mont * b_mont * R^(-1) mod p
                         = (a * R) * (b * R) * R^(-1) mod p
                         = a * b * R mod p
                         = (a * b)_mont

This replaces modular division with shifts and additions, which is much faster.

Key Constants

Conversion

• Normal to Montgomery: a_mont = MontMul(a, R^2) = a * R^2 * R^(-1) = a * R mod p
• Montgomery to Normal: a = MontMul(a_mont, 1) = a_mont * 1 * R^(-1) = a * R * R^(-1) = a mod p

CIOS Multiplication Algorithm

The implementation uses the Coarsely Integrated Operand Scanning (CIOS) variant of Montgomery multiplication (src/zk.rs). For each limb i of the multiplier:

1. Multiply-accumulate: Compute partial products a[j] * b[i] and accumulate into a temporary buffer t[0..5].
2. Reduce: Compute m = t[0] * INV mod 2^64, then add m * MODULUS to cancel out the lowest limb.
3. Shift: Move the result down by one limb position.
4. Final subtraction: If the result exceeds p, subtract p once.

Addition

Field addition computes a + b mod p using 128-bit additions with carry propagation, followed by a conditional subtraction of p if the result overflows.

The Poseidon Permutation

The Poseidon hash applies a sponge construction with a specialized permutation. Here is the complete flow:

State Initialization

The state is a vector of T = 3 field elements (state width = arity + 1):

state = [0, input[0], input[1]]

The first element (index 0) is the capacity element, initialized to zero. The remaining elements hold the inputs.

The Round Function

Each of the 65 rounds applies three layers in sequence:

┌──────────────────────────────────────────────────────────────────────┐
│  For each round r = 0..64:                                           │
│                                                                      │
│  1. ARK:  state[i] += ROUND_CONSTANTS[r * 3 + i]   for i in 0..3   │
│  2. SBOX: state[i]  = state[i]^5                    (full or partial)│
│  3. MDS:  state      = MDS_MATRIX * state                            │
│                                                                      │
└──────────────────────────────────────────────────────────────────────┘

Add Round Constants (ARK)

Each round adds a unique set of constants to the state. There are 195 round constants total (65 rounds x 3 state elements). These constants are generated deterministically using the Grain LFSR as specified in the Poseidon paper:

sage generate_parameters_grain.sage 1 0 254 3 8 57 <field_prime>

The constants are pre-computed and stored in Montgomery form in ROUND_CONSTANTS.

S-box Layer

The S-box is the non-linear component that provides cryptographic security. It computes x^5 (alpha = 5):

#![allow(unused)]
fn main() {
fn sbox(x: &Fr) -> Fr {
    let x2 = x.mul(x);       // x^2   (1 multiplication)
    let x4 = x2.mul(&x2);    // x^4   (1 multiplication)
    x4.mul(x)                 // x^5   (1 multiplication)
}
}

This is computed in 3 multiplications using the addition chain: 1 -> 2 -> 4 -> 5.

MDS Matrix Multiplication

The Maximum Distance Separable (MDS) matrix provides diffusion — it ensures that every input bit affects every output bit. The 3x3 MDS matrix multiplication is:

new_state[0] = MDS[0][0]*state[0] + MDS[0][1]*state[1] + MDS[0][2]*state[2]
new_state[1] = MDS[1][0]*state[0] + MDS[1][1]*state[1] + MDS[1][2]*state[2]
new_state[2] = MDS[2][0]*state[0] + MDS[2][1]*state[1] + MDS[2][2]*state[2]

The MDS matrix is a fixed, pre-computed constant derived from a Cauchy matrix, stored in Montgomery form. It is the same matrix used by the circomlib Poseidon implementation, ensuring output compatibility.

Full Rounds vs Partial Rounds

This is the key optimization of Poseidon over earlier designs:

Round 0  ─┐
Round 1   │  Full Rounds (first half: 4 rounds)
Round 2   │  → S-box applied to ALL 3 state elements
Round 3  ─┘
Round 4  ─┐
  ...      │  Partial Rounds (57 rounds)
  ...      │  → S-box applied ONLY to state[0]
Round 60 ─┘
Round 61 ─┐
Round 62  │  Full Rounds (second half: 4 rounds)
Round 63  │  → S-box applied to ALL 3 state elements
Round 64 ─┘

• Full rounds (8 total, split 4+4): Apply x^5 to every state element. This provides wide diffusion at the start and end.
• Partial rounds (57 total): Apply x^5 only to state[0]. The MDS matrix still spreads the non-linearity to all elements.

This "sandwich" structure (full-partial-full) dramatically reduces the number of multiplications while maintaining the same security level. In arithmetic circuits (ZK proofs), this translates to far fewer constraints.

Output

After all 65 rounds, the hash output is state[0] — the capacity element:

#![allow(unused)]
fn main() {
pub fn poseidon(inputs: &[Fr; 2]) -> Fr {
    // ... 65 rounds of ARK + SBOX + MDS ...
    state[0]  // Return first element
}
}

Parameters

Solidity / PolkaVM Interface

The hash function is exposed as a PolkaVM smart contract with a Solidity-compatible ABI:

function hash(uint256[2] memory input) external pure returns (uint256);

Function selector: 0x561558fe

Call Flow

Solidity caller
     │
     ▼
ABI-encoded calldata (68 bytes)
  [4-byte selector][32-byte uint256][32-byte uint256]
     │
     ▼
Decode via ethabi
     │
     ▼
Convert big-endian bytes → little-endian u64 limbs → Fr (Montgomery form)
     │
     ▼
poseidon(&[fr_a, fr_b])
     │
     ▼
Convert Fr → limbs → big-endian bytes (32 bytes)
     │
     ▼
Return via PolkaVM UAPI

Byte Order Conversion

Ethereum uses big-endian 256-bit integers. The Fr type uses little-endian 64-bit limbs. The conversion reverses the limb order and byte order:

Ethereum:  [byte_0, byte_1, ..., byte_31]     (big-endian)
           ────────────────────────────────
Fr limbs:  [limb_0, limb_1, limb_2, limb_3]   (little-endian)
           where limb_0 = least significant 64 bits

Lean Indexed Merkle Tree

The repository also includes a generic Lean Indexed Merkle Tree (src/leanimt.rs) that can use Poseidon as its hash function. This is a binary Merkle tree where:

• Leaves are hashed pairwise up to a single root.
• New leaves can be inserted incrementally without rebuilding the entire tree.
• The tree depth grows as needed.

This is useful for building commitment schemes and membership proofs in ZK applications.

Test Vectors

These test vectors are verified against the reference CircomZK/Solidity Poseidon implementations: