部分ハッシュ衝突に基づく郵便料金方式
この数日、暗号のメーリングリストで、部分ハッシュ衝突に基づく郵便料金方式の話をしてきた。部分ハッシュを使う発想は、（衝突させるビット数を選ぶことで）計算の費用をいくらでも高くできる一方、検証は一瞬で済む、という点にある。
この考えを最初に形にした実装は、ここから取得できる。
- hashcash.tgz
- hashcash.tgzのPGP署名
この実装で何ができるかを、プログラムを使いながら例で説明する。よければ手元で試しながら読んでほしい。
部分ハッシュ衝突の生成器（hashcash mint）とリメーラーのプラグインを一体にしてある。リメーラーのプラグインは、タイプIのリメーラーには簡単につなげられるはずだ。タイプIIや仮名サーバーでは、mixmasterのクライアントとリメーラーに手を入れる必要があるが、それが比較的簡単にできるようにコードを設計してあり、mixmasterやalpha、newnymに直接組み込める。
コンパイル
% gcc -O6 -c *.c
% gcc -o hashcash hashcash.o sha1.o
% gcc -o sha1 sha1file.o sha1.o
% gcc -o sha1test sha1test.o sha1.o
%プログラムが提供する機能は次のとおり。
引数なしで実行すると、フラグの一覧と短い使い方を表示する。
速度の測定：
% hashcash -t
speed: 7218 hashes per sec
%1秒間に探索できるハッシュの数がわかる。（注：使っているsha1の実装は最適化していない、私の参照実装だ。速さを追求したsha1の実装がもう一つあり、あと30分ほどの作業で同じインターフェースになるので、あとで差し替える。sha1.cにコメントとして入れてある。）
17ビットの部分ハッシュ衝突を見つけるのにかかる時間の見積もり：
% hashcash -t -17
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
estimate: 9 seconds
%（実際にかかる時間は見積もりからかなりばらつく）
文字列「flame」で17ビットの衝突を計算する
（flameは、いまはもう動いていないリメーラーだ）：
% hashcash -17 flame
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
collision: 09948flame356018443
tries: 57450
%衝突は実際には、1970年1月1日からの日数（先頭をゼロで埋めた5桁）と、与えた文字列を並べたもののハッシュに対して探す。
つまり、次のものとの衝突を探している。
% echo -n 09948flame | sha1
fbbea210abafe3e72afe7849eaea2052e309e017
%衝突はダイジェストの上位ビットに限っているので、見つかった衝突は手で確かめられる。
% echo -n 09948flame356018443 | sha1
fbbead76da651cf856f7466fed9624d3ada061d9
%先頭の20ビットが一致しているのが手で確かめられる。（17ビットを求めたが、生成されるのは17ビット以上の衝突だ。たまたま運よく3ビット余分に一致した。これはおよそ8回に1回起きる。）
hashcashのクライアントは、衝突を報告することもできる。
% hashcash flame 09948flame356018443
collision: 20 bits
%今日の日付と比べて、有効期間を確かめることもできる。
% hashcash flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
%ハッシュが求めたビット数を満たしているかを確かめることもできる。
% hashcash -25 flame 09948flame356018443
collision: 20 bits
required: 25 bits
rejected: too few bits
%どれかの検査に通らなければ、終了コードは失敗になる。つまり、ビット数が足りない場合、あるいは有効期間を確かめてハッシュが期限切れかまだ有効期間に入っていない場合だ。
二重支払いの防止
選んだ有効期間のあいだ、衝突を覚えておくようhashcashのクライアントに頼むこともできる。
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 20 bits
database: not double spent
adding: 28 09948flame356018443
%衝突が追加されるのは、すべての検査（有効期間内であること、求めたビット数を満たすこと）に通った場合だけだ。終了コードでも、ハッシュが問題なかったかがわかる。
メールの受け手が新しい支払いを受け付けるたびに、データベースは際限なく大きくなってしまう。そこで有効期間をデータベースに記録しておき、有効期間が切れたあとの次の利用のときに、その衝突を捨てる。期限の切れた衝突を取っておく必要はない。期限切れのものはどのみち受け付けないのだから、前に受け付けたかどうかは関係ない。有効期間0は無期限の意味で、データベースから捨てられることはない。
二重支払いの例
新しく加わった検査は、そのハッシュが前に提示されたことがあるかどうかだ。そこで上と同じコマンドを実行すると、データベースに入っているので、使用済みとして拒否されるはずだ。
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 25 bits
rejected: too few bits
database: double spent
%（二重に使われた支払いなので、終了コードは失敗になる）
以上
ごく軽くしか試していないので、何か壊れたら知らせてほしい。
ところどころ効率の悪いところがあるが、まず動くコード、効率はあとだ。
（それから、私のSHA1の実装はビッグエンディアンのマシンで試していない。理屈の上では、バイトの並びを自動で判定する。）
これまでに話に出たリメーラーでの使い道
- 出口のリメーラーでの、投稿ごとの郵便料金
- 受け取るメールのスパムの選り分け。20ビットのハッシュも1セントのdigicashも付いていなければ、必要な郵便料金と、ソフトウェアの入手先を説明する通知を付けて突き返すプログラムを用意しておく。100万通×20で100 MIPS年になり、スパム業者が持っている計算力を超えるうえ、100万通×1セントで1万ドルは、スパムで得られそうな売り上げを超えるだろうから、スパム業者は一晩で商売にならなくなる。
- 仮名サーバーの利用者の行儀のよさを担保する保証金。仮名サーバーの利用者は、返信のできる仮名サーバーのアカウントのために、仮名サーバーに（大きめのハッシュ衝突、または25ドルのdigicashで）支払う。契約を破れば、仮名サーバーがそのdigicashや衝突を没収してアカウントを止める、という罰則の条項の付いた契約に同意する。利用者の身元はわからないが、もう一度参加するには、また大きなハッシュ衝突か、さらにdigicashを払わなければならない。
- ほかにも試せる考えはたくさんある。
これはdigicashとどう関係するか
リメーラーやメールにdigicashの郵便料金を使えれば便利だが、digicashには問題がいくつかある。
- アカウントを作るのが面倒だ（書類の記入など）
- アカウントを持っている人が少ない
- 匿名になるのは支払う側だけで、売る側は匿名にならない
そこで提案したいのは、ハッシュ衝突の郵便料金とdigicashの郵便料金のどちらでも受け付けるリメーラーだ。このやり方には次の利点がある。
- digicashがもっと広く使われるようになるまで、Hashcashがつなぎの役を果たせる
- Hashcashは無料で、PCのCPUをいくらか回すだけで使える。誰もが自由に発言するネットの文化にも合っていて、懐の寂しい者でも、百万長者や引退した政府の役人などと対等に渡り合える。
- digicashがだめになったとき（違法にされたり、利用者の身元の預託を義務づけられたりしたとき）にも、Hashcashがあればスパムを抑える予備の手段が残る。
コメント、コードなど、何でもありがたく受け取る。いくつかのリメーラーでアルファ版を試してもらえると、なおありがたい。
アダム
--
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`