## Hash Function

- Poseidon ([paper](https://eprint.iacr.org/2019/458.pdf)).
- Collision and second preimage resistance target: 128 bits.
- On the BN254 scalar field.
- S-box: x^5.
- Full rounds: 8.
- Partial rounds (S-box on the first "capacity" state): 57.
- Constants: `poseidonperm_x5_254_3`, as generated by the [reference Sage implementation](https://extgit.iaik.tugraz.at/krypto/hadeshash/-/blob/b5434fd2b2785926dd1dd386efbef167da57c064/code/poseidonperm_x5_254_3.sage) or the equivalent [Rust implementation](https://github.com/scroll-tech/poseidon-circuit/blob/e3841d0828e577b80c9cd84aa71f79adc96756fc/src/poseidon/primitives.rs#L61).
- Capacity: 1 element.
- Rate: 2 elements.


## Interface Table

The hash circuit exposes a table containing multiple inputs/output pairs. This table can be looked up by the MPT and codehash circuits. The table has four columns: 2 inputs, 1 digest output, 2 for control flags and additional marking.

| 0: Hash index   | 1: Message       | 2: Message      | 3: Control flag | 4: Head flag |
| --------------- | ---------------- | --------------- | --------------- | ------------ |
| MPT digest      | MPT input 1      | MPT input 2     |      0          |      1       |
|                 |                  |                 |                 |              |
| var-len digest  | word 0           | word 1          |  2000*(2^64)    |      1       |
| var-len digest  | word 2           | word 3          |  1968*(2^64)    |      0       |
|      ...        |      ...         |     ...         |     ...         |      0       |
| var-len digest  | word W-2         | word W-1        |  16*(2^64)      |      0       |
|                 |                  |                 |                 |              |


The hash circuit supports two modes:

### MPT Mode

Compute the digest of two message words, as in Merkle trees. This type of entries is identified by the control flag value of 0.

**Initial capacity:** `0`.

**Message encoding:** each message word is a field element; that is, each word is a digest from the previous MPT layer.

### Var-Len Mode

Compute the digest of a variable-length message. One such entry is composed of consecutive rows with the same digest value, and where the control flag is not 0.

**Initial capacity:** `L * 2^64`, with `L` the message length in bytes (before padding).

**Message encoding:** The message is chunked into `W` words of `STEP/2` bytes. Each word is packed into a field element, least-significant-byte first. The words are given two-by-two on consecutive rows in the table, absorbing `STEP` bytes per row. The control flag on a given row indicates the number of message bytes `R` remaining in the current and following rows (and the value is `R * 2^64`). On the last row, `control <= STEP * 2^64`.

**Padding:** the message is padded to a multiple of `STEP` bytes with zeros.

Specifically, `STEP = 32`.

### Legacy scheme

The initial capcity before `scroll-dev-0215` is not multiplied with the domain mark (`2^64`) so they would get different hash results in *var-len* mode. If we wish
to apply the code work under the legacy schema, use `legacy` feature

### Head flag

The head flag is set at each beginning of message, i.e each row under MPT mode and the first row of message in Var-Len mode would be set to 1

### Custom row

2 Additional row is put at the beginning of hash table:

1. A row being filled with 0 for any lookup which is not enabled
2. A row with `control` and `Message` field being set to 0 and the hash is set to a customed value for representing
the hash of empty message. Currently it is set to equal to `keccak256(nil)` and the indexed hash value must be properly set under challenge API

## Internal Table (hash_table_aux)

| Row      | 0: State (capacity) | 1: State (rate) | 2: State (rate) | 3: State-for-next | 4: State-for-next | 5: Hash Out |
| -------- | ------------------- | --------------- | --------------- | ----------------- | ----------------- | ----------- |
| previous |                     |                 |                 |                   |                   |             |
| current  |                     |                 |                 |                   |                   |             |