techmedia-think.hatenablog.com
↑でConfidential Transactionのコミットメントの作成と検証をしたので、続いてrange proofについて見てみる。
Confidential Transactionではトランザクションの各出力にコインの量ではなくコミットメント（楕円曲線上の点）がセットされるようになり、それにより取引されるコインの量が秘匿され、検証者は楕円曲線上の点を計算することで入力と出力のコインのバランスが取れていることを検証する。
ここで１つ問題になるのが、コミットメントの計算時に非常に大きな値を設定することを値をオーバーフローさせ、負の値として動作する場合。この場合マイナスのコインによりバランスの計算が行われるため、結果的に何も無いところからコインを生み出すことができてしまう。
この問題に対応するため、コミットされた各出力の値が、正常な（0〜264）範囲の値であることを証明する仕組みが必要となり、この証明を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まで削減できるという発言もあるが、それでもまだ大きなサイズだ。
