前に、好きな文字で始まる Symbol のアドレスを探すページを、ブラウザだけで動くように作った。
ブラウザで探すのは手軽でいい。でも、文字を 1 つ増やすごとに 32 倍待たされる。6 文字くらいからは、だんだん正気を疑う時間になってくる😇 もっと文字を増やすと計算が終わる頃には私たちは化石になっているかもしれない🦴
ところで、手元には NVIDIA の GPU がある。GPU といえば最近は AI である。ブロックチェーン界隈は昔から「AI × ブロックチェーン」をやりたがっているけど、AI 界隈からはだいたい相手にされていない。そこに首を突っ込む勇気はないので、GPU のいちばん素直な使い道である、ひたすら総当たりをやらせることにした。総当り、つまりビットコインのマイニング……は参入障壁が高いので大人しくvanityアドレスの生成である。
しかも、自作の heika（Symbol の Rust のツールキット）を GPU 用に書き直すのではない。heika の、鍵とアドレスを計算する部分を、1 行も直さずにそのまま GPU に載せた。結果、CPU で探すより 80 倍ほど速くなった。やったぜぇ🎉 「なにもしてないのにうごいた」と言うやつである。
なぜ載るのか：no_std の話
GPU の上には OS がない。ファイルも、時計も、スレッドも、OS の乱数もない。Rust の標準ライブラリ（std）は、そういう OS の機能を前提にしているので、GPU の上では使えない。
使えるのは、core（OS がなくても動く、いちばん下の部分）と、alloc（メモリを取る仕組みさえ用意すれば使える、Vec や String の部分）だけだ。この 2 つだけで書かれたライブラリを、no_std のライブラリという。
heika の中で、署名やアドレスやハッシュの計算をする heika-core は、最初から no_std で書いてある。こここそ褒めるところである✨ この no_std こそ記事で一番チヤホヤすべきポイントである✨ とってつけた GPU の話なんておまけである。
#![cfg_attr(not(test), no_std)]
extern crate alloc;
#[cfg(feature = "std")]
extern crate std;
- OS の時刻を使う関数は、feature の
stdを付けたときだけ入る - 秘密鍵を作るのに要る乱数は、外から渡せる。OS の乱数は、feature の
getrandomを付けたときだけ使う
もともとは、マイコンやハードウェアウォレットのような、OS のないところでも署名できるように、という気持ちだった。CI でも、std のない組み込み向けのターゲット（thumbv7em-none-eabihf）でビルドが通ることを毎回確かめている。GPU のことなんて、これっぽっちも考えていなかった。本当にこんなことのために頑張ってたわけじゃないのに……😇
それが、nvptx64-nvidia-cuda（NVIDIA の GPU 向けのターゲット）でビルドしてみたら、何も直さずに一発で通った。感動！地道に no_std を守っていた昔の自分を末代まで褒め称えたい🥹
ちなみに、Symbol の公式の SDK はブラウザや Node.js や Python で使うのが前提なので、こういう芸当はできない。……いや、できるかも。できたとしても、苦行が多そうだけど……。そもそも誰もやろうと思わないし、やれるとしても誰もありがたがらないと思う。本当になんでこんなことしてるんだろう私……。
Rust から GPU へ
NVIDIA の GPU のプログラムといえば、ふつうは CUDA C++ で書く。
CUDA C++ ──nvcc──▶ PTX ──ptxas か、ドライバー──▶ SASS（GPU の機械語）
PTX は、NVIDIA の GPU 向けの中間の言葉で、ビルドしたときの世代より新しい GPU なら読める。動かすときにドライバーが、手元の GPU の機械語（SASS）にその場で変換してくれる。
今回は、PTX の手前を Rust に差し替えた。
Rust ──rustc（LLVM の NVPTX バックエンド）──▶ PTX ──ドライバー──▶ SASS
rustc の中の LLVM は、自分で PTX を書き出せる。なので、ビルドに CUDA Toolkit は要らない。要るのは、動かすところの NVIDIA のドライバーだけだ。
ビルドは 2 段になる。
- GPU で動く部分（カーネル）を、nightly の Rust で PTX にする
- ふつうの Rust で手元の側をビルドして、さっきの PTX を文字列として埋め込む
rustup +nightly target add nvptx64-nvidia-cuda
rustup +nightly component add llvm-bitcode-linker llvm-tools
cargo +nightly build --release -p vanitygen-kernel --target nvptx64-nvidia-cuda
cargo build --release
動かすと、手元の側が PTX をドライバーに渡し、GPU ごとの機械語にしてもらって、カーネルを起動する。Rust から CUDA のドライバーを呼ぶところは、cudarc という crate に任せた。
カーネル
GPU の 1 スレッドが動かす部分は、CPU で鍵を 1 個試すときと何も変わらない。
let key = candidate(seed, counter);
let address = Address::from_public_key(&PublicKey::from_private_key(&key), network);
if pattern.matches(&address.0) {
// 当たった番号を返す
}
PublicKey::from_private_key と Address::from_public_key は、heika-core の関数をそのまま呼んでいるだけだ。中では SHA-512、楕円曲線の計算、SHA3-256、RIPEMD-160 が動いている。GPU 用に書き直したところはない。ここがこの記事で注目のポイントである✨
GPU 向けに足したのは、これくらいだ。
-
extern "ptx-kernel"で、GPU から呼ばれる入口を作る（nightly の機能） - panic したときの行き先を書く。GPU の上では止まるだけにした
- メモリを取る仕組み（アロケーター）を置く
最後のがちょっと笑える。heika-core は alloc を使うので、つなぐにはアロケーターが要る。でも、鍵からアドレスを作る道筋では、実はメモリを 1 回も取らない。なので、「取ろうとしたら失敗する」だけのアロケーターを置いて黙らせた。できた PTX を見ても、外の関数を呼ぶところが 1 つもなかった。ちゃんと GPU の中だけで完結している。
模様
探したい模様は、正規表現っぽく書けるようにした。
| 書き方 | 意味 |
|---|---|
NAKAMOTO |
NAKAMOTO で始まる |
N.SUNBORU |
2 文字目は何でもよく、3 文字目から SUNBORU
|
N.*SUNBORU |
どこかに SUNBORU を含む |
最初は NSUNBORU（すんぼる）にしたかった。でも、Symbol のメインネットのアドレスの 2 文字目は、A〜D のどれかにしかならない。
アドレスは 24 バイトで、先頭の 1 バイトはネットワークで決まっている（メインネットは 0x68）。これを 5 ビットずつ文字にするので、2 文字目の 5 ビットのうち 3 ビットが、この決まったバイトにかかってしまう。残りの 2 ビットぶん、つまり 4 通りしか選べない。
なので、NSUNBORU は何年待っても出てこない。何年も待たされないように、探し始める前に「2 文字目が 'S' のアドレスはありません」と弾くようにした。仕方がないので N.SUNBORU で妥協した。すんぼるすんぼる……🥲
先頭だけなら、本当はもっと削れる
アドレスの 24 バイトは、こうなっている。
- ネットワークの 1 バイト
- 公開鍵のハッシュの 20 バイト
- チェックサムの 3 バイト（前の 21 バイトを、もう一度 SHA3-256 にかけたもの）
先頭の模様は、たいてい最初の 21 バイトで決まる。なので、本当はチェックサムの SHA3 は、当たったときだけ計算すれば足りる。でも今回は、heika-core の Address::from_public_key をそのまま使ったので、毎回律儀に計算している。だってこうしないと heika の no_std 対応を活用する話にならないんだもん……
その代わり、というか無理やり存在意義を保ってあげるために、N.*SUNBORU のような含む模様も探せるようにした。アドレスの後ろの 5、6 文字はチェックサムにかかるので、こっちでは SHA3 の計算結果をちゃんと使うことになる。SHA3 はいらない子にならずに済みました。めでたしめでたし✨
秘密鍵の扱い
アドレスを探すのは、要するに秘密鍵を大量に作ることだ。雑にやると、ほかの人に鍵を当てられてしまう。
実際、Ethereum の Profanity という vanitygen は、乱数の種が 32 ビットしかなかったせいで、見つけたアドレスから秘密鍵を逆算されてしまった。大金が盗まれる事件にもなった。こゎぃょぉ😱
今回は、こうしている。
- 候補の秘密鍵は、OS の乱数で作った 256 ビットの種に、通し番号を混ぜたもの。Symbol は秘密鍵を SHA-512 にかけてから使うので、番号が隣どうしの鍵でも、鍵としては関係がない
- GPU には、当たった番号だけを返してもらう。秘密鍵そのものは GPU から出てこない
- 手元で番号から鍵を作り直して、アドレスが本当に模様に合うかを確かめてから、ファイルに書く。GPU の答えは鵜呑みにしない
- 探し終えたら、GPU のメモリに置いた種を 0 で消す
速さ
同じマシンの CPU で探す（--cpu を付けると、CPU のコアの数だけスレッドを立てて探す）のとくらべて、GPU では 80 倍ほど速くなった。CPU で何時間もかかる模様が、GPU なら数分になる計算だ。
ただ、GPU を使い切れているとは言いにくい。起動するときに、カーネルが 1 スレッドで使うレジスターの数を出すようにしたら、255 個だった。1 スレッドが使える上限いっぱいである。
heika-core が楕円曲線の計算に使っている curve25519-dalek は、64 ビットの掛け算を前提に書かれている。GPU は 32 ビットの計算が得意なので、64 ビットの計算を細かく分けてやることになり、レジスターを食う。そのせいで、GPU に同時に載せられるスレッドが少なくなっている。そのあたりがどうも原因として怪しい。
試しに、curve25519-dalek に 32 ビットの計算を使わせてみた（--cfg curve25519_dalek_bits="32"。heika-core は 1 行も直さなくていい）。レジスターは 167 個まで減って、同時に載るスレッドも 1.5 倍になった。勝った！……と思ったら、1 割ほど遅くなった。計算が細かくなったぶん、手数が増えて帳消しどころかマイナスになった印象……。GPU、むずかしい😇
もっと速くしたいなら、GPU 向けに計算を一から書き直すのが本筋だろう。でもそれをやると、「heika-core をそのまま載せた」という今回の一番の売りがなくなってしまう。でもそのままの heika-core で 80 倍だしまあ多分申し分ない……ということにしておく✨私が認める😌
おわりに
no_std で書いておくと、思ってもみなかったところで使える。今回はそれが GPU だった。それも vanitygen だった。なんかくやしい。どう考えてもゼロ知識証明とか AI のほうがかっこいいのに！くやしい！そんな虚栄心のために no_std 対応したわけじゃないのにっっっ！手っ取り早いベンチマークだからまあいいけど……
GPU 用に計算を書き直していないので、署名やアドレスの計算が heika のほかの部分とずれる心配もない。CPU で確かめた結果と GPU の結果を同じ関数で突き合わせられるのも、地味にうれしいところだ。
ちなみに、Rust には AMD の GPU 向けのターゲットもあるらしい。そっちは標準ライブラリを自分でビルドするところからで、カードの世代ごとにビルドし分ける必要もある。なので、高まる虚栄心需要により GPU が逼迫した時は頼りたくなるかもしれない。
ちょっとした試作であって実用するつもりで作ったわけではないので、見つけたアドレスに大事なお金をオールインする前に、その秘密鍵で本当に送金できるかを、少額で一度確かめてあげてね💦