Pedersen Builtin

The Pedersen builtin is dedicated to computing the pedersen hash of two felts. Its use in Cairo is explained on section 11.4 Working with Hashes.

Cells organization

The Pedersen builtin has its own segment during a Cairo VM run. It follows a deduction property, organized by triplets of cells, two input and one output.

  • The input cells must store felts, relocatable are forbidden. It makes sense as you cannot compute the hash of a pointer (unless you allow dereferencing pointers from the builtin...)
  • The output cell is deduced from the input cells. Once an instruction tries reading the cell, the Pedersen hash of the two related input cells is computed and written to the cell.

Let's take a look at two snapshots of a Pedersen segment, during the execution of a dummy program by the Cairo VM.

In the first snapshot, the first triplet has its three cells storing felts and the second one only has its two input cells storing felts.

It means that the Pedersen hash of 15 and 35 has been computed, because the cell 3:2 has been read. The cell 3:5 is still empty while its two input cells are filled with 93 and 5. It means that even if the input cells have been written to, the output cell 3:5 has not been read yet, so the Pedersen hash of 93 and 5 has not been computed yet.

valid pedersen builtin segment
Snapshot 1 - Pedersen builtin segment with valid inputs

On the second snapshot, both triplets of cells would throw an error if their output cell was read.

Why is there an error when trying to read 3:2?

This is because one of the input cells is empty. It's hard to compute a hash of something missing.

Why is there an error when trying to read 3:5?

If you look closely to the related input cells 3:3 and 3:4, you'll notice that the value asserted in 3:4 is a relocatable, a pointer to the cell 1:7. Recall that the Pedersen builtin cannot hash a relocatable value, hence the error.

The error arises when the output cell is read. In the second case, it could have been caught earlier if the input cells were validated as being felts only.

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

Implementation References

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

Resources on Pedersen Hash

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