Poseidon Builtin

The Poseidon builtin is dedicated to computing the Poseidon hash in Cairo VM. It is specifically designed for efficient computation in algebraic circuits and is a core component in Cairo's cryptographic operations. It uses the Hades permutation strategy, which combines full rounds and partial rounds to achieve both security and efficiency in zero-knowledge STARK proofs.

Cells organization

The Poseidon builtin has a dedicated segment in the Cairo VM. It follows a deduction property where input cells store the integer values to be hashed, and output cells store the computed hash results. The values in the output cells are deduced from the values in the input cells upon accessing them. Once an instruction tries reading an output cell, the VM computes the Poseidon hash by applying Hades permutations on the input cells.

The Poseidon builtin operates in instances of 6 cells during VM execution. Each instance contains:

  • Three input cells [0-2] for the Hades permutation inputs
  • Three output cells [3-5] for storing computed hash results

Let's examine two snapshots of a Poseidon segment during the execution of a dummy program by the Cairo VM.

In the first snapshot, we see both single-value and sequence hashing:

valid poseidon builtin segment
Snapshot 1 - Poseidon builtin segment with valid inputs

When hashing a value 42, the computation proceeds as:

  1. Value is added to initial state (s0 = 42)
  2. During finalization: hades_permutation(43, 0, 0) is computed (s0 + 1, s1, s2)
  3. First element of permutation result becomes the hash i.e. cell 3:3

For sequence [73, 91]:

  1. First value updates s0 = 73
  2. Second value updates s1 = 91
  3. During finalization: hades_permutation(73, 91, 0) is computed (s0, s1+1, s2)
  4. All three output states are stored in respective sequential cells for further rounds

In the second snapshot, we see error conditions:

invalid poseidon builtin segment
Snapshot 1 - Poseidon builtin segment with invalid input

When trying to read 3:3, an error occurs because the input in 3:0 is a relocatable value (pointer to cell 7:1). The Poseidon builtin cannot hash relocatable values - it only operates on field elements - and the VM will panic.

Implementation References

These implementation references of the Poseidon builtin might not be exhaustive.

Resources on Poseidon Hash

If you're interested about the Poseidon hash and its use, take a look at those references: