tasm-lib
This repository contains a collection of functions written in Triton VM assembly (tasm). The functions supplied here emulate the standard library of other programming languages: basic functions that are used a lot.
There are two big projects to be written in tasm. They are not contained in this repository. These projects are:
- The consensus logic of Neptune
- The recursive Triton VM STARK verifier (recufier)
This repository helps to benchmark snippets written in tasm in order to gauge the complexity of the (Triton VM) prover.
Please place code in the appropriate directories, or create them if non-existent.
Conventions
Memory
Triton-VM has $P = 2^{64} - 2^{32} + 1$ number of words in its RAM, where each word is a prime field element in the prime $P$, colloquially called "0xfoi" due to its hexadecimal representation. RAM can be initialized at startup by setting non-determinism (ND).
Memory is, by convention, divided up into chunks called pages. All pages, except the last one, have a size of $2^{32}$ words. The last page has a size of $1$. Memory consists of $2^{32}$ pages.
| pages | region | size in words | category | purpose |
|---|---|---|---|---|
| $0$ | $[0, 2^{32})$ | $2^{32}$ | non-deterministic | for pre-loaded data |
| $[1,2^{31})$ | $[2^{32}, 2^{63})$ | $2^{63}-2^{32}$ | dynamic | run-time data |
| $[2^{31},2^{32}-4)$ | $[2^{63}, 2^{34})$ | $2^{63}-2^{34}$ | static | not reserved |
| $2^{32}-4$ and $2^{32}-3$ | $[2^{64}-2^{34},2^{64}-2^{33})$ | $2^{33}$ | static | Reserved for STARK-verifier |
| $2^{32}-2$ | $[2^{64}-2^{33}, 2^{64}-2^{32})$ | $2^{32}$ | static | available for Library::kmalloc |
| $2^{32}-1$ | $[2^{64}-2^{32}, 0)$ | $1$ | static | state of DynMalloc snippet |
- The first memory page, page 0, the address region $[0, 2^{32})$, is reserved for pre-loaded data. Note that $0$ is included and $2^{32}$ is excluded.
- The address region $[2^{32}, 2^{63})$ is used for dynamically allocated memory, memory that was allocated at runtime. The address $-1$ (the last page) handles the state of the dynamic allocator. The dynamic allocator checks at runtime that it is not allocating outside of its region. Note that $-1 = 2^{64} - 2^{32}$ in this prime field.
- Statically allocated memory, which is reserved by snippets and compiled code, starts at address $-2$ and grows downwards. The
kmallocmethod onLibrarycan allocate from $-2$ down to (and including) $-2^{32}-1 = 2^{64}-2^{33}+1$. The rest of memory is also considered static, but cannot be accessed usingkmalloc. Individual snippets are allowed to use the range from $[2^{63}, 2^{64}-2^{33})$. But the two last pages, the range $[2^{64}-2^{34},2^{64}-2^{33})$, is used by the snippet that verifies the VM's own proofs.
The memory conventions above are (read: should be) enforced by the code in this library. They are not enforced by Triton VM. This means that any of the following behaviors are considered a bug if there exists a non-deterministic input to Triton VM that allows the user to
- Read before writing of any address outside of the ND region $[0, 2^{32})$.
- Write to the ND region
- Write to a dynamically-resolved address outside of the region for dynamically allocated memory.
- Perform any read or write in the non-reserved pages.
Additionally, a pointer that is resolved dynamically must only be resolved at most one time for each instance. This means that memory offsets defined in memory must be resolved and kept on stack or in static memory thoughout the execution of the program. They must not be resolved multiple times, as the memory could have changed in between two pointer resolutions.
U64
A u64 type is stored on the stack as two u32 elements. Triton VM provides native support for u32. A u64 is stored with the least significant part on top of the stack and the most significant part below it. So if the least significant part is st0, then the most significant part is stored in st1.
U128
a u128 is represented by four u32 values, where each value takes up a word of space in the VM. u128 follow a similar encoding to that of u64: The least significant u32 value is stored on top of the stack, in st0.
Runtimes
Runtimes are printed in the JSON files in the benchmarks directory. These benchmarks count the number of clock cycles it took to execute each benchmark. They also count co-processor use, like u32-table height and hash-table height.
The benchmark results are generated by tests labeled as benchmark. If you manage to lower any of the numbers by changing a TASM snippet, please make a pull request, so we can get more efficient algorithms :)
All benchmark results must be deterministic. Any benchmark that does not always generate the same numbers is a bug.