ZKSwap团队深入解读——TinyRAM

这篇文章主要介绍了ZKSwap团队深入解读——TinyRAM ,文中通过代码以及文档配合进行讲解,很详细,它对在座的每个人的研究和工作具有很经典的参考价值。 如果需要,让我们与区块链资料网一起学习。

https://www.interchains.cc/23624.html

ZKSwap团队深入解读——TinyRAM是很好的区块链资料,他说明了区块链当中的经典原理,可以给我们提供资料,ZKSwap团队深入解读——TinyRAM学习起来其实是很简单的,

不多的几个较为抽象的概念也很容易理解,之所以很多人感觉ZKSwap团队深入解读——TinyRAM比较复杂,一方面是因为大多数的文档没有做到由浅入深地讲解,概念上没有注意先后顺序,给读者的理解带来困难

ZKSwap团队深入解读——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)。前⼀种架构的数据和程序存放在不同的地址空间中,且程序是只读的;后⼀种架构数据和程序存放在同⼀个可读写的地址空间中。具体⽤图表的⽅式来表示这两者的区别:

ZKSwap团队深入解读——TinyRAM

以下两个架构的图示:

ZKSwap团队深入解读——TinyRAM

ZKSwap团队深入解读——TinyRAM

在开始更详细的 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

ZKSwap团队深入解读——TinyRAM

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

ZKSwap团队深入解读——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 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

为了满⾜计算的需要,提⾼电路可满⾜性的效率,TinyRAM 增加了前导语。如果⼀个 TinyRAM 的程序以前导语的⽅式启动,则说明该程序是个合适(proper)的程序。

ZKSwap团队深入解读——TinyRAM

上述的前导语:

  • 对于哈佛架构来说,I~i~ = 1 * i,并且inc = 1
  • 对于冯诺依曼架构来说,I~i~ = 2W/8 * i,并且 inc = W/8

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

两种架构的性能对⽐

TinyRAM 的两种架构,其设计区别在前⾯的“架构”部分介绍了,此处对⽐两种架构的性能。第⼀个图表展示两种架构产⽣的⻔数量。

l 是指令数量,n 是输⼊⼤⼩,T 是执⾏步数。

n=10^2, T=2^20 哈佛架构 冯诺依曼架构
l=10^3 1872 1368
l=10^4 10872 1371
l=10^5 100872 1400
l=10^6 1000872 1694

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

第⼆个图表展示两种架构在不同字⻓的曲线下,⽣成 Key generator/prover/verifier 的时间及 proof ⼤⼩。

哈佛-爱德华曲线 80bit 冯诺依曼-爱德华曲线 80bit 哈佛-BN曲线 128bit 冯诺依曼-BN曲线128bit
key generator 306s 97s 123s 117s
prover 351s 115s 784s 147s
verifier 66.1ms 4.9ms 9.2ms 5.1ms
proof size 332B 230B 288B 288B

可以看出,在 80 bit 时,冯诺依曼架构相较于哈佛架构有较⼤提升,在 128 bit 时,也有少许提升。

由上述表格数据可以看出,冯诺依曼架构的效率更⾼,这也是为什么冯依诺曼架构 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/595

部分转自网络,侵权联系删除www.interchains.cchttps://www.interchains.cc/23624.html

区块链毕设网(www.interchains.cc)全网最靠谱的原创区块链毕设代做网站 部分资料来自网络,侵权联系删除! 最全最大的区块链源码站 ! QQ3039046426
区块链知识分享网, 以太坊dapp资源网, 区块链教程, fabric教程下载, 区块链书籍下载, 区块链资料下载, 区块链视频教程下载, 区块链基础教程, 区块链入门教程, 区块链资源 » ZKSwap团队深入解读——TinyRAM

提供最优质的资源集合

立即查看 了解详情