2020-02-26

冗長的な支払経路を用いることで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： →

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

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

Boomerang

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

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

経路1： →
経路2： →
経路3： →→→→
経路4： →
経路5： →
経路6： →
経路7： →→→→
経路8： →

６つの経路が１秒で転送完了し、２つの経路が４秒かかったとすると、送金の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コントラクトの結果は以下の３つのいずれかになる。

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

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

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

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

Adaptor Signatureの利用

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

2020-02-18

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

Grin Mimblewimble vulnerability

ちょっと前に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は誰もその離散対数を知らない２つめのベースポイントで、rがブラインドファクター、vがコインの量。

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

C1 = r1G + v1H
C2 = r2G + v2H

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

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

goblockchain.network

ノードの検証内容

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

完全なTXOセット
アウトプット毎のrange proof
トランザクション毎のトランザクションカーネル

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

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

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

MMRとは？

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

高さ

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

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

また値をプルーニングをすることも可能で、例えば上記の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の特性を利用すると次のようなことが可能になる。

２つのアウトプットを持つトランザクションのアウトプットが上記C1, C2の２つのPedersen Commitmentであった場合、トランザクションカーネルを作成し、有効な署名を作った後でアウトプットを以下の２つの異なる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に変更してもトランザクションの署名は有効なままとなる。

ブロックへの拡張

さらにこれをブロックレベルに拡張することができる。↑と同じ方法を使って、ブロック内で使用されるアウトプットのセットが異なる２つの競合するブロックを作ることができる。これは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に対してコミットするようになるので、チェーンの初期同期の遅延のボトルネックが改善されるという副次的効果もある。

2020-02-07

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

Bitcoin Lightning network Cryptography

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はどちらか１人にしか使えないが、UTXO Aは同じままnonceだけ違う値を使って異なるcommitmentを作り両者に渡してしまうことが可能になる。

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

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

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

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

アリスが所有しているUTXOに使われている公開鍵を ${P_1 = xG}$ とした場合、アリスは同じ秘密鍵xとJを使ってもう１つの点 ${P_2 = xJ}$ を計算する。
アリスは ${P_2}$ を使ってコミットメント ${C = H(P_2)}$ を作成し、提供する。
公開された使用済みの情報にCが存在しないければCが未使用であることが確認できるので、ボブはアリスに対してプロトコルを継続する。
アリスはランダムなnonce kを選択し、以下の計算を行う。
- $K_G = kG$
- ${K_J = kJ}$
- ${e = H(K_G || K_J || P_1 || P_2)}$
- ${s = k + ex}$
アリスは上記で計算した ${K_G, K_j, e, s, P_1, P_2}$ をボブに明らかにする。
ボブは受け取ったデータに対して以下の検証を行う。
- 以前アリスから受け取った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}$ 以外の異なるコミットメントを作成する（別の秘密鍵の公開鍵を作ってコミットメントとする）ことができない。これをすると最後の署名検証が失敗する。

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

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

Joinmarketでの活用

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

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

ユーザー（マロリー）は、ミキシングのセッションを開始する前に、PoDLEプロトコルにしたがって自身のUTXOのコミットメントをJoinmarketのネットワークで公開する必要がある。
別の参加者（ボブ）とその特定のUTXOを使用してCoinJoinを始めると、マロリーは同じコミットメントのUTXOを使って他のユーザーとはプロトコルを実行できなくなる。
ボブがマロリーにコミットメントのオープンを依頼すると、マロリーはUTXOの情報を明らかにする。
ボブはマロリーから受け取った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のデータをゴシップすることでスパイ行為への対応としようという議論もある。

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

2020-01-18

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

CT Mimblewimble Bulletproof Cryptography

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〜2⁶⁴など）にありマイナスやオーバーフローをしていないことを証明する（マイナスやオーバーフローしているとコインのインフレーション（生成）が可能になる）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 < 2ⁿの範囲内にあること。例えばn = 4で、v = 5の場合、5が ${0〜2^{4}-1}$ の範囲内にあることを証明する。

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

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

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

vのビット表現 ${a_L \in ｛0, 1｝^{n}}$ 。v = 5の場合は ${a_L = (0, 1, 0, 1)}$ というベクトル
2ⁿのベクトル。つまり ${(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}$ ）

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

2つのベクトルの内積が値vであること（ ${＜a_L, 2^{n}＞ = v}$ ）。
${a_L}$ のベクトルの各値が0か1であること。 ${a_L}$ の各要素から1を引いたベクトルを ${a_R = a_L - 1}$ とすると、この２つのベクトルの各要素を乗算した結果のベクトルの要素は全て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}$ を計算することで作られる。
さらに、２つのブラインドベクトル ${s_L, s_R}$ を選択し、同様にランダムな値pを選択して ${s_L, s_R}$ へコミットするVector Commitment ${S = p\tilde{B} + s_LG + s_RH}$ を計算する。
証明者は、検証者にこのAとSを送信する。
AとSを受け取った検証者はチャレンジとしてランダムな値yとzを選択し、証明者に送る。

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

${＜a_L, 2^{n}＞ = v}$
${＜a_L - 1 - a_R, y^{n}＞ = 0}$
${＜a_L, a_R \circ y^{n}＞ = 0}$

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

${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の多項式の次数０の項を、 ${l_1, r_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のベクトルになるので、内積の証明と同様、ベクトルの要素が１つのスカラー値になるまで圧縮する。ここが図の中央の部分。

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

2020-01-17

Bulletproofsにおける内積の証明

Bulletproof ZK Cryptography

Bulletproofsは2017年にBünzらが発表したゼロ知識証明システムの一種で、Trusted Setupを必要とせず、プルーフが非常に短く、その集約が可能であるという特性を持っている。最初はConfidential Transactionの秘匿した値がある範囲内にあることを証明するrange proofを効率的に実現するために提案されが、range proofに限らず、一般的な算術回路向けの非対話型ゼロ知識証明プロトコルとしても提案されている。

Bulletproofsがどのような仕組みでrange proofや算術回路で動作するのか見ていく前に、Bulletproofsのベースとなる内積の証明の仕組みについて理解する。

内積の証明

Bulletproofsの重要な構成要素の１つは、２つの異なるベクトルを持つPedersen Commitmentに対してベクトルの内積を計算するアルゴリズムにある。

よくConfidential TransactionやMimblewimbleで出てくる楕円曲線Pedersen Commitmentは

C = rG + aH

という形式のコミットメントで、rがブラインドファクター、aが秘匿するコインの量として使われる。

rやaはスカラー値だが、Bulletproofsの内積の証明では、これを拡張し、２つのベクトル ${\textbf{a} = (a_0, a_1, ..., a_n)}$ , ${\textbf{b} = (b_0, b_1, ..., b_n)}$ について

${c = \langle \textbf{a}, \textbf{b} \rangle}$
${P = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle}$

という関係が成立するベクトルa, bの知識を知っていることをa, bを明かすことなく検証者に確信させる（太字はスカラーではなく、G,Hを含めベクトルの表記で、 ${\langle \rangle}$ は２つのベクトルの内積の表記）。

まず↑の２つのステートメントを、GとHとは異なるジェネレータBを利用したQ = wBを使って１つの式にする。このwは検証者がランダムに選択する。cの両辺にQを乗算すると、

${cQ = \langle \textbf{a}, \textbf{b} \rangle Q}$

これをPの式に加算すると、

${P + cQ = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}$

シンプルにするため、P' = P + cQとすると、

${P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}$

というふうにシンプルにでき、このステートメントが成立することを証明する。

証明のプロセス

まず最初にベクトルを圧縮する。a, b, G, Hの要素の数をnとすると、以下の手順をk = log(n)回繰り返し、サイズを１にする。

ランダムな値xを選択し、ベクトルa, bを左右半分に分割し、半分に分割したベクトルにxおよび ${x^{-1}}$ を乗算し、加算することでベクトルのサイズを半分にする。

f:id:techmedia-think:20200110164524j:plain

そしてa', b'に対応する新しいc'は

${c' = \langle \textbf{a'}, \textbf{b'} \rangle = \langle \textbf{a}_{lo} \cdot x + \textbf{a}_{hi} \cdot x^{-1}, \textbf{b}_{lo} \cdot x^{-1} + \textbf{b}_{hi} \cdot x \rangle}$

となる。そして、c'は以下のようにも表現できる。

${c' = \langle \textbf{a}_{lo}, \textbf{b}_{lo} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{hi} \rangle + x^{2} \cdot \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle + x^{-2} \cdot \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}$

ここで、 ${L = \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle}$ 、 ${R = \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle}$ とすると、↑の式は１つまえのcを使って以下のように表現できる。

${c' = c + x^{2} \cdot L + x^{-2} \cdot R}$

各ラウンドのLとRを検証者に送り、k回ラウンドを繰り返すとベクトルa, bの要素の数は最終的に１つになるので、スカラー値となったa', b', c'を証明者に送ると、３つの値と各ラウンドのL, Rを使って逆の計算をすることでcの値を計算できる。この仕組がポイントの１つで、圧縮とその逆の計算を簡単にするためcで説明したが、実際は後述するようにP'を使った計算になる。

↑の圧縮はa, bだけでなくG, Hも同様に圧縮していく。結果、各ベクトルの次の状態は以下のように表現できる。

${\textbf{a}^{k-1} = \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}}$
${\textbf{b}^{k-1} = \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}}$
${\textbf{G}^{k-1} = \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i}}$
${\textbf{H}^{k-1} = \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i}}$

そしてステートメントP'についても以下のようになる。

${P'_{k-1} = \langle \textbf{a}^{(k-1)}, \textbf{G}^{(k-1)} \rangle + \langle \textbf{b}^{(k-1)}, \textbf{H}^{(k-1)} \rangle + \langle \textbf{a}^{(k-1)}, \textbf{b}^{(k-1)} \rangle \cdot Q}$

展開すると

${P'_{k-1} = \langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}, \textbf{G}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{G}_{h_i} \rangle + }$ ${\langle \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i}, \textbf{H}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{H}_{h_i} \rangle + }$ ${\langle \textbf{a}_{lo} \cdot x_k + x^{-1}_k \cdot \textbf{a}_{h_i}, \textbf{b}_{lo} \cdot x_k^{-1} + x_k \cdot \textbf{b}_{h_i} \rangle \cdot Q}$

となるが、これは↑のcとc'の関係と同じ変換を利用して、以下のように変換できる。

${P'_{k-1} = P'_k + x_{k}^{2} \cdot L_k + x_{k}^{-2} \cdot R_k}$
${L_k = \langle \textbf{a}_{lo}, \textbf{G}_{hi} \rangle + \langle \textbf{b}_{hi}, \textbf{H}_{lo} \rangle + \langle \textbf{a}_{lo}, \textbf{b}_{hi} \rangle \cdot Q}$
${R_k = \langle \textbf{a}_{hi}, \textbf{G}_{lo} \rangle + \langle \textbf{b}_{lo}, \textbf{H}_{hi} \rangle + \langle \textbf{a}_{hi}, \textbf{b}_{lo} \rangle \cdot Q}$

各ベクトルの要素数が１になるまで圧縮を繰り返すとP'は最終的に

${P'_{0} = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0Q}$

で、これは各ラウンドのLとRとxの値を使うと以下の式になる。

${P'_{0} = P'_{k} + \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}$

P'を元のPに置き換えると式は以下のように変形できる。

${P + cwB = a^{(0)}_0G^{(0)} + b^{(0)}_0H^{(0)} + a^{(0)}_0b^{(0)}_0wB - \sum^{k}_{j=1}(L_{j}x^{2}_j + x^{-2}_{j}R_{j})}$

ここまでの要素が揃うと以下の検証ができる。

検証者は証明者から受け取った ${P'_0}$ の構成要素であるスカラー値 ${a^{(0)}_0, b^{(0)}_0}$ と各ラウンドのL, Rを使って、圧縮ラウンドの逆の計算をすることで算出した値が元のP'と合致するか検証し、合致すればスカラー値 ${a^{(0)}_0, b^{(0)}_0}$ が正しいことを検証できる。
検証者は ${a^{(0)}_0, b^{(0)}_0}$ と各ラウンドのL, Rを使って↑のP + cwBの等式が成立するか直接検証することができる。 ${a^{(0)}_0, b^{(0)}_0}$ がPを構成する式とcwBでcの式の両方に展開されるので、これをもって、Pとcの関係性の証明になる。

この検証をすることで、検証者はステートメント ${P' = \langle \textbf{a}, \textbf{G} \rangle + \langle \textbf{b}, \textbf{H} \rangle + \langle \textbf{a}, \textbf{b} \rangle Q}$ が成立することをベクトルa, bの値を知ることなく確認することができる。これがBulletproofsの内積の証明の仕組み。

ちなみに↑は証明者と検証者による対話が必要な形で記載しているが、これはFiat-Shamir変換により非対話型にすることができる。

このBulletproofsによる内積の証明ができると何が嬉しいの？と思うかもしれないが、これを冒頭で言ったようにCTやMimblewimbleで使われるrange proofの証明に利用できる。ある値が0〜2ⁿの範囲内にあるというステートメントは内積で表現できるからだ。具体的なプロトコルについてはまた別の記事で解説したい。

Develop with pleasure!

福岡でCloudとかBlockchainとか。