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のプロトコルの概要みたい。

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

Proofs of Proof of Work

Scaling Bitcoin 2017のFlyClientの内容を追っていったら前提としてNiPoPoWs(Noninteractive-Proofs-of-Proof-of-Work)→ PoPoWs(Proofs of Proof of Work)と関連研究が続くので、まず最初にProofs of Proof of Workのプロトコルについて調べてみる。

Proof of Workの検証

Bitcoinブロックチェーンでフルノードはジェネシスブロックから全てのブロックをダウンロードし、そのProof of Workが正しいか検証をすることで正しいチェーンであることを確認する。接続先のノードが偽の情報を流すことも考えられるため、複数のノードと接続し、接続先のノードによって異なるブロックチェーンが返ってくるケースでは、よりProof of Workが行われている方(長いチェーン)を正しいチェーンとして採用する。

SPVノードではブロック全体をダウンロードすることは無いが、ブロックヘッダを全てダウンロードし同様の検証を行う。これらの検証は最もProof of Workが行われたチェーンを検証していると言っても良い。ブロックヘッダのデータサイズは80バイトと小さいが、そのデータ自体は今後も線形に増えていく。

ノードを初回起動し最新のブロックを入手するまでブロックデータをダウンロードするIBD(Initial Block Download)では、各トランザクションの検証や正しいProof of Workが行われているかの検証にCPUリソースを消費し、チェーンが長くなるほどのそのリソース使用量と時間がかかるようになっており、IBDをいかに速くするかは重要な課題の1つになっている。基本的には各ソフトウェアがチェックポイントを設け、そこのブロックまではこういった検証をスキップすることでIBDを高速化する方法が採用されており、以前よりも高速にIBDが行えるようになっているが、これは同時にソフトウェアへのメンテナーへのトラストポイントが出来ているとも言える。

フルブロックをダウンロードしないSPVはフルノードに比べるとその検証は、ジェネシスブロックから最新ブロックまでチェーンのProof of Workの正しさを検証するだけなので比較的軽い処理ではあるが、今後もブロックが線形に成長していくことを考えると、より効率的なProof of Workの検証が求められる。このプロトコルを提案しているのがAggelos Kiayiasらによる「Proofs of Proofs of Work with Sublinear Complexity」というホワイトペーパーだ↓

http://fc16.ifca.ai/bitcoin/papers/KLS16.pdf

今までは各ブロックが前のブロックのハッシュを参照するハッシュチェーンを形成することでブロックチェーンを構築しており、それを辿ってチェーンの有効性を検証していたが、この仕組みをinterconnected blockchainと呼ばれる仕組みに変える。

※ 既存のBitcoinプロトコルのままではできないので、実現する場合はプロトコルの拡張やさらなる分析が必要。

Interconnected Blockchain

基本的にブロックヘッダを全てダウンロードしてProof of Workを検証する現在の方法の計算量はチェーンの長さに対して線形になるが、Proofs of Proof of Workではチェーンの長さに準線形な計算量で済むよう設計されており、既存のSPVと比べてより効率的で軽量なSPV検証を可能にする。

線形に増えていくブロックヘッダを全て計算するから計算量が線形になるのであって、間引いた状態でもProof of Workの正しさを検証できれば計算量を減らすことができる。このとき間引いてできるブロックチェーンをinterconected blockchainと呼ぶ。

ではどうやってinterconnected blockchainを構築するのか?

基本的にマイニングというのは予め定められたターゲット以下のハッシュ値を見つける競争で、 {H(w)<T} を満たすブロックを作ること(Hはハッシュ関数でTはターゲット)になる。マイニングの成功条件はターゲット以下であることだけど、見つかるハッシュはTに近い値だったり、T/2以下だったりT/3以下だったりT/4以下だったりする。そこで {T / 2^{i}}より小さいハッシュが見つかったときに、そのハッシュを深さ(i)と一緒にピックアップしそれらでinnerchainを形成する。

例えば以下のような11個のブロックがある場合(1はジェネシスブロック、ブロック4,7,9がT/2(i = 1)より小さいハッシュを持ち、ブロック7がT/4(i = 2)より小さいハッシュを持つ)

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

深さ1の {innerchain_1}はブロック1,4,7,9で構成され、深さ2の {innnerchain_2}はブロック1,7で構成される。

また各ブロックは現状のブロック構造に加えて新たにinterlinkと呼ばれるデータ構造を加えることになる。これはブロックのポインタのリストで {interlink = \langle s_0, ..., s_l \rangle}のように表す。ここで {s_0}ジェネシスブロックへのポインタで、 {s_i} {T/2^{i}}より小さいハッシュ値を持つ前のブロックへのポインタとなる。

↑の11個のブロックにそれぞれのブロックが持つinterlinkを割り当てると以下のようになる。

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

ブロック4までは {T/2}より小さいハッシュは存在しないので、interlinkは<1>になる。ブロック5からはブロック4が {T/2}より小さいハッシュを満たしているのでinterlinkは<1, 4>となる。ブロック7で {T/4}のブロックが見つかる。ここでブロック8は<1,4,7>になるかと思うけど、interlinkの2つめの要素( {s_1})は {T/2}より小さいハッシュの条件を満たす直近のブロックなので7になり、3つめのinterlinkの要素( {s_2})は {T/4}より小さいハッシュの条件を満たす直近のブロックなのでこれも7で、結果<1, 7, 7>となる。ブロック9で {T/2}より小さいハッシュを満たすブロックが見つかると {s_1}を満たす最新が9になるのでブロック10からのinterlinkは<1, 9, 7>に変わる。

このように {T/2^{i}}より小さいハッシュをもつブロックで構成するブロックチェーンをInterconnected Blockchainと呼んでいる。

Interconnected Blockchainを使ったPoWの証明

従来のSPVノードがチェーン全体のPoWを受け取るのに対し、このプロトコルでは軽量ノードはフルノードから {(\mathcal X, \pi)}のペア(PoWの一部)を受け取る。ここで {\mathcal X}はフルノードのローカルチェーンCの右端kブロック分に相当するブロックチェーンの断片で、 {\pi}はローカルチェーンCからkブロック分取り除いたチェーン {C^{\lceil k}}の、長さが少なくともm(mはセキュリティパラメータ)あり深さが一番深いinnnerchainを指す。

軽量ノードはローカルチェーン {C_A} {C_B}を持つフルノードA, Bからそれぞれ {(\mathcal X_A, \pi_A)}のペアと {(\mathcal X_B, \pi_B)}のペアを受け取り、どちらが正しいProof of Workが行われたチェーンか検証する。

  1.  {\pi_A} {\pi_B}の長さが少なくとも(セキュリティパラメータ)mより長いかチェックする。mより短ければこの時点でリジェクト。
  2.  {\mathcal X_A} {\mathcal X_B}の中に共通のブロックが無いかチェックする。共通のブロックが見つかり、かつ {\mathcal X_A} {\mathcal X_B}が異なる場合は直近kブロックで {C_A} {C_B}がフォークしていることになる。この場合簡単で {\mathcal X_A} {\mathcal X_B}のどちらが長いかチェックし、長い方を正しい証明と判断すれば良い。
  3. 2で共通のブロックが見つからなかった場合、 {\pi_A} {\pi_B}から、どちらの証明がより沢山の計算をしたProof of Workか判定する必要がある。この場合AとBで共通のprefixを見つける必要があり、AとBに深さが小さいチェーンについて追加の問い合わせが必要になる可能性もある。

3の追加検証についてはホワイトペーパー参照。

正直なノードと悪意あるノードにそれぞれ繋がっている場合、↑のように共通のブロックを持つ断片があればどちらのPoWが正か判定できるが、共通のブロックが無い場合が悪意あるユーザーの攻撃ポイントになり、深さが0になるまで軽量ノードに計算と問い合わせを余計にさせるような攻撃が考えられる。 ただ実際に軽量ノードにこういった計算量を増やすためには、悪意あるノードはより計算リソースを投入して沢山の偽ブロックを作成する必要があり、そこまでして攻撃が成功する確率も無視できるレベルに低いためホワイトペーパーの性能分析ではそこは省かれている。

データ量と計算量

データ量

Interconnected Blockchainでは各ブロックにinterlinkを新たに追加する必要があり、この分データ量が増える。ホワイトペーパーでは以下のようにT=2200で安定してる際に、interlinkのサイズは(チェーンの長さ)nの対数で安定するとしている。ホワイトペーパーのFigure 2参照。

マークルツリーを使ったinterlinkの圧縮

interlinkはブロックのポインタのリストなので、これをマークルツリーを使って圧縮する方法もある。この場合、ブロックに追加するのはこのマークルツリーのルートハッシュのみで固定サイズになる。

計算量

複数のフルノードから受信したkブロック分の {\mathcal X}に共通のブロックが存在していれば、追加の問い合わせをフルノードにする必要はない。この場合、軽量ノードは受信した証明 {\pi}のサイズに比例した検証を行う必要があり、その計算はセキュリティパラメータをm、チェーン全体の長さをnとした場合、O(m log n)と準線形になる。またマークルツリーを使ってinterlinkを圧縮した場合、これはO(m log log n)に改善される。

所感

既存のSPVはチェーン全体のPoWを送信して検証するのに対し、このホワイトペーパーでは定量サイズのPoWのサンプルを使って検証している。その仕組みのベースになってるのがターゲットTよりさらに小さい( {T/2^{i}}未満)ハッシュを集めて構成するinnerchain。より小さいハッシュを使うアイディア自体はBitcoin Forumに投稿されたもの。こういう形でチェーンの検証をスキップする仕組みが成立するのは面白い。

ただ定理含めて理解できてないところも多いので、その辺は個人的にちゃんとした理解のための課題が残る。

Proofs of Proof of Workのホワイトペーパーのプロトコルは、ターゲットTが動的に変化するケースの分析や、PoWの検証が場合に {\pi}を使ったものに及ぶと必要に応じて相手のノードに追加の問い合わせが必要となる対話型のプロトコルといった課題がある。後者の部分を改善したのがNiPoPoWs(Noninteractive-Proofs-of-Proof-of-Work)のプロトコルになるので、その内容についてはまた今度見てみたい。

以下は、ホワイトペーパーのざっとした訳↓(正確な内容はホワイトペーパー参照)

イントロダクション

Nakamotoによって導入されたBitcoin及び、同じコードベースを使って開発された他の多数の分散型暗号通貨は、ブロックチェーンベースの取引台帳が中核になっている。これらのシステム台帳は、トランザクションがブロックに編成された分散データ構造を持つ。ブロック自体はハッシュチェーンを形成し、各ブロックにはProof-of-Workパズルが関連付けられ、1つ前のブロックを指し示す。有効なブロックチェーンは分散台帳をサポートするクライアントソフトウェアにハードコードされたジェネシスブロックに根ざしている。

ブロックチェーンはマイナーと呼ばれる動的に変化するプレーヤーのセットによって維持されている。各マイナーの主な仕事はproof of workを解決し次のブロックを見つけることだ。トランザクションブロックチェーンに追加する際に検証される。特定のトランザクションの確実性は、ブロックチェーンの深さと関連付けられる。ブロックチェーンのより深い場所にあるトランザクションほどそのトランザクションの確実性は増す。これはもともと正直なプレーヤーは一致して行動し敵対者は特定の戦略に従うという単純化されたモデルだった。正直なプレーヤーが分散し敵対者がこれを利用する可能性がある状況におけるセキュリティは、その後正式に検討されThe Bitcoin Backbone Protocol: Analysis and Applicationsで証明された。この後の研究では2つの特性が紹介された。共通のプレフィックスとチェーンの品質だ。パラメータkで圧倒的な確率で正直なプレイヤーがブロックチェーンの同じプレフィックスに同意することが示された。kブロック経過したチェーンは正直なプレイヤーによっと生成されたブロックを一定の割合含むだろう。これらの2つの特性は、台帳内のトランザクションは永続的で台帳自体が活性的である、つまり敵対者が新しいトランザクションを無期限に抑止することは不可能であることを示している。

この研究ではsimplified payment verification(SPV)の問題について研究する。Bitcoinのホワイトペーパーで紹介されたこの問題は台帳の最近のトランザクションを調べたい検証者を考慮している。検証者はインプットとしてトランザクションの識別子を持つ。検証者はこの情報だけでそのトランザクションが高い確率で台帳に含まれていることを検証し、高い確率でそのトランザクションが台帳に残っていることを確かめたいと考える。上記に基づき、以下のようなSPV検証を簡単に実装することができる。検証者はネットワークに問い合わせ、直近kブロックを除くほとんどのブロックのブロックヘッダを含むさまざまなブロックチェーン(悪意あるユーザーによって作られたチェーンを含め)を受け取る(このような通信は“SPV proofs”と呼ばれる)。検証者は受信したチェーンの完全性を検証し、最も多くの作業をしているチェーンを1つ選択する。最後に探しているtxが深さkで見つかったらトランザクションは有効であると結論付けることができる。このSPVのオペレーションは、全てのトランザクション履歴を受信して検証する必要がないためフルノードを実行するより効率的だ。

上記の解決先の重要な考察は、ブロックチェーンの線形の計算量以下に改善することが一見不可能な点だ。確かに検証者が準線形の計算量しか許可されないようなケースでは、受信したブロックチェーン内の全てのproof of workが有効であるか検証することはできない。この方法では与えられたブロックチェーンの断片しか確認することができず、攻撃者がジェネシスブロックと実は関連が無いが一見有効そうなブロックチェーンの断片を事前に準備することで、攻撃者に潜在的な攻撃の機会を作るかもしれない。

Our Results

本研究では、ブロックチェーンの長さに準線形な計算量を持つproofs of proof of workを構築する方法を提示する。これらの証明はフルSPV検証と比べて実質より効率的で軽量なSPV検証を可能にする。我々の解決策では現在のBitcoinのコードベースの変更が必要になる。これにより各ブロックには小さなオーバーヘッドが発生する。これはブロックチェーンの長さの対数を超えることはなく、ブロックチェーンを単一のハッシュに圧縮することができる。これによりinterconnected blockchainと呼ばれる特別なタイプのブロックチェーンが誕生する。

我々の解決方法では、軽量な検証者は( {\mathcal X, \pi})のペアを受け取る。ここで {\mathcal X}は送信者のチェーンの右端kブロックに相当するブロックチェーンの断片で、 {\pi}はプルーニングされたチェーンが表す( {C^{\lceil k}}で表される)proof of workの証明である。証明 {\pi}を構築するには以下の仕組みを使う。

ブロックチェーン内の各ブロックは、不等式H(w) < Tを満たすように作られた値wに対応するproof of workに関連付けられていることを思い出して欲しい。ここでHハッシュ関数Bitcoinの場合はSHA-256)で、Tはターゲット計算関数で与えられる難易度のターゲットである。

我々の新しい仕組みは次のように動作する。通常より小さいハッシュを持つブロックが生成される度に、次のブロックでより深いチェーンの続きとしてマークする。これを深さiのinnerchainと呼ぶ。iはH(w) < T/2i を維持する最大の整数。具体的には、各ブロックはポインターのベクトルを運ぶ(これは複数のレベルにまたがるブロックチェーン内の標準的な逆方向リンクを拡張すると考えることができる)。このように変更されたブロックチェーンでは、ブロックは {interlink = \langle s_0, ..., s_l \rangle}と表されるポインターのベクトルを持つ。ここで {s_0}ジェネシスブロックを指し、i = 1, . . . , lと続く。 {s_i}は前のブロックを指し、 {\mathit T / 2^{i}}より小さいハッシュ値を持つ前のブロックを指す。lブロックチェーン内のハッシュがT /2lより小さい最大の整数であることに注意する {s_l}は最新のそのようなハッシュのポインタである)。

プルーフ {\pi}の構築方法は以下の通り。送信者はローカルチェーンCからk-suffixを取り除きそれを {\mathcal X}とする。次に、残りのプレフィックスである {C^{\lceil k}}について、少なくとも長さがmmはセキュリティパラメータ)ある最も深いinnerchain {\pi}を探す。この ( {\mathcal X, \pi}) のペアがプルーフとなり軽量な検証者に送られる。攻撃者が積極的に干渉しない楽観的なシナリオにおいては、軽量な検証者と証明者間で対話は必要無い。一般的な場合、攻撃者は唯一、軽量検証者と証明者との間の通信量を増加させる目的で、非常に小さいターゲットを持つブロックを生成するためにハッシュパワーを投入することが考えられる。そのようなケースでは軽量な検証者は完全な検証のため証明者とのさらなる対話を行う必要がある。

最後に軽量SPVプルーフのセキュリティの正式な取り扱いについて説明する。この議論はシミュレーションベースの議論である。軽量検証者のセキュリティは以下の声明で捉えることができる。軽量検証者向けのSPVプルーフを生成するどんな敵にとっても、同じ結果をもたらす通常のSPVに検証者むけのSPVプルーフを生成する敵が存在する。上記のセキュリティ条件をm内で圧倒的確率で確立する。mは軽量検証プロトコルのパラメータ。

我々の構成では、軽量検証者の計算量は楽観的なケースではO(m log n)で、これは簡単にO(m log log n)に改善できる。ここでnはマークルツリーを使用したブロックチェーンの長さ。

関連研究

ハッシュ値を使用する最初の提案はBitcoinフォーラムの投稿*1にあった。この投稿では、各ブロックに前のブロックのハッシュ値の半分未満のハッシュ値を有する最新ブロックへの単一back-linkを含めるための、Bitcoinプロトコルの変更が提案された。SPV Proofsでこのようなポインタを使用する可能性を含め、この変更に伴う潜在的なメリットについて議論された。

Bitcoin-development listに掲載された短い記事*2では、このアイディアはさらに、前の複数のブロックへのさまざまなバックリンクを含むデータ構造含むものとして提案された。正確なデータ構造は記述されておらず、最も適切なデータ構造を決定するのにはさらに研究が必要であることが示唆された。コンパクトなSPV proofsを構築する可能性やBitcoinとサイドチェーン間の「対称双方向ペグスキーム」の設計など多くのユースケースが議論された。この後者のコンセプトは、Enabling Blockchain Innovations with Pegged Sidechainsで定義されており、台帳の資産を1つのメインチェーン(Bitcoin)からペグしたサイドチェーンに転送することができる。サイドチェーンではブロックチェーンの設計に関する新しい機能を試すことができ、ペグすることでBitcoinブロックチェーンからこれらの代替ブロックチェーンへの流動的な資産の移動を可能にすると言われている。ペグのオペレーション自体は、メインチェーン上でサイドチェーンにおけるSPV proofによってのみアンロック可能な特殊なアウトプットに資金を移動するトランザクションを指す。これにより資金をメインチェーンからサイドチェーンへ移転させることができ、所有者が望めばメインチェーンに資金を戻すことも可能だ。効率的なSPV proofを構築することはこの仕組において重要な側面で、上記の短い記事に沿った提案が上記ホワイトペーパーに記載されている。敵対者がSPV proofの仕組みを利用する可能性も認識されており、明示的なデータ構造やproofの構築アルゴリズムの結論や正式な分析などはないが、いくつかの対策について議論されている。

最後に、SPVノードの検証に関連するBitcoinの変更は、ブロックチェーンのフルノードに影響を及ぼさないので、ブロックチェーン選択のためのGHOSTルールやInclusive Block Chain Protocolsのようなチェーン選択と報酬の仕組みの変更とは異なる性質を持つ。

序文

ホワイトペーパーではBitcoinのバックボーンプロトコルの表記方法に従う。以下にいくつかの基本的な表記方法と用語について紹介する。

  •  {G(.), H(.)} {\{ 0, 1 \}^{K}}のアウトプットを持つ暗号学的ハッシュ関数
  • ブロックBは {B = ⟨s, x, ctr⟩}の形式で表現される。ここで {s \in \{0, 1\}^{K}} {x \in \{0, 1\}^{*}} {ctr \in \mathbb N}
  • ラウンドはネットワーク内の全関係者が同期して互いのメッセージを入手するまでの期間。メッセージのスケジューリングは敵対者によって制御される。さらに、各ラウンドにおいて、敵対者は任意の数のメッセージを生成し、それを選択的に関係者に配信できる。
  • チェーンCの右端のブロックはhead(C)で、 {C^{\lceil k}}はチェーンCの右からkブロック取り除いたもの。 {head(C) = ⟨s, x, ctr⟩}で前のブロックが {⟨s', x', ctr'⟩} {s = H(ctr7, G(s', x'))}を保持する。一般的にすべてのブロックは前のブロックへの参照を有し、このためすべてのブロックはチェーンを形成する。
  • ブロックヘッダは {⟨ctr, G(s, x)⟩}として定義できる。
  • proof of workは {ctr : 0 \leq ctr} <  {2^{32}} の範囲で {H(ctr, G(s, x))} <  {T}となる値を見つけること。 {T \in \{0, 1\}^K}はブロックのターゲット。
  • xは情報がブロックに格納されていることを示す値。Bitcoinプロトコルの場合この情報は一連のトランザクションでマークルツリー形式で構成されている。

Interconnected Blockchains

proof of workのプルーフを生成するため、ローカルチェーンCを持つ証明者は {\mathcal X}をそのローカルチェーンCのk-suffixに設定しプルーフ {\pi}を計算して {(\mathcal X, \pi)}のペアを生成する。プルーフ {\pi}はチェーン {C^{\lceil k}}の一部のブロックの集合を構成し、それは以下に詳述する方法で収集される。

プルーフ {\pi}プルーフの深さである整数 { i \in \mathbb N}に関連付けられる。プルーフに含まれるブロックは {innerchain_i}と呼ばれる特別なタイプのチェーンによって決まる。

定義1

インデックス i > 0によってパラメータ化された {innerchain_i}は、各ブロック {B = ⟨s, x, ctr⟩} {H(ctr, G(s, x))} <  {T/2^{i}}を満たす特徴を持つチェーンCから派生した有効なチェーンである。

 {innerchain_i}では、各ブロックは親チェーンCのターゲットTを持つ {2^{i}}ブロックと同程度のproof of workを表していることが直感的に分かる。その結果、プルーフ {\pi}がmブロックで構成されている場合、 {innerchain_i}はターゲットTの {m \cdot 2^{i}}ブロック分のproof of workを表す。

我々のシステムでは、プルーフを生成するために証明者は {C^{\lceil k}}からi > 0の {innerchain_i}を抽出すべきだ。これはすべての {i \in \mathbb N}に対し、  {T/2^{i}}より小さいハッシュを持つすべてのブロックがチェーンを形成すべきであることを意味し、interconnected blockchainという概念につながる。

 {T/2^{i}}より小さいハッシュを持つすべてのブロックは、 {T/2^{i}}より小さいハッシュを持つ前のブロックへのポインタを必要とする。これは通常のBitcoinブロックチェーンには存在しないため、Cの各ブロックに一連のポインタを適切に変更する必要がある。interlink[]と呼ばれる各ブロックへのこのデータ構造の追加はinterconnected blockchainを生み出す。interconnected chainのグラフィカルな説明をFigure 1に示す。

f:id:techmedia-think:20180104175422p:plain
Figure 1: 深さ1のinnerchain(ブロック(1, 4, 7, 9)で構成される)と深さ2のinnerchain(ブロック(1, 7)で構成される)を含む11個のブロックを持つinterconnected blockchainの図。各ブロックのinterlinkベクトルの値も表示されている。

各ブロックBに含まれるinterlinkのデータ構造は動的で以下に正式に定義する。ブロックBは {B = ⟨s, x, ctr, interlink⟩}と、ブロックヘッダは {⟨ctr, G(s, x, interlink)⟩}と定義される。

定義2

interlinkは各ブロックに含まれるベクトルで、すべてのi > 0について、, interlink[i]は {\mathit T / 2^{i}}より小さいハッシュ値を持つチェーンC内のBの前のブロックハッシュである。interlink[0]はジェネシスブロックのハッシュとなる。

ベクトルの長さは、チェーンCに存在するブロックの種類に依存する。 {B = ⟨s, x, ctr, interlink⟩}がチェーンの先頭で、 {B' = ⟨s', x', ctr', interlink'⟩}が前のブロックとすると、この後説明するアルゴリズムで更新された後のinterlinkinterlink'は等しくなる。

3.1 interlink-Updateアルゴリズムの説明

このアルゴリズムの目的は、interconnected chainを適切に形成するのに必要な動作を決定することだ。新しいブロックをマイニングする時は、使用される適切なポインタのセットを決定しなければならない。sで表される前のブロックのハッシュが与えられると、アルゴリズムは以下を実行する。

  •  {s = H(ctr', G(s', x', interlink′'))} <  {T/2^{i}}を満たすiの最大値を見つける。
  •  {i - i'}の要素を追加してinterlink′を拡張する。 {i'}の値はsizeof(interlink′) (only if i′ < i)と等しい。
  • interlink[1],...,interlink[i]に {H(ctr', G(s', x', interlink')) = s}を割り当てる。

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

4. 準線形のProof of Workの証明

4.1 証明者(Proover)の説明

ローカルチェーンCを持つ証明者が軽量な検証者(Verifyer)から右端のkブロックを要求するリクエストを受け取ると、証明者はConstructProofアルゴリズムを使ってチェーン {C^{\lceil k}}のProof of Workの証明 {\pi}を構築する。

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

このアルゴリズムのインプットは {C^{\lceil k - 1}}で、そのアウトプットは {innerchain_i = \pi}である。ここでiは最大のiで、チェーン {C^{\lceil k}}には {\mathit T / 2^{i}}より小さいハッシュ値を持つ少なくともm個ブロックが存在する(mはセキュリティパラメータ)。ConstructProofアルゴリズムは(以下に説明する)その次にConstructInChainアルゴリズムを呼び出す。

このアルゴリズムは(key, value)のペアを格納するデータ構造であるハッシュテーブルを使用する。このケースではハッシュテーブルにハッシュ値を持つブロックを格納する。ConstructInChainアルゴリズムはチェーンCとiをインプットとし、そのアウトプットはチェーン {C^{\lceil 1}}内で {\mathit T / 2^{i}}より小さいハッシュ値を持つ全ブロックのチェーンである。

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

軽量な検証者(Lite Verifier)の説明

軽量な検証者がチェーン {C_A}とチェーン {C_B}を持つ証明者AとBからそれぞれ {(\mathcal X_A, \pi_A)} {(\mathcal X_B, \pi_B)}を受け取ったとする。目的はどちらの証明が最もproof of workを行ったチェーンのものか見つけることだ。

  • 一般性を失うことなく、 {\pi_A = innerchain_{\mu}}とするとそのブロックのハッシュ値 {T' = \mathit T / 2^{\mu}}より小さい。
  •  {\pi_B = innerchain_{i + \mu}}とするとそのブロックのハッシュ値 {\mathit T / 2^{i + \mu} = \mathit T' / 2^{\mu}}より小さい {(i \geq 0)}

まず軽量な検証者は {\pi_A} {\pi_B}の長さがそれぞれジェネシス抜きでmより長いかsuffixの長さがkかどうかそれぞれ確認する。プルーフがこの特性を満たさない場合、無効なプルーフとしてリジェクトされる。

続いて、 {\mathcal X_A} {\mathcal X_B}の中に共通のブロックxがないか確認する。この確認はどっちのチェーンのproof of workがより容易か見つけるために行う。具体的には直近kブロックで {C_A} {C_B}の間にフォークが発生していることを意味する。そのため、軽量な検証者は両者のうちProof of Workがより良い方(同じTに対してxの後により多くのブロックがある方)のsuffixを選択する。

suffixの中に共通のブロックが無い場合は、 {MaxChain [\pi_A, \pi_B ]}アルゴリズムを実行し、どっちのプルーフが最も優れたProof of Workか決定する。このアルゴリズムはAとBにさらなる相互作用を求め、以下のように動作する。

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

MaxChainアルゴリズムはRemoveCPhighとRemoveCPlowという2つのサブプロシージャを使用する。 {(\pi_A, \pi_B)}をインプットとするRemoveCPlowアルゴリズムは、共通のブロックをプルーニングし、 {\pi_A^{\prime}} {\pi'_B}を共通のブロックの無いプルーフにセットし、 {(\pi_A, \pi_B)}の中で最も直近のブロックにbをセットする。

 {(\pi_A, \pi_B)}をインプットとするRemoveCPhighは、 {\pi_B}で省略された {\mathit T / 2^{\mu}}より小さいハッシュのブロックのチェーンについてBに問い合わせる。RemoveCPhighは {(\pi_A^{\prime}, \pi'_B, b)}を返す。 {\pi_A^{\prime}} {\pi_B^{\prime}}は共通のprefixが無いプルーフで、bは {C_A} {C_B} {\mathit T / 2^{i + \mu}}より小さいハッシュ値を持つ最も最新の共通のブロックだ。より詳細には以下のように動作する。

  • 証明は2つの配列にそれぞれ格納されている前提で、このアルゴリズム {\pi_A}内のブロック {\pi_B [1]}を探し、 {\pi_A}内にはない {\pi_B [i']}を見つけるまで続ける。 {\pi_B [i' - 1]} {\pi_A}に含まれるので {\pi_A[j] = \pi_B[i' - 1]}となる。
  •  {\pi_B [i' - 1]}から。 {\pi_B [i']}の間に {\mathit T / 2^{\mu}}より小さいハッシュ値を持つブロックの配列VをBに問い合わせる。Bから配列Vが返ってこない場合RemoveCPhighは失敗する。
  •  {\pi_A [j']} {V [j' - 1]}とは異なるような最小の {j′ \geq j + 1}を探す。
  •  {\pi_B^{\prime}}は最初の {i' - 1}ブロックが無い {\pi_B}で、 {\pi_A^{\prime}}は最初の {j' - 1}ブロックが無い {\pi_A}である。
  •  {b = \pi_A [j' - 1]}
  •  {(b, \pi_A^{\prime}, \pi'_B)}を返す。

続いてMaxChainのアルゴリズムについて説明する。分岐した {\pi_A, \pi_B}が与えられると、アルゴリズムはsuffixが十分長い(長さはセキュリティパラメータにmより決まる)限り、最も多くのProof of Workを行ったプルーフを選択する。ただ、アルゴリズムがどちらか決定できない場合は、より小さい深さのプルーフをAとBに要求し、必要に応じてレベル0まで再帰的に行うことでパラメータmとは独立して決定する。これらの再帰ステップの途中で通信ノードA、Bのうち1つが、そのプルーフのサポート(軽量ノードが要求した追加ブロックを提供するの)に失敗するとMaxChainアルゴリズムはもう1方のノードのチェーンが正しいチェーンであると結論付ける(もしくはノードがリクエストに応答しない場合は失敗する)。より詳細には以下のように動作する。

  • 最初にアルゴリズムはRemoveCPlowを呼び出して、プルーニングされたsuffixを取得する(これは対話を必要としない)。続いてそれを {i > 0}かチェックする。このケース時点でプルーフは異なる深さを持つので、アルゴリズム {\pi_B^{\prime}.pow \geq  \pi_A^{\prime}.pow}と同時に {\pi_B^{'}.length \geq m}かチェックする。この2つの条件が成立する場合、軽量な検証者は {\pi_B}を選択する。そうでない場合アルゴリズムプルーフ {\pi_A, \pi_B}から共通のprefixを見つけるためRemoveCPhighを使用する(これはBとの対話が必要になる)。
  • 次にアルゴリズムは、どちらのプルーフがよりProof of Workを行っているかチェックする。 {\pi_B^{'}}の場合は少なくとも長さm、 {\pi_A^{'}}の場合は少なくとも {2^{i} m}の長さがあれば最良なProof of Workのプルーフと判断される。この場合、セキュリティパラメータmに依存した決定がされることに注意すること。
  • 最良のProof of Workであると判断するのにプルーフが十分でない場合、アルゴリズムは共通のprefixを使用せず、BもしくはAとBの両方にチェーン {(C_A^{\lceil k} or \, C_B^{\lceil k})}のより深い部分のプルーフを問い合わせ、それを再帰的に継続する。bをルートとするチェーン {C_{B}^{\lceil k}} {T' = \mathit T / 2^{y}}より小さいハッシュ値を持つプルーフのBからのリクエストを表すのに {RequestB[b, y]}を使用する。同様に、 {RequestA[b, y]}プレイヤーAに対して同じように機能する。

最終的にアルゴリズムは、十分長いもしくは、proof of workの量のみに基いて決定される(実際のターゲットTが使用される)深さ0に達する分岐suffixを入手する。これによりどちらが正しいプルーフかが決まり、軽量な検証者は別の比較やプロセスを終了する。

効率解析

このセクションでは、プルーフシステムの効率解析を提示する。最初にスペースの使用量、すなわちinterconnected blockchainのデータ構造により全ノードのローカルストレージに必要とされる拡張について説明する。次にプルーフを送信するために必要な通信と軽量な検証者の検証の計算量について分析する。

スペースの使用量

最初にinterconnected blockchainの各ブロックで唯一の加算ベクトルであるinterlinkの適切な上限を示す。

定理1

 {T = 2^{f}}より小さいハッシュ値を持つブロックで構成されるチェーンCの長さをnとする。次に動的ベクトルであるinterlinkの予想されるサイズは {f - \sum_{i=1}^{f} (1 - \frac{1}{2^{i}})^{n}}

証明。各ブロック {C[j]}に対応する離散確率変数を {X_j \in \{0, ..., f\}}と定義すると、

 {X_{j} = i \iff \frac{T}{2^{i+1}} \leq H_{B} < \frac{T}{2^i}, i \in  0, ..., f - 1 }
 {X_j = f \iff 0 \leq H_B < \frac{T}{2^f}}

{H_B} {C[j]}ハッシュ値。)

各チェーンのブロック{H_B}ハッシュ値は{0, ..., T − 1}の一様な離散分布となる。そのため

 {P_r (X_j = i) = P_r (\frac{T}{2^{i+1}} \leq H_B < \frac{T}{2^i}) = \frac{1}{2^{i+1}}, i \in 0,...,f-1  }
 {P_r (X_j = f) = P_r (0 \leq H_B < \frac{T}{2^f}) = \frac{1}{2^f}}

結果、

 {\sum^{f}_{i=0} P_r (X_j = i) = 1}

次にinterlinkのサイズはY = max{X1, ..., Xn}の分布に従う。0 ≤ y < fの場合

 {P_r (Y \leq y) = (P_r (X_j \leq y))^n = (\sum^{y}_{i=0} \frac{1}{2^{i+1}})^n = (1 - \frac{1}{2^{y+1}})^n}
 {P_r (Y = y) = P_r (Y \leq y) - P_r (Y \leq y - 1) = (1 - \frac{1}{2^{y+1}})^n - (1 - \frac{1}{2^{y}})^n}

結果: {P_r (Y \leq f) = 1}かつ {P_r (Y = f) = 1 - (1 - \frac{1}{2^{f}})^{n}}となり

以下が成立する。

 {E(Y) = \sum^{f-1}_{y=0} y \cdot [ (1 - \frac{1}{2^{y+1}})^{n} - (1 - \frac{1}{2^{y}})^{n} ] + f \cdot [ 1 - (1 - \frac{1}{2^{f}})^{n} ] \\ = (f-1) \cdot (1 - \frac{1}{2^{f}})^{n} - \sum^{f-1}_{i=1} (1 - \frac{1}{2^{i}})^{n} + f \cdot [ 1 - (1 - \frac{1}{2^{f}})^{n} ] \\ = f - \sum^{f}_{i=1}(1 - \frac{1}{2^{i}})^{n}}

Figure 2は、現在のブロックチェーンの長さがnの範囲にありターゲットが2200で安定している場合、interlinkの数がnの対数であることを示している。

f:id:techmedia-think:20180106152743p:plain
Figure 2 : ターゲットT=2200の場合のブロックチェーンの長さを関数としたinterlinkのサイズ

マークルツリーを使ったinterlinkの圧縮

ブロック当たりのデータサイズを減らすのにマークルツリーを使ってinterlinkを圧縮する方法がある。より詳細にいうと、各ブロックにinterlink全体を格納するのではなく、interlinkでマークルツリーを構成しそのルートハッシュのみを各ブロックヘッダに格納する方法だ。この結果ブロックヘッダにinterlinkハッシュ値を順番にセットする必要はなくルートハッシュのみの追加ですむ。ConstructProofに必要な変更については簡単なので省略する。

5.2 通信と時間

プルーフ {\pi}のサイズについて分析する。ここでは敵対者が正直な関係者のプルーフを妨げるような深いフォークを作成していない=敵対者が送信するk-suffixに正直な証明者によって送信されたプルーフのsuffixで共通のブロックが存在する楽観的なシナリオにフォーカスする。正直な関係者はk-suffixより前にチェーンの一部が分岐していることはない(kはそれだけ圧倒的な確率を持つため)。このようなケースでは、軽量な検証者は証明者と余計なやりとりをすることなく最も実証されたproof of workのチェーンを選択することができる。従ってプルーフのサイズはConstructProofアルゴリズムのアウトプットになる。

軽量な検証者が証明者に尋ねたk-suffixを除いたローカルチェーンを {C^{\lceil k}}とし、チェーンの長さをn、セキュリティパラメータをmとする。まず最初に、 {C^{\lceil k}}のブロックが {\frac{T}{2^{i}}}より小さいハッシュ値を持つ確率が {\frac{1}{2^{i}}}になることを証明する。

ブロックBのハッシュ値 {H_B} {j \in \mathbb N} { j < T}で、 {P_r (H_B = j | H_B < T) = \frac{1}{T}}の場合

 {P_r (H_B < \frac{T}{2^{i}} | H_B < T) = \sum^{\frac{T}{2^{i}} - 1}_{j=0} P_r (H_B = j | HB < T) = \frac{\frac{T}{2^{i}}}{T} = \frac{1}{2^{i}}}

チェーン {C^{\lceil k}}ハッシュ値 {\frac{T}{2^{i}}}より小さいブロックの数は、パラメータ {(n, p_i = \frac{1}{2^{i}})}の二項分布に従う離散確率変数 {D_i}となり、その期待値は {E(D_i) = n \cdot p_i}

ConstructProofアルゴリズムのアウトプットが {innerchain_{i_0} = \pi}であることを思い出して欲しい。ここで {i_0} {C^{\lceil k}}内でハッシュ値 {\frac{T}{2^{i}}}より小さいmブロックを持つ最大のiである。結果としてアルゴリズムが返すプルーフの深さ {i_0}プルーフ {\pi}に含まれる( {D_i0}で示される)ブロックの数を調べる必要がある。

次の補助定理では、ConstructProofアルゴリズムが返すinnerchainの長さが最適値(約 {\log{\frac{n}{m}}})に非常に近いことを確認する。

補助定理1

プルーニングされた証明者のローカルチェーン {C^{\lceil k}}のサイズをnとする。 {n < T_m}とし {2^{i}m \leq n < 2^{i+1}}となるiを定義する。次に {P_r (D_{i-1} \leq m - 1) \leq exp(-Ω(m))}を保持する。

証明。 {n \cdot p_{i-1} = \frac{n}{2^{i-1}} \geq \frac{2^{i}m}{2^{i-1}} = 2m > m -1}であることを観察する。これから二項分布のチェルノフ限界によれば以下のようになる。

 {P_r (D_{i-1} \leq m - 1) \leq exp(-\frac{(np_{i-1} - (m - 1))^{2}}{2np_{i-1}}) \\ \leq exp(-\frac{1}{2/(2^{i-1})}) \cdot (n(1/(2^{i-1})) - (m-1))^2/n \\ \leq (- (2m - m + 1)^2 / 2^{3}m) \leq exp(- Ω(m))}

これで証明は完了となる。

この補助定理を利用して次にinnerchainの長さが実質的にmより大きくならないことを観察する。

補助定理2

 {n < T_m}とし、 {2^{i}m \leq n < 2^{i+1}m}となるiを定義する。 {P_r (D_{i-1} \geq 5m) \leq exp(-Ω(m))}とする。

証明。まず {2m/n \leq p{i-1} = 1/2^{i-1} < 4m/n}を観察する。 {X} {\mu} {\delta \in (0, 1]}を持つ二項分布であるとき、 {P_r [X \geq (1 + \delta \mu ] \leq exp(-\delta^{2}\mu/3))}の右端のチェルノフ限界を考えてみる。これは[tex: {P_r \[ D{i-1} \geq 5m \] \leq P_r \[ D{i-1} \geq (1 + 1/4) p{i-1} n \] \leq exp(-p{i-1} n/48) \leq exp(-m/24)}]に従う。

ここまでで、構築し軽量な検証者に伝達されるプルーフの効率を確立する定理を述べる準備ができた。

定理2

楽観的なケースにおいて、軽量な検証者に対して証明者が送信するプルーフ {\pi}のサイズは、mの圧倒的な確立でO(m)となる。

証明。楽観的なケースでは証明者が軽量な検証者に送るプルーフ {\pi}はConstructProofアルゴリズムのアウトプットである。証明者がプルーフを構築するローカルチェーンの長さをnとし、 {i \geq 1}について {2^{i}m \leq n < 2^{i+1}m}とすると、ConstructProofアルゴリズムは補助定理1で証明したようにmで圧倒的な確率で深さi-1のプルーフを返す。さらにプルーフのサイズ {D_{i-1}}は、補助定理2で証明したようにmで圧倒的な確率で5mに制限される。これで証明が完了する。

上記では、敵が明示的に干渉せず、軽量な検証者の複雑さを増やそうとしない楽観的なケースの議論が完成した。敵が干渉しRequestコマンドを使って軽量ノードが余計な通信を行うようにさせた場合、攻撃が成功させるためにはかなりの努力が必要で、攻撃が成功する確率も無視できるレベルのものだ。軽量な検証者の検証を遅らせるためだけに攻撃者がこのような攻撃を行うとは考えにくいため、上記の楽観的な効率解析がプロトコルの実際の性能を完全に示すものだと考えられる。

最後に時間量に関して、楽観的なケースでは、検証者は受信したプルーフのサイズに比例する多数の検証ステップを実行する必要がある。従って検証者の計算量はO(m log n)である。

圧縮されたinterlinkを使用する場合の計算量

この場合の通信量と時間は、interlinkの各ブロックからコミットされたマークルツリーのルートハッシュまでのツリー内のパスのみを送信すればよく改善する。楽観的なケースでは軽量な検証者の計算量はO(m log log n)になることが容易に分かる。

6. セキュリティ分析

この軽量な検証への攻撃が成功するということは、軽量な検証者が特定のトランザクションにおいて完全な検証者とは異なる結論に達することを示唆する。セキュリティのための証明論証は次のようになる。軽量な検証者に応答する攻撃者Aが与えられた時、完全な検証者に応答する攻撃者Aを構築する。高い確率でAと協調する完全な検証者は、Aと協調する軽量な検証者と同じ結論に至る。

直感的に上記は、軽量な検証者が受け入れ、処理する任意のプルーフに対して、リカバリし通常のSPV検証者へ同じアウトプットを生成できるフルチェーンが存在することを意味する。

A*の説明は以下のとおり。

  1. AはAの動作をシミュレートし、さらに各ラウンドで完全な検証者として動作し、 {C_1, ..., C_e}の正直なノードにチェーンをリクエストする。全てのブロックを含むブロックツリーBTを維持し、そこに敵によって生成されたブロックを追加する。ランダムオラクルモデルではAハッシュ関数 {H(\cdot)}に対するAの全てのクエリを監視することが可能なので、A*はこれを実行可能であることに注意する。有効なブロックに対応しないAによるクエリは無視される。
  2. Aがペア {(\mathcal X, \pi)}で軽量な検証者に応答すると、AはBTにおいて {(\mathcal X, \pi)}と一致するチェーンCを検索する。すなわち {\mathcal X}はCのsuffixで {\pi}はCのサブチェーン。そのようなチェーンが見つかると、Aは完全な検証者にCで応答する。見つからなかった場合は、A*は完全な検証者に応答を返さない。

我々はThe Bitcoin Backbone Protocol: Analysis and Applicationsの分析を行う。彼らのモデルでは、ブロックチェーンを維持するn個のパーティがあり、(ランダムオラクルモデルと考えられる)ハッシュ関数へのq個のクエリが許可され、パーティの内t個は敵の制御下にある。1回のハッシュクエリでProof of Workを見つける確率は {T / 2^{\mathcal K}}(ターゲットはTで安定)。彼らのホワイトペーパーと同じ表記を使用し {α = (n - t)pq, β = pqt, γ = α - α^{2}}とする。直感的にαは正直なパーティのハッシュパワーを表す。これは正直なパーティが1つのラウンドで得る予定の解の上限でもある。一方βは敵が1回のラウンドで得る解の予想数である。最後にγは正直なパーティの1人がProof of Workの解を見つけるラウンドの期待値である。

準備ができたので軽量な検証者のセキュリティを確立する定理を定式化する。定理は {γ > (1 + \delta)β}を条件とする。これは正直なパーティが過半数のハッシュパワーを持つ設定である。

定理3

(軽量な検証者のセキュリティ)いくつかの {\delta > 0}について、 {γ > (1 + \delta)β}とする。A*と協調する完全な検証者は確率  {1 - exp(-Ω(\delta^{2}m))}でAと協調する軽量な検証者と同じ結論に至る。

証明。軽量な検証者がAにプルーフを要求して実行する場合と、完全な検証者がAににプルーフを要求して実行する場合を比較する。2つの検証者が異なる結論に至る場合をBADと定義する。BADでは、敵対者Aが生成するプルーフ {(\mathcal X, \pi)}に対応するBTからのチェーンCを再構成出来ない場合、Aの定義において上記ケース2に必然的に対応する。この後の事象をNOWITと定義し、 {BAD \subseteq NOWIT}を観測する。NOWITが発生した場合、圧倒的な確率mにおいて正直なパーティから送られたプルーフでMaxChainを実行した結果それが勝利する。この事象をHWINとする。より詳細には {P_r (\neg HWIN \wedge NOWIT)}が指数関数的に減少することを証明する。これが {BAD \subseteq \neg HWIN}で十分であること観察する。従って {P_r (BAD)}が指数関数的に低下することになる。

事象 {\neg HWIN}(HWINでない場合)は、攻撃者Aが正直なパーティのパフォーマンスを上回るプルーフを生成できたケースとなる。さらにNOWITも発生した場合、AがMaxChainアルゴリズムに勝利したプルーフに対応するチェーンを再構築することは不可能である。これは勝利したプルーフ {(\mathcal X, \pi)}がレベル0からのチェーンの有効な拡張ではないために、AによってブロックチェーンツリーBTに取り付けることができないブロックを含んでいることを示唆している。従って {(\mathcal X, \pi)}のレスポンスでは、プルーフ[\pi]は正直なパーティのチェーンからは分岐するはずだ。bを正直なパーティに属するBTの最長のチェーンCの {\pi}で最も最新の正当に生成されたブロックとする。bをCのオーナーによって提供されたプルーフに対してMaxChainが選出した {\mathcal X, \pi}に与える。 {\pi}はターゲット {T/2^{i}}未満であるbから始まる少なくともm個のブロックを含み、 {\pi}の深さはi > 0である。ブロックbが作られたラウンドをrとする。次に、Aが正直なパーティのチェーンが {2^{i}m}進むより速く {T/2^{i}}未満のハッシュ値を持つmブロックを得る確率がmで無視できることを示す。これはAがMaxChainによって選択される証明を生成できる確率が無視できるほど小さいことになる。

rがsuccessul roundの場合、 {X_r}を1に等しい確率変数とする。The Bitcoin Backbone Protocol: Analysis and Applicationsでは、ラウンドrの後の任意のsラウンドにおいて、正直なパーティのチェーンの長さは少なくとも {\ell + \sum_{l=r}^{s}X_l}である。ここで {\ell}はrでの正直なパーティのチェーンの長さ。

敵対者が {T/2^{i}}未満のハッシュ値を持つブロックをmブロック作成するのに必要なラウンド数は負の二項分布に従う。ラウンド数の期待値は {p = T/2^{K}, β = pqt}の場合、 {2^{i}β^{-1}m}。負の二項分布にtail boundを適用するとラウンド数が {(1 - \delta / 4)2^{i}β^{i-1}m}より小さい確率は {exp(-Ω(\delta^{2}m))}であることが分かる。

一方、 {(1 - \delta / 4)2^{i}β^{i-1}m}ラウンドでは、チェルノフ限界を適用することで、正直なパーティが {(1 - \delta/4)^{2}γ2^{i}β^{-1}m}ブロック未満を生成する確率は {exp(-Ω(\delta^{2}m))}によって制限される。

ここで {γ> (1+\delta)β} {γ(1 - \delta / 4)^{2}β^{-1} > 1}を意味し、正直なパーティのチェーンのPoWが敵のPoWを超える確率は  {1 - exp(-Ω(\delta^{2}m))}

非対話型および固定サイズの証明についての実現可能性と実現不可能性

プルーフのセキュリティパラメータはmで、楽観的なケースの場合プルーフのサイズはO(m)であることを観察する。我々の構成では、軽量な検証者は受信したinnerchainの分岐を見つけると、証明者と追加の対話を必要とする場合がある。ここで、例えば(固定サイズの)短い証明が可能か?、もしくはフルノードから軽量な検証者への単一のメッセージのみで済む非対話型のプルーフが可能か?疑問が残る。固定サイズのプルーフに関してはここで検討しているようなテクニックでは改善は考えにくい。例えば例外的に低いハッシュ値のブロックが比例長の多くPoWのプルーフとして送信されると、攻撃の確率が十分低くはならない。言い換えるとこのような短い証明は攻撃者の攻撃難易度と比例し、安全ではない。同様にinnerchainに関して任意の低いプルーフが非対話的に与えられると、innerchainの最後で攻撃をしようとする攻撃者がいた場合に、正直なパーティに比べて攻撃者に有利に働くと考えられる。しかし、そのような低いハッシュブロックに十分な数のブロックを必要とするようにすれば対抗することができる。将来の研究として短くセキュアな非対話型SPVプルーフの設計と調査の可能性を残している。

動的な設定

Bitcoinおよび関連するブロックチェーンプロトコルでは、ターゲットは定期的に再計算される。Interconnected Blockchainも同様に動的なターゲット設定で構築することは可能だ。ただターゲットの再計算はinnnerchainで実行する必要があるため、プルーフの検証中にいくつか注意を払う必要がある。動的な設定の分析については将来の研究として残しておく。

P2WPKHベースのアカウント導出スキームを定義したBIP-84

HDウォレットでSegwitのアドレスを導出する仕様について、今まではP2SHでネストしたP2WPKHの導出スキームを定義したBIP-49のみだったが↓

techmedia-think.hatenablog.com

今回ネイティブのP2WKHのアドレスをHDウォレットで導出するスキームがBIP-84としてTrezorのPavol Rusnakから提案された。

https://github.com/bitcoin/bips/blob/master/bip-0084.mediawiki

仕様自体はシンプルでP2WPKHのアドレスを導出する区分としてBIP-44のpurposeの階層の値をこのBIPの値84を使った強化導出にするだけで、導出スキーム自体は既存のスキームと変わりない。

概要

このBIPではP2WPKH(BIP-173)のsegregated witnessトランザクションのシリアライゼーションフォーマットを使用するHDウォレットの導出スキームを定義する。

動機

P2WPKHのトランザクションを作る場合、共通の導出スキームを持つ必要がある。これによりユーザーは同じマスタードシードを持つもしくは単一アカウントを異なるHDウォレットでシームレスに扱うことができるようになる。

このBIPと互換性のあるウォレットを使用すれば、ユーザーはsegregated witnessアカウントを検出し適切に処理することが保証される。

考慮事項

BIP-49の考慮事項と同じ。

仕様

このBIPはBIP-32のルートアカウントに基づき、複数の決定性アドレスを導出するために必要な2つのステップを定義する。

公開鍵の導出

このBIPでは、ルートアカウントから公開鍵を導出するためBIP-44やBIP-49で定義されているのと同じアカウント構造を使用するが、トランザクションシリアライズ方法が異なることを示すためpurposeの値に異なる値を使用する点が唯一異なる。

m / purpose' / coin_type' / account' / change / address_index

パス階層のpurposeには84'を使用する。他の階層はBIP-44とBIP-49と同じものが使われる。

アドレスの導出

上記で計算した公開鍵からP2WPKHアドレスを導出するために、BIP-141で定義されているカプセル化を使う。

witness:      <署名> <公開鍵>
scriptSig:    (空)
scriptPubKey: 0 <20バイトの公開鍵ハッシュ>
              (0x0014{20バイトの公開鍵ハッシュ})

拡張鍵バージョン

拡張鍵をシリアライズする際、この方式では、代替version byteを使用する。拡張公開鍵は0x04b24746を使用しzpubというプレフィックスを生成し、拡張秘密鍵0x04b2430cを使用しzprvというプレフィックスを生成する。Testnetでは、0x045f1cf6vpub0x045f18bcvprvを使用する。

追加の登録済みversion byteはSLIP-0132にリストされている。

後方互換

このBIPのには考慮事項に記載されているように後方互換性はない。互換性のないウォレットの場合、対象のアカウントが見つけられず何かおかしいことに気付くでしょう。

Test Vecotr

mnemonic = abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon about
rootpriv = zprvAWgYBBk7JR8Gjrh4UJQ2uJdG1r3WNRRfURiABBE3RvMXYSrRJL62XuezvGdPvG6GFBZduosCc1YP5wixPox7zhZLfiUm8aunE96BBa4Kei5
rootpub  = zpub6jftahH18ngZxLmXaKw3GSZzZsszmt9WqedkyZdezFtWRFBZqsQH5hyUmb4pCEeZGmVfQuP5bedXTB8is6fTv19U1GQRyQUKQGUTzyHACMF

// Account 0, root = m/84'/0'/0'
xpriv = zprvAdG4iTXWBoARxkkzNpNh8r6Qag3irQB8PzEMkAFeTRXxHpbF9z4QgEvBRmfvqWvGp42t42nvgGpNgYSJA9iefm1yYNZKEm7z6qUWCroSQnE
xpub  = zpub6rFR7y4Q2AijBEqTUquhVz398htDFrtymD9xYYfG1m4wAcvPhXNfE3EfH1r1ADqtfSdVCToUG868RvUUkgDKf31mGDtKsAYz2oz2AGutZYs

// Account 0, first receiving address = m/84'/0'/0'/0/0
privkey = KyZpNDKnfs94vbrwhJneDi77V6jF64PWPF8x5cdJb8ifgg2DUc9d
pubkey  = 0330d54fd0dd420a6e5f8d3624f5f3482cae350f79d5f0753bf5beef9c2d91af3c
address = bc1qcr8te4kr609gcawutmrza0j4xv80jy8z306fyu

// Account 0, second receiving address = m/84'/0'/0'/0/1
privkey = Kxpf5b8p3qX56DKEe5NqWbNUP9MnqoRFzZwHRtsFqhzuvUJsYZCy
pubkey  = 03e775fd51f0dfb8cd865d9ff1cca2a158cf651fe997fdc9fee9c1d3b5e995ea77
address = bc1qnjg0jd8228aq7egyzacy8cys3knf9xvrerkf9g

// Account 0, first change address = m/84'/0'/0'/1/0
privkey = KxuoxufJL5csa1Wieb2kp29VNdn92Us8CoaUG3aGtPtcF3AzeXvF
pubkey  = 03025324888e429ab8e3dbaf1f7802648b9cd01e9b418485c5fa4c1b9b5700e1a6
address = bc1q8c6fshw2dlwun7ekn9qwf37cu2rn755upcp6el

参照BIP

techmedia-think.hatenablog.com techmedia-think.hatenablog.com techmedia-think.hatenablog.com techmedia-think.hatenablog.com

ElementsでConfidential Transactionを作ってみる

techmedia-think.hatenablog.com

Elementsのセットアップとコインの移動ができたので↑、続いてElements上でConfidential Transactionを作ってみる。

Confidential Transactionについては↓

techmedia-think.hatenablog.com

以下のサイトを参考にConfidential Transactionを作ってみる。

Confidential Transactions — The Elements Project

Confidential Address

Elementsでアドレスを生成すると以下のようにBitcoinのアドレス形式とは異なっているのが分かる。

$ elements-cli getnewaddress
CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ

CTで始まり長さもBitcoinアドレスより長い。CTで始まるのはベースアドレスの先頭にBlinding Keyから生成したconfidential_key(後述)含まれていることを意味する。

validateaddressでこのアドレスの詳細情報が確認できる。

$ elements-cli validateaddress CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ
{
  "isvalid": true,
  "address": "CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ",
  "scriptPubKey": "76a914aabe7c2cb93edaa3448aa9607ff95849f101d90888ac",
  "confidential_key": "02f7b3997676d9c9f78630b335a99c383f620a7d4630ad7c2d989838b153467683",
  "unconfidential": "2dpzZTGFr8fg9jfQ85jpYyMCU8JxTMJEugt",
  "ismine": true,
  "iswatchonly": false,
  "isscript": false,
  "pubkey": "02540dad951d44b352e30cef19a8a5f25622a19683a2cad4e8152ada19b2d27876",
  "iscompressed": true,
  "account": "",
  "timestamp": 1512977085,
  "hdkeypath": "m/0'/0'/11'",
  "hdmasterkeyid": "24f47e54071c4349a86103bccc26c0636c898506"
}

Bitcoinvalidateaddressの情報に加えて以下の項目が追加されている。

  • confidential_key:Blinding Keyの公開鍵(CTで使うPedersen commitmentcommitment = xG + aHxGの値)
  • unconfidential:Blinding Keyを含まないP2PKHアドレス

Confidential Addressは先頭2バイトがバージョンで、その後32バイトがconfidential_keyとなる。単純にBase58エンコードされてるだけなので、デコードして対象データをピックアップすれば簡単にconfidential_keyは抽出できる。(↓bitcoinrbを使って算出するサンプル)

まずアドレスをBase58デコードすると↓

require 'bitcoin'

confidential_addr = 'CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ'
decoded = Bitcoin::Base58.decode(confidential_addr)
> "04eb02f7b3997676d9c9f78630b335a99c383f620a7d4630ad7c2d989838b153467683aabe7c2cb93edaa3448aa9607ff95849f101d908ef4201bd"

先頭の04ebはConfidential Addressのversion bytes。続く32バイトの02f7b3997676d9c9f78630b335a99c383f620a7d4630ad7c2d989838b153467683confidential_key。その後のaabe7c2cb93edaa3448aa9607ff95849f101d908は公開鍵のハッシュで、最後の4バイトef4201bdはこれらのチェックサムになっている。

この公開鍵ハッシュからP2PKHアドレスを生成すると↑のunconfidentialのアドレスが導出できる。

Bitcoin.encode_base58_address('aabe7c2cb93edaa3448aa9607ff95849f101d908', 'eb') # ebはregtestのP2PKHアドレスのversion byte
> "2dpzZTGFr8fg9jfQ85jpYyMCU8JxTMJEugt"

ちなみにunconfidentialのアドレスを指定して、validateaddressをすると、confidentialの項目にConfidential Addressが表示される。

$ elements-cli validateaddress 2dpzZTGFr8fg9jfQ85jpYyMCU8JxTMJEugt
{
  "isvalid": true,
  "address": "2dpzZTGFr8fg9jfQ85jpYyMCU8JxTMJEugt",
  "scriptPubKey": "76a914aabe7c2cb93edaa3448aa9607ff95849f101d90888ac",
  "confidential_key": "",
  "unconfidential": "2dpzZTGFr8fg9jfQ85jpYyMCU8JxTMJEugt",
  "ismine": true,
  "iswatchonly": false,
  "confidential": "CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ",
  "isscript": false,
  "pubkey": "02540dad951d44b352e30cef19a8a5f25622a19683a2cad4e8152ada19b2d27876",
  "iscompressed": true,
  "account": "",
  "timestamp": 1512977085,
  "hdkeypath": "m/0'/0'/11'",
  "hdmasterkeyid": "24f47e54071c4349a86103bccc26c0636c898506"
}

Confidential Transactionを作りたい場合は、sendtoaddresssendfromsendmanycreaterawtransactionでこのConfidential Addressを指定する。そのため量を秘匿してコインを受け取りたい場合は、相手にConfidential Addressを教える。

Blinding Key

Confidential Transactionでは量の秘匿に使用しているBlinding Keyが分かれば秘匿された量を確認することができる。そのためコインの受信者が第三者機関に取引金額の監査を依頼する場合などはこのBlinding Keyを共有する。

Blinding KeyはdumpblindingkeyにConfidential Addressを渡せばエクスポートできる。

$ elements-cli dumpblindingkey CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ
e059cbb981a09c273b34a81906efa8865fda42679113ca421a58ecb0ee89c140

Blinding Keyを受け取った第三者機関は、importblindingkeyでBlinding Keyをインポートすれば、秘匿されたトランザクションの量が見れるようになる。

$ elements-cli importblindingkey CTErPjNQRCAK6r3Nd3oARyrNhVRecmn6fuAQ7YJABN7KWQdML5uwPyLE7sLmY6wXVrCCnrCqytNYukyJ e059cbb981a09c273b34a81906efa8865fda42679113ca421a58ecb0ee89c140

このBlinding KeyからPedersen CommitmentのxGを生成すると↓

blinding_key = 'e059cbb981a09c273b34a81906efa8865fda42679113ca421a58ecb0ee89c140'
confidential_key = ECDSA::Format::PointOctetString.encode(G.generator.multiply_by_scalar(blinding_key.to_i(16)), compression: true).bth
> '02f7b3997676d9c9f78630b335a99c383f620a7d4630ad7c2d989838b153467683'

validateaddressした際に表示されたconfidential_key(公開鍵=楕円曲線上の点)であることが分かる。

つまり、コインの受信者が送信者にConfidential Addressを教えるということは、confidential_key= Blinding Keyから生成した楕円曲線上の点を教えていることになる。そしてその点を算出する秘密鍵(Blinding Key)はコインの受信者が保持したままで送信者もその値を知らない。

Confidential Transactionの作成

sendtoaddressでコインを別のアドレスに送ってみる。

$ elements-cli sendtoaddress CTEsctcppCktGP7ARmMpLj3jq6UkhPqEsMPra5Jq2g4teyjAcUMv8mZD3J4GiCb5YvBcsNT9orqbwrBv 0.005
36802e52f04b4cb2dc0ae69e05e0cd39ed6949db81deb3c006883948d4f7725d

生成されたトランザクションを確認してみると↓

$ elements-cli getrawtransaction 36802e52f04b4cb2dc0ae69e05e0cd39ed6949db81deb3c006883948d4f7725d 1
...
  "txid": "36802e52f04b4cb2dc0ae69e05e0cd39ed6949db81deb3c006883948d4f7725d",
  "hash": "f1aa768af41856d8e9adfbfd3fb377cff6343d53e7dd36eefa4fcde463213997",
  "withash": "bb617eab4d549f3c0ede13627e97deddd379459a1939762288fc64fbf1e0c96e",
  "size": 5744,
  "vsize": 1775,
  "version": 2,
  "locktime": 2,
  "vin": [
    {
      "txid": "d54755e5ea53083d2a096751f67c62e9e7d090b6b3ad8b157b4444fbaa9d74d2",
      "vout": 0,
      "scriptSig": {
        "asm": "3044022057546130be149c71dd04760fb0f96d9a484bf8a78c974badb00d87ef7e8a9fc002206d65a0f2f829b13ff75fd3c14c7ebdc72e4f736088239d5d9d5dfada574e4823[ALL] 0355d680cbab673077a6dddcae982810e0e236c2182910a6434c4b9db4fa63e3ca",
        "hex": "473044022057546130be149c71dd04760fb0f96d9a484bf8a78c974badb00d87ef7e8a9fc002206d65a0f2f829b13ff75fd3c14c7ebdc72e4f736088239d5d9d5dfada574e482301210355d680cbab673077a6dddcae982810e0e236c2182910a6434c4b9db4fa63e3ca"
      },
      "is_pegin": false,
      "scriptWitness": [
      ],
      "pegin_witness": [
      ],
      "sequence": 4294967294
    }
  ],
  "vout": [
    {
      "value-minimum": 0.00000001,
      "value-maximum": 42.94967296,
      "ct-exponent": 0,
      "ct-bits": 32,
      "amountcommitment": "08e6cb1c2118fa492df6782f84d496882ced45b4e759d7cafd507cc2211d217cef",
      "assetcommitment": "0b6f403c9f46739a0b262c393da46913abcd63fc63e3104f7a5b4de800e39c6bf4",
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 63fbcf117ec0a9c7fd5035fd084096d4fe7a89bc OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a91463fbcf117ec0a9c7fd5035fd084096d4fe7a89bc88ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "2diYQwVkH9yJK4Dtcw7Tcx3ZwZTzX8hzCyK"
        ]
      }
    }, 
    {
      "value-minimum": 0.00000001,
      "value-maximum": 42.94967296,
      "ct-exponent": 0,
      "ct-bits": 32,
      "amountcommitment": "084c55083b0b65ce88d68151b3a051736ac2903a3726106b3649a80c9a9e2abe26",
      "assetcommitment": "0bde7bfe359be84bd2603f803423639d0a5c33ceb36c79b629492a94bc3ffafb78",
      "n": 1,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 dcfd7d0c5155c0de4d46ba3c25061684cf0185d7 OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a914dcfd7d0c5155c0de4d46ba3c25061684cf0185d788ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "2duaEiQggnyMz3MnXp6eV2QAYjwFoPiS4nv"
        ]
      }
    }, 
    {
      "value": 0.00035520,
      "asset": "d381261986457b55823c475adfaaad05268dcd85734f99acf7a96a4031d03bc2",
      "n": 2,
      "scriptPubKey": {
        "asm": "",
        "hex": "",
        "type": "fee"
      }
    }
  ],
  "blockhash": "1a046a2ea884024f0c9fea6489f6a74be59fe22c3e7d2e42c823b72f72c9cdfe",
...

UTXOの量がvalueでなく、"value-minimum": 0.00000001"value-maximum": 42.94967296と値の範囲が記載され、量の値代わりに量のコミットメントamountcommitmentが表示される。手数料も明示的にアウトプットに入っている。

また↑には記載していないがトランザクションhex値が非常に大きい。これはrange proofが含まれているからだろう。

amountcommitmentについてはPedersen Commitmentを計算すれば↓

amount = 500000 # satoshi

commitment = confidential_key + H.multiply_by_scalar(amount)

求められそうだけど、amountcommitmentと一致しない。通常楕円曲線の点をシリアライズすると圧縮形式では02 or 03で始まるんだけど、表示されているamountcommitment08で始まっている。このPedersen Commitmentのシリアライズ方法?とかどこに明記されてるんだろう?

↑ではsendtoaddressを使用したが以下のコマンドを組み合わせても同様のことはできる。

  • createrawtransaction
    Confidential Transactionを作る場合は送付先にConfidential Addressを指定する。また、インプットがブラインディングされている場合、インプット指定時にnValueでそのインプットのコインの量を明示的に指定する(コインの量はlistunspentで確認できる)。この時作られたトランザクションはまだブラインディングされてないので、戻り値のhexデータをデコードすると量はまだ確認できる。
  • blindrawtransaction
    createrawtransactionで作成したトランザクションのインプットもしくはアウトプットの量が秘匿されている場合、blindrawtransactionを実行する。1つのインプットが秘匿されている場合、少なくとも1つのアウトプットは秘匿されていなければならない(値が0の秘匿アウトプットを作成するのも可)。また全インプットが秘匿されていない場合、秘匿アウトプットの数は0か2以上でなければならない(ここでも値が0の秘匿アウトプットを作成するのも可)。
  • signrawtransaction
  • sendrawtransaction

制限事項

プロジェクトサイトに記載されているElementsの制限事項。

実装は指定された精度レベルのrange proofに応じて、各トランザクションアウトプットの所定の桁の数を隠すだけとなる。その後に0.0001 BTCのminimum confidential amountと、minimum amountの232倍のmaximum confidential amountが続く。

最小値より小さい桁数はオブザーバーに明らかになる。例えば最小値が0.0001 BTCの場合、123.456789 BTCのトランザクションアウトプットは?.????89 BTCと見える。このように漏れる金額はわずかなので、これ自体はそれほど重要ではないが、第三者が後続のトランザクションを同じ金額でリンクすることでコインを追跡できるようになることに注意する必要がある。全ての値を最小値に丸めることでこういった情報を公開するのを避けることができる。

最大値より大きいトランザクションアウトプットは、第三者に金額の大きさのオーダーを明かすことになる。例えば最大値が500k BTCの場合、その量以下のアウトプットは同じように見えるが、500k〜5M BTCのアウトプットは第三者に分かってしまう(ただその下の量はわからないので正確な量は分からないが)。こういった最大値を超える部分の値が明らかになるのは重要なプライバシーの漏洩になる可能性がある。そのため、最大値を超えるような高額のトランザクションは、量を分割して最大値以下にすることを強く推奨する。

↑のトランザクションだと、最小値と最大値はそれぞれ

  "value-minimum": 0.00000001,
  "value-maximum": 42.94967296

となっているので、最小値は1 satoshi(つまり最小値に関しては値が明らかになることはない)で、最大値は42.94967296 BTCが設定されているようだ(つまり42.94967296より多い部分の値については明らかになる)。

とりあえずElementsのRPCを利用してConfidential Transactionの作成、ブロードキャストはできたけど、実際にElementsと互換のあるCTを自前のライブラリで作ろうとすると、もう少し詳細な仕様が無いと辛いかな。あとできればrange proofの生成のロジックとか追ってみたい。

サイドチェーンにBitcoinをペグしてみる。

Confidential TransactionをサポートしているElementsで実際にCTを作ってみようと思い、まずElementsのセットアップしてサイドチェーンにコインをペグする。

github.com

Elementsのセットアップ

今回使用したElementsはelements-0.14.1ブランチのソース。(久しぶりに見たら0.14.1がアクティブブランチになってる。Alphaはもう使われてない?)

↓に独自サイドチェーン(elementsのregtest)のビルド手順が書いてあるので、これを参考にして環境をセットアップする。

Building A New Sidechain with Elements — The Elements Project

Elementsのビルド

$ git clone https://github.com/ElementsProject/elements.git
$ cd elements
$ ./autogen.sh 
$ ./configure
$ make -j3

makeが終わったらsrc直下にelementsdelements-clielements-txなどが生成されてる。

起動

基本的にはbitcoindと同じ。

$ elementsd -regtest -daemon

起動するとUbuntuの場合$HOME/.bitcoin/以下にelementsregtestというディレクトリができ、チェーンのデータはこのディレクトリ配下で管理される。

getinfoすると2100万 Bitcoinがあることが分かる。

$ elements-cli getinfo
{
  "version": 2140101,
  "protocolversion": 70015,
  "walletversion": 130000,
  "balance": {
    "bitcoin": 21000000.00000000
  },
  "blocks": 0,
  "timeoffset": 0,
  "connections": 0,
  "proxy": "",
  "difficulty": 1,
  "chain": "elementsregtest",
  "keypoololdest": 1512955437,
  "keypoolsize": 100,
  "paytxfee": 0.00000000,
  "relayfee": 0.00001000,
  "errors": ""
}

Elementsはサイドチェーンなので基本的に通貨発行は行わず、Bitcoinとペグする形でコインを入手する。ペグされたBitcoinと同量のコインがElements上でアンロックされる仕組み(Elements上のコインの名前もbitcoinなのは紛らわしいよね)。

サイドチェーンにコインをペグするのに、Bitcoin⇔Elements間のコインのペグの仕組みについて理解しておいた方が良い↓

techmedia-think.hatenablog.com

ちなみに初期状態でlistunspentすると↓のようなTXIDがb661d7fa55c27dc4dcd804e7640b23f92578a4b1ad0fbffbc2095eaec251ce34のUTXOが100個ほど出てくる。2,100万コインを100個のUTXOに分割して保持しているのが分かる。

{
  "txid": "b661d7fa55c27dc4dcd804e7640b23f92578a4b1ad0fbffbc2095eaec251ce34",
  "vout": 0,
  "scriptPubKey": "51",
  "amount": 210000.00000000,
  "asset": "d381261986457b55823c475adfaaad05268dcd85734f99acf7a96a4031d03bc2",
  "assetlabel": "bitcoin",
  "confirmations": 2,
  "spendable": true,
  "solvable": true,
  "blinder": "0000000000000000000000000000000000000000000000000000000000000000",
  "assetblinder": "0000000000000000000000000000000000000000000000000000000000000000"
}

設定ファイル

設定ファイル名はelements.confで(Bitcoin Coreと同様デフォルトでは作成されないので自分で作る)、Ubuntuだと$HOME/.bitcoinディレクトリ以下を探しにいく。

Elementsではメインチェーン(Bitcoin)上でコインがロックされたのを確認した上で、同量のコインをサイドチェーン(Elements)上でアンロックするが、その際メインチェーンで確かにコインがロックされているか検証するため、メインチェーンのノードに対してRPCアクセスをしている*1。そのため以下のようにelements.confにメインチェーンのノードのRPCアクセス情報を設定する必要がある。

rpcuser=bitcoinrpc(ElementsのRPCユーザー)
rpcpassword=password(ElementsのRPCパスワード)
rpcport=8339(ElementsのRPCポート)
daemon=1
discover=0
testnet=0
regtest=1
mainchainhost=127.0.0.1(BitcoinノードのIP)
mainchainrpcport=8338(BitcoinノードのRPCポート)
mainchainrpcuser=bitcoinrpc(BitcoinノードのRPCユーザー)
mainchainrpcpassword=password(BitcoinノードのIRPCパスワード)
validatepegin=1
txindex=1

Elementsにペグインする際のFederationスクリプトに使用する鍵の生成

Elementsのブロックは、予め決められたユーザー(公開鍵)を持つ人たち(block signer)の一定数が署名する(マルチシグ)ことで生成される。regtestなど独自チェーンを作る場合、まずこのブロックの署名に使用するスクリプトを生成する。

署名に使う新しいアドレスを生成し、

$ elements-cli getnewaddress
CTEuyLmLtg5x82wGhS9cDnAF9DUZcS1EgXTsgHMqJfNDqArjaGQVGsattpCE2CMrh6B1RRnhSUfQ6RGn

アドレスの公開鍵と秘密鍵を取得する。

$ elements-cli validateaddress CTEuyLmLtg5x82wGhS9cDnAF9DUZcS1EgXTsgHMqJfNDqArjaGQVGsattpCE2CMrh6B1RRnhSUfQ6RGn
{
  "isvalid": true,
  "address": "CTEuyLmLtg5x82wGhS9cDnAF9DUZcS1EgXTsgHMqJfNDqArjaGQVGsattpCE2CMrh6B1RRnhSUfQ6RGn",
  "scriptPubKey": "76a91440f6a609d0969b6cbef9557fa8cbedb012472c8088ac",
  "confidential_key": "037be078e2456585073c8f083b822b2a8d307f34144992436ad9e75df101cb3f8f",
  "unconfidential": "2dfMF7EtbPGTREZATPgePtcLXCGby6qPwPg",
  "ismine": true,
  "iswatchonly": false,
  "isscript": false,
  "pubkey": "03d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae28", ←これが公開鍵
  "iscompressed": true,
  "account": "",
  "timestamp": 1512955437,
  "hdkeypath": "m/0'/0'/2'",
  "hdmasterkeyid": "da51d8c6f773da39cfc48d90e1888ff25dcc4993"
}
$ elements-cli dumpprivkey CTEuyLmLtg5x82wGhS9cDnAF9DUZcS1EgXTsgHMqJfNDqArjaGQVGsattpCE2CMrh6B1RRnhSUfQ6RGn
cUgf4MyWeysP5iJMru4RbRpXgoCuSaz3X4beBa3qfqPwvGENity1

続いてブロックに署名するマルチシグスクリプトを作成する。↑の公開鍵使って、ここでは1-of-1のマルチシグを作成する↓

$ elements-cli createmultisig 1 \[\"03d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae28\"\]
{
  "address": "XHfz21yi9JkdtYBzYf7voeYn7et3tq4Khc",
  "redeemScript": "512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae"
}

このマルチシグスクリプトをサイドチェーンのブロック署名用に使用する。一旦Elementsを停止し、既存のチェーンデータをリセットしてマルチシグスクリプト(↑で生成したredeemScript)を指定してElementsを起動する。今回はペグしたコインをサイドチェーンに移動する際に使われる-fedpegscriptも同じスクリプトを指定しておく。

$  rm -Rf ~/.bitcoin/elementsregtest
$ elementsd -regtest -daemon -signblockscript=512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae  -fedpegscript=512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae

チェーンをリセットしてるので、このマルチシグに署名できるよう、↑で作成した秘密鍵をインポートする。

$ elements-cli importprivkey cUgf4MyWeysP5iJMru4RbRpXgoCuSaz3X4beBa3qfqPwvGENity1

ブロックの生成

getnewblockhexでまだマイニングされていない新しいブロックのデータを生成する。

$ elements-cli getnewblockhex
0000002041b97650a81cb6395a79e3109ac5df68c7dceb40a7b65de16baff69fe4c143a61afe4f13e39ed34497613ac34d48b42cfae8590ea386dea33a70f5a178b9b47e1a0a2e5a0100000025512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae00010200000001010000000000000000000000000000000000000000000000000000000000000000ffffffff03510101ffffffff0201b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000016a01b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000266a24aa21a9ed94f15ed3a62165e4a0b99699cc28b48e19cb5bc1b1f47155db62d63f1e047d45000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000

signblockでブロックデータの署名を生成する。

$ elements-cli signblock 0000002041b97650a81cb6395a79e3109ac5df68c7dceb40a7b65de16baff69fe4c143a61afe4f13e39ed34497613ac34d48b42cfae8590ea386dea33a70f5a178b9b47e1a0a2e5a0100000025512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae00010200000001010000000000000000000000000000000000000000000000000000000000000000ffffffff03510101ffffffff0201b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000016a01b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000266a24aa21a9ed94f15ed3a62165e4a0b99699cc28b48e19cb5bc1b1f47155db62d63f1e047d45000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000
00473045022100b347f546a144f153913045da6a6c707d7b4cff7f12b7967bb1597aff080b9de10220790648dfad6a5c2f7e9320a236bf4a35bc2182337de77e67b9d44aa6dc8da8ff

署名ができたらcombineblocksigsにブロックデータと署名データを引数で渡して、署名ブロックを入手する。今回は1-of-1なのでこれで良いけど、複数の署名者がいる場合は、各署名者がsignblockで署名を生成し、その署名をまとめてcombineblocksigsを実行する。

$ elements-cli combineblocksigs 0000002041b97650a81cb6395a79e3109ac5df68c7dceb40a7b65de16baff69fe4c143a61afe4f13e39ed34497613ac34d48b42cfae8590ea386dea33a70f5a178b9b47e1a0a2e5a0100000025512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae00010200000001010000000000000000000000000000000000000000000000000000000000000000ffffffff03510101ffffffff0201b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000016a01b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000266a24aa21a9ed94f15ed3a62165e4a0b99699cc28b48e19cb5bc1b1f47155db62d63f1e047d45000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000 \[\"00473045022100b347f546a144f153913045da6a6c707d7b4cff7f12b7967bb1597aff080b9de10220790648dfad6a5c2f7e9320a236bf4a35bc2182337de77e67b9d44aa6dc8da8ff\"\]
{
  "hex": "0000002041b97650a81cb6395a79e3109ac5df68c7dceb40a7b65de16baff69fe4c143a61afe4f13e39ed34497613ac34d48b42cfae8590ea386dea33a70f5a178b9b47e1a0a2e5a0100000025512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae4900473045022100b347f546a144f153913045da6a6c707d7b4cff7f12b7967bb1597aff080b9de10220790648dfad6a5c2f7e9320a236bf4a35bc2182337de77e67b9d44aa6dc8da8ff010200000001010000000000000000000000000000000000000000000000000000000000000000ffffffff03510101ffffffff0201b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000016a01b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000266a24aa21a9ed94f15ed3a62165e4a0b99699cc28b48e19cb5bc1b1f47155db62d63f1e047d45000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000",
  "complete": true
}

最後に生成した署名付きブロックをネットワークにサブミットする。

$ elements-cli submitblock 0000002041b97650a81cb6395a79e3109ac5df68c7dceb40a7b65de16baff69fe4c143a61afe4f13e39ed34497613ac34d48b42cfae8590ea386dea33a70f5a178b9b47e1a0a2e5a0100000025512103d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae2851ae4900473045022100b347f546a144f153913045da6a6c707d7b4cff7f12b7967bb1597aff080b9de10220790648dfad6a5c2f7e9320a236bf4a35bc2182337de77e67b9d44aa6dc8da8ff010200000001010000000000000000000000000000000000000000000000000000000000000000ffffffff03510101ffffffff0201b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000016a01b34490609efeb1e9d19fa51275c76fd288aa7cc3f662c54c04b44aa242ef398e01000000000000000000266a24aa21a9ed94f15ed3a62165e4a0b99699cc28b48e19cb5bc1b1f47155db62d63f1e047d45000000000000012000000000000000000000000000000000000000000000000000000000000000000000000000

サブミットしたらブロックが追加されてることが確認できる。

$ elements-cli getblockcount
1

生成したブロックを確認すると

elements-cli getblock 7a48bd4377102108abff8d2b58ae22d096e06242db82244e494ef5f1a09dfc54
{
  "hash": "7a48bd4377102108abff8d2b58ae22d096e06242db82244e494ef5f1a09dfc54",
  "confirmations": 1,
  "strippedsize": 371,
  "size": 412,
  "weight": 1525,
  "height": 1,
  "version": 536870912,
  "versionHex": "20000000",
  "merkleroot": "7eb4b978a1f5703aa3de86a30e59e8fa2cb4484dc33a619744d39ee3134ffe1a",
  "tx": [
    "7eb4b978a1f5703aa3de86a30e59e8fa2cb4484dc33a619744d39ee3134ffe1a"
  ],
  "time": 1512966682,
  "mediantime": 1512966682,
  "nonce": 1,
  "bits": "1 03d4d908226f1a075022798611f02ee992271f7581c0f527757ccfb603c43fae28 1 OP_CHECKMULTISIG",
  "difficulty": 1,
  "chainwork": "0000000000000000000000000000000000000000000000000000000000000002",
  "previousblockhash": "a643c1e49ff6af6be15db6a740ebdcc768dfc59a10e3795a39b61ca85076b941"
}

Bitcoinの場合だとbitsには難易度の閾値がセットされるが、Elementsのブロックヘッダでは、ブロックの署名者のマルチシグスクリプトがセットされている。

BitcoinからElementsにペグイン

Elementsのセットアップができたので、BitcoinのコインをElementsに移動してみる。

Bitcoin Coreもregtestで起動しておく(このノードのRPCのアクセス情報と↑のelements.confの内容が一致してること)。

ペグインするアドレスを生成

getpeginaddressでペグインの際に使用するアドレスを生成する。(getnewaddressなどと同様、生成したアドレスの秘密鍵はウォレットファイルに追加される。)

$ elements-cli getpeginaddress
{
  "mainchain_address": "2Muv3LwF8YxV4Jh6mpvGjN9d77AaH1CRfaw",
  "claim_script": "0014e8d28b573816ddfcf98578d7b28543e273f5a72a"
}

mainchain_addressはサイドチェーンにコインをペグする際に、ペグするコインのメインチェーン上での送付先アドレス。

このアドレスにメインチェーンでペグする分のコインを送る。

$ bitcoin-cli -regtest sendtoaddress "2Muv3LwF8YxV4Jh6mpvGjN9d77AaH1CRfaw" 1
d9017e5efc86d2e6e52a39f24edf977fc33e3d7e6eaa0d7a7e8e7599424daf81

ペグされたコインの入手

インチェーン上でペグするコインをロックしたら、サイドチェーン上でclaimpeginを実行しサイドチェーンのコインを入手する。claimpeginは以下の3つの引数を取る。

  • bitcoinTx
    mainchain_address宛にコインをデポジットしたBitcoinトランザクションのrawデータ。
  • txoutproof
    bitcoinTxのトランザクションがブロックに格納されていることの証明。データ自体はmerkleblockメッセージで使われているデータと同じで、そのトランザクションがブロックに含まれていることを示すマークルパスとマークルルートを計算するのに必要なハッシュ。これはメインチェーン上でgettxoutproofを実行すれば取得できる。
  • claim_script(オプション)
    getpeginaddressで生成した際のwitness programを指定。ウォレットに登録されていない場合にこのオプション使って指定する。

bitcoinTxhは↓

$ bitcoin-cli -regtest getrawtransaction d9017e5efc86d2e6e52a39f24edf977fc33e3d7e6eaa0d7a7e8e7599424daf81
02000000014578ddc14da3e19445b6e7b4c61d4af711d29e2703161aa9c11e4e6b0ea08843010000006b483045022100eea27e89c3cf2867393263bece040f34c03e0cddfa93a1a18c0d2e4322a37df7022074273c0ab3836affba53737c83673ca6c0d69bffdf722b4accfd7c0a9b2ea4e60121020bfcdbda850cd250c3995dfdb426dc40a9c8a5b378be2bf39f6b0642a783daf2feffffff02281d2418010000001976a914b56872c7b363bfb3f5af84d071ff282cf2abfe3988ac00e1f5050000000017a9141d4796c6e855ae00acecb0c20f65dd8bbeffb1ec87d1000000

txoutproofは↓

$ bitcoin-cli -regtest gettxoutproof \[\"d9017e5efc86d2e6e52a39f24edf977fc33e3d7e6eaa0d7a7e8e7599424daf81\"\]
03000030ffba1d575800bf37a1ee1962dee7e153c18bcfc93cd013e7c297d5363b36cc2d63d5c4a9fdc746b9d3f4f62995d611c34ee9740ff2b5193ce458fdac6d173800ec402e5affff7f200500000002000000027ce06590120cf8c2bef7726200f0fa655940cadcf62708d7dc9f8f2a417c890b81af4d4299758e7e7a0daa6e7e3d3ec37f97df4ef2392ae5e6d286fc5e7e01d90105

↑の2つを使ってサイドチェーンでclaimpeginを時刻する。

regtestの注意事項

regtestでclaimpeginを使用する際は以下の点に注意する。

  • elementsのノードの最新ブロックが1日以上古い場合、まだIBD中と判断されてエラーになるので、claimpegin実行時にブロックが一日以上古かったら↑に書いてるようにElementsのブロックを生成すること。
  • ロックされたトランザクションを確認するためbitcoindに対してRPCアクセスするが、ロックしたトランザクションがブロックに格納されてから10 confirmation経っていないとエラーになるので、Bitcoinのregtest側で事前に10ブロック作っておくこと。

※ txoutproofはメインチェーン上でペグしたトランザクションがブロックに格納されていることの保証にはなるが、それ単体ではブロックが実際にチェーン上に存在しているか、またそのブロックのConfirmation数がいくつかは分からないので、そういった確認をメインチェーンのノードにRPCして確認している。

$ elements-cli claimpegin 02000000014578ddc14da3e19445b6e7b4c61d4af711d29e2703161aa9c11e4e6b0ea08843010000006b483045022100eea27e89c3cf2867393263bece040f34c03e0cddfa93a1a18c0d2e4322a37df7022074273c0ab3836affba53737c83673ca6c0d69bffdf722b4accfd7c0a9b2ea4e60121020bfcdbda850cd250c3995dfdb426dc40a9c8a5b378be2bf39f6b0642a783daf2feffffff02281d2418010000001976a914b56872c7b363bfb3f5af84d071ff282cf2abfe3988ac00e1f5050000000017a9141d4796c6e855ae00acecb0c20f65dd8bbeffb1ec87d1000000 03000030ffba1d575800bf37a1ee1962dee7e153c18bcfc93cd013e7c297d5363b36cc2d63d5c4a9fdc746b9d3f4f62995d611c34ee9740ff2b5193ce458fdac6d173800ec402e5affff7f200500000002000000027ce06590120cf8c2bef7726200f0fa655940cadcf62708d7dc9f8f2a417c890b81af4d4299758e7e7a0daa6e7e3d3ec37f97df4ef2392ae5e6d286fc5e7e01d90105
27112a69cb01228939f993e93c4f94f764703eb3f3ee05aad7af17a7d9f7329c

正常に終わるとTXIDが返されるので、そのトランザクションを確認すると

$ elements-cli getrawtransaction 27112a69cb01228939f993e93c4f94f764703eb3f3ee05aad7af17a7d9f7329c 1
{
  "hex": "02000000010181af4d4299758e7e7a0daa6e7e3d3ec37f97df4ef2392ae5e6d286fc5e7e01d90100004000ffffffff0201c23bd031406aa9f7ac994f7385cd8d2605adaadf5a473c82557b4586192681d3010000000005f5c940001976a91495208a4cf9f3e6fdf06178baed1bebb8a874b6bf88ac01c23bd031406aa9f7ac994f7385cd8d2605adaadf5a473c82557b4586192681d30100000000000017c0000000000000000002473044022075282f574650e20c3a87d0d1f67d0bcd8f9319b26d244eb254c0aa5bc0284e8002205bddfd4e2f5e278de5f473804a1d061ed6f9bdbcb65fec9b20402879c5a998090121025c36c65910268ee06421053cb9bab1c849c4bdd467d6e77a89d33ff213adc3ca060800e1f5050000000020c23bd031406aa9f7ac994f7385cd8d2605adaadf5a473c82557b4586192681d32006226e46111a0b59caaf126043eb5bbf28c34f3a5e332a1fc7b2b73cf188910f160014e8d28b573816ddfcf98578d7b28543e273f5a72ae002000000014578ddc14da3e19445b6e7b4c61d4af711d29e2703161aa9c11e4e6b0ea08843010000006b483045022100eea27e89c3cf2867393263bece040f34c03e0cddfa93a1a18c0d2e4322a37df7022074273c0ab3836affba53737c83673ca6c0d69bffdf722b4accfd7c0a9b2ea4e60121020bfcdbda850cd250c3995dfdb426dc40a9c8a5b378be2bf39f6b0642a783daf2feffffff02281d2418010000001976a914b56872c7b363bfb3f5af84d071ff282cf2abfe3988ac00e1f5050000000017a9141d4796c6e855ae00acecb0c20f65dd8bbeffb1ec87d10000009703000030ffba1d575800bf37a1ee1962dee7e153c18bcfc93cd013e7c297d5363b36cc2d63d5c4a9fdc746b9d3f4f62995d611c34ee9740ff2b5193ce458fdac6d173800ec402e5affff7f200500000002000000027ce06590120cf8c2bef7726200f0fa655940cadcf62708d7dc9f8f2a417c890b81af4d4299758e7e7a0daa6e7e3d3ec37f97df4ef2392ae5e6d286fc5e7e01d9010500000000",
  "txid": "27112a69cb01228939f993e93c4f94f764703eb3f3ee05aad7af17a7d9f7329c",
  "hash": "440e7c28917bbb9c3145b83c1bc2307b4a4d4b9b54e6a3d0dd0dcb77630054d8",
  "withash": "6767fc94b1e1df216d048d77c739158afa3505a7b3877ad1bb28d12e9164f893",
  "size": 754,
  "vsize": 313,
  "version": 2,
  "locktime": 0,
  "vin": [
    {
      "txid": "d9017e5efc86d2e6e52a39f24edf977fc33e3d7e6eaa0d7a7e8e7599424daf81",
      "vout": 1,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "is_pegin": true,
      "scriptWitness": [
        "3044022075282f574650e20c3a87d0d1f67d0bcd8f9319b26d244eb254c0aa5bc0284e8002205bddfd4e2f5e278de5f473804a1d061ed6f9bdbcb65fec9b20402879c5a9980901", 
        "025c36c65910268ee06421053cb9bab1c849c4bdd467d6e77a89d33ff213adc3ca"
      ],
      "pegin_witness": [
        "00e1f50500000000", 
        "c23bd031406aa9f7ac994f7385cd8d2605adaadf5a473c82557b4586192681d3", 
        "06226e46111a0b59caaf126043eb5bbf28c34f3a5e332a1fc7b2b73cf188910f", 
        "0014e8d28b573816ddfcf98578d7b28543e273f5a72a", 
        "02000000014578ddc14da3e19445b6e7b4c61d4af711d29e2703161aa9c11e4e6b0ea08843010000006b483045022100eea27e89c3cf2867393263bece040f34c03e0cddfa93a1a18c0d2e4322a37df7022074273c0ab3836affba53737c83673ca6c0d69bffdf722b4accfd7c0a9b2ea4e60121020bfcdbda850cd250c3995dfdb426dc40a9c8a5b378be2bf39f6b0642a783daf2feffffff02281d2418010000001976a914b56872c7b363bfb3f5af84d071ff282cf2abfe3988ac00e1f5050000000017a9141d4796c6e855ae00acecb0c20f65dd8bbeffb1ec87d1000000", 
        "03000030ffba1d575800bf37a1ee1962dee7e153c18bcfc93cd013e7c297d5363b36cc2d63d5c4a9fdc746b9d3f4f62995d611c34ee9740ff2b5193ce458fdac6d173800ec402e5affff7f200500000002000000027ce06590120cf8c2bef7726200f0fa655940cadcf62708d7dc9f8f2a417c890b81af4d4299758e7e7a0daa6e7e3d3ec37f97df4ef2392ae5e6d286fc5e7e01d90105"
      ],
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "value": 0.99993920,
      "asset": "d381261986457b55823c475adfaaad05268dcd85734f99acf7a96a4031d03bc2",
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_DUP OP_HASH160 95208a4cf9f3e6fdf06178baed1bebb8a874b6bf OP_EQUALVERIFY OP_CHECKSIG",
        "hex": "76a91495208a4cf9f3e6fdf06178baed1bebb8a874b6bf88ac",
        "reqSigs": 1,
        "type": "pubkeyhash",
        "addresses": [
          "2do2G436PpVMqGxpzBoFJhTQncfKJbGU3YG"
        ]
      }
    }, 
    {
      "value": 0.00006080,
      "asset": "d381261986457b55823c475adfaaad05268dcd85734f99acf7a96a4031d03bc2",
      "n": 1,
      "scriptPubKey": {
        "asm": "",
        "hex": "",
        "type": "fee"
      }
    }
  ]
}
インプットについて

pegin_witnessの部分がペグインの証明で、上から順に以下の項目で構成されている。

アウトプットについて
  • ペグした1 BTCがP2PKH宛に0.99993920コイン送られ、手数料が差し引かれているのが分かる。またこのP2PKHのアドレスはキープールから新しい鍵を取得して割り当てているみたい。
  • 手数料の方は、feeとあるだけでscriptPubKeyスクリプトは空。
  • assetはコインの識別子。メインチェーンのコインとペグするコインの他に任意のアセットが発行できる(Confidentail Assets)ためその識別に使うものと思われる。

あとはまたブロック署名者の鍵を使って新しいブロックを作れば、↑のトランザクションもブロックに入る。listunspentすれば↑のUTXOも利用可能になっており、このコインを使ってサイドチェーンでコインの送付ができるようになる。

ひとまずCT作るための下準備ができたので次は実際にCTを作ってみよう。

*1:もともとのサイドチェーンのホワイトペーパーにあるようなSPV Proofの仕組みがあればこのRPCアクセスはおそらく不要になるが、そのためにはBitcoinに機能追加しないといけないので現状こういう形をとっていると思われる。