# public input circuit optimization

## 1. reduce rows of `rpi` column

the call_data part of `tx_table` are of the form:

|tx_id|tag|index|value|
|-|-|-|-|
|1| CallData| 0 | tx[0].call_data[0]|
|1| CallData| 1 | tx[0].call_data[1]|
|1| CallData| 2 | tx[0].call_data[2]|
|1| CallData| ...| tx[0].call_data[...]|
|2| CallData| 0| tx[1].call_data[0]|
|2| CallData| 1| tx[1].call_data[1]|
|2| CallData| ...| tx[1].call_data[...]|
|0| CallData| 0| 0|
|0| CallData| 0| 0|
|...| CallData| 0 | 0|

that is,

- the `tx_id` column satisfy one of the four constraints.
- if `tx_id == 0` then
- `tx_id_next == 0`
- `index == 0`
- `value == 0`

- if `tx_id != 0` then the relation between `tx_id_next` and `tx_id` is one of the three:
1. `tx_id_next - tx_id == 0`
2. `tx_id_next - tx_id - 1 == 0`
3. `tx_id_next == 0`

in the first case, we have
- `index_next - index - 1 == 0`

in the second case, we have
- `index_next == 0`

Therefore, to test if `tx_id` equals to zero, we add an auxiliary column called `tx_id_inv`.

The layout becomes

|tx_id | tag(fixed) | index | value | tx_id_inv| q_is_calldata|
|-|-|-|-|-|-|
|1| CallData| 0 | tx[0].call_data[0]| 1 | 1 |
|1| CallData| 1 | tx[0].call_data[1]| 1 | 1 |
|1| CallData| 2 | tx[0].call_data[2]| 1 | 1 |
|1| CallData| ...| tx[0].call_data[...]| 1| 1 |
|2| CallData| 0| tx[1].call_data[0]| 2^(-1) |1 |
|2| CallData| 1| tx[1].call_data[1]| 2^(-1) |1 |
|2| CallData| ...| tx[1].call_data[...]| 2^(-1) |1 |
|0| CallData| 0| 0| * |1 |
|0| CallData| 0| 0| * |1 |
|...| CallData| 0 | 0| * |1 |

the constraints are

1. `is_tx_id_zero * tx_id_next == 0`
2. `is_tx_id_zero * index == 0`
3. `is_tx_id_zero * value == 0`
4. `is_tx_id_nonzero * (tx_id_next - tx_id) * (tx_id_next - tx_id - 1) * tx_id_next == 0`
5. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id - 1) * (index_next - index) == 0`
6. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id) * index_next = 0`

these constraints are conditioned on selector *`q_is_calldata`*.

## 2. accumulate call data gas cost

the accumulated call data gas cost of an tx can be computed as follows:

tx.call_data_gas_cost = tx.call_data.fold(0, |acc, byte| if *byte == 0 { 4 } else { 16 })

We add another advice column `gas_cost` for accumulate call data gas cost. We also need an auxiliary column `value_inv` for testing if `value` equals to zero.
Finally, we need an boolean flag (`is_final` column) for testing if the current row is the last of an tx.

|tx_id | tag(fixed) | index | value | tx_id_inv| value_inv | gas_cost| is_final| q_is_calldata|
|-|-|-|-|-|-|-|-|-|
|1| CallData| 0 | tx[0].call_data[0]| 1 | | `4*is_value_zero + 16*(1-is_value_zero)`| 0| 1 |
|1| CallData| 1 | tx[0].call_data[1]| 1 | | | 0| 1 |
|1| CallData| 2 | tx[0].call_data[2]| 1 | | | 0| 1 |
|1| CallData| ...| tx[0].call_data[...]| 1| | | 1|1 |
|2| CallData| 0| tx[1].call_data[0]| 2^(-1) | | | 0|1 |
|2| CallData| 1| tx[1].call_data[1]| 2^(-1) | | |0|1 |
|2| CallData| ...| tx[1].call_data[...]| 2^(-1) | | | 1| 1 |
|0| CallData| 0| 0| * | * | 0 | 0| 1 |
|0| CallData| 0| 0| * | * | 0| 0| 1 |
|...| CallData| 0 | 0| * |* | 0 | 0|1 |

similarly, we get the following constraints:

7. `is_tx_id_zero * is_final == 0`
8. `is_tx_id_zero * gas_cost == 0`
9. `gas_next = is_value_next_zero * 4 + (1 - is_value_next_zero) * 16`
10. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id - 1) * (gas_cost_next - gas_cost - gas_next) == 0`
11. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id) * (gas_cost_next - gas_next) = 0`
12. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id - 1) * is_final == 0`
13. `is_tx_id_nonzero * is_tx_id_next_nonzero * (tx_id_next - tx_id) * (is_final - 1) == 0`

## 3. make the call_data_gas_cost public

Assert `call_data_gas_cost` assigned (in `value` column) equals to the accumulated in the `gas_cost` column.

We use lookup argument to make the assertion.
- If the call_data_length != 0, then the input expr `(tx_id, true, value_next)` of the row where `tag = CallDataLength` is always contained in the table expr `(tx_id, is_final, gas_cost)`.
- If the call_data_length == 0, then the input expr `(tx_id * 0, true * 0, value_next * 0) = (0, 0, 0)` is also contained in the `(tx_id, is_final, gas_cost)` table .

That is, the lookup argument is

[
   (condition * tx_id, tx_id),
   (condition * 1, is_final),
   (condition * value_next, calldata_gas_cost)
]

where the `condition` is `q_tx_table * is_calldata_length_nonzero * is_calldata_length_row`.