セキュリティ競技CTFの問題サーバーでは、接続者に計算問題を解かせることによって大量のリクエストを抑制する Proof of Work(PoW)というものが使われることがある。 解を探すには多くの計算が必要だが、サーバーは解を少ない計算で検証できる。
ここでは、与えられた文字列 prefix に非負整数
nonce の十進表記を連結し、SHA-256 ハッシュ値の先頭が
bits ビット以上連続して 0 となる nonce を探す。 SHA-256
は入力から 256
ビットの値を計算するハッシュ関数であり、出力から入力を逆算する方法が知られていない。
例えば prefix が ctf-demo:、nonce が 123 なら、入力は
ctf-demo:123。
ハッシュ値を一様なランダム値とみなすと、1 回の試行が成功する確率は約
2^(-bits)、解までの平均試行回数は約 2^bits
になる。 ただし、指定した範囲内に解が存在する保証はない。
limit - 1 まで順に試す。solve モードは最初の解で停止する。bench
モードは解を見つけても全候補を調べ、発見数を数える。 性能比較では同じ
prefix, bits, limit の bench
を使い、早期終了による実行時間の違いを避ける。
bench の 10 億候補の時間が約5分、約325万hash/sec。
bench
の発見数は最後に合計し、最小 nonce を集約すれば逐次版と比較できる。