Bitcoinで新しいブロックをダウンロードする仕組み
Bitcoinのノードは、基本的には最も長いチェーンのデータを保存しています。2019年1月24日現在、およそ558000ブロックほどが繋がっていますが、例えばいま僕の手元にある最新のブロックが558010だとすると、基本的には、その558010番目のブロックの次に繋がる558011番目のブロックが他のノードから送られてくるのを待っている状態です。しかし、ノードの中には、他のノードとの接続が悪くてまだ558009番目までしか手元になく、他の人がすでにマイニングしている558010番目のブロックの存在に気づかないまま、558010番目のブロックのマイニングに勤しんでいる場合もあります。そこで偶然その人が558010番目のブロックのマイニングに成功すると、その情報は他のノードに伝搬されて、僕の手元にも、二つ目の異なる558010番目のブロックが送られてくることになります。
ブロックが送られてくる、という表現をしましたが、実はこれは正確ではありません。いわゆる「ブロック」はそれぞれブロックヘッダーとブロックの中身に分解できます。ブロックヘッダーとは、前のブロックのヘッダーのハッシュ値や、そのブロックの中身の送金情報のサマリやナンスと呼ばれるものなど、合計80バイトの情報で構成されるもので、そのヘッダー自体をハッシュ化すると最初にたくさん0が並ぶようになっています。ブロックの中身には最大で1Mバイトの送金情報が詰められています。僕は他のノードから二つ目の558010番目のブロックがあることを伝えられた時、ブロックヘッダーだけまずは受け取ります。ブロックヘッダーを見れば、前の558009番目のブロックの次に繋げる気持ちで送られてきたことと、それをハッシュ化して0がたくさん並んでいることを確認することができ、ブロックの中身に本当は存在しちゃいけないものが混ざっている可能性は否定できないものの、0がたくさん並ぶようなものは相当頑張らないと作れないわけで、とりあえず将来的に最長のチェーンになるかもしれない候補生としてブロックの中身もダウンロードしてきます。ブロックの中身まで含めると1Mバイトになりますが、ブロックヘッダーだけだと80バイトだけなので、およそ1万分の1のデータをちょろっと見るだけで、めっちゃ頑張って作られたものであることが確認できます。実際に正しいブロックであるためには、ブロック内の送金が二重支払いされていないかの確認なども必要ですが、その確認をしようと思ったら、究極的には558010ブロックすべてを見なきゃいけないので、候補生の段階で絞り込まれているというのはすごく便利ですね。
UTXO型PoSで新しいブロックをダウンロードする仕組みとその脆弱性
そもそもUTXO型PoSがどういう仕組みかをまずは説明する必要があります。やりたいこととしては、コインを持っている数量に比例してマイニングに成功する確率が変わるけど、マシンリソースはほとんど必要のない仕組みを作ることです。そこで、マイニングに成功する条件を次のように定義します。
hash(前のブロックの情報で変更できない情報+自分の持ってるUTXOのTXID+16秒単位でしか変更できないtimestamp)<=定数k*そのUTXOにあるコイン数量n/全コイン数量N
普通の人の気持ちとしては、ブロック更新されるたびに自分のUTXOとその時のタイムスタンプを並べてhash関数通して、ワンチャン成功すればブロードキャスト、だめなら16秒後にもう一回、新しいブロックが来たら今度はそれをベースに、と続けていきます。この情報はcoinstake transactionという名前で、ブロックの中に乗っかることになります。
ちなみに、UTXOをたとえば１０個に分解すれば１０倍チャンスですが、一つ当たりの成功確率が1/10になってしまいます。数学的に厳密にいうと、UTXO一つにまとめた場合には自分がブロックを見つける確率はn/Nで、無限に細かく分割すると、1-exp(-n/N)の確率になり、n/N>1-exp(-n/N)が恒等的に成立するので、まとめ上げたほうがお得になり、ユーザーがUTXOを自発的にまとめあげてくれる副次効果もあったりします。
さて、この仕組みのブロックチェーンで、新しく送られてきたブロックが正しいことを確認するためには、coinstake transactionが正しいことの検証と、ブロックの中身に二重支払いのものがないかなどを検証することが必要になりますが、では、coinstake transactionはどのように正しいことを検証すればいいか、が問題になります。検証するポイントは、
①確かに上の不等式を満たしていることの証明
②そのTXをほんとにその人が所有していることを証明する署名
③そのTXがほんとにまだ使われていないこと(UTXOであること)の証明
となりますが、①と②は一瞬の計算です。しかし、③をやろうとすると、究極的には少なくともそのTX以降のブロックはすべて検証する必要が発生します。一応の注意書きとしては、Bitcoin含めUTXO型のブロックチェーンにおいては、毎回0ブロック目から確認するのは無駄なので、直近のブロック時点でのUTXOを手元に保存しておく運用なのですが、いま考えているシチュエーションは、最終的に正しいブロックとなる候補生がたくさんあるケースで、そうするとどの時点のUTXOの情報を使えばいいのか、という問題が発生することになり、やはりブロックをさかのぼって検証するほかありません。その背景から、③の検証はせずに、①と②の検証だけパスできたら、他のブロックの中身の情報をダウンロードしてくることになります。
そこで今回の攻撃手法が考案されました。すなわち、UTXOである必要はないのだから、自分が署名できる使用済みTXをたくさん用意して②をパスできるものをたくさん用意し、それらを使って①をパスできるものをたくさん作って、それにテキトーに作った最大サイズのブロックをくっつけて送り付ければ、ノードはそれらを全部ダウンロードすることになって、disk逼迫するやんけ！というワザです。
自分が署名できるTXをたくさん用意するのは簡単で、どこかの取引所からそこそこな数量のコインを買ってきて、自分の所有するウォレット間で送金しまくって、そこそこな量たまったら、取引所に送って売ればよいのです。ブロックチェーン上の送金手数料と、取引所の売買手数料をいくぶんか支払うだけで攻撃が可能というわけです。
この攻撃が使えるUTXO型PoSコインでショートできる市場があるものはなさそうであるゆえ、得られるメリットは特になさそうですが、暇を持て余した悪戯っ子クラッカーがお小遣い程度の出費でできてしまうので問題ですね。
参考：
https://blog.qtum.org/qtums-proof-of-stake-consensus-at-a-high-level-ea53e051ac66
https://medium.com/@dsl_uiuc/fake-stake-attacks-on-chain-based-proof-of-stake-cryptocurrencies-b8b05723f806