Queueing analysis of transaction-confirmation time in Bitcoin

河瀬 良亮(1651036)


ビットコインは分散型取引台帳ブロックチェーンに基づいた仮想通貨である。マイナーと呼ばれるノードが難解なパズル的問題を競争して解くことで、 ブロックチェーンは維持・更新されている。利用者によって発行されたトランザクションは複数個まとめてブロックに格納され、 パズル的問題が解かれたときにそのブロックはブロックチェーンに接続される。 送金金額や手数料などに基づいた優先権がトランザクションに与えられており、 高優先権のトランザクションは低優先権のトランザクションよりも早く承認される傾向がある。 最近の研究によると、新たに到着したトランザクションはマイニング中のブロックには含まれないことが分かった。 本研究では、このマイニングプロセスを集団サービスを持つ待ち行列によりモデル化し、トランザクション承認時間の解析を行う。

最初のモデルとして、集団サービスを行うM/Gb/1待ち行列を考える。 このモデルでは、新規トランザクションの到着時点でサービス中の集団サイズが制限未満であってもそのトランザクションは待ち行列で待機する。 トランザクションの系内滞在時間はそのトランザクションの承認にかかる時間に相当する。 このモデルに対してサービス中のトランザクション数と待ち行列内トランザクション数の結合分布を考え、それを基に平均トランザクション承認時間を導出する。 この結果を用いて、優先権付きの集団サービスを持つM/Gb/1についての平均トランザクション承認時間の再帰的な式を導出する。 数値例において、ブロックサイズの上限がトランザクション承認時間に与える影響を示す。 低優先権になりやすいマイクロペイメントの増加がトランザクション承認時間に与える影響についても議論する。

関連研究によると、サービス時間であるブロック生成時間間隔は指数分布で近似できることが報告されている。 しかしながら、実際のビットコインではトランザクションの到着間隔は指数分布よりも変動が大きいことが知られている。 そこで二番目のモデルとして、トランザクションは独立同一な一般分布に従って到着し、マイニングの終了時点で複数のトランザクションが離脱するGI/Mb/1 モデルを考える。 トランザクション到着直前の待ち行列内トランザクション数をシステムの状態として定義し、行列解析法により定常分布および平均トランザクション滞在時間を導出する。 数値例において、実データに基づいてパラメータを決定した理論解析結果とシミュレーションを比較することでモデルの妥当性を検証する。