読者です 読者をやめる 読者になる 読者になる

Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoinの匿名性を向上させるConfidential Transactions

Bitcoin単体には個人を表すデータは存在しないけど、アドレス間の送金のやりとりや、取引所を介した現金化などのデータから必ずしも個人が特定できないということは無い。
Bitcoinのアドレスと組織・個人が結びつくと、例えばAという会社はどれくらいの売上をBitcoinで上げているかわかったり、顧客や従業員にいくらBitcoinを支払っているのかといった情報も分かってくる。そこでBitcoinの匿名性を強化しようというZerocashやConfidential Transactionsのような取り組みがされてる。

Confidential Transactionsとは

https://people.xiph.org/~greg/confidential_values.txt

Bitcoinのトラストレスな仕組み上、信頼できる第三者がいなくても取引が可能である反面、全ての取引はブロックチェーン上に記録されパブリックなものになる。
CoinJoinのように入力と出力にそれぞれ複数のアドレスを利用することで、誰から誰にどれだけ送金したのか(実質)追跡できなくするという方法もあるけど、これもどれだけの量が送付されたのかというのを隠すことはできない。

Confidential Transactionsを利用すると、送付するBitcoinの量を取引の関係者のみにしか見えなくすることができるようになる。Confidential Transactionsは準同型暗号*1を利用してこれを可能にしている。この設計の副次的な効果として、Confidential Transactions暗号証明のオーバーヘッド部分を再利用することで、トランザクションデータの増加無しにプライベートなメモ情報(請求番号や返金アドレス等)のやりとりが可能になる。

Confidential Transactionsの仕組み

Confidential Transactionsのベースとなるツールが、Pedersen commitment。

ビットコミットメントを利用することで、秘匿データを保持し、後でデータが変更できないようコミットすることができる。シンプルなビットコミットメントは暗号ハッシュを使用して↓のように構築できる。

commitment = SHA256( blinding_factor || data )

誰かにcommitmentだけ伝えた場合、受け取ったユーザは、送られたデータが何かは分からない。その後、blinding factorとデータを明らかにし、送られたユーザがそのハッシュ値を求めることで、先に伝えられたコミットされたデータと合致することを確認することができる。

Pedersen commitmentは↑のように動作するが、追加のプロパティを使用して、commitmentsを追加することができる。↓のようにcommitmentsのセットの合計はデータ和のcommitmentsと同じになる。

  C(BF1, data1) + C(BF2, data2) == C(BF1 + BF2, data1 + data2)
  C(BF1, data1) - C(BF1, data1) == 0

つまり、commitmentは加算でき交換可能なプロパティを適用できる。

もしデータが{1,1,2}でBlinding Factorが{5,10,15}だと

C(BF1, data1) + C(BF2, data2) - C(BF3, data3) == 0

といった結果になる。

ここで利用するPedersen commitmentsは楕円曲線の点を使って構築する。

通常の楕円曲線暗号の公開鍵は、秘密鍵(x)と楕円曲線のペースとなるグループ(G)の乗算により算出される。(この公開鍵は通常、33バイト配列としてシリアライズされてる。)

Pub = xG

この楕円曲線暗号の公開鍵は↑の準同型の加法特性を持っているため、以下のような計算が成り立つ。

Pub1 + Pub2 = (x1 + x2 (mod n))G.

(この特徴は、第三者が新しいBitcoinアドレスを生成できるようにしたBIP-32のHDウォレットで利用されている。)
Pedersen commitmentsは、グループ(Hと呼ぶ)のための追加のジェネレータを選択することによって作成される。誰もがGに対する(またはその逆)Hの離散対数を知らないように、誰にも xG=Hとなるようなxは知られない。Hを選択するのに以下のようにGの暗号化ハッシュを使用する。

H = to_point(SHA256(ENCODE(G)))

to_point()関数は入力として新しい点xの値を取ると、その曲線上のyの値を確認する。

与えられた2つのジェネレータで、↓のようなコミットメントスキーマを構築できる。

commitment = xG + aH

ここでxは秘密のblinding factorで、aはコミットする量になる。また追加プロパティの可換性を使うだけで、加法準同型ビットコミットメントの持つ特性により全ての関係を検証できる。

量の検証

Pedersen commitmentsは情報理論的にはプライベートで、確認できるcommitmentにはいくつかののblinding factorが存在する。blinding factorが本当にランダムな場合、無限の計算能力を持つ攻撃者もコミットメントされた量を判定することはできない。またユーザが恣意的なマッピングを計算することができないという点で、偽のcommitmentに対しても計算量的に安全である。もし恣意的なマッピングが可能であれば、ジェネレータがお互いに離散対数を見つけることができ、グループのセキュリティが危険にされされることになる。

このツールを利用することで、Bitcoinトランザクションの通常の8バイトの整数量を33-byteのPedersen commitmentsに置き換えることができる。

トランザクションの作者が注意深くblinding factorの選択すれば、そのコミットメントを0まで追加することを確認することで、トランザクションの検証を行うことができる。

(In1 + In2 + In3 + plaintext_input_amount*H...) - (Out1 + Out2 + Out3 + ... fees*H) == 0.

これを実現するためには、明示的にトランザクション内に明示的に手数料を作成する必要があるが、これは一般的に望ましい。(通常”インプットの合計-アウトプットの合計=余り”が手数料としてカウントされる)

commitmentとそのチェックは非常に簡単だが、残念なことに追加手段無しに行うのはこの方法を行うのは安全ではない。

問題は、グループが周期的でさらにmod P(グループの順序を定義する256bitの素数)となる。その結果、大きな値を加えることによるオーバーフローでマイナスの量になる。これは出力にマイナス値の場合でも↑のsum-to-zeroが有効になるということを意味する。

(1 + 1) - (-5 + 7) == 0

↑の例では、誰かが入力として2Bitcoinを使って、-5Bitcoinの無効な出力と7Bitcoinの出力を取得する。この結果、なにもないところから5つのコインが生まれる。

出力の値が取る範囲の証明

これを防止するために、複数の出力がある場合、コミットされた各出力がオーバーフローすることが内範囲の値(0〜2^64)であることを証明する必要がある。

送付するBitcoinの量とblinding factorを開示すればネットワークがチェックできるようになるが、それでは肝心のプライバシーを失うことになる。代わりに量やblinding factorに関して何も明かさないまま、その量が0〜2^64の範囲内であることを証明する必要がある。そのためPedersen commitmentの範囲を証明するための追加の暗号システムが必要となり、Schoenmakersのバイナリ分解に似た方法を多くの最適化を加えて(バイナリは使ってない)使っている。

まず最初に基本的な楕円曲線の署名を使う。'message'が公開鍵のハッシュになるような署名を作る場合、その署名は署名者は秘密鍵を知っていることの証明になり、いくつかのジェネレータにとって公開鍵の離散対数となる。

P = xG + aHのような公開鍵については、付加されているHや誰もxを知らないため、GについてのPの離散対数は誰も知らない。もしaが0の場合は、P=xGで離散対数はちょうどxとなり、誰かがその公開鍵の署名する可能性はある。

pedersen commitmentは公開鍵としてのコミットメントとコミットメントのハッシュに署名するだけでゼロへのコミットメントであることを証明することができる。そのため、任意の値へ署名を設定するのとコミットメントが解読されるのを防ぐために、署名の中に公開鍵を使うことが必須になる。署名に使う秘密鍵がちょうどblinding factorになる。

さらにあなたにblinding factorを明かすことなく、私がCが1へのコミットメントであることを証明したいとなった場合、あなたは

C' = C - 1H

を計算し、公開鍵C'と署名を提供するよう求め、私がそれに答えられた場合Cが1へのコミットメントであることになる。(もしくは楕円曲線の離散対数のセキュリティを破れたか)

量を明かすのを防ぐため、さらに別の暗号化構造を必要とする(リング署名)。リング署名は、2つ以上の公開鍵がある場合の署名方式で、この署名は署名者が少なくとも1つの公開鍵の離散対数を知っていることを証明する。

リング署名によって、Cが0か1のいずれかであるというコミットメントを証明するスキームを構築できる。これを"OR proof"と呼んでいる。
まず最初に私からあなたにCを与え、あなたはC'を計算する。

C' = C - 1H

続いて私が{C, C'}に関するリング署名を提供する。

もしCが1へのコミットメントだったら、私はその離散対数を知らないけどC'は0へのコミットメントとなり、私はその離散対数を知っていることになる(blinding factor)。もしCが0へのコミットメントだったら、私はその離散対数を知っており、C'の離散対数は知らない。もし他の量へのコミットメントであったなら、結果いずれも0ではないので、私は署名することはできない。

Cが0〜32の範囲にあることを証明したいといった場合、コミットメントのコレクションを送ったとして、それぞれにOR proofを行うと、

C1 is 0 or 1 C2 is 0 or 2 C3 is 0 or 4 C4 is 0 or 8 C5 is 0 or 16.

C1..5 のblinding factorを正しく選択できた場合、”C1 + C2 + C3 + C4 + C5 == C”といったアレンジが可能になる。効果的に数値をバイナリ内に蓄積し、0〜32の範囲内で5bitの数値のみ有効になる。これをもっと効果的に行うには多数の最適化が必要になる。

そのためのリング署名に関する新しい提案はBlockstreamのドラフトを参照。

CTの量の記載と仮数

量を直接表す代わりに、CTの量は浮動小数点を使って表現され、数字は10の指数で乗算される。これは小さな証明で大量の証明ができることを意味している。例えば11.2345と0.0112345では数値的には千倍の大きさがあるにも関わらず同じサイズの証明を持つことができる。

またより広い範囲をカバーするための小さな証明を可能にする非プライベートな"minimum amount"というのを送ることができる。(ユーザがminimum amountに関する情報の漏洩を気にしない場合)minimum amountは最初に最小値を減算することによって、その結果が負で無いことを証明する。

浮動小数点の仮数はバイナリではなくサイズ4のリング(base 4)を使ってエンコードされる。

最後の仮数のコミットメントはスキップが可能で、スキップした場合、後ろの実績ある数値と他の数値によって構成される。

最後に、証明でデランダマイズ署名を注意深く利用することで、コインの受信者が証明を巻き戻し、送信者から送られたメッセージを抽出することができる。受信者に価値(量)とblinding factorを通知するためにこれを使うが、参照番号や返金アドレスを通知するのに利用することもできる。

実装とパフォーマンス

結果、32bit値の証明は2564バイトであると共に、2048バイトのメッセージを伝えることができる。32bitの証明は1e-8の精度で42.94967296 BTCの範囲を、1e-7の精度で429.4967296BTCの範囲をカバーできる。IntelのCorei7-4770Rでは毎秒1300を超える32bitレンジの証明が確認できており、まだパフォーマンスの最適化の余地があると。

実装では、送信者によって制御されるパラメータとして、任意の仮数部の大きさや指数をサポートしている。パフォーマンスとサイズは仮数部のビット数で線形で、ビットの奇数番号をサポートしている。

その他もろもろ(省略あり)

Elementsでは、範囲証明は複数の秘密値の出力がある場合(手数料含む)のみ必要とされる。複数の秘密値をマージして単一の出力にするトランザクションでは、全ての入力が充分範囲内であることがわかっているため、範囲証明は必要ない。

秘密の共有に使用したスキャニングキーの共有はウォレットの監視と互換性がある。ユーザが監査役にこれらのキーを共有することで彼らに自分の取引金額を確認してもらうことができる。

今後の課題として、証明時にminimum valueをサポートすることで、単一の秘密値の出力(手数料含む)の場合には範囲証明をスキップできるようにしたり、ノードに詐欺目的の範囲証明の検証をスキップもしくは遅延することができるようにする。

Confidential TransactionsはElements Alphaで有効になっており、全ての通常の取引で使われている。

所感

  • 通常のBitcoinトランザクションで表現されるBitcoinの量(satoshiの量)をPedersen commitmentsに置き換えることで、そのblinding factorを知るメンバーのみしか実際にやりとりされているBitcoin量がわからなくなると。
  • 保存されるのはPedersen commitmentsのみなので、そこにどんな追加データを入れようとそのコミットメントのデータ量が増える訳ではないので、そういった意味でトランザクションへのデータ量の増加無しに付帯的な情報をトランザクションに追加することが実現できるみたい。
  • Confidential Transactionをサポートするためには、手数料は入力の合計-出力の合計で算出するのではなく、明示的にトランザクション内に定義できるようになる必要がある。
  • 量の情報が秘匿されると、ノードはどうやって値の検証するんだろう?と思ったが入力のコミットメントから出力のコミットメントを引いて0になるかチェックするみたい。(このコミットメントの計算についてまだあまりしっかり分かってない)。ただそのまま計算すると出力の一部をオーバーフローさせてマイナス値を取らせることで、コインの創造ができてしまう。これを防ぐのに出力の値が0〜2^64の範囲であることをリング署名をベースにした"OR proof"で証明すると。
  • 個人的に"OR proof"使った範囲の証明がイマイチよく分かってない。実際に利用してみるとわかってくるかも。
  • デランダマイズ署名って何だ?

*1:準同型暗号というのは、暗号化されたデータを元のデータに復号することなく、そのまま加算や乗算が可能な暗号化技術。例えば複数の企業にまたがったデータ分析等で、元の機密情報は暗号化したままクラウド上でデータの分析が可能になる。