Data Structures
Memory
The term memory refers to a data structure that gives read access (and possibly write access, too) to elements indicated by an address. Regardless of the data structure, the address lives in the B-field. There are four separate notions of memory:
- RAM, to which the VM can read and write field elements.
- Program Memory, from which the VM reads instructions.
- OpStack Memory, which stores the operational stack.
- Jump Stack Memory, which stores the entire jump stack.
Operational Stack
The stack is a last-in;first-out data structure that allows the program to store intermediate variables, pass arguments, and keep pointers to objects held in RAM. In this document, the operational stack is either referred to as just “stack” or, if more clarity is desired, “OpStack.”
From the Virtual Machine's point of view, the stack is a single, continuous object. The first 16 elements of the stack can be accessed very conveniently. Elements deeper in the stack require removing some of the higher elements, possibly after storing them in RAM.
For reasons of arithmetization, the stack is actually split into two distinct parts:
- the operational stack registers
st0
throughst15
, and - the OpStack Underflow Memory.
The motivation and the interplay between the two parts is described and exemplified in arithmetization of the OpStack table.
Random Access Memory
Triton VM has dedicated Random Access Memory.
It can hold up to many base field elements, where is the Oxfoi prime1.
Programs can read from and write to RAM using instructions read_mem
and write_mem
.
The initial RAM is determined by the entity running Triton VM. Populating RAM this way can be beneficial for a program's execution and proving time, especially if substantial amounts of data from the input streams needs to be persisted in RAM. This initialization is one form of secret input, and one of two mechanisms that make Triton VM a non-deterministic virtual machine. The other mechanism is dedicated instructions.
Jump Stack
Another last-in;first-out data structure that keeps track of return and destination addresses.
This stack changes only when control follows a call
or return
instruction.
Of course, the machine running Triton VM might have stricter limitations: storing or accessing bits TiB of data is a non-trivial engineering feat.