Develop with pleasure!

福岡でCloudとかBlockchainとか。

取引所の支払い能力を証明する(Proof of Solvency)Provisionsプロトコル

Mt.Goxの破綻後に発表された取引所の支払い能力を証明するプロトコルProvisionsのホワイトペーパー↓

http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf

仮想通貨を取り扱う取引所では、一般的な銀行の仕組みである部分準備金銀行のようなアプローチはコミュニティから良しとされず、顧客が預入をしているコインの総量以上のコインを取引所が保有していることが求められる傾向がある。実際に顧客が預けたり取引所上で購入したコインの総量と同じ量のコインを実際に取引所が持っていない場合、一斉に引き出しが発生すると一部の顧客はコインを引き出すことができないし、取引所がハッキングを受けたり、破綻した場合、不足しているコインは顧客の元に戻ってこない可能性が高い。

取引所の破綻そのものを回避する仕組みはないものの、顧客が預入・取引しているコインを取引所が確かに支払うことができることを証明する仕組みは、顧客の資産保護という点で重要だ。↑のProvisionsでは暗号学的な仕組みを利用して取引所の支払能力を証明するためのプロトコルを提案している。

ざっとホワイトペーパーの内容を見てみる↓

Proof of Solvency

取引所に支払能力があるかどうかは、単純に取引所の総資産 ≧ 取引所の総負債であることが証明できればいい。このためProof of Solvencyを構成するは以下の3つのプロトコルで構成される。

  • プロトコル1 資産の証明
    取引所が署名可能なBitcoinの合計量にコミットした証明
  • プロトコル2 負債の証明
    取引所のすべての顧客のBitcoinの残高にコミットした証明
  • プロトコル3 支払能力の証明
    負債の証明と資産の証明のコミットメントの差を準同型的に計算し、支払能力を証明する

Provisionsは、Confidential Transactionなどでお馴染みのPedersen Commitmentやゼロ知識を使ってこれらのプロトコルを実現する。

表記
  • gとhを楕円曲線のグループGのジェネレータ(固定値)とする。
  • yを公開鍵、xを秘密鍵とする。
  • xとyの関係は、 {y = g^{x}}と表記する(一般的な楕円曲線の公開鍵と秘密鍵の表記は {y = xG}だけど、このホワイトペーパーでは←を使う)。

プロトコル1資産の証明

プロトコル1では取引所が持つ総資産へのコミットメントを生成する。この時重要なポイントが、取引所が実際にいくらの資産を保有しているのかを明かすこと無く資産の証明ができること。

総資産へのコミットメントの作成

取引所はまず公開鍵の匿名セット {PK = {y_1, ..., y_n}}を用意する(yは公開鍵)。このセットの内、取引所が実際に対応する秘密鍵xを知っている公開鍵のセットをSとする。SとPKの関係は {S \subseteq PK}。また、0か1の値を持つ {s_i}を定義し、取引所が秘密鍵を知っている場合はs = 1、知らない場合はs = 0とする。公開鍵 {y_i}にロックされているビットコインの量を {bal(y_i)}とすると、取引所の総資産は↓のように表現できる。

 {\displaystyle \sum_{i=1}^{n} s_i \cdot bal(y_i)}

ここで、公開鍵 {y_i}が持つコインの量 {bal(y_i)}には取引所が秘密鍵を持っている分と持っていない分が含まれ、持っていない分については {s_i} = 0なので合計に加えられない。PKが与えられれば検証者は(誰でも)ブロックチェーンを確認することで各 {bal(y_i)}の量を確認できる。

続いて {bal(y_i)}を使って以下の式を定義する。

 {b_i = g^{bal(y_i)}}

この式では {b_i}が、 {bal(y_i)}秘密鍵としたときの公開鍵となることが分かる。先述したように誰もが {bal(y_i)}の値を知ることができるので、誰もが {b_i}を計算できることになる。

取引所は {s_i \cdot bal(y_i)}毎にランダムな値 {v_i}を選択して、以下のPedersen Commitmentを作成する。

 {p_i = b_{i}^{s_i} \cdot h^{v_i}} [1]

ここで {h^{v_i}}はgとは異なる別のジェネレータhとランダムに選択した秘密鍵 {v_i}から生成した公開鍵になる。 {s_i}については取引所が秘密鍵を知らない場合0なので、その場合 {b_{i}^{0} = 1} {p_i}は実質 {p_i = h^{v_i}}

このコミットメントをi=1,..,nまで足していくと

{ \displaystyle
Z_{Assets} := \prod_{i=1}^{n} p_i = \prod_{i=1}^{n} b_i^{s_i} \cdot h^{v_i} = g^{Assets}h^{(\sum_{i=1}^{n} v_i)}
} [2]

と、取引所の資産の合計額へのコミットメントが出来上がる。
※ 合計額へのコミットメントを公開するだけで実際の合計額が明らかになる訳ではない。
 { g^{Assets}}のAssetsが実際に取引所が所有する=秘密鍵を持つコインの合計)

ちなみに {Z_{Assets}}が取引所の本当の総資産かどうかは分からない。支払能力を証明するには総負債以上の総資産があることが証明できれば良いのでコミットメントには含まれていない余剰金があっても問題はない。

総資産へのコミットメントの証明

総資産へのコミットメント {Z_{Assets}}が計算できても、 {s_i = 1}の公開鍵 {y_i}に対する秘密鍵を本当に取引所が所有しているのだろうか?という疑問は残る。

これが証明できないと {Z_{Assets}}が実際に取引所の管理下にある資産なのか分からないので、取引所は合計額を秘匿したままゼロ知識でこれを証明する。

証明のためまず取引所は各i毎にランダムな値 {t_i}を選択して以下のような {s_i}のPedersen Commitmentを作成する。

 {\displaystyle l_i = y_{i}^{s_i}h^{t_i} \in G} [3]

このコミットメントは以下のように { y_{i}^{s_i}}の部分を量 {x_i \cdot s_i}に対するPedersen Commitmentに置き換えることができる。

 {\displaystyle l_i= g^{x_i \cdot s_i}\,h^{t_i}}[4]

 {\hat x_{i} := x_i \cdot s_i}として以下のように記述する。

 {\displaystyle l_i= g^{\hat x_i}\,h^{t_i}}[5]

 {Z_{Assets}}が取引所の資産の下限値であることを証明するのに、取引所は[1], [3], [5]を満たす以下の数量の知識を証明する。

 {s_i \in \{ 0, 1 \} および、v_i, t_i, x_i \cdot s_i \in \mathbb Z_q}[6]

この証明により {s_i = 1}の時、取引所が公開鍵 {y_i}に対応する秘密鍵 {x_i \in \mathbb Z_q}を知っていることを検証者に確信させる。

取引所はΣプロトコルを利用した以下のProtocol 1を使って[6]の知識を証明する。

f:id:techmedia-think:20171229232223p:plain

プロトコル1自体は対話型のプロトコルになっているけど、これはFiat-Shamirヒューリスティックというのを使用すると非対話型にできるみたい。

プロトコル2負債の証明

まず顧客毎に顧客の一意な情報(ユーザー名、メールアドレス、口座番号など)とランダムに選択したnonceを使って顧客毎のコミットメントCIDを生成する(※異なる顧客に同じエントリーを与えられないよう顧客毎の一意な情報からCIDは生成される)。

 {CID = H(username || n)} (※Hはハッシュ関数

全顧客のCIDとその残高及び、残高のrange proofを持つ、債権者リスト(LiabList)を作成する。この債権者リストには取引所が顧客数を秘匿するため残高0のダミーの顧客が含まれている場合もある(残高があるダミー顧客を追加しても良いが、追加した分債務は増える)。

債権者リストは大まかに以下のようにして作られ、できたリストを公開する。

  1. 顧客の残高に対するPedersen Commitmentを作成する。この時残高をm-bitの二進数で表す(mは {m = \lceil lg_2 \, MaxBTC \rceil}で計算)。
  2. 1で計算した残高の各bit毎にPedersen Commitmentを作成する。
  3. 各顧客ごとに、取引所がPedersen Commitmentに使用したランダム値と残高の各bit値を知っていることを証明=range proofを生成する。
  4. 顧客の固有情報とnonceを使ってCIDを計算する。
  5. 顧客分↑を計算したら、全顧客分の債権リスト = <CID, 残高の各bit値のリスト, ゼロ知識>, ...を生成し公開する。

残高をm-bitの2進数にしてるのが不思議だが、おそらく残高をオーバーフローさせてマイナス残高を設定できないようにするためと思われる(マイナスの残高が加わると総負債が減って見えてしまう)。各bitは0か1かのどちらかであり、それを証明するのにステップ3でrange proofを作っているのか?

各顧客は以下の手順で自分の残高が正しいか検証することができる。

  1. 取引所にログインして、今回の使用されたCIDのnonceの値と、残高のPedersen Commitmentを作成するのに使われたランダム値を取得する。
  2. 1のnonceを使って今回のCIDを計算し、それが公開されている債権者リストの中にあるか確認する。(リストの中に無い場合は取引所が不正を働いていることになる)
  3. 債権者リストの中に自分のデータがあれば、自分の債権リストの自分のデータの残高の各bit値のリストが正しい残高のコミットメントになっているか検証する。

基本的に顧客が確認できるのは自分の残高が間違っていないかということで、債権者リストの他の顧客のデータを見たからといって他の顧客の残高が分かるわけではない。

これらの具体的な計算が以下のProtocol2↓

f:id:techmedia-think:20171231134739p:plain

そして債権者リストのすべての 残高の各bit値のリストを合計すると、総負債額へのコミットメント {Z_{Liabilities}}が計算できる。

債権者リストの拡張

債権者リストのCIDと残高へのコミットメントをリーフとしたマークルツリーを構成することで負債の証明を拡張することもできる。ツリーの内部ノードは2つの子ノードのハッシュとそれらの残高の合計のコミットメントが含まれるようになる。そうやって計算したマークルルートには全顧客の残高の合計へのコミットメントが含まれる。各顧客は自分の残高からマークルルートまでのパスが提供されれば検証が可能だ。このツリーを生成する場合、取引所の証明の生成時間が2倍になるため、オプションとされている。

プロトコル3 支払能力の証明

プロトコル1で総資産額へのコミットメント {Z_{Assets}}が計算され、

プロトコル2で総負債額へのコミットメント {Z_{Liabilities}}が計算されたので、

 {Z_{Assets - Liabilities}}

が0へのコミットメントであれば、総資産額と総負債額はイコールであることになり、取引所に支払能力があることを証明できるということみたい。(hの指数はランダム値なのにこの計算で0へのコミットメントになるというのがイマイチしっくりこない。。)

びったり同額になるということはなく余剰金が発生するケースも考えれる。その場合、余剰金へのコミットメント {Z_{Surplus}}を作成し(当然range proofも一緒に作る。)

 {Z_{Assets - Liabilities - Surplus}}

が0へのコミットメントか確認する。

制限事項

  • Provisionsはある時点における支払能力の証明を提供するのであって、その後の取引所の行動を含め、顧客の資産を確実に保護するプロトコルではない。
  • Provisionsでは公開鍵で口座の所有権を管理しているので、一度も使用されたことのないP2PKHのアドレスやP2SH、複雑なマルチシグなどのアドレスタイプについてはサポートしていない。基本的に取引所はP2SHのマルチシグでコインを管理していることが多いと思うので、実際に導入する際はP2SHベースのアドレスタイプをサポートする拡張が必要になる。
  • ProvisionsのプロトコルにFiat-Shamirヒューリスティックを利用することで非対話型のプロトコルになるが、この場合trusted setupが必要になる。trusted setupはしたくないので、将来的にzk-SNARKsなどを利用したproof of solvencyを模索してる模様。

というのがProof of Solvencyのプロトコルの概要みたい。

この他に悪意ある取引所が結託して取引所間で資産のアドレスを共有する結託攻撃へのアプローチや、総資産へのコミットメントを作成する際の匿名セットの選択方法など、詳しい内容はホワイトペーパー参照。