Poseidon Builtin

The Poseidon builtin computes cryptographic hashes using the Poseidon hash function, which is specifically optimized for zero-knowledge proofs and efficient computation in algebraic circuits. As a core component in Cairo's cryptographic operations, it uses the Hades permutation strategy that combines full rounds and partial rounds to achieve both security and performance within STARK proofs.

Poseidon is particularly important for Cairo applications because it offers:

  • Better performance than Pedersen for multiple inputs
  • ZK-friendly design (optimized for constraints in ZK proof systems)
  • Strong cryptographic security properties

Cells Organization

The Poseidon builtin operates with a dedicated memory segment and follows a deduction property pattern:

CellsPurpose
Input cells [0-2]Store input state for Hades permutation
Output cells [3-5]Store computed permutation results

Each operation works with 6 consecutive cells - a block of 3 inputs followed by 3 outputs. When a program reads any output cell, the VM applies the Hades permutation to the input cells and populates all three output cells with the results.

Single Value Hashing Example

valid poseidon builtin segment
Poseidon builtin segment with valid inputs

For hashing a single value (42) in the first instance:

  1. The program writes the value to the first input cell (position 3:0)
  2. The other input cells remain at their default value (0)
  3. When reading the output cell (3:3), the VM:
    • Takes the initial state (42, 0, 0)
    • Applies padding: (42+1, 0, 0) = (43, 0, 0)
    • Computes the Hades permutation
    • Stores the result in output cell 3:3

The permutation result's first component becomes the hash output when hashing a single value.

Sequence Hashing Example

For hashing a sequence of values (73, 91) in the second instance:

  1. The program writes values to the first two input cells (positions 3:6 and 3:7)
  2. Upon reading any output cell, the VM:
    • Takes the state (73, 91, 0)
    • Applies appropriate padding: (73, 91+1, 0)
    • Computes the Hades permutation
    • Stores all three results in the output cells (3:9, 3:10, 3:11)

When hashing sequences, all three output state components may be used for further computation or chaining in multi-round hashing.

Error Condition

invalid poseidon builtin segment
Poseidon builtin segment with invalid input

In this error example:

  • The program attempts to write a relocatable value (pointer to cell 7:1) to input cell 3:0
  • When trying to read output cell 3:3, the VM throws an error
  • The error occurs because the Poseidon builtin can only operate on field elements, not memory addresses

Input validation occurs at the time the output is read, rather than when inputs are written, which is consistent with the deduction property pattern.

Implementation References

These implementation references of the Poseidon builtin in various Cairo VM implementations:

Resources on Poseidon Hash

If you're interested in the Poseidon hash function and its applications: