免责声明:金色财经所有资讯仅代表作者个人观点,不构成任何投资理财建议。请确保访问网址为(jinse.cn) 举报

    深入理解 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

    以下两个架构的图示:

    深入理解TinyRAM

    深入理解TinyRAM

    在开始更详细的TinyRAM设计细节之前,我们以官方白皮书的例子说明,TinyRAM是如何做到既简洁又全面,能够满足非确定性的计算问题的。

    意义

    Alice 拥有x,Bob拥有w。Alice 想知道算法A(x, w)的计算结果的正确性,但是不想自己计算。这样的场景,在零知识证明系统中非常常见,有证明者(prover)和验证者(verifier),验证者想知道证明者提供的证据的正确性,但不必自己重新计算一次。TinyRAM 架构就满足这样的场景,两个磁带可以传入私有输入w和公开输入x,证明计算和验证程序在其中执行。SCIPR 实验室实现的 libsnark 库中,已实现了TinyRAM。具体参见:https://github.com/scipr-lab/libsnark.

    深入理解TinyRAM

    以Circuit Generator为例,C 程序经过编译器之后,编译成TinyRAM 的程序,再经过Circuit Generator之后,生成电路,最后得到zkSNARK电路。

    深入理解TinyRAM

    指令

    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 增加了前导语。如果一个TinyRAM的程序以前导语的方式启动,则说明该程序是个合适(proper)的程序。

    深入理解TinyRAM

    上述的前导语:

    • 对于哈佛架构来说,I(i)= 1 * i,并且inc = 1

    • 对于冯诺依曼架构来说,I(i) = 2W/8 * i,并且 inc = W/8

    前面的示例代码,也遵循这样的前导语写法。

    两种架构的性能对比

    TinyRAM 的两种架构,其设计区别在前面的“架构”部分介绍了,此处对比两种架构的性能。

    第一个图表展示两种架构产生的门数量。

    l 是指令数量,n是输入大小,T是执行步数。

    深入理解TinyRAM

    可以看出,前者的门数量和指令数量呈线性增加。后者改善很大,指令越多,改善的越大。

    第二个图表展示两种架构在不同字长的曲线下,生成Key generator / prover / verifier 的时间及 proof 大小。

    深入理解TinyRAM

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

    jinse.cn 1
    好文章,需要你的鼓励
    jinse.cn 1
    好文章,需要你的鼓励
    参与评论
    0/140
    提交评论
    文章作者: / 责任编辑:

    声明:本文由入驻金色财经的作者撰写,观点仅代表作者本人,绝不代表金色财经赞同其观点或证实其描述。

    提示:投资有风险,入市须谨慎。本资讯不作为投资理财建议。

    金色财经 > Odaily星球日报 > 深入理解 TinyRAM
    • 寻求报道
    • 金色财经中国版App下载
      金色财经APP
      iOS & Android
    • 加入社群
      Telegram
    • 意见反馈
    • 返回顶部
    • 返回底部