2014-02-26

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ヶ月もすれば全て忘れそう。

2014-02-25

いまさらBitcoinの仕組みについて調べてみた

Bitcoinって聞いたことあるけど「アーハン、ネット上の仮想通貨みたいなやつなんでしょ。あとなんかハッシュめっちゃ計算する必要があるとかなんとか」ぐらいの理解で、「儲かる！」「いや、今はもう儲からない！」とかは耳に入ってたけどあまり興味もてなかった。

けど先週末あたりに Monacoin をきっかけに急に興味持ち始めて色々調べてみた。

Bitcoinとは

ざっくり言うと P2P型の決済網及び暗号通貨とのこと。

俺の下手くそな説明見るよりこれ見たほうが早い
Bitcoin-ビットコイン-とは何か？
ビットコインの採掘とは実際には何をしているのか？

元となった論文(pdf)
http://www.bitcoin.co.jp/docs/SatoshiWhitepaper.pdf

公式FAQ
Bitcoin P2Pベースの仮想通貨 - ビットコイン

氏名とか口座番号とかなくても気軽に送金・受取ができるようになるのは良い。

よくわからなかったとこ

上記の資料読んだり他にもwebでもろもろ調べたり、実際にpool(採掘場)に登録してcoin採掘してみたりしたけど仕組み的によくわかんないとこがでてきた。

ハッシュ値計算中に貨幣取引トランザクションを追加する必要が出た場合

ある時点での取引トランザクションを含めたブロックでハッシュ値計算をしてる最中に新たなトランザクションが追加された場合、次の計算はそれを加えるべきか無視して次のブロック計算にまわしていいのか、加えてしまった場合また1から計算しないといけないので無駄になるのではないか、とか明記されていないことについて疑問に思った。

結論から言うとこの疑問自体が間違ってて、新たなトランザクションが追加された場合は普通にそれを加えて計算すればよい。
というのもハッシュ値の計算には複数パラメータが必要で、そのパラメータの中にブロック生成の時間(unixtime)が含まれているので1秒毎にハッシュ計算元の値は変化する。
これは全マイナー同様なので採掘の性能として重要なのは単純に1秒間の演算処理能力だけである。なのでどっちみち変化するのでトランザクション追加したところで何も変わらない。すごく乱暴に言うと1秒毎にヨーイドンを繰り返してるようなもの。
重要なのは1秒間にどれだけの数のNonceを試行できるかということ。

Block hashing algorithm - Bitcoin

pool(採掘場)利用時、支払先アドレスがpoolのものになるのでnonceを除いた計算元のハッシュがユニークにならずnonceがかぶったりするのでは？

ソロマイニングだと支払先アドレスが自分のものになるので生成するハッシュは(ほぼ)必ずユニークになるが、poolだとその部分が固定になっちゃうのでnonceがかぶったりするのどうしてるんだろうと思った。

poolが各nodeに「あなたはnonce何番から～」とか指示したりしてるのかなとか、nonceはインクリメンタルじゃなくランダムな数値を使って試行してるのかなとか考えて MPOS とか cpu-miner とかのソースコードを適当に読んでみたけどそうではなさそうだった。

pool利用時はstratumっていうプロトコル使っててそこのドキュメントにそれっぽいことが書いてあった。
Stratum mining protocol - mining.bitcoin.cz

Extranonceという値を用いてcoinbaseのトランザクション(のserialization)をユニークにしてるらしい。
この例で言うとScryptSigかScriptPubKeyのことなんかな？トランザクションの生成のとこはちゃんと読んでないから間違ってるかもやけど。
http://blockexplorer.com/tx/51d37bdd871c9e1f4d5541be67a6ab625e32028744d7d4609d0c37747b40cd2d

へーなるほどーって思ったけど英語誤読してる可能性もワンチャンある。

ブロックに含めるトランザクションがMerkle TreeのRoot Hashだけで良い理由

基本的にnode間ではブロックチェーンだけやりとりしてるから Root Hash だけあったところで詳細なトランザクションの検証をあとからするには情報が足りないのではと思った。

どっかに明記されてたわけじゃないけど、マイナー(採掘)ノードじゃなく財布ノードのほうで分割してデータ持ったりしてんじゃないかな。以上。

おわりに

だいたい理解できたつもりでいる。

あとはBitcoinはいいけど、Litecoin とか Monacoin は SHA-256 じゃなく scrypt って方式でやってるらしい。よく知らないからこれもちゃんと調べときたい。ググってもちゃんとした情報見つけられなくてよくわかんなかった。

採掘は今Monacoinだけでやってて、だいたい 300kh/s ぐらい。
Monacoin はまだできたばっかで利用用途とか考えたりするのがおもしろそう。投げ銭推奨派なのでこの先楽しみ。Monacoinについてはまた別途書く。たぶん。

気軽に投げ銭してくれてもいいんですよ？

2013-10-01

進捗どうですか？

進捗ダメです

大体インターネッツのせいでダメなこと多いので、人間から怒り口調で聞かれるより前に優しく聞いてくれるChrome拡張書いた。
dameninngenn/chrome-ext-shinchoku-san · GitHub

f:id:dameninngenn_owata:20131001025607g:plain

ウェッッッブページ開いた回数をカウントして指定した回数に達したら通知が出る。回数は自分で設定できる。

2013-09-25

YAPC::Asia Tokyo 2013に行ってきた&LT-THONで話してきた

Perl

今年もYAPC::Asia Tokyoに行ってきました。

前夜祭

LT-THONで話しました。
前半は前夜祭であるということをお伝えし、後半はここ一年ぐらいで書いたコードのことをいくつか話しました。

Yapc2013 ltthon from ダメ人間

誕生日ですっつってあんなに拍手もらったの人生で初めてで、社交辞令的拍手だとわかってはいても嬉しいものでした。

あ、そういえば今日は25日ですね。多くの方は今日給料日ではないでしょうか？有益なURL置いておきますね＾＾

https://www.amazon.co.jp/registry/wishlist/2NFCUB363SFD8

まだ間に合いますし遠慮しなくていいんですよ＾＾＾

あと質疑応答で「コメントは差し控えさせていただきます」みたいなこと言ったのは、名前挙がった方とは面識ないので(もちろん一方的に知ってはいる)何も言えなかっただけです。。

前夜祭の会場は結構広かったんですが、後ろのほうまで机が並んでいてみんなちゃんと座る感じだったのでみんなLTを聞き入ってた感じでした。後ろ1/3ぐらいは机とっぱらってLT聞きたい人は前のほう座って後ろのほうは人と話して交流できるような感じにしとくのもアリだったのかなとも思いました。

LT-THONは気楽に参加できるので、今年も開催されて嬉しかったし楽しかったです。ありがとうございました。

1日目

急行乗ってると思ったら特急乗ってて日吉余裕で通りすぎて遅刻した。

1日目で一番印象に残ったのはおまけの話だったけど Regexp::Debugger で、なんかワクワク感がすごかった。ワクワク人間。

某非公式イベントもすげーおもしろくて良かった。特にyusukebeさんが親指を立てながら溶鉱炉に沈んでいくシーンは涙無しには見られなかった。

2日目

座談会のセッションおもしろかった。今回のYAPCで一番楽しみにしてた。

懇親会ではビールこぼしておもらししたみたいになってしまった。実際におもらししたとしてもみんな酔っ払ってたのできっと気づかれないし何も問題はなかった。

まとめ

今年も3日間とても楽しかった。スタッフの方々や皆様に感謝です。

ちらっと話が出てたYAPC::Tohokuも楽しみですね。

さて来年は・・・

2013-09-07

mod_cacheとVaryヘッダ

apache

mod_cahceで画像をキャッシュしてる場合は画像に"Vary: User-Agent"つけないようにしましょうという話

はい

外部ストレージで画像を管理してて、表示時に毎回その外部ストレージに取りにいかなくて済むようにフロント側でキャッシュしとくというのはよくある話(?)だと思います。

例えばapacheの設定で

RewriteEngine on
RewriteRule ^/images/(.+)$  http://external.storage.dameninngenn.com/images/$1 [P,L]

<IfModule mod_cache.c>
    CacheRoot /dev/shm/mod_cache
    CacheEnable disk /images
    # ...
</IfModule>

みたいにしておくと /images/hoge.jpg にリクエストきた場合キャッシュされてなければ外部ストレージにとりにいって表示して、キャッシュされていればそれを返すという風になります。

このままだと特に問題はないのですが、ここに"Vary: User-Agent"が入っているとUser-Agent毎にキャッシュが保存されてしまいキャッシュサイズが膨れ上がります。
今回のケースだとdiskキャッシュだけど/dev/shmを使ってるのでモリモリメモリ使ってあげくswapしまくって人間が死ぬ。

画像にはVaryヘッダつかないようにしとくでしょーって思うかもしれませんが、結構コピペとかでうっかりがあったりするもんです。

例えばdeflateの設定部分で全部にVaryつけても問題ない場合だと

Header append Vary User-Agent

としてたり。

SetEnvIfNoCase Request_URI \
    \.(?:gif|jpe?g|png)$ no-gzip dont-vary

Header append Vary User-Agent env=!dont-vary

こうするとか。
http://httpd.apache.org/docs/2.2/mod/mod_deflate.html

余談

なんかのプロセスがswap領域使ってる場合とかだと割りと簡単にどのプロセスが使ってるかっていうのはわかるけど、プロセス以外の何かがswap使ってる時にどいつがswap使ってるのかをどう調べたらいいか全然わかんなかった。

swap使ってるのはコイツですよーってすぐ分かる方法があれば知りたい。。

プロセス以外だとだいたい目処がついたりするもんなんかな？あそこかあそこかなーぐらいの。
いかんせんそこらへんの知識が貧弱なので色々身に付けたいけど、実際に問題が起きて自分でトラブルシュートして始めて身についたりするもんだとも思ってるので難しい。

ダメ人間オンライン

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