liquid(elements)やMoneroにおいてはConfidential Transactions(コンフィデンシャルトランザクション)と呼ばれる技術が使われています。(MoneroはRing Confidential Transactionsと呼ばれる応用手法にしています) Confidential TransactionsはblockstreamのGreg Maxwellによって2015年6月に発表されたアイデアです。とても面白いアイデアなのでこちらに解説を書いておきます。
なお、インプットには
- オリジナルのGreg Maxwellの発表
- Monero Research Labが出しているRing Confidential Transactionsのペーパー
- Chaintope 安土氏のブログ
- Chaintope 安土氏の動画
を参考にしました。安土氏のブログや動画ですでに日本語でも解説されているので二番煎じなのはご承知おきください。
- Confidential Transactionsとは
- input合計とoutput合計が同一である事はPedersenのCommitmentで行う
- オーバーフローによるコイン生成問題
- 原始的なOR PROOFによるオーバーフローしないことの証明
- まとめ
Confidential Transactionsとは
Confidential Transactionsは送金、着金額を秘匿するための手法です。まず、Confidential Transactionsはビットコインのトランザクション形式(UTXO式)を前提としています。
具体例を挙げると以下のように複数のinputとoutputが複数存在するトランザクションです。inputは過去のutxoを指し示しているため送金額であり、outputは着金先が示されていて着金額です。
input | output -------------- 1BTC | 4BTC 2BTC | 2BTC 3BTC |
Confidential Transactionsは、こちらの金額を秘匿し、
input | output -------------- ?BTC | ?BTC ?BTC | ?BTC ?BTC |
とする手法です。Bitcoinのようなトランザクションにおいて以下の制約をクリアしなければなりません。
・input合計とoutput合計が同一である事
・第3者には秘匿しながらoutputの金額は受取手にはわかる
input合計とoutput合計が同一である事はPedersenのCommitmentで行う
Confidential TransactionsはPedersenのCommitment理論を応用しています。Pedersen Commitmentは元の数値を知らせる事なく、加算結果同士を検証することができるアイデアです。
Confidential Transactionsにおいては、
GはECDSAのベースポイントであり、以下の式でHを計算します。topointはベース
H = topoint(SHA256(ENCODE(G)))
topoint()
は引数が楕円曲線上にある事を検証する関数です。さらに、blinding factorと呼ばれる秘密の数字xと金額aを用いて以下式でcommitment C
を求めます。
C = xG + aH
例えば金額が1BTCの場合は C = xG + 1H
になります。
上にあげた例のトランザクションを秘匿すると
[秘匿前]
input | output -------------- 1BTC | 4BTC 2BTC | 2BTC 3BTC |
[秘匿後]
input | output ---------------------- x_1G + 1H | x_4G + 4H x_2G + 2H | x_5G + 2H x_3G + 3H |
となります。秘匿後のinputの合計は
input_total = (x_1+x_2+x_3)G + 6H output_total = (x_4+x_5)G + 6H
で表せます。input_totalとoutput_totalはcommitmentとして公開されています。秘匿化処理の中で (x_1+x_2+x_3) == (x_4 + x_5)
を担保しておけば、input_total - output_total == 0
となり、金額aを知らせる事なくinputとoutputの合計の同一を確認することができます。
オーバーフローによるコイン生成問題
問題はあり、負の数が紛れている場合にも合計が一致してしまいます。例えば、1coinと2coinがinputとして送金に使われたが、-2coinと5coinがoutputとして着金にすると5coinのUTXOが生まれ、着金者は5coinを利用できてしまいます。
(1 + 2) - (-2 + 5) = 0
実装において負の値の入力は認められていませんが、大きな値を入力してオーバーフローをかけることで負の値を入力するという悪用が考えられます。そこで秘匿された金額がオーバーフローを起こさない範囲内であることを証明すれば悪用防止できます。
原始的なOR PROOFによるオーバーフローしないことの証明
commitmentが0か1に対するcommitmentであることは証明できることを利用してオーバーフローしない範囲内であることを証明します。
金額a
が0の場合
C=xG+aH = xG
であり、$C$に対する署名をする事で$x$の保持者は0に対するcommitmentを証明できます。
金額a
が1の場合、
C=xG+aH = xG+1H
です。ここで、
C' = (xG + 1H) - 1H = xG
を導入すると、こちらも$C'$に対する署名で$x$の保持者は1に対するcommitmentを証明できます。
0か1に対するcommitmentである事を証明できれば、[0,2n]の範囲内である事も証明できます。例えば、Cを2進数で表現し、CN = 0
をCのN桁目について0のcommitmentである事を示すとき、Cが[0,25]の範囲であることは以下を示せば良くなります。
C1 =0 or 1, C2 = 0 or 1, C3 = 0 or 1, C4 = 0 or 1, C5 = 0 or 1
この方法を用いて C>0
を表現できます。
単純なOR Proofではパフォーマンスが悪いため、 範囲を絞って効率的に行う証明方法として、実際にはRange Proofという手法やボロミアン・リング署名が利用されています。
まとめ
Pedersen Commitmentの手法とUTXOモデルのトランザクションとの相性が非常に良くその組み合わせを行ったことが優れたアイデアだったのだと思います。また、blockstreamのGreg Maxwellによる発表を受けて、そのアイデアをベースに、Moneroもこれまでしていなかった(できていなかった?)金額の秘匿を行うようになりました。暗号通貨系には影響力のある発表だったと思います。 Moneroの秘匿化手法についても調査したので折を見て書き記しておきます。