Develop with pleasure!

福岡でCloudとかBlockchainとか。

Verifiable Delay Function

最近ブロックチェーン関連のペーパーでよく話題に上がる新しい暗号プリミティブVerifiable Delay Function(VDF)について調べてみた。

VDFに関する研究は、以下のサイトでまとめられている。

https://vdfresearch.org/

今回はVDF Day 2019のDan Bonehのセッションを見てみる↓

http://diyhpl.us/wiki/transcripts/verifiable-delay-functions/vdf-day-2019/dan-boneh/

VDFとは?

VDFは正直な参加者が並行多項性を持っている場合でも、評価にTステップかかることになっている関数(並列処理してもスピードアップしない)で、分散環境において難しいとされる偏りの無いランダム性や時間経過のプロキシなどの機能を提供する。

VDFには

  • セットアップ
    セキュリティパラメータλと時間制限Tを入力にとり、公開パラメータpを生成する。
  • 評価
    評価関数は(p, x)を入力として、出力yとプルーフを生成する。並列コンピュータを使用したとしてもこれにはTステップかかり、並列処理によって計算が高速化することはない。
  • 検証
    検証アルゴリズムは(p, x, y, proof)を入力として、yがVDFの正しい評価かどうか迅速に示す。

の3つのアルゴリズムがある。

安全性

VDFには2つの安全性要件がある。

  • 一意性
    任意の値xが与えられた場合、検証者を納得させる値yは1つだけ存在する。同じyに対して異なるプルーフを持つことができるが、yは1つだけ。
  • シーケンシャル性
    敵対者が並列マシン、特に多項式個数のプロセッサを使っている場合でも、時間Tを費やさない限り、VDFの出力が完全にランダムに見える。

分散環境においてランダム値を生成しようとした場合、参加者はそれぞれランダム値を計算し、それを掲示板に貼り、ランダム値はその全てのXORで生成される。この場合、最後の参加者が最終的な生成値を制御できてしまう。これを防ぐために事前にランダム値のハッシュ値をコミットメントとして提出させる方法が考えられるが、コミットメントが提供された後ランダム値が提供されなかった場合、プロトコルは停止する。公開されなかったコミットメントは無視するというのは安全ではないからだ。

そこで分散環境におけるランダム値の生成にVDFを導入し、VDFの出力値をランダム値とする。なぜこれが可能で偏りのないランダム性になるのか?というと

全員が正午までにランダム値を送信し、特定の時間になるとそれがプロトコルの参加者になる。VDFは送信時間帯よりも長くなる。VDFのシーケンシャル特性は、VDFを計算するためには送信時間よりも時間がかかるため、最後の送信者がプロトコルへ多くの入力と試行できないこと保証する。 gallium-arcinide ASICなどの最新技術を持っていたとしても、時間がかかることを確実にする必要がある。

シーケンシャル特性により最後の参加者は出力にバイアスをかけられなくなる。バイアスをかけるためには多くの時間を必要とするため。また、一意性により出力に曖昧さがないことが保証される。シーケンシャル特性と一意性によってVDFは困難になる。

VDFの構築方法

VDFを構築するにあたっては以下のような構築方法がいくつか挙げられている。

ハードウェアEnclave

VDFを構築するのにとても簡単なのはハードウェアEnclaveを使う方法。Enclave内に暗号鍵を保存し、その鍵を使ってVDFを生成する。この場合、公開パラメータは公開鍵暗号の署名、つまり公開鍵は公開される。入力が入るとEnclaveは時間遅延を強制し、入力XのHMACもしくはPRFを生成し、出力に署名してVDFがハードウェアによって正しく計算されたことを証明する。ハードウェアEnclaveがあればVDFの構築は非常に簡単になる。しかしHMACを生成する際の秘密鍵が盗まれると、VDFの時間外で誰もが即座に結果を計算することができてしまう。

そのため、Enclaveの保護が重要だが、十分な資金があればこのハードウェアEnclaveを破ることは可能と思われ、プライバシーやデータ保護には問題がないが、コンセンサスを破ることが資金の損失に繋がるコンセンサスに採用するのは危険になる。

ハッシュ関数

ハッシュ関数を利用してもVDFを構築することはできる。この場合、公開パラメータはSNARKのパラメータで、VDFはSHA256を繰り返し評価するのに時間Tかかるハッシュチェーンとして定義される。しかし、出力が正しく計算されたかどうか検証するためにSNARKが登場する。しかしこれを正しく動作させることは難しい。プルーフはハッシュチェーンが正しく計算されたことのSNARKだが、SNAKRの計算にはチェーンの計算よりも時間がかかるため、それに対処する必要がある。

その対処として考えられているのが検証をSNARKのプルーフの検証にするというもので、最近、Recursive SNARKs(= SNARK内でSNARKのプルーフの検証を行う仕組み)として研究が行われている。SBC20の「Fractal: Post-Quantum and Transparent Recursive Proofs from Holography」のセッションでは、Recursive SNARKsを効率的に実現するための量子耐性を持つ新しい方法としてFractalというプロトコルが提案されている。

置換多項式

置換多項式からVDFを構築するというアイディアもあるっぽい。置換多項式は、有限体の元との置換多項式で、有限体内の2点x, yについて多項式f(x)がf(y)と等しくならないもの。この構造で使用する特性は、多項式の根*1を見つけること。VDFの入力は値xで、xと等しくなるようなf(y)の値yを求める。そのようなf(y)を見つけたい場合、多項式f - xの根を見つけることになる。この根を見つけるための実用的な方法は、シーケンシャルに行われるGCP(Generalized Characteristic Polynomial)計算となり、VDFに使えるのでは?とされている。

課題はショートカットがなくGCP計算が最良の計算方法である置換多項式があるかどうで、まだ研究がされてないっぽい?

代数的構成

代数的な構成では、有限巡回群Gから始まり、群Gの位数は不明、つまり群に含まれる要素の数を誰も知らないという仮定を持つ。公開パラメータは群へのハッシュ関数。VDFはxを入力として受け取り、群にハッシュし、出力yを以下のようにT回の平方演算を求める。

 {y = H(x)^{2^{T}}}

これは時間の証明やtimelock puzzlesなどで使われており、この種の関数はよく使われる。

こうやって生成された出力が正しいかどうかの検証proofs of exponentiationを行う必要がある。これについてはサーベイ論文で解説されてるっぽい。

↑で群の位数が不明と書いたが、群の位数がもし分かっていると、例えばDとすると、 {2^{T} \mod D}を計算でき小さな冪乗になり評価は簡単になる。VDFとしては、群の位数が分かればTは対数時間まで加速するため、群の位数は不明でなければならない。

未知の位数の群をどうやって生成するか?

既知の位数の群でVDFを構成した場合、安全はなくなるため、未知の位数を持つ群を生成する必要があるが、まずこれをどうやって生成するのか?

1番最初に思いつくのがRSA。2つの整数pとqを選択し、それらを乗算する(n = p * q)と因数分解出来ない限り群の位数は不明になる。この因数分解を知っていれば群の位数を知っていることになるので、誰も因数分解を知らない方法でこれを構築する必要があり、そのためにTrusted Setupが必要になる。また十分大きなnにする必要があり、30,000-40,000ビットほどの大きさである必要がある。

RSAの問題はこのTrusted Setupが必要なことで、RSAモジュラスが2つの巨大な素数の因子からなり、その因数分解を誰も知らないことを誰もが確信するように生成するプロトコルが必要になる。

この辺りの研究は、SBC20でも「Scalable RSA Modulus Generation with Dishonest Majority」として取り上げられている。

Class Group

未知の位数を持つ群のもう1つの候補で注目されているClass Groupだ。Class Groupというのは1990年代に提案された暗号プリミティブだが、まだ実際に展開されたことは無い。Class Groupは素数で指定された群を持ち、その素数が1000ビットのように大きな値の場合、その群の位数を計算する方法を誰も知らないという特徴がある(なぜそうなるのか、どういうものなのか詳しくは知らない)。

これにより素数を選択することで未知の位数の群を入手し、VDFに使用できるということらしい。利点としてRSAで必要だったTrusted Setupを必要としない。ネックになるのはRSAよりClass Groupの演算の方が遅いのと、Class Groupの演算がどれくらい並列化できるものなのかがはっきり分かっていない点にある。

尚、現状代数学的なアプローチは量子耐性はなく、量子耐性を持つのはハッシュベースの構成だが、これはRecursive SNARKsを必要とする。

といずれも現在進行系でそれぞれに一長一短があり、さまざまな研究が進んでいる。

*1:p(x) = 0となるようなx

冗長的な支払経路を用いることでLN支払のスループットを向上させるBoomerang

Lightning Networkで決済可能な金額は各チャネルのキャパシティに依存する。この制限を緩和するため、支払に複数の経路を使用するAtomic Multi-Path Payments(AMP)が提案され、各ノードに実装されつつある。AMPの仕組みについては以前書いた↓参照。

techmedia-think.hatenablog.com

このAMPを利用した支払の経路に冗長性をもたせることで支払のレイテンシースループットを向上させようという提案が最近発表された↓ので、どういう内容か見てみる。

https://arxiv.org/pdf/1910.01834.pdf

AMPの課題

AMPは(OG AMPもBase AMPも)、全ての経路の支払の準備が出来るまで支払の受け取りを開始しない仕組みになっている。

例えばアリスからボブに4コインを送金するのに、1コインずつ4つの経路を使ってAMPで送金する場合。

  • 経路1: →
  • 経路2: →
  • 経路3: →→→→
  • 経路4: →

経路1,2,4は1秒でHTLCの転送が完了するのに対し、経路3は4秒かかったとする。この場合全てのHTLCの転送が完了した段階でボブはコインのクレームを実行するので、経路3の転送を受信するまで経路1,2,4はアイドル状態になる。つまりこの送金における送金完了までに時間=TTC(Time-to-completion)は4秒で、消費されるコインの流動性は、4 · 4 s = 16 · sとなる。

AMPでは複数の経路を使用した支払のアトミック性を担保するために、「最後まで全て待つ」という方針を掲げているが、遅延した経路がいるとその分レイテンシースループットが犠牲になる。

Boomerang

↑の課題に対して、AMPの複数の経路に冗長性を持たせることで、レイテンシーを削減し、スループットを向上させようというのがBoomerangプロトコル

上記の4コインの送金を1コインずつ8つの経路を使って支払をする。この場合、4つの経路が冗長であるため、8つの経路の内、4つの経路のHTLCの転送が成功すれば送金完了で、ボブは余分なコインは盗めないと仮定する。

  • 経路1: →
  • 経路2: →
  • 経路3: →→→→
  • 経路4: →
  • 経路5: →
  • 経路6: →
  • 経路7: →→→→
  • 経路8: →

6つの経路が1秒で転送完了し、2つの経路が4秒かかったとすると、送金のTTCは1秒で、消費されるコインの流動性は、4 · 1 · 1 s + 2 · 1 · 1 s + 2 · 1 · 4 s = 14 ·sとなり、冗長的な支払によりTTCが削減でき、結果的に消費される流動性が少なくなり、より高いスループットが得られるというもの。

Boomerangプロトコル

↑のような冗長経路を採用した場合に必要な仕組みが、ボブが元の送金額より余分に受け取ろうとするカウンターパーティリスクなくすこと。ここに秘密分散の仕組みを利用する。

アリスとボブは、送金する資金をv個のTxに分割して送金すること、u個の冗長性をもたせることに合意するものとする。この時トランザクションの総数はw = v + u

ボブはまず、ランダムな値 {α_0, ..., α_v}を選択する。そしてこのランダム値を係数とした次数v多項式P(x)を作成する。

 {P(x) = \sum^{j}_{j=0} α_{j} x^{j}}

続いて、ボブは多項式の各係数 {α_0, ..., α_v}を一方向関数Hにかけた値を計算し、その値 {H(α_0), ..., H(α_v)}をアリスに提供する。

ここで、Hは {g \in \mathbb G, H(α) = g^{α}}とした場合 {H(cα + dβ) = H(α)^{c} H(β)^{d}}の関係が成立する準同型性を持つ一方向関数。

アリスは受け取った {H(α_0), ..., H(α_v)}とその準同型性を利用して、多項式P(x)を評価するハッシュを計算できる↓

 {h_i = H(P(i)) = H(\sum^{v}_{j=0}α_{j}i^{j}) = \Pi^{v}_{j=0}H(α_{j})^{i^{j}}}

こうしてi個め経路でのチャンレンジとして {h_i}を使うHTLCタイプの転送コントラクトを構成する。

このような転送を受信したボブはi個めの経路のコインを受け取るために、 {h_i}のプリイメージを明らかにする。もしボブがここで、v個以上の {h_i}のプリイメージを明らかにすると、アリスはラグランジュ多項式補完を使って {α_0, ..., α_v}を計算することができる。そしてこの {α_0}は、送金額を取り戻すことができるシークレットとして機能する。ただし、ボブがv個より多くのプリイメージを明らかにしなければ、アリスは {α_0}を計算することはできない。

このように冗長性を持たせた経路を用いた支払において、相手が余分な償還を行った場合、それを取り消すことができるよう、秘密分散の仕組みを利用することでカウンターパーティリスクに対処しているのがBoomerangプロトコルの特徴だ。

Boomerangコントラクト

上記を実現するBoomerangコントラクトの結果は以下の3つのいずれかになる。

  • 転送がクレームされずタイムアウトを迎えアリスに資金が戻る。
  • 転送が条件が満たされボブによりプリイメージが公開されると、この経路がアクティベートされ資金がRetaliation Txに送られる。Retaliation Txのコインの使用方法は以下のいずれかになる。
    • アリスがボブの余分な引き出しのプルーフ(↑の {α_0})を提出した場合、資金はアリスに戻る。
    • 設定されたタイムアウトを過ぎ、それまでにアリスによるプルーフの提出がない場合、資金はボブのものになる。

なお、現状のBitcoinには↑のような準同型性を持つ一方向関数Hは存在しないため、Bitcoin Scriptを使って実現する場合は、スタックから要素xを取り出し、xGをスタックに戻す新しいopcodeECEXP<g>Bitcoin Scriptに追加する必要がある。

ペーパーではこれをeltooのペイメントチャネルに適用する方法について書いてる↓(Eltooの仕組みについては、以前解説したGBEC動画参照

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

eltooのSettlement Txに、HTLC転送のアウトプットを追加し、そのアンロック条件が↑のタイムアウトによる送信元への返金か、プリイメージ公開によるRetaliation Txへの送金。単純なeltooプロトコルではSettlement Txのみで完結したてけど、アリスがボブの超過引き出しに対応するため、Retaliation Txが作られ、ここで一定期間ボブのコインの入手がロックされ、その間超過引き出しがあれば、そのプルーフの提出により、すべての送金を取り消しできるようになっている。

Adaptor Signatureの利用

↑の場合、新しいopcodeがBitcoinに追加されなければ実現できないが、代わりにAdaptor Signatureを使うことでScriptlessに同様のことができるようになる。SchnorrベースのAdaptor Signatureでも可能だし、やろうと思えばECDSAベースのものもある。

Grinで発見された脆弱性CVE-2020-6638の内容

ちょっと前にGrinで発表された脆弱性CVE-2020-6638↓の内容について見てみる。

https://github.com/mimblewimble/grin-security/blob/master/CVEs/CVE-2020-6638.md

Grinの構成要素

具体的な脆弱性の解説の前に、Grinの構成要素について抑えておく↓

Pedersen Commitment

GrinではMimblewimble実装のためトランザクションのアウトプットが以下のようなPedersen Commitmentになっている。

C = rG + vH

Gはベースポイント、Hは誰もその離散対数を知らない2つめのベースポイントで、rがブラインドファクター、vがコインの量。

このPedersen Comittmentは、加法準同型性を持っているので、以下のような加算が可能である。

C1 = r1G + v1H
C2 = r2G + v2H

C1 + C2 = (r1 + r2)G + (v1 + v2)H

そしてGrinでは、アウトプットの合算からインプットの合算を差し引くことで、vの合算値が0になることでコインの総量が増えていないことを証明し(正確にはrange proofと合わせて)、残ったrについて、それを秘密鍵とした有効な署名を作ることで有効なトランザクションを作成している。具体的な仕組みについては、GBECの解説動画参照↓

goblockchain.network

ノードの検証内容

各Grinノードは、以下のデータを持っている。

そしてこの3つそれぞれに対してMMR(後述)を持っている。Grinの完全なステートを維持していると、以下の検証が可能になる。

  1. トランザクションカーネルの署名が正しいか検証する。
  2. 全ブロックのカーネルコミットメントの合計が、全てのTXOコミットメントからコインの供給量を引いたものと等しい(全てのTXOコミットメント値からコインの供給量を引くとコミットメントのHの項が0Hとなり、ブラインドファクターのみが残り、その合計がカーネルコミットメントの合計となるため)。これにより、全てのカーネルとコミットメントが正しく、コインが予期せず生成されていないことが証明される。
  3. TXOセット、range proof、トランザクションカーネルに対してそれぞれMMRを維持しており、各ブロックヘッダーはこの各MMRにコミットしている。

3つのMMRの内、TXOセットのMMRは追記専用でジェネシスから全てのアウトプットのコミットメントで構成されている。

MMRとは?

MMRというのはMerkle Mountain Rangesの略で、マークルツリーを代替するもの。MMRは追記のみをサポートするツリーで、要素は左から右へと追加され、ペアができるとそれに親が構成させる。例えば11個の要素を追加したツリーは以下のようになる。

高さ

3              14
             /    \
            /      \
           /        \
          /          \
2        6            13
       /   \        /    \
1     2     5      9     12     17
     / \   / \    / \   /  \   /  \
0   0   1 3   4  7   8 10  11 15  16 18

各要素は全て左から順にツリーのリーフとして追加され、ペアができるとその上のノードができ、高さ3のツリーが1つと高さ1のツリーが1つ、高さ0のツリーが1つできた山になる。

また値をプルーニングをすることも可能で、例えば上記のMMRからリーフ0, 3, 4, 8, 16を削除するとツリーは以下のようになる。

高さ

3             14
            /    \
           /      \
          /        \
         /          \
2       6            13
       /            /   \
1     2            9     12     17
       \          /     /  \   /  
0       1        7     10  11 15     18

3, 4のように左右の要素が無くなった場合、その親要素も削除される。

UTXOセット、range proof、トランザクションカーネルのデータについて、それぞれこのMMRを構成し、そのルートハッシュをブロックヘッダーにコミットするようになっている。

UTXOの管理

↑でTXOセットのMMRは全てのコミットメントを含んでいると述べたが、ではあるコミットメントが使用された場合どうなるのか?と疑問が生じる。

実は、コミットメントが使用済みかどうかはMMR自体では管理されず、軽量なbitmapで維持されている。各ビットはUTXOセットのMMRの各リーフにマッピングされており、このbitmapを使ってツリー上のどのコミットメントが使用済み/未使用なのか判断するようになっている。

脆弱性の内容

↑のようなPedersen Commitmentの特性を利用すると次のようなことが可能になる。

2つのアウトプットを持つトランザクションのアウトプットが上記C1, C2の2つのPedersen Commitmentであった場合、トランザクションカーネルを作成し、有効な署名を作った後でアウトプットを以下の2つの異なるPedersen Commitmentに置き換えることが可能になる。

C3 = r2G + v1H
C4 = r1G + v2H

C3 + C4 = (r2 + r1)G + (v1 + v2)H

合算したコミットメントであるC1 + C2 = C3 + C4になるためだ。

署名はアウトプットの合計からインプットの合計を差し引いた結果の公開鍵rGに対して有効な署名が作られればいいのだが、Grinの実装ではトランザクションの署名を作成する際に使用する署名対象のメッセージはトランザクションカーネルから作られる。具体的にいうと、手数料、kernel feature、block heightのデータで構成される。つまりBitcoinなどと違ってトランザクションのインプットやアウトプットがメッセージに含まれていないので、トランザクションに署名後にトランザクションのアウトプットをC3とC4に変更してもトランザクションの署名は有効なままとなる。

ブロックへの拡張

さらにこれをブロックレベルに拡張することができる。↑と同じ方法を使って、ブロック内で使用されるアウトプットのセットが異なる2つの競合するブロックを作ることができる。これはPoWも署名も有効なブロックを作成した後に、使用するアウトプット(インプット)のペアのみを置き換えることで簡単に作成することができる。

  • Block A
    • Inputs:
      • C1
      • C2
  • Block B
    • inputs:
      • C3
      • C4

C1とC2を使用するブロックAを作成し、その後C1とC2をC3, C4に置き換えたブロックを作った場合(いずれも送信先は同じ)、ブロックAとブロックBはブロックヘッダーもPoWも同じで有効なままだ。これはMMRがTXOにコミットしているため、ブロックAもブロックBもそのMMRは同じになり、競合するブロックを作れてしまう。UTXO自体をMMRで管理していないためだ。こによりUTXOのbitmap自体のmalleabilityが発生する。

ブロックAとブロックBが同じタイミングで公開されると、ブロックAを受信したネットワークAはC1、C2を使用済みとし、ブロックBを受信したネットワークBはC3, C4を使用済みとマークする。次にC3を使用するトランザクションをブロードキャストすると、ネットワークAではそれを使用可能として受け入れ、ネットワークBではそれを既に使用済みであるとして受け入れないという状況が発生し、この段階でチェーンが分岐する。

このような状況が発生すると分岐したチェーンを復元するのは難しい。幸いにもそういった現象が発生していないのが救いだ。

解決方法

修正の方針はシンプルで、現在ブロックヘッダーは全TXOに対してコミットしているが、これを全UTXOに対してコミットするように変更するというもの。具体的には既存のアウトプットのPMMR(プルーニングしたMMR)と現在の未使用のUTXOを管理しているbitmapの状態を組み合わせたルートにコミットするようになる。これにより↑のような競合ブロックを作成するのができなくなる。

またブロックヘッダーがUTXOに対してコミットするようになるので、チェーンの初期同期の遅延のボトルネックが改善されるという副次的効果もある。

未使用のUTXOを所有していることをUTXOを明らかにせず証明するプロトコルPoDLE

BitcoinトランザクションのプライバシーやFungibilityの向上のためCoinJoinを実装しているJoinmarketで提案されているPoDLEというプロトコルが面白かったので見てみる↓

joinmarket.me

PoDLEプロトコル

PoDLEが解決するのは、自分があるUTXOを所有していて、別のユーザーにそのUTXOを所有しておりかつ未使用であることをUTXO自体を公開することなく証明したいという問題。

暗号コミットメントを使ったアプローチ

こういう問題への対応としてよく上げられるのが暗号コミットメントの利用。UTXOの情報とランダムに選択したnonceを使って

commitment = hash(UTXO || nonce)

を作成する。そしてプロトコルの後半でUTXOをnonceを明らかにすることで、commitmentを解くというもの。

UTXOだけでなくnonceを必要とするのは、例えば証明したいデータのセットが小さい場合、相手がどのUTXOか特定することが可能になるため。BitcoinのUTXOセットは有限で誰もが知っている情報なので、UTXOのみでcommitmentを作成すると、それがどのUTXOのものなのか計算できてしまう。

一方、nonceを加えた場合はまた別の問題が生じる。アリスがあるUTXO Aをcommitmentを作成し、それをボブとキャロルに渡す場合。UTXO Aはどちらか1人にしか使えないが、UTXO Aは同じままnonceだけ違う値を使って異なるcommitmentを作り両者に渡してしまうことが可能になる。

そのため単純なコミットメントスキームでは上記の問題を解決できない。

離散対数の等価性の証明を使ったアプローチ

そしてGreg Maxwellによって提案されたのが離散対数の等価性を証明するという方法。

まず楕円曲線のベースポイントGに加えてもう1つ別のNUMSポイント(誰もGに対してその点の離散対数を知らない点)Jを用意する。

  1. アリスが所有しているUTXOに使われている公開鍵を {P_1 = xG}とした場合、アリスは同じ秘密鍵xとJを使ってもう1つの点 {P_2 = xJ}を計算する。
  2. アリスは {P_2}を使ってコミットメント[tex :{C = H(P_2)}]を作成し、提供する。
  3. 公開された使用済みの情報にCが存在しないければCが未使用であることが確認できるので、ボブはアリスに対してプロトコルを継続する。
  4. アリスはランダムなnonce kを選択し、以下の計算を行う。
    •  K_G = kG
    •  {K_J = kJ}
    •  {e = H(K_G || K_J || P_1 || P_2)}
    •  {s = k + ex}
  5. アリスは上記で計算した {K_G, K_j, e, s, P_1, P_2}をボブに明らかにする。
  6. ボブは受け取ったデータに対して以下の検証を行う。
    • 以前アリスから受け取ったCが {H(P_2)}と等しいかどうか。
    • チェーン上のUTXOに {P_1}で構成されるUTXOがあるかどうか。
    • Schnorr署名が有効な署名かどうか
      •  {K_G = sG - eP_1}
      •  {K_J = sJ - eP_2}
      •  {e = H(K_G || K_J || P_1 || P_2)}

このプロトコルの特徴として、

  • アリスが事前に公開するcommitmentのプリイメージ {P_2} {P_1}と同じ秘密鍵を使っているもののBitcoinのUTXOセットには存在しないので、nonce抜きにハッシュしたデータを共有してもアリスのUTXOがそれによって特定されることはない。
  • Schnorr署名の検証により、UTXOを所有していることが確認できる。
  • 同じ公開鍵 {P_1}から {P_2}以外の異なるコミットメントを作成する(別の秘密鍵の公開鍵を作ってコミットメントとする)ことができない。これをすると最後の署名検証が失敗する。

↑のプロトコルでは2つめのベースポイントJについてJ = zGとなるような離散対数zを誰も知らない点であることが重要。

以上がPoDLEプロトコルの仕組み。

Joinmarketでの活用

JoinmarketではCoinJoinプロトコルを実行するにあたって、悪意あるユーザーがプロトコルを途中で止めることで、相手のUTXOセットの情報を学習し、最終的にチェーン上のミキシングトランザクションをアンミックスすることを可能にする攻撃が懸念されていた。

これに対応するために↑のPoDLEプロトコルを組み入れている。

  1. ユーザー(マロリー)は、ミキシングのセッションを開始する前に、PoDLEプロトコルにしたがって自身のUTXOのコミットメントをJoinmarketのネットワークで公開する必要がある。
  2. 別の参加者(ボブ)とその特定のUTXOを使用してCoinJoinを始めると、マロリーは同じコミットメントのUTXOを使って他のユーザーとはプロトコルを実行できなくなる。
  3. ボブがマロリーにコミットメントのオープンを依頼すると、マロリーはUTXOの情報を明らかにする。
  4. ボブはマロリーから受け取ったUTXOが事前に公開されていたコミットメントと一致すれば、自身のUTXOを開示しCoinJoinプロトコルを継続する。

マロリーが悪意あるユーザーであった場合、4でボブのUTXOセットを学習し、それ以降のプロセスを中止できる。ただ、同じUTXOを使って別のユーザーと同じことはできない。そのため、別のユーザーのUTXOセットを学習したい場合、UTXOを使用して別のUTXOにする必要がある。これにはコストが発生するので、こういうスパイ行為に対してコスト面での負担を強いるようにしているというわけみたい。

Lightning NetworkのFundingでも活用?

LNでは、現在Funding Txはチャネル参加者のどちらか一方の資金をファンドするようになっているが、これを両者の資金をファンドできるようDual Fundingをサポートしようという議論が進んでいる。

Dual Fundingの場合、両者がそれぞれUTXOを提供することになるが、この調整をする際に、↑のJoinmarketの悪意あるユーザーのようにプロトコルを途中で停止し、相手のUTXOセットを学習することでLNユーザー管理下のUTXO情報がリークされる可能性がある。これに対して、PoDLEのようなプロトコルを導入し、途中で停止した場合、UTXOやPoDLEのデータをゴシップすることでスパイ行為への対応としようという議論もある。

離散対数の等価性の証明は他にも適用可能なユースケースがあるかもなー。

Bulletproofsを利用したrange proofの仕組み

techmedia-think.hatenablog.com

↑でBulletproofsの基本となる内積の証明の仕組みについて書いたので、今回はこれがCTやMimblewimbleなどで必要とされるrange proofにどう適用されるのか見ていく。

range proofとは?

CTと同様Mimblewimbleなどでもコインの量を秘匿するのに以下のような楕円曲線を利用したPedersen Commitmentが採用されている。

C = xG + aH

xはBlinding Factor(MWでは秘密鍵に該当)で、aがコインの量。コインの量をこのようなコミットメントCにすることで、外部からaの値を分からなくしている。具体的な仕組みが知りたい場合は、以前撮影したMWのGBEC動画を参照↓

goblockchain.network

このようなPedersen Commitmentを使ってコインの量を秘匿する場合には、コインの量aが決められた正の範囲(0〜264など)にありマイナスやオーバーフローをしていないことを証明する(マイナスやオーバーフローしているとコインのインフレーション(生成)が可能になる)range proofが必要になる。

CTの初期の提案では、このrange proofにBorromean Ring Signatureを使用するものになっていた。ただしこの証明のサイズの大きさ(数百バイトのTxに対してrange proofのサイズが2.xKBなど)がCT導入のハードルとなっていた。この問題を解消するために提案されたのがBulletproofだ。

Bulletproofを利用したrange proof

Bulletproofを利用したrange proofプロトコルを表す図が↓

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

ぱっと見ても???なので、具体的にどういうことをやっているのか見ていこう。

range proofの内積表現

図の左上にあるように、range proofで証明したいのはある値vが0 ≦ v < 2nの範囲内にあること。例えばn = 4で、v = 5の場合、5が0〜24-1の範囲内にあることを証明する。

証明者は最初にランダムな値γを選択し、値vへのコミットメントを作成する(CTやMWのアウトプットに相当)。

 {V = γ\tilde{B} + vB}

vがある範囲内にあることを証明する場合、図の左上の2番めの枠のようにvは以下の2つのベクトルの内積として表現することができる。

  • vのビット表現 {a_L \in {0, 1}^{n}}。v = 5の場合は {a_L = (0, 1, 0, 1)}というベクトル
  • 2nのベクトル。つまり {(2^{n-1}, 2^{n-2}, ..., 2^{0})}というベクトル

この2つのベクトルの内積は、 {<a_L, 2^{n}> = v}になる。(n = 4で、v = 5の場合、 {2^{3}・0 + 2^{2}・1 + 2^{1}・0 + 2^{0}・1 = 5}

このような内積を使った表現をした場合、証明するステートメントは↓

  1. 2つのベクトルの内積が値vであること( {<a_L, 2^{n}> = v})。
  2.  {a_L}のベクトルの各値が0か1であること。 {a_L}の各要素から1を引いたベクトルを {a_R = a_L - 1}とすると、この2つのベクトルの各要素を乗算した結果のベクトルの要素は全て0になること {a_L \circ a_R = 0^{n}}。また、 {(a_L - 1) - a_R = 0}

これが図の左上の部分。

ステートメントの結合とBlinding Factorを使った内積のブラインド

続いて、↑の1と2のステートメントをチャレンジスカラーを使って結合し、Blinding Factorを追加する。

  • まずその前に、証明者が {a_L}を直接公開しては意味がないので(値を公表することになる)、range proofを作成する証明者は、↑の実質vの値を指す  {a_L}へのコミットするVector Commitmentを作成する。このVector Commitment Aはランダムな値αを選択し、 {A = α\tilde{B} + a_LG + a_RH}を計算することで作られる。
  • さらに、2つのブラインドベクトル {s_L, s_R}を選択し、同様にランダムな値pを選択して {s_L, s_R}へコミットするVector Commitment  {S = p\tilde{B} + s_LG + s_RH}を計算する。
  • 証明者は、検証者にこのAとSを送信する。
  • AとSを受け取った検証者はチャレンジとしてランダムな値yzを選択し、証明者に送る。

この検証者が選択したyを使って、 内積<0n, yn> = 0であるため、上記の1と2のステートメントは暗黙的に以下のように表現できる。

  •  {<a_L, 2^{n}> = v}
  •  {<a_L - 1 - a_R, y^{n}> = 0}
  •  {<a_L, a_R \circ y^{n}> = 0}

さらに検証者が選択したzを使って、上記3つのステートメントを1つのステートメントに結合できる↓

 {z^{2}v = z^{2}<a_L, 2^{n}> + z<a_L - 1 - a_R, y^{n}> + <a_L, a_R \circ y^{n}>}

このステートメントをより単純な項を持つように分割し、再配置する↓

 {z^{2}v =  z^{2}<a_L, 2^{n}> + z<a_L, y^{n}> - z<a_R, y^{n}> - z<1, y^{n}> + <a_L, a_R \circ y^{n}>}  {z^{2}v + z<1, y^{n}> = z^{2}<a_L, 2^{n}> + z<a_L, y^{n}> -z<1, a_R \circ y^{n}> +<a_L, a_R \circ y^{n}> }  {z^{2}v + z<1, y^{n}> = <a_L, z^{2}2^{n}> + <a_L, zy^{n}> + <-z1, a_R \circ y^{n}> +<a_L, a_R \circ y^{n}>}  {z^{2}v + z<1, y^{n}> = <a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}> + <-z1, a_R \circ y^{n}>}

右辺を結合するため、両辺に {<-z1, z^{2}2^{n} + zy^{n}>}を加算し、単純化すると↓

 {z^{2}v + z<1, y^{n}> - <z1, z^{2}2^{n} + zy^{n}> = <a_L, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}> + <-z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}>}  {z^{2}v + (z - z^{2})<1, y^{n}> - z^{3}<1, 2^{n}> = <a_L - z1, z^{2}2^{n} + zy^{n} + a_R \circ y^{n}>}

そこから内積以外の秘密の値でない項を以下のように定義すると↓

 {δ(y, z) = (z - z^{2})<1, y^{n}> - z^{3}<1, 2^{n}>)}

(この値は検証者が提供したyとzを使って簡単に計算できる。)これを適用した最終的なステートメントは、

 {z^{2}v + δ(y, z) = <a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}>}

となる。この式の右辺の内積は、左の要素に {a_L}を持ち、右の要素に {a_R}を持つ。そしてこの式の各パーツを以下のように定義する。

  •  {l(x) = a_L - z1}
  •  {r(x) = y^{n} \circ (a_R + z1) + z^{2}2^{n}}
  •  {z^{2}v + δ(y, z) = <l(x), r(x)>}

ただこの段階ではl(x)とr(x)はブラインドされていない。つまり、このステートメントを証明する際にl(x)とr(x)の情報をそのまま送るとvの値が検証者に分かってしまうので、↑で選択したブラインドファクター {s_L, s_R}を使用して、l(x)とr(x)を以下のようなブラインド多項式にする。

  •  {l(x) = a_L + s_Lx - z1} = l_0 + l_1x
  •  {r(x) = y^{n} \circ (a_R + s_Rx + z1) + z^{2}2^{n} = r_0 + r_1x}

 {a_L, a_R}がそれぞれ {a_L + s_Lx, a_R + s_Rx}に置き換わっただけ。 {l_0 + l_1x} {r_0 + r_1x}はxの多項式として表現した場合の式で、 {l_0, r_0}はxの多項式の次数0の項を、 {l_1, r_1}は次数1の項をそれぞれ表している。ここでブラインドファクター {s_L, s_R}に対してのみxが乗算されているため、 {l_0, r_0}がブラインドされていない内積の左右の要素となる。つまり、

 {<l_0, r_0> = z^{2}v + δ(y, z)}

である。このような式変形をすると以下のような多項式表現ができる↓

 {t(x) = <l(x), r(x)> = t_0 + t_1x + t_2x^{2}}

この多項式の各項( {t_0, t_1, t_2})はKaratsuba法を使うと以下のように表現できる↓

  •  {t_0 = <l_0, r_0>}
  •  {t_2 = <l_1, r_1>}
  •  {t_1 = <l_0 + l_1, r_0 + r_1> - t_0 - t_2}

ここで {t_0 =  <l_0, r_0> = <a_L - z1, y^{n} \circ (a_R + z1) + z^{2}2^{n}>}であるので、証明者が検証者にアンブラインドした内積の式が成立することを証明するためには、t(x)の定数項 {t_0} {z^{2}v + δ(y, z)}であることと、t(x)が正しい多項式であることを証明すればいい。

ここまでが図の真ん中上部の緑の枠の部分(長かった。。)。

 {t_0}の正しさの証明

続いて、↑の {t_0 = z^{2}v + δ(y, z)}であることを証明する。

まず証明者はt(x)の係数へのコミットメントを作成し、チャレンジポイントxを使って多項式を評価することで、コミットメントが正しいt(x)へのコミットメントであることを検証者に証明する。

vに対するコミットメントVは既に作ってあり、それが {t_0}へのコミットメントにもなるので、新たに {t_1, t_2}へのコミットメント {T_1, T_2}を作成し、検証者に送信する。この時 {V, T_1, T_2}には以下の関係がある。

t(x)をPedersen Commitmentにマッピングするのに、点Bを使用してまず値へのコミットメントを作る。

 {t(x)B = z^{2}vB +δ(y, z)B + xt_1B + x^{2}t_2B }

続いて、別の点 {\tilde{B}}を使ってブラインドファクターとなる部分を作る。

 {\tilde{t}(x)\tilde{B} = z^{2}\tilde{v}\tilde{B} + 0\tilde{B} + x\tilde{t_1}\tilde{B} + x^{2}\tilde{t_2}\tilde{B}}

ここで {\tilde{v}, \tilde{t_1}, \tilde{t_2}}はそれぞれ {v, t_1, t_2}のブラインドファクター。そして {t(x)B} {\tilde{t}(x)\tilde{B}}を加算してt(x)のPedersen Commitmentが作成できる↓

 {t(x)B + \tilde{t}(x)\tilde{B} = z^{2}V + δ(y, z)B + xT_1 + x^{2}T_2}

なので検証者に送る {V, T_1, T_2}はブラインドファクターを含んでいる。

検証者にt(x)が {t(x) = z^{2}v + δ(y, z) + t_1x + t_2x^{2}}であることを納得させるために、証明者は {t(x), \tilde{t}(x)}を検証者に開示する。そして検証者は、以下が成立するか検証する。

 {t(x)B + \tilde{t}(x)\tilde{B} = z^{2}V +  δ(y, z)B + xT_1 + x^{2}T_2}

上記が成立すると、検証者は {t_0} = z^{2}v + δ(y, z)であることを納得する。

これが図の右上の部分。

t(x)が正しい多項式であることの証明

続いてt(x)が正しい多項式であること、つまりt(x) = <l(x), r(x)>であることを証明する。

証明者は既に、↑ですでに {a_L, a_R, s_L, s_R}へのコミットメント {A = α\tilde{B} + a_LG + a_RH} {S = p\tilde{B} + s_LG + s_RH}を検証者と共有している。そしてAは以下のように表現できる。

 {A = <a_L, G> + <a_R, H> + α\tilde{B} = <a_L, G> + <y^{n} \circ a_R, y^{-n} \circ H> + α\tilde{B}}

ここで、 {H' = y^{-n} \circ H}とするとl(x)とGの内積

 {<l(x), G> = <a_L, G> + x<s_L, G> + <-z1, G>}

となり、r(x)とH'の内積

 {<r(x), H'> = <a_R, H> + x<s_R, H> + <zy^{n} + z^{2}2^{n}, H'>}

となる。l(x), r(x)とコミットメントA、Sを関連付けるには、 {e\tilde{B} = α\tilde{B} + xp\tilde{B}}を使って以下を計算すると、↓

 {<l(x), G> + <r(x), H'> + e\tilde{B} =}

 {<a_L, G> + <a_R, H> + α\tilde{B} + x<s_L, G> +  x<s_R, H> + xp\tilde{B} + <-z1, G> + <zy^{n} + z^{2}2^{n}, H'>}

となり、これは

 {<l(x), G> + <r(x), H'> + e\tilde{B} = A + xS + <zy^{n} + z^{2}2^{n}, H'> - <z1, G> }

つまり

 {<l(x), G> + <r(x), H'> = -e\tilde{B} + A + xS + <zy^{n} + z^{2}2^{n}, H'> - <z1, G> }

になる。これが合成ブラインドファクターeを持つl(x)とr(x)へのVector Pedersen Commitmentとなる。ここまでが図の右下の部分。証明者が検証者にeを送ることでこのコミットメント {P = <l(x), G> + <r(x), H'>}を計算することができる。

↑の式は要素の数nのベクトルになるので、内積の証明と同様、ベクトルの要素が1つのスカラー値になるまで圧縮する。ここが図の中央の部分。

そして {P = <l(x), G> + <r(x), H'>}とt(x) = <l(x), r(x)>の関係が成立するかどうかを検証するために、Pとt(x)を入力して冒頭のBulleptproofsの内積の証明を利用する。この関係性が証明できれば結果的にrange proofの証明になる。