Develop with pleasure!

福岡でCloudとかBlockchainとか。

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part2

Part1でDLSAGの仕組みについて整理したので↓

techmedia-think.hatenablog.com

続いて、DLSAGを利用して、Payment Channel Networkを構築する際に必要な構成要素を順番に見ていく。

MoneroでPayment Channel

上記のDual-Keyアウトプットを使った払い戻しトランザクションを使ってMoneroでPayment Channelを構築する。

Dual-Keyは↑のDLSAGの提案で新しく出てきた概念で、現状のMoneroでは各アウトプットには送信先として公開鍵が1つだけ指定できるが、Dual-Keyでは2つ公開鍵が指定できるようになり、さらにタイムロックを制御するフラグtがセットされた以下のような3つの要素で構成されるようになる。

(アリスの公開鍵、ボブの公開鍵、t)

tはチェーン上のブロック高をセットでき、

  • t = 0の場合は、このアウトプットをいつでもアリスの公開鍵に対応した秘密鍵で署名すれば使用できる
  • tが0でない場合、ブロックチェーン上のブロック高がtを超えると、2つめのボブの公開鍵に対応した秘密鍵で署名して使用できるようになる

という性質を持つ。

チャネルのオープン

アリスがMoneroのDual-Key {(pk_{A,0}, pk_{A,1})}にγ XMR保持していて、ボブとの間にPayment Channelを作成したい場合、↑のDual-Keyを使ってチャネルを開く。

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

アリスはγ XMRをDual-Key {(pk_{AB}, pk_{A'})}に送金するデポジットトランザクション(dtx)を作成し、ブロック高lにロックするよう設定する。

Moneroにおける2-of-2のマルチシグは、アリスとボブがそれぞれその秘密鍵のシェアを持つ公開鍵 {pk_{AB}}で実現する。この公開鍵に対応する秘密鍵 {sk_{AB}}は、アリスが持つ秘密鍵 {[sk_{AB}]_A}とボブが持つ秘密鍵 {[sk_{AB}]_B}を加算したもの {sk_{AB} = [sk_{AB}]_A + [sk_{AB}]_B}となる。つまり、コインを公開鍵 {pk_{AB}}に送金することで、両者の秘密鍵の情報がなければ署名を完成させられない=使えない2-of-2のマルチシグへのロックとなる。

こうして、ボブが {pk_{AB}}にロックされたコインの使用に協力しない場合、アリスはチェーンのブロックがlを超えると別の払い戻しトランザクションを作ること無く、自分の資金のコントロールを取り戻すことができる。一方、ボブがオフチェーンで {pk_{AB}}からコインを受け取った場合、チェーン上でブロック高lに達するまでに最も金額の高いものをオンチェーンにプットする必要がある。

このデポジットトランザクションのアウトプットを使用する方法は以下の2つ。

  • アリスとボブが協力して {pk_{AB}}に対して有効な署名を作る
  • チェーンのブロック高がlを超えたら、アリスの {pk_{A'}}に対して有効な署名を作る

このことから、このPayment Channelは以下の特性を持つ。

  • ブロック高lを超えるとアリスによる払い戻しが可能であることから、有効期間付きのPayment Channelであること。
  • 一度もオフチェーン決済をしない場合( {pk_{AB}}に対して有効なアリスの署名をボブに送っていない場合)、ブロック高lを超えるとアリスしかコインを取り扱えないので払い戻し用にトランザクションをブロードキャストする必要なく、コインはアリスの所有物となる。

オフチェーン決済

↑でセットアップしたPayment Channelを使ってオフチェーン決済をする。アリスはγ'をボブに送金するオフチェーントランザクション(otx)を作成する。このトランザクションのインプットは↑のDual-Key {(pk_{AB}, pk_{A'})}で、アウトプットはボブのDual-Keyアドレス {(pk_{B,0}, pk_{B,1})}と、お釣りγ-γ'を送るアリスのDual-Key {(pk_{A,0}, pk_{A,1})}。このトランザクションotxを有効なトランザクションにするためには、アリスとボブが協力して署名する必要がある。

が、このPayment Channelの要は、アリスだけがotxに署名し、署名のシェアとなる {[σ]_A}をボブに送る。この時点でボブはブロック高lが来る前に、署名を完成させトランザクションをブロードキャストすることでγ'を入手できる状態になる。その後は、ブロック高lが訪れるまでは、γ'より高い残高のオフチェーン決済トランザクションを受け取ることができる。

この時の署名プロセスが↓の2OF2RSSIGNプロトコル(青字の部分は除く)

f:id:techmedia-think:20190711165015p:plain
2OF2RSSIGN(pkAB, [skAB]A, [skAB]B, tx) プロトコルの定義

このプロトコルの結果、アリスとボブはそれぞれの署名 {[σ]_A} {[σ]_B}を入手するので、それを結合して最終的な署名 {σ = ([s_0]_A + [s_0]_B, s_1, ..., s_{n-1}, h_0, (J_A + J_B))}を完成させる。

署名のシェアの検証

また、署名プロトコルにおいて重要なのが、それぞれが出力する署名のシェアが正しいものかの検証だ。アリスが {[σ]_B}を受け取り、それが有効な署名σのシェアかどうか検証したい場合、 {[σ]_B}から {[s_0]_B}をピックアップし、 {([s_0] + [s_0]B)G = (R_A + R_B) - h_{n-1}pk_{AB,b}}が成立するか検証する。ここで {R_A = [s'_0]_A G} {R_B = [s'_0]_B G}である。

Channelのクローズ

Channelのクローズには2パターンある。

  • ボブが最新のotxに自分の署名 {[σ]_B}を計算し、アリスの {[σ]_A}と組み合わせて最終的な署名を完成させブロードキャストする。
  • タイムロックlを過ぎてもボブがotxをブロードキャストしない場合、アリスがdtxのDual-Keyのタイムロック側の条件を使ったトランザクションを作成、ブロードキャストし資金を取り戻す。

※ クローズ処理やオフチェーン決済を見て分かるが、どのオフチェーントランザクションをブロードキャストしたとしても、チェーン上に記録されたものが有効で、ペナルティや最新の残高の反映を強制させる仕組みがないため、これはあくまで一方向のPayment Channelっぽい。

Moneroの条件付き支払い

条件付き支払いは、ハッシュのプリイメージや離散対数問題の解を入手するなど暗号問題に対する解を提供できる場合にのみ有効になる支払いだ。この条件付き支払いはAtomic SwapやPayment Channel Networkなどで利用される。

グループ要素Y = yG、XMRの量γおよびタイムアウトtで定義される 以下のようなDiscrete-log Timelock Contract (DTLC)を考える。

  1. ボブがt日前にyG = Yとなるような値yを生成した場合、アリスはボブにγXMR支払う。
  2. tが経過するとアリスはγXMRを取り戻す。

アリスとボブの間のPayment Channelを開く際に作成したDualアドレス {(pk_AB, pk_A)}において、この条件付き支払いを行う場合、アリスとボブは条件Yで、2OF2RSSIGNCONDプロトコル(上図の青字の部分が加わる)を使ってctxに署名する。この時、 {Y = yg} {Y^* = ympk_{AB,1}}

このプロトコルの要は、アリスとボブが協力して署名を完成させるが、もう1人ボブにyを教えるユーザーがいる。これは別のコインのチェーンと交換する場合にはアリスだったり、マルチホップ決済の場合はボブより先の受領者だったりする。アリスは ([{s'_0}]_A, [sk_AB]_A)をボブは ([{s'_0}]_B, [sk_AB]_B)を、そして3人目のユーザは(y, Y)を提供する。アリスとボブがそれぞれ {[σ]_A}および {[σ]_B}を提供しても、最終的な署名を完成させるためにはtの値が必要だ。

そのため、2OF2RSSIGNCONDプロトコル実行後、ボブはアリスに自分の署名のシェア {[σ]_B}を渡し、アリスはその有効性を検証した後、自分の署名のシェア {[σ]_A}を返信する。この順の交換で、値yが明らかになっていて、ブロック高のロックlに達していない場合にのみctxが公開されることを保証する。

ボブがctxで自分のXMRを請求する場合、ボブは {[s'_0]_A + [s'_0]_B + y}を含む署名σを提供する必要がある。そのためボブはyを知っている場合のみこれを行える。この署名が公開されると、アリスは既に {[σ]_A}および {[σ]_B}を知っているのでσからtを計算できる。

重要なのはyとYがチェーン上に現れないということで、第三者がチェーンを監視しても、同じ条件を使う別のトランザクションと結びつけることはできない。このトランザクションは条件なしのMoneroトランザクションと変わらないため、暗号通貨MoneroのFungibilityに貢献する。

MoneroのPayment Channel Network

アリスが、アリス⇔ボブ⇔キャロル⇔デイブという形式の開かれたPayment Channel Networkの経路を使ってデイブへのオフチェーン支払いをする場合、支払は以下の3つのフェーズで行われる。

  1. 最初にデイブは条件 {(Y = yG, Y^{*} = ympk^{1}_{CD})}を作成する。条件 {(Y, Y^{*})}をアリスに伝える。
  2. アリスは条件 {(Y, Y^{*})}を使ってボブへの条件付き支払いを作成し、ボブは同じ条件を使ってキャロルへの条件付き支払いを作成し、キャロルも同条件を使ってデイブへの条件付き支払いを作成する。
  3. 最後にデイブはyをキャロルに公開し、キャロルからコインを受け取る。次にキャロルはボブに、ボブはアリスにyを公開してそれぞれコインを入手する。

と基本は↑のような手順を踏むが、全てのユーザーで同じ条件(Y, Y^*)は使用できない(計算に使うGは全ユーザー共通だけど各 {Y^*_i}の値などは異なる)。この問題に対応するため、各ユーザーペアは支払いの受取人を彼らの共有アドレスの払い戻しアドレスにアウトプットの識別子を掛けたもの(つまり、 {m_{AB}pk_A}で、 {pk_A}はペア {(pk_{AB}, pk_A)}の払い戻しアドレス)に転送する通信ラウンドを追加する。この値を受け取ると、受信者は各ユーザーについてペア {(Y, Y^*_i)}を両方の条件値が期待通りに功徳されている事実のゼロ知識証明と共に計算する。最後に、受信者はこれらの条件をゼロ知識証明と一緒に支払いのパスに送り返すという処理が加わる。

ここで、条件付き支払いを設定する前に、各ユーザーは入金の条件が出金の条件と同じ値yに基づいて構築されていることを検証するため、受信者が作成したゼロ知識証明を検証する必要がある。ゼロ知識スキームの健全性は、デイブがその証明をずるし、その状態で他のユーザーが正しいと検証できないようにすることが重要で、そうでなければ、デイブへの支払いは行われるが、同じyが使えず中継ユーザーがコインを失う状況ができるかもしれない。

この条件部分はMulti Hop Locks↓を利用して、最初に送金者がセットアップするようになるのかも?

techmedia-think.hatenablog.com

所感

↑がDLSAGを利用した条件付き支払いやPayment Channelの構成方法だけど、やっぱりかなり複雑ね。あと以下の制約もあるので、まだBitcoinのLNほど柔軟に決済とまではいかず、課題は残る。

  • DLSAGはまだMoneroでは利用可能ではなく、まだ具体的なデプロイ計画は無い?
  • Dual-Keyを使ってセットアップしたPayment Channelは有効期間付きである。
  • ペナルティや最新の残高を反映するような制約はついていないため、基本的に一方向の決済となるっぽい。

ただスクリプトシステムが無いかつ、リング署名スキームを採用しているプラットフォームで実現するという意味では意味のある提案だと思う。

MoneroでスクリプトレスなPayment Channelを実現するためのDLSAGリング署名スキーム Part1

ベースの考え方であるLSAGについて整理したので↓

techmedia-think.hatenablog.com

本丸のDLSAGとDLSAGを利用したPayment Channelの仕組みについて見ていく。

https://eprint.iacr.org/2019/595.pdf

Moneroの課題

  • BitcoinBitcoin ScriptをEthereumがSolidityなどで記述可能なコントラクトを記述出来るのに対し、Moneroにはそういったスクリプト機能が無く、コインをある秘密鍵宛に送信者を匿名化し、量を秘匿して送ることができるだけである。BitcoinやEthereumのようにどんな条件にコインがロックされ、ただどんな条件でアンロックされるのかという情報がオンチェーン上に記録され、これがFungibilityを損なう要因にもなりうる。これに対しホワイトペーパーでは、スクリプトを導入することなく、Fungibilityを担保し、インターオペラビリティを向上する仕組みを提案している。
  • BitcoinやEthereumなどのパブリックチェーンと同様、スケーラビリティの課題を抱えている。Moneroのブロックは2分毎に作成されるが、リング署名の仕組みによりBitcoinなどと比べてどうしてもトランザクションサイズが大きくなり、スケーラビリティの課題はBitcoinよりも深刻と言える。ホワイトペーパーでは、このスケーラビリティに課題に対して既にBitcoinでは実現されているが、Payment Channel Networkを利用したオフチェーンスケーリングを提案している。

上記のMoneroにおけるトランザクションの表現力の欠如とスケーラビリティという2つの問題を解決するために提案されているのが新しいリング署名方式=Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)だ。

Dual-Key LSAG

現在のMoneroのトランザクションはインプットとアウトプットを持ち、その両者は {(pk, COM(γ), \Pi_{amt})}で定義される。pkは新しい公開鍵で、COM(γ)はコインの量γへの暗号学的コミットメントを示し、 {\Pi_{amt}}はγが範囲内の値であることを証明する範囲証明を表す。トランザクションインプットは、デコイを持つため1インプットあたり複数のタプルを持つ。トランザクションアウトプットは、1アウトプットあたり1つのタプルを持つ。

これに対し、Dual-Key LSAGでは、 {((pk_{A, 0}, pk_{B, 1}), COM(γ), \Pi_{amt}, t)}と定義される新しいdual-key タプルフォーマットがベースになる。このタプルには(それぞれ異なるユーザーの公開鍵である)2つの公開鍵が含まれ、フラグtに応じて使用できる。このDual-Keyタプルは現在のMoneroのタプルと比べて以下の点が異なる。

  1. このタプルのコインを使用する可能性がある2人のユーザーを識別するため1つではなく2つの公開鍵が含まれる。
  2. 公開鍵間のスイッチを示す(例えばtがMoneroのブロックチェーン内の現在のブロック高より小さい場合には {pk_{A, 0}}が使われる等)追加の要素tが含まれる。

Dual-Keyタプルフォーマットにより、払い戻し用トランザクションを作るためのロジックをエンコードできるようになる。

シグナルt {pk_{A, 0}}を使わなければならいことを示す場合、アリスは {pk_{A, 0}} {pk_{B, 1}}をそれぞれ含む2つの公開鍵のセットを選択し、公開鍵 {pk_{A, 0}}に対応する秘密鍵 {sk_{A}}リンク可能なリング署名を生成する。

逆にt {pk_{B, 1}}を使用する必要があると示す場合、ボブはこれまでと同じ方法でリングを選択し、 {sk_{B}}でリング署名を作ることでアウトプットを使用できる。

もちろん1人のユーザーが2つの公開鍵に対応する各秘密鍵を持っているのであれば、tの値に関係なくこの1人でそのDual-Keyタプルを使用できる。

Dual-Keyのリンク可能なリング署名

↑のDual-Keyのサポートにあたって必要になるのは、新しいリンク可能なリング署名の設計で、以下の課題がある。

キーイメージの仕組み

Moneroの現在のリング署名スキームでは、単一の公開鍵から構成されるキーイメージを公開することで、Linkabilityを実現している。例えばアリスは {sk_A}を使って署名する際は、合わせてキーイメージ {I = sk_Aℍ(pk_A)}を公開する(ℍは曲線上の点を出力するハッシュ関数)。アリスが二重使用しようとして再度 {sk_A}で署名しようとすると、同じキーイメージが計算され、ブロックチェーン上で既に使用済みであることを検出できる。

Dual-Keyで同様のLinkabilityをサポートする際の課題は、公開鍵のペア {(pk_0, pk_1)}を一意に識別し、署名鍵の内 {sk_b}1つだけで計算できる単一のキーイメージを定義する方法だ。

このホワイトペーパーでは、キーイメージをDual-Keyタプルの2つの公開鍵を使ってDiffie-Hellmanの鍵交換を使い、共有鍵を導出する方法提案している。つまり {J = sk_0 \cdot sk_1 \cdot G}として再定義している。これは以下の要件を満たす:

  1.  {sk_b}の知識で {J = sk_b \cdot pk_{1-b}}を計算できる。
  2.  {sk_b \cdot pk_{1-b} = sk_{1-b} \cdot pk_b}が成り立つので、 {(pk_0, pk_1)}を一意に識別できる。
キーイメージのLinkabilityの強化

↑の新しいキーイメージの定義は公開鍵のペアのリンクを可能にする。ただし、キーイメージを公開鍵のペアに一意になるだけでなく、それらを含むアウトプットも一意にするのが重要だ。そうしないと、ユーザーの1人が、同じ公開鍵のペアを使って別のDual-Keyタプルを作成し、それ(およびそのキーイメージ)を使って署名を作成すると、Moneroでは同じキーイメージは二度と使えないので、元々のタプルのコインは使用不可能になってしまう。

署名スキームの安全性とプライバシーの保証を損なうこと無く、各アウトプットに一意の識別子を追加することでこれを軽減できる。例えば、Moneroでは全てのアウトプットを、そのアウトプットが含まれるトランザクションとアウトプットのインデックスで構成する値 {m = H(txid || output_index)}で識別できる。

そのため、DLSAGで使われているリングを一意のトリプル {(pk_0, pk_1, m)_{[1,n]}}で構成されていると見なし、Dualキーイメージを {J = m_j \cdot sk_{j,0} \cdot sk_{j, 1} \cdot g}と定義する。jはリング内の本当の署名の位置を表す[1, n]の値。

以上を踏まえた、新しいDLSAG署名スキームは以下のようになる。

二者がそれぞれ保持する鍵ペアを {(sk_0, pk_0), (sk_1, pk_1)}とする。 そのDual-Keyタプルのコインがロックされたトランザクションアウトプットの識別子をmとする。

DLSAGの署名生成

Dual-Keyにロックされたコインを使用するトランザクションを作成し、そのインプットにはデコイと実際に使用するDual-Keyのタプルのリスト {( (pk_{0,1}, pk_{1,1}, m_1), ...., (pk_{n, 0}, pk_{n, 1}, m_n) )}がセットされている。

  1. n個ほどランダムな値をサンプリングする。  {s'_0, s_1, ..., s_{n-1}}
  2. 実際に使用する鍵と、その公開鍵とペアになる公会鍵を使ってキーイメージ {J = m_n \cdot sk_b \cdot pk_{n, 1-b}}を計算する。ここで {sk_b}は公開鍵 {pk_{n, b}}に対応する秘密鍵
  3.  {L_0 = s_0 \cdot G}および {R_0 = s'_0 \cdot ℍ(pk_n)} {h_0 = H(tx || L_0 || R_0)}を計算する。
  4.  {i \in {1, ..., n-1}}について以下の計算をする。
    •  {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    •  {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    •  {H(tx || L_i || R_i)}
  5.  {H(tx || s_0 \cdot G + h_{n-1} \cdot pk_{n, b} || s_0 \cdot m_n \cdot pk_{n, 1-b} + h_{n-1} \cdot J) = h_0}となるような {s_0 = s'_0 - h_{n-1} \cdot sk}を計算する。
  6. 結果、計算した {σ = (s_0, s_1, ..., s_{n-1}, h_0, J, b)}が署名となる。

ホワイトペーパーに合わせたので若干前回のブログと表記は違うが、基本的な署名の仕組みはLSAGと大きく変わっておらず、キーイメージおよび、キーイメージを計算に使っているRの計算式が異なるのと、どの公開鍵によるアンロックなのか示すbが署名に追加される。

DLSAGの署名検証

検証者は以下の手順で検証する。

  1.  {i \in {1,..., n}}について以下を計算する。
    •  {L_i = s_i \cdot G + h_{i-1} \cdot pk_{i, b}}
    •  {R_i = s_i \cdot m_i \cdot pk_{i, 1-b} + h_{i-1} /cdot J}
    •  {H(tx || L_i || R_i)}
  2. 算出した {h_n} {h_0}と一致すれば有効な署名。

これも基本的にLSAGの仕組みと大きく変わらない。

Moneroへの適用について

Dual Outputはもちろん現在のMoneroではサポートされないが、ハードフォークでMoneroに導入可能。現在の署名方式ととDLSAGを組み合わせたトランザクションを構成することが可能で、この混合トランザクションの場合、トランザクションは各インプット毎に通常にLSAGと、Dual-Key形式のDLSAGの署名が含まれる。どちらの形式でも公開鍵の数が異なり、Dual-Keyの場合追加のフィールド(フラグt)がある。このため、コミットメントおよび範囲証明に関する操作や検証についてはDLSAGとなっても互換性が残る。

Fungibility

2種類のアウトプット形式を共存させるとFungibilityが低下する可能性がある。例えばマイナーは選択したアウトプット形式によっては特定のトランザクションのマイニングを拒否するかもしれない。これを軽減するためには、シングルキーの場合も自分の鍵をもう1つ追加してDual-Key形式のトランザクションにするという方法がある。

タイムロック処理の拡張

Dual-Keyタプルにはフラグtが含まれており、このフラグはMoneroではブロック高として実装されると思われる。公開鍵のペア {(pk_0, pk_1)}が与えられた場合、 {pk_0}はブロックtがマイニングされる前に使うことができ、ブロックtがマイニングされた後は {pk_1}で使用できるようになる。

最近の論文に記載されているMoneroへの攻撃において、不明瞭だが、異なるtの値が敵対者にプライバシーを侵害する十分な情報を漏らす可能性がある(例えばtが現在に近い場合リングの1つめの鍵が使われる可能性が高いなど)。このため、この研究では、区別できないタイムアウトを持てるようにするタムロック処理スキームの拡張を提案している。このスキームは、Dual-KeyタプルフォーマットとDLSAG署名スキームの拡張として追加されたもので、MoneroのFungibilityを維持するのに役立つ。

提案されているタイムロック処理スキームは、tを平文のまま含めるのではなく、tの値へのPedersen Commitmentをその範囲証明と一緒に含めるというもの。tが有効期限切れになっていないかは以下のように証明できる。

  1. t < t' < Tとなるようなt'を選択する。Tはトランザクションをマイニングする必要があるブロックの高さ。
  2. 続いて、Pedersen Commitmentの準同型性を利用してコミットメント COM(t' - t) = COM(t') - COM(t)を計算する。
  3. t' - tが[0, 2k]の範囲あることを証明するために、範囲証明 {\Pi_{time}}を計算する。
  4. Pedersenタプル {(COM(t), t', COM(t' - t), \Pi_{time})}はタイムロックtが期限切れになっていないことを証明する。

この仕組みにより、ユーザーはtの実際の値を隠す任意の値t'を選択できる。MoneroはすでにPedersen Commitmentとその範囲証明をサポートしているので、この機能はシームレスにMoneroに追加できる。

以上がDLSAGの大枠。次回はDLSAGを利用してPayment Channel Networkを構成する方法について見ていきたい。

Linkable Spontaneous Anonymous Group(LSAG)リング署名の仕組み

こないだ開催されてたMonero Conference 2019でPedro Moreno-Sanchez*1がMoneroでPayment Channel Networkを実現するためのプロトコルについて発表していた↓

https://youtu.be/AsJaMw-3gGE?t=30157

ホワイトペーパーは↓

https://eprint.iacr.org/2019/595.pdf

スクリプトもないMoneroでどうやってPayment Channel Networkを構成するのか?気になったので読み始めたら、このホワイトペーパーではMoneroのトランザクションの表現力およびスケーラビリティを向上させるために、新しいリンク可能なリング署名方式=Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG)を提案している。

このDLSAGはリング署名の署名スキームの話。Moneroでは送信者の匿名性を確保するのにリング署名を使っている。リング署名というのはユーザーグループのメンバーによって生成されるデジタル署名の一種で、別の言い方をすると、署名検証の際に単一の公開鍵ではなく、公開鍵のセットに対して署名が有効かどうかをチェックする署名スキームである。その署名が有効であった場合、それが公開鍵のセットの内どの公開鍵に対応した秘密鍵で作られた署名なのかは分からないという仕組みだ。Moneroはこのリングメンバー(公開鍵)を明らかにすることなく残高を証明するのにLSAG(Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups)のマトリクスバージョンであるMLSAGを使用している。

新しい提案のDLSAGの前に、今回はまず基本のLSAGについて理解する。LSAGの仕組みについては、↓のブログが参考になった。

https://joinmarket.me/blog/blog/ring-signatures/

リング署名

リング署名の概要は↑に書いた通りだけど、実際のアプリケーションでリング署名を使用するにあたっては以下の特性が求められる(LSAGのLとS)。

Linkability

最初にLinkabilityについて、一見リンク可能性という言葉は、匿名性を向上させるための仕組みと相反して署名者の特定ができるようなキーワードだが、ここでいうリンクというのはそういう意味ではない。リンク可能なリング署名というのは、ある公開鍵 {P \in L}(Lは公開鍵のセット)があったとして、与えられたメッセージに対して1つのリング署名を作成することができる。そして同じ秘密鍵を使って別のリング署名を作成した場合、この2つのリング署名がリンク可能であるということだ。つまり、この特性を利用すると、各参加者は同じ秘密鍵を使った署名を1回しか作成できないようにすることができる。また、リンク可能であるがそれがどの秘密鍵であるかは分からないための、そのようなケースでも匿名性は維持できる。これはコインの二重使用を制限したり、投票システムにおいて同じ人間が複数回投票するのを防ぐのに適している。

Spontaneity

Spontaneityというのは自発性という意味だ。リング署名ではデコイとなる公開鍵のセットを用意するが、その際にそのデコイの秘密鍵の所有者などグループメンバーとの協力を必要とせずに、署名者自身のみでリング署名を作成できることが必要要件になる。コインを送金する際に誰と協力することもなくデコイのセットをピックアップして送金できる必要があるし、よくある例では、内部告発をする際にグループのメンバーであることだけを明かしたい場合、他のメンバーの協力が必要な署名スキームでは成立しないだろう。

上記のLinkabilityとSpontaneityを備えた署名スキームがLinkable Spontaneous Anonymous Group(LSAG)だ。LSAGはもともと暗号通貨などとは関係なく、2004年にJoseph K. Liu、Victor K. Wei、Duncan S. Wongらによって発表された署名スキームで、電子投票システムでの利用が想定されていた(各人の頭文字からLWWのLSAGと表記される)。

Abe-Ohkubo-Suzukiスキーム

LSAGの具体的なスキームの前に、NTT研究所が2002年に発表したAOS署名スキームについて理解した方が分かりやすい。↑のブログではAOS方式を単純化して説明している。

ここではSchnorr署名の式を利用する。鍵ペア P = xG、nonce R = kGで、Schnorr署名の s = k + H(m || R)x とした場合、署名の検証は

sG = R + H(m || R)P

が成立するか検証する。

この検証式、Rの秘密鍵を知らず作ることができるだろうか?

答えはNoで、Rを計算する前にH(m || R)でRを含む値のハッシュ値を知る必要があるが、そのハッシュ値を計算する前にRが必要になる。鶏が先が卵が先か。

この検証式をベースに、ハッシュ値が前のコミットメントを参照するSchnorr署名の式を考える。サンプルとしてN = 4人のメンバーによるリング署名を想定する。4人の公開鍵のセットを {P_0, P_1, P_2, P_3}とし、そのうち秘密鍵を知っているのは {P_2 = x_2G}のみと仮定する。

  •  {s_0G = R_0 + H(m || R3)P_0}
  •  {s_1G = R_1 + H(m || R0)P_1}
  •  {s_2G = R_2 + H(m || R1)P_2}
  •  {s_3G = R_3 + H(m || R2)P_3}

署名の生成

ハッシュを計算する際のRは1つ前のRを参照している。この内 {P_2}秘密鍵を知っている場合、以下の順序で計算すると、この式を満たす値を計算することができる。

  1. まず {R_2}の離散対数となる {k_2}をランダムに選択する。 {R_2 = k_2G}
  2. 続いて、またランダムに {s_3}の値を選択する。
  3.  {R_3 = s_3G - H(m || R_2)P_3}を計算し、 {s_0}をランダムに選択する。
  4.  {R_0 = s_0G - H(m || R_3)P_0}を計算し、 {s_1}をランダムに選択する。
  5.  {R_1 = s_1G - H(m || R_0)P_1}を計算する。
  6. 最後に {s_2}をランダムではなく、 {s_2 = k_2 + H(m || R_1)x_2}で計算する。

署名の検証

こうして出来た値 {(e_0 = H(m || R_3), s_0, s_1, s_2, s_3)}が署名データとなり、どの秘密鍵を使ったのか明かすことなく、以下の検証ができる。

  1. まず {e_0, s_0}を使って、 {R_0 = s_0G - e_0P_0}を計算する。
  2. あとは順に、 {e_1 = H(m || R_0), R_1 = s_1G - e_1P_1}
  3.  {e_2 = H(m || R_1), R_2 = s_2G - e_1P_2}
  4.  {e_3 = H(m || R_2), R_3 = s_3G - e_1P_3}
  5. 最後に、 {e_0 = H(m || R_3)}が成立するか検証する。

LWWのLSAG署名スキーム

↑を踏まえた上で、LSAGの署名スキームについて。

まず、署名者はn個の公開鍵のセット {L = {P_0, ..., P_{n-1}}}を選択する。この内、署名者が秘密鍵を持っている公開鍵のインデックスをπとする。続いて、キーイメージとして知られる、特別な新しい種類の曲線上の点を形成する。

 {I = x_π ℍ(L)}

ℍはスカラーではなく曲線上の点を出力するハッシュ関数。実装する方法としては、LのSHA-256ハッシュを取り、その256 bitの数値をsecp256k1のx座標として解釈し、xをインクリメントしながら有効な点(x, y)を見つける。

このキーイメージは署名に含まれるため、公開され誰もが知る値となる。しかし、それがどのインデックスの値で作られたのかは誰も知らない。

LSAGの署名生成

以下の手順で署名を生成する。

  1. ランダムな値  {k_π} を選択する。
  2. πの次のインデックスのハッシュチャレンジを作成する。  {e_{π+1} = H(m || L || k_πG || k_πℍ(L) || I)}
  3. ランダムな値 {s_{π+1}}を選択する。
  4.  {R_{π+1} = s_{π+1}G - e_{π+1}P_{π+1}}および {R_{π+1}^* = s_{π+1}ℍ(L) - e_{π+1}I}を計算する。
  5. 次のハッシュチャレンジ {e_{π+2} = H(m || L || R_{π+1} || R_{π+1}^* || I)}を計算し、続くRおよびR*の計算を残りのインデックス分続ける。インデックス毎にsの値をランダムに選択するが、インデックスπの場合だけは {s_π = k_π + e_πx_π}とする。
  6. そして署名値 {σ_L(m) = (s_0, ..., s_{n-1}, e_0, I)}ができあがる。

公開するハッシュチャレンジは1つのみで、他のチャレンジはそれから決定論的に生成されるのはLWWのスキームと変わらない。LSAGの場合、加えて、キーイメージIを署名の一部として公開する。

LSAGの署名検証

公開鍵のセットLと、メッセージmおよび署名 {σ_L(m) = (s_0, ..., s_{n-1}, e_0, I)}が与えられると、以下の手順で署名を検証する。

  1.  {R_0 = s_0G - e_0P_0}および {R^*_0 = s_0ℍ(L) - e_0I}を計算し、それを使って、 {e_1 = H(m || L || R_0 || R^*_0 || I)}を計算する。
  2.  {e_0}を計算するまで、この計算を続けて、 {e_0 = H(m || L || R_{n-1} || R^*_{n-1} || I)}が成立するか検証し、成立したら有効な署名となる。

Adam Backが提案したLSAGの修正

LWWのLSAGではキーイメージは {I = x_π ℍ(L)}と、保持する秘密鍵と公開鍵のセットから計算されていた。このためこのキーイメージを署名に添付してLinkabilityによりチェックできるのは、

  • 同じ公開鍵セットを使った異なるLSAG署名が複数ある場合、それらが同じ秘密鍵により署名されているかどうか

である。つまり公開鍵セットが異なると、キーイメージも異なる。そのため、Moneroのような送信者が任意の公開鍵のセットを選択できるケースにおいては、二重使用をチェックできない。

2015年、Adam Backが提案したのはLWWのLSAGの以下の点を変更する↓

  • まずキーイメージを {I = x_π ℍ(P_π)}とする。公開鍵のセットLではなく、秘密鍵 {x_π}に対応する {P_π}を使って生成する。
  • πの次のインデックスのハッシュチャレンジの作成はLの部分が {P_π}になりIも含めなくなる→  {e_{π+1} = H(m || L || k_πG || k_πℍ(P_π))}
  •  {R_{π+1} = s_{π+1}G - e_{π+1}P_{π+1}}の計算は変わらないが、 {R_{π+1}^* = s_{π+1}ℍ(P_{π+1}) - e_{π+1}I}はLの部分が変わる。
  • 次のハッシュチャレンジもLとIがなくなり、 {e_{π+2} = H(m || R_{π+1} || R_{π+1}^* )}

他はLWWと同様。

↑のようにキーイメージが公開鍵のセットLに関係なく、使用するキーに固定されるので、Linkabilityのチェックの際に、公開鍵セットが異なる複数のリング署名が与えられても、署名に使った秘密鍵は同じであれば、それをチェックでき、Moneroのようなトランザクション毎に公開鍵セットが変わるようなケースにおける二重使用のチェックが可能になる。

実際にMoneroで使われているリング署名の仕組みはもう少し複雑で、Multilayered Linkable Spontaneous Anonymous Group Signatures(MLSAG)と呼ばれる署名スキームを使っている。これはMoneroがコインの量を秘匿するRing CTプロトコルを導入した際に一緒に導入された。MLSAGと他のリング署名の主な違いはMのマルチレイヤーの部分だ。n個の鍵のリング署名の代わりに、MLSAGはn個のキーベクトルのセットにリング署名を使用する。そのため2つのレイヤーというか次元ができ、そのためマルチレイヤーと呼ばれみたい。

とLSAGの仕組みが分かってきたので、次回はもともと読む予定だったDLSAGの内容を見ていきたい。

*1:2018年のScaling BitcoinではMulti Hop Locksの提案していた

チェーン上のトランザクションの新たな参照方法の標準TxRefを定義したBIP-136

提案は結構前からあったみたいだけど先月マージされたBIP-136↓

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

Bitcoinトランザクションを識別する際は、基本的にトランザクションのハッシュのエンディアンを逆にしたTXIDを使用する。フルノードでこのTXIDをキーにしてトランザクションを取得したい場合は予め-txindexオプションを有効にしてTXIDによるインデックスを作成しなければならない。このインデックスの作成が高価なのと、TXID自体32バイトと長い。そのため↑のBIP-136では、TXIDに変わってブロックチェーン上のトランザクションを参照する新しい識別子TxRefを提案している。

TxRefは何番目のブロックの何番目のトランザクションという、ブロック高とトランザクションの位置をエンコードしたデータになる。そのため、reorgなんかが起こると参照先のトランザクションが別のものに変わったり、なくなっている可能性があるという制約が付く。

具体的なユースケースがあるのか?と思って調べたら、どうも分散IDの文脈で、Bitcoinブロックチェーンを利用したDID methodの1つであるBTCR DID methodでチェーン上のトランザクションの位置を指すのにTxRefエンコーディングを使ってるっぽい↓

https://w3c-ccg.github.io/didm-btcr/#txref

注意点としては、やっぱりreorgの影響かな。BIPにも100承認以上とあるけど、TXIDと違って別のTxを参照する可能性があるので承認がある程度ないと使いづらい。

以下、BIPの内容↓

イントロダクション

概要

この文書は、Bitcoinブロックチェーン内のトランザクションの位置および参照トランザクション内の特定のOutPointインデックスを参照するための標準的な方法として、人が便利に使用できるフォーマット「TxRef」を提案する。このフォーマットの主な目的は、承認されたトランザクションを参照する際の標準的で信頼性のある簡潔な方法を提供することだ。

注意:IDと実際のトランザクションとの間に強力な暗号学的リンクがあるTxIDとは違い、TxRefは特定のトランザクションへの弱いリンクを提供するだけだ。TexRefはトランザクションブロックチェーン内でのオフセットを指すが、これは実際のトランザクションを指している場合と指していない場合がある(実際のトランザクションは再編成によって変わることがある)。TxRefは、成熟度が100ブロック未満のブロックチェーン内の位置には使用しないことを推奨する。

動機

Bitcoinの初期バージョン以降、TxID(トランザクション識別子)はコンセンサスプロトコルのコア部分であり、ユーザー間で個々のトランザクションを識別するために日常的に使われてきた。

しかし、多くのユースケースにおいて、実用上の制限がある。

  • TxIDは、フルノードが検索するのには高価である(ブロックチェーンのリニアなスキャンか、高価なTxIDのインデックスを必要とする)。
  • TxIDは、SPVウォレットが検索するにはサードパーティのサービスを必要とする。
  • TxIDは非常に長いHEXエンコード値(64文字)である。

ブロックチェーンに埋め込まれているトランザクションの場合、そのTxIDではなく、ブロックチェーン自体の中のそのトランザクションの位置により参照することが可能だ。また人が転記しやすいようにエンコードできる。この文書ではこのための標準を提案する。

サンプル

以下はBitcoinトランザクションのサンプル。

仕様

承認済みトランザクションの位置参照、つまりTxRefはブロックの高さとブロック内のトランザクションのインデックスおよびオプションでトランザクション内のOutPointのインデックスによって指定される、ブロックチェーン内の特定の場所への参照だ。

注意:この仕様の全ての値はリトルエンディアン形式でエンコードされている。

TxRef

以下の理由によりTxRefは存在しない場所を参照している可能性がある:

したがって、実装者はTxRefを早い段階でユーザーに表示しないよう注意する必要がある:

エンコーディング

TxRefはBIP-173で定義されている標準のBech32エンコーディングを使用しているため、以下で構成される。

  • Human-readable、つまりHRPの部分は、namespaceを提供する。MainnetとTestnetを区別するための以下のように定義する。
    • Mainnetの場合は:tx
    • Testnetの場合は:txtest
    • これら2つと他のプロジェクトに関連するものを含む完全なHRPのリストについては、SLIP-0173を参照。
  • セパレータ: 1
  • データパート

注意:分散IDの仕様など他の仕様では、HRP内の他の場所に含まれる情報が暗黙的にエンコードされている。この場合、ここで指定されているようなHRPを含まないことを選択するかもしれない。

移植性と可読性を高めるため、セパレータを追加する必要がある。

  • 1の後にコロンを追加する。
  • コロンの後、4文字毎にハイフン(-)を追加する。

bech32のコードセパレータの後にある非bech32アルファベット文字は、パースの際に無視/削除しなければない(終端文字を除く)。

TxRefのテキストエンコーディングは、

Bit Character Characters Value
Human-readable部分 1-2 2 BitcoinのMainnetはtx、Testnetはtxtest
セパレータ 3 1 1
コロン 4 1 :
データ 0-19 5-8 4
ハイフン 9 1 -

データ - ハイフンパターンは、データ全体の長さに渡って繰り返される(ハイフンがエンコードされた20bitまたは4データ文字毎に挿入される)。

データ

オプションのトランザクションのOutPointが含まれるかどうかで、上記文字列にエンコードされた75ビットもしくは90ビットのデータになる。これらのbitは次のように定義されている。

Bitcoin MainnetとTestnetのTxRefバイナリフォーマット

Bit Bit(s) Type values Notes
マジックコード 0-4 5 チェーンのネームスペースコード Bitcoinの場合は0x03、OutPointを含むMainnetの場合は0x04。Testnetが0x06でOutPointを含むTestnetが0x07
バージョン 5 1 将来のための確保 必ず0x0
ブロック高 6-29 24 Txのブロック高 ブロック0(ジェネシス)〜ブロック16777215 2328年まで
トランザクションインデックス 30-44 15 ブロック内のTxインデックス Tx0(コインベース)〜32767番目のTxまで ブロック内の最大Txが16665個

マジックコードが0x040x07の場合、オプションのOutPointがエンコーディングに含まれる。

Bit Bit(s) Type values Notes
OutPoint インデックス 45-59 15 Tx内のOutPointのインデックス OutPoint 0〜32767番目のOutPointまで

最後に30bitのチェックサムを含める。

Bit Bit(s) Type values Notes
チェックサム 45-74 or 60 - 89 30 Bech32チェックサム

マジックに関して

マジックコードはチェーン間のnamespaceを提供する。BitcoinのMainnetとTestnetには5bitのマジックコードが使われている(他のプロジェクトやチェーンではかなり長くなるかもしれない):

  • Bitcoin Mainnetの場合、マジックコードは0x3で、エンコードすると文字rになる。
  • OutPointを含むBitcoin Mainnetの場合マジックコードは0x4で、エンコードすると文字yになる。
  • Bitcoin Testnetの場合、マジックコードは0x6で、エンコードすると文字xになる。
  • OutPointを含むBitcoin Testnetの場合マジックコードは0x7で、エンコードすると文字8になる。

コード0x00x10x20x5Bitcoinの将来のプロジェクト用に予約されている。

他のチェーンは0x0から0x7までで始まるマジックコードとして使ってはならない。

他のチェーンのマジックコードはSLIP-XXXX "TxRef for Non-Bitcoin Chains and Networks"で指定される。

互換性

互換性に関する既知の課題はない。

論拠

  1. 承認済みトランザクションの参照になぜBech32エンコーディングを使用するのか?
    Bech32エンコーディングフォーマットの誤り検出および訂正特性は魅力的だ。ソフトウェアが最大2文字の修正するのが妥当だと期待しているが、まだこれを指定していない。
  2. どうしてコロンを追加したのか?
    これによりW3CのURN/URL標準への準拠性が向上する。
  3. TxRef内にハイフンがあるのはなぜ?
    TxRefは短いので、音声で引用するか手で書くことを予想している。4文字毎にハイフンを入れると文字列が分割され、人が場所を簡単に見失わないようになる。
  4. 非bech32アルファベット文字列を削除するのはなぜ?
    ユーザーは自分のTxRefを良いUnicode形式にしておきたいと望むことはないと思っている。コピーやペースト、手書きを組み合わせて書くと予想する。パーサーはこれらによる一般的なエラーを全て自動的に修正すべきだ。

参照実装

Appendix

Test Vector

以下を含む2つのTest Vectorをセットがある。

  • Bech32エンコードされたTest Vector。実装が正しいHuman-readableパートとセパレーターを含む円k−土を受け入れるかどうかテストするのに使用する。
  • Bitcoin TxRef Test Vector。完全な仕様、特にブロック高およびトランザクションインデックスの正しい値かどうかテストするのに使用する。
TxRef用のBech32エンコーディング

注意:すべてのTest Vectorは文字列が準拠しているかどうかをテストするのに役立つ。すべての実際のアプリケーション(Bitcoin向けの)は、書きのBitcoinのTest Vectorに準拠している必要がある。

以下の文字列は有効なHuman Readable PartとBech32チェックサムを持つ。

  • TX1A12UEL5L
  • tx1an83characterlonghumanreadablepartthatcontainsthenumber1andtheexcludedcharactersbio1tt5tgs
  • tx1abcdef1qpzry9x8gf2tvdw0s3jn54khce6mua7lmqqqxw
  • tx11qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqc8247j

以下のリストは無効なTxRefとその理由を示している。

  • bc1qw508d6qejxtdg4y5r3zarvary0c5xw7kg3g4ty: Human-Readable Partが無効
  • tx1qw508d6qejxtdg4y5r3zarvary0c5xw7kv8f3t5チェックサムが無効
Bitcoin TxRef(mainnetおよびtestnet)

以下のリストは正しくエンコードされたBitcoin mainnetのTxRefとhex値(ブロック高およびトランザクションインデックス)。

  • tx1:rqqq-qqqq-qmhu-qhp: (0x0, 0x0)
  • tx1:rqqq-qqll-l8xh-jkg: (0x0, 0x7FFF)
  • tx1:r7ll-llqq-qghq-qr8: (0xFFFFFF, 0x0)
  • tx1:r7ll-llll-l5xt-jzw: (0xFFFFFF, 0x7FFF)

以下のリストは正しくエンコードされたBitcoin testnetのTxRefとhex値(ブロック高およびトランザクションインデックス)。

  • txtest1:xqqq-qqqq-qkla-64l: (0x0, 0x0)
  • txtest1:xqqq-qqll-l2wk-g5k: (0x0, 0x7FFF)
  • txtest1:x7ll-llqq-q9lp-6pe: (0xFFFFFF, 0x0)
  • txtest1:x7ll-llll-lew2-gqs: (0xFFFFFF, 0x7FFF)

以下のリストは(奇妙フォーマットされているが)有効なBitcoin TxRefとhex値(ブロック高およびトランザクションインデックス)。

  • tx1:rjk0-uqay-zsrw-hqe: (0x71F69, 0x89D)
  • TX1RJK0UQAYZSRWHQE: (0x71F69, 0x89D)
  • TX1RJK0--UQaYZSRw----HQE: (0x71F69, 0x89D)
  • tx1 rjk0 uqay zsrw hqe: (0x71F69, 0x89D)
  • tx1!rjk0\uqay*zsrw^^hqe: (0x71F69, 0x89D)

以下のリストは無効なTxRefとその理由。

  • tx1:t7ll-llll-ldup-3hh: 0x3の代わりにマジックが0xBになっている。(0xFFFFFF, 0x7FFF)
  • tx1:rlll-llll-lfet-r2y: バージョンが0でなく1になっている。(0xFFFFFF, 0x7FFF)
  • tx1:rjk0-u5ng-gghq-fkg7: 有効なBech32だが、8ではなく10x5 bitのパッケージになっている。
  • tx1:rjk0-u5qd-s43z: 有効なBech32だが、8ではなく6x5bitのパッケージになっている。
OutPointを含むBitcoin TxRef(mainnetおよびtestnet)

以下のリストは正しくエンコードされたOutPointを含むBitcoin mainnetのTxRefとhex値(ブロック高およびトランザクションインデックス、TXOインデックス)。

  • tx1:yqqq-qqqq-qqqq-ksvh-26: (0x0, 0x0, 0x0)
  • tx1:yqqq-qqll-lqqq-v0h2-2k: (0x0, 0x7FFF, 0x0)
  • tx1:y7ll-llqq-qqqq-a5zy-tc: (0xFFFFFF, 0x0, 0x0)
  • tx1:y7ll-llll-lqqq-8tee-t5: (0xFFFFFF, 0x7FFF, 0x0)
  • tx1:yqqq-qqqq-qpqq-5j9q-nz: (0x0, 0x0, 0x1)
  • tx1:yqqq-qqll-lpqq-wd7a-nw: (0x0, 0x7FFF, 0x1)
  • tx1:y7ll-llqq-qpqq-lktn-jq: (0xFFFFFF, 0x0, 0x1)
  • tx1:y7ll-llll-lpqq-9fsw-jv: (0xFFFFFF, 0x7FFF, 0x1)
  • tx1:yjk0-uqay-zrfq-g2cg-t8: (0x71F69, 0x89D, 0x123)
  • tx1:yjk0-uqay-zu4x-nk6u-pc: (0x71F69, 0x89D, 0x1ABC)

以下のリストは正しくエンコードされたOutPointを含むBitcoin testnetのTxRefとhex値(ブロック高およびトランザクションインデックス、TXOインデックス)。

  • txtest1:8qqq-qqqq-qqqq-cgru-fa: (0x0, 0x0, 0x0)
  • txtest1:8qqq-qqll-lqqq-zhcp-f3: (0x0, 0x7FFF, 0x0)
  • txtest1:87ll-llqq-qqqq-nvd0-gl: (0xFFFFFF, 0x0, 0x0)
  • txtest1:87ll-llll-lqqq-fnkj-gn: (0xFFFFFF, 0x7FFF, 0x0)
  • txtest1:8qqq-qqqq-qpqq-622t-s9: (0x0, 0x0, 0x1)
  • txtest1:8qqq-qqll-lpqq-q43k-sf: (0x0, 0x7FFF, 0x1)
  • txtest1:87ll-llqq-qpqq-3wyc-38: (0xFFFFFF, 0x0, 0x1)
  • txtest1:87ll-llll-lpqq-t3l9-3t: (0xFFFFFF, 0x7FFF, 0x1)
  • txtest1:8jk0-uqay-zrfq-xjhr-gq: (0x71F69, 0x89D, 0x123)
  • txtest1:8jk0-uqay-zu4x-aw4h-zl: (0x71F69, 0x89D, 0x1ABC)

Bitcoin TxRef ペイロード値の選択

ブロック高とトランザクションインデックスの特定のビット長を選択した理由を示すいくつかの計算結果がある。

ブロック高の値:

0〜0xFFFFFF(16,777,216ブロック)の間の24 bit。

  • 毎年52500ブロック増え、アドレス可能なブロックは319年分である。
  • しtがって、2328年より前にこの仕様は拡張されるべきだ(我々には十分な時間がある)。
トランザクションの位置の値:

0x0から0x7FFF(32,768トランザクション)の15 bit。

  • 現実的な最小のトランザクションは83バイトで、1ブロック内で最大トランザクション数は12047。
    • 4B version + 1B tx_in count + 36B previous_output + 1B script length + 0B signature script + 4B sequence + 1B tx_out count + 8B amount + 1B script length + 23B pubkey script + 4B lock_time = 83B
  • 極端に最小のトランザクションは60バイトで、1ブロック内の最大トランザクション数は16665。
    • 4B version + 1B tx_in count + 36B previous_output + 1B script length + 0B signature script + 4B sequence + 1B tx_out count + 8B amount + 1B script length + 0B pubkey script + 4B lock_time = 60B

LNでインボイスを必要としないSpontaneous Paymentの2つの実装方法

通常Lightning Networkの決済では、支払先が予めインボイスを作成し、それを支払元に送ることで支払いがスタートする。このインボイスにはLNでマルチホップ決済をするにあたって、支払先のノードIDやコントラクトを構成する際に必要な情報(プリイメージのハッシュ、HTLCの有効期間など)が含まれる。これらの情報の伝達のため、基本的にLNではインボイスを使った支払いフローがデフォルトになっている。

ただ、Bitcoinのオンチェーントランザクションのように、相手のアドレスさえわかっていれば、相手と対話することなく支払元か直接支払するというユースケースも十分考えられる。

AMPを利用する方法

インボイスを必要としないSpontaneous Paymentについては、既にAMP(Atomic Multi Path Payments)をベースにしたアイディアがある。

従来のLNでは決済に使用するプリイメージは支払先が作成し、そのハッシュをインボイスに載せて支払元に伝達するが、Spontaneous Paymentでは、支払元がプリイメージを作成し、ルーティング含めた決済ではそのプリイメージのハッシュを使用する。そしてLNのオニオンルーティングを仕組みを利用して、プリイメージは支払先のみが復号できるように暗号化され、LNのルーティングパケットの最後のオニオンパケットにセットされ、支払先まで送信される。データを受信した支払先のノードは、プリイメージを復号し、そのプリイメージを利用して支払を受け取る。

この機能の自体は支払元と支払先のノードだけ、この仕組みに対応していればよく、中間ノードは通常のLN決済として認識する。

ECDHを利用する方法

このSpontaneous Paymentについて、ECDHを利用する方法が先日LNの開発者MLに新しいアイディアがポストされた↓

[Lightning-dev] ECDH for spontaneous payments and offline vending machines

このアイディアは、↑で発生する暗号化したプリイメージのルーティングをECDHを使うことで不要にしようというもの。

支払元から支払先へのLNのルーティングができるのであれば、両者がECDH(楕円曲線 Diffie-Hellman)によって導出できる共有シークレットを持つことを意味するため、それをプリイメージとして使えば、暗号化したプリイメージ自体をルーティングする必要はないというもの。

ECDHは楕円曲線を使って共通鍵を導出する仕組みで、アリスとボブがそれぞれ秘密鍵abと対応する公開鍵A = aGB = bGを持ち、それぞれ相手の公開鍵を知っている場合、相手の公開鍵に自分の秘密鍵を乗算して出来た点は同じ点を指すという特性ががある。

共通鍵 = a * B = b * A

具体的には、支払先のノードのノードIDをN(ノードID = 公開鍵)、支払元が支払の際に生成する一時鍵(ephemeral key)をkとするとk * Nで新しい点が算出され、その点のx座標のハッシュをプリイメージとし、x座標のdoubleハッシュをペイメントハッシュとするというもの。

この場合、支払先のノードは自分がインボイスとして発行したものではないペイメントハッシュの支払を受け取ったら、自身のノードIDN秘密鍵nとオニオンパケットにセットされている一時鍵kの公開鍵(K = kGとする)を使って共通鍵n + Kを計算し、そのx座標のdoubleハッシュと比較する。合致すれば対応する共有シークレットがその支払のプリイメージとなる。

既にChristian Deckerによるc-lightningで動作するPoCコードもある↓

GitHub - cdecker/lightning at stepan-pay

プリイメージ用に余計なオニオンパケットのデータを作らなくて良い分、ECDHの方がデータ量が少し少なくて済むのでシンプルで良いかもね。