ダメ人間オンライン

あまり信用しないほうがいい技術メモとか備忘録とかその他雑記

The scrypt algorithm

scrypt(scriptではない)について調べた。何か間違ってたらご指摘下さい。

ググらビリティが最悪すぎて情報を探すのにすごく苦労した。。

Proof-of-work

BitcoinのProof-of-workではSHA-256が使われてるけど、LitecoinやMonacoinの場合はscryptっていうのが使われてるらしいってのを知って興味持ったので調べてみた。

scryptとは

Tarsnap - The scrypt key derivation function and encryption utility

  • ハッシュ方式の1つで、計算時に大量のmemoryを必要とするよう設計されている。
  • memoryを大量に必要とすることでブルートフォースアタックへの耐性を高めていると主張。
  • 一度の演算でmemoryリソースが大量に必要となればハードウェアにそれなりのスペックを要求することになる。
  • 昨今SHA-256の演算とかだと専用のチップとかですげー速さで演算できたりするらしいけどそういったことを困難にしている。

アルゴリズム

本家資料
http://www.tarsnap.com/scrypt/scrypt.pdf

簡易的な説明(図がわかりやすい)
http://alpha-t.net/wp-content/uploads/2013/11/Alpha-Technology-Scrypt-Analysis-on-FPGA-proof-of-concept.pdf

日本語での詳細な説明!!!(日本語での解説はこの方のblogしか見つけられなかった)
scryptを実装してみた 前編 | プログラマのつれづれなるままに

正味本家の資料見ただけじゃちんぷんかんぷんすぎて頭が痛くなった。。
頭の悪い俺にもわかりやすい資料を~~って探して図がわかりやすいのを見つけた。 なんとなく全体像がわかったけど詳細部分がいまいちまだ理解できなくて探してたら日本語で詳しく解説してるエントリ(最高!)を見つけて大体大雑把な感じで理解した。

細かい部分を理解するにはやっぱりコード見るのが早いなってことでscrypt実装のコード探してみた。

scrypt - Wikipedia, the free encyclopedia
ここに色んな言語での実装一覧があって、あっPerlもある~~~って思って見てみたけどXSで書かれてて全然読めなかった。つらい。
RubyとかPHPとかのコードもなんか .c ってファイルが見えたりしてアッアッてなって自分の無能さがただただつらかった。

で、ひと通り見て自分にとってはJavaの実装が一番わかりやすかった。
https://github.com/kocakosm/pitaya/blob/master/src/org/pitaya/security/SCrypt.java

ここまでの資料とか図とかコードとかを全部見てようやくなるほどーって感じになった。

キーとなっているのは BlockMix って書かれてるとこの処理で、ROMix の中で2回 BlockMix のフェーズがある。
どちらのフェーズでも1024回ループぶん回して(CPU/memoryのコストパラメータが 1024の場合) Salsa20(Rounds => 8) でハッシュ値をこねくりまわしてる。

最初のフェーズでは演算毎に得られたハッシュ値を全て保持するようにしている。ここがmemoryを一番使うところで、例えばブロックサイズのパラメータが 1 でCPU/memoryのコストパラメータが 1024 とかだと 128 * 1 * 1024 = 128kB のmemoryサイズを必要とする。
ブロックサイズのパラメータやCPU/memoryのコストパラメータを変更すると必要なmemory量も変化する。

2度目の BlockMix のフェーズでは上記で演算した結果を用いて1024回ループぶん回している。

memoryを必要としている仕組みがこれでわかったのでスッキリした。

スッキリしたついでに理解できてるかの確認も含めてXSじゃないPerl実装書いてみようかなと思ったけど、技術力もなけりゃ元気もないのでやめた。(`ェ´)ピャー

まとめ

たぶん2ヶ月もすれば全て忘れそう。