Keccak Builtin

The Keccak builtin implements the core functionality of the SHA-3 family of hash functions. It computes the new state s' by applying the 24 rounds of the keccak-f1600 permutation to an input state s. This builtin is particularly important for Ethereum compatibility, as Ethereum uses Keccak-256 for various cryptographic operations.

Cells Organization

The Keccak builtin uses a dedicated memory segment organized in blocks of 16 consecutive cells:

Cell RangePurposeDescription
First 8 cellsInput state sEach cell stores 200 bits of the 1600-bit input state
Next 8 cellsOutput state s'Each cell stores 200 bits of the 1600-bit output state

The builtin processes each block independently, applying the following rules:

  1. Input validation: Each input cell must contain a valid field element not exceeding 200 bits (0 ≤ value < 2^200)
  2. Lazy computation: The output state is only computed when any output cell is accessed
  3. Caching: Once computed, results are cached to avoid redundant calculations if other output cells from the same block are accessed

Example Operation

keccak builtin segment
Keccak builtin segment with a complete operation

In this example:

  • The program has written input values [0x1, 0x2, 0x3, 0x4, 0x5, 0x6, 0x7, 0x8] to the first 8 cells
  • Upon reading any of the output cells, the VM computes the keccak-f1600 permutation on the entire state
  • The resulting output state is stored in the next 8 cells
  • The computation happens only once per block and is cached

Error Conditions

The Keccak builtin will throw an error in the following scenarios:

  • If any input cell contains a value that exceeds 200 bits (≥ 2^200)
  • If any input cell contains a relocatable value (pointer) instead of a field element
  • If an output cell is read before all eight input cells have been initialized

Implementation References

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

Resources on Keccak Hash

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