Arithmetization Overview
Tables
| table name | #main cols | #aux cols | total width |
|---|---|---|---|
| ProgramTable | 7 | 3 | 16 |
| ProcessorTable | 39 | 11 | 72 |
| OpStackTable | 4 | 2 | 10 |
| RamTable | 7 | 6 | 25 |
| JumpStackTable | 5 | 2 | 11 |
| HashTable | 67 | 20 | 127 |
| CascadeTable | 6 | 2 | 12 |
| LookupTable | 4 | 2 | 10 |
| U32Table | 10 | 1 | 13 |
| DegreeLowering (-/8/4) | 0/118/230 | 0/14/38 | 0/160/344 |
| Randomizers | 0 | 1 | 3 |
| TOTAL | 149/267/379 | 50/64/88 | 299/459/643 |
Constraints
The following table captures the state of affairs in terms of constraints before automatic degree lowering. In particular, automatic degree lowering introduces new columns, modifies the constraint set (in a way that is equivalent to what was there before), and lowers the constraints' maximal degree.
Before automatic degree lowering:
| table name | #initial | #consistency | #transition | #terminal | max degree |
|---|---|---|---|---|---|
| ProgramTable | 6 | 4 | 10 | 2 | 4 |
| ProcessorTable | 29 | 10 | 41 | 1 | 19 |
| OpStackTable | 3 | 0 | 5 | 0 | 4 |
| RamTable | 7 | 0 | 12 | 1 | 5 |
| JumpStackTable | 6 | 0 | 6 | 0 | 5 |
| HashTable | 22 | 45 | 47 | 2 | 9 |
| CascadeTable | 2 | 1 | 3 | 0 | 4 |
| LookupTable | 3 | 1 | 4 | 1 | 3 |
| U32Table | 1 | 15 | 22 | 2 | 12 |
| Grand Cross-Table Argument | 0 | 0 | 0 | 14 | 1 |
| TOTAL | 79 | 76 | 150 | 23 | 19 |
| (# nodes) | (534) | (624) | (6679) | (213) |
After lowering degree to 8:
| table name | #initial | #consistency | #transition | #terminal |
|---|---|---|---|---|
| ProgramTable | 6 | 4 | 10 | 2 |
| ProcessorTable | 29 | 10 | 165 | 1 |
| OpStackTable | 3 | 0 | 5 | 0 |
| RamTable | 7 | 0 | 12 | 1 |
| JumpStackTable | 6 | 0 | 6 | 0 |
| HashTable | 22 | 46 | 49 | 2 |
| CascadeTable | 2 | 1 | 3 | 0 |
| LookupTable | 3 | 1 | 4 | 1 |
| U32Table | 1 | 18 | 24 | 2 |
| Grand Cross-Table Argument | 0 | 0 | 0 | 14 |
| TOTAL | 79 | 80 | 278 | 23 |
| (# nodes) | (534) | (635) | (6956) | (213) |
After lowering degree to 4:
| table name | #initial | #consistency | #transition | #terminal |
|---|---|---|---|---|
| ProgramTable | 6 | 4 | 10 | 2 |
| ProcessorTable | 31 | 10 | 238 | 1 |
| OpStackTable | 3 | 0 | 5 | 0 |
| RamTable | 7 | 0 | 13 | 1 |
| JumpStackTable | 6 | 0 | 7 | 0 |
| HashTable | 22 | 52 | 84 | 2 |
| CascadeTable | 2 | 1 | 3 | 0 |
| LookupTable | 3 | 1 | 4 | 1 |
| U32Table | 1 | 26 | 34 | 2 |
| Grand Cross-Table Argument | 0 | 0 | 0 | 14 |
| TOTAL | 81 | 94 | 398 | 23 |
| (# nodes) | (538) | (676) | (7246) | (213) |
Triton Assembly Constraint Evaluation
Triton VM's recursive verifier needs to evaluate Triton VM's AIR constraints. In order to gauge the runtime cost for this step, the following table provides estimates for that step's contribution to various tables.
| Type | Processor | Op Stack | RAM |
|---|---|---|---|
| static | 37759 | 70227 | 24996 |
| dynamic | 49456 | 78029 | 28895 |
Opcode Pressure
When changing existing or introducing new instructions, one consideration is: how many other instructions compete for opcodes in the same instruction category? The table below helps answer this question at a glance.
| IsU32 | ShrinksStack | HasArg | Num Opcodes |
|---|---|---|---|
| n | n | n | 12 |
| n | n | y | 10 |
| n | y | n | 11 |
| n | y | y | 3 |
| y | n | n | 6 |
| y | n | y | 0 |
| y | y | n | 4 |
| y | y | y | 0 |
Maximum number of opcodes per row is 16.