Sin7Y团队深入解读—— TinyRAM

Sin7Y ｜2022-07-07 15:00

我们讲了TinyRAM的架构，设计，汇编指令等，介绍了它的优势：可以⽤来便捷的进⾏非确定性计算。尤其在零知识证明系统中，有更多的发挥空间。最后介绍了两种TinyRAM架构的性能对⽐，在⽣成的⻔数量和时间以及proof⼤小上，冯诺依曼架构都更胜⼀筹。

TinyRAM 是由大名鼎鼎的 BCTGTV 五⼈组(Eli Ben-Sasson, Alessandro Chiesa、Daniel Genkin、Eran Tromer、Madars Virza) 和 SCIPR 实验室提出的⼀种随机访问器架构，旨在成为表达⾮确定性计算证明性的便捷⼯具。具体来说，TinyRAM 是⼀种精简指令集计算机 (RISC)，具有字节级可寻址的随机存取存储器。它在“拥有足够表达能力”和“足够简约”这两个对立面之间取得平衡：

• 当从高级编程语言编译时，有足够的表达能力来支持简短高效的汇编代码

• 小指令集，指令通过运算电路简单验证，利⽤ SCIPR 的算法和密码机制实现⾼效验证。

架构

TinyRAM 由两个整数参数化：字长 W，需要是 2 的幂且可以被 8 整除（这点和现代计算机⼀样，如 32、64），以及寄存器的数量 K。⼀般⽤ TinyRAM(W,K) 来表示，机器的状态包括以下内容：

1. 程序计数器 pc(program counter)，由 W 个 bit 组成。

2. K 个通⽤寄存器，以 r0, r1, …, r(K-1) 表示，每个寄存器都是 W 个 bit。

3. 条件标志 flag，由⼀个 bit 组成。

4. 内存，2^W 个字节的线性数组，使⽤⼩端约定排列字节。

5. 2 个磁带(tape)，每个包含⼀串 W bit 的字。每个磁带都是单向只读的。其中，⼀个磁带是⽤于公开输⼊ x，另⼀个⽤于私有输⼊ w。其实就是 TinyRAM 的输⼊载体。

TinyRAM 机的输⼊是 2 个磁带以及内存，输出是 answer 指令，该指令有⼀个参数 A，代表返回值，A = 0 表示接受。也可以使⽤该指令终⽌执⾏程序。

TinyRAM 根据执⾏指令的位置不同有两种变体：⼀种变体遵循哈佛架构（Harvard architecture），另⼀种遵循冯诺依曼架构（von Neumann architecture）。前⼀种架构的数据和程序存放在不同的地址空间中，且程序是只读的；后⼀种架构数据和程序存放在同⼀个可读写的地址空间中。具体⽤图表的⽅式来表示这两者的区别：

以下两个架构的图示：

在开始更详细的 TinyRAM 设计细节之前，我们以官⽅⽩⽪书的例⼦说明，TinyRAM 是如何做到既简洁⼜全⾯，能够满⾜⾮确定性的计算问题的。

意义

Alice 拥有 x，Bob 拥有 w。Alice 想知道算法 A(x,w)的计算结果的正确性，但是不想⾃⼰计算。这样的场景，在零知识证明系统中⾮常常⻅，有证明者（prover）和验证者（verifier），验证者想知道证明者提供的证据的正确性，但不必⾃⼰重新计算⼀次。TinyRAM 架构就满⾜这样的场景，两个磁带可以传⼊私有输⼊ w 和公开输⼊ x，证明计算和验证程序在其中执⾏。SCIPR 实验室实现的 libsnark 库中，已实现了 TinyRAM。具体参⻅：https://github.co m/scipr-lab/libsnark

以 Circuit Generator 为例，C 程序经过编译器之后，编译成 TinyRAM 的程序，再经过 Circuit Generator 之后，⽣成电路，最后得到 ZK-SNARK 电路。

指令

TinyRAM 支持 29 个指令，每条指令都通过 1 个操作码和最多 3 个操作数指定。操作数可以是寄存器名称（即 0 到 K-1 的整数）或者立即数（即 W 位字符串）。除非另有说明，否则每条指令都不会修改 flag，且将 pc 增加 i（模掉 2^W），对于哈佛架构来说，i=1，对于冯诺依曼架构来说，i=2W/8。通常，第一个操作数是指令执行计算的目标寄存器，其他操作（如果有）指定指令的参数。最后，所有指令都需要机器的一个周期来执行。

指令包含几种类型，指令名称和 intel x86 汇编指令类似，可顾名思义。

• 位操作指令：

￮ and

￮ or

￮ xor

￮ not

• 整数操作指令：

￮ add

￮ sub

￮ mull

￮ umulh

￮ smulh

￮ udiv

￮ umod

• shift操作指令：

￮ shl

￮ shr

• 比较操作指令

￮ cmpe

￮ cmpa

￮ cmpae

￮ cmpg

￮ cmpge

• move操作指令

￮ mov

￮ cmov

• jump操作指令

￮ jmp

￮ cjmp

￮ cnjmp

• 内存操作指令

￮ store.b

￮ load.b

￮ store.w

￮ load.w

• 输入操作指令：

￮ read

• 输出操作指令:

￮ answer

汇编语⾔

TinyRAM 的程序是由 TinyRAM 汇编语言编写的，这个语言受Intel x86 汇编语言语法启发。程序是包含多行 TinyRAM 汇编代码的文本文件。程序按照哈佛架构还是冯诺依曼架构的不同，第一行包含的字符串也不同：

• 哈佛架构

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

• 冯诺依曼架构

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

其中，W 是十进制表示的字长，K 是十进制表示的寄存器数量。程序文件中，其他每一行依次包含的内容需要满足：

1. 可选的空格。

2. 可选的 label，用于定义为引用其后的第一条指令。

3. 可选的指令，由指令助记符，以及后面的操作数。

4. 可选的空格。

5. 可选的以分号;开始的注释，到该行尾结束。

一个程序中，最多可以有 2^W 个指令。一个 label 只能定义一次，有点像高级语言中的变量。

示例代码https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s:

Plaintext
; TinyRAM V=2.000 M=vn W=16 K=16
store.w 0, r0
mov r0, 32768
read r1, 0
cjmp 28
add r0, r0, 2
store.w r0, r1
jmp 12
store.w 32768, r0
answer 0