Pedersen Builtin

The Pedersen builtin is dedicated to computing the Pedersen hash of two field elements (felts). It provides an efficient, native implementation of this cryptographic hash function within the Cairo VM. For a guide on using hashes in Cairo programs, see section 11.4 Working with Hashes.

Cells Organization

The Pedersen builtin has its own dedicated segment during a Cairo VM run. It follows a deduction property pattern and is organized in triplets of cells - two input cells and one output cell:

  • Input cells: Must store field elements (felts); relocatable values (pointers) are forbidden. This restriction makes sense because computing the hash of a memory address is not well-defined in this context.
  • Output cell: The value is deduced from the input cells. When an instruction tries to read this cell, the VM computes the Pedersen hash of the two input cells and writes the result to the output cell.

Let's examine two snapshots of a Pedersen segment during the execution of a program by the Cairo VM:

In the first snapshot, we see two triplets in different states:

valid pedersen builtin segment
Snapshot 1 - Pedersen builtin segment with valid inputs
  • First triplet (cells 3:0, 3:1, 3:2): All three cells contain felts. The value in cell 3:2 (output) has been computed because this cell has been read during program execution, which triggered the Pedersen hash computation of inputs 15 and 35.
  • Second triplet (cells 3:3, 3:4, 3:5): Only the input cells have been filled with values 93 and 5. The output cell 3:5 remains empty because it hasn't been read yet, so the Pedersen hash of 93 and 5 hasn't been computed yet.

In the second snapshot, we see two cases that would cause errors when attempting to read the output cell:

Invalid pedersen builtin segment
Snapshot 2 - Pedersen builtin segment with invalid inputs

  1. First triplet: Reading cell 3:2 would throw an error because one of the input cells (3:0) is empty. The VM cannot compute a hash with missing input data.

  2. Second triplet: Reading cell 3:5 would throw an error because one of the input cells (3:4) contains a relocatable value pointing to cell 1:7. The Pedersen builtin can only hash field elements, not memory addresses.

Note that these errors only manifest when the output cell is read. For the second case, a more robust implementation could validate the input cells when they're written, rejecting relocatable values immediately rather than waiting until the hash computation is attempted.

Implementation References

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

Resources on Pedersen Hash

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