アルゴリズムとかオーダーとか

仕事で勉強したことなどをまとめてます

Poseidon Hash Contractを1.97Mガスから34.9Kガスまで削減した話

最近、EVM上のPoseidonハッシュを57分の1のガスまで削り込んだ話をXにツイートした。

https://x.com/nakajo/status/2071157014399701442

コードはこちらに公開している。

https://github.com/chaintope/poseidon-goldilocks

ツイートには結果の数字しか書けなかったが、そこに至るまでにはガス削減を見込んで試したのに、実測すると減らなかった施策のほうが圧倒的に多い。むしろそちらのほうが記録として価値がある。本記事では、何をどう測り、どこを削り、どこで削れなくなったのかを最初から順に書いていく。

対象はplonky2互換のPoseidon-Goldilocksハッシュ関数のコントラクトである。plonky2の実装とbit-exactに一致させることが絶対条件になる。

先に結論を述べておくと、コンパイラの最適化フラグでは45%程度しか削減できなかった。そこでassemblyとYulでバイトコードを直接書き、最終的に98%の削減に成功した。

  • TL;DR
  • 1. 何を測るか
  • 2. 出発点 — 素朴なSolidity実装
    • 2.1 コンパイラフラグでは45%しか削れない
  • 3. 最適化の前に — AIに回させるためのハーネス
  • 4. 第2段階 — solc + インラインアセンブリ
    • 4.1 MDSを展開し、stateをスタックローカルに保持
    • 4.2 fast partial rounds(O(n²) → O(n))
    • 4.3 定数をPUSH即値にインライン
    • 4.4 EIP-170でライブラリ分割 → デプロイ可能に
    • 4.5 ステージ間で渡すstateを12ワードから3ワードに詰める(−10%)
    • 4.6 ラウンドstateのスタックキャッシュ + in-place書き戻し(−15%)
    • 4.7 partial roundの mod p を最後の1回にまとめる(−8%)
    • 4.8 4→2ステージ統合(−3.7%)
    • 4.9 partial roundのS-boxを単回計算に矯正する(−11%) — optimizerの再計算を止める
    • 4.10 第2段階の変遷
  • 5. 第3段階 — 手書きの2ステージYul
    • 5.1 MDSから mod を外し、命令を安いものに置き換える
    • 5.2 入力の取り出しと第1ラウンドのS-boxを一体にする
    • 5.3 最後のfull roundのMDSと、その次の層を1つにまとめる
    • 5.4 最終MDSの出力を、そのまま3ワードに詰めて返す
    • 5.5 permuteを2つのコントラクトに分け、stateは3ワードで渡す
    • 5.6 関数呼び出しをなくす — インライン化はoptimizerがやってくれない
    • 5.7 レーンをスタックに常駐させる — ただし8本目で悪化する
    • 5.8 細かいが積み上がるもの
    • 5.9 ビルド設定の勘所
  • 6. 結果
  • 7. 失敗した施策
    • アルゴリズムと数値の限界
    • コンパイラの限界
    • ビルドフラグの限界
  • 8. まとめ
続きを読む

EIP-1822 UUPS

タイトル: EIP-1822 UUPS

前回は、Upgradable Proxyにおけるストレージ衝突を2種類に整理した。(1)はProxyの管理変数とImplementationの業務変数が同じslot 0を奪い合う衝突、(2)はアップグレードでV1とV2のレイアウトがずれる衝突である。この2つを念頭に、本記事ではEIP-1822(UUPS)を読んでいく。

先に結論を述べておくと、1822は衝突(1)を解決するためのEIPである。

  • UUPSとは何か
  • 解決策(a): keccak256("PROXIABLE")に配置することで衝突を回避
  • 解決策(b): アップグレードロジックをLogic側に置く
続きを読む

Storageの衝突問題

最近、EthereumのProxyまわりの標準化について改めて調べている。EIP-1822(UUPS)、EIP-1967、ERC-7201といった一連の標準は、いずれも「ストレージスロットの衝突」という一つの問題への解答として提案されてきたものである。これらを歴史的な流れに沿って読み解いていく記事を書こうと思う。

本記事では、個々の標準の解説に入る前に、そもそも何が問題だったのかを整理しておく。問題点を明確にすることで、以降の各EIPの内容を理解しやすくするのが狙いである。

  • 前提1：Solidityは状態変数をスロット番号に割り当てる
  • 前提2：delegatecallは呼び出し元のストレージを共有する
  • delegatecallが使われる場面
  • Upgradable Proxyにおける2種類の衝突
    • (1) Implementation addressスロットの衝突
    • (2) アップグレード時のレイアウト破壊
  • なぜアップグレードでレイアウトが変わるのか
  • まとめ
続きを読む

EIP-7702の後方互換性 (Backwards Compatibility)

EIP-7702は、イーサリアムの既存の不変条件（Invariants）をいくつか破る変更を含んでいます。 本記事では、EIP-7702の仕様書で言及されている3つの不変条件に加え、EOAの判定方法の変更について、詳細と関連する go-ethereum の実装コードを交えて解説します。なお、本記事の作成には生成AI(Gemini3 Pro)を活用しています。

※invariantsを記事内ではわかりやすく直訳的に「不変条件」と記載してますが、本来の意味を汲むとしたら「暗黙的に守れてきた一貫性」などと意訳したほうが正しいと思います。これらの条件はプロトコルで厳格に守られているものではなく、副次的に一貫性が保たれてきたためです。

  • 1. アカウント残高の減少 (Account Balance Decrease)
  • 2. EOA nonceの増加 (EOA Nonce Increase)
  • 3. tx.origin == msg.sender の意味 (Topmost Frame)
  • 4. EXTCODEHASH の挙動変化 (EOA判定の崩れ)
  • 付録A: EIP-7702トランザクションの実行順序
  • 付録B: 委任コードに対するEXTCODEHASHの挙動について
続きを読む

Spec Kit + Claude Codeを試してみた（感想雑記）

最近話題の Spec Driven Development を試してみた感想記。ツールはspec kit を利用した。

spec kitのインストール方法などは下記を参考に行った。
azukiazusa.dev

簡単なLLM Chatアプリを作成。コードは以下のリポジトリにアップしている。
github.com

spec kit利用で期待したことは以下の３つ。
1. ある程度大きなタスクをClaude Codeで自走できるようにしたい
2. 仕様を明確化してAIと共同作業ができること
3. TDD順守による仕様に準拠したコードをLLMが生成できること

以下、試してみた感想をつらつらと書いてみる。

  • 自分のAI利用状況
  • 率直な感想
  • やったこと
  • 「現状の」LLMの限界
  • LLMができること・できないこと
  • LLMのコードはなぜに読みにくいのか？
  • 今のagentやcontextを与える方法の限界
  • coding LLMは使えない？
続きを読む

EIP-7702の署名対象とリプレイ保護

本記事ではEIP-7702について学習しているときに浮かんだ以下の2点の疑問について、go-ethereumの実装とEIP-7702の仕様を詳細に分析して解説する。

1. auth listに含まれる署名は何に対して署名をしてるのか？
2. auth listの署名を使ってリプレイ攻撃されないのか？

EIP-7702については過去記事を参考：
y-nakajo.hatenablog.com

  • 1. Authorization Listの署名対象とメカニズム
    • 何に対して署名するのか？
    • 署名に含まれる3つの要素とその目的
  • 2. リプレイ攻撃防止とセキュリティメカニズム
    • EIP-7702で保護可能な攻撃
続きを読む

EIP-7702入門

Pectra Upgradeが行われてからだいぶたっており、いまさら感はありますが個人的にずっと気になっていたのでEIP-7702について調べたことをまとめる。
いつも通り、go-ethereumの実装を参照しながら、EIP-7702に動作について詳しく見ていく。まずは入門としてEIP-7702の基本的な動きを確認する。

続きを読む