---
# System prepended metadata

title: Twist and Shout cost comparison

---

# 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.