您的位置 首页 资讯

深入理解 TinyRAM

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、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。

热门文章

发表回复

您的电子邮箱地址不会被公开。