LINE Blockchain BFT finality - Consensus Algorithm

Digest2020.11.20

はじめに

サトシ ナカモトの論文が発表されたときは、ブロックチェーンという言葉はなかったり、コンセンサスアルゴリズムという言葉は世間に注目される言葉ではありませんでした。その論文にあったのは、hash、chain、Proof of Work (PoW)、Consensus Mechanism 、etc. という言葉たちでした。この論文から Bitcoin は誕生し、そしてたくさんの議論や研究が進み、多くの新しい言葉が生まれたのはブーム、みんなが注目したからでしょう。

さて早速、今回は LINE Blockchain で採用している PBFT (Practical Byzantine Fault Tolerance)のコンセンサスアルゴリズムについて紹介します。

 

コンセンサスアルゴリズム

現在、古代から今も行われている物々交換から始まり、お金と物、デジタルマネーと物、デジタルマネーとデジタルアイテムなどの交換が盛んに行われています。特にお金の誕生から、お金やデジタルマネーを用いた安心・安全な交換・取引を行うために金融機関が多大なコストを支払いそれを実現しています。安心・安全のために、取引記録を残すことにして、そして、そのために人手を介した徹底的な取引内容のチェックおよび改ざんされないための仕組みを導入して、人々になんの気兼ねなく安心して商取引、デジタル商取引が行えるようにしています。

ブロックチェーンおよび、コンセンサスアルゴリズムが注目されたのはこの多大なコストへの解決策としてでした。インターネットの登場ともに見直されている各種業務改善は、人手を介さずにコンピュータでできることはコンピュータに任せて、効率をあげようとするためのものです。コンセンサスアルゴリズムは、人手を介した徹底的な取引内容のチェックを、暗号学的に証明されたデジタル商取引に置き換えることです。事実、デジタルゴールドとして(個人的には現時点ではデジタルマネーではないのが残念でもあり将来への期待でもあります) Bitcoin や Ethereum などでの活発な取引はそれを証明していると思います。金融機関ではなく、ブロックチェーンベースのシステム自体の安心、安全は人々を惹きつけて、デジタルゴールドは将来への投資、リスク回避としての魅力を存分に発揮しています。

私たちは、LINK という暗号資産を LINE Blockchain の上に発行しています。そこではもちろんブロックチェーンの特徴、ハッシュチェーンのデータ構造とコンセンサスアルゴリズムを用いてデジタル商取引および取引記録を安全に保存しています。

 

ファイナリティ

コンセンサスアルゴリズムとして有名な PoW の特徴は、全員でCPUパワーを使い、nonce (number used once)という一度だけ使われる数字を計算で求めることが重要な要素でした。この nonce を使うことで条件を満たす hash を求めることができ、他の人もその nonce を使えば条件を満たす正しい hash が求めていることが確認できます。ただし、この nonce は唯一固有の数字ではなく、条件を満たす hash を求めるための数字の一つでしかないので、条件を満たすための nonce は複数存在します。そうすると、全員で nonce を計算で求めると、複数の条件を満たす正解の hash も生成されます。基本的に、それは早いもの勝ちなので問題になりません。ですが、もし同時に計算と確認ができてしまうと、ブロックチェーンでのデータ保存、ブロックの生成において、チェーンが分岐してしまうことがあります。Bitcoin ではこの問題解決のために、確率的ファイナリティ(probabilistic finality)というものでチェーンの分岐を一つにするにようにしています。時間が経てば一つのチェーンに収縮するはず、一つに収縮する確率が高いというものです。証明された計算によると、hash 計算をして分岐しているチェーンそれぞれが同時に6回連続してブロック生成される確率は相当低いということです。

ここで注目したいのは確率的ファイナリティです。Longest Chain プロトコルと呼ばれる、ブロックが複数のチェーンに分岐したときに最も長いチェーンを選択するプロトコルは確率的ファイナリティとなります。もしデジタルゴールドではなく、デジタルマネーとして、ごく一般的な取引などをするとき、確率的、つまり絶対に取引が成功する確信がない状態というのは、安心して使うには心もとなく、急いで決済したいときに、時間が解決するようなやり方では人々がすぐに使いたいということが実現できません。そこで確率的でないファイナリティというものが注目されています。BFT (Byzantine Fault Tolerance)プロトコルは、複数の分岐が絶対に発生しないようにして、即座にブロックの生成と確認を完了させます。ただしこの方法は、だれか一人 Proposer という人を選出しないといけません。この Proposer がブロックを生成して他の人を Validator として確認することで、分岐が絶対に発生しないようにしています。(セキュリティ的に Propser が攻撃されれば危ないんじゃないかと思う人は勘がいいです。)

ファイナリティが確率的なのかそうでないのか、これは用途や要件に合わせて採用すべきものが変わるのでどちらが正解ということはありませんが、LINE としては確実な安心を提供したいので、確定的なファイナリティがある BFT プロトコルを重視しています。

 

PBFT

BFT プロトコルで有名な実装としては PBFT があります。LINE では現在プライベートのブロックチェーンネットワークで運用しているので、先ほどの Proposer が攻撃されるリスクをほぼ無くして、こちらの PBFT をコンセンサスアルゴリズムに採用しています。Bitcoin の PoW では全員で Proposer/Validator になるのに対して、PBFT では固定のProposer/Validator でブロックの生成をします。Bitcoin の PoW に対して対極に位置するようなコンセンサスアルゴリズムです。

LINE での Proposer/Validator の選出は、上述の BFT protocol の図にあるように、まずは全 Node の中から Validator となる Node たちを指定しています。そして、その中から Proposer の一人をランダムで確定させています。投票を通じて選出された議員内閣制に近く、ブロックの提案、検証、確定、そしてそのファイナリティは、その選出された議員たち Propoer/Validator の投票で確定されるのが特徴です。(PoW をこれに近いもので例えるなら国民投票でブロックを確定させるとなるでしょう。)

ちょっとコンセンサスアルゴリズムから話を少しそらしてブロックチェーンのデータ構造の観点でみてみます。PBFT、PoW そして一般的な Database の Replication と見比べてみると、ブロックチェーンが採用しているブロック生成は検証強度が高いのがわかると思います。PBFTは3フェーズあり、その中で検証が2回あり、かつ2回とも特別多数(67%以上の合意投票)でブロックがファイナリティを持って生成されます。PoWは検証は1回で、過半数(51%の合意投票)でブロックが確率的ファイナリティで生成されていきます。一般的な Database の Replication ではリクエストがきたら検証して登録して、それをレプリカに配ります。そのとき設定された閾値の数のレプリカが生成されたらデータが生成されるようになっていて、検証強度やブロックチェーンのデータ構造の特徴の対検閲制からみると非常にシンプルになっています。

 

終わりに

さきほども言いましたがこれらは用途によって採用するコンセンサスアルゴリズムを決定すべきで、どれも一長一短があります。現在進行形で Bitcoin の Longest Chain プロトコル、Ethereum の  GHOST プロトコル や BFT プロトコルの実装は日々研究されています。GHOST プロトコルに BFT プロトコルを使ってファイナリティを得ようとしている、LMD Ghost/CBC Casper や BABE/GRANDPA など、BFT プロトコルの Proposer/Validator への攻撃リスクを研究している PoS/DPoS/NPoS や VRF を使った Proposer の安全でランダムな選出があります。これらについては私たちも日々研究しています。最近は、BalPhargmms というバランスよく Validator を選出するアルゴリズムについてリサーチをしていました。(https://engineering.linecorp.com/ja/blog/internship-report20-blockchain/)

そして LINE としては LINE Blockchain で採用している BFT プロトコルのPBFTを基本に、さらによりよいコンセンサスアルゴリズムを研究しています。私たちから何か新しい成果がありましたら、またこちらで紹介できればと思います。

 

 

 

List
LINE Blockchain BFT finality - Consensus Algorithm

LINE Blockchain BFT finality - Consensus Algorithm

Digest・2020.11.20


はじめに

サトシ ナカモトの論文が発表されたときは、ブロックチェーンという言葉はなかったり、コンセンサスアルゴリズムという言葉は世間に注目される言葉ではありませんでした。その論文にあったのは、hash、chain、Proof of Work (PoW)、Consensus Mechanism 、etc. という言葉たちでした。この論文から Bitcoin は誕生し、そしてたくさんの議論や研究が進み、多くの新しい言葉が生まれたのはブーム、みんなが注目したからでしょう。

さて早速、今回は LINE Blockchain で採用している PBFT (Practical Byzantine Fault Tolerance)のコンセンサスアルゴリズムについて紹介します。

 

コンセンサスアルゴリズム

現在、古代から今も行われている物々交換から始まり、お金と物、デジタルマネーと物、デジタルマネーとデジタルアイテムなどの交換が盛んに行われています。特にお金の誕生から、お金やデジタルマネーを用いた安心・安全な交換・取引を行うために金融機関が多大なコストを支払いそれを実現しています。安心・安全のために、取引記録を残すことにして、そして、そのために人手を介した徹底的な取引内容のチェックおよび改ざんされないための仕組みを導入して、人々になんの気兼ねなく安心して商取引、デジタル商取引が行えるようにしています。

ブロックチェーンおよび、コンセンサスアルゴリズムが注目されたのはこの多大なコストへの解決策としてでした。インターネットの登場ともに見直されている各種業務改善は、人手を介さずにコンピュータでできることはコンピュータに任せて、効率をあげようとするためのものです。コンセンサスアルゴリズムは、人手を介した徹底的な取引内容のチェックを、暗号学的に証明されたデジタル商取引に置き換えることです。事実、デジタルゴールドとして(個人的には現時点ではデジタルマネーではないのが残念でもあり将来への期待でもあります) Bitcoin や Ethereum などでの活発な取引はそれを証明していると思います。金融機関ではなく、ブロックチェーンベースのシステム自体の安心、安全は人々を惹きつけて、デジタルゴールドは将来への投資、リスク回避としての魅力を存分に発揮しています。

私たちは、LINK という暗号資産を LINE Blockchain の上に発行しています。そこではもちろんブロックチェーンの特徴、ハッシュチェーンのデータ構造とコンセンサスアルゴリズムを用いてデジタル商取引および取引記録を安全に保存しています。

 

ファイナリティ

コンセンサスアルゴリズムとして有名な PoW の特徴は、全員でCPUパワーを使い、nonce (number used once)という一度だけ使われる数字を計算で求めることが重要な要素でした。この nonce を使うことで条件を満たす hash を求めることができ、他の人もその nonce を使えば条件を満たす正しい hash が求めていることが確認できます。ただし、この nonce は唯一固有の数字ではなく、条件を満たす hash を求めるための数字の一つでしかないので、条件を満たすための nonce は複数存在します。そうすると、全員で nonce を計算で求めると、複数の条件を満たす正解の hash も生成されます。基本的に、それは早いもの勝ちなので問題になりません。ですが、もし同時に計算と確認ができてしまうと、ブロックチェーンでのデータ保存、ブロックの生成において、チェーンが分岐してしまうことがあります。Bitcoin ではこの問題解決のために、確率的ファイナリティ(probabilistic finality)というものでチェーンの分岐を一つにするにようにしています。時間が経てば一つのチェーンに収縮するはず、一つに収縮する確率が高いというものです。証明された計算によると、hash 計算をして分岐しているチェーンそれぞれが同時に6回連続してブロック生成される確率は相当低いということです。

ここで注目したいのは確率的ファイナリティです。Longest Chain プロトコルと呼ばれる、ブロックが複数のチェーンに分岐したときに最も長いチェーンを選択するプロトコルは確率的ファイナリティとなります。もしデジタルゴールドではなく、デジタルマネーとして、ごく一般的な取引などをするとき、確率的、つまり絶対に取引が成功する確信がない状態というのは、安心して使うには心もとなく、急いで決済したいときに、時間が解決するようなやり方では人々がすぐに使いたいということが実現できません。そこで確率的でないファイナリティというものが注目されています。BFT (Byzantine Fault Tolerance)プロトコルは、複数の分岐が絶対に発生しないようにして、即座にブロックの生成と確認を完了させます。ただしこの方法は、だれか一人 Proposer という人を選出しないといけません。この Proposer がブロックを生成して他の人を Validator として確認することで、分岐が絶対に発生しないようにしています。(セキュリティ的に Propser が攻撃されれば危ないんじゃないかと思う人は勘がいいです。)

ファイナリティが確率的なのかそうでないのか、これは用途や要件に合わせて採用すべきものが変わるのでどちらが正解ということはありませんが、LINE としては確実な安心を提供したいので、確定的なファイナリティがある BFT プロトコルを重視しています。

 

PBFT

BFT プロトコルで有名な実装としては PBFT があります。LINE では現在プライベートのブロックチェーンネットワークで運用しているので、先ほどの Proposer が攻撃されるリスクをほぼ無くして、こちらの PBFT をコンセンサスアルゴリズムに採用しています。Bitcoin の PoW では全員で Proposer/Validator になるのに対して、PBFT では固定のProposer/Validator でブロックの生成をします。Bitcoin の PoW に対して対極に位置するようなコンセンサスアルゴリズムです。

LINE での Proposer/Validator の選出は、上述の BFT protocol の図にあるように、まずは全 Node の中から Validator となる Node たちを指定しています。そして、その中から Proposer の一人をランダムで確定させています。投票を通じて選出された議員内閣制に近く、ブロックの提案、検証、確定、そしてそのファイナリティは、その選出された議員たち Propoer/Validator の投票で確定されるのが特徴です。(PoW をこれに近いもので例えるなら国民投票でブロックを確定させるとなるでしょう。)

ちょっとコンセンサスアルゴリズムから話を少しそらしてブロックチェーンのデータ構造の観点でみてみます。PBFT、PoW そして一般的な Database の Replication と見比べてみると、ブロックチェーンが採用しているブロック生成は検証強度が高いのがわかると思います。PBFTは3フェーズあり、その中で検証が2回あり、かつ2回とも特別多数(67%以上の合意投票)でブロックがファイナリティを持って生成されます。PoWは検証は1回で、過半数(51%の合意投票)でブロックが確率的ファイナリティで生成されていきます。一般的な Database の Replication ではリクエストがきたら検証して登録して、それをレプリカに配ります。そのとき設定された閾値の数のレプリカが生成されたらデータが生成されるようになっていて、検証強度やブロックチェーンのデータ構造の特徴の対検閲制からみると非常にシンプルになっています。

 

終わりに

さきほども言いましたがこれらは用途によって採用するコンセンサスアルゴリズムを決定すべきで、どれも一長一短があります。現在進行形で Bitcoin の Longest Chain プロトコル、Ethereum の  GHOST プロトコル や BFT プロトコルの実装は日々研究されています。GHOST プロトコルに BFT プロトコルを使ってファイナリティを得ようとしている、LMD Ghost/CBC Casper や BABE/GRANDPA など、BFT プロトコルの Proposer/Validator への攻撃リスクを研究している PoS/DPoS/NPoS や VRF を使った Proposer の安全でランダムな選出があります。これらについては私たちも日々研究しています。最近は、BalPhargmms というバランスよく Validator を選出するアルゴリズムについてリサーチをしていました。(https://engineering.linecorp.com/ja/blog/internship-report20-blockchain/)

そして LINE としては LINE Blockchain で採用している BFT プロトコルのPBFTを基本に、さらによりよいコンセンサスアルゴリズムを研究しています。私たちから何か新しい成果がありましたら、またこちらで紹介できればと思います。

 

 

 


List