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=WK=K”
•馮諾依曼架構
Plaintext
“; TinyRAM V=2.000 M=vn W=WK=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
為了滿⾜計算的需要，提⾼電路可滿⾜性的效率，TinyRAM 增加了前導語。如果⼀個TinyRAM 的程序以前導語的⽅式啟動，則說明該程序是個合適（proper）的程序。
上述的前導語：
•對於哈佛架構來說，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
關於我們
Sin7Y成立於2021年，由頂尖的區塊鏈開發者和密碼學工程師組成。我們既是項目孵化器也是區塊鏈技術研究團隊，探索EVM、Layer2、跨鏈、隱私計算、自主支付解決方案等最重要和最前沿的技術。
微信公眾號：Sin7Y
GitHub：Sin7Y
Twitter：@Sin7Y_Labs
Medium：Sin7Y
Mirror：Sin7Y
HackMD：Sin7Y
HackerNoon：Sin7Y
Email：contact@sin7y.org
