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が維持されるということで、以下のように無から5コインの生成が可能になる。

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

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

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

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

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

まず最初に基本的な楕円曲線の署名から始める。公開鍵のハッシュを署名対象のメッセージとする署名を作る場合、その署名は署名者が秘密鍵を知っていることの証明になる(秘密鍵はいくつかのジェネレーターに関する公開鍵の離散対数となる)。

P = xG + aHのような公開鍵について、Gに加えてHが付加されているので誰もPの離散対数を知らない。もしaが0の場合は、P=xGとなり、その離散対数はxになるため、xを知っているユーザーはその公開鍵に対応した署名を作ることができる。

pedersen commitmentは、commitmentを公開鍵としcommitmentのハッシュ署名するだけで、ゼロへのコミットメントであることが証明できる。署名のメッセージに公開鍵を使うのは、署名に任意の値をセットして、commitmentを解くのを防ぐために必要となる。署名に使われる秘密鍵はblinding factor。

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

C' = C - 1H

を計算し、公開鍵C'に対応する署名を提供するよう求める。有効な署名が提供できた場合(秘密鍵はblinding factorのみとなるので)、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の範囲にあることを証明したいといった場合、以下のC1〜C5のコミットメントのコレクションと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.

33個のコミットメントをつくる必要はなく、足りないコミットメントはC1〜C5を組み合わせて作れる(”C1 + C2 + C3 + C4 + C5 == C”のように)。効果的に数値をバイナリ内に蓄積し、0〜32の範囲内で収まるのは5bitの数値のみ。

これをもっと効果的に行うには多数の最適化が必要になる。

ボロミアン・リング署名

最初に、新しいリング署名の公式として、特に効率的なボロミアン・リング署名を提案する。ボロミアン・リング署名だと公開鍵1つにつき32バイトしか必要なく、多くの別のリングで32バイトを共有でき、今まで提案されていたものに比べ2倍の漸近効率がある。

CTの量の記載と仮数

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

またより小さな証明でより広い範囲をカバーするため、非プライベートな"minimum amount"も送信できる。ユーザがminimum amountに関する情報の漏洩を気にしない場合(何らかの方法で既に外部に公開されてる)、これにより指数が使用されている際の最下位の桁を非0にすることもできる。minimum amountは最初に最小値を減算し、その結果がマイナスでないことを証明することでサポートされる。

浮動小数点の仮数はバイナリではなくサイズ4(base 4)のリングを使ってエンコードされる。こればbase 2より署名データを使用しない間に送られるコミットメントの数を最小限に抑えるためである。

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

最後に、証明者の作成した署名を慎重に使い、(受信者の公開鍵とのECDHの鍵交換により送金者とシークレットを共有する)コインの受信者が証明をひも解き、送信者が送信したメッセージ(プルーフのサイズの内80%)を抽出する。これをblinding factorと量を受信者に伝えるのに使うが、これは参照番号や払い戻しアドレスを送るのにも利用できる。

実装とパフォーマンス

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

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

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

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

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

ここで提示されているシステムは、基本的に新しい暗号要件には依存せず、secp256k1グループの離散対数問題と解く難しさとBitcoinの通常の署名と同様のランダムオラクルモデルのみに依存する。

range proofのサイズは小さな問題ではないが、Zerocoinのようないくつかの選択肢に比べるとまだ小さく検証も速い。これらのデータスペースはユーザー間で追加のデータをやりとりするのに再利用でき、こういった機能をパブリックなブロードキャストネットワークで求めら声もあるが正当化するのは難しい。署名と同様、range proofもブロック内の別のツリーブランチに配置しそれを認識しない旧ノードはそれらの受け取りをスキップすることができる。

最も重要なのは、このスキームはプルーニングと互換があるので、range proofも同様にプルーニングしてデータ量の増加を抑えることができる。CoinJoinやCoinSwapとも互換性があり、トランザクショングラフのプライバシーを確保するとともに、プライバシーに対するこれらのアプローチのネックを解消する。

他の提案とは異なり、これは単なる推論ではなく、Bitcoinのシステムに統合されていない純粋な暗号システムだ。

基本の暗号システムはlibsecp256k1をフォークした以下で実装されている。
github.com

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

所感

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

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