第15回 地域間インタークラウドワークショップ
2019年 9月 4日(水)0 / 15

ブロックチェーン「ネットワーク」の研究

首藤 一幸
東京工業大学Tokyo Tech

1 / 15ブロックチェーン• 暗号通貨を支えている技術– Bitcoin の時価総額 20兆円

ノード群のpeer-to-peer(P2P) ネットワーク• 非集中 分散 / decentralized• 期待されている応用= アプリケーションレベル
ネットワーク– いわば時刻認証局, 公証役場
ノード

ブロックのハッシュチェーン
ブロック

ハッシュ値

トランザクション (TX) とブロックは全ノードにブロードキャストされる全ノードが同一の台帳を保持する。
ノード群はブロック生成競争をする→ Proof of Work におけるマイニング

TX

TX

暗号学的ハッシュ関数

TX

TX

TX

TX

•
•

– 流通履歴追跡、投票等の政治プ
ロセス、組織の自動運営、…

ブロックハッシュ値•(マイナー = 採掘者)

Bitcoin ネットワーク 約 9,200ノード
出典：https://bitnodes.earn.com/

2 / 15

ブロックチェーンを支える技術
ブロックチェーンが達成したこと– 不整合 (二重消費) 防止・改ざん困難– 耐故障性– 多数のノード群によるデータの承認• 暗号理論 /cryptography– 公開鍵暗号方式, それに基づく署名, 暗号学的ハッシュ関数,乱数生成方式, …

• 分散システム /distributed systems– peer‐to‐peerネットワーク,flooding, 複製, 整合性, 分散合意アルゴリズム, …

3 / 15

ブロックチェーンの課題• 承認までに要する時間– ブロック生成頻度 Bitcoin 10分, Ethereum 15秒• 承認のスループット– Bitcoin 7件/秒, Ethereum (概算) 〜300件/秒– PayPal 350件/秒, Visa 1,700件/秒– いわゆるスケーラビリティ問題 ➡ second layer, …

• 保持できるデータ量– 全ノードが同じデータを保持, > 200 GB➡ 間引く [Li 2019], DHTで分散 [Abe 2018], …

• 暗号通貨の運用が必要– 暗号通貨が崩れると応用も総崩れ➡ 移植性・移送 [Shudo 2018], …

• 他にもいろいろ面白い問題が4 / 15

スループット向上と安全性の相克• スループット向上策が安全性の低下を招く– メインチェーン以外でのブロック生成が増えると、攻撃が容易に。
例：51% 攻撃による TX 無効化– ブロックの生成頻度と伝搬時間の比➡ フォーク発生率 ➡ 安全性向上策

向上策
ブロック生成頻度

ブロック伝搬時間 ↑ここをメイン なんとかする

この2つの比がスループットと安全性を決める

チェーン

フォークしたブロックチェーン“Secure High-Rate Transaction Processing in Bitcoin”, FCʼ15, 2015 の図

5 / 15

性能と安全性の両立に向けて• 伝搬時間 推定 with
ネットワーク座標系

TX 承認
スループット向上
ブロック生成頻度向上・調整• ブロックチェーンシミュレータ

安全性向上・維持ブロック
伝搬時間 短縮Compact
Block RelaybloXroute, FIBRE, …

リレー
隣接ノード [青木2019c] ネットワーク
選択[Aoki2019d]• 隣接ノード選択• リレーネットワーク
効果推定

順に紹介

伝搬時間 推定w/ ネットワーク
座標系

リレー
ネットワーク
効果推定[神田 2019a] [Kanda 2019b]

ブロックチェーン
シミュレータ[大月 2019a][Otsuki 2019b][青木 2019a] [Aoki 2019b] [Banno 2019]

伝搬時間 推定with ネットワーク座標系

6 / 15[神田 2019a][Kanda 2019b]• ネットワーク座標系 [Dabek 2004] [Chen 2007]– を適用して、ノード間伝搬時間を推定– n次元座標系 + バネモデルでの位置決め• 狙い〜 10,000 ノードブラジル？

– 伝搬高速化手法の指針– 隣接ノード選択の指針• 現状と今後
単位：ミリ秒• ただ…

– 精度の向上– そのためのトポロジ取得と推定

7 / 15

伝搬時間 推定with ネットワーク座標系• 精度は ほどほど

[神田 2019a][Kanda 2019b]

何もしなかった場合Vivaldi
仮定：次数 10,第一ホップ群 15ノード

推定値と実測値があまり一致していない？

効果がまったくないわけでもない• トポロジが不明なのが、ボトルネック– cf. “TxProbe: Discovering Bitcoin’s Network Topology …”, FC’19, 2019better誤差

8 / 15

シミュレータ[青木 2019a] [Aoki 2019b] [Banno 2019]• (パブリック) ブロックチェーン「ネットワーク」のシミュレータ– 2019年 6月 27日(木) 公開・プレスリリース– インターネット上のノード間でのブロック / トランザクション伝搬、Proof of Work のマイニングをシミュレート• 離散イベントシミュレーション– 可視化ツール– 現在、Bitcoin, Litecoin, Dogecoin のパラメータを提供– 研究の例：Median block propagation time (msec)

Normal Bitcoin algorithm

9400

Proposed algorithm

8900

8400

7900

7400
0

2000

4000

6000

8000

10000

The number of blocks

隣接ノード選択

リレーネットワーク 効果推定

9 / 15

シミュレータ[青木 2019a] [Aoki 2019b] [Banno 2019]
ウェブ
サイト

Visualizer

縮小 Bitcoin ネットワーク,
600 ノードIEEE Spectrum
記事IEEE ICBC 2019 デモ,ソウル, 2019年 5月

10 / 15

隣接ノード選択[青木 2019c] [Aoki 2019d]• 速く通信できる相手と優先的につながる• peer‐to‐peer 分野でメジャーな手法– 例えば DHT では proximity (近接性) {ID, neighbor, route} selection– 僕らもやった：DHT での proximity neighbor selection [Miyao 2013]– 実験手段がなかったので、シミュレータを作った• 手法– ブロックを配信してくれた相手ノードすべてにスコア付け• スコア = (ブロック配信時刻 – 生成時刻) の指数重み付き平均値– 10 ブロック受信するごとに隣接ノードを選択し直す• ただし、新しいノードとつながるために、K ノードは知っているノード群からランダムに選ぶ• 予備実験の結果：K = 1, P (伝搬時間 最新値の重み) = 0.3

11 / 15

隣接ノード選択[青木 2019c] [Aoki 2019d]• そこそこ縮まった– 伝搬に時間がかかったブロック群で、11.5 秒 → 8.5 秒 くらい
50%
Bitcoin ネットワークに適用
45%
6%
5%
提案⽅式
4%
隣接ノード固定3%2%
1%
0%07000 8000 9000 10000 11000 12000 13000
better

ブロック伝搬時間の中央値(ミリ秒)• 課題: Compact Block Relayの考慮, インターネットのパラメータ更新

12 / 15

リレーネットワーク 効果推定
[大月 2019a] [Otsuki 2019b]• リレーネットワーク– ブロック高速配信ネットワーク– bloXroute (2018), FIBRE (2016), Falcon (2016), BFRN (2014), …
– bloXroute: Falcon をやっていた Cornell U. の人達がビジネスとして開始
リレーネットワーク
通常の• 効果は？

ブロックチェーン
ネットワーク– 孤立ブロックはどのくらい減る？
– ブロックを早く受け取れるのだから、マイニング成功率が上がる？

13 / 15

リレーネットワーク 効果推定
[大月 2019a] [Otsuki 2019b]• SimBlock 上の Bitcoin ネットワークで実験
シミュレータ• ネットワーク レベル：
betterbetter

伝搬が速くなった！

孤立ブロックが減った！

• では、ノード レベルでは？

フォークによって発生した、メインチェーンから外れたブロック

14 / 15

リレーネットワーク 効果推定
[大月 2019a] [Otsuki 2019b]• ノード レベル：
betterbetterマイニング成功率は変わらないが…

生成したブロックが孤立ブロックになってしまう率が低下！
➡ マイニング報酬 増加

これがリレーネットワークの効能ブロックチェーン「ネットワーク」の研究

15 / 15• 課題：トランザクション承認– までの時間– スループット

TX 承認
スループット向上
ブロック生成頻度向上・調整

安全性向上・維持ブロック
伝搬時間 短縮Compact
Block Relay
bloXroute, FIBRE, …

リレー
隣接ノード [青木2019c] ネットワーク選択• ブロック伝搬時間推定短縮を狙っていろ w/伝搬時間
ネットワーク座標系
いろやってる（右図）[Aoki2019d]

リレー
ネットワーク
効果推定[神田 2019a] [Kanda 2019b]

• 謝辞
––

本研究は（公財）セコム科学技術振興財団の支援を受けたものです。
伝搬時間推定の研究はカウラ(株)の支援を受けたものです。

ブロックチェーンシミュレータ[大月 2019a][Otsuki 2019b][青木 2019a] [Aoki 2019b] [Banno 2019]参考資料 / 15

論文
• 私達–––––––––––[Shudo 2018] “Towards Application Portability on Blockchains“, IEEE HotICN 2018, 2018年 8月[神田 2019a] “ビットコインネットワーク上でのデータ伝搬遅延推定”, 信学技報, Vol.118, No.481, IA2018‐77, pp.317‐
322, 2019年 3月[Kanda 2019b] “Estimation of Data Propagation Time on the Bitcoin Network”, AINTEC 2019, 2019年 8月[大月 2019a] “Bitcoinネットワークに対するリレーネットワークの影響”, 信学技報, Vol.118, No.481, IA2018‐76, pp.309‐
316, 2019年 3月[Otsuki 2019b] “Effects of a Simple Relay Network on the Bitcoin Network”, AINTEC 2019, 2019年 8月[青木 2019a] “SimBlock: ブロックチェーンネットワークシミュレータ”, 信学技報, Vol.118, No.481, IA2018‐70, pp.219‐224, 2019年 3月[Aoki 2019b] “SimBlock: A Blockchain Network Simulator“, CryBlock 2019, 2019年 4月[Banno 2019] “Simulating a Blockchain Network with SimBlock“, IEEE ICBC 2019, pp.3‐4, 2019年 5月[青木 2019c] “ブロックチェーンネットワークにおける隣接ノード選択”, 信学技報, Vol.118, No.481, IA2018‐71, pp.225‐
232, 2019年 3月[Aoki 2019d] “Proximity Neighbor Selection in Blockchain Networks“, IEEE Blockchain 2019, 2019年 7月[Miyao 2013] “A Method for Designing Proximity‐aware Routing Algorithms for Structured Overlays”, IEEE ISCC’13,2013年 7月• 他––––––[Li 2019] “Downsampling Blockchain Algorithm”, CryBlock 2019, 2019年 4月[Abe 2018] “Mitigating Bitcoin Node Storage Size By DHT”, AINTEC 2018, 2018年 11月“Secure High‐Rate Transaction Processing in Bitcoin”, FC’15, 2015年 1月[Dabek 2004] “Vivaldi: A Decentralized Network Coordinate System”, ACM SIGCOMM 2004, 2004年 9月[Chen 2007] “Pharos: A Decentralized and Hierarchical Network Coordinate System for Internet Distance Prediction”,
IEEE GLOBECOM 2007, 2007年 12月“TxProbe: Discovering Bitcoin’s Network Topology Using Orphan Transactions”, FC’19, 2019年 2月