# RLP Encoding Circuit

## Transaction (DataType::Tx)

### Legacy Tx

Fields:
1. Nonce: `u64` (1 <= bytes <= 8)
2. Gas Price: `U256` (1 <= bytes <= 32)
3. Gas: `u64` (1 <= bytes <= 8)
4. To: `Address` (bytes == 20)
5. Value: `U256` (1 <= bytes <= 32)
6. Data: `Vec<u8>`

Tags:
- `Tag::TxPrefix`: Denotes the prefix bytes indicating the "length of length" and/or "length" of the tx's RLP-encoding.
- `Tag::TxNonce`: Denotes the byte(s) for the tx's `nonce`.
- `Tag::TxGasPrice`: Denotes the byte(s) for the tx's `gas price`.
- `Tag::TxGas`: Denotes the byte(s) for the tx's `gas`.
- `Tag::TxToPrefix`: Denotes the prefix byte indicating the "length" of the tx's `to`.
- `Tag::TxTo`: Denotes the bytes for the tx's `to`.
- `Tag::TxValue`: Denotes the byte(s) for the tx's `value`.
- `Tag::TxDataPrefix`: Denotes the prefix byte(s) indicating the "length of length" and/or "length" of the tx's `data`.
- `Tag::TxData`: Denotes the bytes for the tx's `data`.

#### Example

##### Fields

- Nonce = 1
- Gas Price = 2
- Gas = 3
- To = [4; 20]
- Value = 5
- Data = [6; 66]

##### Output

[248, 93, 1, 2, 3, 148, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 184, 66, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]

##### Layout

| data_type | tag | tag_index | tag_length | value | index | length_acc |
|-----------|--------------|-----------|------------|-----------|-------|------------|
| Tx | TxPrefix | 2 | 2 | 248 | 95 | 0 |
| Tx | TxPrefix | 1 | 2 | 93 | 94 | 93 |
| Tx | TxNonce | 1 | 1 | 1 | 93 | 0 |
| Tx | TxGasPrice | 1 | 1 | 2 | 92 | 0 |
| Tx | TxGas | 1 | 1 | 3 | 91 | 0 |
| Tx | TxToPrefix | 1 | 1 | 148 | 90 | 0 |
| Tx | TxTo | 20 | 20 | 4 | 89 | 0 |
| Tx | TxTo | 19 | 20 | 4 | 88 | 0 |
| Tx | ... | ... | ... | ... | ... | ... |
| Tx | TxTo | 2 | 20 | 4 | 71 | 0 |
| Tx | TxTo | 1 | 20 | 4 | 70 | 0 |
| Tx | TxValue | 1 | 1 | 5 | 69 | 0 |
| Tx | TxDataPrefix | 2 | 2 | 184 | 68 | 0 |
| Tx | TxDataPrefix | 1 | 2 | 66 | 67 | 66 |
| Tx | TxData | 66 | 66 | 6 | 66 | 0 |
| Tx | TxData | 65 | 66 | 6 | 65 | 0 |
| Tx | ... | ... | ... | ... | ... | ... |
| Tx | TxData | 2 | 66 | 6 | 2 | 0 |
| Tx | TxData | 1 | 66 | 6 | 1 | 0 |

### EIP-1559 Tx

*TODO*

## Log (DataType::Log)

Fields:
1. Status: `u8` (1 byte)
2. Cumulative Gas Used: `u64` (1 <= bytes <= 8)
3. Bloom: `[u8; 256]` (bytes == 256)
4. Logs: `Vec<Log>`
- log.address: `Address` (bytes == 20)
- log.topics: `Vec<H256>`
- topic: `H256` (bytes == 32)
- log.data: `Vec<u8>`

Tags:
- `Prefix`
- `Status`
- `Cumulative Gas Used`
- `BloomPrefix`
- `Bloom`
- `LogsPrefix`
- `LogPrefix`
- `LogAddressPrefix`
- `LogAddress`
- `LogTopicsPrefix`
- `LogTopicPrefix`
- `LogTopic`
- `LogDataPrefix`
- `LogData`

## Circuit Layout

### Columns

1. `q_enable`: Selector that denotes whether this row is enabled in the layout.
2. `q_first`: Fixed column that denotes whether this is the first row in the layout.
3. `q_last`: Selector that denotes whether this is the last row in the layout.
4. `is_final`: Denotes whether the row is the last byte in the RLP-encoded data.
5. `index`: Denotes the index of this row, starting from `1` and ending at `n` where `n` is the byte length of the RLP-encoded data.
6. `rindex`: Denotes the index of this row, but reversed. It starts from `n` where `n` is the byte length of the RLP-encoded data and ends at `1`.
7. `data_type`: Denotes the data type, whether this circuit encodes a `DataType::Tx` or a `DataType::Log`.
8. `value`: Denotes the byte value in the RLP-encoded data.
9. `tag`: Denotes the row's tag, which can be a field from the data type encoded.
10. `tag_index`: Denotes a decrementing index specific to the tag in in the current block of bytes.
11. `tag_length`: Denotes the current tag's length in bytes.
12. `aux_tag_index[0:1]`: Denotes a decrementing index over all nested tags within a parent tag (Receipt.Log).
13. `aux_tag_length[0:1]`: Denotes the aux tag's length in bytes.
14. `length_acc`: Denotes an accumulator for the length of data, in the case where `len > 55` and the length is represented in its big-endian form.
15. `value_rlc`:
- Denotes an accumulator for the value field over all rows.
- `value_rlc = value[0] + r * value[1] + r^2 * value[2] + ... + r^(n-1) * value[n-1]`.
16. `hash`: Denotes the keccak-256 hash of the RLP-encoded data.
17. `keccak_tuple`:
- Denotes a tuple `(keccak_tuple[0], keccak_tuple[1], keccak_tuple[2])` where
- `keccak_tuple[0] -> value_rlc`
- `keccak_tuple[1] -> n`
- `keccak_tuple[2] -> keccak256(rlp_encode(input))`
18. `padding`: Denotes whether the row appears after `is_final`, hence the purpose is padding.

#### Tag check

We use the following logic to check the tag of the current row:
- Allocate `N` columns, where `N` is the number of different tx tags: `is_prefix`, `is_nonce` and so on.
- Allocate `N'` columns, where `N'` is the number of different receipt tags: `is_prefix`, `is_status` and so on.
- Assign to the above columns:
- `0` or `tag.invert()`
- `TagVariant` is the variant value of that column. For instance, in the case of `TxNonce`:
- `val := if (tag::cur == TxTag::TxNonce) 0 else tag::cur.inverse()`
- Calculate boolean whether the row is a certain tag:
- For instance, `is_nonce = 1 - (tag::cur() * val)`.
- If `tag::cur() == TxTag::TxNonce` then `val := 0 => is_nonce := 1`.
- If `tag::cur() != TxTag::TxNonce` then `val := x.inverse()` and `=> is_nonce := 0`.

### Constraints

Common constraints:
- For every row:
- `is_final` is boolean, i.e. `is_final ∈ [0, 1]`.
- `padding` is boolean, i.e. `padding ∈ [0, 1]`.
- For the first row in the circuit, i.e. `q_first == 1`:
- `value_rlc == value`.
- `index == 1`.
- For the subsequent rows:
- `index == index_prev + 1`.
- `rindex == rindex_prev - 1`.
- `hash == hash_prev`.
- `value_rlc == (value_rlc_prev * r) + value`.
- For the last row of the RLP-encoded data, i.e. `(is_final == 1) and (padding == 0)`:
- `(value_rlc, index, rindex, hash) == (keccak_tuple[0], keccak_tuple[1], keccak_tuple[2], keccak_tuple[3])`.
- For all rows except the first row, i.e. `q_first != 1`:
- Padding can go 0 -> 1 only once, i.e. `padding - padding_prev ∈ [0, 1]`.
- For the last row of the layout, i.e. `q_last == 1`:
- The row is either the end of the RLP-encoded data or its a padding row, i.e. `(is_final == 1) or (padding == 1)`.

#### DataType::Tx

- Current row's `tag`: `tag == Tag::TxPrefix`:
- `tag_index <= 9`.
- If `tag_index > 1` then:
- `tag::next == Tag::TxPrefix`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::TxNonce`
- `tag_index::next == tag_length::next`
- `rindex::next == length_acc`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xf8 <= value <= 0xff`
- `tag_index::next == value - 0xf7`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- `length_acc == (length_acc::prev * 256) + value`
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xc0 <= value <= 0xf7`
- `length_acc == value - 0xc0`
- Current row's `tag`: `tag == Tag::TxNonce`:
- `tag_index <= 9`.
- If `tag_index == tag_length` and `tag_length == 1`:
- `value < 0x80`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- `tag_index::next == length_acc`
- If `tag_index > 1` then:
- `tag::next == Tag::TxNonce`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::TxGasPrice`
- `tag_index::next == tag_length::next`
- Current row's `tag`: `tag == Tag::TxGasPrice`:
- `tag_index <= 33`.
- If `tag_index == tag_length` and `tag_length == 1`:
- `value < 0x80`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- `tag_index::next == length_acc`
- If `tag_index > 1` then:
- `tag::next == Tag::TxGasPrice`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::TxGas`
- `tag_index::next == tag_length::next`
- Current row's `tag`: `tag == Tag::TxGas`:
- `tag_index <= 9`.
- If `tag_index == tag_length` and `tag_length == 1`:
- `value < 0x80`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- `tag_index::next == length_acc`
- If `tag_index > 1` then:
- `tag::next == Tag::TxGas`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then `tag::next == Tag::TxToPrefix`.
- Current row's `tag`: `tag == Tag::TxToPrefix`:
- `tag_index == 1`.
- `tag_length == 1`.
- `value == 148`.
- `tag::next == Tag::TxTo`.
- `tag_index::next == 20`.
- `tag_length::next == 20`.
- Current row's `tag`: `tag == Tag::TxTo`:
- `tag_index <= 20`.
- If `tag_index > 1` then:
- `tag::next == Tag::TxTo`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::TxValue`
- `tag_index::next == tag_length::next`
- Current row's `tag`: `tag == Tag::TxValue`:
- `tag_index <= 33`.
- If `tag_index == tag_length` and `tag_length == 1`:
- `value < 0x80`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- `tag_index::next == length_acc`
- If `tag_index > 1` then:
- `tag::next == Tag::TxValue`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then `tag::next == Tag::TxDataPrefix`.
- Current row's `tag`: `tag == Tag::TxDataPrefix`:
- `tag_index <= 9`.
- If `tag_index > 1` then:
- `tag::next == Tag::TxDataPrefix`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- If `length_acc == 0` then `is_final == 1`.
- If `length_acc > 0` then:
- `tag::next == Tag::TxData`.
- `tag_index::next == tag_length::next`.
- `tag_length::next == length_acc`.
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xb8 <= value <= 0xbf`
- `tag_index == (value - 0xb7) + 1`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- `length_acc == (length_acc::prev * 256) + value`
- If `tag_index == tag_length` and `tag_length == 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- Current row's `tag`: `tag == Tag::TxData`:
- If `tag_index > 1` then:
- `tag::next == Tag::TxData`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then `is_final == 1`.

#### DataType::Log

- Current row's `tag`: `tag == Tag::Prefix`:
- `tag_index <= 9`.
- If `tag_index > 1` then:
- `tag::next == Tag::Prefix`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::Status`
- `tag_index::next == tag_length::next`
- `rindex::next == length_acc`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xf8 <= value <= 0xff`
- `tag_index::next == value - 0xf7`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- `length_acc == (length_acc::prev * 256) + value`
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xc0 <= value <= 0xf7`
- `length_acc == value - 0xc0`
- Current row's `tag`: `tag == Tag::Status`:
- `tag_length == 1`.
- `value == 128` or `value == 1`.
- `tag::next == Tag::CumulativeGasUsed`.
- `tag_length::next == tag_index::next`.
- Current row's `tag`: `tag == Tag::CumulativeGasUsed`:
- `tag_index >= 1` and `tag_index <= 9`.
- If `tag_index == tag_length` and `tag_length == 1`:
- `value < 0x80`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0x80 <= value <= 0xb7`
- `length_acc == value - 0x80`
- `tag_index::next == length_acc`
- If `tag_index > 1` then:
- `tag::next == Tag::CumulativeGasUsed`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::BloomPrefix`.
- `tag_index::next == tag_length::next`.
- Current row's `tag`: `tag == Tag::BloomPrefix`:
- `tag_length == 3`. (bloom is 256-bytes, so prefix is [0xf9, 0x01, 0x00])
- If `tag_index == tag_length`:
- `value == 0xf9`.
- If `tag_index > 1` then:
- `tag::next == Tag::BloomPrefix`.
- `tag_index::next == tag_index - 1`.
- `tag_length::next == tag_length`.
- If `tag_index == 1` then:
- `value::prev == 1`.
- `value == 0`.
- `length_acc::prev == 1`.
- `length_acc == 256`.
- `tag::next == Tag::Bloom`.
- `tag_index::next == 256`.
- `tag_length::next == 256`.
- Current row's `tag`: `tag == Tag::Bloom`:
- If `tag_index > 1` then:
- `tag::next == Tag::Bloom`.
- `tag_index::next == tag_index - 1`.
- `tag_length::next == tag_length`.
- If `tag_index == 1` then:
- `tag::next == Tag::LogsPrefix`.
- `tag_index::next == tag_length::next`.
- Current row's `tag`: `tag == Tag::LogsPrefix`:
- `tag_index <= 9`. (TODO: THINK ABOUT REPLACING WITH TAG_LENGTH)
- If `tag_index > 1` then:
- `tag::next == Tag::LogsPrefix`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- If `length_acc == 0` then `is_final == 1`.
- If `length_acc > 0` then:
- `tag::next == Tag::LogPrefix`.
- `tag_index::next == tag_length::next`.
- `rindex::next == length_acc`.
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xf8 <= value <= 0xff`
- `tag_index::next == value - 0xf7`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- `length_acc == (length_acc::prev * 256) + value`
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xc0 <= value <= 0xf7`.
- `length_acc == value - 0xc0`.
- Current row's `tag`: `tag == Tag::LogPrefix`:
- `tag_index <= 9`. (TODO: THINK ABOUT REPLACING WITH TAG_LENGTH)
- If `tag_index > 1` then:
- `tag::next == Tag::LogPrefix`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1` then:
- `tag::next == Tag::Log`
- `tag_index::next == tag_length::next`
- `length_acc == aux_tag_length::next`
- `aux_tag_index::next == aux_tag_length::next`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xf8 <= value <= 0xff`
- `tag_index::next == value - 0xf7`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- `length_acc == (length_acc::prev * 256) + value`
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xc0 <= value <= 0xf7`
- `length_acc == value - 0xc0`
- Current row's `tag`: `tag == Tag::LogAddressPrefix`
- `tag::next == Tag::LogAddress`
- `tag_index::next == tag_length::next`
- `tag_length::next == 20`
- Current row's `tag`: `tag == Tag::LogAddress`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- If `tag_index > 1`:
- `tag::next == Tag::LogAddress`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1`:
- `tag::next == Log::LogTopicsPrefix`
- `tag_index::next == tag_length::next`
- Current row's `tag`: `tag == Tag::LogTopicsPrefix`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xc0 <= value <= 0xf7`
- `tag_index::next == value - 0xc0`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- length_acc == (length_acc::prev * 256) + value.
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xf8 <= value <= 0xff`
- `length_acc == value - 0xc0`
- If `tag_index > 1`:
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- `tag::next == Tag::LogTopicsPrefix`
- If `tag_index == 1`:
- If `length_acc == 0`:
- `tag::next == Tag::LogDataPrefix`
- `tag_index::next == tag_length::next`
- If `length_acc > 0`:
- `tag::next == Tag::LogTopicPrefix`
- Current row's `tag`: `tag == Tag::LogTopicPrefix`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- `tag_length == 1`
- `tag_index == 1`
- `value == 160`
- `tag_length::next == tag_index::next`
- `tag_length::next == 32`
- Current row's `tag`: `tag == Tag::LogTopic`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- If `tag_index > 1`:
- `tag::next == Tag::LogTopic`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1`:
- If `aux_tag_index[1] == 1`:
- `tag::next == Tag::LogDataPrefix`
- If `aux_tag_index[1] > 1`:
- `tag::next == Tag::LogTopicPrefix`
- `tag_index::next == tag_length::next`
- Current row's `tag`: `tag == Tag::LogDataPrefix`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- If `tag_index == tag_length` and `tag_length > 1`:
- `0xc0 <= value <= 0xf7`
- `tag_index::next == value - 0xc0`
- `length_acc == 0`
- If `tag_index < tag_length` and `tag_length > 1`:
- length_acc == (length_acc::prev * 256) + value.
- If `tag_index == tag_length` and `tag_length == 1`:
- `0xf8 <= value <= 0xff`
- `length_acc == value - 0xc0`
- If `tag_index > 1`:
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- `tag::next == Tag::LogDataPrefix`
- If `tag_index == 1`:
- If `length_acc == 0`:
- `aux_tag_index == 1`
- If `rindex > 1`:
- `tag::next == Tag::LogPrefix`
- `tag_index::next == tag_length::next`
- If `length_acc > 0`:
- `tag::next == Tag::LogData`
- Current row's `tag`: `tag == Tag::LogData`
- `aux_tag_length == aux_tag_length::prev`
- `aux_tag_index == aux_tag_index::prev - 1`
- If `tag_index > 1`:
- `tag::next == Tag::LogData`
- `tag_index::next == tag_index - 1`
- `tag_length::next == tag_length`
- If `tag_index == 1`:
- `aux_tag_index == 1`
- If `rindex > 1`:
- `tag::next == Tag::LogPrefix`
- `tag_index::next == tag_length::next`

#### Log
###### Structure

struct Log {
    address: Address,
    topics: Vec<H256>,
    data: Vec<u8>,
}

###### RLP encoding

stream.begin_list(3);
stream.append(&self.address);
stream.append_list(&self.topics);
stream.append(&self.data);

###### Example

Log {
    address: [197, 246, 64, 201, 36, 223, 135, 11, 47, 244, 201, 173, 235, 131, 47, 52, 151, 33, 45, 56],
    topics: [
        [155, 84, 2, 97, 157, 97, 155, 187, 83, 180, 233, 143, 183, 54, 28, 132, 87, 24, 181, 82, 16, 113, 232, 236, 16, 13, 109, 113,
226, 255, 2, 133],
        [135, 54, 24, 24, 197, 175, 122, 58, 171, 240, 207, 233, 36, 226, 197, 139, 116, 182, 27, 112, 53, 190, 238, 112, 171, 154, 203
, 197, 97, 44, 95, 84],
    ],
    data: [5, 4, 3, 2, 1],
}

has an RLP-encoding of:

[
    // log prefix
    248, 95,
    // log address prefix
    148,
    // log address
    197, 246, 64, 201, 36, 223, 135, 11, 47, 244, 201, 173, 235, 131, 47, 52, 151, 33, 45, 56,
    // log topics prefix
    248, 66,
    // log topic prefix
    160,
    // log topic
    155, 84, 2, 97, 157, 97, 155, 187, 83, 180, 233, 143, 183, 54, 28, 132, 87, 24, 181, 82, 16, 113, 232, 236, 16, 13, 109, 113, 226, 255, 2, 133,
    // log topic prefix
    160,
    // log topic
    135, 54, 24, 24, 197, 175, 122, 58, 171, 240, 207, 233, 36, 226, 197, 139, 116, 182, 27, 112, 53, 190, 238, 112, 171, 154, 203, 197, 97, 44, 95, 84,
    // log data prefix
    133,
    // log data
    5, 4, 3, 2, 1
]