TinyRAM は、有名な BCTGTV の 5 人のメンバー グループ (Eli Ben-Sasson、Alessandro Chiesa、Daniel Genkin、Eran Tromer、Madars Virza) と SCIPR Laboratory によって提案されたランダム アクセサー アーキテクチャであり、非決定論的コンピューティングの便利なツールの証明を目指しています。具体的には、TinyRAM は、バイトレベルでアドレス指定可能なランダム アクセス メモリを備えた縮小命令セット コンピュータ (RISC) です。 「十分な表現力」と「十分なシンプルさ」という相反するもののバランスをとります。

• 高級プログラミング言語からコンパイルした場合に、短く効率的なアセンブリ コードをサポートするのに十分な表現力。

●命令セットが小さく、演算回路による命令の検証が容易であり、SCIPRのアルゴリズムとパスワード機構を利用することで効率的な検証を実現します。

建築

TinyRAM は 2 つの整数でパラメータ化されます。ワード長 W は 2 のべき乗で 8 で割り切れる必要があります (これは、32、64 などの現代のコンピュータと同じです)。もう 1 つはレジスタ数 K です。一般に TinyRAM(W,K) で表されるマシンの状態には次のものが含まれます。

1. プログラムカウンタpc（プログラムカウンタ）はWビットで構成されます。

2. r0、r1、...、r(K-1) で表される K 個の汎用レジスタ。各レジスタは W ビットです。

3. 条件フラグ flag は 1 ビットで構成されます。

4. メモリ。リトルエンディアン規則を使用してバイトを配置する、2^W バイトの線形配列。

5. 2 つのテープ。それぞれに W ビット ワードの文字列が含まれています。各テープは一方向の読み取り専用です。このうち、1 つのテープはパブリック入力 x 用で、もう 1 つはプライベート入力 w 用です。実際、これは TinyRAM の入力キャリアです。

TinyRAM マシンの入力は 2 本のテープとメモリで、出力は応答コマンドです。このコマンドには戻り値を表すパラメータ A があり、A = 0 は受け入れを意味します。このコマンドを使用してプログラムの実行を終了することもできます。

TinyRAM には、命令が実行される場所に応じて 2 つのバリアントがあります。1 つはハーバード アーキテクチャに従い、もう 1 つはフォン ノイマン アーキテクチャに従います。前者のアーキテクチャのデータとプログラムは異なるアドレス空間に格納され、プログラムは読み取り専用ですが、後者のアーキテクチャのデータとプログラムは、同じ読み取りおよび書き込み可能なアドレス空間に格納されます。具体的には、2 つの違いを図で表します。

次の 2 つのアーキテクチャの図:

TinyRAM 設計の詳細を開始する前に、公式ホワイト ペーパーの例を使用して、TinyRAM がどのように簡潔かつ包括的であり、非決定論的なコンピューティングの問題を解決できるかを説明します。

意義

アリスは x を所有し、ボブは w を所有します。アリスはアルゴリズム A(x, w) の計算結果の正しさを知りたいと思っていますが、自分自身で計算することは望んでいません。このようなシナリオは、ゼロ知識証明システムでは非常に一般的です。証明者と検証者がいます。検証者は証明者が提供した証拠の正しさを知りたいと考えていますが、自分で再計算する必要はありません。 TinyRAM アーキテクチャは、2 つのテープがプライベート入力 w とパブリック入力 x を渡すことができ、証明計算と検証手順が実行されるこのようなシナリオを満たします。 TinyRAM は、SCIPR lab によって実装された libsnark ライブラリに実装されています。詳細については、以下を参照してください。https://github.com/scipr-lab/libsnark.

Circuit Generator を例に挙げると、C プログラムはコンパイラを通過した後、TinyRAM プログラムにコンパイルされ、Circuit Generator を通過した後、回路が生成され、最終的に zkSNARK 回路が得られます。

命令

TinyRAM は 29 命令をサポートし、各命令は 1 つのオペコードと最大 3 つのオペランドによって指定されます。オペランドは、レジスタ名 (つまり、0 から K-1 までの整数) または即値 (つまり、W ビット文字列) にすることができます。特に指定がない限り、各命令はフラグを変更せず、pc を i (モジュロ 2^W) だけ増加させます。ハーバード アーキテクチャの場合は i=1、フォン ノイマン アーキテクチャの場合は i=2W /8 です。通常、最初のオペランドは命令が実行する計算の宛先レジスタであり、他の演算 (存在する場合) は命令の引数を指定します。最終的に、すべての命令の実行にはマシンの 1 サイクルがかかります。

命令にはいくつかの種類があり、命令名はその名のとおり intel x86 アセンブリ命令に似ています。

● ビット操作命令：

•and

•or

•xor

•not

● 整数操作命令:

•add

•sub

•mull

•umulh

•smulh

•udiv

•umod

● シフト演算命令：

•shl

•shr

● 比較演算命令

•cmpe

•cmpa

•cmpae

•cmpg

•cmpge

●移動操作命令

•mov

•cmov

● ジャンプ動作命令

•jmp

•cjmp

•cnjmp

● メモリ操作命令

•store.b

•load.b

•store.w

•load.w

● 操作コマンドを入力します。

•read

● 出力操作命令:

•answer

アセンブリ言語

TinyRAM のプログラムは、Intel x86 アセンブリ言語構文からインスピレーションを得た TinyRAM アセンブリ言語で作成されます。プログラムは、TinyRAM アセンブリ コードの行を含むテキスト ファイルです。プログラムがハーバード アーキテクチャに基づいているか、フォン ノイマン アーキテクチャに基づいているかに応じて、最初の行に含まれる文字列も異なります。

• ハーバード大学の建築

“; TinyRAM V=2.000 M=hv W=W K=K”

• フォン・ノイマン・アーキテクチャ

“; TinyRAM V=2.000 M=vn W=W K=K”

このうち、Wは10進数で表した語長、Kは10進数で表したレジスタ数です。プログラム ファイルでは、他の各行に含まれる内容が次の条件を満たす必要があります。

1. オプションのスペース。

2. オプションのラベル。その後に続く最初の命令を参照するために定義されます。

3. オプションの命令。命令ニーモニックとその後にオペランドが続きます。

4. オプションのスペース。

5. オプションでセミコロンで始まり、行末で終わるコメント。

プログラム内には最大 2^W の命令を含めることができます。ラベルは 1 回だけ定義でき、高級言語の変数と似ています。

サンプルコード (https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s)

計算のニーズを満たし、回路満足度の効率を向上させるために、TinyRAM はプリアンブルを追加します。 TinyRAM プログラムがプリアンブルで始まる場合、そのプログラムは正規のプログラムであることを意味します。

上記の前文:

• ハーバード アーキテクチャの場合、I(i)= 1 * i、および inc = 1

• ノイマン型アーキテクチャの場合、I(i) = 2W/8 * i、および inc = W/8

前のサンプル コードもこのプリアンブルの後にあります。

2 つのアーキテクチャのパフォーマンスの比較

TinyRAM の 2 つのアーキテクチャの設計の違いは前の「アーキテクチャ」セクションで紹介されており、ここでは 2 つのアーキテクチャのパフォーマンスを比較します。

最初のグラフは、2 つのアーキテクチャによって生成されるゲートの数を示しています。

l は命令の数、n は入力サイズ、T は実行ステップ数です。

前者の場合、ゲート数と命令数が直線的に増加していることがわかります。後者は大幅に改善され、命令が増えるほど改善も大きくなります。

2 番目のグラフは、異なる語長の曲線の下で鍵生成器 / 証明器 / 検証器を生成するための 2 つのアーキテクチャの時間と証明サイズを示しています。

80 ビットでは、フォン ノイマン アーキテクチャはハーバード アーキテクチャと比較して大幅に改善されており、128 ビットでもわずかに改善されていることがわかります。

要約する

要約する

TinyRAM のアーキテクチャ、設計、アセンブリ命令などについて説明し、非決定論的な計算を便利に実行するために使用できるというその利点を紹介しました。特にゼロ知識証明システムには開発の余地があります。最後に、2 つの TinyRAM アーキテクチャの性能比較を紹介しますが、生成されるゲートの数と時間、および証明のサイズの点で von Neumann アーキテクチャが優れています。

WeChat 公開アカウント: Sin7Y

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、レイヤー 2、クロスチェーン、プライバシー コンピューティング、自律型決済ソリューションなどの最も重要で最先端のテクノロジーを研究しています。

WeChat 公開アカウント: Sin7Y

GitHub | Twitter | Telegram | Medium| Mirror | HackMD | HackerNoon