Develop with pleasure!

福岡でCloudとかBlockchainとか。

Ed25519で決定論的な鍵導出をサポートするBIP32-Ed25519

Bitcoinのウォレットなどが、単一のマスターシードから多数の鍵ペアを決定論的に導出する仕様を定義したのがBIP-32↓

techmedia-think.hatenablog.com

これは、Bitcoinが採用している楕円曲線secp256k1とECDSAを前提に作られた仕様になる。

これに対して、EdDSA(Edwards-Curveデジタル署名アルゴリズム)の一種であるEd25519においても、BIP32と同様の決定論的な鍵導出を可能にする提案の1つがBIP32-Ed25519↓

https://raw.githubusercontent.com/LedgerHQ/orakolo/master/papers/Ed25519_BIP%20Final.pdf

Ed25519

Ed25519は鍵の導出方法がsecp256k1と異なり、これがBIP-32をそのまま利用できない原因でもある。

鍵生成

Ed25519は以下の手順で秘密鍵と公開鍵を生成する。

秘密鍵は、32バイトのランダム値で、これをxとする。公開鍵はこの秘密鍵を使って以下のように計算される。Gを曲線のベースポイント、nを曲線の位数とする。

  1. SHA-512を使って秘密鍵をハッシュし、その値を {k = H_{512}(x)}とする。
  2. kの下位32バイトを {k_L}とし、上位32バイトを {k_R}とする。公開鍵の導出に使用するのは、 {k_L}のみ。
  3.  {k_L}のデータに対して以下を行う。
    • 先頭バイトの下位3 bitをクリアする。
    • 最終バイトの最上位bitをクリアする。
    • 最終バイトの最上位から2つめのbitをセットする。
  4. 3のデータをリトルエンディアンで整数として解釈してスカラー値sとする。
  5. Gに対してスカラー値sをスカラー倍算する(sG)。
  6. 公開鍵Pは点sGをエンコードしたもの。sGのy座標を32バイトのリトルエンディアンのバイト列としてエンコードする。最終バイトの最上位bitは常に0で、x座標の最下位bitを最終バイトの最上位bitにコピーする。

こうして生成されたのが公開鍵になる。

秘密鍵からSHA-512で64バイトのハッシュしたけど、半分の {k_R}使ってないじゃん?って思うけど、これは署名生成の際に使用される。

署名生成

メッセージMと公開鍵Pに対する署名は以下のように作成される。Schnorr署名の一種なので、基本的にはSchnorr署名の計算。

  1.  {H_{512}(k_R || M)}を計算し、結果をリトルエンディアンの整数rとして解釈する(なお、 { r = r \mod n})。
  2. R = rGを計算する。
  3.  {h = H_{512}(R || P ||M)}を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
  4.  {s = (r + h \cdot k_L) \mod n}を計算する。
  5. R || sが署名データ

Schnorr署名と違うのは、Schnorrがnonceの選択に乱数を使うのに対し、Ed25519は、 {k_L}とメッセージMのハッシュからnonceを生成している。そのため署名生成に乱数を必要としない。

署名検証

R || sおよび、P、Mが与えられた検証者は、以下の検証を行うことで署名の有効性をチェックする。

  1.  {h = H_{512}(R || P ||M)}を計算し、64バイトのダイジェストをリトルエンディアンの整数として解釈する。
  2.  {8sG = 8R + 8h \cdot A}が成立するか検証する(Ed25519のco-factorが8であるため)。

BIP32採用の問題

secp256k1のECDSAの場合、秘密鍵xに対応する公開鍵は、単純にベースポイントに対してスカラー倍算したP = xG。公開鍵Pに対してQ = yGを加算した公開鍵Z = P + Qを導出すると、Zに対応する秘密鍵は x + yになるという特性がある。

そのため、公開鍵から新しい公開鍵を導出することができ、元の公開鍵に対応する秘密鍵を知っていれば、導出した公開鍵の秘密鍵を知ることができる。なので、オンラインのECサイトには公開鍵だけ置いといて、支払いの度に新しい支払いアドレスを導出し、秘密鍵はオフラインで管理し、必要な場合に対象の秘密鍵を計算して利用するといったユースケースが可能になる。

これに対し、Ed25519の場合、公開鍵は秘密鍵のSHA-512ハッシュ値の下位32バイトを細工して出来た値をスカラー倍算した値になるため、↑のような特性がない。これがEd25519にBIP-32をそのまま採用できない理由。

BIP32-Ed25519

ただ、Bitcoinみたいに1人のユーザーやシステムが多数の公開鍵を使用するようなケースなど、同じシードから鍵やIDを多数生成したい場合、BIP-32のような決定論的な鍵導出スキームの需要がある。Ed25519でもBIP-32を少し変更することで、これに対応したのがBIP32-Ed25519。

ルート鍵

まず、ランダムに選択した32バイトのマスターシークレットをxとする。

  1. SHA-512を使ってマスターシークレットをハッシュし、その値を {k = H_{512}(x)}とする。
  2. kの下位32バイトを {k_L}とし、上位32バイトを {k_R}とする。 {k_L}の最終バイトの最上位3つめのbitがゼロでない場合、マスターシークレットを廃棄してやり直す。
  3.  {k_L}のデータに対して以下を行う。
    • 先頭バイトの下位3 bitをクリアする。
    • 最終バイトの最上位bitをクリアする。
    • 最終バイトの最上位から2つめのbitをセットする。
  4. 得られた {(k_L, k_R)}のペアを拡張ルート秘密鍵とし、 {P = k_LG}をルート公開鍵とする。

鍵の導出手順から分かるように、拡張ルート秘密鍵とルート公開鍵は、Ed25519と鍵としても使えるもの。

そしてBIP-32のルートチェーンコードを {c = H_{256}(0x01 || k)}とする。

子鍵

ルート鍵は、 {2^{32}}個の子鍵(インデックスi \in 0..{2^{32} - 1})を持つ。

秘密鍵の導出

親のチェーンコードを {c^{P}}、拡張秘密鍵 {k^{P} = (k^{P}_L, k^{P}_R)}、公開鍵を {P^{P}}とした場合、i番目の拡張秘密鍵は以下のように計算される。

  1. インデックスに応じて、チェーンコードをHMACの鍵として、以下の計算を行う:
    •  {i \lt 2^{31}}の場合
       {Z = HMAC(0x02 || P^{P} || i, c^{P})}
    •  {i \ge 2^{31}}の場合
       {Z = HMAC(0x00 || k^{P} || i, c^{P})}
  2. Zの左28バイトを {Z_L}、右32バイトを {Z_R}とする。
  3. 子の拡張秘密鍵 {k_L = 8Z_L + k^{P}_L}とし、 {k_R = (Z_R + k_R^{P}) \mod 2^{256}}とする。 {k_L}が位数nで割り切れる場合、その子は破棄する。
  4. 子のチェーンコードは、
    •  {i \lt 2^{31}}の場合
       {c_i = HMAC_{512}(0x03 || P^{P} ||i, c^{P})}
    •  {i \ge 2^{31}}の場合
       {c_i = HMAC(0x01 || k^{P} || i, c^{P})}

そして、対応する子どもの公開鍵は {P_i = k_LG}

 {Z_L}だけ28バイトにトリムしているのは、子の {k_L}の最終バイトの最上位2 bitめが常に1であることを保証するためらしい。

子公開鍵の導出
  1. ↑の子秘密鍵の場合と同じようにZを計算する。そのため、BIP32と同様、 {i \ge 2^{31}}の強化導出の場合、親の拡張秘密鍵を知らないと導出できない。
  2.  {P_i = P^{P} + 8Z_LG}を計算する。
  3. ↑の子秘密鍵と同様に子のチェーンコードを算出する。

↑からBIP32-Ed25519では、本来の鍵xではなく、拡張秘密鍵 {k = (k_L, k_R)}を使って鍵導出をしている。公開鍵を親の {k_L}に対して加算処理をすることで、親密鍵→子秘密鍵(子公開鍵)、親公開鍵→子公開鍵(親の公開鍵は {k_LG}で既知であるため)の導出をできるようにしていることが分かる。

そして、すべての拡張鍵がEdDSAの仕様で定義されるように特定のビットのセット、クリアが行われるようになってるっぽい。

SLIP-0010

BIP32-Ed25519とは別に、異なる曲線で異なる秘密鍵決定論的に導出する仕様がSLIP-0010として提案されていて、Ed25519も対象に含まれている↓

https://github.com/satoshilabs/slips/blob/master/slip-0010.md

ただ、この仕様では、Ed25519については親公開鍵→子公開鍵の導出はサポートしていない。

Merkle Sum Sparse Merkle Tree

先日、Olaoluwa Osuntokunが発表したTaprootを利用したアセットオーバーレイプロトコルTaro↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020196.html

今回はその構成要素の1つであるMerkle Sum Sparse Merkle Tree(MS-SMT)の仕様についてみてみる↓

https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-ms-smt.mediawiki

MS-SMTは、Sparse Merkle TreeとMerkle Sum Treeを組み合わせたマークルツリーの一種。これらそれぞれのツリー構造自体は、Plasmaなど既存のプロダクトで既に採用されてる仕組みでもある。

Sparse Merkle Tree

Sparse Merkle Tree(SMT)というのは、key-valueのマップをマークルツリーにエンコードしたマークルツリーの一種。

通常のマークルツリーとの違いは、

  • ツリーのリーフノードの値はkey-valueマップのエントリー値になっており、そしてキーに対応するエントリー(ツリーのリーフノード)がどこにあるかは、キーをビットに展開し、ツリーのルートを0としてその左の子ノードを0、右の子ノードを1として、ツリーを上から下にキーのビットに対してリーフノードまで降りていくことで特定することができる。
  • キーに対応するエントリーが存在しない場合は、空の値がリーフノードにセットされる。空のリーフノードにはTaroの場合H(nil || nil || 0)がセットされる。

Taroではキーの値はSHA256値なので、キーは256 bitの範囲の値になる。このキースペースを持つツリーの深さは256で、 {2^{256}}個のリーフノードを持つ。

↑の仕様から、Sparse Merkle Treeにはマークルツリーにはない以下の特性を持つ。

  • キーから、対応するエントリーがツリー内のどの位置にあるかが分かる。
  • 効率的に非包含証明を作成できる。
    エントリーの値が空であることと、その空の値までのマークルプルーフを提供することで、あるエントリーがツリー内に存在しないことを証明する非包含証明を提供できる。
    通常のマークルツリーで、ある要素が含まれていなことを証明しようとすると、ツリーの全てのリーフを公開する必要があり効率的ではない。

ビットマップを利用した最適化

非包含証明は、キーに対応した空のリーフノードが存在することを証明するため、空のリーフノードまでの兄弟ノードのリストをマークルプルーフとして提供する。しかし、空のリーフノードのハッシュ値は既知のデータであり(H(nil || nil || 0)のように)、その空ノード同士の親ノードのハッシュ値も事前に計算可能な既知の値になるため、マークルプルーフから

  • 空ノードのノード値を除外し
  • 代わりに経路のどのノードが空でないかを示すビットマップを追加する

ことで、マークルプルーフのデータスペースを節約することができる。

Merkle-Sum Tree

Merkle Sum Sparse Merkle Treeのもう1つの特性がMerkle-Sum。

通常、マークルツリーのリーフノードの値は要素のハッシュ値で、親ノードは2つの子ノードのハッシュ値を連結してそれをハッシュした値を自身のハッシュ値として、これをルートまで繰り返すことでルートハッシュを得る。

Merkle-Sum Treeというのは、この時単に要素のみにコミットするのではなく、その要素の属性の合計にもコミットするタイプのマークルツリー。Taroでは、8バイトの合計値(sum)を持つ。

例えば要素Aが100、要素Bが50の2つのリーフがあるとすると、その親ノードのハッシュ値は、

ParentAB = SHA256(H(A) || H(B) || (100 + 50))

さらにその親ノードABCDがある場合、同様の計算が行われ、以下のようなツリーになる。

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

MS-SMT

MS-SMTは、↑のSparse Merkle TreeとMerkle-Sum Treeを組み合わせたツリー。

Taproでは、↑のMS-SMTツリーを使ってアセットツリーを構成し、そのルートハッシュをコミットメントとしてTaprootのスクリプトツリーに配置するようになってる*1

そんなアセットを保持したTaprootアウトプットを転送する際に、

  • アセットの以前の所有者がアセットツリー内でアセットにコミットしていないこと
  • 新しいアセットが作成されていないこと(アセットのインフレーションが発生していないこと)

を証明するため、非包含証明と、Merkle-Sumの特性から非インフレーションの証明にMS-SMTを利用するっぽい。

Taroのこのあたりの仕様については、また別途。

*1:そのため、オンチェーン上でアセットツリーやアセットの情報が直接的に記録されることはない。この辺りのアプローチはRGBとかも同じ

1つのUTXOの所有権を複数人でシェアするCoinPool

Lightning Networkなどの現在主流のペイメントチャネルプロトコルはいずれも2人で1つのUTXOの所有権を管理するプロトコルだけど、N(N > 2)人で1つのUTXOの所有権を管理できるようにするプロトコルがCoinPoolで、少し前にホワイトペーパーが公開された↓ので、内容を見ていこう。

https://coinpool.dev/v0.1.pdf

CoinPool

CoinPoolは、LNなどのプロトコルや運用から得られた教訓をもとに、UTXOの所有権を共有するこで新しいスケーラビリティ構造を提案するプロトコルになる。CoinPoolではN人のプール参加者のコインを1つのUTXO(プール)で管理する。つまりN人が1つのUTXOの所有権を共有することになる。そしてこのプールについて、以下の基本的な機能を提供する。

  • 参加者はプール内で、オフチェーンで資金の転送ができる(プール内の資金の配分を変更できる)。
  • 参加者は、他の参加者の承諾なしに、いつでもプールから抜けることができる。

そして、高度な機能として、ペイメントチャネルなどのコントラクトでの使用や、LNや他のプールのユーザーとの取引に使用することができる。

セットアップ

N人の参加者はUTXOを持ち寄って、CoinPoolをセットアップする。まずN人の参加者はキーキャンセルができない方法を使って、それぞれの公開鍵(N個の公開鍵)を加算して集約公開鍵Pを作成する。セットアップでは、以下の3種類のトランザクションを作成する。

f:id:techmedia-think:20220320160335p:plain
CoinPoolのセットアップ

Setup Tx

各メンバーのUTXOをインプットとして、単一のUTXOに参加者の資金をロックするトランザクション。このアウトプットをPre-CoinPoolアウトプットと呼ぶ。Pre-CoinPoolアウトプットは、参加者全員の鍵から計算した集約公開鍵Pにロックされる。

Update Tx

プールの状態を表すトランザクションで、Setup TxのPre-CoinPoolアウトプットをインプットとし、アウトプットは以下の支払いパスを持つTaprootアウトプット(CoinPoolアウトプット)になる。

  • Key-Path: 参加者全員の集約公開鍵P
  • Script-Path: 以下のアンロック条件を持つ。
    • 参加者全員が協力してUpdate Txを更新する際に使用する条件
    • N個の各参加者毎の引き出し条件
Withdraw Tx

これは各参加者が、他の参加者の許諾なしにプールを抜ける際に使用するトランザクションで、各参加者の人数分作られる。

Update TxのCoinPoolアウトプットをインプットとし、以下の2つのアウトプットを持つ。

  • CoinPoolから抜ける退出者の金額をロックしたアウトプット
  • 退出者を除いた残りのCoinPoolの残高をロックしたアウトプット
    • このアウトプットのscriptPubkeyは、Update TxのCoinPoolアウトプットからCoinPoolから抜ける参加者の条件を削除したもの。

途中で資金がロックされることがないように、署名はWithdraw->Update->Setupの順に行われる。

実際のTx構成の例は、以下で公開されてる

gist.github.com

プールの更新

プール内のユーザー間でコインを送金する場合は、新しいUpdate Txと送金後のバランスを反映したWithdraw Txのセットを作成することでオフチェーンで送金が完了する。

古い状態のUpdate Txがブロードキャストされるようなことがあれば、ブロードキャストしたユーザーがWithdraw Txで引き出す前に(タイムロックされてる間に)、eltooの仕組みにより最新のUpdate Txに置き換える。

プールからの引き出し

プール参加者は、他の参加者の許諾なしにいつでもプールから退出(引き出し)できる。

退出する参加者は、

  1. 最新のUpdate Txをブロードキャストする。
  2. 続いて、自身のWithdraw Txをブロードキャストする。
    • ただし、Update TxのCoinPoolのUTXOをWithdraw Txで使用する際はタイムロックが付与されているので、Update Txがブロックに格納されてから一定期間待つ必要がある。
    • タイムロックが経過したら他の参加者が署名済みの自身のWithdraw Txに自身の署名を追加してブロードキャストする。

この結果、退出する参加者のプールの残高は、Withdraw TxのUTXOとして利用可能になり、残りのプール参加者には同様にプールから退出するかプールに留まるかの選択肢がある。

  • プールから退出する場合は、このWithdraw TxのCoinPool UTXOをインプットとしてプールから抜ける。
  • 継続する場合は、Snapshot Txを作成&ブロードキャストし、これまで事前署名したWithdraw Txの署名を無効にする。Snapshot TxはWithdraw TxのCoinPool UTXOをインプットとし、残ったプールメンバーの集約公開鍵にコインをロックするトランザクションでSetup Txと似たトランザクションになる。当然ながら、Snapshot Txに署名する前に、後続となるUpdate TxおよびWithdraw Txのセットを作成し先に署名しておく必要がある。

Bitcoinに必要な機能追加

CoinPoolプロトコルは、現在のBitcoinプロトコルでは実装ができず、Bitcoinに以下の機能を追加する必要がある。

OP_MERKLESUB

OI_MERKLESUBは、Update TxおよびWithdraw TxのCoin Poolアウトプットの各ユーザーの引き出し条件のスクリプトに使われる。これは、プールからのユーザーの退出にあたって、

  • プールから退出するユーザーの引き出しに使用する条件ブランチが新しいCoinPoolアウトプットのTapScriptのツリーから削除されている。
  • プールから退出するユーザーの公開鍵が新しいCoinPoolアウトプット集約公開鍵から削除されている。

ことを保証する必要があり、その検証をするために新たに追加されるopcodeになる。このopcodeの仕様案は↓

https://github.com/ariard/bips/blob/coinpool-bips/bip-merklesub.mediawiki

SIGHASH_GROUP

Withdraw Txの2つのアウトプットの量が、それぞれ

  • 元々プール参加者全員が合意した退出ユーザーの残高であること
  • 残りのプールのCoinPoolアウトプット量はプールの量から退出者の残高を差し引いた額と等しいこと

を保証する必要がある。これを事前署名時にコミットするために新しいSIGHASHタイプであるSIGHASH_GROUPが必要になる。この具体的な仕様は↓

https://github.com/ariard/bips/blob/coinpool-bips/bip-group.mediawiki

SIGHASH_ANYPREVOUT

Update Txの更新にeltooスタイルで行うため、SIGHASH_ANYPREVOUTが必要になる。

また、Taprootアウトプットとして構成されるCoinPoolアウトプットのTapscriptでは、ツリーのリーフブランチに各ユーザーの引き出しが可能な条件が設定されている。このリーフを2社間のペイメントチャネルで利用可能にすることで、CoinPoolのスケーラビリティは大きく向上する。ただ、CoinPoolのステート(Update Tx)は随時更新されるため、このリーフレベルのペイメントチャネルを有効にするためには、特定のステートにロックされることがないよう、SIGHASH_ANYPREVOUTによりペイメントチャネルの参照先のUpdate Txを切り替えられる必要がある。

オフチェーンプロトコルのプライバシーを向上させるオンチェーンウォレットのポリシーを定義したBIP-326

最近オフチェーンプロトコルのプライバシーを向上させるために、オンチェーンウォレットで実装が推奨されるポリシーが、BIP-326として定義された↓

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

Informational BIPなのでコンセンサスに影響するものではなく、各ウォレットへの対応が期待される。

プライバシーの向上というのは、現状のLightningチャネルなどのオフチェーン・コントラクトでは、nLockTimeやnSequenceなどのタイムロック機能を使ったトランザクションを構築しており、これらの値が設定されたトランザクションがオンチェーン上に現れると、それがオフチェーン・コントラクトであることを識別できる可能性がある。

これに対して、通常のオンチェーンウォレットでも支払いをする際に、これらのnLockTimeやnSequenceの値を設定することで、オフチェーン・コントラクトの識別をしにくくしようというもの。

また、現時点で脅威ではないけど、将来ブロック報酬の割合が少なくなり手数料収入がメインとなった場合に、マイナーにとって価値のある(手数料の高い)過去のトランザクションをマイニングするような攻撃が考えられる。今回のポリシーの適用による副次的な効果として、このようなフィー・スナイピング攻撃を防止することができる。

具体的には、オンチェーンウォレットで支払いをするトランザクションを作成する際に、現在の最新ブロックの次のブロック以降でマイニング可能になるようnLockTimeもしくはnSequenceの値を設定するという内容。どちらを使用するかは50%の確率で決める。

nLockTimeの場合は、単純に次のブロックのブロック高を設定すればいいけど、nSequenceの場合は、インプットで使用するUTXOの承認数+1をインプットのnSequenceの値にセットする。この辺りの具体的な仕組みは、以前GBEC動画でも解説してる↓

goblockchain.network

仕様の詳細については、BIP参照。以下はBIPの意訳。

概要

このドキュメントは、BIP341 Taprootを使用する、あるタイプのウォレットの動作を提案するものであり、Coin SwapやLightning、Discrete Log ContranctsなどのPoint Time Locked Contract(PTLC)を利用するオフチェーンプロトコルに、より大きな匿名セットを提供する。

動機

最近、BitcoinにTaprootが追加され、ウォレットソフトウェアがTaprootウォレットを実装しようとしいる。ここですぐに行動すれば、オフチェーンプロトコルのプライバシーを改善できるユニークな位置にいる。

Taprootは、Hash Time Locked Contract(HTLC)に代わるよりプライベートなものとしてPoint Time Locked Contract(PTLC)を可能にする。(例えばLightningチャネルなどの)オフチェーンコントラクトが、HTLCの代わりにPTLCを使って閉じられた場合、ブロックチェーンにはハッシュ値とプリイメージの代わりに通常のTaprootのスクリプトが現れるだけになる。しかし、コントラクトがタイムロックのパスを使って閉じられた場合、ブロックチェーン上のトランザクションでは、OP_CHECKSEQUENCEVERIFYnSequence値を参照するが、どちらも現在あまり一般的ではなく、クロージングトランザクションが特別で珍しいものとしてマークされることになる。

このBIPでは、Bitcoin Coreのようなオンチェーンウォレットも、BIP68のように、TaprootトランザクションでnSequenceフィールドをセットすることで、オフチェーンプロトコルのプライバシーとファンジビリティを改善することを提案している。これは、通常のnLocktimeのアンチ・フィー・スナイピング保護の代わりになる。その結果、ブロックチェーンの監視者が、nSequence値を持つTaprootの支払いを確認した場合、これは、ウォレットからの通常の支払いか、タイムロックが使われたオフチェーンの決済トランザクションのどちらかである。この2つのケースは区別がつかず、ビットコインのプライバシーとファンジビリティを大きく向上させることができる。コミュニティとウォレット開発者は、ウォレットへのTaproot自体の採用と同時に、nSequenceトランザクションの匿名セットが構築され始めるように、この実装を今すぐ行うべきだ。

背景

フィー・スナイピング

フィー・スナイピングは、低インフレの未来において、ビットコインのマイニングに悪いインセンティブが働くと仮定した場合の結果である。大規模なマイナーにとっては、ベストブロックとmempoolのトランザクションの価値は、ベストブロックをオーファンにするために意図的に2つのブロックをマイニングしようとするコストによって上回る可能性がある。しかし、nLocktimeやnSequenceを使ったアンチ・フィー・スナイピングの保護があれば、悪意あるマイナーは最初のブロックに格納可能なトランザクションを使い果たしてしまう。つまり2つめのブロックに格納する必要がでてくる。アンチ・フィー・スナイピングは、ブロックチェーンを前進させるインセンティブを高める。

nLocktimeフィールドは、現在このように使用されている。Bitcoin CoreとElectrumで実装されており、最近の全トランザクションの約20%で採用されている。

絶対的なロックタイムと相対的なロックタイム

nLocktimeは絶対的なロックタイムで、あるブロック高またはUNIX時間後にのみトランザクションがマイニングできるようにするものである。これが広く採用されることで、オフチェーンプロトコルに優れた匿名性がもたらされた可能性がある。残念ながらこれらのプロトコルでは、相対的なロックタイムも一般的に使用されている。これはクロージングトランザクションが承認された場合にのみカウントダウンクロックが動きだすため、(例えばLightingのペイメントチャネルやCoinSwapなどにょうに)コントラクトを無限に開いたままにすることができるからだ。

絶対的なロックタイムもまだ使用されているため、nLockTimeを使用し続ける必要があるが、nSequenceもよく使用される。

トランザクションのピン留め

トランザクションのピン留めは、帯域はCPU、メモリを消費する攻撃に対するノードの保護を悪用して、手数料の引き上げを法外に高くする手法だ。これは、マルチパーティコントラクトプロトコル(Lightning NetworkやCoinSwapなど)において、手数料管理を難しくする可能性がある。この問題を解決するいつの可能な方法は、すべての支払い条件に1ブロックの相対タイムロック(1 OP_CSV)を含め、未承認のUTXOの使用を不可能にすることだ。このような1ブロック分のタイムロックは、nSequenceの値を1にして作成することもできる。Bitcoinの多くのオンチェーントランザクションは、わずか1〜2ブロック前に作成されたインプットを使用している。このBIPに従えば、nSequence = 1のそのようなトランザクションは、トランザクションのピン留めを無効にするオフチェーントランザクショントラフィックをカバーする。

仕様

ウォレットがBIP341のTaprootで保護されたUTXOを使用するトランザクションを作成する場合、現在のブロックではなく先頭の次のブロックでのみマイニングされるようにすることで、フィー・スナイピングを阻止するためにnLockTimeの値またはnSequenceの値のいずれかを設定する必要がある。このBIPは、nLockTimeを使用する確率を50%、nSequenceを使用する確率を50%と提案している。nSequenceを設定する場合、トランザクションに複数のインプットがある場合は、そのうち少なくとも1つのインプットに適用する必要がある。オンチェーンウォレットはインプットをランダムに選択することを推奨する。

ウォレットはまた、nLockTimeおよびnSequenceの値をさらに後ろに設定する第2のランダム条件を持つべきで、そうすれば何らかの理由で遅延するトランザクション(例えば、高レイテンシーのミックスネットなど)は、より良いプライバシーを持つことができる。既存の動作は、10%の確率で0〜99の間の乱数を選択し、それを現在のブロック高から減算する。例として、参考文献にリンクされているBitcoin CoreやElectrumのソースコードを参照してほしい。

nSequenceは、ブロックの距離に対して65535までしかエンコードできないため、使用されるUTXOに65535以上の承認がある場合、ウォレットはnLockTimeを使用する必要がある。

擬似コード

def apply_anti_fee_sniping_fields(transaction, rbf_set):
    # bip68 requires v=2
    transaction.version = 2
    # Initialize all nsequence to indicate the requested RBF state
    # nsequence can not be 2**32 - 1 in order for nlocktime to take effect
    for input in transaction.inputs:
        if rbf_set:
            input.nsequence = 2**32 - 3
        else:
            input.nsequence = 2**32 - 2
    # always set nlocktime if any of the transaction inputs have more
    # confirmations than 65535 or are not taproot inputs, or have
    # unconfirmed inputs
    # otherwise choose either nlocktime or nsequence with 50% probability
    if not rbf_set || any(map(lambda input: input.confirmations() > 65535
            || !input.is_taproot() || input.confirmations() == 0,
            transaction.inputs)) || randint(2) == 0:
        transaction.nlocktime = blockchain.height()
        if randint(10) == 0:
            transaction.nlocktime = max(0, transaction.nlocktime
            - randint(0, 99))
        # nsequence must be set in order for nlocktime to take effect
    else:
        transaction.nlocktime = 0
        input_index = randint(len(transaction.inputs))
        transaction.inputs[input_index].nsequence = transaction.inputs\
            [input_index].confirmations()
        if randint(10) == 0:
            transaction.inputs[input_index].nsequence = max(1,
                transaction.inputs[input_index].nsequence - randint(0, 99))

互換性

このBIPは、コンセンサスの変更を必要としない。ウォレットが一方的に、そして徐々に採用することができる。しかし、より高いプライバシーのためには、ソフトウェアができるだけ早くそれを採用することが望ましいだろう。理想的には開発者がTaprootウォレットを実行する過程で、Taprootが使われた始めた時に、すでにnSequenceのコードが含まれているようにすること。

すべてのウォレットソフトウェアは、既にUTXOの承認回数を記録しているので、nSequneceフィールドを設定するのに必要な情報は既に得られている。

SMART Health CardのVerifiable Credential

SMART Health Cardは、COVID-19のワクチン接種や検査結果を検証可能な方法で提示できることを直近の目標としたヘルスカードのフレームワーク。長期的には予防接種やその他の健康情報なんかもサポートする計画らしい。これらの証明について、組織や国を超えて機能できるよう国際的な標準の作成と分散型のインフラの設計を目標にしている。

↓がこのフレームワークのコンセプトモデルで、

https://i.imgur.com/T8RHjlJ.png

以下のロールで構成される:

  • 接種証明や検査結果をVerifiable Credentialとして発行するIssuer
  • 発行されたVCのHolder
  • HolderからVCを受け取り正しく署名されているか検証するVerifier

↑の証明スキームにVCが利用されている。そしてデジタル庁が公開した新型コロナワクチン接種証明書アプリもこのSMART Health Cardのスキームに則ってVCを発行しているみたい↓

idmlab.eidentity.jp

ちょうど、こないだ3回めのワクチン接種をしたので、そこで発行されたVCを確認しながらSMART Health Cardの仕組みを見てみる。

SMART Health Cardの内容を確認

新型コロナワクチン接種証明書アプリで接種証明のQRコードを読み取ると、shc:/から始まり数値が続くデータになっている。shcというのは、このデータがSMART Health Cardのデータであることを示しており、スマホにこのスキームに対応するアプリが入っていたらおそらく反応するんだろう。

QRコードのデータフォーマット

shc:/以降の数値のデータがヘルスカードの実体で、これはJSON Web Signature (JWS)のデータになる。ただ、QRコードに効率的にJWSのデータを載せるため、数値モードでエンコードされており、まずはこれをデコードする必要がある。

SMART Health Card仕様では、JWSのデータを以下の手順でQRコードエンコードしている:

  1. チャンク化:1つのQRコードに記述可能なJWSは最大1195文字まで。これを超えるデータをエンコードする場合、長さ1191以下のチャンクに分割する。(チャンク分割がある場合)チャンクの総数をN、現在のチャンクのインデックスをCとした場合、shc:/の後に以下のデータを付与する。
    1. Cの10進表現
    2. セパレーター/
    3. Nの10進表現
    4. セパレーター/
  2. JWSの各文字を0〜9で構成される数値にエンコードする。JWSの各文字は、Ord(文字) - 45を計算して数値にエンコードする。45という数値は、JWSの有効な文字の内、文字コードが最小の文字-文字コードで、これを引くとデータの取り得る値が00〜99の範囲になることから設定されている定数になる。

この結果、

  • 単一のチャンクから生成したQRコードは、shc:/56762909524320603460292437404460...
  • 長いJWSで、3つのチャンクのセットの内2つめのチャンクで生成したQRコードは、`shc:/2/3/56762909524320603460292437404460...

のようになる。

ワクチン接種証明のQRコードをデコード

今回、ワクチン接種証明アプリからQRコードを表示できるので、そのデータをデコードしてみる。shc:/以降の数値のデータは、上記のエンコード方法と逆に、2桁の数値毎に+45した文字コードをの文字を算出すればいい。Rubyだと以下のように書けばデコードできる(JWSは、Header、Payload、Signatureの3つのデータで構成され、各パーツはドット(.)で区切られている。)。

qr_content = '<shc:/以降の数値>'

header, payload, sig = qr_content.scan(/.{1,2}/).map do |chrs|
  (chrs.to_i + 45).chr
end.join.split('.')

データはBase64URLエンコードされてるので、Headerをデコードしてみると↓

require 'base64'

Base64.urlsafe_decode64(header)
=> {"zip": "DEF", "alg": "ES256", "kid": "f1vhQP9oOZkityrguynQqB4aVh8u9xcf3wm4AFF4aVw"}

↑から、

ことを示している。ただ、zipはJWSの仕様で定義されているパラメータではないので、SMART Health Cardのカスタム仕様っぽい

なので、Payloadを確認するには、Inflateする必要がある。

require 'zlib'

zstream = Zlib::Inflate.new(-Zlib::MAX_WBITS)
uncompressed = zstream.inflate(Base64.urlsafe_decode64(payload))

※ RAW Inflateモードを有効にするためにウィンドウサイズを-Zlib::MAX_WBITS(-15)に設定してる。通常のZlib::Inflate.inflateを使うとincorrect header checkエラーが発生する。

uncompressedを整形すると、以下のVCが確認できる

{
  "iss": "https://vc.vrs.digital.go.jp/issuer",
  "nbf": 1646822383.591016,
  "vc": {
    "type": [
      "https://smarthealth.cards#health-card",
      "https://smarthealth.cards#immunization",
      "https://smarthealth.cards#covid19"
    ],
    "credentialSubject": {
      "fhirVersion": "4.0.1",
      "fhirBundle": {
        "resourceType": "Bundle",
        "type": "collection",
        "entry": [
          {
            "fullUrl": "resource:0",
            "resource": {
              "resourceType": "Patient",
              "name": [{"use": "usual", "family": "\u5b89\u571f", "given": ["\u8302\u4ea8"]}],
              "birthDate": "1980-08-23"
            }
          },
          {
            "fullUrl": "resource:1",
            "resource": {
              "resourceType": "Immunization",
              "status": "completed",
              "vaccineCode": {
                "coding": [{"system": "http://hl7.org/fhir/sid/cvx", "code": "207"}]
              },
              "patient": {"reference": "resource:0"},
              "occurrenceDateTime": "2021-07-09",
              "performer": [{"actor": {"display": "MHLW_Gov_of_JAPAN"}}],
              "lotNumber": "3002618"
            }
          },
          {
            "fullUrl": "resource:2",
            "resource": {
              "resourceType": "Immunization",
              "status": "completed",
              "vaccineCode": {"coding": [{"system": "http://hl7.org/fhir/sid/cvx", "code": "207"}]},
              "patient": {"reference": "resource:0"},
              "occurrenceDateTime": "2021-08-06",
              "performer": [{"actor": {"display": "MHLW_Gov_of_JAPAN"}}],
              "lotNumber": "3004232"
            }
          },
          {
            "fullUrl": "resource:3",
            "resource": {
              "resourceType": "Immunization",
              "status": "completed",
              "vaccineCode": {"coding": [{"system": "http://hl7.org/fhir/sid/cvx", "code": "207"}]},
              "patient": {"reference": "resource:0"},
              "occurrenceDateTime": "2022-03-09",
              "performer": [{"actor": {"display": "MHLW_Gov_of_JAPAN"}}],
              "lotNumber": "000126A"
            }
          }
        ]
      }
    }
  }
}

↑から、

  • 発行者はhttps://vc.vrs.digital.go.jp/issuerとなっており、デジタル庁。
  • nbf(Not Before Time)は発行日を表すUNIXタイムスタンプ
  • vccredentialSubjectには、 接種対象者の情報、接種情報がそれぞれ記録されている。↑だと3回分(回数増えてデータが増えると、QRコードもチャンク化されるんだろう)。Credentialのタイプは以下の3つ:
    • https://smarthealth.cards#health-card:ヘルスカードの伝達用に設計されたVC
    • https://smarthealth.cards#immunization:免疫に関する詳細のVC
    • https://smarthealth.cards#covid19:COVID-19の詳細のVC

が分かる。基本的にFHIR(Fast Healthcare Interoperability Resources)でモデル化された臨床データを提示するVCっぽい。

署名鍵

SMART Health Cardの仕様では、発行者は署名鍵の公開鍵をJSON Web Keyのセットとして/.well-known/jwks.jsonで公開することになっている。そのため↑では、https://vc.vrs.digital.go.jp/issuer/.well-known/jwks.jsonで公開鍵が公開されている↓

{
  "keys": [
    {
      "kty": "EC",
      "kid": "f1vhQP9oOZkityrguynQqB4aVh8u9xcf3wm4AFF4aVw",
      "use": "sig",
      "alg": "ES256",
      "x5c": [
        "MIIByjCCAXGgAwIBAgIJAPZFN9WW4voaMAoGCCqGSM49BAMDMCIxIDAeBgNVBAMMF3ZjLnZycy5kaWdpdGFsLmdvLmpwIENBMB4XDTIxMTEyNTEyNTUxNloXDTIyMTEyNTEyNTUxNlowJjEkMCIGA1UEAwwbdmMudnJzLmRpZ2l0YWwuZ28uanAgSXNzdWVyMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEViKBgZ0f3pQKv+tSz653HUtIzCS8TVSNu1Hwi0tKpSnTXXvtqkpcfYeAZ+SfvVk8SWNaTRDZ9wTNjb9c58v9l6OBizCBiDAJBgNVHRMEAjAAMAsGA1UdDwQEAwIHgDAdBgNVHQ4EFgQUiIXKUyT93YdyqsIjE8i5I1z8w0IwHwYDVR0jBBgwFoAU0cYt0sPpuIDBt7a9PD3qs9mOu7EwLgYDVR0RBCcwJYYjaHR0cHM6Ly92Yy52cnMuZGlnaXRhbC5nby5qcC9pc3N1ZXIwCgYIKoZIzj0EAwMDRwAwRAIgEwVdLdbPqMYqEsVltnsm3bI/Z6eibgMwYaNVZiu0r2sCIFebHk1i6ghWOQn+Q0+t5F77fasgJ3Oc6NWx9I8AWjRM",
        "MIIBkDCCATagAwIBAgIJAOECTZDa4MA7MAoGCCqGSM49BAMEMCcxJTAjBgNVBAMMHHZjLnZycy5kaWdpdGFsLmdvLmpwIFJvb3QgQ0EwHhcNMjExMTI1MTI1NTEzWhcNMjYxMTI0MTI1NTEzWjAiMSAwHgYDVQQDDBd2Yy52cnMuZGlnaXRhbC5nby5qcCBDQTBZMBMGByqGSM49AgEGCCqGSM49AwEHA0IABEL3S0yNIJ8EuxgiaHEvsjGWd60P0BBKUfVUVSxpVyGsnXwuzkS7OPGG/DT60m5XTvKT125MRuZoS/sajPBcg2KjUDBOMAwGA1UdEwQFMAMBAf8wHQYDVR0OBBYEFNHGLdLD6biAwbe2vTw96rPZjruxMB8GA1UdIwQYMBaAFPKN8VogQyX0IuxEi7jBB5gUnFinMAoGCCqGSM49BAMEA0gAMEUCIQCcq3H/pRMRkUmpWUDsggQXJAjLB/AutlHQigEBsVx0sgIgfVyc0L1cbRaDmdCQ3CGd994rRuwlQI0/cJCIv5LeI3g=",
        "MIIBlTCCATugAwIBAgIJANt2MZrWChe2MAoGCCqGSM49BAMEMCcxJTAjBgNVBAMMHHZjLnZycy5kaWdpdGFsLmdvLmpwIFJvb3QgQ0EwHhcNMjExMTI1MTI1NDUzWhcNMzExMTIzMTI1NDUzWjAnMSUwIwYDVQQDDBx2Yy52cnMuZGlnaXRhbC5nby5qcCBSb290IENBMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEilfgw+JIG8TOliOLe7jufm2m0+HqL4t5nvBdQj3UMgh8jjl6VoVKKwcj3T1DWFinm6sCTWYUrPSXWcvOq64GbKNQME4wDAYDVR0TBAUwAwEB/zAdBgNVHQ4EFgQU8o3xWiBDJfQi7ESLuMEHmBScWKcwHwYDVR0jBBgwFoAU8o3xWiBDJfQi7ESLuMEHmBScWKcwCgYIKoZIzj0EAwQDSAAwRQIgQWnKyVhaKpu1WcXP49s9inaa5mnWgV/pCW31h/NIJnwCIQDSIHvGUuPwK+ofYqLJGo99hhwhfkIBWhvSo0vr5IGesg=="
      ],
      "crv": "P-256",
      "x": "ViKBgZ0f3pQKv-tSz653HUtIzCS8TVSNu1Hwi0tKpSk",
      "y": "01177apKXH2HgGfkn71ZPEljWk0Q2fcEzY2_XOfL_Zc"
    }
  ]
}

楕円曲線P-256の公開鍵のデータになっている。x5cはこの公開鍵のX.509証明書(もしくは証明書チェーン)のデータ。

そして、JWSのHeaderにあったkidはこの公開鍵を指すJSON Web Key Thumbprintになっている。これは、json-jwt gemを使って以下のように計算できる。

require 'json/jwt'

params = {
  kty: :EC,
  crv: 'P-256',
  x: 'ViKBgZ0f3pQKv-tSz653HUtIzCS8TVSNu1Hwi0tKpSk',
  y: '01177apKXH2HgGfkn71ZPEljWk0Q2fcEzY2_XOfL_Zc'
}

jwk = JSON::JWK.new(params)
jwk.thumbprint('sha256')
=> f1vhQP9oOZkityrguynQqB4aVh8u9xcf3wm4AFF4aVw

今回は鍵は1つだったけど、/.well-known/jwks.jsonには複数の署名鍵の情報が設定されることもあるので、kidでそのうちのどの鍵を使って署名されているのか確認する。

署名検証

署名鍵が特定できたので、最後にJWSの署名を検証する。ecdsa gemを使って検証すると↓

require 'ecdsa'

x = Base64.urlsafe_decode64('ViKBgZ0f3pQKv-tSz653HUtIzCS8TVSNu1Hwi0tKpSk').unpack1('H*').to_i(16)
y = Base64.urlsafe_decode64('01177apKXH2HgGfkn71ZPEljWk0Q2fcEzY2_XOfL_Zc').unpack1('H*').to_i(16)
public_key = ECDSA::Point.new(ECDSA::Group::Secp256r1, x, y)

digest = Digest::SHA256.digest("#{header}.#{payload}")

signature = Base64.urlsafe_decode64(sig)
r = signature[0...32].unpack1('H*').to_i(16)
s = signature[32..-1].unpack1('H*').to_i(16)
signature = ECDSA::Signature.new(r, s)

ECDSA.valid_signature?(public_key, digest, signature)
=> true

と、署名の正しさを検証できる。Secp256r1NIST P-256の別名(ちなみにOpenSSLでは、prime256v1)。

気になった点

  • 接種証明をVerifiable Credentialで提供しているけど、IssuerやHolderに関してDIDで識別されている訳ではなさそう。
  • ↑のVCの提示で接種証明はできるけど、このQRコードのコピーを持っていたら誰でも証明できてしまいそう。DIDなんかでHolder側にも鍵があって、(VCのIssuerの署名に加えて)Verifiable PresentationなどでHolderの署名を提供するような仕組みが欲しい。