0xMiden / 0xMiden/miden-vm

Expantion of VM operation slots from 96 to 104 or 120

Aperta
#2,983 2 commenti 1 reazione 0 assegnatari Vedi su GitHub
instruction set
Lingua principale
Rust
Stelle
772
Fork
352
Merge medio
1g 12h
PR unite (30g)
93

Descrizione

We currently have 96 operation slots of which 93 are used, leaving only 3 free. This severely limits our ability to add new instructions. For context, the expansion from 88 to 96 slots was done in #887 (motivated by #884).

We propose two options that reclaim unused opcode bits in the `11` prefix group (degree-4 operations), trading 1 or 2 extra trace columns for 8 or 24 new slots, respectively.

## Background

The 7-bit opcode space is partitioned into four groups. A more intuitive way to view them is by how each family's flags are formed under the system-wide degree-9 bound:

| Valid opcode pattern | How flags are formed | Slots | Flag degree | Remaining degree budget |
|----------------------|----------------------|-------|-------------|-------------------------|
| `0xxxxxx` | use all 7 opcode bits directly | 64 | 7 | 2 |
| `100xxx-` | force `b0 = 0`, then use the remaining 6 bits directly | 8 | 6 | 3 |
| `101xxxx` | use `e0 = b6 * (1-b5) * b4` plus `b3..b0` | 16 | 5 | 4 |
| `11xxx--` | use `e1 = b6 * b5` plus `b4..b2`, and force `b1 = b0 = 0` | 8 | 4 | 5 |

So:
- `e0` reduces the `101` family from degree 7 to degree 5.
- `e1` reduces the `11` family from degree 6 to degree 4, but only after additionally forcing `b0 = b1 = 0`.

Here is an overview over the 8 current degree-4 operations for latter use:

| Op | Opcode | b4 | b3 | b2 |
|-------------|--------|----|----|-----|
| MRUPDATE | 96 | 0 | 0 | 0 |
| CRYPTOSTREAM | 100 | 0 | 1 | 0 |
| SYSCALL | 104 | 0 | 0 | 1 |
| CALL | 108 | 0 | 1 | 1 |
| END | 112 | 1 | 0 | 0 |
| REPEAT | 116 | 1 | 0 | 1 |
| RESPAN | 120 | 1 | 1 | 0 |
| HALT | 124 | 1 | 1 | 1 |

## Option A: +1 column, +8 slots

### Design

Add one degree-reduction column:

```
e2 = e1 * b4 (= b6 * b5 * b4)
```

Remove the constraint `very_high_prefix * b0 = 0`, freeing b0 as a discriminating bit. The complementary selector `e1 - e2` (= $b6\*b5\*(1-b4$)) comes for free as a degree two selector

Each degree-4 flag now uses 3 discriminating bits (b0, b2, b3) times a degree-1 selector:

| Subgroup | Selector | Flag degree | Slots |
|----------|----------|-------------|-------|
| b4=1 | e2 | 4 | 8 (4 existing + 4 new) |
| b4=0 | e1 - e2 | 4 | 8 (4 existing + 4 new) |

All 16 flags have degree 4 which is nice, both for the current and future ops.

## Option B: +2 columns, +24 slots

### Design

Add two degree-reduction columns:

```
e2 = e1 * b4 (= b6 * b5 * b4)
e3 = e2 * (1 - b3) (= b6 * b5 * b4 * (1 - b3))
```

Remove both constraints `very_high_prefix * b0 = 0` and `very_high_prefix * b1 = 0`, freeing b0 and b1.

The asymmetric split gives three subgroups:

| Subgroup | Selector | Flag degree | Slots | Current ops |
|----------|----------|-------------|-------|-------------|
| b4=1, b3=0 | e3 | **4** | 8 | END, REPEAT |
| b4=1, b3=1 | e2 - e3 | **4** | 8 | RESPAN, HALT |
| b4=0 | e1 - e2 | **5** | 16 | MRUPDATE, CRYPTOSTREAM, SYSCALL, CALL |

The b4=1 ops, including the END/REPEAT pair which is involved in the degree 9 constraint

```
f_end * f_repeat_next * (hi_next - hi) = 0
```
stay at degree 4.

The b4=0 ops rise to degree 5 but after doing a thorough pass, it looks like all current constraints for the ops in this group should be able to absorb this degree increase. More precisely:

- **`MRUPDATE`**: participates in `no_shift_flags` and the chiplets bus request; both remain below degree 9.
- **`CRYPTOSTREAM`**: directly gates its stack-crypto constraints and a chiplets-bus request; both remain below degree 9.
- **`SYSCALL`**: feeds `control_flow`, block stack / decoder buses, and system-context transitions; these remain below degree 9.
- **`CALL`**: feeds `control_flow`, `no_shift_flags`, block stack / decoder buses, and system ctx/fn-hash transitions; these remain below degree 9.
- **Additive composites** (`control_flow`, `no_shift_flags`): dominated by pre-existing degree-5/7 terms, so adding more degree-5 terms does not raise the composite degree.
- **Stack depth**: `call_or_dyncall_or_syscall` is additive, dominated by DYNCALL (degree 5).

Guida per i contributori

Apri la guida per i contributori

Valutazione

Questa issue non è ancora stata valutata.

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.