Develop with pleasure!

福岡でCloudとかBlockchainとか。

Output Script Descriptorの基本仕様を定義したBIP-380

Output Script Descriptorは、Bitcoin Core v0.17からサポートされ始めた言語で、ウォレットやその他のプログラムが、自身が所有(関連)するUTXOを追跡するのに必要な情報を含むデータを定義する。

Bitconiのウォレットの多くはHDウォレットをサポートしており、基本的には12個 or 24個からなるニーモニックをバックアップしておけば、マスターシードが復元でき、ウォレットが所有するUTXOを認識できる。

ただ、Segwit(P2WPKH、P2WSH)を始めマルチシグや、11月にアクティベート予定のTaprootへの支払いであるP2TRアドレスなど、1つの鍵が取るアドレス(アウトプット)の形態が増えてきたため、単純に鍵を復元しただけでは、どのアドレスを復元するのか判断できなくなっている。

そのため、ウォレット間のインターオペラビリティを担保するために、アウトプット(アドレス)の導出方法まで含めてウォレットのバックアップができるようにOutput Script Descriptorを利用しようと、今回新しくOutput Script DescriptorのBIPが定義された↓

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

BIP-380で定義されているのは、Output Script Descriptorの基本コンセプトと、ベースとなるScirpt Experession、Key Expressionとチェックサムの仕様について。その他のExpressionについては後続のBIPで定義されている。

まぁ、でもウォレットのエクスポート形式がOutput Script Descriptorになって、アドレス追加する度にウォレットのバックアップが必要になるのは、マスターシードさえバックアップしておけばいい現状の仕組みと比べて不便だな。それとも/*みたいな指定方法で回避するようになるのかな?

以下、BIP-380の意訳↓

概要

Output Script Descriptorは、Output Scriptのコレクションを記述するために使用できるシンプルな言語である。さまざまなdescriptorの断片や関数がある。このドキュメントでは、descriptorの一般的な構文、チェックサムおよび共通の式について記載する。

動機

Bitcoinウォレットは、従来、鍵のセットを保存していた。これらの鍵は、後でシリアライズされ、ウォレットが監視するOutpu Scriptやユーザーに提供するアドレスを生成するのに使われる。通常、バクアップは秘密鍵のみで構成され、最近では、BIP39のニーモニックの形で保存されている。しかし、Segregated Witnessが導入され、新たなアウトプットタイプが追加されてからは、このバックアップ方法では不十分だ。秘密鍵だけでは、復元されたウォレットがどのような種類のOutput Scriptやアドレスを生成するか知ることはできない。そのため、バックアップを復元したり、監視用ウォレットのデータをエクスポートする際に、ウォレット間で互換性がないという問題があった。

さらに問題を複雑にしているのがBIP32の導出パスだ。BIP44, 49, 84では、さまざまなOutput Scriptやアドレスのための標準的なBIP32導出パスが定義されているが、すべてのウォレットがそれらをサポートしている訳ではなく、それらの導出パスを使っているわけでもない。これらのバックアップやエクスポートに導出パスの情報が含まれていないため、ウォレット間の互換性が失われてしまう。

これらの問題に対する現在の解決策は、一般的なものではなく、レイヤー違反とみなすことができる。拡張鍵のシリアライゼーションに異なるversion byteを導入するような解決策は、レイヤー違反であり(鍵の導出はスクリプトタイプの意味とは分離されるべき)、特定の導出パスとスクリプトタイプにのみ特有のものだ。

Output Script Descriptorは、これらの問題に対する一般的な解決策を導入する。スクリプトタイプはScript Expressionを用いて明示的に指定される。鍵の導出パスはKey Expressionで明示的に指定する。これにより、作成するスクリプトやサブスクリプト(redeemScriptやwitnessScriptなど)および鍵を正確に指定したウォレットのバックアップおよびエクスポートを作成できる。本BIPで指定された一般的な構造により、新しいスクリプトタイプが追加されると、新しいScript Expressionを導入することができる。最後に、共通の用語と既存の規格を使用することで、Output Script Descriptorを技術的に読みやすくし、結果を一目で理解できるようにしている。

仕様

Descriptorはいくつかのタイプの式で構成される。最上位の式はSCRIPT。この式の後には#CHECKSUMが続く。ここでCHECKSUMは8文字の英数字のdescriptorのチェックサム

Script Expression

Script Expression(SCRIPTと表記)は、Bitcoinスクリプトに直接対応する式。これらの式は関数として記述され、引数を取る。このような式には、対応する引数を満たすスクリプトテンプレートがある。式は人が読める識別子文字列で書かれ、引数は括弧で囲まれている。識別子の文字列は英数字で、アンダースコアを含むことができる。

Script Expressionの引数は、その式自体によって定義される。Script Expression、Key Expressionまたはその他の式である可能性がある。

Key Expression

Script Expressionの引数としてよく使われる式に、Key Expression(KEYと表記)がある。これは公開鍵または秘密鍵と、オプションとしてその鍵のオリジンに関する情報を表す。Key Expressionは、Script Expressionの引数としてのみ使用することができる。

Key Expressionは以下の要素で構成される:

  • オプションで、以下で構成されるキーオリジンの情報:
    • 開き括弧[
    • 導出を開始する鍵のfingerprintを表す正確な8つのhex文字(詳細はBIP-32参照)
    • fingerprintとそれに続く鍵との間の、非強化導出または強化導出ステップを示す0個以上の/NUMもしくは/NUMhパス要素。
    • 閉じ括弧]
  • 次のいずれかである実際の鍵が続く:
    • hexエンコードされた公開鍵で、Script Expressionに応じて、次のいずれかになる:
      • 圧縮公開鍵を表す02または03で始まる66個のhex文字列
      • 非圧縮公開鍵を表す04で始まる130個のhex文字列
    • WIFエンコードされた秘密鍵
    • xpubエンコードされた拡張公開鍵、もしくはxprvエンコードされた拡張秘密鍵(詳細はBIP-32参照)
      • 拡張鍵の後に、実行されるBIP32導出ステップを示す0個以上の/NUMもしくは/NUMhパス要素が続く。
      • オプションで、最後のステップで単一の/*または/*hが続く。これはすべての直接的な非強化もしくは強化導出される子を示す。

KEYがBIP32拡張鍵の場合、Output Scriptを作成する前に、拡張鍵の後に続く導出情報を使って子鍵を導出する必要がある。最終ステップが/*または/*hの場合は、各子鍵のインデックス毎にOutput Scriptが作成される。導出した鍵は、非圧縮公開鍵としてシリアライズしてはならない。Script Expressionでは、導出した公開鍵をスクリプト作成のためどうシリアライゼーションするかについて、追加要件が定められている場合がある。

上記の仕様では、強化導出を示すhは、代替表現であるH'に置き換えることができる。

強化導出を伴うKey Expressionの正規化

秘密鍵なしでdescriptorがエクスポートされる場合、エクスポートされたdescriptorが有用であるためには、中間の強化導出ステップを削除するために追加の導出を行う必要がある。エクスポーターは、最後の強化導出ステップで拡張公開鍵を導出し、その拡張公開鍵をdescriptorの鍵として使用しなければならない。その鍵を導出するまでに行われた導出ステップは、前の鍵のオリジン情報に追加されなければならない。鍵のオリジン情報がない場合、新たに導出した拡張公開鍵のために追加しなければならない。最終的な導出が強化導出の場合、追加の導出は必要ない。

文字セット

descriptorで使用される式には、descriptorのチェックサムが機能するように、この文字セット内の文字のみが含まれている必要がある。

許可される文字は:

0123456789()[],'/*abcdefgh@:$%{}
IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~
ijklmnopqrstuvwxyzABCDEFGH`#"\<space>

最後の行の<space>はスペース文字であることに注意。

この文字セットは、以下のチェックサムがより多くのエラーを識別できるように、32文字の3つのグループとして特定の順序で書かれている。最初のグループは最も一般的な「保護されていない」文字(つまり、hexやkeypathなどの独自のチェックサムを持たないもの)。大文字小文字のエラーは32の倍数のオフセットを発生させるが、その一方で、前の制限に従い、できるだけ多くのアルファベット文字が同じグループに入っている。

チェックサム

トップレベルのScript Expressionの後には、単一のナンバー記号(#)とそれに続く8文字のチェックサムが続く。チェックサムはbech32と同様のエラー訂正チェックサムだ。

チェックサムには以下の特性がある:

  • descriptor文字列の間違いは、「シンボルエラー」で測定される。シンボルエラーの数が多いほど、検出が難しくなる:
    • 0123456789()[],'/*abcdefgh@:$%{}の文字を、そのセット内の別の文字に置き換えるエラーは、常に1シンボルエラーとしてカウントされる。
      • hexエンコードされた鍵はこれらの文字でカバーされることに注意してほしい。拡張鍵(xpubおよびxprv)は他の文字も使用するが、独自にチェックサムの仕組みもある。
      • SCRIPT式の関数名は、他の文字を使用する。これらの文字を間違えると、通常descriptorをパースできりなくなる。
    • 大文字小文字のエラーは常に1シンボルエラーとしてカウントされる。
    • その他の1文字の置換エラーは、1つまたは2つのシンボルエラーとしてカウントされる。
  • 1シンボルエラーは常に検出される。
  • 最大49154文字までのdescriptorの2または3シンボルエラーは常に検出される。
  • 最大507文字までのdescriptorの4シンボルエラーは常に検出される。
  • 最大77文字までのdescriptorの5シンボルエラーは常に検出される。
  • 最大387文字までのdescriptorで5シンボルエラーが検出されない可能性を最小限に抑えるよう最適化されている。
  • ランダムエラーは、 {1/2^{40}}で検出されない可能性がある。

チェックサム自体はbech32と同じ文字セットqpzry9x8gf2tvdw0s3jn54khce6mua7lを使用する。

チェックサム付き有効なdescriptor文字列は、以下のPython3のコードスニペットで指定された有効性の基準に合格する必要がある。descsum_check関数は、引数sSCRIPT#CHECKSUM形式で構成されるdescriptorである場合にtrueを返す。

INPUT_CHARSET = "0123456789()[],'/*abcdefgh@:$%{}IJKLMNOPQRSTUVWXYZ&+-.;<=>?!^_|~ijklmnopqrstuvwxyzABCDEFGH`#\"\\ "
CHECKSUM_CHARSET = "qpzry9x8gf2tvdw0s3jn54khce6mua7l"
GENERATOR = [0xf5dee51989, 0xa9fdca3312, 0x1bab10e32d, 0x3706b1677a, 0x644d626ffd]

def descsum_polymod(symbols):
    """Internal function that computes the descriptor checksum."""
    chk = 1
    for value in symbols:
        top = chk >> 35
        chk = (chk & 0x7ffffffff) << 5 ^ value
        for i in range(5):
            chk ^= GENERATOR[i] if ((top >> i) & 1) else 0
    return chk

def descsum_expand(s):
    """Internal function that does the character to symbol expansion"""
    groups = []
    symbols = []
    for c in s:
        if not c in INPUT_CHARSET:
            return None
        v = INPUT_CHARSET.find(c)
        symbols.append(v & 31)
        groups.append(v >> 5)
        if len(groups) == 3:
            symbols.append(groups[0] * 9 + groups[1] * 3 + groups[2])
            groups = []
    if len(groups) == 1:
        symbols.append(groups[0])
    elif len(groups) == 2:
        symbols.append(groups[0] * 3 + groups[1])
    return symbols

def descsum_check(s):
    """Verify that the checksum is correct in a descriptor"""
    if s[-9] != '#':
        return False
    if not all(x in CHECKSUM_CHARSET for x in s[-8:]):
        return False
    symbols = descsum_expand(s[:-9]) + [CHECKSUM_CHARSET.find(x) for x in s[-8:]]
    return descsum_polymod(symbols) == 1

これにより、上記の特性を持つBCH符号が実装される。descriptor文字列全体が最初に処理されシンボルの配列になる。各文字のシンボルはそのグループ内での位置。3つめのシンボルごとにグループ番号を組み合わせた4つめのシンボルが挿入される。これは、グループ内の位置にのみ影響する変更、もしくはグループ番号の変更にのみ影響する変更は、単一のシンボルのみに影響することを意味する。

Script Expressionを指定して有効なチェックサムを作成する場合、以下のコードを使用できる:

def descsum_create(s):
    """Add a checksum to a descriptor without"""
    symbols = descsum_expand(s) + [0, 0, 0, 0, 0, 0, 0, 0]
    checksum = descsum_polymod(symbols) ^ 1
    return s + '#' + ''.join(CHECKSUM_CHARSET[(checksum >> (5 * (7 - i))) & 31] for i in range(8))

後方互換

Output Script Descriptorは、まったく新しい言語であり、既存のソフトウェアとは互換性がない。ただし式の多くのコンポーネントはこれまでのBIPで定義されたエンコーディングとシリアライゼーションを再利用する。

Output Script Descriptorは、将来の拡張用に、あらにセグメントタイプと新しいScript Expressionを使って設計されている。これらは追加のBIPに定義される。

参照実装

descriptorは、バージョン0.17以降のBitcoin Coreに実装されている。

Appendix A:式のインデックス

将来のBIPは、追加の式のタイプを指定する可能性がある。この表には、使用可能なすべての式タイプがリストされている。

名称 記述 BIP
Script SCRIPT 380
Key KEY 380
Tree TREE 386

Appendix B: Script Expressionのインデックス

Script Expressionは追加のBIPで定義される。この表は使用可能なScript Expressionとそれを定義したBIPのリスト。

BIP
pk(KEY) 381
pkh(KEY) 381
sh(SCRIPT) 381
wpkh(KEY) 382
wsh(SCRIPT) 382
multi(NUM, KEY, ..., KEY) 383
sortedmulti(NUM, KEY, ..., KEY) 383
combo(KEY) 384
raw(HEX) 385
addr(ADDR) 385
tr(KEY), tr(KEY, TREE) 386

楕円曲線のスカラー倍算アルゴリズム Part 2

前回の投稿では、楕円曲線スカラー倍算のアルゴリズムとしてバイナリ法やWindow法のアルゴリズムについて、また射影座標を用いた高速化手法について解説した↓

techmedia-think.hatenablog.com

今回は、もともとスカラー倍算の高速化について調査するきっかけとなったGLV法を用いた方法について。

GLVという名前は、発明者のRobert Gallant、Robert Lambert、Scott A. Vanstoneの3名の名前から来ており、自己準同型写像を持つ楕円曲線スカラー倍算を高速化する。このアルゴリズム特許が取られていたけど、それが2020年9月に有効期限切れになったため、Bitcoin Coreでもデフォルトで有効化された↓

github.com

検証自体は、故Hal Finneyにより2011年に行われ署名検証が約25%高速化すると報告されている。また、Pieter Wuille によりlibsecp256k1にも実装されたが、↑の特許のためデフォルトで無効化されていた。

GLV法

具体的に、GLV法ではどうやってスカラー倍算を高速化するのか見ていこう。この方法の解説は、Hal Finneyのbitcointalkへの投稿が分かりやすい(Hal Finneyが参考にしたのはScott A. Vanstoneが執筆したこの本)。

ここではスカラー値をk、乗算する点をQとする。つまりk*Qを計算する。

自己準同型の性質

secp256k1曲線は、楕円曲線上の任意の点Q(x, y)について、以下を満たす自己準同型の性質を持つらしい。

 {\lambda Q = (beta * x \mod p, y)}

ここで、pは楕円曲線のパラメータの1つでベースとなる有限体の素数 {\lambda, beta}は、それぞれ

  •  {\lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72}
  •  {beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee}

実際に↑の性質があるかは↓のように検証できる。

require 'ecdsa'
require 'bitcoin'

lambda = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

# 任意の点Qを作成
key = Bitcoin::Key.generate
Q = key.to_point

# 検証用にλQを計算
lambda_q = Q.multiply_by_scalar(lambda)

# beta * x mod p を計算
field = ECDSA::Group::Secp256k1.field
x = field.mod(beta * Q.x)

# λQが(beta * x \mod p, y)と同じであるかチェック
puts lambda_q.x == x && lambda_q.y == Q.y

結果、任意の点に対してこの性質が成立してるのが確認できる。

高速化

続いて、↑の性質を利用して、スカラー値kをλを使って以下を満たすnの約半分のビット長の {k_1, k_2}に分割する(nは曲線の位数)。

 {k = k_1 + k_2 * \lambda \mod n}

つまりk*Qは、

 {kQ = (k_1 + k_2 * \lambda)Q = k_1Q + k_2 * \lambda Q }

となる。ここで {Q' = \lambda Q}を先に計算しておく、つまり {kQ = k_1Q + k_2Q'}。このQ'の計算は {\lambda Q}を単純にスカラー倍算するのではなく、↑の特性を利用して {Q(x, y)}に対して {(beta * x \mod p, y)}を計算することで、つまりmod pの乗算を1回するだけで、効率的に計算することができる。

 {k_1, k_2}の分割方法

kをそれぞれ半分のビット長の {k_1, k_2}の分解するアルゴリズムは↑の書籍の、Algorithm 3.74 Balanced length-two representation of a multiplieで紹介されている。Hal Finneyの投稿では、以下の手順で計算している。

  • a1 = 0x3086d221a7d46bcde86c90e49284eb15
  • b1 = -0xe4437ed6010e88286f547fa90abfe4c3
  • a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
  • b2 = 0x3086d221a7d46bcde86c90e49284eb15

とし(a1=b2)、

  • c1 = (b2 * k / n.to_f).round
  • c2 = (-b1 * k / n.to_f).round
  • k1 = (k - c1 * a1 - c2 * a2) % n
  • k2 = (-c1 * b1 - c2 * b2) % n

のように分割する。後は、 {k_1Q + k_2Q'}を計算する。ここで、 {k_1, k_2}は、それぞれ半分のビット長であるため、計算する際のビット長が約半分になり、計算速度が向上すると。この計算量の削減によりスカラー倍算を高速化するというのがGLV法の仕組みっぽい。

Rubyでこのアルゴリズムを書くと↓のようになる。

require 'ecdsa'
require 'bitcoin'

beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
n = ECDSA::Group::Secp256k1.order

q = Bitcoin::Key.generate.to_point

# beta * x mod n を計算
field = ECDSA::Group::Secp256k1.field
x = field.mod(beta * q.x)
# Q' = λQ
lambda_q = ECDSA::Point.new(ECDSA::Group::Secp256k1, x, q.y)

# k
k = 1 + SecureRandom.random_number(n - 1)
a1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

# kを分割
c1 = (b2 * k / n.to_f).round
c2 = (-b1 * k / n.to_f).round
k1 = (k - c1 * a1 - c2 * a2) % n
k2 = (-c1 * b1 - c2 * b2) % n

# k1Q + k2Q'を計算
glv = q.multiply_by_scalar(k1) + lambda_q.multiply_by_scalar(k2)

※ 厳密にはこのコードでは、最後のk1Q + k2Q'のmultiply_by_scalarを個別にやってるので速度は向上しない。速度向上させるためには、multiply_by_scalarの計算を1回のループで同時にやるよう修正する必要がある。

異なる楕円曲線間の離散対数の等価性の証明

MoneroからBitcoinとMoneroでAtomic Swapが利用可能になったというアナウンスが出ていて↓

https://www.getmonero.org/2021/08/20/atomic-swaps.html

そのプロトコルの一部で使用されているのが、異なる楕円曲線間の離散対数の等価性の証明。開発をしているのがCOMITというチームで、リポジトリは↓

https://github.com/comit-network/xmr-btc-swap

今回は、Atomic Swapプロトコル全体ではなく、異なる楕円曲線間の離散対数の等価性の証明方法についてみていく。

MoneroでAtomic Swapをする際の課題

チェーンをまたいで資金の交換を可能にするAtomic Swapは、いろんなブロックチェーンで可能になっているけど、MoneroでこのAtomic Swapを行うためには、次の課題がある。

  • スクリプト言語がない
    MoneroにはBitcoin Scriptのようなスクリプトが存在しないので、よくAtomic Swapで使用されているHTLCなどのロジックが利用できない。
  • 楕円曲線の違い
    スクリプトを使用せずにAtomic Swapをする方法の1つとしてAdaptor Signatureを利用したスクリプトレスな方法があり、BitcoinとLitecoin間のAtomic Swapでもこの方法が利用できる。ただ、これは2つのチェーンが同じ楕円曲線を使用している必要があり、Moneroで使用している楕円曲線(ed25519)とBitcoinで使用されている楕円曲線(secp256k1)は異なるため、Adaptor Signatureを利用するのは難しい。

今回のAtomic Swapは、後者のアプローチを可能にするもの。

異なる楕円曲線間のインターオペラビリティ

Adaptor Signatureを利用したAtomic Swapは、2つのチェーンで同じ補助ポイント(公開鍵:T = tG)を使って、その補助ポイントの離散対数(秘密鍵:t)の知識が片方のチェーンのトランザクションが公開されることで判明し、その値を使ってもう一方のチェーンのコインの支払いを可能するという仕組みで機能するようになっている。詳しくは、↓のGBEC動画参照。

goblockchain.network

ただ、これは両方のチェーンが、同じ楕円曲線を使用しているから成立する。そのためBitcoinではsecp256k1、Moneroではed25519のように異なる楕円曲線を採用しているチェーン間では成立しない。これはT = tGという1つの鍵ペアが両方のチェーンにおいて同時に成立することができないため。

この問題に対して、各チェーンの公開鍵XとYがそれぞれ異なるものながら、それが実際には同じ秘密鍵xを利用してできた公開鍵であることを、秘密鍵を明かすことなく証明できればクロースチェーンAtomic Swapができるのではないか?というのが今回BitcoinとMoneroでAtomic Swapを可能にしたアイディア。

※ さすがに秘密鍵の鍵長まで違う曲線だと使えないと思うけど。

異なる楕円曲線間の離散対数の等価性の証明

キーとなるのはsecp256k1とed25519という異なる楕円曲線間で離散対数の等価性(DLEQ)を証明するスキームで、↓のペーパーで発表されている

https://web.getmonero.org/resources/research-lab/pubs/MRL-0010.pdf

表記

詳しいプロトコルの前に、表記を定義↓

  •  {\mathbb G}:secp256k1の群
  •  {\mathbb H}:curve25519の(部分)群
  •  {G, G'}:それぞれ {\mathbb G}のジェネレーター
  •  {H, H'}:それぞれ {\mathbb H}のジェネレーター

証明プロトコル

秘密鍵をxとした場合、xGとxHが指す点は異なるが、それらの点の離散対数(x)は同じであることを証明する。ここでxの値は、両楕円曲線で取りうる秘密鍵の数値内であること。

ビットコミットメントの作成

まず、秘密鍵xをビット列に変換する、つまり  {x = \sum_{i=0}^{n} b_i 2^{i}}

続いて、n -1個(0〜n-2)のランダムなブラインドファクター {r_i} {s_i}を生成する。そしてn個(n-1)めのブラインドファクターはそれぞれ、

 {r_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} r_i 2^{i}}

 {s_{n-1} = -(2^{n-1})^{-1} \sum_{i=0}^{n-2} s_i 2^{i}}

とする。つまり、 {\sum_{i=0}^{n-1} r_i2^{i} = \sum_{i=0}^{n-1}s_i2^{i} = 0}が成立するように、それぞれ最後のブラインドファクターを選択する。

生成したブラインドファクターと秘密鍵の各ビット値を使って以下のビットコミットメントを生成する。

 {C^{G}_i = b_iG' + r_iG}(secp256k1用のコミットメント)

 {C^{H}_i = b_iH' + s_iH}(ed25519用のコミットメント)

ブラインドファクターrとsについては、↑の関係があるため、各ビットコミットメントの合算値について、 {\sum_{i=0}^{n-1}2^{i} C_i^{G} = xG'}および {\sum^{n-1}_{i=0} 2^{i}C_i^{H} = xH'}が成立する。

リング署名の作成

続いて、ビットコミットメントの各ビット値が0か1であること、そして2つの群において同じ値であることを示すリング署名を作成する。

具体的には、各 {i \in \lbrack 1, n - 1 \rbrack}について、ビット値が0か1かで以下の計算をする。

 {b_i = 0}の場合

ランダムな値 {j_i} {k_i}を選択し、以下を計算する。

 {e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

 {e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

続いて、ランダム値 {a_{0, i}} {b_{0, i}}を選択し、以下を計算する。

 {e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}

 {e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i}(C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i}(C^{H}_i - H'))}

そして以下を定義する。

 {a_{1, i} = j_i + e^{G}_{0, i} r_i}

 {b_{1, i} = k_i + e^{H}_{0, i} s_i}

 {b_i = 1}の場合

ランダムな値 {j_i} {k_i}を選択し、以下を計算する。

 {e^{G}_{0, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

 {e^{H}_{0, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, j_iG, k_iH)}

続いて、ランダム値 {a_{1, i}} {b_{1, i}}を選択し、以下を計算する。

 {e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}

 {e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i}C^{G}_i, b_{1, i}H - e^{H}_{0, i}C^{H}_i)}

そして以下を定義する。

 {a_{0, i} = j_i + e^{G}_{1, i} r_i}

 {b_{0, i} = k_i + e^{H}_{1, i} s_i}

そうして計算した以下のタプルがプルーフになる。

 {(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}

検証プロトコル

プルーフ {(xG', xH', \lbrace C^{G}_i \rbrace, \lbrace C^{H}_i \rbrace, \lbrace e^{G}_{0, i} \rbrace, \lbrace e^{H}_{0, i} \rbrace, \lbrace a_{0, i} \rbrace, \lbrace a_{1, i} \rbrace, \lbrace b_{0, i} \rbrace, \lbrace b_{1, i} \rbrace)}が与えられたら、以下の検証を行う。

まず、ビットコミットメントが両曲線の離散対数へコミットしているか以下を確認する。

 {\sum_{i=0}^{n-1} 2^{i} C^{G}_i = xG'}

 {\sum_{i=0}^{n-1} 2^{i} C^{H}_i = xH'}

続いて、各 {i \in \lbrack 1, n - 1 \rbrack}について、以下の計算を行う:

 {e^{G}_{1, i} = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}

 {e^{H}_{1, i} = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{1, i}G - e^{G}_{0, i} C^{G}_i, b_{1, i}H - e^{H}_{0, i} C^{H}_i)}

 {(e^{G}_{0, i})' = H_{\mathbb G}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}

 {(e^{H}_{0, i})' = H_{\mathbb H}(C^{G}_i, C^{H}_i, a_{0, i}G - e^{G}_{1, i} (C^{G}_i - G'), b_{0, i}H - e^{H}_{1, i} (C^{H}_i - H'))}

そして、 {(e^{G}_{0, i})'} {(e^{H}_{0, i})' }が、プルーフ {e^{G}_{0, i}} {e^{H}_{0, i} }それぞれ等しく、プルーフのデータが各群の要素であれば検証は成功する。

証明の仕組み

ぱっと↑の証明と検証をみても何をやってるのか分からないけど、基本的な仕組みはMoneroで最初に導入されていたリング署名スキーム(LSAG)↓を拡張した構造になってるっぽい。

techmedia-think.hatenablog.com

この場合のリングは2つで、ブラインドファクターを秘密鍵として、各ビットコミットメントが0か1へのコミットメントであることを確認するスキームになってるみたい。

COMITのスキーム

今回、Bitcoin - Monero間のAtomic Swapを行うソフトウェアを提供しているCOMITでは、↑のSarang Noetherのペーパーのプロトコルをそのまま使っているのではなく、簡略化して安全性を証明したものを使用してるっぽい。ただ、具体的なプロトコルの説明が見つけられなかった。

LitecoinのMWEBで非対話型トランザクションを構築するプロトコル(LIP-0004)

Litecoinでは、Extension Blockを利用してMimblewimbleを実装するMWEBの開発が行われているけど、その中でMimblewimbleのトランザクションを送信者のみが構築するプロトコルがLIP-0004として提案されている↓(まだ正式にLIPとしてマージされてる訳ではななくMWEBの開発者であるDavid Burkettのリポジトリ

https://github.com/DavidBurkett/lips/blob/master/lip-0004.mediawiki

MWのトランザクション構築

Mimblewimbleでは、基本的に送信者と受信者が協力してトランザクションを作成する必要がある。これは送信者が所有するインプットのUTXOのブラインドファクターと、受信者が新たに所有するアウトプットのブラインドファクターの値をそれぞれ秘匿した状態で、インプットのコミットメントとアウトプットのコミットメントの差分値(超過値)に対して共同で署名する必要があるためだ。詳しい仕組みについてはGBECのMimblewimble動画を参照。

非対話型にするための課題

トランザクションの構築が対話型になると、送信者と受信者の通信が必要になり、両者がオンラインになっている必要がある。LNも同様だが、Bitcoinのように送信者のみでトランザクションを構築できると利便性は上がる。そのような非対話型のトランザクションの構築にあたって課題になるのがブラインドファクターの共有。

送信者のみでトランザクションを構築するということは、新たに作られる受信者のUTXOのブラインドファクターを送信者が生成することになる。この場合、

  • 生成したブラインドファクターをどう受信者に伝えるのか?
  • 従来MWプロトコルではこのブラインドファクターが秘密鍵の代わりをしているため、送信者がこれを知るということは、そのコインは完全に受信者だけのものではなく送信者も使えてしまうことになる。

といった課題が発生する。

初期の提案

David Burkettは、Mimblewimbleを実装しているGrinでも送信者のみでトランザクションを構築する提案をしている↓

https://gist.github.com/DavidBurkett/32e33835b03f9101666690b7d6185203

仕組みとしては、送信者と受信者の鍵でECDHを実行し共有シークレットを生成し、それでブラインドファクターとコインの量を暗号化してアウトプットにセットすることで、受信者がブラインドファクターを抽出可能にする。そして別途受信者の公開鍵もアウトプットに追加し、ブラインドファクターによる検証+その公開鍵に対して有効な署名が提供されているか追加のチェックをコンセンサスに加えることで、送信者が受信者のブラインドファクターを知っている状態でも、受信者しかコインが使用できないようにするというもの。

プロトコルの詳細は、以前書いた↓の「非対話型トランザクション作成」参照

techmedia-think.hatenablog.com

初期提案の問題点

↑の提案に対して、3つの問題点が指摘されている↓

  • トランザクションがブロックに入る前に、受信者はトランザクションからブラインドファクターを抽出でき、それを変更できるため*1、資金を受け取った事実を否定することができる。
  • トランザクション・カットスルーにより、アウトプットがブロックに格納される前に削除された場合、支払いの証明をオンチェーンで行えない。
  • 署名がアウトプットやカーネルをカバーしていない場合、ランダム性の欠如によりインプットの署名を再利用することができてしまう。つまり、アリスからボブに支払いをし、その後ボブがチャーリーに支払いをした場合、アリスはreorgを発生させ、ボブ→チャーリーのトランザクションの署名を使って、ボブ→アリスのように支払いを送り返すことができる*2

LIP-0004の提案

↑の問題を解決するために、Owner Offsetという新たな要素を追加する。

もともと、Mimblewimbleプロトコルでは、コインのインフレーションが発生していないことをチェックするため、以下の検証を行っている

全アウトプットのコミットメントの合計 + 手数料*H - 全インプットのコミットメントの合計 == Kernel excess(超過値)

で、Kernel excessを公開鍵として、それに対して有効な署名を提供する(正確にはKernel excessはkernel offsetとkernel commitmentで構成される)。

↑はコインの量のインフレーションに対するチェックだが、これと似たチェックを送信者の公開鍵に対して行う。トランザクションに新たにOwner excessというフィールドを追加し(正確にはowner offsetとowner proof commitmentで構成される)

全アウトプットのsender_pubkeyの合算値 - 全インプットのreceiver_pubkeyの合算値 == Owner excess

が成立するかチェックする。Owner excessに対する有効な署名があるかチェックする。

アウトプットのsender_pubkeyというのは、受信者がECDHで共有シークレットを導出するための送信者の一時公開鍵。インプットのreceiver_pubkeyというのは、インプットが参照するUTXO(つまり、コイン送信者のUTXO)にセットされている公開鍵。なので、どちらも送信者の公開鍵である(じゃないと非対話型でトランザクション作れない)。

このチェックにより、アリス→ボブ→チャーリーの支払いにおいて、アリスがreorgを起こしてもボブ→チャーリーのトランザクションのOwner excessの署名を再利用することはできなくなる。これは、Owner excessがボブがチャーリーに送金する際の一時公開鍵も含めて計算されているため。

仕様

LIP-0004の仕様を詳細に書くと、

各アウトプットにコミットメント以外に追加のoutput_dataを追加し、それは以下の要素で構成される:

  • sender_pubkey:送信者の一時公開鍵
  • receiver_pubkey:受信者の公開鍵
  • encrypted_data:(送信者の鍵と受信者の鍵による)ECDHで生成された共有シークレットを使って暗号化したデータ(アウトプットの量とブラインドファクター)
  • sender_signature:送信者の鍵を使ったメッセージreceiver_pubkey || public_nonce || encrypted_dataへの署名

実際に拡張される項目は↓の青色の部分

https://github.com/DavidBurkett/lips/raw/master/lip-0004/tx-model.png

コンセンサスルールで、以下のチェックを追加する。

  1. output_datasender_signatureが公開鍵sender_pubkeyとメッセージreceiver_pubkey || public_nonce || encrypted_dataに対して有効な署名であること。
  2. 各インプットのinput_signatureは、それが参照するアウトプットのreceiver_pubkeyに対して有効な署名であること(メッセージはTBDみたい)
  3. owner_proofowner_signatureはブロック内のカーネルのハッシュに対し有効な署名であること。
  4. 各ブロックについて、sum(output.sender_pubkey) - sum(input.receiver_pubkey) == sum(owner_offset)*G + sum(owner_proof.commitment)が成立すること。

攻撃の可能性

↑のowner_offsetの検証が有効なのは、最新のブロックからhorizonブロックまでということなので、それを超えるreorgを発生させると攻撃の可能性が残っているとされている。reorgのコストと攻撃により得られる利益が釣り合うかが判断ポイントで、そのため大きめの資金を受け取った場合は、すぐに自分宛てに使用することで、攻撃を防御可能と。

このhorizonブロックの位置づけがよく分かってないので、また時間があるときにでも調べよう。

*1:Bitcoinなどではトランザクションを一部でも変更すると署名が無効になるが、現状のMWプロトコルではトランザクションアウトプットは署名に含まれないため変更ができてしまう

*2:Bitcoinと違って、トランザクションインプットやアウトプットが署名対象に含まれていない、かつ送信者が受信者のブラインドファクターを知っているため、アウトプットに受信者の公開鍵をセットしたとしても、このような攻撃が可能になる

LN Offer

LN Offerは、ノードがLNを介してインボイスを要求、受信できるようにするプロトコル拡張機能の1つで、BOLTにもBOLT 12として提案されている↓

https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md

http://bolt12.org/

LNの支払いは、受信者がBOLT 11で定義されているインボイスを発行し、それをQRコードコードなどで読み取って送信者がLN支払いをするというのが一般的で、実際に送信者と受信者がインタラクティブに通信することはない。

LN Offerの機能

LN Offerはインボイスの前段階の処理フェーズで、Offerに基づいてインボイスの要求や発行をするための情報を提供する。

Offerを利用したフロー

Offerを利用した支払いのフローは以下のようになる:

ユーザー→サービス提供者へ支払いをする場合
  1. サービス提供者がWebサイトやQRコードでOfferを公開する。
  2. ユーザーは、LNを介して一意のインボイスを要求する。
  3. サービス提供者は2に対してインボイスを返信する。
  4. ユーザーは送られたインボイスに従って支払いをする。
ユーザーがサービス提供者から支払いを受ける場合

ATMや払い戻しなどでサービス提供者がユーザーへ支払いするフローは:

  1. サービス提供者がユーザー固有のOfferを、WebサイトやQRコードで金額と一緒に提供する。
  2. ユーザーはOfferの金額のインボイスを送信する。
  3. サービス提供者は、2のインボイスに従って支払いをする。

インボイスは1回しか使えないけど*1、Offerの場合同じものを何度でも利用可能。寄付なんかを受け付ける場合も、サイトにOfferのQRコードだけ貼っておけば、寄付したいユーザーがOfferを読んで、インボイスを要求し、発行されたインボイスに対して支払いをする。

メッセージの通信

LN Offerに対してインボイスの要求や発行する際のメッセージの送信には、既存のオニオンルーティングを使ったLNのメッセージ送信の仕組みがそのまま使われる。アプローチは、実際に支払いをしない偽の支払いを送信するLNを使ったチャットアプリとかと似てる。

bootstrap.bolt12.orgで公開されているサンプルを見ると、一番シンプルなOfferのデータは↓

{
  description: "Offer by rusty's node",
  node_id: "4b9a1fa8e006f1e3937f65f66c408e6da8e1ca728ea43222a7381df1cc449605",
  offer_id: "28522b52ac39fa518ce3a5b3e4a9a96372487e78ba5eb1540ec4d9f02ca82718",
  signature: "f4c5b54263766d8aa86dcb28b9973449cf995ef58ce8a96430bbb5b516460f465e9794b6842f1260b400966a3eb7e1557998f858aeb5bce1459ebc984fa3cabb",
  type: "bolt12 offer",
  valid: true
}

Offerを受けつるnode_idが記載されているので、ここにインボイスの要求/発行をするメッセージをLNのネットワークを介して送信することになるっぽい。

bech32でエンコードしたデータも記載されてる↓けど、どうもQRコード自体がチェックサム機能を持っているから、bech32のチェックサムは省略されてるっぽい(bech32使う必要ないよね。。)。

lno1pg257enxv4ezqcneype82um50ynhxgrwdajx283qfwdpl28qqmc78ymlvhmxcsywdk5wrjnj36jryg488qwlrnzyjczlqs85ck65ycmkdk92smwt9zuewdzfe7v4aavvaz5kgv9mkk63v3s0ge0f099kssh3yc95qztx504hu92hnx8ctzhtt08pgk0texz0509tk
ブラインドパス

↑のOfferにはnode_idが記載されているけど、Offerとインボイス両方についてノードIDを明らかにすることなく、つまりメッセージの送信先を知ることなく、Offerへのリクエスト/レスポンスを返すことも可能。

支払いの証明

通常のLN支払いの支払いの証明は、インボイスに含まれているpayment_hashのプリイメージを示すこと。ただ、この場合、プリイメージさえ知っていれば誰でも支払いをしたと主張できてしまう。

この問題に対処するため、Offerに対してインボイスを要求する場合、送信者は公開鍵payer_keyを、リクエストのTLVフィールドに含める。そして、発行されるインボイスのTLVデータにもこのデータが含まれ、これによりインボイスの所有を証明する。※ 払い戻しの時などに、実際の支払者であることを証明するのに使われる。

また、BOLT 11インボイスの場合、署名がインボイス全体適用されるため、インボイスの全データを公開しないとインボイスを証明することはできなかった。BOLT 12では、各TLVフィールドのデータでマークルツリーを構成し、そのルートハッシュに対して署名が計算される(Taprootと同様の署名スキームを実装している)。このため、支払いに関する情報をすべて公開することなく支払いの証明が可能になる。

※ また署名アルゴリズムはSchnorr署名を採用しており、BIP340と同様、公開鍵はx座標のみをエンコードした32バイトの公開鍵が採用されている。

デプロイ状況

現在BOLT 12はまだドラフトで、c-lightningが実験的にサポートしている状況。

また↑のオニオンメッセージについても、現在まだドラフトで、現状のc-lightningは、オニオンメッセージを送信する際は、直接接続をしてるっぽいので、Torなどを使ってないとプライバシー上のリスクがある状態。

Offerが利用可能になると、OfferのQRコードを公開しておけばよく(WebサイトでもTwitterでも)、後はLNノードにインボイス要求が来たら反応するということが可能になるので、インボイス生成用にWebサーバーとかを別途用意するみたいなことしなくてもよくなる。

ただ、インボイスの要求や配信はオニオンメッセージを介して送信されるので、対象ノードまでの経路がなければ送れないだろうし、これらのメッセージを中継するノードの帯域幅やリソースは消費されることになるんじゃないかな。

*1:使用済みのインボイスは、ネットワーク上でペイメントシークレットが既知のものになっているので、同じシークレットを使用した支払いは安全ではない