TinyRAM Review: Architecture, Design, and Assembly Instructions

Last week, we talked about Layer2 interoperability and compared StarkEx, Loopring, Hermez, and Connext, which adopt different methods to solve the funding efficiency problem after introducing a liquidity provider to aggregate multiple transactions into a single transaction. Today, we take a deep look at TinyRAM, a random-access architecture designed to be a convenient tool for expressing the provability of non-deterministic computations.

TinyRAM was proposed by the famous BCGTV group, i.e., Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza, together with the SCIPR Lab. Specifically, TinyRAM is a Reduced Instruction Set Computer (RISC) with byte-level addressable random-access memory. It strikes a balance between two opposing requirements — “sufficient expressibility” and “small instruction set”:

(1) Sufficient expressibility to support short, efficient assembly code when compiled from high-level programming languages, and (2) Small instruction set to support simple verification via arithmetic circuits and efficient verification using SCIPR’s algorithms and cryptographic mechanisms.

Architecture

TinyRAM is parameterized by two integers — the word size, denoted W, which must be a power of 2 and divisible by 8 (as in modern computers, e.g., 32, 64), and the number of registers, denoted K. Generally, this is explicitly denoted as TinyRAMw,k.

The state of the machine is expressed in terms of the following:

(1) The program counter, denoted pc; it consists of W bits. (2) K general-purpose registers, denoted r0, r1, . . . , r(K − 1); each register consists of W bits. (3) The (condition) flag, denoted flag; it consists of a single bit. (4) Memory, which is a linear array of 2W bytes. When storing or loading blocks of multiple bytes, we use the little-endian convention. (5) Two tapes, each containing a string of W-bit words; each tape is read-only in one direction.

One tape is for a primary input x and the other tape is for an auxiliary input w. It is actually the input carrier of TinyRAM.

The input of the TinyRAM machine is two tapes and memory, and the output is the answer instruction, which has an A parameter representing the return value, with A = 0 indicating acceptance. This instruction can also be used to terminate the program.

There are two variants of TinyRAM depending on where the instruction is executed: one follows the Harvard (hv) architecture, and the other follows the von Neumann (vn) architecture. In the former architecture, data and programs are stored in separate address spaces and programs are read-only; in the latter architecture, data and programs are stored in the same read-write address space. The difference between the two architectures is as follows:

Below are diagrams of the two variants of TinyRAM:

Before we get into more details of TinyRAM, we use examples from its official white paper to illustrate how TinyRAM is both simple and comprehensive enough to solve non-deterministic computational problems.

Meaning

Alice has x and Bob has w. Alice wants to know the correctness of the computation of algorithm A (x, w) but does not want to compute it herself. Such a scenario is not uncommon in zero-knowledge proof systems, where there is a prover and a verifier, and the verifier wants to know the correctness of the evidence provided by the prover but does not have to recompute it himself. That’s where TinyRAM can help with. Two tapes can be passed with private input w and public input x using TinyRAM, in which proof computation and verification procedures are performed.

TinyRAM is implemented by the SCIPR Lab in libsnark. (See https://github.com/scipr-lab/libsnark)

Take Circuit Generator as an example. The C program is compiled into a TinyRAM program, and then created into a circuit via the Circuit Generator, and finally, the zkSNARK circuit is obtained.

Instructions

TinyRAM supports 29 instructions, each specified by an opcode and up to 3 operands. The operands can be either register names (i.e., integers from 0 to K-1) or immediate values (i.e., W-bit strings). Unless otherwise specified, each instruction does not modify the flag and increments pc by i (modulo 2W), i=1 for the Harvard architecture, and i=2W/8 for the von Neumann architecture. Finally, all instructions take one cycle of the machine to execute.

Instructions are of various types. Instruction names are similar to intel x86 assembly instructions.

(1) Bit-related: and or xor not

(2) Integer-related: add sub mull umulh smulh udiv umod

(3) Shift-related: shl shr

(4) Compare-related: cmpe cmpa cmpae cmpg cmpge

(5) Move-related: mov cmov

(6) Jump-related: jmp cjmp cnjmp

(7) Memory-related: store.b load.b store.w load.w

(8) Input-related: read

(9) Output-related: answer

Assembly Language

TinyRAM programs are written in the TinyRAM assembly language, which is inspired by the Intel x86 assembly language syntax. The program is a text file consisting of a sequence of lines. The first line has different strings, depending on whether the program is based on Harvard or von Neumann architectures.

(1) hv TinyRAM

(2) vn TinyRAM

Above, W is the word size in decimal representation and K is the number of registers in decimal representation. Each subsequent line in the program file, in turn, contains the following:

· An optional whitespace.

· An optional label that defines the label as referring to the first instruction following it.

· An optional instruction consisting of the instruction mnemonic followed by its operands.

· An optional whitespace.

· An optional comment starting with a semicolon and ending at the end of the line.

There can be up to 2W instructions in a program. A label can be defined only once, somewhat like a variable in a high-level language.

Example code:

In order to meet the computational needs and improve the efficiency of the circuit’s adequacy, TinyRAM adds a preamble. If a TinyRAM program starts with a preamble, it is a proper program.

Where above,

The example code in the foreground also follows this style of preamble writing.

Comparison of Performance

The design differences between the two architectures of TinyRAM are described in the previous section “Architecture”. This part compares the performance of the two architectures. The graph below shows the number of gates created by hv TinyRAM and vn TinyRAM, where l is the number of instructions, n is the input size, and T is the number of execution steps.

It can be seen from the above graph that the former has a linear increase in the number of gates and instructions. The latter has a very large improvement. The more instructions, the larger the improvement.

The next graph shows the time and proof size of the key generator/prover/verifier for the two architectures with different word size curves.

It can be included that at 80-bit, the von Neumann architecture has a greater improvement compared to the Harvard architecture, and at 128-bit, there is also a small improvement. Therefore, the von Neumann architecture tends to be more efficient. This explains why vn TinyRAM was a later design than hv TinyRAM.

Summary

In summary, this paper presents the architecture, design, and assembly instructions of TinyRAM, which can be used to perform non-deterministic computations easily. In particular, TinyRAM can be used in zero-knowledge-proof systems, where it often plays a more important role. After comparing the performance of hv TinyRAM and vn TinyRAM, we may conclude that the latter is superior in terms of the number of gates, their generation time and the proof size.

References

(1) http://www.scipr-lab.org/doc/TinyRAM-spec-2.000.pdf (2) https://www.cs.tau.ac.il/\~tromer/slides/csnark-usenix13rump.pdf (3) http://eprint.iacr.org/2014/595

Note: This is an article jointly written by Sin7Y and the ZKSwap tech team.