ビットコイン・インスティテュート

署名の検証を速くする

1件のメッセージ BitcoinTalk ハル・フィニー 2011年2月7日 — 2011年2月7日

別のスレッドで、[mike]がこう書いていた。

Quote from: [mike] on February 07, 2011, 12:10:44 PM

GPUを使ってECDSAを大幅に速くするアルゴリズムは、私の知るかぎりない。これを速くしたいなら(そもそも気にするなら、だが)、一番見込みがあるのは、secp256k1という曲線の特別な性質を利用することだ。

http://portal.acm.org/citation.cfm?id=1514739

http://www.hyperelliptic.org/tanja/KoblitzC.html

secp256k1の近道を実装しようとしているところだ。もうすぐ結果が出るはずだ。残念ながら、速くなるのは20%ほどだろうと見ている。結果を待とう。

署名の一括検証も調べている。

http://cseweb.ucsd.edu/~mihir/papers/batch.pdf

http://www.math.snu.ac.kr/~jhcheon/publications/2007/BatchVer_PKC2007_CL.pdf

これは、一度に検証する署名がたくさんあれば、理論上は検証を4倍近く速くできる(2本目の論文の表6)。ECDSAの署名の形式を少し変える必要がある。(r, s)を(R, s)に置き換えるのだ。Rは楕円曲線上の点で、rはそのx座標に当たる。この変更は、過去にさかのぼって適用できる。Rは署名を検証するたびに計算され、捨てられているからだ。

私たちの署名は、ブロックという形でまとまって届くことが多い。数十、ときには数百にもなり、これからも増えていく。一括検証は、すべての署名が有効なときに限って真を返す。正しいブロックに無効な署名が入っていることはないはずだから、検証をまとめるのは理にかなっている。

セキュリティの面で、調べなければならないことがある。Rが曲線上にあるか(つまりy^2 = x^3 + 7か)を確かめる必要はあるのか。そして、一括検証のテストがだまされる確率について、適切なセキュリティパラメーターはどれくらいか。論文は2^80と言っているが、それは慎重すぎるように思える。