DEIM Forum 2023 2a-5-3

ブロックチェーンにおけるブルームフィルタを用いたブロック生成通知の最適化
長谷川

毅†

晶††

櫻井

首藤

一幸†

† 京都大学†† 東京工業大学
あらまし 本稿では，ブロックチェーンにおいてフォーク発生率を抑えるために，ブロックの生成通知を素早く全ノードに届ける手法を提案する。ブロックに含まれるトランザクション群の情報をブルームフィルタを用いて表現し，それを通知として伝播させることで，通知を受け取ったノードは次のブロックのマイニングに移ることが可能になる。
シミュレータを用いた実験において，50%ile の伝搬時間は既存手法の 41.1%，90%ile の伝搬時間は既存手法の 39.2%となり，平均伝搬時間から計算されるフォーク発生率は既存手法の 40.8%となった.
キーワード ブロックチェーン，ブロック伝搬，フォーク率
Node A

1 はじめにブロックチェーンは非集中性と改竄の困難性を持つ分散シス

Node B

block

テムであり，このことから暗号通貨の基盤として用いられていinv

る. 現在，Bitcoin [1] に代表される多くの暗号通貨は Proof ofWork を利用しているが，この合意アルゴリズムは一定時間に少量のトランザクションしか承認することしかできないという問題がある. 具体的には Bitcoin のトランザクション承認性能

time

getdata

は，当初，7 TPS（トランザクション / 秒）しかなかった.
トランザクション承認性能が不足している問題を解決する方法として，ブロックの生成間隔を短くする方法が考えられるが，block

この方法はブロックチェーンのセキュリティを犠牲にする [3].
これは安易にブロックの生成間隔を短くすると，生成されたブ
ロックがブロックチェーンネットワークの全ノードに行き渡る

図 1 Bitcoin におけるレガシープロトコルのノード間のやり取り

前に，そのブロックが届いていないノードが新たにブロックを生成してしまい，ブロックチェーンに分岐を生じさせてしまう
可能性が上昇するためである. このブロックチェーンに分岐が生じることをフォークと呼ぶ. そこでブロックの伝搬時間を短くすることで，フォーク発生率を抑えることができ，ブロックの生成間隔を短縮することが可能になる.
本研究では，ブロックが生成されたことを知らせるブロック
生成通知を伝搬させることで，フォークの発生率を低下させる手法を提案する. また全ノードが確率的にブロックを生成するためにフォークが発生し得るブロックチェーンを対象とする.
本論の構成は以下の通りである. まず，2 章ではブロックのノード間の伝搬においての関連研究について述べる. 3 章では本研究の提案手法について述べる. 4 章では評価実験の手法及び結果について示し，考察を述べる. 5 章で結論を述べる.

2 関連研究題なければ自身の隣接ノードにブロックを転送する. このノード間の転送プロトコルについて，まず通常のノード間のプロト
コル (レガシープロトコル) を説明し，Compact Block Relay(CBR) [4] と Graphene [5] を説明する. これらはノード間のブロックの転送時間を短くするためのプロトコルである.

2. 1 通常のブロック伝搬（レガシープロトコル）
レガシープロトコルでは，ノードはブロックに含まれている
トランザクション全体を伝搬させる. 転送可能なブロックサイズは 1 MiB ほどに制限されている [6].
図 1 にレガシープロトコルのノード間のやり取りを示す. ノー
ド A はブロックを受け取り検証したあと，inv メッセージを自身の隣接ノードであるノード B に送る. inv メッセージにはブロックのハッシュ値が含まれている. inv メッセージを受け取ったノード B は，ブロックのハッシュ値を使い，自身が該当のブロックを持っていなかった場合は getdata メッセージをノード

ブロックを生成したあるノードは，隣接ノードに生成したブ

A に送りブロックを要求する. getdata メッセージを受け取っ

ロックを送信する. 受信したノードはそのブロックを検証し，問たノード A は，トランザクション全体を含んだブロックをノーNode A

Node B

Node A

Node B

block

Node A
block

inv

block
inv

Node Binv

getdatagetdata

Bloom filter S, IBLT I

Bloom filter S, IBLT I

time

time

Bloom filter R

getdata

txn set C, IBLT J

compact block
図 3 Graphene のノード間のやり取り

time
getblocktxn

2. 3 Graphene
Graphene [5] は ブ ル ー ム フィル タ [8]，Invertible Bloom

block txn

Lookup Table (IBLT) [9] を用いたプロトコルである. ブルー
ムフィルタは，ある要素が集合に含まれているかどうかを判定できる確率的なデータ構造である. ただし，誤って，含まれて図 2 CBR のノード間のやり取り

いない要素を含まれていると判断してしまう偽陽性の可能性がある. IBLT はブルームフィルタと同じく確率的なデータ構造

ド B に送信する.

であり，IBLT としてエンコードした集合の情報を相手に送ることで，相手は自身の集合との差分を求めることができる. こ

2. 2 Compact Block Relay (CBR)の際 IBLT を受けとった側は自身の集合を IBLT として encode

Compact Block Relay (CBR) [4] はレガシープロトコルと違し，それを用いて受け取った IBLT を decode する必要がある

い，ブロックに含まれるトランザクション全体ではなく，ブロッが，この decode は失敗する可能性がある. この可能性は２つクヘッダとブロックに含まれるトランザクションの ID からコの集合の差分が大きいほど高くなる.

ンパクトブロックを作成し，それを伝搬させる. コンパクトブ

図 3 に Graphene でのノード間のやり取りを示す. まずブロックを受け取ったノードは，自身のトランザクションプール

ロックを受け取ったノード A はレガシープロトコルと同じよう(mempool) から該当のトランザクションを取り出しブロックをに inv メッセージを隣接ノード B に送る. ノード B は該当のブ再構成する.

ロックを持っていなかった場合，getdata メッセージをノード

図 2 に CBR でのノード間のやり取りを示す. ノード A はブ

A に送る. この際自身のトランザクションプールのトランザク

ロックを受け取り検証したあと，inv メッセージを自身の隣接ションの数も合わせて送る. ノード A は getdata メッセージをノードであるノード B に送る. ノード B は該当のブロックを受け取ると，ブロックに含まれるトランザクションの ID を要

持っていなかった場合 getdata メッセージでブロックを要求す

素としてブルームフィルタ S ，IBLT I を作成し，ノード B にる. CBR ではノード A は getdata メッセージを受け取ると，送る. この際ブロックに含まれるトランザクション数，ノード

ブロックヘッダとブロックに含まれるトランザクションの ID

B のトランザクションプールのトランザクション数を考慮してをコンパクトブロックとしてノード B に送る. コンパクトブ

ブルームフィルタと IBLT のサイズを決定する. ノード B は自ロックを受け取ったノード B は自身のトランザクションプール

身のトランザクションプールのトランザクションを受け取ったから該当のトランザクションを取り出しブロックを再構成する.

ブルームフィルタに通し，陽性集合 Z を得る. そして Z を要

この際，該当のトランザクションの中に自身のトランザクショ

素として IBLT I ′ を作成し，I と I ′ を用いてブロックに含まンプールに存在しないトランザクションが含まれていた場合，れるトランザクションと陽性集合 Z の差分を求める. 差分が求

ノード A に getblocktxn メッセージを送り，足りないトラン

められればノード B はブロックに含まれるトランザクションをザクションを要求する. getblocktxn メッセージには足りない把握できるため，自身のトランザクションプールからブロック

トランザクションの ID が含まれる. getblocktxn メッセージを再構成する. 足りない場合は CBR と同じように gettxn メッを受け取ったノード A は足りないトランザクションをノード B

セージで足りないトランザクションをノード A に要求する.

に送り，それによりノード B はブロックを再構成することが可能になる.

IBLT の decode が失敗し，差分が求められない場合が存在する. その場合はノード B は陽性集合 Z を要素として新たにブコンパクトブロックは 18 KiB ほどであり [7]，通常のブロッ

ルームフィルタ R を作成し，ノード A に送る. ノード A はブ

クが 1 MiB ほどであることに比べると小さい. 受信側のトラン

ルームフィルタ R をもとにノード B に足りないトランザクショ

ザクションプールのトランザクションが足りなければ追加のやンセット C を推定する. また R の陽性集合と C の和集合を要り取りが発生するが，レガシープロトコルよりも短い時間で全素として IBLT J を作成し，C と J をノード B に送る. ノー

ノードに行き渡る.

ド B はブルームフィルタ S の陽性集合 Z と，トランザクショ

表1

ブロック生成通知を Bitcoin に実装する場合は，ブロック生成

ブロック生成通知 (ブロックヘッダ) の構造

要素

説明

通知をマイナーが作るトランザクションに含めブロックチェー

Transaction ﬁlter

ブロック内のトランザクションでンネットワーク上に伝搬させる手法が考えられる.

使われた UTXO を要素とした

3. 1 トランザクションフィルタ

ブルームフィルタ
前提ブロック情報前提とした，有効化するブロックの情報

Version

ソフトウェア / プロトコルバージョン番号

トランザクションフィルタ Fh は，生成されたブロック Bh 内のトランザクションで消費された UTXO を要素としたブルー

Previous Block Hash 親ブロックのハッシュ値
Merkle Root

ブロックの全トランザクションに対するムフィルタである. ブロック生成通知 Nh を受信したノードは，

マークルツリーのルートハッシュ

自身のトランザクションプール内のトランザクションがそれぞTimestamp

ブロックの生成時刻

れ消費している UTXO をトランザクションフィルタ Fh を用

Diﬃculty Target

ブロック生成時の diﬃculty

いて判定し，各トランザクションについて，消費する UTXO

Nonce

Proof of Work で用いるカウンタ

がすべて陰性だった場合，生成されたブロック Bh には含まれていないと判断し，次のマイニングに含める.

′

ンセット C の和集合を要素として IBLT J を作成し，J と J′を用いて差分を求め Z を修正する. この際ブロックに含まれるトランザクションをすべてノード B が持っていればブロックを再構成する. 持っていなければ CBR と同じようにノード A に要求する. また J と J ′ を用いた decode が失敗した場合は，それをノード A に知らせ，レガシープロトコルと同じように通常のブロックを伝搬させる.

Graphene においてノード間で転送されるデータのサイズはすべて合わせても CBR よりも少なくなる. ただし decode が失敗したりした場合追加のやり取りが多くなる.

3 提案手法ブロックチェーンにおいてのフォーク発生率を抑えるための本研究の提案手法について述べる.
本研究では，ブロックが生成されたことを素早くネットワー
ク上のノードに通知する手法を提案する. 以降この通知のこと

ブルームフィルタには偽陽性の可能性が存在するため，それの対処については 3. 2 節で述べる.

3. 2 ブロックの有効化
提案手法においてのブロックの有効化についての説明をする.
ブルームフィルタには偽陽性の問題がある. そのことからあるトランザクションフィルタによって偽陽性になったトランザ
クションはマイニングに含められなくなってしまう. ここで，ある高さ h のトランザクションフィルタ Fh で偽陽性となっているトランザクションは，対応するブロック Bh により，偽陽性であると判断できる. 言い換えると，トランザクションフィ
ルタ Fh は，ブロック Bh により無効化できる. ブロック Bh の存在を保証し，対応するトランザクションフィルタ Fh を無効化することをブロック Bh の有効化と呼ぶ. マイニングの際に各ノードが持っているブロックを有効化することで，それに対応するトランザクションフィルタを無効化し偽陽性の問題を解決できる.

をブロック生成通知と呼ぶ. ブロック生成通知には生成された

ただしブロックの伝播状況は各ノードで一意ではない. それブロックの情報を含め，通知を受け取ったノードはその通知をに対し，各ノードはあるブロック Bh を検証する際に，ブロッ

もとにして次のマイニングを開始する. ブロック生成通知が素ク Bh の生成時に有効化されていたブロックを把握することが早く伝搬し，それを受け取ったノードが通知に対応するブロッ必要である. ゆえに提案する手法として，各ノードがマイニン

クを親とした次のマイニングに入ることで，フォーク発生率をグの際所持しており，対応するトランザクションフィルタを無抑えることができる. ゆえに，空間効率の良いデータ構造であ効化したブロックの情報をブロック生成通知に含ませる. これるブルームフィルタを用いて生成されたブロックの情報を表現を前提ブロック情報という. 高さ h のブロック生成通知 Nh のし、ブロック生成通知に含める.

前提ブロック情報によりブロックを有効化することで、高さ h

表 1 にブロック生成通知の構造を示す. 本研究では，ブロッ
クのブロックヘッダを拡張し，ブロック生成通知とする. 構造との時点での有効なブロックの情報を全ノードで一意に保つことができる.

しては，トランザクションフィルタ，前提ブロック情報以外はまた悪意のあるノードにより，高さ h のマイニングに成功しBitcoin のヘッダと同様である. マイナーは拡張したヘッダをた際，ブロック生成通知 Nh のみを伝搬させ，ブロック Bh を用いてマイニングを行い，ブロックの生成に成功するとヘッダ伝搬させない攻撃が考えられる. この攻撃によりブロック Bh

をブロック生成通知として伝搬させる. このようにすることで，が伝搬させられないためそれに対応するトランザクションフィ

ブロック生成通知を受け取ったノードは，生成されたブロック

ルタ Fh を無効化することができず，Fh により陽性となっていのメタデータの確認，またブロック生成通知の作成者が確かにるトランザクションがマイニングに含められなくなる. この攻Proof of Work のマイニングに成功したことを確認することが撃に対処するためにブロックの有効化に期限を設ける. 具体的できる. トランザクションフィルタについては 3. 1 節で，前提には連続して b ブロックの間ブロック Bh が有効化されなかっブロック情報については 3. 2 節で詳しく述べる.

た場合，つまり高さ h + 1 から h + b のブロック生成通知の前

図 4 は提案手法の概要を示したものである.

提ブロック情報にブロック Bh が含まれなかった場合，トラン

Block Height

Block Generation
Notification (BGN)

Block

h-b

h-1

h

h+1

h+n

Headerelements

Headerelements

Headerelements

Headerelements

Headerelements

Transaction
filterTransaction
filterTransaction
filterTransaction
filterTransaction
filterPrerequisite
block
indices

Prerequisite
block
indices

Prerequisite
block
indices

Prerequisite
block
indices

Prerequisite
block
indices

Header(BGN)

Header(BGN)

Header(BGN)

Header(BGN)

Header
(BGN)

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..

Tx
Tx
..
.

.

validate

activate

Headerelements
Bitcoin’s
header elements.

Tx
inactivetransactionTxactivetransaction

図4

提案手法の概要

ザクションフィルタ Fh を無効化し，これ以降 Bh を有効化できないようにする. ブロック Bh は有効化ができなくなるため，.

Tx
unconfirmed
transaction

Transaction
filterinactive
filter.
Transaction
filteractivefilter

3. 4 ブロックの検証
アルゴリズム 2 は高さ h のブロック Bh の検証アルゴリズム

トランザクションフィルタ Fh で陽性となっていたトランザクである. あるノードが高さ h + 1 以上のブロック生成通知を受ションをすべてマイニングに含める. b はシステムワイドなパ

信し，その通知によってブロック Bh が有効化されるとき，Bh

ラメータで，これの決め方については 3. 6 節で述べる.

の検証が行われる.

3. 3 ブロック生成通知の検証
アルゴリズム 1 は高さ h のブロック生成通知 Nh を受信した

アルゴリズム 2 ブロック Bh の検証
1: ブロック生成通知 Nh の検証

ノードが行う，ブロック生成通知の検証アルゴリズムである.

2: ブロック Bh 内のトランザクションが統合フィルタ Th を通過する

アルゴリズム 1 ブロック生成通知 Nh の検証

3: ブロック Bh 内のトランザクションの検証

かの検証
1: 一つ前のブロック生成通知 Nh−1 の検証
2: Nh が有効化するブロックの検証
3: ブロック生成通知 Nh−1 自体の検証 (Merkle root の検証はしない，それ以外は Bitcoin のヘッダの検証と同じ)

アルゴリズム 3 統合フィルタ Th の生成
1: 統合フィルタ Th = ブルームフィルタの初期値
2: r = h

ブロック生成通知 Nh の検証において，まずひとつ前のブロッ
ク生成通知 Nh−1 が検証されていることを確認する. これにより再帰的に以前のブロック生成通知がすべて検証されているこ

3: while r >= 0 do4:

if Fr が有効 thenTh = U nite(Th , Fr ) ▷ U nite は各ビットの論理和を取る

5:関数とが必要となる. そして次に Nh 内の前提ブロック情報を確認

6:

end if

し，有効化されるブロックをそれぞれ検証する. ブロックの検

7:

r−−

証については 3. 4 節で述べる. 仮に Nh の受信側が有効化され

8: end while

るブロックを持っていなかった場合は，Nh の送信側に該当の9: return Th

ブロックを要求する. 最後にブロック生成通知 Nh 自体の検証を行う. この際 Merkle root の検証は行わない. それ以外の検ブロック Bh の検証において，まず対応するブロック生成通証などは Bitcoin のヘッダの検証と同様である. またブロック

知 Nh の検証を行う（アルゴリズム 1）. そして次にブロック内

Bh の検証は行わない.

のトランザクションが統合フィルタ Th を通過するかの検証を行う. 統合フィルタ Th は，高さ h の時点の無効化されていなアルゴリズム 4 マイニング

イズについて述べる. ブロック生成通知の伝搬時間を最小化す

1: ブロック生成通知 Nh の検証るために，トランザクションフィルタはできるだけ小さいサイ

2: 手元にある b ブロック前までのまだ有効化されていないブロック

ズにする.

に対応するトランザクションフィルタを無効化
3: 手元にある b ブロック前までのまだ有効化されていないブロック

を，前提ブロック情報に含める
4: Nh に対する統合フィルタ Th を生成
5: トランザクションプールに含まれるトランザクションを Th でフィ

ルタリング

トランザクションフィルタ Fh は対応するブロック Bh が b
ブロックの間有効化されなかった場合に無効化される (3. 2 節).
このことから有効なトランザクションフィルタは，b ブロック
連続でブロック生成通知によるブロックの有効化がされなかった場合に最も多くなり，その数は b 個である. 本研究では，b 個

6: ブロックに入れるトランザクションを決めるのトランザクションフィルタによって偽陽性となるトランザク

7: トランザクションフィルタ Fh+1 を作成

ションと，本来マイニングに使えるはずのトランザクション全

8: トランザクションフィルタと前提ブロック情報をブロックヘッダに体の比が，パラメータ r 以下になるようにブルームフィルタの含めてマイニングを開始する
9: マイニング成功
10: 生成したブロック Bh+1 のブロックヘッダをブロック生成通知

Nh+1 として伝搬させる
11: ブロック Bh+1 を伝搬させる

偽陽性率を設定する. 偽陽性率が決まれば，その際の最も小さいブルームフィルタのサイズは，フィルタの要素数を n, 偽陽f
性率を f とすると − nlnln
2 2 ビットとなる.

一つのトランザクションが消費する UTXO の数の平均は 3 である [10]. 本研究では，この数字を採用する. 消費する UTXO

いトランザクションフィルタを統合したもので，統合フィルタの生成アルゴリズムはアルゴリズム 3 で示す. そして最後にブロック Bh に含まれるトランザクションが正しいものであるかの検証を行う. また，一つ前のブロックであるブロック Bh−1の検証は行わない. これは本研究ではブロックはブロック生成
通知によって有効化されるものであり，ブロック Bh が生成されたときに前提となったブロックは，ブロック生成通知 Nh で示され，最初に行う Nh の検証の中で検証されるためである（アルゴリズム 1）.

3. 5 マイニング
アルゴリズム 4 はブロック生成通知 Nh を受けとったノードが次のマイニングに入る際のアルゴリズムである.
ブロック生成通知 Nh を受け取ったノードが次のマイニングに入る際，まず受け取った Nh を検証する（アルゴリズム 1）.

のうち，少なくとも 1 つの UTXO が陽性のとき，そのトランザクションは次のマイニングに含めない. よってブルームフィ
ルタの偽陽性率を f とすると，本来使えるトランザクションが偽陽性トランザクションとなる確率 f ′ は,

f ′ = 1 − (1 − f )3となる. b 個のブルームフィルタによる偽陽性トランザクショ
ンと，本来マイニングに使えるはずのトランザクション全体に占める比が r 以下であるために，f ′ が満たすべき条件は，b∑f ′ (1 − f ′ )k−1 <=r

k=1である. これにより f が満たすべき条件は
1f<= 1 − (1 − r) 3b

そして次に，手元にあるブロック b ブロック前までのブロックとなる. 偽陽性率 f とブルームフィルタのサイズはトレードオのうち，まだ有効化されていないブロック Bi があった場合，対フであり，ブルームフィルタのサイズはできるだけ小さくする

応するトランザクションフィルタ Fi を無効化し，前提ブロッ

ために，ブルームフィルタの偽陽性率 f はできるだけ高くする.

ク情報を更新する（有効化するブロックは複数でも良い）. そ

よっての後，Nh に対する統合フィルタ Th を生成する（アルゴリズム

1

f = 1 − (1 − r) 3b(1)

3）. その後生成した統合フィルタ Th を使い，自身のトランザ
クションプールのトランザクションをフィルタリングする. ことする.

のときそれぞれのトランザクションが消費する UTXO を統合

パラメータ b の決め方について考察する. 式 (1) より，r を固フィルタ Th で判定し，少なくとも１つ陽性となったトランザ

定すると，b が大きくなるにつれて f は小さくなる. 偽陽性率

クションはマイニングから除く. そして残ったトランザクショ

f が小さくなるにつれてフィルターサイズは大きくなるため，bンからブロックに入れるトランザクションを決め，新しいトラが大きくなるにつれてフィルターサイズは大きくなる. よって

ンザクションフィルタ Fh+1 を作成する. そして拡張したブロッフィルターサイズをできるだけ小さくするために，許容できるクヘッダにトランザクションフィルタと前提ブロック情報を含最小の b を求める. 提案手法においては，ブロックは後に生成めてマイニングを開始する. マイニングに成功すると，生成しされたブロック生成通知によって有効化される. このことからたブロック Bh+1 のブロックヘッダをブロック生成通知 Nh+1

b を小さくしすぎると，悪意のあるノードが b 回連続でブロッとして伝搬させ，その後ブロック Bh+1 を伝搬させる.

クを生成し，ブロックを有効化しないことにより，悪意のない

b + 1 個前のブロックが無効化されてしまう可能性が高まってし3. 6 トランザクションフィルタのサイズ
ブロック生成通知に含まれるトランザクションフィルタのサ

まう. 本研究では b は，悪意のあるノードが b 回連続でブロック生成に成功する確率が double spending 攻撃の成功確率より

表3

Bloom filter size [KiB]

12000
10000
8000

ネットワークパラメータ

ノード数

10000

ブロック生成間隔

10 分

ブロックサイズ

1.0 MiB

ハッシュレートの分布 正規分布
6000

ハッシュレートの平均 400000 /sec
ハッシュレートの分散 100000 /sec

4000
2000

クを有効化しないことにより，b + 1 個前の悪意のないブロック
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

が無効化されてしまうというものである. この攻撃はパラメー
タ b が大きくなるにつれて成功確率が低くなるため，本研究でrは，この攻撃の成功確率が double-spending 攻撃の成功確率よ
図 5 r を変化させた際のブルームフィルタのサイズ (n=2000, b=4)
表2

トランザクションフィルタのサイズ (n=2000, b=4)

r=0.1 r=0.5
ﬁlter size [ KiB ]

7.181

4.391

りも低くなるようにパラメータ b の値を設定した.

3. 7. 3 特定のトランザクションを陽性に保つ攻撃
ブロックを生成した際，特定のトランザクションが陽性となるようなトランザクションフィルタを作成することで，特定のトランザクションを使わせないようにすることが可能である.

も低くなるように設定する. 悪意のあるノード，またはノード群が全体のハッシュパワーに占める割合を h とすると，それらのノードが b 回連続でブロックの生成に成功する確率は hb である. これがハッシュレートに応じた double spending 攻撃の成功確率よりも小さくなるように b を設定する. Chaudharyら [11] によるハッシュレートに応じた double spending 攻撃の発生確率を参考にすると，b = 4 で十分である.
パラメータ r について考察する. r を変化させ，b = 4，ブロックに含まれるトランザクションの数を 2000 とすると，ト
ランザクションフィルタのサイズは図 5 のようになる. トラン
ザクションの数は [6] を参考にした. 図 5 より，r を小さくすればするほど，トランザクションフィルタのサイズは大きくなる
ことがわかる. 表 2 は r = 0.1, 0.5 のときのトランザクション
フィルタのサイズを示したものである.

3. 7 攻撃の影響および対策提案手法への考えられる攻撃とその影響，また，提案手法による対策について述べる.

3. 7. 1 ブロックを伝搬させない攻撃
3. 2 節，3. 6 節で述べたように，ブロックを生成した際，ブロック生成通知のみを伝搬させブロックを伝搬させない攻撃が考えられる. これに対処するために b ブロックの間有効化されこれにより，b ブロック積み重なるまでに再びマイニングに成功することで，特定のトランザクションを陽性に保ち，ブロッ
クに含められなくする攻撃が考えられる. この攻撃は b が大き
くなるにつれて成功確率が上昇するため，上のブロックを伝搬させない攻撃とトレードオフの関係となる.

3. 7. 4 不正なトランザクションフィルタを伝搬させる攻撃
すべての UTXO が陽性になるような不正なトランザクショ
ンフィルタを伝搬させることで，すべてのトランザクションが使えなくなってしまう. この攻撃へ対処する場合は，仮にブルームフィルタの初期値を 0，陽性ビットを 1 とした場合，1となっているビットの数の割合に制限をかける手法が考えられる. 偶然により悪意のないノードでも制限を超える 1 の数になる可能性もあるため，この場合はブルームフィルタの再構成を許し，再構成回数を示す情報を通知に含める.

4 実験と考察
提案手法がフォークの発生確率を抑えることができることを示すための実験を行う. フォークの発生確率は，ブロックの伝搬時間と密接に関係している. よってシミュレータを使い提案
手法や関連研究の伝搬時間を測定する.

4. 1 実 験 手 法

なかったブロックは対応するトランザクションフィルタを無効

実験にはブロックチェーンネットワークシミュレータである化する（3. 2 節）. ただし b ブロック積み上がるまで該当のトラ

SimBlock [12] [13] を用いる. SimBlock には既にレガシープロ

ンザクションフィルタは無効化されないため，一定の間そのト

トコル，CBR の実装がされている. よって追加で Graphene，

ランザクションフィルタによって陽性となったトランザクショ

提案手法の実装を行い，ブロックの伝搬時間を測定した. 提案

ンがマイニングに含められないという問題がある. 本研究では手法については，ブロック生成通知とブロックの伝搬時間を最悪の場合の偽陽性トランザクションの数が一定の割合以下に別々に測定したが，他の手法との比較はブロック生成通知の伝なるようにトランザクションフィルタのサイズを設定する手法

搬時間を用いる. これは提案手法では，ブロック生成通知を受を提案している.

信した時点で現在のブロックのマイニングをやめ，次のブロッ

3. 7. 2 ブロックを有効化しない攻撃

クのマイニングに移るためである. 実験は手法ごとのフォーク

この攻撃は，3. 6 節で述べたように，悪意のあるノードが b 回

発生率を明らかにするために行うため，提案手法においてはブ

連続でブロックを生成し，それらのブロック生成通知でブロッ

ロック生成通知の伝搬時間だけを考慮すれば十分である. 表 3

表6

表 4 CBR のパラメータ

提案手法のパラメータコンパクトブロックサイズ

18 KiB

ブロック生成通知サイズ 7.272 KiB (r=0.1) or 4.468 KiB (r=0.5)

チャーンノードの割合

0.97

ブロックのサイズ

1.0 MiB

チャーンノードのブロック再構成失敗率0.27

ブロックの伝搬手法

CBR

有効化ブロックの深さ

1, 2 or 3

コントロールノードのブロック再構成失敗率 0.13
表 5 Graphene のパラメータ

1 ブロックあたりのトランザクション数

表 7 r によるブロック生成通知の伝搬時間

r=0.1

2000

r=0.5

ノードのトランザクションプールのトランザクション数 4000

50%ile 伝搬時間

274 ms 242ms

ブロック再構成の際の不足しているトランザクション数 312

90%ile 伝搬時間

453 ms 418ms

Bloom ﬁlter S のサイズ

2.434 KiB

100%ile 伝搬時間 634 ms 601ms

IBLT I のサイズ

0.901 KiB

平均伝搬時間Bloom ﬁlter R のサイズ

1.453 KiBIBLT J のサイズ

1.407 KiB

1 回目の decode 成功確率（シナリオ 1）

100%

1 回目の decode 成功確率（シナリオ 2）0%

decode の成功確率はブロック再構成の際の不足トランザク

100%

ションの割合に基づき決定した. [5] によると 1 回目の decode，

2 回目の decode 成功確率

302 ms 269ms

大きくなる.

つまり IBLT I の decode においては，受信ノードのトランザにシミュレーションで使用するブロックチェーンネットワークのパラメータを示す. 表 3 のパラメータ以外のネットワークのパラメータとして，ノード分布，帯域幅，ネットワーク遅延があり，これらは永山ら [7] の値を用いた.

4. 1. 1 SimBlock における CBR の実装
CBR は SimBlock に実装されているものをそのまま利用する. 表 4 に CBR のパラメータを示す. パラメータは [7] を参照した. コントロールノードとはブロックチェーンネットワー

クションプールに不足しているトランザクション数が，ブロックに含まれるトランザクション数の 2%未満ならば（シナリオ1），decode はほとんどの場合成功する. 不足トランザクショ
ン数は [14] をもとにチャーンノード，コントロールノードそれぞれの分布を用い，単純化のために不足トランザクション数の割合が 2%未満の場合，IBLT I の decode は 100%成功するものとした. また [5] によるとその不足トランザクションの割合が2%以上の際（シナリオ 2），decode はほとんどの場合失敗す

クに常に参加しているノードで，チャーンノードとはブロックるとあるので，単純化のためにその場合の decode 成功確率は

チェーンネットワークへの参加・離脱を繰り返すノードであ0%とした. 2 回目の decode，つまり IBLT J の decode の成功

る. チャーンノードとコントロールノードで CBR におけるブロックの再構成失敗率が異なり，ブロック再構成失敗の際に不足しているトランザクション数の分布もコントロールノードとチャーンノードで異なる [14]. 永山ら [7] はそれぞれの分布をもとに，不足しているトランザクションを送信する際のコストを計算している. 本実験ではそのパラメータをそのまま使用する.

4. 1. 2 Graphene のモデル化
表 5 に今回実装した SimBlock における Graphene のパラ
メータを示す. 1 ブロックあたりのトランザクション数，ノードのトランザクションプールのトランザクション数は [6] を参照した. ブロック再構成の際にトランザクションが不足している際の不足するトランザクション数の平均は，Imtiaz ら [14]によるとチャーンノードの場合は 312 であり，チャーンノー
ドの際の Bloom ﬁlter, IBLT のサイズを計算する際にはこの数値を用いることにした. これらのパラメータから Grapheneの Bloom ﬁlter，IBLT のサイズを計算した. Bloom ﬁlter S,

IBLT I は getdata メッセージを受け取った送信ノードが送る
Bloom ﬁlter, IBLT であり，Bloom ﬁlter R, IBLT J は一回目の IBLT の decode が失敗した際の recover するためのものである. その際不足していると思われるトランザクションセット

C も伝搬させるが，単純化のために CBR の不足トランザク
ションのサイズをそのまま流用した. 実際には Bloom ﬁlter Rの偽陽性の問題で CBR の不足トランザクションサイズよりも確率は，同じく [5] によるとほぼ 100%であるため，必ず成功するものとした.

4. 1. 3 提案手法の実装
SimBlock に本研究の提案手法を実装した. 提案手法のパラメータを表 6 に示す. ブロック生成通知のサイズは 3. 6 節で述
べたブルームフィルタのサイズに加えて，Bitcoin のブロック
ヘッダのサイズ 80B を加えたものである. 前提ブロック情報は非常に小さいので無視した. 偽陽性トランザクションと，本来マイニングに使えるはずのトランザクション全体の比 r = 0.1, 0.5のそれぞれの際の伝搬時間の比較を行う. ブロック生成通知が有効化するブロックの深さは全ノードが一定であるとし，深さ1 から 3 で伝搬時間の比較を行う. ブロックの伝搬は CBR を用いる.

4. 2 実験結果と考察
提案手法のパラメータによる伝搬時間の比較と，レガシープ
ロトコル，CBR，Graphene と提案手法の平均伝搬時間の比較
実験の結果と考察を述べる. シミュレーションの終了ブロック
高は 100000 ブロックとする.

4. 2. 1 提案手法のパラメータによる実験結果比較
表 7 は r = 0.1, 0.5 の際のそれぞれの伝搬時間の比較である.
有効化ブロックの深さは 1 としている. r = 0.1 のときのブロッ
ク生成通知サイズは 7.433 KiB, r = 0.5 のときのブロック生成
通知サイズは 4.576 KiB であるため，r = 0.1 よりも r = 0.5

25%
20%
15%
10%
5%
0%

0

300

600

900

1200

>150
0

average propagation delay [ms]proposed algorithm
図6

有効化ブロックの深さごとのブロック生成通知の伝搬時間
深さ 1

深さ 2

50%ile 伝搬時間

274 ms

267 ms 267 ms

90%ile 伝搬時間

453 ms

443 ms 443 ms

100%ile 伝搬時間

634 ms564 ms 570 ms

平均伝搬時間302 ms

293 ms 293 ms

ブロックの要求回数3802710 133445

CBR

平均伝搬時間深さ 3118951のほうが伝搬時間が小さくなった.
表 8 は有効化ブロックの深さを変化させた際のそれぞれの伝搬時間と，ブロックの要求回数の比較である. r = 0.1 としている. 表 8 より，有効化ブロックの深さが 1 のときと深さが 2,3のときでブロックの要求回数に大きな差があるのに対し，有効化ブロックの深さが 2 の場合と 3 の場合の差はあまり大きくな

6,200

average propagation delay [ms]表8Graphene

6,000
800
600
400
200
0

proposed Graphene
protocolい. これは 2 ブロック前のブロックは殆どの場合行き渡ってい図7るためであると考えられる. 深さ 1 と深さ 2 の場合のブロック

legacy各パーセンタイルの伝搬時間
表9

生成通知の平均伝搬時間の差は 9ms であり，深さ 2 と深さ 3 の

CBR

伝搬時間

提案手法 Graphene

CBR

レガシー

場合に関しては平均伝搬時間は等しかった. 有効化ブロック深50%ile 伝搬時間

274 ms

666 ms

746 ms6182 ms

さが深いほど，該当のブロックが行き渡っているため，ブロッ

90%ile 伝搬時間

453 ms1154 ms

1241 ms

8633 ms

クの要求回数は少なくなった. それに伴い平均伝搬時間も短く

100%ile 伝搬時間

634 ms2282 ms

2367 ms 15326 msなった. 有効化ブロックの深さは実際には各ノードのブロック

平均伝搬時間302 ms741 ms

828 ms6478 msの伝播状況によって変化するが，表 8 より，有効化ブロックの深さがいずれであっても伝搬時間の影響は小さかった.

90%, 100%ile，平均のすべての項目で最も小さい平均伝搬時

4. 2. 2 手法間の平均伝搬時間の比較間であった. ついで Graphene, CBR となり，レガシープロト

図 6 に，各手法について，平均伝搬時間のブロック毎頻度をコルが最も大きい平均伝搬時間となった. 提案手法の伝搬時示す. 提案手法のパラメータは r = 0.1，有効化ブロックの深さ

間は Graphene と比べて，50%ile は 41.1%，90%ile は 39.2%，

は 1 であり，提案手法はブロック生成通知の平均伝搬時間であ

100%ile は 27.8%，平均は 40.8%となった.

る. 提案手法のほぼすべてのブロック生成通知での平均伝搬時
間が，CBR, Graphene のブロックの平均伝搬時間よりも小さい. また CBR よりも Graphene のほうがブロックの平均伝搬時間は小さい傾向があった.

4. 3 ネットワークの通信量
ネットワークの通信量について考察する. 図 8 は各手法についての，1 ホップあたりのノード間のブロック伝搬における，

図 7，表 9 に，各手法での伝搬時間を示す. 提案手法のパメッセージの合計サイズの期待値を示したものである. 提案

ラメータは r = 0.1，有効化ブロックの深さは 1 であり，提案

手法はブロックの伝搬には CBR を用いるものとし，CBR は

手法はブロック生成通知の伝搬時間である. 提案手法が 50%,

4. 1. 1 節で，Graphene は 4. 1. 2 節で述べたパラメータ，モデル

F

0.012

1,000

0.01
60

fork rate

expected value ofsum of messages [KiB]

1,030

30
0

proposed
protocol(blocknotification)

proposed
protocolGraphene

CBR

legacy

0.008
0.006
0.004
0.002
0

proposed Graphene
alogorithm

図 8 1 ホップあたりの 2 ノード間のメッセージサイズの期待値
表 10

フォークの発生確率

提案手法

Graphene

CBR

レガシー

TW

302ms

741ms

828ms

6478msF

0.000503

0.001230.001380.0107

図9

5 結を元に計算した. 提案手法については，ブロック生成通知のみのブロックメッセージと，ブロックとブロック生成通知の合計
ブロックメッセージの２つを別々に示している. これはフォー
クの発生確率という観点ではブロック生成通知のメッセージサ
イズが重要であるためである. 1 ホップあたりのノード間のメッ
セージの合計サイズの期待値は，提案手法のブロック生成通知のみが最も小さく 7.3 KiB であり，ついで Graphene が 13

KiB，CBR が 43 KiB であった. レガシープロトコルは 1 MiBであり，最も大きくなった. これは表 9 から読み取れる伝搬時間を小さい順に並べたものと等しい. また Graphene は 2. 3 節
で述べたようにノード間のやり取りの数が多くなる傾向がある
ため，伝搬時間が大きくなっている. これは Graphene と CBR

CBR

legacyフォークの発生確率論

本研究では，ブロックの生成通知を全ノードに素早く通知することでフォークの発生確率を抑える手法を提案した. シミュ
レータを用いた実験において，50%ile の伝搬時間は既存手法の41.1%，90%ile の伝搬時間は既存手法の 39.2%となり，フォー
ク発生率の理論値は既存手法の 40.8%となった. ブロック生成
間隔を短縮するとフォーク発生率が上昇してしまうが [3]，提案
手法によるフォーク発生率の抑制で相殺することで，フォーク発生率を保ったままブロック生成間隔を短縮することもできる.
そうした手法も取り組んでいる [16].

謝辞にはメッセージサイズの期待値に大きな差があるのに対し，伝本研究は，京都大学大学院情報学研究科社会情報学専攻 伊

搬時間は大きな差がないことから読み取れる. このことからも

藤孝行教授にご支援をいただきました. ここに感謝の意を表し

提案手法が伝搬時間の観点で優れている理由は，メッセージサ

ます.

イズの期待値が小さいことに加え，ノード間のやり取りが少な
いためであると考えられる.

4. 4 フォークの発生率
櫻井ら [15] によると，フォーク発生率は次の式で求めること
ができる.

F =

TW
T

ここで，F はフォークの発生確率，TW はノードのハッシュレー
トで重み付けされたブロックの平均伝搬時間. T はブロックの生成間隔である. 表 10 は各手法のハッシュレートで重み付けされたブロックの平均伝搬時間，そしてそこから計算されるフォークの発生確率を示したものであり，図 9 は同様のフォー
クの発生確率をグラフにしたものである. 提案手法の伝搬時間
はブロック生成通知を用いている. 提案手法のフォーク発生率
は Graphene の 40.8%となり、最も低くなった.

文

献[1] Satoshi Nakamoto, “Bitcoin: A peer-to-peer electronic cash
system,” Decentralized Business Review (2008) : 21260.
[2] https://en.Bitcoin.it/wiki/Scalability, Accessed: Dec. 10.
2022.
[3] Yonatan Sompolinsky and Aviv Zohar, Secure high-ratetransaction processing in Bitcoin, in International Conference on Financial Cryptography and Data Security (FC2015), Springer, 2015, pp. 507–527.
[4] Matt Corallo, 2016, “BIP 152: Compact block relay,”https://github.com/Bitcoin/bips/blob/master/bip-0152.mediawiki.
[5] A. Pinar Ozisik, et al., ”Graphene: eﬃcient interactive setreconciliation applied to blockchain propagation,” Proceedings of the ACM Special Interest Group on Data Communication, 2019, 303-317.
[6] https://www.blockchain.com/explorer/charts, Accessed: Dec.
10. 2022.
[7] Ryunosuke Nagayama, Ryohei Banno, and Kazuyuki
Shudo, “Identifying impacts of protocol and internet development on the Bitcoin network,” 2020 IEEE Symposiumon Computers and Communications (ISCC), IEEE, 2020.
[8] Burton H. Bloom, 1970, “Space/Time Trade-oﬀs in Hash

[9]

[10]
[11]
[12]

[13]

[14]

[15]

[16]

Coding with Allowable Errors,” Commun, ACM 13, 7 (July
1970) , 422-426.
Michael T. Goodrich and Michael Mitzenmacher, (Sept2011), “Invertible bloom lookup tables,” In Conf, on Comm,
Control, and Computing, 792-799
https://Bitcoinvisuals.com/chain-input-count-tx, Accessed:
Dec. 10. 2022.
Chaudhary Kaylash, Vishal Chand, and Ansgar Fehnker,“Double-Spending Analysis of Bitcoin,” PACIS, 2020.
Yusuke Aoki, Kai Otsuki, Takeshi Kaneko, Ryohei Banno,
and Kazuyuki Shudo, SimBlock: A Blockchain Network
Simulator, in Proc, Workshop on Cryptocurrencies andBlockchains for Distributed Systems (CryBlock 2019, In
conjunction with IEEE INFOCOM 2019), April 2019.
Ryohei Banno, and Kazuyuki Shudo, Simulating a
Blockchain Network with SimBlock, in Proc. IEEE International Conference on Blockchain and Cryptocurrency(ICBC 2019), May 2019, pp. 3-4
Imtiaz, Muhammad Anas, et al. “Churn in the Bitcoin
network: Characterization and impact,” 2019 IEEE International Conference on Blockchain and Cryptocurrency(ICBC), IEEE, 2019.
Akira Sakurai, Kazuyuki Shudo, “Impact of the Hash Rateon the Theoretical Fork Rate of Blockchain,” Proc, IEEEICCE 2023, 2023
Masumi Arakawa, and Kazuyuki Shudo, “Block Interval Adjustment Based on Block Propagation Time ina Blockchain,” 2022 IEEE International Conference on
Blockchain (Blockchain), IEEE, 2022.