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 Range | Purpose | Description |
|---|---|---|
| First 8 cells | Input state s | Each cell stores 200 bits of the 1600-bit input state |
| Next 8 cells | Output state s' | Each cell stores 200 bits of the 1600-bit output state |
The builtin processes each block independently, applying the following rules:
- Input validation: Each input cell must contain a valid field element not exceeding 200 bits (0 ≤ value < 2^200)
- Lazy computation: The output state is only computed when any output cell is accessed
- 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 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:
- StarkNet, Hash Functions - Starknet Keccak
- NIST, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
- Wikipedia, SHA-3 (Secure Hash Algorithm 3)
- Keccak Team, Keccak Reference