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 through st15, 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 $p$ many base field elements, where $p$ is the Oxfoi prime¹. 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 $(2^{64} - 2^{32} + 1)^{2}$ bits $\approx 4 \cdot 1 0^{25}$ TiB of data is a non-trivial engineering feat.