深入理解TinyRAM

特邀专栏作者

2022-08-17 12:53

本文約3083字，閱讀全文需要約5分鐘

本文講述了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.

指令

TinyRAM 支持29個指令，每條指令都通過1個操作碼和最多3個操作數指定。操作數可以是寄存器名稱（即0到K-1的整數）或者立即數（即W 位字符串）。除非另有說明，否則每條指令都不會修改flag，且將pc 增加i（模掉2^W），對於哈佛架構來說，i=1，對於馮諾依曼架構來說，i=2W /8。通常，第一個操作數是指令執行計算的目標寄存器，其他操作（如果有）指定指令的參數。最後，所有指令都需要機器的一個週期來執行。

位操作指令

● 位操作指令：

•and

•or

•xor

•not

● shift操作指令：

•add

•sub

•mull

•umulh

•smulh