全人類の口座残高を管理する――(1) Bitcoinの場合――

ブロックチェーンや暗号通貨に関する前提知識は不要です。お気軽にお読みください。

# 「残高」と「取引」

Bitcoinは、決済や貯蓄などの通貨機能を代替できるデジタル通貨ネットワークシステムとして、現実に世界中で利用されています。
そして、このような決済や貯蓄が可能になるのは、ユーザーがBitcoinを利用したシステム上で「残高（balance）」および「取引（transaction）」を確認することができるからこそです。

言うまでもなくこの両者には密接な相互関連性があります。「残高」は「取引」によって変化し、「取引」は「残高」の範囲内でのみ実行可能である、といった関連性です。

![b&t.png](https://qiita-image-store.s3.amazonaws.com/0/104347/13201183-9da6-953d-11fb-c2dfd3ed52bb.png)

ユーザーとしては、「取引」の事実とその「残高」への反映が確認できるから、Bitcoin上のシステムを決済に利用することができ、「残高」が狂ったりせずにちゃんと維持されるから、Bitcoin上のシステムを貯蓄に利用することができるわけです。

# 抽象化：「状態」と「差分」という基本構造

さてここで、「残高」をより抽象的に「状態」としてとらえ、「取引」を抽象的に「差分」としてとらえるならば、「状態」に「差分」が適用されて新たな「状態」が生み出される、という基本構造は、他の多くのシステムにも共通して見られるものであり、そのようなシステムは、それぞれの（熟慮された）ポリシーに従ってこの構造を取り扱っているということが分かるでしょう。


例えば、バージョン管理システムです。
Gitは木構造のリポジトリのある時点におけるスナップショットすなわち「状態」を「コミット」として保持し、その「コミット」が、前の「コミット」への参照を保持することによって、その「コミット」のためにコントリビュータが何をしたのかという「差分」を、git diffコマンドによって派生的に導出することができるようになっています。

![git_pattern.png](https://qiita-image-store.s3.amazonaws.com/0/104347/61ce1a9d-ef5c-640b-e0c6-d6dbef303248.png)

同じバージョン管理システムでも、SubversionはGitとはまるで逆に、個々のファイルに対するリビジョン間の「差分」の集合こそが実体としてサーバーに保存されていて、そのような「差分」を累積的に適用することによって、ある時点におけるファイルの内容すなわち「状態」が、クライアントにおいて再現されるのでした。これは、サーバーの容量を節約するためなのだと思います。

![svn_pattern.png](https://qiita-image-store.s3.amazonaws.com/0/104347/95ae8932-1ff9-cb41-548f-3353201336be.png)

まったく違うジャンルの例としては、会計システムがあります。
会計システムは、事業体の財産状態のある時点におけるスナップショットすなわち「状態」を、「貸借対照表（balance sheet）」として保持し、事業体の財産に影響を与える「差分」である個々の取引を「仕訳（journal）」として保持します。「貸借対照表」に一定期間の「仕訳」を全部適用すれば、その期間の末日時点の「貸借対照表」が（理論的には）できあがる、ということです。会計にとっては、状態も差分もどちらも必須の情報なので、両方が実体化されて管理されます。

![fin_pattern.png](https://qiita-image-store.s3.amazonaws.com/0/104347/d36f1259-a3b8-6a74-9145-6686c6b39d8c.png)

# Bitcoinのデータモデル：「取引」一元主義！

このように様々なシステムがそれぞれのやり方で状態と差分を取り扱っているわけですが、それではBitcoinは、状態である「残高」と差分である「取引」とを、どのような設計思想によって取り扱っているのでしょうか？

なんとBitcoinのコアプロトコルは、「残高」データについて一切関知せず、「取引」の記録のみを管理する、という非常に大胆なポリシーによって設計・実装されています。（つまり、Subversionと同じパターンです。）
決済や貯蓄の機能を実現するためのデジタル貨幣ネットワークシステムが、ユーザーごとの「残高」情報を持たない、というのは非常に意外で奇異に感じられる設計ですが、この決断にはそれなりにもっともな理由があります。
その理由についてはまた別の記事で書こうと思いますが、ここではひとまず、このポリシーにも理由があったのだ、ということを受け入れてください。

いずれにせよ、記録すべき情報として「残高」か「取引」か、どちらか一方だけを選ばなければならないとしたら、「取引」を選ぶべきことに疑問の余地はないでしょう。
なぜなら、２つの時点間における「残高」スナップショットどうしを比較しても、その間に行われたすべての「取引」を再構築するための情報は得られませんが、すべての「取引」の記録があれば、任意の時点の「残高」を再構築することは、理論的には可能だからです。
（Gitでは、コミットとコミットの間でコントリビュータが単に5行足したのか、10行足してから5行引いたのか知る必要はありません。しかし貨幣システムでは、単に5BTC入金があったのか、10BTC入金があって5BTC出金があったのかはちゃんと知る必要があるのです。）

このように、「取引」のみを保管対象にする、と決めた上で、適当な個数の取引を１個の「ブロック」内にまとめて、さらに直前のブロックのダイジェスト値を含むいくつかのメタ情報をブロックに加えた上で、そのブロックのダイジェスト値を計算して、そのダイジェスト値についてノード（ピア）間で合意を形成する、というのがBitcoinにおけるブロックチェーンの根本的なモデルです。

![blockchain.png](https://qiita-image-store.s3.amazonaws.com/0/104347/64af0a40-4081-4b12-fe1b-0dfe159432ea.png)

つまりBitcoinのブロックチェーンには、Bitcoinネットワーク（全世界で共有されるシングルトンの空間です）における開闢（Genesis）以来の全世界のすべての取引記録が含まれており、あるブロックのダイジェスト値は前のブロックのダイジェスト値を含んで計算される、というルールによって、チェーンの末端に連なるべき最新のブロック１個のダイジェスト値について合意できれば、自動的に、それまでの全世界の全取引履歴について合意できたことになるのです。

このブロックチェーンに記録された全取引の記録を前提として、新たな取引が次々と行われ、その取引の正当性が検証され、検証をパスした取引が新たなブロックに含められてチェーンにつなげられる、というわけです。


# 暗雲――ブロックチェーンとUTXOデータベースの二元性――

ここまではなかなか壮大で美しい話なのですが、こんな極端な設計のシステムが、そうそううまく動くわけはないですよね。
特に気になるのは「取引における送金は、送金者の残高の範囲内でおいてのみ可能である」という根本的な制限が、Bitcoinのブロックチェーン上でどのように実現できるのか？という点です。

Bitcoinのブロックチェーンには、開闢以来の全人類の全取引が記録されているのだから、それを全部スキャンすれば、どのユーザーのどの時点の残高でも算出できるはずで、その算出された残高にもとづいて消費できる額を制限すれば良い、という答えは、論理的にはあり得るとしても、しょせんは空想的です。
１個ずつの「取引」の正当性検証に要する時間計算量という面で、現実的ではありません。

それではどうするのかというと、Bitcoinのコアプロトコルレベルでは、「残高」という概念を導入することを避けたまま、この制限が巧妙にモデル化されています。

すなわち、個々の「取引」は他の任意個の「取引」を「入力」として持ち、それを任意個の口座に対して「出力」する、そして「入力」の合計と「出力」の合計とは釣り合ってなければならない（取引手数料の話は無視します）、さらに、一度ある「取引」への「入力」として消費された「取引」は、二度と別の「取引」への「入力」として使用することはできない、という形でのモデル化です。

![tx.png](https://qiita-image-store.s3.amazonaws.com/0/104347/1b2b1774-e7d1-40cc-ac0f-d773c402616b.png)

つまり、自分が過去に受けた入金「取引」の対象額を、まとめたり分割したりして、それを自分自身を含む任意個の口座に送金する（そしてその際に秘密鍵で署名する）、というのがBitcoinにおける「取引」のモデルであり定義なのです。

これが、「残高」概念を排除したまま、実質的に引当可能残高の検査をすることができるようになるための仕組みです。
これによって、「引当可能残高の検査」という課題は、１個の「入金」の記録を、複数の「支払取引」に重複して割当ててしまう「二重消費（double spending）」を防止する、という「取引」間の連結関係の正当性検査に還元され、「残高」概念を排除することができているのです。

さて、いよいよここからがやっかいな問題なのですが、このような二重消費を検出し、取引の正当性検査ではじくために、Bitcoinネットワークのノードは、「現時点においてまだ消費されていない入金取引額（unspent transaction output）」の集合をデータベースとして管理しており、新規「取引」がその「入力」として既存の「取引」を指定してきた場合に、その「取引」が本当に引当可能なものであるか否かを検査するために、このデータベースを使うようになっています。

「現時点においてまだ消費されていない入金取引額（unspent transaction output）」のことを、業界用語ではUTXOと呼ぶので、これからこの記事でもそう呼ぶことにしましょう。


# コアプロトコルと実装との間のねじれ

「現時点においてまだ消費されていない入金取引額（UTXO）」だって？ なんか話がおかしくないか？ と思ったあなたは正しいです。

「現時点における」という言葉からもわかる通り、このUTXOデータベースというのは、本質的にある時点の「状態」を管理するための実装です。
つまりBitcoinは、コアプロトコルの仕様からは「いついつ時点の残高」という「状態」に関する情報を完全に排除することにしたのですが、入金取引の二重引当を防止する、という取引の正当性検査をまともな時間計算量で実装するためには、各ノードが実装において、実質的に「UTXOの集合」という「状態」を管理する必要がある、ということです。

これは結局のところ、各ノードが独自の工夫によって「残高」を管理しなければ行けないということに等しく、コアプロトコルでは合意の対象とされていない、各ノードの実装によって維持される「UTXO集合」の情報が、実質的には取引の正当性検査で重要な意味を持つ、ということになってしまいます。

つまり、全取引の履歴であるブロックチェーンについてはコアプロトコル上で合意できているが、そのブロックチェーンから派生的に算出されるはずの「UTXOの集合」≒「残高」については、実装ノード固有のバグがあるため、ある取引の正当性について合意できない、というような嫌な問題が発生しかねないようになっている、ということです。


# 巻き戻しの悪夢とundoファイル

各ノードが管理しなければならない状態が、最新のUTXOの集合のみだったらまだ良いのですが、ものが「状態」である以上、そうは行きません。
Bitcoinには、ブロックチェーンの巻き戻りという仕様があり、現実にもたまに発生するため、話は相当イヤな感じになってくるのです。

どういうことかというと、ブロックチェーンに連なる最新のブロックとして、あるノードがブロックAを受け入れたが、その後紆余曲折があって、チェーンのその箇所につなげるのは、やっぱりブロックAではなくブロックBにすべきだった、と判断を改めることがあるのです。
（Bitcoinの仕様上は、このような１世代の巻き戻りだけではなく、多世代にわたる巻き戻りもあり得ます。）

こういう時に、最新のブロックチェーンに基づいた「状態」であった「UTXOデータベース」を実体として管理していたことが、ものすごく裏目に出る、というのは容易に見て取れると思います。
つまり、今まで「共通系列　＋　ブロックA」に基いて算出され管理されていた「UTXOデータベース」を、「共通系列　＋　ブロックB」に基づく状態へと改変してやる必要があるのです。

![rollback.png](https://qiita-image-store.s3.amazonaws.com/0/104347/73c06710-dcac-62aa-10b2-a2a33dd037ae.png)

このような巻き戻りは、Bitcoinの実装においては、ブロックAを適用する前の状態にまでUTXOデータベースを巻き戻すためのパッチを適用し、その上でブロックBに基づく更新を行う、という形で行われます。
Bitcoinノードの実装は、このような任意世代への巻き戻しを実現するためのパッチであるundoファイルというものを、独自に生成し、管理しています。
（むろん、これはノードの実装の問題であり、コアプロトコルにはそんなことは書いてありません。）

DBMSやファイルシステムなど、状態を保存する上にさらに「巻き戻し」や「再適用」のためのパッチ情報を生成管理して、必要に応じてそれを適用するシステムの例は世の中にちゃんとありますから、このような実装をあまり毛嫌いするのも正しくないのかもしれません。
しかしそれでも、このようなアーキテクチャには危なっかしさを感じざるを得ませんし、それを優れていると評することは難しいように思います。

たとえば考えてみていただきたいのですが、もしGitの仕様として、git checkout 、git revert、git merge などが「差分パッチを個々のファイルに適用する」処理だったとしたら、少なくともあまり気持ちよくこれらの機能を使う気にはなれないのではないでしょうか。
（実際、Gitが開発され人気を博したポイントは、これらの機能の高速性や信頼性にあったはずです。）


# Walletアプリケーションの苦しみ

冒頭に書いたとおり、Bitcoinはデジタル通貨なわけですから、利用者がそれに求めるのは、決済や貯蓄ができることです。

ですから、これまで説明してきたような「ブロックチェーン」とか「UTXO」といった小難しい概念を、「あなたの取引履歴」や「あなたの現在残高」にわかりやすく翻訳して提示し、それに基いて新たな取引を実行するためのアプリケーションソフトが必要になりますし、そのようなアプリケーションは現に多く存在します。

そういうアプリケーションはWallet（財布）アプリケーションと呼ばれ、このWalletアプリケーションは、おおざっぱに言えば、ある口座に関連する「取引」を管理したり実行し、また、ある口座のUTXOリストを集計して「残高」として表示したりしているわけです。

そして、容易に想像できることだと思いますが、コアプロトコルにおいて「残高」が管理されていないBitcoinにおいて、「取引」の金額が「残高」から引き当てられて実行される、という常識的なモデルに合致したフィクションを提示するには、大変な手間と苦労があるようです。

https://blog.bitgo.com/challenges-optimizing-unspent-output-selection/

Bitgoは大手のWalletサービスですが、上のblog記事によれば、ユーザーにとって自然な形でBitcoinの取引を実行する裏には、ユーザーが理解しているのとは異なったモデルに基づいた処理固有の手数料を抑えようとか、取引の数が膨張しすぎないように、とか様々な配慮が必要になり、引当可能残高から取引を実行する、というだけの、ユーザーにとっては単純であるべき処理の実行も、なかなか一筋縄ではいかないようです。


# まとめ

この記事の内容を簡単にまとめてみます。

+ Bitcoinは（この記事では説明しなかった事情により）、コアプロトコルでは「残高」を管理せず、「取引」の記録のみをブロックチェーンに刻んで合意する、というエクセントリックな設計を採用しました。

+ しかし、「取引」に引当可能な「残高」の検査を現実的な時間計算量で行うためには、実質的には、各ノードが実装上の工夫として、「UTXOデータベース」を管理する必要があります。

+ このことは、コアプロトコルでの合意対象となっていない、派生的な「残高」情報が、「取引」の正当性検査の実質的な中核になることを意味するものであり、コアプロトコルのモデルと実質との間に、ねじれを生むことにつながっていると言わざるを得ません。

+ 特に、ブロックチェーンの巻き戻りが発生する際に、ノードが自分のUTXOデータベースに独自に管理していたundoパッチを当てて巻き戻す、という実装は、ブロックチェーンというモデルの単純な美しさを台無しにしてしまうような、なんとも感触の悪いものになっていると思います。

+ 決済や貯蓄の機能を利用者に提供するWalletアプリケーションにとっても、「残高」を管理しないというBitcoinのエクセントリックなモデルを、利用者にとって理解しやすい形に飼い馴らすことは容易ではなく、苦労が絶えないようです。

このように、「残高」の管理という観点からBitcoinにはかなり本質的で深刻な問題があると私は考えます。
ではなぜBitcoinはこのようにエクセントリックな設計を取らなければいけなかったのか、そしてこれよりも良い方法はあるのか、という点について、次回は、Ethereumを題材として書いてみたいと思います。