TinyRAM is a random accessor architecture proposed by the famous BCTGTV five-member group (Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza) and SCIPR Laboratory, aiming to become a proof of non-deterministic computing handy tool. Specifically, TinyRAM is a Reduced Instruction Set Computer (RISC) with byte-level addressable random access memory. It strikes a balance between the opposites of "expressive enough" and "simple enough":

•Small instruction set, the instruction is easily verified by the operation circuit, and the efficient verification is realized by using the algorithm and password mechanism of SCIPR.

•Small instruction set, the instruction is easily verified by the operation circuit, and the efficient verification is realized by using the algorithm and password mechanism of SCIPR.

architecture

TinyRAM is parameterized by two integers: the word length W, which needs to be a power of 2 and divisible by 8 (this is the same as modern computers, such as 32, 64), and the number of registers K. Generally represented by TinyRAM(W,K), the state of the machine includes the following:

1. The program counter pc (program counter) consists of W bits.

2. K general-purpose registers, represented by r0, r1, ..., r(K-1), each register is W bits.

3. The condition flag flag consists of one bit.

4. Memory, a linear array of 2^W bytes, using the little-endian convention to arrange the bytes.

5. 2 tapes, each containing a string of W bit words. Each tape is read-only in one direction. Among them, one tape is for the public input x and the other is for the private input w. In fact, it is the input carrier of TinyRAM.

The input of the TinyRAM machine is 2 tapes and memory, and the output is the answer command, which has a parameter A, which represents the return value, and A = 0 means acceptance. You can also use this command to terminate program execution.

TinyRAM has two variants depending on where instructions are executed: one variant follows the Harvard architecture and the other follows the von Neumann architecture. The data and programs of the former architecture are stored in different address spaces, and the programs are read-only; the data and programs of the latter architecture are stored in the same readable and writable address space. Specifically, the difference between the two is represented by a diagram:

Illustration of the following two architectures:

Before starting the more detailed TinyRAM design details, we use the example of the official white paper to illustrate how TinyRAM is concise and comprehensive, and can satisfy non-deterministic computing problems.

significance

Alice owns x and Bob owns w. Alice wants to know the correctness of the calculation result of the algorithm A(x, w), but does not want to calculate it herself. Such a scenario is very common in zero-knowledge proof systems. There are provers and verifiers. The verifier wants to know the correctness of the evidence provided by the prover, but does not have to recalculate it himself. The TinyRAM architecture satisfies such a scenario, where two tapes can pass in a private input w and a public input x, on which proof computation and verification procedures are executed. TinyRAM has been implemented in libsnark library implemented by SCIPR lab. For details, see:https://github.com/scipr-lab/libsnark.

Taking Circuit Generator as an example, after the C program passes through the compiler, it is compiled into a TinyRAM program, and after passing through the Circuit Generator, a circuit is generated, and finally a zkSNARK circuit is obtained.

instruction

TinyRAM supports 29 instructions, each instruction is specified by 1 opcode and up to 3 operands. Operands can be register names (ie, integers from 0 to K-1) or immediate values ​​(ie, W-bit strings). Unless otherwise specified, each instruction will not modify the flag, and increase the pc by i (modulo 2^W). For the Harvard architecture, i=1, and for the von Neumann architecture, i=2W /8. Typically, the first operand is the destination register for the computation the instruction performs, and the other operations (if any) specify the arguments for the instruction. In the end, all instructions take one cycle of the machine to execute.

There are several types of instructions, and the instruction name is similar to the intel x86 assembly instruction, as the name implies.

● bit manipulation instructions：

•and

•or

•xor

•not

● Integer manipulation instructions:

•add

•sub

•mull

•umulh

•smulh

•udiv

•umod

● shift operation instruction:

•shl

•shr

● comparison operation instruction

•cmpe

•cmpa

•cmpae

•cmpg

•cmpge

●move operation instruction

•mov

•cmov

● jump operation instruction

•jmp

•cjmp

•cnjmp

● memory manipulation instructions

•store.b

•load.b

•store.w

•load.w

● Enter the operation command:

•read

● Output operation instructions:

•answer

Assembly language

Programs for TinyRAM are written in TinyRAM assembly language, which is inspired by the Intel x86 assembly language syntax. Programs are text files containing lines of TinyRAM assembly code. Depending on whether the program is based on the Harvard architecture or the von Neumann architecture, the strings contained in the first line are also different:

• Harvard Architecture

“; TinyRAM V=2.000 M=hv W=W K=K”

• Von Neumann architecture

“; TinyRAM V=2.000 M=vn W=W K=K”

Among them, W is the word length expressed in decimal, and K is the number of registers expressed in decimal. In the program file, the content contained in each other line in turn needs to meet:

1. Optional spaces.

2. An optional label, defined to refer to the first instruction following it.

3. Optional instructions, by instruction mnemonic, followed by operands.

4. Optional spaces.

5. Comments that optionally start with a semicolon; end at the end of the line.

In a program, there can be at most 2^W instructions. A label can only be defined once, a bit like a variable in a high-level language.

sample code (https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s)

In order to meet the needs of calculation and improve the efficiency of circuit satisfiability, TinyRAM adds a preamble. If a TinyRAM program starts with a preamble, it means that the program is a proper program.

The above preamble:

• For Harvard architecture, I(i)= 1 * i, and inc = 1

• For von Neumann architecture, I(i) = 2W/8 * i, and inc = W/8

The previous sample code also follows this preamble.

Performance comparison of the two architectures

The design differences of the two architectures of TinyRAM are introduced in the previous "Architecture" section, and the performance of the two architectures is compared here.

The first graph shows the number of gates produced by the two architectures.

l is the number of instructions, n is the input size, and T is the number of execution steps.

It can be seen that the number of gates and the number of instructions increase linearly for the former. The latter improved greatly, and the more instructions, the greater the improvement.

The second chart shows the time and proof size of the two architectures to generate Key generator / prover / verifier under the curves of different word lengths.

It can be seen that at 80bit, the von Neumann architecture has a greater improvement compared with the Harvard architecture, and at 128bit, there is also a slight improvement.

Summarize

Summarize

We talked about TinyRAM's architecture, design, assembly instructions, etc., and introduced its advantages: it can be used to conveniently perform non-deterministic calculations. Especially in the zero-knowledge proof system, there is more room for development. Finally, the performance comparison of the two TinyRAM architectures is introduced. The von Neumann architecture is superior in terms of the number and time of generated gates and the size of the proof.

WeChat public account: Sin7Y

http://www.scipr-lab.org/doc/TinyRAM-spec-2.000.pdf

https://www.cs.tau.ac.il/~tromer/slides/csnark-usenix13rump.pdf

http://eprint.iacr.org/2014/59

about Us

Sin7y was established in 2021 and is composed of top blockchain developers. We are both a project incubator and a blockchain technology research team, exploring the most important and cutting-edge technologies such as EVM, Layer2, cross-chain, privacy computing, and autonomous payment solutions.

WeChat public account: Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon