# Twist and Shout cost comparison

## Read-only memory (a.k.a. lookup)

To show: `[v] in [t]` where
- `v` is of size $n$
- `t` is of size $m$

### Baseline: LogUp + GKR

bus_receive(v, 1);
bus_send(t, m);

Commitment cost:
- `v`: The values being looked up (size $n$)
- `t`: The table (unless MLE-structured) (size $m$)
- `m`: The multilicities (size $m$)

Additional cost:
- Prove bus interaction using GKR ($log(n)$-layer circuit)
- Prove bus interaction using GKR ($log(m)$-layer circuit)

### Shout

Commitment cost:
- `t`: The table (unless MLE-structured) (size $m$)
- `a_1, ..., a_d`: $d$ *sparse* polynomials of size $\sqrt[d]{n \cdot m}$, with $n$ $1$-entries and otherwise zeros. $d$ should be as small as possible such that the commitment scheme supports the commitment size.

Additional cost:
- Sum-check to evaluate the *virtual* polynomial `v`. Degree depends on $d$.
- Various sum-checks to prove that `a_1, ..., a_d` form a one-hot encoding.

### Aplication to zkVMs

- PC lookup: `[pc, opcode, a, b, c, d, e, f] in [...]`
- These are 8 columns on the LHS that have to potentially be committed with LogUp + GKR, but they'd be virtual with Shout!
- The `a_1, ..., a_d` polynomials are only needed once (even though we look up 8 values)
- If $n = 2^{25}$ (time steps) and $m = 2^{25}$ (program size), $d = 2$ would be a reasonable choice

## Read-write memory

In each of the $n$ rows, read a given address `a` into `v` and write a new value `wv` to the same address. The memory size is $m$ (e.g., for RISC-V registers, $m = 32$).

### Baseline: Offline memory checking

bus_receive((a, v, prev_timestamp), 1);
bus_send((a, wv, timestamp), 1);

// Need to assert that prev_timestamp < timestamp
// This is done by decomposing timestamp - prev_timestamp - 1
// into two limbs and range-checking both limbs

timestamp - prev_timestamp - 1 = diff_low + 2**16 * diff_high;
[diff_low] in [BIT16];
[diff_high] in [BIT13];

Commitment cost (assuming `timestamp` exists already):
- `a`: The address (size $n$)
- `v`: The value (size $n$)
- `wv`: The written value (size $n$)
- `prev_timestamp`: The timestamp of the last write to this address (size $n$)
- `diff_low`: Lower limb of `timestamp - prev_timestamp - 1` (size $n$)
- `diff_high`: Higher limb of `timestamp - prev_timestamp - 1` (size $n$)

Additional cost:
- GKR circuits for various bus interactions

### Twist

- `wv`: The written value (size $n$)
- `a_1, ..., a_d`: $d$ *sparse* polynomials of size $\sqrt[d]{n \cdot m}$, with $n$ $1$-entries and otherwise zeros. $d$ should be as small as possible such that the commitment scheme supports the commitment size.
- `Inc`: Another sparse polynomial of size $n \cdot m$ with $n$ non-zero entires, storing the increment of the modified memory cell.
- *Note: Not sure what happens if $n \cdot m$ becomes too large!*

Additional cost:
- Sum-check to evaluate the *virtual* polynomial `v`. Degree depends on $d$.
- Sum-check to evaluate the *virtual* polynomial `a`. Degree depends on $d$.
- Various other sum-checks, see paper for details. No GKR proving though.

### Applications to zkVMs

- Registers:
- For 32 RISC-V registers, $m = 32$ and $d = 1$ should be sufficient. This reduces the commitment cost per register access from 6 to 3 (for a write).
- RAM:
- Here, we'd need larger values of $d$, increasing cost.
- Note tha if all memory accesses are handled with Twist, the `timestamp` can also be removed.