最近、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. まとめ
