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.com/scipr-lab/libsnark.
以Circuit Generator为例，C 程序经过编译器之后，编译成TinyRAM 的程序，再经过Circuit Generator之后，生成电路，最后得到zkSNARK电路。
指令
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 汇编代码的文本文件。程序按照哈佛架构还是冯诺依曼架构的不同，第一行包含的字符串也不同：
• 哈佛架构
“; TinyRAM V=2.000 M=hv W=W K=K”
• 冯诺依曼架构
“; 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)
为了满足计算的需要，提高电路可满足性的效率，TinyRAM 增加了前导语。如果一个TinyRAM的程序以前导语的方式启动，则说明该程序是个合适（proper）的程序。
上述的前导语：
• 对于哈佛架构来说，I(i)= 1 * i，并且inc = 1
• 对于冯诺依曼架构来说，I(i) = 2W/8 * i，并且 inc = W/8
前面的示例代码，也遵循这样的前导语写法。
两种架构的性能对比
TinyRAM 的两种架构，其设计区别在前面的“架构”部分介绍了，此处对比两种架构的性能。
第一个图表展示两种架构产生的门数量。
l 是指令数量，n是输入大小，T是执行步数。
可以看出，前者的门数量和指令数量呈线性增加。后者改善很大，指令越多，改善的越大。
第二个图表展示两种架构在不同字长的曲线下，生成Key generator / prover / verifier 的时间及 proof 大小。
可以看出，在80bit时，冯诺依曼架构相较于哈佛架构有较大提升，在128bit时，也有少许提升。
由上述表格数据可以看出，冯诺依曼架构的效率更高，这也是为什么冯依诺曼架构TinyRAM是后来在哈佛架构TinyRAM的基础上提出的。
总结
我们讲了TinyRAM的架构，设计，汇编指令等，介绍了它的优势：可以用来便捷的进行非确定性计算。尤其在零知识证明系统中，有更多的发挥空间。最后介绍了两种TinyRAM架构的性能对比，在生成的门数量和时间以及proof大小上，冯诺依曼架构都更胜一筹。
引用
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
关于我们
Sin7y成立于2021年，由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号：Sin7Y
GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon
