Develop with pleasure!

福岡でCloudとかBlockchainとか。

Taroのオンチェーンアドレス仕様

techmedia-think.hatenablog.com

↑のアセットの新規発行に続いて、アセットを送付しようと思ったけど、その前にアセットを受け取る際に必要になるTaroのオンチェーンアドレス仕様について見ておく。

Taroアドレス

Taroのアセットを受け取る際のアドレスは既存のBitcoinアドレスではなく、その仕様は↓のBIPドラフトに定義されている。

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

アドレスはエンコード仕様にTaprootと同じbech32mを採用しており、bech32mのhuman-readable parts(HRP)は

  • mainnetがtarobc
  • testnet/signettarotb
  • regtestがtarort

で(BIPドラフトではtarotarotと記載されてるけど、tarodのα版では↑のように定義されてる)、データ部は、以下のTLVデータで構成される。

タイプ 定義
0 taro_version Taroのバージョン。現在は0。
2 asset_id 受け取るアセットのアセットID。※ ただα版の実装ではIDではなくアセットジェネシスになってる。
3 asset_key_family アセットファミリーキー。異なるアセットIDのアセットを関連付けるために使用する鍵。ノーマルタイプのアセットを追加発行する際に、発行済のアセットと追加発行したアセットでIDが異なるので、それを紐付けるために利用。
4 asset_script_key アセットを受け取る公開鍵
6 internal_key アセットを受け取るトランザクションアウトプット(Taprootアウトプット)で使用するTaprootの内部鍵(公開鍵)
8 amt 受け取るアセットの量
9 asset_type アセットタイプ(省略時は0=ノーマル)Type:2がジェネシスになるのであれば必要ないので無くなるものと思われる。

タイプが厳密に連番じゃないのは、ライトニングの機能ビットと同様で、奇数値のフィールドはオプションであることを示すため(↑ではasset_key_familyasset_typeがオプション)。1と5使ってないのは何でだろう?

アセットの受信者は、受け取りたいアセットの情報と、受け取りに使用する鍵(asset_script_keyinternal_key)から↑のTaroアドレスを生成する。

tarocliでアドレスを生成

tarocliaddrs newコマンドを使用すればTaroアドレスが生成される。前回1,000発行したアセットを500ほど受け取るアドレスの生成は↓

$ tarocli addrs new --amt 500 --genesis_bootstrap_info a92eb9e8d42437b8879ff571903fcbb74b55fc558c3cbc80ba8ca293bcd82eaf000000010874657374636f696e116d6574616461746120666f7220746573740000000000
{
    "encoded": "tarotb1qqqsqqjy4yhtn6x5ysmm3pul74ceq07tka94tlz43s7teq963j3f80xc96hsqqqqqyy8getnw33k76twz9kk2arpv3shgcfqvehhygr5v4ehgqqqqqqqqppq5746x7psp9fvl0mhs6f80zcnpzlch5v97xh46j6459sy80supf9svgzkf72uhhmf2a2ma8s8glra7dqagk96n47fda64q6dkmu32xjfw7syq8lgp7syf8tft",
    "asset_id": "9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061ca",
    "asset_type": "NORMAL",
    "amount": "500",
    "family_key": null,
    "script_key": "02a7aba378300952cfbf778692778b1308bf8bd185f1af5d4b55a16043be1c0a4b",
    "internal_key": "02564f95cbdf695755be9e0747c7df341d458ba9d7c96f755069b6df22a3492ef4",
    "taproot_output_key": "37fc965befde457f4c7943750d83a5743a565fb12eaf7c01c3084fe8b106f533"
} 

アセットの情報はgenesis_bootstrap_infoで指定する。このデータは、アセット発行の際に使用したアセットジェネシスのデータ(アセットIDを算出する際のデータ)になる。tarocliではassets listコマンドの出力結果にも含まれている。

受信者は↑のbech32mアドレスを送信者に送り、送信者はそのアドレスから送金先のTaroアウトプットを作成することになる。

taproot_output_keyは、500個分のアセット9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061caをリーフノードとして空のMS-SMTツリーに挿入してTaroのアセットツリーを構成し、それとinternal_keyをTaprootの内部鍵として利用して計算したTaprootのwitness programになる。そのため、実際に受信者が受け取るTx内のアウトプットのscriptPubkeyは、

OP_1 <37fc965befde457f4c7943750d83a5743a565fb12eaf7c01c3084fe8b106f533>

となり、P2TRアドレスに変換すると、

tb1pxl7fvkl0mezh7nregd6smqa9wsa9vha396hhcqwrpp873vgx75es923e09

となる。

tarocliで↑のアドレスを作成した段階で、連携先のlndのウォレットにこのアドレスがインポートされていることが確認できた。

単純に、↑のP2TRアドレスをTaroアドレスとしないのは、どういったツリーが構成されるか送信者も検証する必要があるからかな。

Taroのアセット発行の仕組み

前回の記事でTaroのアセットツリーの構造を確認したので↓

techmedia-think.hatenablog.com

今回は、Taroでのアセット発行の仕組みをRubyで実装しながらみていく。

tarocliを使ったアセットの発行

tarocliのassets mintコマンドを利用するとアセットを新規発行することができる。実際にtestnetで発行してみたのが↓

$ tarocli assets mint --type normal --name testcoin --supply 1000 --meta "metadata for test" --skip_batch
{
    "batch_key": "02fe3155363518765636316775fec96b57e454c3dd50ce19d18da5a1f9cf91b3a7"
}
$ tarocli assets list                                                                                    
{
    "assets": [
        {
            "version": 0,
            "asset_genesis": {
                "genesis_point": "af2ed8bc93a28cba80bc3c8c55fc554bb7cb3f9071f59f87b83724d4e8b92ea9:1",
                "name": "testcoin",
                "meta": "6d6574616461746120666f722074657374",
                "asset_id": "9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061ca",
                "output_index": 0,
                "genesis_bootstrap_info": "a92eb9e8d42437b8879ff571903fcbb74b55fc558c3cbc80ba8ca293bcd82eaf000000010874657374636f696e116d6574616461746120666f7220746573740000000000",
                "version": 0
            },
            "asset_type": "NORMAL",
            "amount": "1000",
            "lock_time": 0,
            "relative_lock_time": 0,
            "script_version": 0,
            "script_key": "026e552eef52663dcf984ad1443660a66923aca4c8b77240fb83114dbb0ea91269",
            "asset_family": null,
            "chain_anchor": {
                "anchor_tx": "02000000000101a92eb9e8d42437b8879ff571903fcbb74b55fc558c3cbc80ba8ca293bcd82eaf0100000000ffffffff02e8030000000000002251204a8b4d59fede637b63c2473c06234615a7c82406912954f744e358e74922e254e9e500000000000016001496c99700a2d53b57904468a77e0c3db3da7463660140f5af40e5a9bcc96a57aa0d7a696e05f3752e0b150dd414fb0f5796e9b4ff625b3efaf06dc90733d0b6b949126d3a0b24bc1db796e54984234654e6a9c4e72a2000000000",
                "anchor_txid": "57ffcf286d5f1ec8a3168d48e7ec861bda2edaec87ddba4784d81e46a3a48a47",
                "anchor_block_hash": "0000000000000000000000000000000000000000000000000000000000000000",
                "anchor_outpoint": "478aa4a3461ed88447badd87ecda2eda1b86ece7488d16a3c81e5f6d28cfff57:0",
                "internal_key": "02fe3155363518765636316775fec96b57e454c3dd50ce19d18da5a1f9cf91b3a7"
            }
        }
    ]
}

※ anchor_txidは、エンディアンが逆になってるので要注意

今回は、この発行処理の中身を見ていく。

アセットの発行手順

アセットを発行するということは、Taprootベースのアセット発行用のTaprootのアウトプットを作成するということで、Taroでは以下の手順でアセット発行用のTaprootアウトプットを作成する。

  1. ウォレットが保持している任意のUTXOをピックアップし、アセット発行に使用するOutPointを選択する。
  2. 1をgenesis_pointとして、asset_tagとasset_metaからアセットIDを計算する。
  3. 新規発行するアセットのアセットツリーを構築する(ツリー構造については↑の記事参照)。
    1. 新規発行する2のアセットIDのアセットツリー(2階層めのツリー)のリーフノードを作成する(asset_leaf || leaf_sum)。
    2. 生成したリーフを含むMS-SMTのルートハッシュを計算する。
    3. 計算したルートを使って、アセットツリー(1階層めのツリー)であるMS-SMTのリーフを作成する(taro_version || asset_id_tree_root || asset_sum)。
    4. 作成したリーフを持つMS-SMTのルートハッシュを計算する。
  4. Taprootの内部鍵用の鍵を生成する。
  5. アセットツリーのルートハッシュをリーフとしたTapscriptのツリーを作成し、内部鍵と合わせてTaprootアウトプットを作成する。

このプロセスを詳しくみていく。

アセットIDの計算

まず最初にアセットIDは、前回の記事から、

asset_id = sha256(genesis_outpoint || asset_tag || asset_meta || output_index || asset_type)

として計算されるので、genesis_pointname(=タグ)、metaoutput_indexasset_type(NORMAL = 0)から以下のように計算できる(bitcoinrbを使用)。

require 'bitcoin'

genesis_point = Bitcoin::OutPoint.from_txid('af2ed8bc93a28cba80bc3c8c55fc554bb7cb3f9071f59f87b83724d4e8b92ea9', 1)
tag = Bitcoin.sha256('testcoin')
asset_meta = Bitcoin.sha256("6d6574616461746120666f722074657374".htb) # 6d6574616461746120666f722074657374 = "metadata for test"
output_index = [0].pack('I>')
type = [0].pack('C')
payload = genesis_point.to_payload + tag + asset_meta + output_index + type

asset_id = Bitcoin.sha256(payload)
=> "9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061ca"

アセットツリーの構築

Taroのアセットツリーは、↑の記事に書いたように2階層のツリーで構成されている。

2階層めのツリー

まず最初に、TaroのアセットID毎のツリー(MS-SMT)を作成する。このツリーに挿入するKey-Valueのペアは、

  • Key:Asset Script Key(アセットの所有者の管理化にある公開鍵)
  • Valueasset_leaf || leaf_sumをリーフの値とし、Sumとして発行量leaf_sumを持つリーフノード。

KeyのAsset Script Keyは、↑のtarocliで発行したアセットの場合↓の公開鍵になる。

"script_key": "026e552eef52663dcf984ad1443660a66923aca4c8b77240fb83114dbb0ea91269"

Valueであるリーフノードは、asset_leafleaf_sum結合したデータで、asset_leafアセットに関連する項目をLightningでおなじみのTLVフォーマットで定義した内容になる(現状、こことかFamily Keyのバイト数とか一部BIPドラフトとtarodのα版とでどうも仕様のズレがある)。

↑の単一のアセットの発行のみであれば、空のMS-SMTを作成し、↑のKey-Valueのデータを1つツリーに挿入してアセットツリーを作成すればいい。

このツリーは、あるアセットの各所有者とその所有量を管理するツリーとなる。

1階層めのツリー

続いて↑の記事の1階層めのツリー(MS-SMT)を作成する。このツリーに挿入するKey-Valueのペアは、

  • Key:アセットID(Asset Family Keyが設定されている場合は、その公開鍵のSHA-256値)
  • Value:リーフノードの値としてtaro_version || asset_id_tree_root || asset_sumを持ち、アセットIDツリーのsum値を持つリーフノード。ここでasset_id_tree_rootは先程作成したツリーのルートハッシュで、asset_sumは先程作成したツリーのルートのsum値。

つまり、1階層めのツリーは、アセットIDをキーにそのアセットの所有者及び所有量がコミットされている2階層めのツリーに対するコミットを行うツリーとなる。

Taprootアウトプットの作成

アセットツリーが構成できたら、それにコミットするTaprootのアウトプットを作成する。Taprootの作成には、内部鍵(Internal Key)とTapscriptのツリーが必要になる。

Taprootの内部鍵

Taprootの内部鍵はウォレットが作成することになる。今回tarodが生成した内部鍵は↑の出力結果から↓

"internal_key": "02fe3155363518765636316775fec96b57e454c3dd50ce19d18da5a1f9cf91b3a7"
Tapscriptツリー

続いて、↑のアセットツリーにコミットするTapscriptのツリーを構成する。今回みたいな単一のアセットの発行では、条件となるScriptブランチが1つのTapscriptツリーを構成すればいい。

この時、ツリーに挿入するリーフのスクリプトは以下のペイロードスクリプトになる。

leaf_version || taro_marker || taro_version || asset_tree_root || asset_tree_sum
  • versionは、アセットツリー内のアセットのバージョンの最大値(現状0)
  • taro_markerは、マーカー用のタグで、値はsha256("taro")
  • asset_tree_rootは↑の1階層めのツリーのルートハッシュ
  • asset_tree_sumは↑の1階層めのツリーのsum値

↑から分かるように、Bitcoin Scriptとして有効なデータではなさそう。つまり、これをそのままTaprootのTapscriptとして評価するような使い方はしないということかな。

今回の発行の仕組みでは、単純にこの単一のスクリプトをリーフとしたTapscriptのツリーを作って、そのルートハッシュと、↑の内部鍵を使ってTaprootのアウトプットを作ればいい。

サンプル実装

試しにtarocliが作成したアセット発行トランザクションと同じTaprootアウトプットをRubyで書いてみた(個別の処理を書いてくと長くなるので、tarorbというライブラリとして実装)。

require 'taro'

Bitcoin.chain_params = :testnet
# 発行に使用するUTXOの指定
genesis_point =
  Bitcoin::OutPoint.from_txid(
    "af2ed8bc93a28cba80bc3c8c55fc554bb7cb3f9071f59f87b83724d4e8b92ea9",
    1
  )
# アセットの生成
genesis =
  Taro::Genesis.new(
    prev_out: genesis_point,
    tag: "testcoin",
    metadata: "metadata for test",
    output_index: 0
  )
asset_script_key =
  Bitcoin::Key.new(
    pubkey:
      "026e552eef52663dcf984ad1443660a66923aca4c8b77240fb83114dbb0ea91269"
  )
asset = Taro::Asset.new(genesis, 1000, 0, 0, asset_script_key)
asset_id = asset.genesis.id # ↑で計算したのと同じアセットID

# 2階層めのツリーを構築
asset_commitment = Taro::AssetCommitment.new([asset])
# 1階層めのツリーを構築
taro_commitment = Taro::TaroCommitment.new([asset_commitment])

# 内部鍵
internal_key =
  Bitcoin::Key.new(
    pubkey:
      "02fe3155363518765636316775fec96b57e454c3dd50ce19d18da5a1f9cf91b3a7"
  )

#Taprootのアウトプットを作成
taproot_script_pubkey = taro_commitment.to_taproot(internal_key)
taproot_script_pubkey.to_addr # tarocliが発行したTxと同じTaprootのアドレス

最後のアドレスはtaroclianchor_outpointのUTXO(478aa4a3461ed88447badd87ecda2eda1b86ece7488d16a3c81e5f6d28cfff57:0)と同じアドレスになる。

以上が、Taroのアセット発行の手順。新規発行の場合は、アセットの所有者の検証などないので、次はアセットを転送する際の検証処理など見ていきたい。

lnd v0.15.1-beta以下で発生したチェーン同期の障害

lnd v0.15.1-beta以下で発生したlndでチェーンの同期ができなくなる不具合↓についてまとめておく。

github.com

正確には、btcdの不具合↓

github.com

障害の内容

今回発生した障害は、lndでブロックチェーンの同期ができなくなるというもの。そのため、その間、新しいチャネルの開設やクローズができなくなった。※ 稼働中のチャネルを利用したオフチェーン支払いは可能なまま。

実際、自宅で運用してるUmbrelでも、lndの以下のログを吐いてた↓

2022-10-09 21:04:09.448 [ERR] LNWL: Unable to deserialize transaction: readScript: script witness item is larger than the max allowed size [count 33970, max 11000]
2022-10-09 21:04:09.559 [ERR] LNWL: Unable to deserialize block: readScript: script witness item is larger than the max allowed size [count 33970, max 11000]
...
2022-10-11 00:05:36.001 [ERR] LNWL: Unable to process chain reorg: unable to get block 0000000000000000000400a35a007e223a7fb8a622dc7b5aa5eaace6824291fb: readScript: script witness item is larger than the max allowed size [count 33970, max 11000]

トリガーとなったのは、ブロック757922内の以下のトランザクション

7393096d97bfee8660f4100ffd61874d62f9a65de9fb6acf740c4c386990ef73

インプットが参照するUTXOはTaprootのアウトプットで、それをscript-pathで998-of-999のマルチシグを使ってアンロックしている。この結果、インプットのscriptWitnessには、999個の公開鍵と998個の署名データが含まれ、合計98,881バイトのデータになる。

※ ちなみに、998-of-999のマルチシグの場合、今回のケースとは別に998-of-998の組み合わせを999個作って1つの公開鍵と1つの署名に集約するというアプローチを採れば、データは150バイト以内に収められる。

このトランザクションをbtcdが正常にパースできず、チェーンの同期が失敗するようになった。

不具合の原因

問題となったbtcdのコードは、ピアからtxメッセージやblockメッセージを受け取って、そのトランザクションをパースする以下の部分↓

https://github.com/btcsuite/btcd/blob/v0.22.0-beta/wire/msgtx.go#L589-L594

maxWitnessItemSizeが11,000バイトに設定されており、このサイズを超えるscriptWitnessはエラーになる。このため、↑のscriptWitnessが98,881バイトあるトランザクションはパースに失敗する。

もともとこのチェックは、P2WSHの仕様↓から来てるっぽい(ただ、1,000バイトの差は何だろう?)。

The witnessScript (≤ 10,000 bytes) is popped off the initial witness stack. SHA256 of the witnessScript must match the 32-byte witness program.

本来Taprootにはこのルールが適用されないが↓*1、このルールが適用されたまま上限を超えるTxが登場したので今回問題が顕在化した。

Script size limit The maximum script size of 10000 bytes does not apply. Their size is only implicitly bounded by the block weight limit.

ちなみに、Bitcoin Coreの場合、このチェックはScriptを評価するこのコードに実装され、P2SHよびP2WSHに限定されている↓

if ((sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) && script.size() > MAX_SCRIPT_SIZE) {
    return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE);
}

不具合の修正内容

不具合の修正内容は単純で、maxWitnessItemSizeの値をブロックの最大サイズである4,000,000に引き上げるというもの。

ただ、この修正でちょっと気になったのが

  • このチェックはトランザクションレベルのサイズチェックで済む話なので、あえてこのインプット毎のチェックとして必要なのか?
  • チェックを残すにしても、P2WSHについては↑のチェック回避することになるけど、そこは問題はないのか?

どうしてlndで影響が出たのか?

今回の障害が発生した際、btcdの不具合で、lndの接続先にBitcoin Coreを選択してる自分には関係ない話かな?と思ったけど、そうでもなかった。

lndは、Bitcoinのノード実装だけでなく、ライブラリとしてbtcdのコードを多く利用している。今回も、フルノードから受け取ったブロックのパースに↑のbtcdのコードを使っているため、パースに失敗し新しいブロックを処理できなくなり、今回の障害に至ったと。

チャネルの開設やクローズのオペレーションができないくらいならまだ良いけど、不正なTxがブロードキャストされたのを検知できなくなる方が問題かな。今回みたいなケースを想定すると、Watchtowerの実装はLNノードの実装とはまた別のコードベースのものを使いたいと思うようになる。

*1:この制限がどうしてなくなったかというと、P2WSHまでは署名対象のメッセージダイジェスト(つまりトランザクションのダイジェスト)を計算する際に、アンロックに使用するScriptのデータもその計算に含まれていた(scriptCodeとして)。Scriptのサイズが増加するとメッセージダイジェストを計算するコストも比例して増加してしまうので、この計算リソースを限定するためにScriptのサイズに最大サイズの制限が設定されていた。Taprootでは、メッセージダイジェストを計算する際のデータ項目が変更され、直接Scriptをメッセージダイジェストに含めなくなったため、このリソース要件をなくした模様。ただ、実行するScriptがTaprootツリーのリーフハッシュと一致することを検証する必要はあるので、いずれにせよハッシュ計算は発生するんだけど。

BLS署名を利用した検証可能なwitness encryption

検証可能なwitness encryptionという新しい暗号プリミティブを利用してDLCを構成する新しい提案のペーパーが発表されてたので↓

https://eprint.iacr.org/2022/499.pdf

「II. TECHNICAL OVERVIEW」の内容を見てみた(まだ一部よく分かってない)。

BLS署名

ペーパーではBLS署名を利用したwitness encryptionスキームが提案されているので、まず前提となるBLS署名について。

ペアリング

BLS署名が利用しているペアリングは、同じ素数qを位数とした、2つの加法巡回群 {G_1, G_2} *1と乗法巡回群 {G_T} *2という3つの巡回群について、

 {e:G_1 \times G_2 \rightarrow G_T}

という関係が成立する写像のことを指す。つまり {G_1} {G_2}の各要素を入力として、 {G_T}の要素を出力できることを意味する。

 {G_1, G_2}については楕円曲線を利用するため、入力は {G_1, G_2}に対応する楕円曲線上の2つの点で、有限体 {G_T}の要素を出力することになる。このことから楕円ペアリングとも呼ばれる。

また、この時、 {G_1}楕円曲線の生成元をP、 {G_2}楕円曲線の生成元をQとした場合、任意の数値a, bが与えられた場合に、

 {e(aP, bQ) = e(bP, aQ) = e(P, Q)^{ab}}

が成立することを双線形性と呼ぶ。

BLS署名

ECDSAやSchnorr署名が1つの群、楕円曲線を使ったデジタル署名方式であるのに対し、BLS署名は↑の3つの群の関係を利用したデジタル署名方式になる。

 {G_1}の曲線の生成点をP、 {G_1}の曲線の生成点をQとした場合、BLS署名は以下のように作成される。

  • ランダムな数値 {x \in \mathbb Z_q}を選択し、これを秘密鍵とする。対応する公開鍵は {G_2}上の点Y = xQ
  • 署名対象のメッセージをmとした場合、 {\sigma = xH_1(m)}を計算する。ここで、 {H_1} {G_1}の曲線の要素を出力するハッシュ関数。この {\sigma}が署名で、かつ {G_1}の曲線上の点になる。

※ 署名方式によって公開鍵と署名に使用する際の {G_1, G_2}が逆になる場合もある。

署名の検証は、

  •  {e(\sigma, Q) = e(H_1(m), Y)}が成立するか検証する。

 {e(\sigma, Q)}は、ペアリングの双線型性から {e(xH_{1}(m), Q) = e(H_{1}(m), Q)^{x} = e(H_{1}(m), xQ) = e(H_{1}(m), Y)}と展開できる。右辺と左辺のペアリング関数の出力結果である有限体 {G_T}の要素が同じであれば検証をパスする。

つまりBLS署名はペアリングの双線形写像の特性を利用して秘密鍵の知識を証明する署名方式であることが分かる。また、ECDSAやSchnorr署名と違って署名の作成に乱数(nonce)を必要としない、決定論的な署名方式。

BLSベースのwitness encryption

検証可能なwitness encryptionに行く前に、前提となるBLSベースのwitness encryptionについて。BLSベースのwitness encryptionというのは、BLS署名を利用した暗号化スキームで、ある公開鍵とメッセージに対応するBLS署名が公開されたら、その署名を使って暗号化されたデータを復号できるというもの。

表記については以下を前提とする。

  • 暗号化対象のメッセージをmとする。
  • 署名に利用する公開鍵の鍵ペアをV = vQとする。vが秘密鍵で、Qは↑の {G_2}楕円曲線の生成点。
  • 署名対象のメッセージを {\tilde{m}}とする(これは暗号化対象のメッセージではない)。
  •  {H_1} {G_1}の要素(点)を出力するハッシュ関数
  •  {H_T} {G_T}の要素のハッシュ値を計算するハッシュ関数

公開鍵Vとメッセージ {\tilde{m}}に対して有効なBLS署名が提供されたら、メッセージmを復号できる暗号スキーム。

暗号化

以下の手順でメッセージmを暗号化する。

  1. ランダムな値 {r_1 \in \mathbb Z_q}を選択する。
  2. ランダムな値 {r_2 \in G_T}を選択する。
  3.  {c_1 = r_1P}とする。
  4.  {h = H_T(r_2)}とする。
  5.  {c_2 = e(V, H_1(\tilde{m}))^{r_1} \cdot r_2}とする。
  6.  {c_3 = h + m}とする。
  7. {c = (c_1, c_2, c_3)}を暗号文とする。

復号化

上記の暗号文は、Vとメッセージ {\tilde{m}}に対するBLS署名 {\tilde{\sigma}(= vH_1(\tilde{m}))}が公開されると、以下の手順で復号できる。

  1. {c = (c_1, c_2, c_3)}をパースする。
  2.  {r = c_2 \cdot e(c_1, \tilde{\sigma})^{-1}}を計算する。
  3.  {h = H_T(r)}を計算する。
  4.  {m = c_3 - h}が復号したメッセージとなる。

↑では、 {\tilde{\sigma} = vH_1(\tilde{m})}であるため、rの計算に出てくる {e(c_1, \tilde{\sigma})^{-1}}は、ペアリング関数の双線形性により、 {e(r_1P, vH_1(\tilde{m}))^{-1} = e(V, H_1(\tilde{m}))^{-r_1}}となる。

そして、 {c_2 = e(V, H_1(\tilde{m}))^{r_1} \cdot r_2}であるため {r = r_2}となり、 {h = H_T(r) = H_T(r_2)}であるため、 {c_3 - h}でメッセージmが入手できると。

復号のためには、h(つまり {r_2})の値が必要になり、それを算出するためには、 {c_2}内のペアリング関数部分を打ち消す必要があり、それをBLSの双線形性と乱数使ってワークするようにしてるの面白いな。

ということで、このスキームを利用すると、(オラクルなどの)ある公開鍵とあるメッセージに対応した署名を入手すると復号可能な暗号文を作成することができる。

条件付きの支払い

DLCが扱うのは、オラクルが証明可能なイベントの結果を条件に支払いを行う条件付き支払いをサポートするユースケース

ここでは、アリスがイベントの結果にコミットし、結果がコミットした値と同じ場合に、ボブに対して支払いをす条件付き支払いを考える。DLCでは、アダプター署名を利用して、署名を完成させるために必要なシークレットを復元するアプローチを採っている。

このような条件付き支払いを成立させるためには、

  • イベントの結果がコミットした内容である場合、ボブは必ず署名を入手することができる。
  • イベントの結果がコミットした内容でない場合、ボブが署名を入手することはできない。

ことを保証する必要がある。さらに追加で、オラクルを分散させて一定数のオラクルによる証明が提供された場合に、署名の入手を可能にする(閾値性)を考慮する必要があるが、今回はシンプルにオラクル1人のケースで考える。

検証可能なwitness encryption

↑の新しいソリューションとして提案されているのが検証可能なwitness encryptionという新しい暗号プリミティブを利用する方法。プロトコルの参加者(アリスとボブ)=ブロックチェーンレイヤーが使用する署名方式はSchnorr署名(もしくはECDSA)で、オラクルの署名方式はBLS署名。まず、前提として、

  • アリスの鍵ペアを {P_A = x_AG}とする。ここで、Gはsecp256k1などの楕円曲線の生成点。
  • ラクルであるオリビアの鍵ペアを {P_O = x_OQ}とする。ここで、Qは上記のペアリングの {G_2}楕円曲線の生成点。
  • アリスがボブに条件付き支払いをするメッセージ(トランザクション)をmとする。

アリスは秘密鍵 {x_A}を使ってメッセージに署名する。通常のSchnorr署名であれば、

  1. ランダムなnonce kを選択
  2. R = kGとする。
  3.  {s = k + H(P_A||R||m)x_A}を計算する。
  4. (R.x, s)が署名

この署名があれば、ボブは資金を手に入れられる。ただ、条件付き支払いなので、アリスは、 {T = tG}を使って、メッセージmに対する事前署名s'を生成する。

  •  {s' = k + t + H(m)x_A}

ボブには、(R, s)の代わりにアダプター署名 {(R, s', T)}を送る。アダプター署名を入手したボブは、tさえ分かれば、有効な署名sを導出できる。

その後は、

  1. アリスはtを暗号化した暗号文cをボブに送信する。この暗号化に↑のwitness encryptionを利用する。
  2. リビアがイベントeをメッセージとして、秘密鍵 {x_O}を使ってBLS署名を作成し、公開する。
  3. ボブはこの署名とcからtを抽出し、s = s' - tをして署名sを手に入れる。

というプロセスを実行するが*3、ここで問題になるのが、ボブがアリスからアダプター署名と暗号文cを受け取った際に、cが暗号化されているので、tが確かに暗号化されているのか検証する術がない点。この検証ができなければ、単にアリスを信頼するしかないということになるのでよろしくない。

そこで、Cut&Chooseという手法を使って、暗号化されたデータが有効なデータ形式であることを検証できるようにしたのが検証可能なwitness encryption。具体的には、アリスが暗号文cを生成する際に、単一のtの暗号文を作るのではなく、以下の手順でλ個の暗号文を作成する(λはセキュリティパラメーター)。

暗号化

t単体を暗号化するのではなく、λ個の乱数 {r_i}(i = 0..λ-1)を生成し、この各 {r_i}を↑のBLSベースのwitness encryptionで暗号化する。そして、このλ個の暗号文とは別に、

  1.  {r_i}について {s_i = r_i + t}を計算する(sym-cipherと呼ばれる)。
  2.  {r_i}について {R_i = r_iG}を計算する。

アリスは、λ個の暗号文と {R_i}とアダプター署名をボブに送信する。

Cut & Choose

その後、

  1. ボブは受け取ったλ個の暗号文と {R_i}からλ/2個のペアを選択して、選択したペアをアリスに伝える。
  2. アリスは、
    • ボブから受け取ったデータに対応する {r_i}の値とwitness encryptionで暗号化に使用した乱数値をボブに送信する。
    • 選択されなかった残りのλ/2個のペアについて、 {s_i}をボブに送信する。
  3. ボブは、
    • 選択したペアについて、 {r_i}をアリスから受け取り、前に受け取った {R_i}について {r_iG = R_i}が成立するか検証する。さらに、オラクルの公開鍵Vとメッセージ {\tilde{m}}およびアリスから受け取った乱数値を使って {r_i}の暗号化計算を行い、それがアリスが送ってきたものと一致するか検証する。これにより、アリスが送ってきた暗号文はすべて {r_i}が暗号化されているだろうことが検証できる。
    • 選択しなかったペアについて、前に受け取った {R_i}とTに対して、 {s_iG = R_i + T}が成立するか検証する。これによりアリスが作成したデータはすべて {s_i = r_i + t}の形式のデータだろうということが検証できる。

そして、オラクルが署名を公開すれば、アリスが開示しなかった {r_i}も復号できるので、 {t = s_i - r_i}を計算して、witness tを入手できるということみたい。

この辺りが、ペーパーの「II. TECHNICAL OVERVIEW」で説明されてるんだけど、これアリスが {r_i}を開示した方のパターンだと、ボブはsym-cipherもらってないからどうやってt計算するんだろう?この辺り、まだよく理解できてない。

ちなみにペーパーの方は、

  • Fiat-Shamir変換した非対話型への変換
  • Cut&Chooseのバッチ化
  • 分散オラクルの閾値

など、実用的な課題に対するプロトコルの拡張が続く。

*1:加法巡回群は、群の元がすべて生成元の整数倍で表現できる群

*2:乗法巡回群は、群の元がすべて生成元の冪乗で表現できる群

*3:イベントの結果に両者が合意していれば、tをそのまま渡して終了

x-only public keyの課題とワークアラウンドな回避策

ちょっと前のBitcoin Optechのニュースレターでx-only public keyの課題とその回避策について取り上げられていたので、詳しく調べてみた。

x-only public keyとは?

Bitcoinに導入されたTaprootでは、署名検証に使用する公開鍵に32バイトのx-only public keyという形式を採用した。

公開鍵はこれまで33バイトの圧縮公開鍵(楕円曲線の点のy座標の偶奇を示す1バイト+x座標32バイト)が使われてきたが、Taprootではy座標は常に偶数となるようルールを設けることで、y座標の1バイトを削除し32バイトの公開鍵を指定するようになった。これがx-only public key。なので、TaprootなUTXOを使用する場合は、以下のTaprootの構成要素でこのx-only public keyが適用される:

  • TaprootのscriptPubkeyであるOP_1 <公開鍵>で構成されるP2TRアウトプットの<公開鍵>部分。
  • ↑の公開鍵は、内部公開鍵 + tGで構成される。この時、
    • この計算時に内部公開鍵はy座標が偶数となる公開鍵として扱われる
    • tは、内部公開鍵のx座標とTaprootのスクリプトツリーのルートハッシュから作られるタグ付きハッシュで、t = H("TapTweak" || 内部公開鍵(x-only) || merkle root)
  • Taprootのスクリプトツリー内の各スクリプトに登場する公開鍵

x-only public keyの課題

x-only public keyにより、公開鍵が登場する際に1バイト分データを節約できるようになったけど、これによる課題も報告されている↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-September/019420.html

具体的には、TAPLEAF_UPDATE_VERIFY opcodeを導入してCovenantsをサポートするという提案で見られる。この提案自体は↓

techmedia-think.hatenablog.com

問題となるのは、TLUVで内部公開鍵を更新するケース。例えば、アリス(A)、ボブ(B)、キャロル(C)がP2TRのコインを共有するプールスキームを考える。

3人の公開鍵A、B、Cのy座標がすべて偶数で、かつA + B + C(内部公開鍵)のy座標も偶数のケースを考える。この場合、P2TRの公開鍵は、

Q = (A + B + C) + H("TapTweak" || (A + B + C) || root1)G

この段階で、Taprootのx-only public keyの要件を満たしていたとしても、プールからCが抜ける場合、更新後の内部公開鍵A + Bのy座標が偶数になるとは限らない。A + Bのy座標が奇数である場合、

Q' = -(A + B) + H("TapTweak" || -(A + B) || root2)G

のような変換が必要になる。ここまでは、まぁ変換すればいいだけと捉えても問題ないが、さらにBがプールから抜ける場合、-(A + B)からBを減算することになり、

Q'' = -A - 2B + H("TapTweak" || -A - 2B) || root3)G

となり、Bがプールから抜けても、keypath支払いをする場合、Bの協力が必要になってしまう。

この回避のために↑の投稿では、内部公開鍵のy座標が奇数になる場合はエラーにして、参加者のすべての鍵の組み合わせでy座標が偶数になるよう事前調整するという手法も提案されてる。参加者(公開鍵)の数をnとした場合、約2nの計算が必要になるとされている。nが30以下くらいであれば計算可能な範囲だけど、まぁそれでも計算コストはかかるのと、事前に鍵の組み合わせの検証を求めるのもハードル高いので、あまり現実的ではないように思える。

ワークアラウンドな回避策

これに対して、Tim Ruffingが提案したのがワークアラウンドな回避策↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-July/020663.html

この回避策は、内部公開鍵のy座標が偶数になるまで、ベースポイントGを加算するというもの。

Q = (A + B + C)からCが抜ける場合、Q'のy座標を偶数にするために、

Q' = A + B + G

とする。そして、さらにBが抜ける場合Q'' = A + Gのy座標が奇数であれば、さらに

Q'' = A + G + G = A + 2G

とするというもの。必ず1回Gを加算する訳ではなく、y座標が偶数になるまでGを加算する。↑の投稿では、平均1回の加算で成功する(証明はなし)だろうとしている。

すべての鍵の組み合わせを事前に計算するより、対応が簡単な方法だ。

TLUV自体は、まだ提案中のopcodeだけど、こういうコントラクトを作成するアプローチは十分考えられるので、結果的にx-only public keyはあまり良いアプローチではなかった感じかなー。