スタックマシンの解剖：256 ビット語、1024 段のスタック、実行ループ

0x6001600201 という 5 バイトは、EVM の中で一つのことをします。1 と 2 を足し、スタックの先頭に 3 を残すのです。どのレジスタも参照せず、結果の置き場所も書かれていません。二つのオペランドはスタック上に暗黙のうちに並び、結果もまたスタックへ戻ります。EVM の算術と制御フローはすべてこのモデルの上に成り立っています。

これまでの記事はステートマシンとアカウントを扱ってきましたが、本稿は一歩内側を見ます。このマシンが何で構成され、1 回の実行ループがどう回り、256 ビット語長と 1024 段のスタック深さがどこから来たのか、そしてこのスタックマシンの設計が何を得て何を支払ったのかです。

256 ビット語長：算術のためではなく暗号のための選択

イエローペーパーの語長についての説明は一言だけです。マシン語長（つまりスタック要素の幅）は 256 ビットで、この選択は Keccak-256 ハッシュと楕円曲線演算を容易にするためです。展開すると、具体的な理由は三つあります。

Keccak-256 の出力は 256 ビットなので、ハッシュ値もストレージキーも切り詰めたり拡張したりする必要がありません。イーサリアムは secp256k1 上の ECDSA で署名し、秘密鍵と署名の成分は 256 ビット空間に収まります。EVM 側の対応する機能は ecrecover が提供し、これはアドレス 0x01 上のプリコンパイル・コントラクトで、価格は 3000 ガスです。アドレスは 160 ビットで、256 ビットの語に入れると自然に整列します。

ここに、見落とされがちな正確さの問題があります。イーサリアムが使う Keccak-256 は、NIST が標準化した後の SHA3-256 ではありません。両者は出力のビット幅が同じで置換関数も同じですが、パディングのドメイン分離バイトが異なります。原版の Keccak は 0x01 を使い、SHA3-256 は 0x06 を使います。ハッシュ検証を行うときは Keccak-256 と明記されたライブラリを選ぶ必要があり、SHA3-256 を使うとまったく違う結果になります。

語幅の代価も明確です。すべての算術は 2^256 を法として行われ、オーバーフローは静かにラップアラウンドし、例外を出しません。真偽値も 32 バイト全体を占めます。calldata とストレージスロットは 32 バイト単位で揃えられ、短い型はエンコード層で詰め直す必要があり、Solidity の storage packing がやっているのはまさにこれです（同シリーズの 0.19「Storage Layout：Solidity の状態変数はどうスロットに配置されるか」を参照）。ラップアラウンドのセマンティクスは、歴史上の数多くの整数オーバーフロー脆弱性の根源でもあります。Solidity 0.8 以降は既定でチェックを挿入し、Panic(0x11) でリバートしますが、これは言語層での補修であり、EVM 自体は変わっていません。

マシン状態：スタック、メモリ、プログラムカウンタがそれぞれ何を担うか

イエローペーパーはマシン状態を 6 つ組 μ = (g, pc, m, i, s, o) として書いています。利用可能なガス、プログラムカウンタ、メモリの内容、現在アクティブなメモリの語数、スタックの内容、そして戻りデータ・バッファです。四つの構成要素の役割は並べて見比べられます。

スタック（stack）は唯一の暗黙のオペランド領域です。先頭だけを露出し、ほとんどの命令は先頭から引数をポップし、結果を先頭にプッシュし直します。途中の要素は命令からは見えません。上限は 1024 項、各項は 256 ビットです。

メモリ（memory）はバイト単位でアドレス指定され、すべての位置は初期値がゼロで、MLOAD/MSTORE（32 バイト語単位の読み書き）と MSTORE8（1 バイトの書き込み）からアクセスできます。そのコストは動的です。拡張はアクティブな語数に応じて課金され、イエローペーパーが示す式では、a 語を占有するときの総メモリコストは 3a + ⌊a²/512⌋ ガスになります。二次の項があるため、極端に大きなオフセットにアクセスするとガスを直接使い切ります。したがって EVM のメモリには無料の大きな配列は存在せず、「未初期化データを読む」という問題も存在しません。書いていない位置は常に 0 です。

プログラムカウンタ（program counter、PC）は、次の命令のコード内でのバイトオフセットです。制御フローは JUMP/JUMPI でしか変えられず、イエローペーパーは正当なジャンプ先の集合を、コード中で JUMPDEST 命令が現れる位置として定義しています。したがってジャンプ先の集合は静的に列挙でき、実行時に任意のアドレスを計算して飛ぶことはできません。この制約が、オフラインの制御フロー解析を成り立たせる土台です。

コード自体はスタック、メモリ、ストレージのどこにも置かれません。イエローペーパーは、このマシンがノイマン型に従わないと明確に述べており、コードは専用命令でしかアクセスできない仮想 ROM に別途保存されます。そのためデプロイ済みのコントラクト・コードが自分自身を書き換えることはなく、実行の途中で命令列を差し替える余地もありません。ストレージとメモリは可変ですが、コードは可変ではありません。

フェッチ、デコード、実行：1 回のループ

イエローペーパーは「次に実行すべき命令」を区分関数として定義しています。プログラムカウンタがコード長より小さければ、命令はその位置のバイトです。そうでなければ命令は STOP と等価になります。つまり、コードの末尾を越えて読むことは誤りではなく、仕様はこの形で自然な終了を定義しています。

命令が実行されるには、まず三つのことを知る必要があります。いくつ項をポップするか（δ）、いくつ項をプッシュするか（α）、そしていくらガスを消費するか（コスト関数 C）です。これら三つの量は命令自身が決め、オペコード表の行に書かれています。するとループは次のように書けます。ここでは substate、access list、ガス返金を省略しています。

# 簡略版の実行ループ。仕様上の判定順序を保っている
pc, gas, stack, memory = 0, gas_limit, [], bytearray()

while True:
    # フェッチ：コード末尾を越えるのは STOP と等価
    op = code[pc] if pc < len(code) else STOP
    # デコード：表を引いてポップ数、プッシュ数、コストを得る
    delta, alpha, cost = OPCODE_TABLE[op]
    # 検証は実行より前に来る：ガス不足、スタック不足、スタックオーバーフローはいずれも異常停止
    if gas < cost or len(stack) < delta or len(stack) - delta + alpha > 1024:
        raise ExceptionalHalt()
    gas -= cost
    # 実行：スタック先頭からオペランドを取り、結果を先頭に戻す
    args = [stack.pop() for _ in range(delta)]
    stack.extend(dispatch(op, args, memory, pc))
    # PC を進める。PUSH 系の命令は直後の即値もスキップする
    pc += 1 + immediates(op)

コメントは、間違えやすい三か所に対応しています。範囲外のフェッチのセマンティクス、検証が実行より先に来ること、PUSH の即値がコード空間を占めることです。

最後の点はもう少し展開する必要があります。PUSH1 から PUSH32 は定数をオペコードの直後に直接エンコードします。たとえば PUSH1 0x2a は 2 バイトを占めます。ここから直感に反する帰結が生まれます。バイトコードのすべてのバイトが命令というわけではなく、ジャンプ先の走査は即値データを識別して読み飛ばさなければなりません。そうしないと、定数の中の 1 バイトを JUMPDEST と誤認する可能性があります。

5 バイトの 60 2a 60 5b 56 を並べて見ると分かりやすくなります。60 2a は即値を伴う命令です。60 5b の 2 番目のバイトは定数 0x5b で、その値は JUMPDEST のオペコードと完全に同じですが、命令ではありません。56 がようやく JUMP です。正当なジャンプ先を走査するときは、まず 0x60 を識別し、その直後の 1 バイトを読み飛ばさなければなりません。規則自体は複雑ではなく、制御フロー解析を行うあらゆる実装に PUSH の長さを正確に数えることを求めるだけです。そうしなければジャンプ先の集合が定数バイトで汚染されます。

これは、任意のオフセットへのジャンプを許すのではなく、専用の 0x5b をジャンプの印として用意する必要がある理由でもあります。

スタックのアンダーフローとオーバーフロー：二つの例外、同じ結末

イエローペーパーの異常停止判定関数 Z は、実行を即座に中断させるすべての条件を列挙しています。そのうちスタックに関わるものは二つです。スタック内の要素が、その命令がポップする数より少ない場合、すなわちアンダーフロー（stack underflow）。実行後のスタック高さが 1024 を超える場合、すなわちオーバーフロー（stack overflow）です。

どちらも同じ道をたどります。異常停止し、残りのガスはすべて消費され、今回の呼び出しフレーム内の状態変更はすべて破棄されます。EIP-3855 の仕様テストベクトルは、きれいな対照を与えてくれます。1024 個の PUSH0 を連続させると成功し、1025 個を連続させるとスタックオーバーフローで中止します。

ここは別の種類の「失敗」と区別する必要があります。REVERT 命令（0xfd、Byzantium 以降、EIP-140）も状態をロールバックしますが、残りのガスは消費せず、メモリ内の一定のバイト列をエラーデータとして呼び出し元に返せます。Solidity の require の失敗は通常 REVERT にコンパイルされ、エラーメッセージは呼び出し元に持ち帰られ、残りのガスも消費されません。スタックのアンダーフローはハードな例外で、デバッグ時にはガスを使い切って戻りデータがない形で現れます。デバッグの経験では、トランザクションがガスを使い切って戻りデータも得られないとき、よくある原因はバイトコードがハードな例外を踏んだことで、計算量そのものが多いとは限りません。

境界も明確にしておきます。REVERT 自身のガスが足りない場合、あるいはその実行中にスタックのアンダーフローに遭遇した場合、REVERT は通常の例外に退化し、同じくガスをすべて消費します。

スタックマシンの利点：実装の複雑さを最小に押し下げる

ethereum.org の説明によれば、スタック構造は実装が容易で、誤りやセキュリティ脆弱性の可能性が低くなるため、仮想マシンの第一選択のアーキテクチャです。この利点はいくつかに分解できます。

デコーダは極めて簡素です。オペコードは 1 バイトで、オペランドの位置はスタックの順序から暗黙に決まり、バイトコード内で命令ごとにレジスタ番号をエンコードする必要はありません。PUSH 系の命令が即値を持つほかは命令長がほぼ固定なので、デコードは 1 回の表引きで済みます。

仕様にはレジスタ割り当てという層がありません。割り当ての方針は本来コンパイラの自由ですが、いったん仮想マシンの仕様に入り込むと、すべての実装がビット単位で一致しなければならない挙動になります。スタックマシンは「値をどこに置くか」を仕様から削り落とし、コンセンサスが固定すべき状態記述をそれだけ小さくします。

スタック上の操作のセマンティクスはほぼ項目ごとに独立して定義でき、ガスコストはオペコードに直接結び付けられます。静的解析、ファジング、形式検証の探索空間もより小さくなります。EVM が複数の独立実装（geth、revm、evmone など）を持ちながらバイト単位で一致できるのは、これも理由の一つです。

スタックマシンの代価：DUP、SWAP とランダムアクセスの不可能性

スタックが先頭しか露出しないことの代価は、バイトコードの命令数に現れます。

先頭に近い要素を使うには、DUP1 から DUP16 でそれを先頭に複製するか、SWAP1 から SWAP16 で先頭に交換して持ってきます。16 が硬い上限です。複製したい要素が 17 層目にあるなら、まず SWAP16 のような命令で複製可能な範囲まで持ってきてから操作を続ける必要があり、スタックが深いほど運搬の連鎖が長くなります。レジスタマシンなら 1 命令で済む同じ計算が、ここではプッシュ、複製、交換、ポップの列に展開されます。

具体的な場面を挙げます。コントラクトが f(a, b, c, d) を計算しようとして、d がスタックの 4 層目にあるとします。レジスタマシンなら d のあるレジスタを直接参照できます。スタックマシンではコンパイラが、前もって d の複製を先頭に近い位置に置くか、呼び出しの前に SWAP 系で先頭に上げ、使い終わったら戻すかのどちらかを行います。Solidity コンパイラが関数の引数が多いときにこうした並べ替え命令を大量に生成するのは、ここに理由があります。

コンパイラはスタックのバランスも維持しなければなりません。各基本ブロックの終了時にスタック高さが予測可能でなければ、ジャンプ後のコードがオペランドを特定できません。そのため Solidity のコンパイル時には専用のスタック・スケジューリングが必要になり、引数とローカル変数が多いときは DUP、SWAP、POP を挿入してオペランドを運びます。これらの命令自体は高くなく、多くは 3 ガスの区分に入りますが、インタプリタの実行パスを長くします。

スタックマシンがレジスタマシンより余分に支払うものについては、JVM に間接的な参照があります。Davis らは JVM のバイトコードを仮想レジスタマシンへ変換し、実行命令数が減り、バイトコードのフェッチ回数が増えるというトレードオフを報告しました（Davis ら、2003）。この対照は JVM 由来で、そのまま EVM に持ち込めるものではありません。測定対象はインタプリタ実行のディスパッチ費用であり、EVM のガス価格設定は解釈の費用の大部分をすでに外部化しています。支持できる方向性の判断は一つだけです。同じ計算に対して、スタックマシンは通常より多くの実行命令を必要とし、レジスタマシンはより多くのフェッチと引き換えにより少ない実行命令を使います。

EVM の設計者はこの代価を受け入れ、実装の単純さと仕様の確定性を取り戻しました。近年は小さな漸進的改善もあり、たとえば PUSH0（EIP-3855、Shanghai）は 2 バイト・3 ガスの PUSH1 0x00 を、1 バイト・2 ガスの命令で置き換えました。

この設計はどのような条件で負担になるか

式のネストが深く、関数の引数が多いほど、スタックの並べ替え命令の割合が上がり、コントラクト実行のガス消費もそれに伴って高くなります。ビット幅の扱いでは、EVM に生来の 8 ビット、32 ビット、64 ビット型はなく、すべてを明示的に切り詰めるかマスクする必要があり、他言語からの移植では特に注意が要ります。

スタック深は 1024 ですが、ここの 1024 は、よく混同されるもう一つの 1024 とは別物です。イエローペーパーは CALL/CREATE の定義で、呼び出しの深さも 1024 に制限しています。前者は単一フレーム内のオペランド数を制限し、後者は呼び出しチェーンの長さを制限します。前者に引っかかるのはプログラムの誤りで、後者に引っかかるのは通常、再帰の書き方が正しくないことを意味します。

もう一つ境界を引いておきます。スタックマシンは並列実行の障害ではありません。並列が扱うのはグローバルな可変状態の下での読み書きコンフリクトであり、オペランドがスタック上のどこにあるかはスタックの順序から暗黙に決まる事柄で、コンフリクト検出や実行の決定性とは関係ありません。本当の制約は状態層にあり、それは後続の記事の範囲です。

出典

• Ethereum Yellow Paper（マシン状態の 6 つ組、スタック上限 1024、メモリコストの式、JUMPDEST のジャンプ先集合、異常停止関数 Z、ガス費用表とオペコード表、ECREC プリコンパイルの価格）：https://ethereum.github.io/yellowpaper/paper.pdf
• ethereum.org、Ethereum Virtual Machine (EVM)（スタック深 1024、256 ビット語長と Keccak-256 / secp256k1 の関係）：https://ethereum.org/developers/docs/evm/
• ethereum.org、Understanding the Yellow Paper's EVM Specifications（スタックマシンは実装が容易なため欠陥が少ない、256 ビット語の選択理由）：https://ethereum.org/developers/tutorials/yellow-paper-evm/
• Keccak Team、Keccak specifications summary（SHA3-256 のサフィックスビット 0x06 とパディング過程）：https://keccak.team/keccak_specs_summary.html
• Keccak Team、The Keccak reference, version 3.0（原版 Keccak のマルチレート・パディング pad10*1）：https://keccak.team/files/Keccak-reference-3.0.pdf
• NIST、FIPS 202（SHA-3 のパディング 0x06）：https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
• EIP-3855、PUSH0 instruction（0x5f、2 ガス、1024 個と 1025 個の PUSH0 のテストベクトル）：https://eips.ethereum.org/EIPS/eip-3855
• EIP-140、REVERT instruction（ロールバックするが残りガスをすべては消費しない。例外に退化する境界も）：https://eips.ethereum.org/EIPS/eip-140
• Davis、Beatty、Casey、Gregg、Waldron、The Case for Virtual Register Machines、2003（JVM バイトコードを仮想レジスタマシンへ変換し、実行命令数の減少とバイトコード・フェッチ回数の増加を報告）：https://mural.maynoothuniversity.ie/id/eprint/10191/1/KC-Case-2003.pdf
• Solidity 0.8.0 Release Announcement（算術演算の既定チェック、Panic(0x11) でのリバート）：https://www.soliditylang.org/blog/2020/12/16/solidity-v0.8.0-release-announcement/
• ethereum/execution-spec-tests（PUSH0 とスタックオーバーフローの仕様テスト）：https://github.com/ethereum/execution-spec-tests

関連記事