Graphen – BitcoinCashのブロック伝搬速度を劇的に向上させる技術について解説します

2018.11.17

BCHNews編集部

こんにちは、BCHNews編集部のreiです。

この度、BitcoinCashの有力クライアントのうちの一つであるBitcoinUnlimited(BU)は、$50,000をマサチューセッツ大学のGeorge Bissias氏およびBrian Levine氏に対して融資することを発表しました。

Bitcoin Unlimited's membership has approved a budget of US $50,000 to fund Phase II of Graphene fast block propagation work by the University of Massachusetts. Phase I on the #BitcoinCash main-net has performed up to 10x faster than Xthin / Compact Blocks.https://t.co/efIpo5qQEc

— BitcoinUnlimited (@BitcoinUnlimit) October 10, 2018

これは、Bitcoin Forumに投稿された、二人の学生がBUバージョンのGraphene2.0の初期実装を行うための資金援助の要請に対して、BUが応じたものとなります。
Grapheneは、簡単にいうとブロックを他のノードへ高速に送信する技術のことです。
従来のXtreme Thinblocks(XThin)やCompact Blocksなどの仕組みよりも数倍速いブロックの伝達を可能にしています。
この仕組みを利用した既存の暗号通貨として、BitSharesやEOS、Steamなどの通貨が挙げられ、BUのクライアントもGraphene1.0プロトコルを導入しています。

そこで、本日はこのGrapheneについてご紹介しようと思います。

Grapheneの概要

まず、Grapheneという技術は、Cryptonomexというブロックチェーン開発企業によって開発されました。
Cryptonomexは、BitSharesブロックチェーンの開発者たちが創業した、産業用ブロックチェーン技術の成長と普及を目標とする企業です。

前述した通り、BitSharesやEOS、Steamなどの通貨ですでに使用されており、Bitcoinで問題になったスケーラビリティ問題やトランザクションの承認速度を大幅に改善した技術となっています。

現在、GrapheneはGraphene1.0とGraphene2.0の二つのバージョンが存在します。
Graphene2.0はSteemが開発した技術で、Graphene1.0のメモリ使用に関する問題点を改善したものがGraphene2.0です。
1秒間に何十万件ものトランザクションを処理できたGraphene1.0の性能からさらに、

ロード時間と終了時間の短縮
データベースへの並列アクセス
クラッシュに対してより堅牢

などの利点を獲得したものです。

Grapheneの仕組み

Grapheneのアイデアの根幹は、「受信者がメモリプールに持っている情報は、送信者がわざわざ送る必要がない」という部分にあります。

ブロックには、受信者には事前に知られていないであろうヘッダー情報と、既に受信者のメモリプールにある可能性が高いトランザクションの集合で作成されます。そのため、帯域幅を節約するために、実際のトランザクションデータとトランザクションIDを送信せず、代わりにトランザクションのリストを表現するため、ブルームフィルターおよび、Invertible Bloom Lookup Tables(IBLTs)という２つのデータ構造の組み合わせを使用します。

ここで、ブルームフィルターとは要素が集合に含まれるかどうかを効率的に判定することができる仕組みです。

ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。

引用元：https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AB%E3%83%BC%E3%83%A0%E3%83%95%E3%82%A3%E3%83%AB%E3%82%BF

また、IBLTは、ブルームフィルターの一種であるCounting Bloom Filterに似ていますが、２つのIBLT同士で差を取ることができ、共通の要素だけのIBLTを得ることができる仕組みです。

下図はGrapheneでの送信者から受信者までのメッセージ送信を図示したものです。簡単に言えば、「受信者の持っていない情報を、送信者と受信者で確認し合って、受信者の持っていない情報だけを送信者が送る」ということになります。

引用元：https://github.com/BitcoinUnlimited/BUIP/blob/master/093.mediawiki#ref2

詳細な手順は次のようになっています：

送信者がINVメッセージを送信し、受信者に対して新しいブロックが利用できると通知
受信者がそのブロックをまだ知らない場合、自身のメモリプール”m”に含まれるトランザクション数を含んだget_grblkメッセージを送信
送信者は、送信するブロック内の全てのトランザクションIDのブルームフィルターS、各トランザクションIDのCheap hashを含むIBLT I”、追加のトランザクションリストV、トランザクションの順序Rとブロックヘッダでgrblkメッセージを構築
受信者はローカルで知られている全てのトランザクションIDの集合Tを作成
Sを使用して、TからSにあると思われるトランザクションIDを算出、IBLT I’を作成
I – I’を行ない、受信者の持っていないトランザクション集合Mを算出
Mが空でなかった場合、受信者はget_grblktxメッセージを送信
送信者は、Mにある完全なトランザクションを含むgrblkメッセージで反応
受信者は、ブロックヘッダのマークル木のルートに対してトランザクションを検証・配置

IBLTを構築する際に出てくるCheap hashは、トランザクションIDのハッシュのはじめ8バイトを、64ビットの符号なしリトルエンディアン整数として解釈したものを指します。

上記の手順は、IBLTの確率的な性質などからIBLT減算や、その後のトランザクション送信で失敗する可能性があります。
しかし、失敗を検出した時点でフルブロックもしくはXThinブロックの要求を行うようになっており、素早く正確なトランザクションの送信を可能にしています。

参考URL：
https://github.com/cryptonomex/graphene
https://github.com/BitcoinUnlimited/BUIP/blob/master/093.mediawiki
https://steemit.com/steem/@steemitblog/steem-developer-update-graphene-2-0

一言

本日は、効率的に素早くブロックを送信するGrapheneという仕組みに関してご紹介しました。
仕組みについて簡単にまとめると、ブロック自体ではなく、トランザクションに関する2つリストを送信し、受信者が持っていない情報だけを送る仕組みです。
最初にお話をしましたが、Grapheneはすでにいくつかの通貨で導入されており、これからの通貨のスタンダードになる技術かもしれませんね。