Bitcoinのソフトフォークとして導入するConfidentail Transaction

昨年Bitcoinの開発メーリングリストにポストされたConfidential TransactionをBitcoinのソフトフォークとして導入する話↓

[bitcoin-dev] Confidential Transactions as a soft fork (using segwit)

Confidential TransactionについてはBlockstreamが開発したサイドチェーンの実装であるElements Alphaに実装されている。
そもそもトランザクションの出力に量の代わりにコミットメントと呼ばれる楕円曲線上の点（公開鍵）をセットしたりrange proofや明示的な手数料など、既存のBitcoinの仕様とは異なるのでサイドチェーンによる拡張として実装されていた。

これをBitcoinにソフトフォークしようというのが↑のポスト。

トランザクションの拡張

このソフトフォークではSegwitの新しいwitness programを定義することで、Confidential Transactionを評価する仕組みを導入しようとしている。

既存のSegwitでは、トランザクションは以下のデータで構成される。

もともとSegwitでは入力のscirptSigをwitness scriptとして入力の外に分離する仕様だが、このソフトフォークではさらに、出力にも入力と同様のwitness領域を設けるようトランザクションの構造を拡張する↓

各出力の既存のBitcoinの量のフィールドには0をセットし、量の代わりになるConfidential Transactionのペダーセンコミットメントとそのrange proofをwitnessOutsにセットする。このソフトフォークに対応していないノードでは入力と出力のビットコインの量が0に見える。

こうやって、既存のトランザクションのデータ構造にないコミットメントとrange proofを格納する場所をトランザクションの別の領域に確保する。

コミットメントとrange proof以外にも、Confidential Transactionでは手数料を明示的に指定する必要がある。このため誰もが使用可能な（anyone-can-spend）出力（GCTXO）をその手数料用に作成する。

新しいトランザクションタイプ

Confidential Transactionは、blinding、unblinding、confidentialという新しい３つのタイプのトランザクションを組み合わせることで実現する。また、これらの新しいタイプのトランザクションを含むブロックは、そのコインベーストランザクションに特殊な出力を含み、さらに追加で新しい特別なConfidential base transactionを含める必要がある。

Blinding Transaction

Blinding Transactionは通常のUTXOを入力にとり、出力が秘匿化したUTXOになるトランザクションで、以下のような構成になる。

Ins: 全て秘匿されていない通常のUTXOを参照する
Outs: 
  0..N: 新しい秘匿対象の出力
    量: 0
    scriptPubkey: `OP_2 <32バイトのハッシュ値>`
    witnessOut: `0x{petersen-commitment}> <0x{range-proof}>`
  最後の出力: 
    量: 0
    scriptPubkey: `OP_RETURN OP_2 {blinding-fee-amount}`
Fee: 全入力のコインの合計

全出力の量は全て0になるため、通常のBitcoinのトランザクションとして考えると、全ての入力のコインが手数料になることになるように思えるが、このコインは秘匿化された手数料を除いて全て、このトランザクションが含まれるブロックのコインベーストランザクションの特殊な出力（GCTXO）にセットされる。

出力の最後のスクリプトはこのトランザクションがBlinding Transactionであることを示すマーカーにもなる。ソフトフォークがアクティベートされた後は、マイナーがBlinding Transactionのコインをコインベースの出力に入れずに自身のアドレスに送るようなスクリプトを書いた場合、そのブロックは無効なブロックとして扱われる。

コインベーストランザクション

Blinding Transactionを含むブロックは、Blinding Transactionの全ての手数料を新しい出力（Confidential base transaction）に送金する必要がある。GCTXOのコインは同じブロックのConfidential base transactionでのみ使用可能なためscriptPubkeyは重要でなくOP_TRUEとかで良い。

Unblinding Transaction

Blinding Transactionは秘匿化されたUTXOを入力にとり、出力が通常の秘匿化していないUTXOになるトランザクションで、以下のような構成になる。

Ins: 
  prev: CTXO[n]
  scriptSig: 空
  witnessIn: `<署名> <0x{redeem script}>`
Outs: 
  0..N: 
    量: 0
    scriptPubkey: `OP_RETURN OP_2 {アンブラインドするコインの量} {p2sh-destination}`
    witnessOut: 空
  最後の出力: 
    量: 0
    scriptPubkey: `OP_RETURN OP_2 {unblinding-fee-amount}`
Fee: 0

このトランザクションは入力のUTXOセットから秘匿性を削除する。このトランザクションの出力自体は全てOP_RETURNであるため使用可能な出力ではないが、同じブロックにGCTXOを償還するマイナーが作成したConfidential base transactionが含まれる。

Confidential transaction

Confidential transactionは秘匿化されたUTXOを入力にとり、それを別の出力に秘匿化されたまま送金するトランザクションで、以下のような構成になる。

Ins: 
  prev: CTXO[n]
  scriptSig: 空
  witnessIn: `<署名> <0x{redeem script}>`
Outs: 
  0..N: 新しい秘匿対象の出力
    量: 0
    scriptPubkey: `OP_2 <32バイトのハッシュ値>`
    witnessOut: `0x{petersen-commitment}> <0x{range-proof}>`
  最後の出力: 
    量: 0
    scriptPubkey: `OP_RETURN OP_2 {confidential-fee-amount}`
Fee: 0

入力、出力とものに全てのコインの量は0で、誰もが使用可能なスクリプトになっている。ただこのトランザクションはコミットメントとそのrange proofが有効な場合のみ有効なトランザクションと判断される。このトランザクションのマイナーへの手数料は、最後の出力で表現されている。

Confidential base transaction

上記トランザクションのいずれかを含むブロックでは、そのブロックの最後のトランザクションとして以下のトランザクションが含まれる。

Ins: 
  GCTXO[last_block],
  GCTXO[coinbase]
Outs: 
  0: GCTXO[current_block]
    量: {last_block + coinbase - unblindings}
    scriptPubkey: `OP_TRUE`
  1..N: 
    量/scriptPubkey: このブロック内でアンブラインドしたいトランザクションの出力

このトランザクションの入力にセットするのは、以下の２つのGCTXOになる。

• GCTXO[coinbase]: このブロックのコインベーストランザクションのGCTXO。コインベースのGCTXOには、そのブロック内のBlinding Transactionで秘匿化した全てのコインの量がセットされている。
• GCTXO[last_block]：この前のブロックのConfidential base transactionの０番目の出力（そのブロック内の秘匿化された量からアンブラインドしたコインを除外した量）のコインがセットされている。

Fee: このブロック内の全Confidential transactionの`OP_RETURN OP_2 <手数料>`で表現される手数料の合計

このトランザクションはブロックを作ったマイナーによって作成され、ブロック内の全Confidential Transactionの手数料を入手する。

まとめ＆所感

ざっと見ただけだと分かりにくいけど、秘匿したコインがブロックチェーン上で無くなることなくブラインド/アンブラインドできるようになってる。

簡単に言うと、コインを秘匿化したい場合はBlinding Transactionを作成するが、このトランザクションの出力は全て量が0（秘匿化された量はちゃんと別にある）になるので一見コインが全て手数料になってしまうように思えるが、このコインは全てBlinding Transactionが含まれるブロックのコインベーストランザクションの特殊な出力（GCTXO）の量として加算される。そしてこのGCTXOのコインは、同じブロックの最後のトランザクションであるConfidential base transactionの入力になる。

秘匿化されたコインは基本的に全てGCTXOが保持することになり、ブロック内にUnblinding Transactionが存在する場合は、アンブラインドするコインをConfidential base transactionの１番目以降の出力にそれぞれ通常のUTXOとしてセットする。こうするとConfidential base transactionの0番目の出力（GCTXO）にはコインベースのGCTXOからアンブラインドした量を引いいた量がセットされる。がもう１つ前のブロックのConfidential base transactionの0番目の出力のコインの量も加算される。

こうやってブロックチェーン内のコインベースと最後のConfidential base transactionのGCTXOで秘匿化されたコインのバランスを担保している。

• Confidential Transactionを新たなwitness programを定義して（なのでSegwit前提）Bitcoinのソフトフォークとして導入するアプローチ。
• 既存のSegwitのwitnessは入力の署名を分離するが、出力用のwitness(witnessOuts)を用意し、そこにコミットメントとrange proofを格納する。
• Unblinding Transactionの出力のscriptPubkeyが全てOP_RETURNなのは如何なものか。
• 既存のBitcoinのプロトコルに存在しない秘匿した量をどうやって整合性とるのか疑問だったけど、コインベーストランザクションとConfidential base transactionでその整合性をマイナーに取らせていて、秘匿された量が勝手に消えない仕組みになってる。この辺はよく破綻しないよう考えたなー。
• 結構マイナーがやらないといけないこと多く、それに対するインセンティブも無いので、これをソフトフォークとしてアクティベートするのは難しいんじゃないかな。
• MLにはこのポストがあるだけで、特にレスは付いて無いようで、このソフトフォークの仕組み自体は現在進んでいないのか？
• 量の代わりにコミットメントをセットすることで出力のサイズが28バイト増えるのはまだしも、witnessOutsを導入するとは言えやはりrange proofの2.5KBというサイズがネックだと思う。

Confidential Transactionのrange proofの仕組み

techmedia-think.hatenablog.com

↑でConfidential Transactionのコミットメントの作成と検証をしたので、続いてrange proofについて見てみる。

Confidential Transactionではトランザクションの各出力にコインの量ではなくコミットメント（楕円曲線上の点）がセットされるようになり、それにより取引されるコインの量が秘匿され、検証者は楕円曲線上の点を計算することで入力と出力のコインのバランスが取れていることを検証する。

ここで１つ問題になるのが、コミットメントの計算時に非常に大きな値を設定することを値をオーバーフローさせ、負の値として動作する場合。この場合マイナスのコインによりバランスの計算が行われるため、結果的に何も無いところからコインを生み出すことができてしまう。

この問題に対応するため、コミットされた各出力の値が、正常な（0〜2⁶⁴）範囲の値であることを証明する仕組みが必要となり、この証明をrange proofと呼ぶ。

コミットメントとリング署名

まずコインの量へのコミットをどうするかについて説明する。例えばコインの量が１である場合、その量へのコミットは、まずコミットメントCを使って以下のC'を計算する。

C' = C - 1H

元々のCが以下だとすると（xがblinding factorで1がコインの量）

C = xG + 1H

C'は結果的に↓になる。

C' = C - 1H = xG + 1H - 1H = xG

ここでC'について、その秘密鍵はblinding factorであるxなのでHが無くなった今、xを使って普通にsecp256k1の署名を生成でき、公開鍵C'に対する有効な署名が提供されれば、Cがコインの量１に対するコミットメントであることの証明になる。

ただ単純にこの証明をしては、コインの量が明らかになってしまうので意味が無い。つまりコインの量を秘匿した状態でも実際のコインの量に対するコミットができる仕組みが必要で、そこで利用されるのがリング署名になる。

リング署名は、2つ以上の複数のキーペアで構成される公開鍵のグループの中から、ある１つの公開鍵に対応する秘密鍵を使って署名をするが、グループ内のいずれかの公開鍵に対応する秘密鍵で署名されたことは分かるが、どのキーペアで署名されたかどうかを特定することはできないといった署名スキームになる。

Confidential TransactionではC'のような量へのコミットメントと、リング署名を組み合わせることで、量を秘匿したまま量が有効な数値の範囲内であることを証明している。

量の異なるC'のような量のコミットメント（公開鍵）を沢山作って、その中のいずれかに実際コインの量が１つ含まれている。blinding factorとコインの量を知っている取引の当事者であれば、正しいコインの量のコミットメント（公開鍵）に対応する秘密鍵でリング署名を生成でき、その署名をrange proofとしてトランザクションの出力にセットすることで、その出力のコインは正しい範囲内の数値であることを保証できるようになる。

これを単純に実装しようとすると、Rubyでring_sigというCryptoNoteで定義されたワンタイムリング署名を実装したgemを使うと以下のように量へのコミットメントの作成と、署名及びその検証ができる。

require 'ecdsa'
require 'securerandom'
require 'ring_sig'

# G及びHは前回のcommitment作成記事のコードと一緒

hasher = RingSig::Hasher::Secp256k1_Sha256

# blinding factor
x = 1 + SecureRandom.random_number(G.order - 1)

# 実際のトランザクションの出力にセットするコミットメント
output =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1000)

# 1000の量にコミットするコミットメントは output - 1000Hになるので
amount_commitment = output + H.multiply_by_scalar(1000).negate

# ↑は元がxG + 1000Hなので、amount_commitment＝(x)Gになるため署名に用いる秘密鍵は↓
key = RingSig::PrivateKey.new(x, hasher)

# 偽の量へのコミットメントを３２個ほど用意
foreign_keys = 32.times.map{
  random_amount = SecureRandom.random_number(10000000) # 10000000以下で乱数を生成
  commitment = output1 + H.multiply_by_scalar(random_amount).negate
  ECDSA::Format::PointOctetString.encode(commitment).unpack('H*').first
}
foreign_keys = foreign_keys.map{|s| RingSig::PublicKey.from_hex(s, hasher)}

# 秘密鍵で署名
sig, public_keys = key.sign('message', foreign_keys)

# 署名の検証
sig.verify('message', public_keys)
=> true

上記は３３個の公開鍵を使ったリング署名だが、この署名値（＝range proof）sigの値は以下のように2317バイトと、普通のECDSAの署名などに比べてかなりサイズが大きくなる。

308209090421023d249ef23a11e1fce8c1c539128d641b7de92edea24ceda1b17277d496ccb7e4308204720221008ebbc436681a401b4dfeadc3ec916a37545479286d1ad142a543ec6293103257022100899a7a74d109907bb70dd9588a72b125a0cb6d12e001f505910a03f1973406e802200a0aebe3c81d2a5ec8d790476c146fe567154f0f173d25479174699e2af92913022100aaafff08304a2c589f0df9b13a3b047cba57acd714184ac56173831fa8f9f73c02203a1d0afe2e50ec05ca701c88d3555700f87fa79d47bc8e7c8be1852c2e64d30e0220369812a49f7f6c649483863fcfe2c0881c66ae59c042e8f2c320815c20816efa02204935d2790b2af6a99fa292f308aee25cf60c506f2327b77eb77abde830b6e352022100d8cff770a6917aac410ff4194256efc5c59838dd78d031db537bc4f5e12a38fc022100d7ae003935b1a6d274c2601c6aaa75e0cc9e3fd6c4a1d8846968dc365a107484022075c477ad4793db07bceb6c378314df3b1039b856999f6d6f065f91f368b71347022100b4d0dac8d1b8b08c022845812c8573462fe419f3adc63b3c9fb1b42b2741e5bd022100e8e2776098157914ec325df278224fd397bb5a69085bbf4de5ae0ffdf0bf2532022100fffe317a93d788f39f4cebafa87f4d58af95a7c61e684738ec8dbdf1a2485011022100bc86a5f18a42a8faa28d0049ae3a39bccd2857b2d0477a84fd4f5f30fe01b6f502200dd450ca1ba49a7627eff2cd92c57a529d1fbee11c04c34a88b333245e2ab816021f65594deaa1fbdf1e8e964e9a8d65a82107af6e9bd81016eb09a0209c1260ab0220590e85563c7bb046cf1fe4243b275b58c0863989afd037ad7b5574dea835340c022025e0a374d4132ce5c229b39120fa3c3ff429bbf8f3765c9a0fbbd4ea7144ea5e022100d0bd1c0a8ca20d0ab80d7f9f65d4e3764325d2a4982d5d638b00aa679f1619fd022076f7fac091ca610aef6075f147249a6eca7fa9134727acedd00b8b02ddc33526022100e92f759ba305852d1700fb695c5aa602f644cf6f3f3aff02041ea38cf5e8f800022100aa1e2fb3fed1da7a803f9295701758f35f73f2ea5aa1b8bc0d6d3c05ac1078a3022100d887f4cd108e0f74c3eff611f4d2119338cda40e0aa8af997d48ce9c813189ec02207d091e00e372097c8875945164cc58083b4e49d73528d087138ce4faa500811902210080d14fa2b315cea7bbeaf6c9f0054495293de5ff1975e27b3276f10a96e6dac702205ec90a62465e1c1d46a3528a7650b084661acc5b43b0e8b0dfa5c6a452dd6f05022100a3664817eab64c4a9f576918890f70953d9fe8e4ecfbe91f26a6df221f4cfde202201c61d9b568413e18c361be555bafbed1ba923e32d01d494d8df33fc75bbfda9f022100a5dfd562402d24102bd97179ff1287b30912d70f958f03abeaf74061b6ebcb3c02201c3ca327707dd31dfc82b66e5670d43a9205096af0d60e39d5b2c2fe53777978022100d6792ee73368a6e0096b5e0ca4722aafdf0e33155285ce02b99d15851b4a3f1802202dc698c31894b00569945aa38b6862df0c6c95bb488af7c61830e28e50fbaf060220647fe6e12ab00b2182b7a7d049c9d836426497a77143b445a0c11dba45fccc973082046c022100923f807c4dca60d9f3f4b0d066a0f4921dbfb630e2e7941e7bcbde4e1ee9355102203cc56b92661b414d6180a6c7f8a28454098f95a40e01803389744dabb4d5a1ca022032ab2f64698cf78d58a50e4dec775082233bf87a82cbd29fa23445736ab45df7022042ad8bca0b6ff9271288765aa96b097746376c8b3a54cb9dbe9dee30106f69d3022100df3042a03714e8121cf006bc5328ed6241ab135e9084304856c67d5c4490b7f6022034d3245d70a993f15a55d9a718de528b3a1d4ba04b4a2ebd6899d55dfad3abce02206de7ef2041f6aa53725cc5d214725165ce602efb91cabf7ffb8a77469c90d214022020b2908567f9e8c97a8701ff91d1b18bc69f03531ac041656b14a613d63c50300221009afcf632c51788898389c2c0919828f2b86f218a763a3d6e074de61af2168963022100d3c38252bc504d8a9b141af3aa71acd0b39ee9d7b699f465120fe1dc6a15b6d50220505457bb089893986b4dd6ef561929b7703ec5fb2fe614b0983310775aa0dbc3022100cbfe697aa76c70a26b43e755afa1abb8ddff76b7c8d911a82c3d9a77116b1e1d022100e94addabbdc03e51cdc8d9369a6a2758d487497fcfa8cf8b5f2544b5d2116743022076c0368f3dcc63225d5d78bfadd21b2f516b52190ea76c7dc69de7865e1f30b402203886f5031eae7b7dfdc5bef8bc34d09f505662ac8e4970bde499e30cecd785f502207d9e3c25ab075114033744302c9f32f67f63396860a3a0b4c6614a365ff1588302205e112337977b822304abdbe00a12554a3eb7a0d8c77af569e66bb859f4702996022049181783f268be175ad6e23ff39b2c68fbf00e8adae2bf7a7405b39018a7f87402206bc5fc87deceb088c112f88e1af8392439861dff8c3bb78c1ae5426f64f4226c022079756ac5f53bc6e35a9690ddb5ece09fb6850cb544be30958207b7be284486e7022065ade8c6e7d395d9c4668a7008d4b6420e57608539730ba86672d79362cf146a02203c86f08d43447868e86e655612e8b437fd79edd3f191121214c424ec55cc03a2022100ac4dc34a34f3419ec7aaebfc47d72bb21f43b40ba7fc44a71cd4e32dfc3cc4dd022100aae8a64cac6a75c1a1eda86cbb482d86dee07433db89e65344e2b884c7feb9a70220540af0a2d9ac11e688173654b5e61dcb340d4a4850166cc07978c0d8c2251da9022100d5b9b99b25fcf1f1fbb08e08e7852b14ea5065a11f88b63b0233df6c90e4e8a5022100e0e6ca4919e767e34cecbb23acfbbcca1bc4194fdf6f6b01312ce062911a46bc02204f93b2c204ee20d3dd15e2d69b78128206e56eb038893dc070721657b3b7c95a02201986320ce60cf364f38625e1ddafe2643919c62f69809f74c72e2212b7f49df4022042d02beb2d14f47440ce131feb27038d55318e9331d633d9056c6ec9e7c3914702207aa655bb5b00cad84ad2050bbed33759c8de5b3d7d9f0e0a637566cf52315dcf021f4f4e660a9753b2960c9fe9ae0160bf7438eadd19ed99ed4cf113ef1e4acbf7022100ffa030ddef18eef1783a9661b78dd0444af40d93004b921cfba641d3d531e3c5

これは候補となる公開鍵の数が増えれば、その分署名値のサイズも増えることになる。

また↑はシンプルなrange proofの表現をしただけで、実際のConfidential Transactionでは、量を直接指定するのではなく浮動小数点を使って表現したり、Gregory Maxwellが新しいリング署名のスキームとしてBorromean Ring Signaturesを提案していたり、様々な最適化がさらに加わっている。

ただ、それでもrange proofのサイズは2.5KBほどらしく、出力１つにつき2.5KBのrange proofがあると考えると、ブロックチェーンのデータも結構なボリュームになると思われる。
アダム・バックの2KBまで削減できるという発言もあるが、それでもまだ大きなサイズだ。

Confidential Transactionのcommitmentを生成してみる

以前、Confidential Transactionのホワイトペーパーを読んだ↓

techmedia-think.hatenablog.com

Confidential Transactionでは、トランザクションの出力にコインの量をセットする代わりに、Pedersen commitmentを楕円曲線に適用したコミットメント（この場合は楕円曲線上のある点）をセットすることで、トランザクションで取引されるコインの量を秘匿している。

ホワイトペーパーを読んで概要はなんとなく分かったまま放置してたので、実際にコードで検証してみる。

commitmentの生成

このコミットメントは

commitment = xG + aH

の式で定義され、xが量の秘匿のために用いられるblinding factorでいわゆるシークレットに該当する。実際に取引するコインの量はaになる。
この式はxとGからなる楕円曲線上の点と、aとHからなる楕円曲線上の点を加算した新たな点を算出し、この点をコインの量の代わりにトランザクションの出力にセットしている。

Hの算出

ここでGは楕円曲線のベースポイントで、HはGをエンコードして生成するもう１つのベースポイントである。Hは以下の式で楕円曲線上のX座標を計算し、そこからY座標を求めることで算出でき、これも楕円曲線上の点になる。

HのX座標 = SHA256(ENCODE(G))

Rubyのecdsa gemを使うとこのX座標は以下のように算出できる。

require 'ecdsa'
require 'securerandom'

G = ECDSA::Group::Secp256k1

encoded_g = ECDSA::Format::PointOctetString.encode(G.generator)
coordinate_x = Digest::SHA256.hexdigest(encoded_g).to_i(16)
=> 36444060476547731421425013472121489344383018981262552973668657287772036414144

X座標が分かれば、secp256k1の楕円曲線上のY座標は以下のように算出できる。ただ楕円曲線はX軸関して対称であるため、Y座標の候補は２つある。

P = G.field.prime

coordinate_y1 = G.field.power((coordinate_x**3 + 7) % P, (P + 1)/4)
=> 93254584761608041185240733468443117438813272608612929589951789286136240436011

coordinate_y2 = coordinate_y1 * -1 % P
=> 22537504475708154238330251540244790414456712057027634449505794721772594235652

Confidential Transactionを実装しているBlockstreamのサイドチェーンElements Alphaのソースを確認すると後者のY座標の値が使われていたので、そちらを使用して、Hの楕円曲線上の点は以下の座標になる。

• X座標：36444060476547731421425013472121489344383018981262552973668657287772036414144
• Y座標：22537504475708154238330251540244790414456712057027634449505794721772594235652

# ２つめのベースポイントH
H = ECDSA::Point.new(G, coordinate_x, coordinate_y2)

ちなみにこのHをGから導出する固定値でなく、アセットを表す識別子としてアセット毎に任意に生成できるようにしたのがConfidential Assets。

Hの算出方法を確認するため↑の計算をしたけど、Hは固定値なので以下のように定義してそのまま使うのでも良い。

# ECDSA::Grou::Secp256k1 = G とgenerP = G.field.primeatorのポイントが違うだけのGroupを定義
module ECDSA
  class Group
    Secp256k1H = new(
        name: 'secp256k2',
        p: 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_FFFFFC2F,
        a: 0,
        b: 7,
        g: [0x50929b74_c1a04954_b78b4b60_35e97a5e_078a5a0f_28ec96d5_47bfee9a_ce803ac0,
            0x31d3c686_3973926e_049e637c_b1b5f40a_36dac28a_f1766968_c30c2313_f3a38904],
        n: 0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFE_BAAEDCE6_AF48A03B_BFD25E8C_D0364141,
        h: 1,
    )
  end
end

コミットメントの作成

blinding factorをx、取引するsatoshiの量をaとした時、そのコミットメントは以下のように算出できる。

# blinding factor
x = 1 + SecureRandom.random_number(G.order - 1)

# コミットするコインの量
a = 10000

# コミットメント
commitment = G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(a)

どうしてGとHの２つのベースポイントが必要かというと、もしHでなく同じGを使うと、blinding factorの値によって実際のコインの量をなんとでもコントロール出来てしまうからで、そのためblinding factorとコインの量を表現する際のベースポイントは必ず別のポイントである必要がある。

秘匿された量の検証

Confidential Transactionでは、↑のように出力にセットするのが明示的な量ではなく、コミットメント＝楕円曲線上の点になる。この場合実際にいくらの量がやりとりされているかは、blinding factorの値を知る取引の当事者しか分からず、blinding factorを知らない他の参加ノードは実際の取引量は分からない。

ただ、取引量がわからなくても、トランザクションの入力と出力でコインの量が正しくセットされているか＝入力に使われているコインの量を超えるような出力がセットされていないかについては、blinding factorを知っている・知っていないに関らず誰もが検証できる必要がある。

この検証は、トランザクションの入力に使われている全コミットメントと出力の全コミットメントに対し以下の式が成立すれば入力と出力でコインの量は等しいことが確認できる。

（入力１のコミットメント + 入力２のコミットメント... ） - （出力１のコミットメント + 出力２のコミットメント...） = 0

ただこの時、手数料が問題になる。Bitcoinのトランザクションでは入力-出力の差が手数料として使用されるが、Confidential Transactionのように量が秘匿されている状態では手数料がいくらかは分からないので、手数料は明示的にトランザクションにセットする必要がある。

実際にこの式が成立するか検証してみよう。とりあえず手数料を考えず、全入力のコミットメントを加算した点から全出力のコミットメントを加算した点を引いたものが0になれば良い。

楕円曲線上の点の減算は、減算したい点についてX軸について対称の点を計算し、その点を加算することが減算になる。(x, y)に対して(x, -y)を作れば前者の点を使った減算ができる。ちなみにこの両者を加算すると無限遠点となり、この場合、無限遠点はこの演算に関してゼロとして機能する。そのため、全入力のコミットメントから全出力のコミットメントを減算した結果、無限遠点となればイコール0と判断できる。

1500のコインをもつ1つの入力と、1000と500の2つの出力を例に計算してみる。

この場合入力のコミットメントは

# blinding factor
x = 1 + SecureRandom.random_number(G.order - 1)

input =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1500)

となる。同じxを使った出力のコミットメントは単純に考えると以下のようになる

output1 =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(500)

が、この出力は正しくない。このコミットメントを使って全入力のコミットメント-全出力コミットメントを計算するとG.generator.multiply_by_scalar(x)の分だけ余りが発生し0にはならない。

そのため、こういうケースでは計算が合うように出力のblinding factorの値を選択する必要がある。
今回は簡易的に計算するため、それぞれのflinding factorを以下のように調整した値のコミットメントを作成した。

output1 =  G.generator.multiply_by_scalar(x / 2) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x - x / 2) + H.multiply_by_scalar(500)

実際にblinding factorをどのように設定するかは、トランザクションを作成するユーザーが全入力のコミットメント-全出力コミットメント＝０になれば後は自由に決めて良い。

実際にこのコミットメントを持つトランザクションが与えられた際、当事者以外は以下の検証をすると入力と出力が同じ量であるか検証できる。

input =  G.generator.multiply_by_scalar(x) + H.multiply_by_scalar(1500)

output1 =  G.generator.multiply_by_scalar(x / 2) + H.multiply_by_scalar(1000)
output2 =  G.generator.multiply_by_scalar(x - x / 2) + H.multiply_by_scalar(500)

outputs = output1 + output2

result = input + outputs.negate # ECDSA::Point#negateは、その点のX軸に対して対象な点を算出するメソッド

result.infinity?
=> true

実際に入力と出力の関係が1:1になることはほとんど無いと思うので、入力のblinding factorとその入力が持つ量と出力先の数を踏まえて、新たに出力で使用するbliding factorを計算する必要がある。

ECDSAの脆弱性を利用した未承認トランザクションの二重使用を防止する仕組み

Bitcoinのトランザクションは10分に一度作成されるブロックに取り込まれる。最近のメモリプールの状況では10分後に取り込まれればラッキーな方で、まだ時間がかかることもよくあると思う。
その一方でECサイトや実店舗でのBitcoin決済の導入は進んでいる。リアルな店舗で決済する際に10分以上待たされてはBitcoinを使って決済しようとは思えないから、こういった店舗では、決済するトランザクションがブロードキャストされれば決済されたと判断しトランザクションがブロックに取り込まれるまで待たずに決済をしている。つまに未承認のトランザクションで決済している。

この場合、もし二重使用が発生すると店舗側は決済した金額を受け取れない事態が発生する。まぁその辺のリスクを考慮してBitcoin決済ができるのはある一定額までで、そういう事態が発生した場合は決済会社が保証などしているのだと思う。

そんな未承認トランザクションの二重使用を防ぐ仕組みについてバルセロナ自治大学のホワイトペーパーが公開されていたので見てみた↓

http://eprint.iacr.org/2017/394.pdf

二重使用を防ぐ基本的な仕組み

二重使用はその資金を二重使用できないようなトランザクションに送る初期化フェーズと、そのトランザクションを使って決済を行うファストペイメントフェーズの２つのフェーズからなる。

初期化フェーズ

アリスはまず自分のUTXOをFR-P2PKの出力に送るfunding transactionを作成する。このトランザクションを作るためアリスは、ランダムな整数値kと公開鍵PKa（対応する秘密鍵はSKa）を選択し（＝決済に使用するキーペアの生成）、FR-P2PKの出力（具体的なスクリプトは後述）をセットし、そこにいくらかの資金を送金するトランザクションを構成する。アリスはfunding transactionをブロードキャストし、トランザクションがブロックに格納されたら初期化フェーズが完了する。

FR-P2PKというのはfixed-r pay-to-pubkey scriptの略で、Pay-to-Pubkeyを少し変形させたスクリプトになる。Pay-to−Pubkeyの場合、そのスクリプトを使用するには署名をscript_sigにセットすればいいけど、FR-P2PKはその署名が特定の値rを使って生成される必要がある。FR-P2PKではECDSAの脆弱性を逆に利用して二重使用から保護する。

つまり、FR-P2PKを使用するトランザクションを作り、更に同じFR-P2PKを二重使用するトランザクションがブロードキャストされた場合、ネットワーク上には

• 同じ秘密鍵
• 同じ乱数
• ２つ異なる署名対象のメッセージ

から生成された署名が２つ存在することになり、ネットワークに参加しているノードであれば誰でもそこから秘密鍵を計算することができる。そのため二重使用しようとしたユーザーは、ネットワーク上のノードに計算した秘密鍵からFR-P2PKの資金を奪われるというリスクを考慮するから、二重使用するインセンティブが働かなくなるという仕組み。

この脆弱性から秘密鍵を導出するのは簡単でRubyでecdsa gemを使って書くと↓のように書ける。

※ 署名値のSが-S mod Nの場合もあるので、ちゃんと計算する場合はそこも考慮する必要はある。

Fast paymentフェーズ

実際に決済する際は、アリスは初期化フェーズで作成したfunding transactionのFR-P2PK出力を使ってボブにBitcoinを送るfast-payment transactionを作成する。このトランザクションのscript_sigが有効であるということは、アリスが公開鍵PKaに対応する有効な秘密鍵SKaと初期化フェーズで生成したkの値を持っていることの証明になる。アリスは作成したfast-payment transactionをBitcoinネットワークにブロードキャストする。

ボブはメモリプール内にある受信したfast-payment transactionを確認すると、このトランザクションで使用されるUTXOがFR-P2PK出力であることを検証することができる。FR-P2PK出力であることが確認できれば、ボブはアリスが二重使用しようとすると彼女が自分の資金を失う可能性があることを認識する。

アリスがfunding transactionの資金を二重使用する場合、FR-P2PK出力を二重使用するトランザクションを新たに作成する必要がある。このトランザクションの署名はもちろん有効な署名でないといけないので、SKaと初期化フェーズで選択されたkを使った２つ目の署名を作ることになる。つまり二重使用のトランザクションを作るということは、同じ秘密鍵SKaと同じrをを使った異なる署名を作ることになる。署名されるメッセージ（トランザクションダイジェスト）も異なるので、この場合ECDSAの、同一の秘密鍵によって同じ値kで行われる２つの署名があれば、署名に使用された秘密鍵を導出するのに充分なヒントになるという脆弱性に該当する。

そのためアリスは二重使用トランザクションをブロードキャストすると、自分の資金を失う危険性がある。これはfunding transactionとfast-payment transactionの両方を受信するオブザーバーがアリスの秘密鍵SKaを導出できるため、結果 FR-P2PKの出力をオブザーバーに送金する第３のトランザクション（ペナルティトランザクション）を作成することができる。

抑止的な保護の仕組み

↑の仕組みには明らかな欠陥がある。アリスがボブの店で↑のファストペイメントを行い商品を購入するとする。ボブはトランザクションを受信すると商品をアリスに発送する。アリスは商品を受取ると二重使用を試みるかもしれない。オブザーバーがfast-payment transactionと二重使用トランザクションの両方を監視しているケースでは、ペナルティトランザクションを作成し、それが先にブロックチェーンに格納されるように調整する（手数料などで）。この場合ペナルティトランザクションがブロックに入れられるとアリスは資金を失うが、ボブも支払いを受け取れない。このようなケースであればボブは、商品を発送したが、それと交換にBitcoinを受け取ることができない。結果的にアリスはBitcoinをボブではなく第三者のオブザーバーに支払ったことになり、オブザーバーがトランザクションの総量を手に入れる。結果的にアリスが二重使用をするインセンティブは働かないので、この提案した方法は二重使用を防ぐかもしれない。

しかし、方法を少し変えるだけでアリスに二重使用を思いとどまらせる方法がある。それはfunditoin transactionのFR-P2PK出力に支払いに使う金額より一定の係数λだけ高い金額をセットすることを強制する方法だ。この場合、アリスが二重使用を試みると、支払金額より多いFR-P2PK出力分のコインをオブザーバーに全て持って行かれる可能性があり、商品をボブから入手したとしても、係数λの分だけアリスが損をすることになる。そのため自分が損する可能性があるのにアリスは二重使用を試みるはずはない。

FR-P2PKスクリプトの構成

Bitcoinのトランザクションの署名データは、以下のDERエンコーディング仕様で構成されている。

0x30 [total-length] 0x02 [R-length] [R] 0x02 [S-length] [S] [sighash]

techmedia-think.hatenablog.com

この署名データのフォーマットを考慮した上で、FR-P2PKの出力は以下のように定義される。

ScriptPubKey: OP_DUP <pubKey> OP_CHECKSIGVERIFY OP_SIZE <0x47> OP_EQUALVERIFY <sigmask> OP_AND <r> OP_EQUAL
ScriptSig: <sig>

• <pubKey>: 署名の検証に使われる公開鍵
• <sigmask>: 71バイトのバイト列で、DERエンコーディングされた署名データ(sig)のrの位置と最後のSIGHASH_TYPEの位置に1がセットされ、その他の部分には0がセットされたビットマスクになる。
• <r>: 71バイトのバイト列で、整数rのDER形式の値と、SIGHASH_TYPEには0x01が、それ以外の箇所は全て0がセットされている。

このスクリプトを実行すると、まず署名が<pubKey>に対応した有効な署名か検証が行われ、続いて署名のサイズを検証する。その後<sig>と<sigmask>のビット単位のANDを計算し、その結果が<r>と同じかチェックされる。このようにして署名データに固定値のrを強制している。

ただ、このOP_ANDというopcodeはBitcoinの標準仕様では無効化されているものなので、このスクリプトを現在使用することはできない。

所感

• ECDSAの脆弱性を利用するという逆転の発想感は面白い。
• オブザーバーの存在や、現実的に全てのノードがオブザーバーになるわけでもないのと、二重使用のトランザクションがブロードキャストされそれをオブザーバーが検知してからの対応になるという仕組みを考えると、完璧に二重使用を防げるものではないので、そういうリスクを取らせることで二重使用するインセンティブを排除していくのだろう。
• 初期化フェーズでfunding transactionをブロードキャストする必要があるので、最終的に決済するのに２つのトランザクションのブロードキャストが必要になる。この部分の手数料や手間とか考慮すると残念ながらあまりカジュアルに使える方法ではないと思う。
• 実現する場合は、現在無効化されているOP_ANDが再び使えるようになる必要がある。

Strong Federationsの概要

Blockstreamが今年に入って公開したStrong Federationsのホワイトペーパーに記載されている技術仕様についてを読んでみた↓

https://arxiv.org/pdf/1612.05491v2.pdf

もともとBlockstreamのサイドチェーンのホワイトペーパーのFederated Pegでは、信頼できる連合の職員がメインチェーンとサイドチェーン間のコインのロック/アンロックをする構成になっている↓

techmedia-think.hatenablog.com

Strong Federationというのは、このFederated Pegに加えて、Federated Blocksigningという仕組みを追加で定義した内容みたい。

Federated Pegの流れ

Federated Pegの基本的な流れが↓

1. ユーザーは自分のアセットをメインチェーン上で特殊なアドレス宛に送付する。このアドレスはサイドチェーンがアセットが返却されたと通知されるまでアセットをロックしておくよう設計されている。
2. ユーザーはFederated Pegのinチャネルを使って、メインチェーンでアセットが凍結されていることを示す情報をサイドチェーンに埋め込み、サイドチェーン上でそのアセットを利用できるよう要求する。
3. ユーザーがメインチェーンでロックしたアセットと等価なサイドチェーン上のアセットがアンロックもしくは新規作成され、ユーザーはそのアセットを持ってサイドチェーンに参加できるようになる。
4. ユーザーがサイドチェーン上のアセットもしくはアセットの一部をoutチャネルを介してメインチェーン上に戻したい場合は、メインチェーン上の出力情報をサイドチェーンに埋め込む。
5. Strong Federationが合意すると、Federated Pegはサイドチェーンで示された数量分、メインチェーン上のアセットの凍結を解除する。

Strong Federationを使ったサイドチェーンの改善

Bitcoinにおいては、ブロックへの署名＝マイナーと呼ばれる署名者のセットを使った動的メンバーシップマルチパーティ署名と捉えることができる。ただBitcoinの場合（10分という）レイテンシーの問題があり、Federated Pegのモデルでは、この動的メンバーシップマルチパーティ署名の部分を、固定メンバーによるマルチシグで代替してサイドチェーン側のブロックの署名（ブロックの作成）をしている。

Strong Federationというのは、連合のメンバーがメインチェーンとサイドチェーンの間のプロトコルアダプタとして機能するようフェデレーションされたサイドチェーンで、以下の特徴がある。

• 第三者の許可を必要とせずにチェーン間の資金移動が可能
• フェデレーションが失敗した場合にはメインチェーン上に資金を戻す仕組みがある

連合のメンバーも、ユーザーの資金を直接コントロールすることはできない。

Strong Federationのネットワークオペレーターは、２種類の職員から構成されている。職員というのは、特定の条件が満たされた場合に定義された操作を機会的に実行するエンティティのこと。セキュリティ強化のため、特定の操作は複数のエンティティ間で分担され、あるエンティティが攻撃されてもその損害を限定的にできるように設計されている。Strong Federationでは、職員がブロックチェーン間のアセットの移動のコントロールとサイドチェーン側のコンセンサスルールの実行権限を持っている。この職員は以下の２種類に分けられる。

• Blocksigner
  サイドチェーン上のトランザクションのブロックに署名し、コンセンサスの履歴を定義する。
• Watchmen
  メインチェーン上のトランザクションに署名することで、サイドチェーン上のアセットをメインチェーンに移動する責任を持つ。

この２つのコンポーネントは独立していてもいい。Blocksignerはブロックチェーンのコンセンサスを生成し、サイドチェーンの台帳を作っていく。Watchmenはブロックチェーン間でアセットを移動するときだけオンラインになればいい。（極端な例では１日１回オンラインになって、溜まったアセットの移動要求を処理するのでも良い）

Strong Federationsの技術要素

Strong Federationをサポートするには、Federated PegとFederated Blocksigningの２つのタイプのフェデレーションを開発する必要がある。

Federated Peg

サイドチェーンのホワイトペーパーでは、Bitcoinのコンセンサスルールを変更することなく、サイドチェーンを展開する方法について提案されている。ホワイトペーパーでは、サイドチェーンは5人のうち３人の職員が同意してブロックへの署名・検証、ペグを行うモデルになっていた。

Federated Pegは職員を使って２つのチェーン間でアセットを移動する仕組み。職員は少なくとも２つのチェーンを監視し、チェーン間のアセットの転送を検証する。Strong Federationの基準を満たすため、地理的及び管轄的に分散されたサーバを使用して職員のネットワークは作られる。

Federated Pegのメンバーは、Bitcoinとサイドチェーンのノードを実行するセキュアなサーバーと、クロスチェーンのトランザクションを作成、管理するソフトウェアを操作する。各サーバは暗号鍵とその署名を管理するハードウェアセキュリティモジュールを持つ。モジュールの仕事は、主にネットワークのセキュリティを守ることで、compromiseを検知すると全ての鍵を削除し、設計通りネットワークをフリーズさせる。１人もしくは少数の職員が攻撃された場合でも、その耐タンパー性のあるハードウェアに侵入されていても、他の職員に影響が無ければシステムは影響を受けない。federated pegのシステムを改竄するためには、主要なBlocksignerとWatchmenのcompromiseが必要になる。それでもブロックチェーンのデータはノード間で常に共有されているため、すぐに改竄は発覚する。不適合なブロックが公開されるとすぐにBlocksignerの過半数がcompromiseであることが分かる。過半数のWatchmen が安全であれば、サイドチェーン上のアセットがありながらメインチェーン上でアンロックされれることはない。

ビザンチン耐性

Bitcoinのマイニングスキームの最も重要な点の１つとしてビザンチン耐性が挙げられる。悪意あるマイナーが過半数を超えない限り、履歴の改竄やトランザクションの削除などは行えない。

Bitcoinは、全てのマイナーが平等な立場で参加でき、大多数のハッシュパワーに裏付けされたチェーンの有効性によってこれを実現している。過半数のハッシュパワーを持たない攻撃者は履歴を書き換えることはできず、計算リソースを投入しても無駄になる。これによりマイナーに正直な多数派に加わることを促し、攻撃者の負担を大きくしている。しかしこの仕組みでも、１０分に１度のブロック生成でネットワークの遅延によりチェーンの一時的なフォークが発生し、チェーンの再編成リスクは残る。

Strong Federationsにおけるコンセンサス

職員の経済的な利益と連合の正しい機能と一致させることが重要で、重要な価値を持つ商業的なサイドチェーンをサポートするのにボランティアの無作為な組み合わせに頼るのは明らかに間違いだろう。フェデレーションは各参加者がフェデレーションによって保持されているのと同程度の価値を持つ場合に最も安全になる。これはビジネスでよく見られるパターンで、インセンティブはエスクロー、機能的な配分または保証債権や保険証券などの外部の法的構成物を通じて調整できる。

Strong FederationsにおけるBlocksigning

Strong Federationsでは、低レイテンシーの実現と、特定の敵対する少数派によるチェーンの再編成リスクを回避するためBitcoinにおける動的なマイナーセットを固定の署名者のセットに置き換える。プライベートチェーンと同様PoWは、スクリプトの検証に置き換えられる。連合ではこのスクリプトは k-of-n のマルチシグネチャスキームで実装する。このスキームでは、ブロックの署名にｎ個の鍵の内のk個の署名を必要とする。このようにしてBitcoinのビザンチン耐性をエミュレートすることができ、悪意ある署名者が少数の内はシステムに影響を与えることはない。

以下のFig4が、Strong Federationsにおけるコンセンサスの流れ

で、以下のフェーズで構成される。

1. ブロック候補を作成するBlocksignerはラウンドロビンで決まる。ラウンドロビンでマスターとなったBlocksignerは候補ブロックを作成して他のBlocksignerに提案する。
2. マスターではないBlocksignerは、受信した候補ブロックに賛成する意思表示を行う。
3. 閾値Xを満たす場合、各Blocksignerはブロックに署名する。
4. 閾値Yを満たす場合、ブロックは受け入れられ、ネットワークにブロードキャストされる。
5. 次のブロックは、ラウンドロビンで次のBlocksignerにより提案される。

セキュリティの改善

Bitcoinではブロックの生成は確率的に行われるため、最近のブロックではチェーンの再編成の傾向がある。Strong Federationのブロックの生成は確率的ではなく、固定された一連の署名者によって行われるため、決して再編成されることはない。これによりトランザクションの確認に要する時間はだいぶ短縮される。

ビザンチン耐性は、2つの一般的なケースの攻撃に対する保護になる。１つはノードのクリティカルな部分がネットワークから分離され可用性が失われるケース。もう１つは攻撃者による多数のノードが操作され、完全性が失われるケース。

Strong FederationのBlocksigningは、最大2k − n − 1の攻撃者に対して堅牢である。つまり2k − nのビザンチン攻撃者だけが競合する同じブロック高のブロックに署名し、ネットワークをフォークすることができる。例えば、5-of-8の閾値の場合は１人の攻撃者に対するビザンチン耐性があり、6-of-8の場合は３人の攻撃者に対するビザンチン耐性がある。

一方、n − k + 1の署名者が署名に失敗すると、ブロックは生成されない。従って閾値kを増やすとフォークに対する保護は強化されるが、署名者が署名できない場合のネットワークの復元力は低下する。

所感

• PoWを固定した署名者のセットを使ったマルチシグに置き換えて、悪意ある署名者が少数であればビザンチン耐性があるみたいな解釈は成り立つの？固定してる時点permittedなんじゃないの？と思ってしまう。
• LiquidがこのStrong Federationsを最初に採用したプロダクトになるみたいね。
  blockstream.com