Develop with pleasure!

福岡でCloudとかBlockchainとか。

離散対数仮定が崩れた際にConfidential Transactionチェーンのコインを保護するSwitch Commitment

CT Bitcoin SBC Cryptography

Stanford Blockchain Conference 2019のGrinのセッションで、Grinの構成要素として挙げられていたSwitch Commitmentについて↓

https://eprint.iacr.org/2017/237.pdf

Bitcoinなどの多くの暗号通貨では楕円曲線暗号を導入しており、楕円曲線暗号の安全性は離散対数仮定の下に成立している。これは離散対数問題を解くのに現時点で効率的な方法がなく、総当りの計算をする必要があり計算量的に困難であるというもの。

しかし将来的に量子コンピュータなどの登場により離散対数問題が効率的に解かれる時代が来るかもしれない。そうなった場合に既存の暗号通貨は鍵長の変更や、暗号アルゴリズムの変更を求められるようになる。これは通貨によってソフトフォーク/ハードフォークによって切り替えが行われるだろうが、切り替えのタイミングを決めて、それ以降では新しい暗号アルゴリズムを使用できるようにし、既存のUTXOを新しいアルゴリズムでロックする新しいUTXOに移す必要がある。移さずにずっと据え置かれるUTXOは、その離散対数を解いた者に資金を奪われる可能性が高い。

このようにBitcoinなどであれば新しい暗号アルゴリズムもしくはパラメータに移行することで対処が可能だ。問題がより深刻なのはConfidential Transactionを導入しているチェーンである。BlockstreamのElementsやLiquid、Mimblewimbleを実装したGrinやBEAMなどが対象だ。

Confidential Transaction

コインの量はBitcoinの場合はトランザクションのアウトプットに明示的に正数値で記録されるが、Confidential Transactionではコインの量を以下のような準同型コミットメントであるPedersen Commitmentで管理している。

commitment = rG + vH

GおよびHは楕円曲線上の生成点で、rはブラインディングファクターでvを隠すためのランダムな値、vがコインの値。ランダム値はコインの受信者が決める値で、このコミットメントにいくらのコインがあるのかはrとxの値を知らないと分からない。つまり取引の当事者以外、第三者はこのコミットメントにいくらのコインがあるのか知りようが無い。こうやってコインの量を秘匿するのがConfidential Commitmentだ。検証方法など詳細が知りたい場合は↓

techmedia-think.hatenablog.com

離散対数仮定が成立しなくなった場合にどうなる？

量子コンピューターの登場などにより離散対数問題を解くことができるようになるとPedersen Commitmentを使用しているConfidential TransactionはBitcoinなどよりも大きな問題を抱える。

Confidential Transactionのチェーンを破壊するには１つの離散対数の値が分かればいい。上記Pedersen CommitmentのHの離散対数だ。 H = xGとなるようなxの値を攻撃者に知られるとまずい。

例えば攻撃者が既にConfidential Transactionを使っているチェーン上で誰かからコインを貰っておく＝自分がブラインディングファクターrを選択したCommitmentを入手する。

この状態でH = xGとなるxの値が分かると

r' = r + x(v - v')

を計算する。v'はv' > vとなる（コインを増やす）新しいコインの量である。この新しい(r', v')のペアを使うと

r'G + v'H = (r + x(v - v'))G + v' xG
          = rG + x(v - v')G + v' xG
          = rG + xvG
          = rG + vH
          = commitment

が成立し、コインの量を自由に制御可能になる。こうやって無からコインを生み出すことができる(r', v')のペアを計算できる。

Bitcoinの場合、離散対数の値が計算できるようになったとしても個人のコインが盗まれるだけで、コインを無から生み出すようなことはできない。また個人のコインが盗まれないよう暗号アルゴリズム・パラメータを変更することでこれに対処できる。Confidential Transactionの場合は、その性質上、上記のように無からコインを生み出すことができてしまい、チェーンに対する攻撃が可能になる。こういったリスクを回避するための仕組みがSwitch Commitmentだ。

Switch Commitment

上記のPedersen Commitmentは離散対数仮定に依存しているが、たとえ無制限の計算能力があったとしても性質を破ることが不可能であるコミットメントを追加し、検証処理をそのコミットメントに切り替えることでこの問題に対応する。Pedersen Commitmentに代わるコミットメント方式としてElGamal Commitmentを採用する。

ElGamal Commitment

ElGamal CommitmentはPedersen Commitmentとほとんど同じだが、Pedersen Commitmentの要素にもう１つ同じブラインディングファクター r と生成点Hを使って計算した点をコミットメントのデータとして持つ。

commitment = rG + vH, rH

rHのデータを追加することで、このコミットメントを開くには、rGとｒHのrが同じなければならない。このようなrのルールがある場合、いくら計算量があってHの離散対数がわかったとしてもvを変更することはできない。このようなElGamal Commitmentの特性により、コインを無から生成するような攻撃を回避することができるようになる。

またElGamal Commitmentが都合が良いのは、rHの部分を無視すると、今まで通りのPedersen Commitmentとして扱うことができるという点だ。

Confidential Transactoinではvの値がオーバーフローしない値の範囲内であることを保証するために別途、範囲証明をする必要があるが、現在CT用に設計されている範囲証明はいずれもPedersen Commitmentには最適化されているが、ElGamal Commitmentの範囲証明はそのような最適化はされておらず効率が悪い。

そのためコミットメントのデータ自体はElGamal Commitmentとして作成するが、検証の方法を2つ用意する。

  • 部分検証 = Pedersen Commitmentによる検証
  • 完全検証 = ElGamal Commitmentによる検証

離散対数仮定が崩れるようなおそれがあるまでは、今まで通り部分検証によりPedersen Commitmentを検証する。その後実際に脅威が訪れた際に完全検証に切り替えるソフトフォークを行う。そうすることで、チェーン上で無制限にコインが発行されチェーン自体を攻撃するといったリスクは回避することができるようになる。これがSwitch Commitmentだ。

※ ただ、注意が必要なのは、これはConfidential Transactionを構成するチェーンにおいて、無からコインを生成するようなことをできなくするための対応方法であって、離散対数問題が解かれた際にコミットメント内のコインの量のプライバシーを引き続き提供するものではない。つまり離散対数問題が解けているということは、そのコミットメントのコインの量が計算可能であるということだ。そのような状況になった場合は、秘匿系の仕組みは別途新しく考える必要があるだろう。

Grinの実装

mainnetがリリースされる前のバージョンのGrinでは上記方法でElGamal Commitmentが実装されており、トランザクションのアウトプットにrHのハッシュ値（switch commit hash：32バイト）が追加されていた。

その後、上記のElGamal Commitmentでアウトプット毎に追加の32バイトのデータスペースを消費することなく同様のことが可能なアイディアをTim Ruffingが提案され以下のように変更されたみたい。

通常のPedersen Commitmentではブラインディングファクターであるrの値はランダムに選択されるが、r自体はランダムにせず、別のランダムな値r'を使ってPedersen Commitmentを作る。

commitment = rG + vH

r = r' + hash(vH + r'G, r'J)

JはHに次ぐ3つめの生成点。ハッシュ関数に渡すデータの部分がElGamal Commitmentになっていることが分かる。

検証の仕組みについてはまだよく見てないけど、基本的には初期はPedersen Commitmentで検証し、その後脅威が訪れた際にrの導出元となっているElGamal Commitmentを検証するように変更するといったアプローチか？ この辺はまたElGamal Commitmentの範囲証明のやり方含めて調べてみたい。

コインの所有を証明するProof of Reserveの標準化（BIP-127）

BIP Bitcoin

少し前に、取引所に自分が預けているコインが本当に存在するか一斉に引出して確認してみようとするProof of Keysというイベントがあって、どこぞの取引所が事前に引き出し制限始めたというニュースもあったけど、ユーザーにとっては預けている資産がちゃんと存在することを検証できるのは重要なこと。

進んでそういった証明を開示してくれる取引所があれば素晴らしく、そういったアプローチをする取引所もあるが、証明方法については明確な標準はない。そこで最近Blockstreamがその標準化の提案をしている↓

blockstream.com

もともとBlockstreamが提供するサイドチェーンLiquid上での監査のために着手したものみたい。提案されたBIP-127が↓

https://github.com/bitcoin/bips/blob/master/bip-0127.mediawiki

プルーフのフォーマットの定義とそのコミットメントと保有するUTXOで構成されたBitcoinトランザクションとしてエンコードする仕様（BIP 174のPSBTの拡張を含む）を定義したシンプルなBIP。

このProof of Reserveの仕組みにより取引所などのカストディが保持する金額を把握できる仕組み標準化しようということだが、これだけだと自分のコインがちゃんと存在するかという証明には不十分である。証明しているのは総量だけなので、確実に取引所が預かっている顧客資産に対し十分な支払い能力があるか証明するためには、

  • 資産の証明（今回のProof of Reserve）
  • 負債の証明（顧客が取引所内で保有するBitcoin残高）
  • 支払能力の証明 = 資産−負債の証明

が必要になる。この事は実際BIPの記述でも触れられているが、最後の支払能力の証明までやろうとすると、↓のProof of Solvencyまで必要になる。

techmedia-think.hatenablog.com

今回は１つめの資産の証明をまずは、なるべく既存のウォレットと互換性のある形で標準化しようというアプローチになる。

以下BIP案を和訳したもの↓

概要

このBIPは、proof-of-reserveトランザクションを構築するための簡単な方法を説明する。この提案は、そのような証明を構築し、既存のウォレットインフラを使ってそれらの構築を容易にし、一般的な証明検証ソフトウェアを可能にするための標準フォーマットを形式化する。このフォーマットは、通常のBitcoinトランザクションのシリアライゼーション/検証およびBIP 174 PBSTフォーマットなどの既存の規格に依存する。この提案には、ユーザーエクスペリエンスを向上するためのPSBTの拡張機能の説明も含まれている。

動機

Bitcoinの歴史の初期の頃から、ユーザーのためにBitcoinを管理する会社があった。これらのユーザーは特定のサービスと引き換えにコインの管理を放棄する。必然的にそのような企業がユーザーのBitcoinを失うことがあり、そのような事が起きても事件が公に公開されることはなかった。Proof of Reserveは大量の資金を管理している企業が一定額の資金に対する所有権を証明するための方法だ。定期的な所有権の証明は、重大な損失が発生していないことを確認するのに役立つ。

Proof-of-Reserveという用語は決して新しいものではないが、この手順は多くの資金を持つカストディアン企業であまり一般化されていない。その理由の１つは、proof-of-reserveを実行しようとするすべての企業は、それぞれ独自の方法で構築する必要があること。従って、そのユーザーはその証明を検証するために証明の構造を理解しなければならない。これは管理者にとってもユーザーにとっても参入障壁を高めることになる。

このBIPでしないこと

このドキュメントで説明されているProof-of-Reserveの構造には、主にそのプライバシー特性について、いくつかの既知の欠点がある。より優れたプライバシー特性を持つ改良されたProof-of-Reserveの仕組みに関する研究があるが*1、このBIPは意図的に事実上の既存の方法を形式化するだけだ。

仕様

我々の仕様は以下の２つのパートで構成される：

  1. 実際の証明のフォーマット
  2. 証明と関連メタデータのセットをパッケージ化するために使用されるファイルフォーマット

最終的な構成は以下の特性を持つべきである：

  • 複雑なウォレットインフラをサポートするための柔軟なプルーフ構造
  • 既存のウォレットソリューション（ハードウェア、ソフトウェア両方）との簡単な統合
  • プルーフの発行元に関係なく、標準手順による検証のサポート
  • プルーフは、メッセージに対してコミットすることで他の当事者によるプルーフの再利用を防ぐ
  • 発行者が特定のブロックにおいてあるコインが自分の管理下にあることの検証を許可する（その後のブロックでどうなるかに関わらず）

プルーフフォーマット

既存のシステムと最大限の互換性を担保するため、プルーフは通常のBitcoinトランザクションとしてフォーマットされる。ただし以下の２つの機能を持つ１つの小さな適応をトランザクションに対して行う。

  1. 資金を危険にさらさないようトランザクションを使用不可能なものにする。
  2. 他のカストディによるプルーフのコピーを防ぐために、プルーフをプルーフの発行者とリンクする。

結果として得られる構造は、以下の特徴を持つBitcoinトランザクションとなる。

  • 最初のインプット（コミットメントインプット）
    • 前のOutPointのtxidの部分には、"Proof-of-Reserves："というプレフィックスが付いたコミットメントメッセージのSHA-256ハッシュ*2をセットし、indexは0とする。
  • 残りのインプット
    • コミットメントインプットにコミットする署名（例えばSIGHASH_ALLを使った）を持たなければならない。
  • トランザクションは、コミットメントインプットのコインの量を0と仮定して、すべてのインプットのコインの量の正確な合計を持つ単一のアウトプットを持たなければならない。これはトランザクションがマイニング手数料を持たないことを意味する。

最初のインプット（単なるコミットメントハッシュ）の存在は、このトランザクションが無効であり決して承認されるものではないことを保証する。

プルーフファイルフォーマット

理論的には、仕様の最初の部分は実用最小限の標準として十分である。しかし、追加のメタデータレイヤーを使って標準を拡張するする動機は多数ある。

  1. 複数のプルーフの構築と結合
    何千ものUTXOを異なるオフライン、オンラインのウォレットに分散させると、その全てのUTXOを使って単一のトランザクションでプルーフを作成するのは困難な可能性がある。同一のコミットメントメッセージとブロック番号を持つ複数のプルーフトランザクションを許容することで、複雑なウォレットインフラを持つカストディにとって、結合されたプルーフの安全性を低下させることなく、さらなる柔軟性が得られる。
  2. 検証用のメタデータ
    検証に使われる全てのシステムが全てのトランザクションの完全なインデックスにアクセスできるわけではない。ただし、プルーフに使われているUTXOが既に未使用でなくなった後でも、プルーフは簡単に検証できるはずである。プルーフに存在するメタデータは、トランザクションインデックスが使えない場合でも、プルーフの比較的効率的な検証を可能にする。
  3. 将来の改善の可能性
    拡張可能なメタデータフォーマットは、将来の標準の修正を可能にする。１つの潜在的な改善はUTXOセットコミットメントを持つことだ。これらは、プルーフ構成のブロックでUTXOセット内の全ての使用されたUTXOのproof-of-inclusionをproof-of-reserveが付随することを可能にする（検証をさらに効率的にする）。

提案するproof-fileのフォーマットは、複数のプルーフと関連するメタデータを結合するための簡単な方法を提供する。フォーマットの仕様はProtocol Bufferフォーマット*3である。

syntax = "proto3";
import "google/protobuf/any.proto";

message OutputMeta {
    // OutPointの識別子
    bytes txid = 1;
    uint32 vout = 2;

    // このアウトプットが作成されたブロックのブロックハッシュ
    bytes block_hash = 3;
}

message FinalProof {
    // プルーフトランザクション。 通常のBitcoinトランザクションのようにパース可能。
    bytes proof_tx = 1;

    // プルーフトランザクションで使用されるアウトプットのメタデータ。
    repeated OutputMeta output_metadata = 2;
}

message ProofOfReserves {
    // 追加フィールドを拡張できるよう、このフォーマットのバージョン番号
    uint32 version = 1;

    // プルーフが有効なネットワークのネットワークマジック。
    // mainnetは0xD9B4BEF9, testnetは0x0709110B
    //TODO BIP44のcoin type idを代わりに検討
    // https://github.com/satoshilabs/slips/blob/master/slip-0044.md
    uint32 network_magic = 2;

    // このproof-of-reservesのコミットメントメッセージ。
    // このメッセージは全てのプルーフのためのグローバルなもの。
    string message = 3;

    // このプルーフが検証されるブロック。
    // 検証では、このブロック高でアウトプットが未使用であることを考慮する必要がある。
    bytes block_hash = 4;

    // アウトプットメタデータを含む最終プルーフトランザクションのセット。
    repeated FinalProof final_proofs = 5;

    // proof-constructionツールで使われる可能性のある予約フィールド。
    // 検証では無視される。
    repeated google.protobuf.Any pending_proofs = 6;
}

最後のフィールドpending_proofsは proof-constructionツールで使われるスペースを同じファイル内にいくつか確保する。これによりファイルフォーマットを切り替えることなく、さまざまなプルーフを段階的に構築できる。

PSBT（BIP 174）の拡張

プルーフフォーマットのセクションで詳述されているコミットメントインプットは既存のUTXOを使用するわけではないので、署名されるべきではない（scriptSigとwitnessは空）。このタイプのトランザクションに署名する際、いくつか問題を引き起こす可能性がある。例えば、ハードウェアウォレットは、よく署名しようとしているトランザクションの全インプットに関する情報（前のアウトプットや前のトランザクションなど）を提供するよう署名者に求める。しかし、このデータは明らかにコミットメントインプットには存在しない。

ほとんどの既存デバイスでは、ダミーデータを提供するか、この特定のインプットを無視するようデバイスに指示することで、こららの要件を回避することができる。それでもUXの問題が残る。ハードウェアウォレットデバイスは、そのトランザクションをproof-of-reserveトランザクションとして認識しないため、UTXOの全てのお金を使用する通常のトランザクションに署名していると捉えられる。ほとんどのデイバスは「XXX BTCをアドレス[...]に送信してよろしいですか？」というメッセージで確認を求めるが、これは最高のUXではない。

BIP 174 PSBTフォーマットに定義を追加することで、署名デバイスがProof-of-Reserveを認識することができる。以下のフィールドがBIP 174のINPUT Mapに追加される。

  • タイプ：Proof-of-Reserve コミットメントPSBT_IN_POR_COMMITMENT = 0x09
    • キー：なし。1バイトのタイプのみ。
      • {0x09}
    • 値：Proof-of-ReserveのUTF-8エンコードされたコミットメントメッセージの文字列
      • {porCommitment}

このフィールドがセットされているインプットを処理するウォレットは、

  • 上述したように、OutPointにプレフィックス付きコミットメントメッセージの文字列のSHA-256ハッシュがセットされていることを確認しなければならない。
  • インプットの値（コインの量）は0と仮定しなければならない（前のアウトプットのトランザクションを提供する必要はない）。
  • 任意のインプットに署名する前に、確認のためコミットメントメッセージをユーザーに表示し確認を求めるべきである。
  • このインプットにコミットするSIGHASHが使われている署名のみを提供するべきである。
  • このインプットについては、（scriptPubkeyがOP_TRUEであるかのように）空のscriptSigを受け入れる必要がある。

実装

PSBT拡張のproof of conceptの実装がrust-bitcoinプロジェクトのpsbt-porブランチにある。

https://github.com/stevenroose/rust-bitcoin/tree/psbt-por

上記フォーマットのプルーフを生成、検証するツールの進行中の実装が以下にある。

https://github.com/ElementsProject/reserves

*1: Dagher, Gaby G., Benedikt Bünz, Joseph Bonneau, Jeremy Clark, and Dan Boneh. "Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges." (2015)

*2:メッセージが"Some Message"の場合、txidの部分はUTF-8でエンコードされた文字列のSHA-256("Proof-of-Reserves: Some Message")となる。

*3:https://github.com/protocolbuffers/protobuf/

How Much Privacy is Enough? at Scaling Bitcoin 2018

Bitcoin Scaling Bitcoin

2019年になったけど、Scaling Bitcoin 2018 復習シリーズ。今回は、Zcashのファウンダーの１人でもあるCornell TechのIan Miersによる「How Much Privacy is Enough?」↓（1時間あたりから）

youtu.be

書き起こしは↓

http://diyhpl.us/wiki/transcripts/scalingbitcoin/tokyo-2018/how-much-privacy-is-enough/

内容は、プライバシーとスケーラビリティのトレードオフを評価しながら、どれだけのプライバシーがあれば十分かについての発表。新しい技術提案というわけではないけど、今まではどちらかというとブロックチェーンの分析を行う会社による、ブロックチェーンのデータ分析によるプライバシー漏洩のリスクをふわっと考えることはあったけど、実際の脅威とは何か？その脅威を現実するエンティティは何か、さまざまなプライバシーに関する提案がある中で、デコイベースのプライバシー効果は？などが、まとめられていて個人的に暗号通貨に関するプライバシーの課題を捉え直すことができる内容でよかった。

プライバシー技術

Bitcoinが登場したばかりの頃は、送金の匿名性が注目されていたが、最近ではBitcoinで提供されるのはあくまで疑似匿名性のレベルであり、完全なプライバシーを提供するものではないということが認知されてるようになってきている。実際にブロックチェーンを監視しトランザクションの分析を行う企業も存在する。一方、暗号通貨のプライバシーを向上させるため様々な提案も活発にされている。アドレスの再利用の禁止といったものから、

  • coinjoin
  • mixcoin
  • coinswap
  • coinjoinxt
  • joinmarket
  • Tumblebit
  • Zerocash
  • Bolt
  • Confidental Transaction
  • Ring Signature

などの複雑な暗号プロトコルまで、多数の提案がある。これらの技術を実際に自分で使用する場合、使用する前にそれがどう動作し、それによってどの程度のプライバシーを得るのか正確に評価する必要がある。エンジニアはパフォーマンスベンチマークの実行方法や概算の方法を知っているが、どの程度のプライバシーを確保するか計測し判断するのは難しい。

プライバシーの評価

ではどうやってプライバシーを評価するかという点だが、これにも課題がある。暗号通貨が利用可能であるといっても現状の使用状況を考慮すると、それはcookiesやターゲット広告、監視などより前の唯一のウェブサイトがCERNであった1992年のプライバシーを評価しようとしているようなものだ。

  • 経験的な側面からは計測できない
    • ブロックチェーン上のほとんどのトランザクションは投機的なものであるため
    • 日常生活で暗号通貨を利用するほどの環境はなく、そういった意味で制限が多い
    • 研究者にはデータやコスト、倫理的な限界がある。

そのため、各プライバシー技術がどれほどのプライバシーを提供するかについて、経験的に見積もることはできず、思考実験で検討するしかない。そしてそのためには現実的な脅威を理解しなければならない。

実社会におけるプライバシーの脅威

じゃあ、現実的な脅威とは何だろうか？共通の脅威としてブロックチェーンの取引内容を見ている政府や法の執行機関が挙げられるが、それは確かに１つの脅威かもしれないが唯一の脅威でもなければ最も現実的な脅威でもない。

例えば、GoogleではVISAとMastercardから決済データを収集し、それを使ってターゲットを絞った広告を行うことでユーザーのプロファイルを作り上げることができる。同様に、企業は顧客の行動に関する豊富なプロファイルを構築したいと考えている。有名な例が↓ techland.time.com アメリカのディスカウント百貨店チェーンのTargetが、ミネソタ在住の女子高生が妊娠していることを彼女の父親より早く知って起きた事件。Targetでは顧客1人1人にポイントカードを配布し、購入内容をチェックすることができるようになっている。Targetは彼女の購買データから彼女が妊娠していると判断し、ベビーグッズのクーポンを配信した。彼女の父親は当初娘に関係の無いベビーグッズのクーポンが続くため店に抗議したが、その後妊娠の事実を知り謝罪する。

このように人々が何を買うのか、購入と習慣が何なのかというデータから起こる深刻なプライバシー問題がある。↑はブロックチェーンから取得するよりももっと細かい情報をベースにしているが、ブロックチェーンの取引履歴にも同様のことが言える。

もう１つの例は、Venmoだ。Venmoは個人間送金が可能なアプリで、友人同士でバーやレストランで支払いを割り勘できたりもする。Venmoを使用するとすべての取引について、利用者の名前、受取人の名前、金額、メモ欄がデフォルトで公開されるようになっている。これらはブロックチェーンから得られるものに近いが、Venmoの場合そういったデータを匿名化するような事はせず単純に提供しているだけで、大きなプライバシーリスクがある。

そして通常の決済と違い、暗号通貨ならではの問題としてFungibilityが挙げられる。Fiatと異なりBitcoinのような暗号通貨は、その通貨がどのように流通してきたかブロックチェーンの取引履歴を遡ることで確認することができる。そういった側面があるため、

  • マイニングされたばかりのコイン（これまでの取引履歴がなく汚染されていないことが確実なため）がプレミアで売られている。
  • 取引所は取引履歴をベースに顧客をブロックすることが可能。
  • 取引所は単なる第三者オブザーバーではない。

これはGMailやGoogle MapやAndroidを使いながら、Googleからプライバシーを保護しようとするのに似ている。

暗号通貨のプライバシーのための防御とは何か？

↑のような脅威から自身を守るために、暗号通貨において必要な防御とは何だろうか？自身が何も知らなかったから問題はない、どんな使われ方ををしていようが自分はそれについて知らなかった、だから自分は関係ないというのは防御にはならない。法の執行機関はそのようなことは気にしない。そのため我々は何をする必要があるか？

Bitcoinのプライバシーを侵害しようとするエンティティは？

通常、ブロックチェーン上のプライバシーの脅威というと、サードパーティのブロックチェーンの観察者などをイメージするが、そういった脅威だけではなく、現実には以下のような積極的な攻撃を行うエンティティ

  • ターゲットとなるユーザーから支払いを受け取るエンティティ
  • ターゲットとなるユーザーへ支払いを行うエンティティ
  • 第三者とのやりとりが可能なエンティティ

や以下のような明確な攻撃者が考えられる。

  • 自身の顧客を追跡しようとするマーチャント
  • 受信者のリアルな身元を特定しようとするユーザー
  • 特定の取引行動をした顧客をBANする取引所

プライバシーのアプローチ

暗号通貨のプライバシーを改善するための技術は↑のように数多く広い範囲に渡って提案されているが、それらをすべて個別に調べたくはない。これらの提案は3つの種類のシステムという観点で分類できる。

  • Bitcoin：支払いのソースを明示的に識別している
  • デコイトランザクションをベースにしたシステム：
    • CoinjoinやMimblewimbleなど（現在のトランザクションからデコイを選択するタイプ）
      複数人のユーザーの送金を１トランザクションで行うミキシングベースのアプローチで、インプットのどのコインがどのアウトプットに流れたのかを難読化する。
    • Cryptonote/RingCT（Moneroなど）（全履歴からデコイを選択するタイプ）
      未使用/使用済み関係なく、ブロックチェーンからTXOをサンプリングし、本当に使用するUTXOと混ぜてどれが使用するコインか分からないようコインのソースを難読化する。
  • ZerocinやZerocashなど
    支払いのソースを識別することができないプライベートトランザクション。強力なアプローチで、コインの送信元、送金先、送金量が秘匿され、周りのノードはそれが正しいことを一緒に付与されたゼロ知識証明を使って検証する。

Bitcoinの支払いの場合

Bitcoinでマーチャントに支払いをする場合、支払いに使用するコインがどこから来たものなのかソース明確に特定する必要がある＝インプットでUTXOを指定する。これが基本的にプライバシーを持たない理由。

デコイベース支払いの場合

デコイベースのシステムで支払いをする場合、この場合も同様に支払いに使用するコインがどこから来たものなのかソース明確に示す必要があるが、それとは別にデコイ用のソースを混ぜ、デコイ入りの複数のソースとして指定することで、本物のソースを隠す。トランザクションを見てもどれが本物のソースか誰も分からない。

Zerocashの支払いの場合

最後にZerocashで支払いをする場合、コインのソースを識別する情報は何もない。

デコイシステムはプライベートか？

Bitcoinのプライバシーの制限についてはよく研究されている。Zerocashのプライバシーの制限は、学術文献と実際に研究がされている。しかしデコイベースのシステムは実際どうだろうか？

f:id:techmedia-think:20190121164230p:plain

↑のTaint treeは、支払いに使われた資金について、その資金およびデコイの源（ソース）となる可能性を追っていってできる歴史のツリーだ。

そしてコインをマーチャントに支払った場合、買い手はそのコインがどこにいくのか見ることが可能だ↓

f:id:techmedia-think:20190121173358p:plain

ただ、コインはマーチャントとは別のユーザーによりデコイの支払いとして使われる可能性もあり、その場合コインがどこにいったのかは分からない。つまりコインの送信先の可能性のみが分かるというだけだ。

顧客の識別

この状態でどういったことができるだろうか？

できることの１つは、あなたがマーチャントか共謀するマーチャントグループだった場合、繰り返しの支払いにより顧客を追跡することができる。私が毎日Target（小売店）に行き、現金で買い物をする分には誰も私を追跡できないだろう。じゃあ暗号通貨で支払いをするとどうだろうか？理想的には、例えば3つ商品を別々に購入した場合、3つの購入は別々のものでリンクされるべきではない。単純に考えるとこれらが結びつくようなことは無いように思える。しかし、私が何かを購入し、代金として$20を支払い、お釣りを$5受け取る。私は３つの各支払でこれと同じことをする。すると遅かれ早かれ受け取ったお釣りを使わなくてはならなくなる。その場合、そのデコイを含むトランザクションのインプットの１つはマーチャントから前回購入した際のお釣りになる。基本的にデコイは今までのトランザクションの中から一様にランダムに選択しているため、このような状況でそれがデコイとして選ばれる可能性は低い。

また別の観点として、３つの支払いで使われたコイン（デコイを含む）についてTaint treeを構成し、それぞれ３つの支払いのコインが同じ祖先を指しているケースを考えてみよう↓

f:id:techmedia-think:20190121193121p:plain

暗号通貨で支払いをするために取引所で多額のコインを入手し、それが祖先となる支払いのリンクが形成される。デコイが含まれていても共通の祖先に遡ることができれば、同じ人物による支払いであることが特定できる情報をマーチャントに与えることになる。これは１つのマーチャントに限った話ではなく、複数のマーチャントが結託した顧客を追跡する可能性も考えられ、これも問題である。

匿名マーチャントの識別

もう１つ別の視点の攻撃について考える。あなたが民主主義の活動家で、匿名で寄附を受け付けるサイトを持っているとしよう。ただ、あなたが働いている国での生活が危険にさらされるため、自分の身元は明らかにしたくない。活動のために資金を得たいが、政府はあなたを特定したがっている。プライバシーが保護されたシステムでは、あなたがその寄付金を受け取り取引所に預けるのは安全なはずだ。例え取引所が政府によって管理されていても、彼らがあなたを特定する方法はない。あなたは安全なはずだが、これは事実ではない。

政府があなたを特定したい場合、政府いくつかの（Torでしかアクセスできないものを含む）Webサイトに載っているあなたのアドレスを知っているだろう。彼らにできるのは、３つの追跡用の支払いをすることだ。あなたはそれを受け取り取引所に預ける。すると、取引所の記録を入手した人物であれば誰でも（召喚状を入手したり、取引所にハックしたり）、預金されたコインのセットとTaint treeを見ることで、匿名の支払いを受けているこの民主主義活動家が誰なのかを調べることができる。

f:id:techmedia-think:20190122150406p:plain

３つの追跡用の支払いのペイントされたコインがデコイとして使われることも考えられる。デコイはそれぞれがランダムに選択するので、誰であろうと預金をする際にペイントされたコインをデコイとしてピックアップする可能性がある。しかしペイントされたコインの選択を３回も５回も100回もすることはないだろう。政府があなたの預金を調べてTaint treeに送った痕跡の支払いが全てにおいて存在するなら、それは圧倒的な確率で本人であることの証拠になる。その証拠を持ってあなたが民主主義活動家であることが判明してしまう。これについてはかなり問題がある。暗号通貨にはプライバシーがあると直観で思っている人が多いのに反し、実際にそれを使用する人が学ぶと驚くような方法でプライバシーの侵害が見つかるだろう。

そのため悪意ある送信者/受信者とのやりとりを繰り返すことは実際に危険だ。

ダスト攻撃：どこでお金が使われているかを確認する

さて↑でマーチャントに支払ったコインが送金される先が（正確には候補が）分かるとといった内容を覚えているだろうか？ 支払いをするということは、同時に将来そのコインを含む可能性のあるトランザクションを知ることができ、これを悪用することもできる。例えば、友人がどこでお金を使っているのか調べるのに利用できる。小額の支払いを、マーチャントと友人にそれぞれする。そしてTaint treeとトランザクショングラフを監視する。するとある時点で面白いことが起こるかもしれない。

f:id:techmedia-think:20190122164220p:plain

この両方の資金を含む可能性のあるトランザクションが公開された場合、誰かがデコイとしてランダムに選択したものなのか、それとも友人とマーチャントに支払ったコインが実際一緒に使われたのか。そしてマーチャントがホットウォレットから資金をコールドウォレットに移したのか、それとも請求への支払いにあてたのか。もちろんデコイの可能性もあるが、こういうトランザクションが何度も観測される場合、あなたの友人はこのマーチャントで定期的な購入をしているという強い証拠になる。

デコイアプローチの制限

↑のようにデコイベースのアプローチには実際には限界がある。

  • 顧客の追跡が可能
  • 匿名マーチャントも特定される
  • 第三者にお金の行き先が分かる

さまざまなプライバシー向上のための技術や暗号通貨について思う共通の認識は、Bitcoinはおそらくプライベートではない（チェーン的な意味ではなくて）、しかしデコイやZerocashのような仕組みにより意味のあるプライバシーが追加される。技術が何かが問題ではなく、これらの技術の間にはどれくらいプライベートであるかという点でトレードオフがある。そしてそのトレードオフが何を意味するのかについてこそ理解する必要がある。

デコイアプローチを使う場合

何らかの理由でデコイスキームを使用する場合、5つの起源ではなく5000もしくは500万の起源の可能性があるような非常に大きな匿名セットを使える場合、実行可能であるかもしれない。

以下のようなケースであれば機能すると思われる

  • デコイのセットが非常に多い（5とかではなく500万のデコイなど）
  • デコイのセットは直近のすべてのトランザクションで実質的に重なっている
  • デコイは本当に慎重に選択されること

しかし、

  • どの程度のプライバシーが提供されているのかの厳密な分析
  • 物事がどこで失敗するかを注意深く理解する
  • 制限を認める

といった点に十分注意する必要がある。実際以前、Moneroがデコイをサンプリングした分布と、実際の人々がコインを使用する分布が一致しなかったことを示す一連の論文があった。そこにはギャップがあり、これは現在やや修正されているが、Moneroの旧バージョンでは、圧倒的な確率で最後のトランザクションが本物のトランザクションであった。

もしこのデコイベースのアプローチを取るなら、繰り返しになるがそれがどれくらいのプライバシーを提供するのかについての様々な分析を知る必要がある。

スケーラビリティ

制限を定めることはスケーラビリティに帰着する。デコイシステムを利用していて、本当に大きなデコイセットを得るにはスケーリングが必要になる。

対数スケーリング

デコイの数によってリニアにスケールするシステムは持てない。例えばbulletproofをサポートしたMoneroは、デコイを追加するのトランザクション内に1〜2 KB必要とする。もしデコイの数によりトランザクションサイズがリニアに増加するなら100や500、1000個のデコイを持つトランザクションはとても現実にはワークしない。リニアスケーリングのデコイシステムはワークしないので、必要なのはトランザクションサイズやトランザクションの生成、検証時間がデコイの数に対して対数になるようなシステムが必要となる。

Zcashスタイルのシステム

デコイベースではなくZcashライクなシステムを採用する手もある。Zcashでは、トランザクションアウトプットは（金額や受診者）へのコミットメントとなり、金額や宛先は誰にも分からず、それが確かに未使用なUTXOであること、またそれを所有していることの証明をゼロ知識証明で行う。こういったZcashスタイルのシステムを設計するのも１つの方法だ。

  • ゼロ知識証明技術のピックアップ
    スケーラビリティを向上させるためには、暗号が安全で仮定が保証され、セットアップ特性があらゆる運用要件に対応したゼロ知識証明技術をピックアップする必要がある。zk-SNARKだったりbulletproofだったりzk-STARKだったり。
  • zkが効率的であるマークルツリーの深さdを選択
    ゼロ知識証明技術を選択したら、ベンチマークを行い、効率的に動作するようパラメータを選定する。ZcashではUTXOセットはマークルツリーで管理されているが、マークルツリーが長くなれば深さも深くなり、デコイセットでトランザクションは大きくなり、生成や検証は遅くなる。そのためパフォーマンス要件を満たすマークルツリーの深さdを見つける。dが決まるとデコイのセットは2dで決まる。
  • デコイをサンプリングする際の安全性

スケーラビリティ vs プライバシー

暗号通貨にはプライバシーソリューションが必要である。オンチェーンソリューション？またはオフチェーンで解決した方がいいかもしれない。

ソリューションが上手く動作することを期待するが、

  • 何が起きているのか批判的に考え
  • 現実的な脅威モデルは何か？
  • 対処しなければならない問題は何か？

を究明する必要がある。

そして、プライバシーよりもスケーリングを優先させるが、制限についてきちんと理解すること。

  • 実際の脅威モデルは傍観者ではない。
  • プライバシーを追加してもプロトコルが完全にプライベートになるわけではない。
  • 攻撃というものは良くなるだけだ。

現在は、プライバシーソリューションがどう機能するのか黎明期にあり、プライバシーソリューションを構築し、攻撃する方法について多くの経験はまだない。インターネットのプライバシー問題がどれほど悪いか理解するのに20年かかったように、暗号通貨をベースとしたプライバシー問題の理解にも時間がかかるだろう。そして最後にプライバシー問題はプロトコルへの小さな微調整で魔法のようになくすことはできない。

Compact Block Filter（BIP-158）をRubyで実装してみた

Bitcoin Ruby BIP

Bitcoinの軽量クライアント向けに自身に関連するトランザクションを判別する仕組みとしては、Bloom Filterを利用するBIP-37がベースだが、軽量ノード側のプライバシーの改善とフルノードの負荷を軽減するためCompact Block Filterという新しい仕組みが提案されている↓

techmedia-think.hatenablog.com

Bitcoin Coreのmasterブランチにもマージされていたので、それをbitcoinrbにも移植してみた。

Compact Block Filterの仕組み

BIP-37のBloom Filterを利用したフィルタリングでは、各軽量クライアントがフルノードと接続する際に、クライアント毎にフィルタが作成されフルノードは接続されたクライアント毎に、トランザクションやブロックを伝播すべきかフィルタを通して検証していたが、Compact Block Filterは、各ブロック毎に生成されるようになる。そのため、そのブロックに自身に関連するトランザクションがあるかどうかは、各クライアントがブロック毎のフィルタをダウンロードし検証するようになり、フィルタを作成するエンティティとフィルタを使って検証するエンティティの関係が変わる。

フィルタの作成

Compact Block Filterでは上述の通り、ブロック毎にフィルタを作成する。BIP-158で定義されているフィルタタイプはBasic（フィルタタイプ=0x00）の１つのみで、このフィルタにはブロック内の以下のデータがセットされる。

なので、ブロック内の↑の全てのscriptPubkeyのペイロードをフィルタに登録する。

bitcoinrbではフィルタを作成する対象のブロックと、そのブロックの各インプットが参照するUTXOのscriptPubkeyのペイロードのセットを使って以下のようにフィルタを作成する。

# block はBitcoin::Block、prev_out_scriptsはUTXOのscriptPubkeyのバイナリの配列
block_filter = Bitcoin::BlockFilter.build_from_block(Bitcoin::BlockFilter::TYPE[:basic], block, prev_out_scripts)

実際に中身でやってることは、まず、blockとprev_out_scriptsから要素をピックアップする。

elements = []
block.transactions.each do |tx|
  elements += tx.outputs.select{|o|!o.script_pubkey.empty? && !o.script_pubkey.op_return?}.map{|o| o.script_pubkey.to_payload}
end
elements += prev_out_scripts.select{|s|!s.empty? && !s.op_return?}.map(&:to_payload)
elements.uniq

OP_RETURN及び空のscriptPubkeyを除外し、重複するscriptPubkeyは除外する。

ここまでで要素の準備ができたので、続いて実際にフィルタを作成する。BIP-158ではBloom Filterに代わって、フィルタサイズを削減するためGolomb-coded set（GCS）が使われる。GCSの確率構造では、セット内に存在する要素を問い合わせた場合必ずマッチし、セット内に存在しない要素を問い合わせた場合にそれがマッチする確率は1/Mとなる。つまりBloom Filterと同様、偽陽性が存在する。この偽陽性率は整数のパラメータMで制御され、↑のBasicタイプのフィルタではM = 784931と設定されている。

↑のようにブロック内の要素をピックアップしたら、その要素を使って以下のステップでGCSを構成する。

1. 各要素をハッシュし整数にマッピングする

続いて各要素を、要素の数をN個とするとフィルタの偽陽性パラメータMと合わせた0〜N*Mの数値の範囲内にマッピングする。

まず最初に要素のバイナリのSipHash*1を使ってハッシュ値を計算する（使用するSipHashのパラメータはc = 2, d = 4）。BasicフィルタではSipHashの128 bitの鍵には、ブロックハッシュの先頭16バイトを使用する。これにより鍵はブロックごとに決定論的に導出され、かつブロック毎にランダムになる（先頭16バイトというのはビッグエンディアンでなので、リトルエンディアンとは違い0が続くのは先頭ではなく後方である）。

ruby ではsiphash gemを利用することで、SipHash-24のハッシュ値が得られる。

key = ブロックハッシュの先頭16バイト（バイナリ）
element = フィルタに登録する要素のバイナリ
hash = SipHash.digest(key, element)

SipHash#digestによりハッシュ値が整数で返ってくるので、この整数に F = M * N を乗算し、その上位64 bitを取得する。

(hash * f) >> 64

モジュロ演算は高価なので、結果がある範囲内に一様に分布しかつ高速に計算できるよう↑の計算が採用されている。

↑のように全要素を64 bitのハッシュ値に変換し、その結果を昇順にソートしたセットを用意する。

hashed_set = elements.map{|e| hash_to_range(e) }.sort
2. フィルタへの登録

↑までで、各要素をハッシュし、結果をソートした整数のセットが準備できた。

肝心なのはここからで、要素のハッシュをそのままフィルタに登録するととても巨大なフィルタになってしまうので、圧縮してフィルタに登録する。この時、圧縮に使われるのがゴロム・ライス符号だ。

現在、昇順にソートされた整数のセットを持っているので、この連続する整数の差分をフィルタに登録する。各整数値は↑の計算により一様に分布しているため、その差分は幾何分布に似るとされており、ゴロム・ライス符号はその幾何分布の値を最適に圧縮するための方法になる。ソートされた順番で連続する2つのアイテムの差分を算出し、その差分をゴロム・ライスでエンコードする（先頭の要素の差分は0との差）。ゴロム・ライス符号では、差分の値は2P*2を法とする商と剰余に分割され、別々にエンコードされ（商は単項としてエンコードされ、その後に１ bit0が続き、その後余りがP bitの値としてエンコードされる）、順次BitStreamに追記される。尚、値が幾何分布を形成するため、商は0もしくは１のケースが多い。

  bit_writer = Bitcoin::BitStreamWriter.new
  last_value = 0
  hashed_set.each do |v|
    delta = v - last_value # 連続する要素の差分がdelta
    golomb_rice_encode(bit_writer, p, delta) # deltaをゴロムライスでエンコード
    last_value = v
  end
  bit_writer.flush
  filter = bit_writer.stream
  ...

def golomb_rice_encode(bit_writer, p, x)
  q = x >> p
  while q > 0
    nbits = q <= 64 ? q : 64
    bit_writer.write(-1, nbits) 
    q -= nbits
  end
  bit_writer.write(0, 1)
  bit_writer.write(x, p)
end

BitStreamは追記型のbit型のストリームで、指定bit分データをバッファに書き込み、書き込まれたデータが8 bitになったら、それをストリームに書き込むという、bit単位の書き込み/読み込みが可能なストリームである。 今回Rubyで実装したものが↓

https://github.com/chaintope/bitcoinrb/blob/master/lib/bitcoin/bit_stream.rb

※ Rubyの場合、整数は無限多倍長整数に自動拡張されていくので仕様でデータ長の制限がある場合は、そのデータ長に合うよう計算時に桁溢れの対応を逆に自前でする必要がある。

上記のように、ソート済みの要素のハッシュのセットの各差分を順次、ゴロム・ライス符号でエンコードしたデータをストリームに追記していく。全データ分エンコードしたら最後にBitStreamのバッファについて最も境界に近い値に0でパディングし、ストリームをビット列に変換する。こうやって出来たビット列の先頭に要素数をCompactSizeでエンコードしたデータを付加したデータがBasicタイプのフィルタデータになる。

フィルタの検索

↑でブロック毎のフィルタが作成され、ブロックチェーンとは別にこのフィルタデータがP2Pネットワークで配信されるので、軽量クライアントはそのフィルタをダウンロードし、自身に関連するトランザクションがそのブロックに含まれるか検証する必要がある。

クライアントはまずエンコードされたフィルタから、要素数とフィルタのペイロードをロードする。

n, payload = Bitcoin.unpack_var_int(エンコードされたフィルタのバイナリデータ)
bit_reader = Bitcoin::BitStreamReader.new(payload)

nがフィルタに登録されている要素の数。

続いて、フィルタに検索をかけるデータを用意する。これは自身が持つUTXOのscriptPubkeyなどで、フィルタに登録した時と同様、SipHashを使って整数値に変換し、要素が複数ある場合は昇順にソートしておく。

あとは要素の数分n回、ゴロム・ライス符号でエンコードされたデータをデコードし、その差分を加算していき、検索対象のデータと一致するか順番に検証していく。一つでも一致するデータがあれば偽陽性率Mの下で、フィルタに合致するデータが存在したことになる。

  hashes = 昇順にソートした要素の整数値の配列
  size = hashes.size
  value = 0
  hashes_index = 0
  n.times do
    delta = golomb_rice_decode(bit_reader, p)
    value += delta
    loop do
      return false if hashes_index == size
      return true if hashes[hashes_index] == value
      break if hashes[hashes_index] > value
      hashes_index += 1
    end
  end
  return false

...

def golomb_rice_decode(bit_reader, p)
  q = 0
  while bit_reader.read(1) == 1
    q +=1
  end
  r = bit_reader.read(p)
  (q << p) + r
end

bitcoinrbでは、GCSFilter#match?,match_any?でそれぞれ上記の検索をしている。

フィルタに合致した場合、そのブロック内に自身に関係するトランザクションがある可能性が高いので、軽量クライアントは別途そのブロックをダウンロードし、対象のトランザクションを特定する必要がある。BIP-37のBloom Filterを利用した既存のフィルタではmerkeleblockメッセージの他txメッセージで関連するトランザクション情報をフルノードが送ってくれるが、BIP-157,158のCompact Block Filterでは軽量クライアントがフルブロックデータをダウンロードする必要がある。このため、BIP-37のプライバシーの課題は解消されるが、使用する帯域幅は増加するため、ビッグブロックを掲げるチェーンでは採用し辛いだろう。

Rubyでの実装

ほぼ↑で説明したけど、Bitcoin Coreから移植したRuby実装は主に以下のコンポーネントになる。

テストは

*1:SipHashは鍵付きハッシュ関数の一種で、128 bitの鍵と可変長データを入力に取り、64 bitのダンダムな値を出力する。各プログラミング言語の連想配列のハッシュ関数によく採用されている。

*2:Pはゴロム・ライスのパラメータで今回のBasicフィルタの場合は19

2017年に起きたMoneroのキーイメージを細工したコイン無限生成の脆弱性の内容

Monero Bitcoin Cryptography vulnerability

2017年2月に発覚したMonero（正確にはCryptoNoteのプロトコルを採用している暗号通貨）でコインを無限生成できる脆弱性について、原因が曲線の特性に起因するもので興味深かったので調べてみた。

ww.getmonero.org

この脆弱性自体は実際にMoneroでは悪用されることなく、表向き別の目的でパッチが当てられ、問題は回避されている。

脆弱性の内容

MoneroのベースとなっているCryptoNoteは匿名通貨を実装するプロトコルの1種で、中でも特徴的な技術がリング署名。トランザクションを作成する際に、自身が所有するUTXOの他に、そのUTXOと同じ量のコインを持つ他人のTXO*1をブロックチェーンから複数選択し（現在は最低10個）、それを実際に使用する自分のUTXOと一緒にインプットにセットする。この時点でインプットにセットしたTXOの内、自分が秘密鍵を知っているのは1つだけで、その秘密鍵とインプットにセットしたTXOの公開鍵のセットを使ってリング署名を生成する。こうすることで、インプット内のいずれかのTXOが使用されたのは分かるが、実際にどのTXOが使用されたのかは分からず、これによって送信元の匿名化を図る。

ただ、このままだとどのインプットが使われたか分からず、UTXOの二重使用が発生する可能性がある。そのため、インプットには実際に使用するUTXOに紐づく秘密鍵から生成したキーイメージがセットされ、リング署名のインプットの１つにもなる。トランザクションインプット内のキーイメージがこれまで使用されていないかどうかチェックをすることで、二重使用を防ぐ仕組みになっている。

キーイメージは、秘密鍵をx、対応する公開鍵をP = xGとした場合、I = x * hashp(P)で計算される。hashp()は公開鍵から決定論的にランダムな公開鍵を生成するハッシュ関数。

今回の脆弱性では、このキーイメージが特別な方法で変更することができたため、それによって二重使用が可能な状態だった模様。

では具体的にどうやってキーイメージを変更するのか？という点だが、これは↓のサイトが詳しい。

nickler.ninja

monero.stackexchange.com

曲線Ed25519の特性

CryptoNoteはEd25519の曲線を使用している。Ed25519の特性の１つは、曲線上の点の数（曲線の位数）がベースポイントGによって生成された群内の点（群の位数）より多いという点。群の位数は素数ｌ = 2^252 + 27742317777372353535851937790883648493で、曲線の位数は8*lとなる。曲線の位数と群の位数の比はcofactorとして知られており、Ed25519の場合は8。ちなみにBitcoinで使われている曲線secp256k1のcofactorは1なので、群の位数と曲線の位数は等しい。

  • cofactor == 1の場合、部分群は曲線全体で、任意のゼロ以外の点が生成点となる。曲線の方程式を満たす点はすべて部分群の一部。
  • cofactor != 1の場合、素数位数の部分群は曲線の厳密なサブセットで、点を考慮すると、曲線の座標が方程式と一致するか検証するだけでは、点が適切な部分群にあることを保証するには不十分。さらに位数がrの倍数でない点が存在する。cofactor = 8の曲線25519で起こり、その場合それを使用するプロトコルでいくつかの注意が必要になる。例えば曲線25519でDiffie-Hellman鍵交換をする場合、Diffie-Hellmanの秘密鍵は8の倍数を選択する必要がある。これにより点が確実に部分群に格納される。

cofactorは曲線上に低位の群が存在すること示している。例えばPを26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05で表される点とし、Pから8*P = 0を意味する位数8の（ユニークな）群を生成する。低位数の曲線上にはわずかな点しか存在しない。その点を見つける１つの方法は、a*lの位数で曲線上にランダムな点を生成し、その点にIを乗算して位数1 <= a <= 8の点を得る。一方、CryptNoteでキーイメージを生成する際に使用するハッシュ関数hashpは結果を出力する前に8を乗算して、結果の点が素数位数群にあることを保証する。

攻撃と解決

攻撃者がコインを持っており、キーイメージI = x*hashp(P)を使ってそのコインを使用するための通常のワンタイムリング署名を作成できると仮定する。普通にIを使えば攻撃者が持っているコインを使用できるが、コインを使用後さらにIとは別のキーイメージI' = I + Lを生成して同じコインを使用できる。ここで、Lは位数oの下位の点である（曲線上には存在するが群の点ではない）。

キーイメージの検証は元々s*hashp(P) + e*Iを評価するようになっている。

  • eは（暗号学的ハッシュ関数によるランダムオラクル値なので）攻撃者には選択できない。
  • sは署名者が署名の所有権と一意性を証明するために使用する値。

なので細工するとしたらIの部分。oがeで割れる場合（e = e'*o）、e*I' = e*I + e'*o*L = e*Iとなり、Iと同じ方法でI'を使って有効な署名を作成することができる（ただしメッセージmは今度はI'にコミットする必要がある）。つまり、曲線の方程式を満たす点は存在するが、Ed25519で指定された群には含まれない（部分群内にある）点を使用する。これらの点のいくつかは8で割り切れる位数の群にある。これらの点の１つがキーイメージとして選択されていて、ランダムオラクル値eが部分群の位数の倍数である場合、キーイメージの検証は約分のため正しい点に戻すようマップされるようになる。そのため有効なキーイメージに、群の位数が8で割り切れる点を加算すると1/8の確率で本当のキーイメージと同じ点に写像されるeを入手できる。

ちなみにByteCoinではこれをはるかに効果的な方法で悪用された模様。攻撃者は低位キーイメージIを生成するのに低位公開鍵Pを使用した。曲線上には8個の低位点しかないので（CryptoNoteでは同じ点の複数の表現を禁止しているため）、この攻撃は１つのブロックチェーン上で8回実行できる。

Moneroで実装された修正は、キーイメージが素数位数群内に存在する点であることを保証するためにl*I = 0をチェックすることで、各キーイメージIが素数位数l群を生成することを検証する。実際に、l' != lを持ちl*I = 0ならば、lはl'で割り切れなければならいが、これはlが素数であるため矛盾する。この修正による追加コストは、トランザクションインプット毎に1回のスカラー演算ですむ。

というのが2017年の無限コイン生成の脆弱性の内容。

Bitcoinのsecp256k1と違い、cofactor > 1の場合、群の位数と曲線の位数が異なり、曲線上に低位の群が存在して↑のような考慮事項が発生すると。問題はEd25519自体の脆弱性とかではなく、キーイメージを生成する際にEd25519の場合は必要な位数の検証が抜けていたという点で、そういう安全性の評価までちゃんとする必要があるんだろうけど、中々難しいものもあるので、secp256k1のようなcofactor1の曲線を使用するの方が無難な気もする。

*1:TXOと記載しているのは、未使用でも使用済みでも良いため。参加ノードからは実際に使用済みかどうかは分からない（但し、今は不可能だがmixinするインプットが0の場合は使用されたインプットが明確になる）。