ビットコイン取引の裏側で働くブルームフィルタ

ブルームフィルタとは計算機科学におけるデータ構造の名前であり、ブルームフィルタは主に、スマートフォンのようなデータの通信量に制限がある端末を用いてビットコイン取引を行う際、効率的に必要なデータを判定し、収集するために使われている技術です。ビットコイン取引の裏側で動いているブルームフィルタについて知ることで、今後新たに効率的なデータ判定システムが登場した際にも素早く対応できるようにしましょう。今回のコラムではビットコインの内部で用いられているブルームフィルタという仕組みについて、どのような役割を担っているのか説明します。

ブルームフィルタとは

ブルームフィルタは計算機科学におけるデータ構造の名前で、他のデータ構造に比べて非常に高速に、データが存在するか否かという判定を行うことができます。またブルームフィルタの特徴として、「膨大なデータの中から必要なデータが存在することを確実に見つけ出すが、不要なデータについても必要なデータであると判定してしまう可能性がある」という点が挙げられます(偽陽性が発生する)。逆にブルームフィルタは「膨大なデータの中に必要なデータが存在しない場合には、データが存在するとは判定しない」という特徴も持ちます(偽陰性は発生しない)。より簡潔に表現すると「必要なデータの取りこぼしは起こさないが、不要なデータも多く混じる」となります。このことを利用し、スマートフォンのようにストレージ容量や通信容量が限られている端末でもビットコインを快適に利用できる仕組みが実現されています。

偽陽性と偽陰性についてもう少し踏み込んでご説明します。偽陽性は「偽物なのに本物であると判定する」ことを意味します。統計用語では「第一種の過誤」とも呼ばれます。身近な言葉に置き換えて「濡れ衣」とも呼ばれます。犯人ではない(偽物)のに犯人(本物)である、と判定してしまうことです。逆に、偽陰性は「本物なのに偽物であると判定する」ことを意味します。統計用語では「第二種の過誤」とも呼ばれます。こちらも身近な言葉に置き換えて「見逃し」とも呼ばれます。犯人(本物)なのに犯人ではない(偽物)である、と判定してしまうことです。ここで、ブルームフィルタは偽陽性、すなわち「濡れ衣」が発生する可能性はあるものの、偽陰性、すなわち「見逃し」は発生しない、という特徴を持っています。この特徴を利用することでビットコイン取引の際も「まず大まかに、しかし取りこぼしは無いように、必要なデータが存在するか否かを判定」することができます。

非常に大きなデータに対し、目的とするデータが存在するか否か、厳密に判定しようとすると膨大な時間がかかります。これに対してブルームフィルタは先述のように「まず大まかに、しかし取りこぼしは無いように、必要なデータを判定」します。その後、ブルームフィルタによって高速に判定された「大まかなデータ」に対して厳密な判定を行うことで必要なデータのみを絞り込みます。上記の手続きを経ることで、効率的に、かつ取りこぼすことなく必要なデータを集めることができます。

ブルームフィルタと SPV

SPV (= Simplified Payment Verification) とはブロックチェーンの中から必要なデータだけを判定・抽出し、検証・利用する技術の総称です。 SPV についてはビットコインの発端である論文「Bitcoin: A Peer-to-Peer Electronic Cash System (Satoshi Nakamoto, 2009)」においても言及されていました。しかし、必要なデータだけを部分的にダウンロードする、という方法については具体的な実装手段が提案されていなかったこともあり、初期のビットコインにおいて SPV は実装されませんでした。後年、 2014年10月24日に公開された BIP0037 において SPV の具体的な実装手段としてブルームフィルタを採用することが提案され、ビットコインにおけるプロトコル(通信方式)の拡張がなされたことで SPV が実現しました。

ちなみに、BIP とは Bitcoin Improvement Proposals の略であり、ビットコインに関する技術を議論するために作成され、公開されている一連の文章です。公開先はGitHub というサービスです。英語で書かれており、また暗号技術や計算機科学等の専門用語が飛び交うため読解はかなり困難ですが、ビットコインの最新技術に関する動向を知りたい場合は BIP を定期的にチェックすると良いでしょう。

さて、ビットコインに対するブルームフィルタの応用例は、自分のビットコインアドレスをキーワードに指定してブロックチェーンという巨大なデータにブルームフィルタを適用することです。これによって自分のビットコインアドレスに関するデータだけを効率的に収集することができます。というのも、ビットコインにおいて実装されているブロックチェーンは1ブロックあたりおおむね 1 MB 程度の容量で構成されており、約10分に一個、ブロックが追加され続けています。2017年11月6日時点では 430,000 個以上のブロック高が存在します。つまり2017年11月6日現在、ブロックチェーン全体のデータ量は約 430 GBもあるのです(!)。なお、現実の利用に際しては十分な長さのブロックチェーンが確保されていれば問題ないため、例えば bitcoin.org が提供している Bitcoin Core というアプリケーションにおいては「完全なブロックチェーン・サイズ」として 65 GB 程度の容量を必要とするようです(それでも巨大なデータ量であることには変わりがありませんが)。

ブロックチェーンはビットコインの中核を担うデータですが、全てのブロックチェーンをスマートフォンに格納し、検証・利用することは現実的ではありません。そこで、スマートフォンのように通信容量が限られている端末でビットコイン取引を行う際は、完全なブロックチェーン・サイズを持ち、かつ信頼できるビットコイン利用者に依頼してブルームフィルタを適用し、必要なデータだけを効率的に収集し、取引内容を検証するということが行われています。

具体的なアプリケーション例

多くのビットコイン・ウォレットはブルームフィルタを実装した SPV を利用しており、高速かつ軽快に動作します。代表的なアプリケーションとしては Bitcoin Wallet や Copay が挙げられ、これらは SPV クライアントとも呼ばれます。

一方で、 SPV を利用したアプリケーションはブロックチェーンに対して一部のデータしか持っていないため、全体のブロックチェーンを持つアプリケーションが不可欠となります。代表的なアプリケーションとしては Bitcoin Core や bitcoind が挙げられ、これらは完全クライアントとも呼ばれます。

他方、完全クライアントと SPV クライアントを組み合わせたアプリケーションとして Electrum というアプリケーションも存在します。完全クライアントである bitcoind が稼働している複数のサーバーに対し、 SPV の仕組みを利用して接続します。このことから Electrum はサーバー・クライアント型とも呼ばれています。

ビットコインに関しては技術仕様が全て公開されているため、プログラミングの知識があれば自前でビットコイン用のアプリケーションを作成することも不可能ではありません。事実、 Bitcoin Core や bitcoind はビットコインの発案者である「Satoshi Nakamoto」が開発したアプリケーションのソースコードをもとに作成されています。


今回のコラムではビットコインの内部で用いられているブルームフィルタという仕組みについて、どのような役割を担っているのか説明しました。ブルームフィルタとは効率的なデータ収集を目的としたデータ構造です。 ビットコインにおいてはブロックチェーンの中から必要なデータだけを抽出し、検証・利用する技術、 SPV に用いられています。 SPV が実装されたことにより、スマートフォンのような通信量が限られている端末でも容易にビットコインを利用することができるようになりました。

一方、情報技術の向上は日進月歩です。ビットコインについては特に、最新の技術が多く使われており、今後も様々な技術が追加される可能性があります。 SPV についても、現在はブルームフィルタが利用されていますが、より効率の良いデータ構造が提案され、採用される可能性は十分にあります。ビットコインの情報を集める際、相場や取引方法だけではなく、技術情報についても日常的なチェックを行った方が良いでしょう。

関連記事

コメントは利用できません。

bitFlyer

最近の投稿

新着記事

  1. ビットコインの取引を行っている方の中では、ビットコインそのものは非常に堅牢な仕組みとなっていることは…
  2. ビットコインについて調べているとまず目にする国家の名前は中国、ギリシャ、キプロス、そして世界最大級の…
  3. ビットコイン投資に興味を持ったものの、ビットコインを始めとした仮想通貨がいったいどのようなものかわか…
  4. ビットコインをはじめとした仮想通貨は従来の通貨には無いユニークな特徴を多く持っています。世界各国の中…
  5. ブルームフィルタとは計算機科学におけるデータ構造の名前であり、ブルームフィルタは主に、スマートフォン…
  6. 行動経済学という比較的新しい学問が存在します。行動経済学は従来の経済学では説明できなかった現象を説明…
  7. 2017年5月末、日本国内でビットコイン取引所を運営しているビットポイントジャパンが大手コンビニチェ…
  8. ガイドラインとは様々な機関によって様々な位置づけで公表される、何らかの取り決めを記載した文書のことで…
  9. ビットコインの情報を調べていると、様々なお国事情を垣間見ることができます。情勢が不安定な国ほど自国の…
  10. 最近、ビットコインについて調べていると韓国の話題も目にするようになりました。韓国は元々、高速なインタ…
ページ上部へ戻る