bitFlyer BlockchainのDevメンバーがブロックチェーンや日々の開発について投稿します。

サイズが不変なブロックチェーン「Coda Protocol」

こんにちは、bitFlyer BlockchainのResearch Teamです。

先日、日本時間の5月12日 4時23分43秒にビットコインが半減期を迎え、ブロック報酬が12.5BTCから6.25BTCへと変更されました。
(※弊社が提供しているエクスプローラーの chainFlyer でその様子を確認できます!)
ビットコインの価格への影響を考察する記事が多く出ていますが、一技術者としては、2010年1月の稼働開始時から10年間、大きなエラーも無く安定した稼働を続けているビットコインの仕組みに改めて感動しました。

一方、前回の記事でも取り上げた通り、ビットコインをはじめ、多くのブロックチェーンは様々な課題を抱えているのが現状です。
次の半減期は2024年頃になると想定されていますが、それまでにブロックチェーン技術がどのような発展をしているのか今から楽しみです!

今回の内容

「グローバルで行なわれている研究開発事例をわかりやすく解説するシリーズ」の第二回目の今回は、ブロックチェーンのブロック高に関わらずそのサイズが不変であるという、とても不思議な特徴を持つ Coda Protocolを取り上げます。
Coda Protocolチームが公開している公式WebページとTechnical Whitepaperの内容に基づき解説を進めていきます!

公式Webページ: https://codaprotocol.com/
Technical Whitepaper: https://eprint.iacr.org/2020/352.pdf

サイズが増えないブロックチェーン??

そもそもサイズが増えないブロックチェーンとはどういうことなのでしょうか?
通常のブロックチェーンでは、複数のトランザクションを含んだブロックを過去から現在にかけて連結するデータ構造となります。
そのため、ブロックチェーン全体のサイズは常に増加し続けます。
例えばBitcoinの場合、下の図に示す通り、ブロック0からサイズが増加し続け、2020年5月16日時点で277GBになっています。

f:id:bitFlyerBlockchainResearchTeam:20200518200929p:plain
https://www.blockchain.com/charts/blocks-size より引用

一方でCoda Protocolでは、ブロックチェーンのサイズは常に一定です。
トランザクションが発行されなかったり、ブロックが生成されない訳ではありません。
とある工夫と仕掛けを利用することで、サイズを不変にしているのです。
果たしてどのような工夫と仕掛けを利用しているのでしょうか?

データサイズを削減するための工夫

一般にブロックチェーンでは、保持するデータの候補として、トランザクション・ブロック・コントラクトコード・残高など、様々なものがあります。
この中から、各ブロックチェーンの構造・性質・思想などに基づき、保持すべきデータを取捨選択します。

Coda Protocolでは、極力データサイズを削減するために、残高のみを保持します。
この選択をすることにより、Coda Protocolは資産の送金・受金に特化したブロックチェーンとなります。*1

残高情報の正当性はどのように担保する?

残高のみを保持することでデータサイズを削減してもなお、ブロックチェーンのサイズは不変にはなりません。
ブロックチェーン上の残高が正しく更新されていること、つまりその残高の正当性を担保するためには、別の情報が必要となります。

ここで、ブロックチェーンにおける代表的な残高管理方法である、「UTXO」と「アカウント」の例を見てみましょう。
「UTXO」による残高管理の代表例はBitcoinです。
Bitcoinにおける取引データは入力と出力で構成されており、ある取引における出力は、別の取引における入力に利用されます。
UTXOは、ある取引の出力となっているが、まだ入力として利用されていない「未使用の取引」、つまり利用可能資産を指します。
よってBitcoinにおける残高は、UTXOの集合そのものとなります。
Bitcoinにおける残高情報の正当性担保に必要なデータサイズは、UTXOの集合サイズに比例します。
UTXOの集合は可変であることから、必要なデータサイズも可変となります。
つまり、不変にはなりません。

「アカウント」による残高管理の代表例はEthereumです。
Ethereumでは、トランザクションが実行されると、その結果に応じて各アカウントの残高を保持するキーバリューストアが更新されます。
非常にシンプルな管理方法ですが、アカウントの残高情報の正当性を担保するためには、トランザクションそのものを保持しておく必要があります。
ここから、残高情報の正当性担保に必要なデータサイズは、アカウントやトランザクションの数に比例して増加します。
つまり、不変にはなりません。

Coda Protocolでは、Ethereumと同じくアカウント型の残高管理を行います。
そのため、データサイズを不変にするためにはある「仕掛け」が必要になります。
アイデアとして、トランザクションを保持することなしに、アカウントの残高が正しく更新されていることを証明すれば良さそうです。
また、各アカウントの残高は、そのアカウントの保有者のみが管理しておくことで、他のアカウントの残高情報データを削減できそうです。
つまり「アカウント残高情報が正しく更新されていることの証明情報」と「自分のアカウントの残高情報」の2つのデータのみを保持する、、、ということです。

実はCoda Protocolでは、まさしくこの2つのデータのみを保持することで、データサイズを不変にすることに成功しています。
しかし、この2つのデータはどのように実現すればよいのでしょうか?
…その答えが「ゼロ知識証明」と「マークルパス」です!

ゼロ知識証明 - 情報を与えずにその情報の正しさを証明する技術

ゼロ知識証明とは?

ゼロ知識証明とは「証明者Pが検証者Vに対してある命題Xが正しいことを証明し、かつその命題が正しいこと以外の一切の情報をVに与えない」という性質を満たすプロトコルです。
具体例を用いて説明します。
例えば、検証者VはあるWebページのシステム、証明者Pはそのシステムにパスワード pwd を用いてログインしたいユーザであるとします。
ここで、Vのシステムでは、あるハッシュ関数Hを用いることで、pwd のハッシュ値 H(pwd)が、事前にシステムに登録されているハッシュ値 A に一致するかどうかでログインの判定を行います。
通常は、Pはセキュアな方法で pwdVに送信し、VH(pwd)を計算します。
しかしこれでは pwdVに漏れてしまうため、ゼロ知識証明とはいいません。

ゼロ知識証明では、Ppwdの代わりに、 pwd から生成されるゼロ知識証明情報 \pi を計算し、(\pi, H, A)の組をVに送信します。
Vは、特別な検証処理を行うことで、「H(pwd) = A となる pwdPが知っている」ことを確認します。
このとき、証明情報\piから pwd に関する一切の情報がわからない、というのがゼロ知識証明の特徴です。

ブロックチェーンにおいてゼロ知識証明を利用すると、トランザクションやブロックそのものの代わりに証明情報\piのみを利用することで、トランザクション・ブロックの正しさを証明することが可能になります。
もし証明情報\piの大きさが非常に小さい場合は、大幅にデータサイズの削減ができそうです。
一方、ブロックチェーンにおいては、Pはトランザクション作成者、Vはトランザクション検証者(マイナー等)となるため、Pが不特定多数のVとやり取りすることは非現実的です。
そのため、非対話型、つまりPが証明情報を一方的にVに送ることで検証が実行できる形式のゼロ知識証明である必要があります。
この性質を満たすゼロ知識証明がzk-SNARKです。

非対話型かつ軽量なゼロ知識証明 - zk-SNARK

zk-SNARKは、非対話型かつ、証明情報サイズが小さい固定値(つまりサイズの観点で簡素)となるようなゼロ知識証明プロトコルです。
また、証明情報の検証コストは \mathcal{O}(1)であることが知られています。

そのため、zk-SNARKを利用すると、小さな固定値サイズの証明情報\piのみで、トランザクションやブロックの正しさを証明することが可能になります。
残高はトランザクションの実行結果として表現されるため、トランザクションの正しさが証明されれば、残高の正しさも担保されます。

zk-SNARKを利用したサイズが不変なブロックチェーンの構築

zk-SNARKを利用することで、ブロックチェーンサイズが不変となるようなブロックチェーンを構築することが可能です。

具体的な構成手順を

  1. ブロックの証明情報へと置き換え、と
  2. ブロックチェーン全体の証明上への置き換え、

に分けて説明します。
以降では、ブロックチェーンは合計3つのブロックから構成されているものとします。

ブロックの証明情報へと置き換え

f:id:bitFlyerBlockchainResearchTeam:20200518200933p:plain

1つ目の手順として、ブロックを証明情報へと置き換えます。
zk-SNARKを利用して、ブロックが正しいこと(= ブロックが含む全てのトランザクションが正しい、ブロックがプロトコル通りに構築されている)に対する証明情報を生成します。
すると、上図にあるように、証明情報のみから構成されるブロックチェーンを構成できます。
しかしこれでは、時間経過とともに、保存すべき証明情報のサイズが線形的に増加してしまうため、これだけではブロックチェーンサイズは不変になりません。

ブロックチェーン全体の証明情報へと置き換え

f:id:bitFlyerBlockchainResearchTeam:20200518200938p:plain

そこで、2つ目の手順として、ブロックチェーン全体を1つの証明情報へと置き換えることを考えます。

まず「ブロック0の証明情報とブロック1の証明情報が同時に正しいこと」を証明するための証明情報 Proof #01 を生成します。
同様に、「<ブロック0の証明情報とブロック1の証明情報が同時に正しいことを証明するための証明情報 Proof #01>と<ブロック2の証明情報>が同時に正しいこと」を証明するための証明情報 Proof #012 を生成できます。
このとき、Proof #012は、ブロック0からブロック2までの全てのトランザクションの正しさを証明するための証明情報となっているため、この証明情報1つで、過去の全てのトランザクションの検証が可能となります。
以後、同様な証明情報の生成を繰り返すことで、ブロックチェーン全体を常に1つの証明情報へと置き換えることができます。

zk-SNARKの性質から、この証明情報のサイズは不変です。
よって、ブロックチェーン全体を、ただ一つのサイズが不変な証明情報に置き換えることができました!*2

マークルパスを利用した自身の残高の管理

ここまででブロックチェーン全体をサイズが不変な証明情報で表現できることはわかりましたが、このままでは自身の残高がわかりません。
なぜなら、証明情報はトランザクションの正しさを証明するだけで、トランザクションや残高は表現していないからです。
しかしながら、残高管理は簡単な工夫を施すことで解決することができます。
その工夫こそ「マークルパス」です。

マークルツリー・マークルルートと証明情報

f:id:bitFlyerBlockchainResearchTeam:20200525002430p:plain

マークルパスを理解するためには、マークルツリーとマークルルートの理解が必要です。
そこでまずは、マークルツリーとマークルルートについて説明します。

トランザクションを実行した結果として、ある時点でのAlice, Bob, Charlie, Davidの残高はそれぞれ100, 50, 70, 140であるとします。
この時、各残高のハッシュ値を求め、さらにそのハッシュ値と別のハッシュ値を連結した値のハッシュ値を求め、、、という操作を繰り返すと、図のような木構造ができあがります。
この木構造のことをマークルツリー、木の頂点に位置するハッシュ値をマークルルートと言います。
ハッシュ関数の特性から、マークルルートの値は常に一定のデータサイズになります。

残高を表すマークルツリーでは、残高が完全に一致していない限り、異なるマークルルートが生成されます。
そのため、マークルルートは、その時点での全ての残高を代表した値と考えることができます。

実は、先程説明したzk-SNARKで生成した証明情報が証明しているのは、トランザクションそのものの正しさではなく、「トランザクションの結果として得られる残高の代表値であるマークルルートの正しさ」を証明しています。
そのため各ノードは、その時点での残高のマークルルートと対応する証明情報を保持することになります。

マークルパスを利用した残高証明

f:id:bitFlyerBlockchainResearchTeam:20200525002426p:plain

前述の状況下で、例えばAliceが「自分の残高が100であること」を確かめたいとします。
この時、Aliceは次の3つの情報のみを保持していれば十分です。

  • Aliceの残高情報
  • Hash B
  • Hash CD

これらの情報から、マークルルートHash ABCDを計算することができるため、Aliceの残高が100であることが確認できます。
この時、この3つの情報をマークルパスと言います。
一般に、マークルツリーが管理するアカウント数が Nの時、マークルパスのサイズは \log(N)+1となります。
仮に、1800京個のアカウントを管理するとしても高々64個のハッシュ値と1個の残高情報を管理すれば十分です。
256ビットのハッシュ関数を利用すると仮定しても、65個を管理するためには、多く見積もっても3KBあれば十分です。
ここから、マークルパスを利用することで、十分小さなデータ容量で自身の残高を管理することが可能になることがわかりました。

Coda Protocol

Coda Protocolは、ここまで説明してきた「zk-SNARKを利用したサイズが不変なブロックチェーン」と「マークルパスを利用した自身の残高の管理」を利用したブロックチェーンプロトコルです。
ただし、これらは単にブロックチェーンのデータの表現形式を定めているに過ぎないため、ブロックチェーンとして稼働させるためには他にも検討すべき項目があります。
Coda Protocolは具体的に次のようにプロトコルを規定しています。

  • coda という基軸通貨が存在します。トランザクション手数料の支払い、マイニング報酬等に利用されることが想定されています。
  • コンセンサスアルゴリズムにはPoSベースのOuroboros Samasikaを利用します。ブロック生成者は、ステーキングしているcodaの量に応じて選択されます。
  • 証明情報を生成することに特化した処理を行う Snake Workersが存在します。ブロック生成者は、いずれかのSnake Workersに証明情報の生成を依頼する必要があります。これにより、ブロック生成と証明情報生成の権限を分散させることができます。

その他の詳細はCoda Technical Whitepaperを参照してください。

おわりに

データサイズが常に一定となるブロックチェーンプロトコルである Coda Protocol を解説しました。
ブロックサイズによらずブロックチェーン全体としてはサイズが一定に保たれることから、ブロックサイズを実質無限にスケールさせることができます。
そのため、Coda Protocolはブロックチェーンのトランザクションスケーラビリティを解決可能な技術としても利用できます。
記事執筆時点ではテストネットのβ版が公開されていますが、今後の進化が楽しみです!

bitFlyer Blockchainではブロックチェーンエンジニアを絶賛採用中です!!
エンジニアチームはメンバー間のコミュニケーションを英語で行うなど様々な国籍のメンバーで構成されるチームでお互いに協力をしながら、個々人が自発的に情熱をもって仕事に取り組んでいます。
ご興味ある方は、ぜひご連絡ください!!
www.wantedly.com

bitFlyer Blockchainがブロックチェーンエンジニアを募集!

*1:スマートコントラクトを利用するためには、ブロックチェーンにコントラクトコードを保存する必要があります。ブロックチェーンに保存することで、コントラクトコードの同一性と実行結果の正確性を担保することができるためです。

*2:なお、このような証明情報の構築方法は Incrementally-computable SNARKと呼ばれています。詳細は下記論文を参照してください。https://iacr.org/archive/tcc2008/49480001/49480001.pdf