Develop with pleasure!

福岡でCloudとかBlockchainとか。

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の署名を提供するような仕組みが欲しい。

通信ラウンドの効率性を重視したSchnorrベースの閾値署名スキームFROST

TaprootのアクティベートによりBitcoinでもSchnorr署名が利用可能になったけど、Schnorr署名をメリットの1つはマルチシグの署名を単一の署名に集約できる集約特性があることで、この恩恵を受けるためにはこのようなマルチシグを扱うウォレットの開発が必要になる。

マルチシグの集約について、簡単なのはn-of-nのケースで、このようなマルチシグをトラストレスに安全に構成する(Rogue-Key攻撃に対して安全)プロトコルとしてMuSig2などが発表され開発が進んでいる↓

techmedia-think.hatenablog.com

n-of-nのマルチシグはSchnorr署名の線形特性をそのまま利用するためシンプルだが、一方、m-of-nのような閾値設定のマルチシグのプロトコルは、秘密分散法を利用して、集約された秘密鍵の情報を漏らすことなく、閾値m個の有向な部分署名が集まった場合に有効な署名を完成できる必要があり、難易度はぐんと上がる。有名なのはPedersenの検証可能な秘密分散法(VSS)を用いた閾値署名スキームなど↓

techmedia-think.hatenablog.com

FROST

そんな閾値署名スキームの提案の1つがFROST: Flexible Round-Optimized Schnorr Threshold Signatures。堅牢性よりも効率性を採ったプロトコルになる。

これまでの閾値署名スキームは、ある参加者が不正をして、不正なシェアを提供した場合、残りの正直な参加者は、その不正を検出し、残りの正直な参加者の数が閾値tいる限りプロトコルを完了できるという堅牢性を備えている。

ただ、ある程度信頼できる参加者の中では、つまり全参加者が正直にプロトコルに従っているという楽観的なケースでは、プロトコルを中断し、不正を行ったユーザーを除外してプロトコルを再実行することで、署名プロセスで必要になる通信ラウンド数を減らすというのがFROSTの採るアプローチ。

https://eprint.iacr.org/2020/852.pdf

今回は、このFROSTの署名スキームについて詳しくみていく。

前提として、n人の参加者がいて、この内、t人の協力があれば集約鍵に対して有効なSchnorr署名を構成できるものとする。

多項式補間

具体的なプロセスの前に、重要な構成要素である多項式補間について。

↑の記事にも書いたシャミアの秘密分散法は、閾値tにおいてf(0) = シークレットとなるようなt-1次の多項式を構築し、そのシェア(i, f(i))を配布し、それがt個集まったら多項式f(x)が再構築できf(0)のシークレットが分かるという仕組み。

多項式の復元には、ラグランジュ補間を使用できる:

 {\displaystyle f(x) = \sum_{j=1}^{t}f(j) \Pi_{i \neq j}\frac{x - x_i}{x_j - x_i}}

そして復元した多項式からf(0)のシークレットを求めるには、

 {\displaystyle f(0) = \sum_{i=1}^t}f(i)\lambda_i

を計算する。ここで {\lambda_i}は、x = 0つまりf(0)における {\displaystyle \lambda_i = \Pi^{t}_{j=1, j \neq i} \frac{j}{j-i}}となるiに対するラグランジュ係数。

後の署名処理の際に登場するけど、ここでのポイントは、シークレットを求める際に使用するラグランジュ係数は、閾値の数とiの値が分かれば定数値として求まるという点。

分散鍵生成

まず最初に、分散鍵生成(Distributed Key Generation=DKG)プロセスを実行して、集約鍵を生成する。ここではPedersenの検証可能な秘密分散法(VSS)のDKGをベースにしている。*1

n人の参加者は、それぞれ1〜nまでの一意の識別番号を持っていることとする。各参加者は以下を行う。

  1. t個のランダムシークレット {a_0,..., a_{t-1}}を生成する。
  2. 1のシークレットを使ってt-1次の多項式を作成する。 {f(x) = a_{t-1}x^{t-1} + a_{t-2}x^{t-2} + ... + a_0}
  3.  {a_0}の知識の証明をするため、以下の手順でSchnorr署名を作成する。
    1. ランダムなnonce kを選択。
    2. 自身のIDと {a_0G, kG}およびリプレイ攻撃を防ぐための文字列の値のハッシュ値を計算しチャレンジcとする。
    3.  {a_0}秘密鍵としてSchnorr署名 {sig = (kG, k + ca_0)}を生成する。
  4. 各係数に対するコミットメントとして、1で生成した多項式の各係数に対応する公開鍵 {(a_0G, ..., a_{t-1}G)}を計算する。
  5. 3で生成したSchnorr署名と4の多項式の係数に対応した公開鍵のリストを他の参加者に送信する。
  6. 他の参加者から受信した5のデータから、署名の有効性(署名が {a_0G}に対して有効か)を検証する。

ここまでで、第一ラウンドの通信が終了。

続いて第二ラウンドでは、以下を行う。

  1. 参加者は生成した多項式を使って、他の参加者に {(i, f(i))}のシェアを送信する。ここでiは他の参加者のID。
  2. 1のシェアを受け取ったユーザーは、第一ラウンドで受け取った公開鍵のリストを使って、そのシェアが正しく計算されたものか検証する。多項式の係数自体は不明だが係数に対応する公開鍵を持っているので、検証は可能。
  3. 他のすべての参加者からシェアを受け取ったら、それらのシェアを合算して、集約鍵のシェアを導出する。IDがiの参加者は、 {s_i = f_1(i) + f_2(i) + ... + f_n(i)}を持つことになる。
  4. 自分の公開シェア {P_i = s_iG}とし、集約公開鍵 {P = \sum^{n}_{i=1} a_{i0}G}を計算する。
  5. また他の参加者の公開シェアも、多項式の係数に対応する公開鍵のリストから算出できる。

つまり、この第二ラウンドが終わった時点で、第一ラウンドで各参加者がそれぞれランダムに生成した多項式を合算した多項式に対するシェア( {s_i})を各参加者が持っている状態になる。

そして、各参加者の {a_0G}を合算した {P = \sum^{n}_{i=1} a_{i0}G}が集約公開鍵となる。署名生成フェーズでは、この集約公開鍵に対して有効な署名をt人で協力して生成することになる。

FROSTのDKGプロトコルは以上の2ラウンドの通信で完了する。

署名生成

前処理ラウンド

署名生成は、前処理ラウンドから始まる。前処理ラウンドでは各参加者iは以下を実行する。

  1. 一度だけ使用するnonceのペア {(d_i, e_i)}生成する。
  2. 1のシークレットに対応する公開鍵のペア {(D_i = d_iG, E_i = e_iG)}を生成する。

↑を {\pi}個作成し、 {\pi}個の公開鍵のペアのリストを他の参加者に公開する。各署名プロセスではこのnonceの値のペアを1つ使用するため、 {\pi}個使い切ったらまたこの前処理ラウンドを実行する。つまり、署名の度にこの前処理ラウンドが必要という訳ではない。初回の前処理ラウンドは、↑のDKGと一緒にやっても良い。

署名ラウンド

DKGで集約鍵が決定し、前処理ラウンドが終わると、メッセージmに対して署名をする準備が完了する。

署名プロセスでは参加者の1人がSignature Aggregator = SA(署名の集約を行う人)の役割の担う。SAは参加者の中から、自身を含めてt人をピックアップし、このt人の未使用のnonceのペア {(D_{ij}, E_{ij})}(iは参加者のID、jは前処理ラウンドで生成した {\pi}個中のインデックス)をピックアップする。そして、SAは選択した {(D_{ij}, E_{ij})}のリストとメッセージmをt人の参加者に送信する。

t人の参加者は、

  1. SAから送られた署名対象のメッセージmを確認する。
  2. SAから送られてきた {(D_{ij}, E_{ij})}のリストのコミットメントが、前処理ラウンドで自分が受け取ったリストの中にあるか確認する。
  3. IDと {(D_{ij}, E_{ij})}のリストとメッセージをハッシュしたバインディング {p_i = H(i, m, リスト)}を署名参加者全員分計算する。このバインディングを行うことで既知の偽造攻撃を回避する。
  4. 署名に使用する集約nonce  {R = \sum^{t}_{k=1}D_{kj} + p_iE_{kj}}を計算する。
  5. 続いて署名のチャレンジ {c = H(P, R, m)}を計算する。
  6. DKGで導出された自身の秘密鍵に関するシェア {s_i}を使って部分署名 {z_i = d_{ij} + p_i e_{ij} + H(P, R, m)s_i \lambda_i}を計算し、SAに送信する。

↑の部分署名を見てみると、 {d_{ij} + p_ie_{ij}}をnonceとした秘密鍵 {s_i \lambda_i}のSchnorr署名の形式になっていることが分かる。 {\lambda_i}は、前述した多項式f(x)についてf(0)を求める際のラグランジュ係数。

ここで、 {s_i \lambda_i}というのは、多項式補間で求める秘密鍵 {\displaystyle f(0) = \sum_{i=1}^t}f(i)\lambda_iの一部で、それによってSchnorrの部分署名を作成していることが分かる。つまり、これを閾値分合算すれば、集約秘密鍵で署名したのと同じ結果のSchnorr署名の値になるということ

SAはすべての部分署名を受信し、

  1. 集約nonce Rとチャレンジcを計算する。
  2. すべての部分署名が正しいものか、 {z_iG = R_i + c \cdot \lambda_i \cdot P_i}が成立するか検証する。成立しなかった場合、その部分署名を作った参加者が不正をしていることになる。前述したように、参加者のセットが決まれば {\lambda_i}はどの参加者も計算できるため、この検証が可能になる。
  3. 部分署名を合算して、最終的な署名 {z = z_1 + ... + z_t}を計算する。
  4. (R, z)がメッセージmに対して有効なSchnorr署名となる。

また、各参加者は署名を行ったら、 {(D_{ij}, E_{ij})}のリストから署名に使用したデータを削除する必要がある。

上記のプロセスから、FROSTの署名プロセスはSAと各署名者の1ラウンドの通信で完了することが分かる。

参考

*1:ちなみにVSSとは、秘密分散法でシェアを配布する際に、参加者のシェアがすべて正しいことを検証するための仕組み。FledmanのVSSでは中央のディーラーを必要としたのに対し、PedersenのVSSは各参加者がディーラーとして機能するようになっている。

CTVを利用したDLCプロトコルのパフォーマンス改善

先月Lloyd Fournierにより提案された、現在提案中のBIP-119のCTV(OP_CHECKTEMPLATEVERIIFY)を使うとDLCのパフォーマンスが大幅に向上するという内容についてみてみる↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-January/019808.html

DLCとは?

DLC(Discreet Log Contracts)はBitcoinでオラクルを利用したコントラクトを実現するプロトコル

もともとBitcoinには任意のメッセージに対して署名検証を行うようなopcodeはないため、本来オラクルを利用したコントラクトは作れないが、Schnorr署名やAdaptor Signatureを利用することで、これを可能にしたのがDLC

簡単に説明すると、あるイベントの結果を発表するオラクルが存在する。このオラクルの公開鍵 {P = xG}は事前に公開されている。そしてイベント毎にオラクルはその結果の情報に署名して署名値を公開する。ただ、事前に署名に使用するPublic nonce  {R = kG}は公開しておく。Pはオラクルにつき1つだが、Rはイベント毎に作られる。

このオラクルが公開する結果を元にして、資金を決済したい2人は、オラクルが公開したRを使って、結果の取り得る値の数分、以下の証明ポイントを計算する。

 {S_i = R + H(R || X || 結果_i) P}

そしてこのSの候補セットを使って、 {結果_i}に応じて資金を分配する(契約を実行する)Contract Execution Transaction(CET)を作成する(例えば、 {結果_i}がXであれば1BTCをAに残りをBに、Yであれば1BTCをBに残りをAに送るというような)。

この時、CETのアウトプットの資金は、 {賭けたユーザーの公開鍵 + S_i}にロックされる。

イベントが終わると、オラクルは、対象となる {結果_i}について、Public nonce Rに対応するnonce kを使ってSchnorr署名 {s_i = k + H(R || X || 結果_i) x}を計算し、署名データを公開する。

この {s_i}は、予め賭けの参加者が計算した証明ポイント {S_i}秘密鍵になるため、 {s_i}が分かれば、資金をロックした {i賭けたユーザーの公開鍵 + S_i}について、自分の秘密鍵と合わせてアンロックすることができる。

詳細な仕組みについては、以前のブログ記事GBEC動画を参照。

Adaptor Signature版

↑はオリジナルのDLCプロトコルだけど、CETでAdaptor Signatureを利用するパターンが現在の主流になっている。

オリジナルのプロトコルでは、CETのアウトプットのロック条件に証明ポイントを使用していたけど、Adaptor Signatureを使う場合、CETのアウトプットは、イベントの結果による両者の残高が単純に反映されたものになる。そしてCETのインプットの署名にAdaptor Signatureを利用する。

インプットは参加者の2-of-2のマルチシグになっているので、これをインプットとして、結果のパターン分両者の残高を反映したCETを作成する。そして各CETに対して証明ポイント {S_i}を補助ポイントとしてAdaptor Signatureを生成し、交換する。この場合、オラクルが結果の {s_i}を公開すると、そのデータを使ってAdaptor Signatureを有効な署名に変換することができる。つまり、オラクルが公開した結果に対応した {CET_i}のみが有効な署名を得られることになる。

DLCの課題

↑のようにしてBitcoinでもオラクルを利用したコントラクトを構築できるが、DLCプロトコルの参加者は、

  • 結果の取り得る数分の証明ポイントの計算
  • CETの数分のアダプター署名の計算と検証

をしなければならない。結果の取り得る値が数件なら特に問題になるようなことはないけど、例えばBTC/USD価格のようなものが対象の場合、何千、何万というオーダーの証明ポイントおよびCETを作成しなければならず、参加者が通信するデータ量もそれに応じて増加する。特にCETの数分のAdaptor Signatureの演算はコスト高になる。

また、複数のオラクルを用いる場合や、複数のオラクルの閾値を利用するようなケースでは、さらに大幅に計算量が増える。

CTVを使ったパフォーマンス改善

↑の課題をCTVを利用することで改善しようというのが今回の提案。

これまで各CET毎にAdaptor Signatureを作成していたけど、代わりに結果の数分の以下のようなTapleafのスクリプトにコインをロックする。

<CET-hash_i> CHECKTEMPLATEVERIFY <証明ポイント> CHECKSIG

ここで、<CET-hash_i> {結果_i}の場合に、その結果に応じた各ユーザーの残高を反映した {CET_i}トランザクションから生成したハッシュ値。証明ポイントに対して有効な秘密鍵は、オラクルが公開した署名データから得られる。

つまりオラクルが公開した値により対象の結果のTapleafの署名検証をパスするが、CHECKTEMPLATEVERIFYにより、このコインは予め定められたCETトランザクションでしか使えないという制約を付けている。

この結果、Adaptor Signature作成時に必要な楕円曲線の演算を、ハッシュ計算に置き換えることができ、計算コストが大幅に削減される。事前の証明ポイントの計算しないといけないのは変わらないので、CTVによるパフォーマンス改善がAdaptor Signature版の場合ということかな?

また、複数のオラクルを使用する場合やオラクルの閾値を使用する場合も、以下のように簡単に実現できる。

<CET-hash> CHECKTEMPLATEVERIFY
<オラクル1の証明ポイント> CHECKSIG
<オラクル2の証明ポイント> CHECKSIGADD
<オラクル3の証明ポイント> CHECKSIGADD
2 EQUAL

CTVを使う場合のトレードオフ

これまでのDLCプロトコルは、Bitcoinスクリプト機能を使うものではなく、暗号技術を組み合わせたScriptlessな構造だったけど、↑のようにCTVを使うと、非協調ケースの場合にCETをブロードキャストすると、それがDLCトランザクションであることが識別できてしまう。また、CTVで検証するハッシュ分や、そのTapleafまでのマークルパスなどデータサイズが少し増えることになる。