Develop with pleasure!

福岡でCloudとかBlockchainとか。

LitecoinでMimblewimbleが利用可能なMWEBチェーンにペグインしてみる

LitecoinはExtension Blockという手法を使ってMimblewimbleを導入し(MWEB)、mainnetで2022年5月22日にアクティベートされた。今回はそんなMimblewimbleを試してみる(mainnetじゃなくtestnetだけど)。

トランザクション構造が全く異なるMimblewimbleをソフトフォークでLitecoinに追加した仕組み(MWEB)およびMimblewimbleについては、↓GBECの動画や過去記事を参照:

Litecoin Core

LitecoinにMWEBのコンセンサスを実装したLitecoin Core v0.21.2をインストールする↓

github.com

今回は、testnetで起動しチェーンの同期が終わると、MWEBがアクティベートされてることを確認する↓

$ ./litecoin-cli getblockchaininfo
...
    "mweb": {
      "type": "bip8",
      "bip8": {
        "status": "active",
        "start_height": 2209536,
        "timeout_height": 2419200,
        "since": 2215584
      },
      "height": 2215584,
      "active": true
    }
...

コインの入手

Testnetのコインを入手する。最初にウォレットを作成して、アドレスを生成する。

$ ./litecoin-cli createwallet "default"
{
  "name": "default",
  "warning": ""
}
$ ./litecoin-cli getnewaddress
tltc1qzy3fzen7gvhazyqypwtfr2f0crj97wf5njv2hp

生成したアドレスで、LitecoinのtestnetのFaucetからコインを入手する。

MWEB

P2P関連の変更

Litecoin CoreのP2P関連のコードについては以下の変更が行われている模様:

  • ピアとのハンドシェイク時に、NODE_MWEB service flagを使って、MWEBをサポートしていることを通知
  • 新たにCompact Blockのバージョン3を定義し、cmpctblockメッセージでMWEBのブロックを含むブロックの伝播をサポート
  • inventoryのタイプに、MSG_MWEB_BLOCKMSG_MWEB_TXが追加され、MWEBのブロックやトランザクションの通知、伝播をサポート

Litecoin→MWEBへのペグイン

MWのトランザクションは、Litecoinの通常のブロックではなく、Extension Block側で処理される。まずは、通常のチェーンからMWEBのExtension Blockのチェーンにコインを移動(ペグイン)してみよう。

ステルスアドレス

ペグインするにあたって、MWEB用のアドレスを生成する。getnewaddress RPCに対してaddress_typemwebを指定する↓

$ ./litecoin-cli getnewaddress "" "mweb" 
tmweb1qq0h2drunehmgm55str9gp26xplhdwyekklc0g4l8kcqst0vxwv3z6qsx9up7zjmr0rurfpy95fmsx9k2pxs7at4u25nhsuz6dyqcu5030uh9vz0u

bech32エンコードされたアドレスが生成されているのが分かる。hrpは通常チェーンのP2WPKHやTaprootのアドレスとは違ってMWEBチェーン用にtmwebになってる。これはステルスアドレスで、witness programをデコードすると↓のデータになってるいる。

03eea68f93cdf68dd29058ca80ab460feed71336b7f0f457e7b60105bd8673222d02062f03e14b6378f8348485a2770316ca09a1eeaebc552778705a69018e51f17f

これは、以下の2つの公開鍵を連結したデータであることが分かる。

  • 03eea68f93cdf68dd29058ca80ab460feed71336b7f0f457e7b60105bd8673222d
  • 02062f03e14b6378f8348485a2770316ca09a1eeaebc552778705a69018e51f17f

Litecoinではデュアル・キー・ステルスアドレスでステルスアドレスを生成しているため、1つはスキャン用の公開鍵で、もう1つはこのコインを使用する際に使用する公開鍵になる。

ちなみに↑のステルスアドレスアドレスに対してdumpprivkeyを実行すると、後者の使用鍵の秘密鍵が取得できる。

MWEBへのペグインやMWEBでのコインの支払いには、基本的にこのステルスアドレスを使用することになる。

ペグイン・トランザクション

生成したアドレスに対して、Faucetで入手したコインを送ってみる↓

$ ./litecoin-cli sendtoaddress tmweb1qq0h2drunehmgm55str9gp26xplhdwyekklc0g4l8kcqst0vxwv3z6qsx9up7zjmr0rurfpy95fmsx9k2pxs7at4u25nhsuz6dyqcu5030uh9vz0u 0.0005
e091a837886c078e530bc7f50d5559ddb677d5e99bb94ef41021d99af7e4b9cb

このTxが標準チェーン→MWEBチェーンへコインを移動するペグイン・トランザクションで、そのアウトプットが↓

$ ./litecoin-cli  getrawtransaction e091a837886c078e530bc7f50d5559ddb677d5e99bb94ef41021d99af7e4b9cb 1
...
  "vout": [
    {
      "ismweb": false,
      "value": 0.00067400,
      "n": 0,
      "scriptPubKey": {
        "asm": "9 2ac1d7fcb62c17072e8ba34a3711eff346b3b7f4f937cacacafddde7301b701a",
        "hex": "59202ac1d7fcb62c17072e8ba34a3711eff346b3b7f4f937cacacafddde7301b701a",
        "type": "witness_mweb_pegin"
      }
    }
  ]

ここでscriptPubKeyに注目してみよう。通常、sendtoaddressでコインを送付すると、アウトプットのscriptPubkeyはsendtoaddressで指定したアドレスになるはずだが、ここでは全く違うsegwitアウトプットになっていることが分かる。このwitness programはMWEBブロックのペグイン・カーネルカーネルコミットメントの値を表しており、MWEB側のチェーンにLTCを移動する役割になる。

このペグイン・トランザクションのUTXO自体は、マイニングされたブロック内のHogExトランザクション↓ですぐに使用される。

ホグワーツ・エクスプレス

Extension Blockの仕様で、標準チェーン→EBへのペグイン、EB→標準チェーンへのペグアウトを処理するために作成されるのがインテグレーション・トランザクションで、標準ブロック内のトランザクションリストの最後に配置される。

LIIP-0003では、このインテグレーション・トランザクションを、Hogwarts Express(HogEx)トランザクション命名している。

↑のペグイントランザクションを含むブロックのHogExトランザクションは↓のような構成になっている。

$ ./litecoin-cli  getrawtransaction b941effb6e58795a1bcb0f27f5c3f75ee2325a247890d9897e594c9612c95ce1 1
{
  "txid": "b941effb6e58795a1bcb0f27f5c3f75ee2325a247890d9897e594c9612c95ce1",
  "hash": "b941effb6e58795a1bcb0f27f5c3f75ee2325a247890d9897e594c9612c95ce1",
  "version": 2,
  "size": 138,
  "vsize": 135,
  "weight": 540,
  "locktime": 0,
  "vin": [
    {
      "ismweb": false,
      "txid": "fdd51df3e001a542f9f2ef03612041b0192e42265972428437f0f5de23af93df",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967295
    },
    {
      "ismweb": false,
      "txid": "e091a837886c078e530bc7f50d5559ddb677d5e99bb94ef41021d99af7e4b9cb",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967295
    }
  ],
  "vout": [
    {
      "ismweb": false,
      "value": 556411.83427695,
      "n": 0,
      "scriptPubKey": {
        "asm": "8 bffeac085bb3249c38558008b99c825dc091058ed7aeb42d3143311621afb834",
        "hex": "5820bffeac085bb3249c38558008b99c825dc091058ed7aeb42d3143311621afb834",
        "type": "witness_mweb_hogaddr"
      }
    }
  ],
  "hex": "02000000000802df93af23def5f0378442725926422e19b041206103eff2f942a501e0f31dd5fd0000000000ffffffffcbb9e4f79ad92110f44eb99be9d577b6dd59550df5c70b538e076c8837a891e00000000000ffffffff016f1cf9f89a320000225820bffeac085bb3249c38558008b99c825dc091058ed7aeb42d3143311621afb8340000000000",
  "blockhash": "a91e4217f411821e3e98a9e235dc76e1672fea4ddfd119426f5ed8742c4d41f9",
  "confirmations": 4680,
  "time": 1653051210,
  "blocktime": 1653051210
}

ここで、インテグレーション・トランザクションのインプット数は、ブロック内のペグイン・トランザクションの数 + 1で、アウトプットの数はブロック内のペグアウト・トランザクションの数 + 1であるため、このブロックには、自分がペグインしたトランザクションしかないことが分かる。

最初のインプットは前のブロックのExtAddr UTXO*1。2つめのアウトプットを見ると、↑で作成したペグイン・トランザクションのUTXOであることが分かる。

このブロックにはペグアウト・トランザクションは無いので、アウトプットはこのブロック時点でEBにあるコインの総量を表すExtAddrアウトプットのみ。このscriptPubykeyは、

OP_8 bffeac085bb3249c38558008b99c825dc091058ed7aeb42d3143311621afb834

と、witness versionがOP_8で、witness programはこのトランザクションが含まれるブロックに対応するMWEB側のブロックのハッシュ値と一致する。ちなみにこのアウトプットはLIP-0002ではExtension Addressとして定義されているもので、MWEBではホグワーツアドレス(HogAddr)と命名している。

この1つの前のブロックのインテグレーション・トランザクションのExtAddr UTXOが保持するコインの量が556411.83364195なので、0.000635がEBチェーンに移動している。なお、MWEB側のマイニングの手数料は全て、このHogExトランザクションで徴収されるようになっている。

Extension Block

getbock RPCを使うと標準チェーンのブロックの情報に加えて、MWEBのブロック情報も確認できるようになっている。その際、verbosityを2で指定すると、MWEBブロックのインプットやアウトプットの詳細も確認できる。

↑のペグイン・トランザクションが含まれるMWEBブロックは↓

$ ./litecoin-cli  getblock a91e4217f411821e3e98a9e235dc76e1672fea4ddfd119426f5ed8742c4d41f9 2
{
...
"mweb": {
    "hash": "bffeac085bb3249c38558008b99c825dc091058ed7aeb42d3143311621afb834",
    "height": 2344901,
    "kernel_offset": "f53d32b816b823d579b6cfde70e0db41da88f313fe5d328577cc81287d2bcbe1",
    "stealth_offset": "7b9f50585e9ed0af0a09815bd1db86ff99e3f4f5b7e20bfa1fd53065ed213c6f",
    "num_kernels": 1,
    "num_txos": 3498,
    "kernel_root": "7ea915a3bbd5baf771e21a58ec674f423d3fcc115a0cbd14d46a3001ae92c364",
    "output_root": "7d78fedf65359ba2c83a4374bf10593b1eeb715a127a3b775bf2f226e4643e02",
    "leaf_root": "c8b998f21bb2009320916422a7784cb1d139da25ee981bff653c06c4e8d8d53f",
    "inputs": [
    ],
    "outputs": [
      {
        "output_id": "147785fb93659118be70445d947496dbedd7983086446f73d5f803eec2ff7691",
        "commit": "09db9a47459753159ec66cc85fb35baf6fb2d16fb3062c860fb7cfc559fcbe2f0b",
        "sender_pubkey": "03414cf1b5c709f228dbae62706400baf82fffca94676e2975c3be2f3700e3efc3",
        "receiver_pubkey": "0230a1f2999419e1e745fdde8f67cda99064a9f17732f0768997e982511d836b6f",
        "range_proof": "37d5d12d300c3159eedb5ec207ca3108e1a4e7afe9b1831273e775f641d3a5dcb812ffb48ef7e369b63c198fcf646ecd700303ba9325ab7ca127510e8be124b801c38b04dbe0899555cb5fd8274f8c841d3a53fc15b3d0cbfd383b0ea2e7939f20a012f5edf7954cb9e8ec42aadefd0404d7698bd6164e3832f4d6454070bea5ea11ba97fb41ff0565d468e7ef0463151c6e2784c53f72d9c5e819a0b1df8c959597df8bea0eef6a768da1b5b71adf07e66a250b8096876e97e40fc5148b99b06968bf0b7cb08d8f6b20783b954ffb60fe430f2d500656cda59ff473fdb64013348edba2a29dcc8de5edb84050343ee528709f0fe9e1af31026c708290c7c68236deb4c2d85b8927f8204f2e37dce349dd69d717c7fe0b9986c75345693777608c51335fa5301e2d166ff5ac5ce021b2009abccd20997752099d2c39b829505531feab7a26d2592066ba7f10ed80081ad72a8f694ea2c2d9b4a893b60921cca915cf01b110b040d64fe5249fbd3eeaa0e6a73054b78f85d1228340b15c03730816cfa10d11a4a92bee916626a84cb4b1c352b91e8ef7f1b4202881145863051d0297d417383c6dfc97d3410d234d795476d1196e7daa5c8923a06a419387b91f3168bbf780683031759f0a5d1d9c12312547157446c986050550a412b12ffb5c2a0bf7acd111c524c0babe4edbef0a4c35f6ed24267f3441270790f18e844e015f8b67f0fa6ec5e3d2afb1cacb25aa1409a639a9254580b26c680a48c10e6572d3520bc565816e9432a8fa2752c0701d86808e6ed5f802976fb635c3f189932fceda2478fa16b22b1b6cd5c68bf3c3a930372442350f8974259c5711dac7433b4e175bcd3276dbc328361297e503a82fb25687a563dd112661786d270e80ea8c5c6c73cbc8ae864c9ffa9686772cb78c3cabb3a7a5c00cc16efcd044533bb04b3b44c5",
        "message": "01035efb14bd692a54b188abb3e1db529b7d7e4037b4367488b02e70efec67b810cf10892bd871463f2a12ea7157450f50ddc1edce1195afa2795e"
      },
      {
        "output_id": "a5cd2f891fb43046db53245881ca7c5e5b8bd2f6d36c44bfd6a107480d9c145a",
        "commit": "099f5fded238f7122ad54048bec596a8ea3fe7d4d90834ca50d2cb2cbb6eb17a3b",
        "sender_pubkey": "037f92823e0a59c99d91b26eae4d5c6eb6629e2d0993b9db9ff41e93319e5a82f8",
        "receiver_pubkey": "03356ee34bb852bb5d871dc00df708f6c5ade5dca081fc734a0368325de39fb241",
        "range_proof": "7b4dacdb883036e8cbced235159ba50d5b0f99ca0dbbf10b29317ff7814d7a8a837d14ead5b79616e43c5ddc0e68b21e3aae76ef0c9201e2b6d6da557eeac9c50135898a289e16e5269ff6ef44c28840384a2a32ba405dff7b4f7e454912589d987945705198c0ebe8040e7f7939ff9d2bb1b9f74104a773f2c5c8bf525832462a94a5e42e1aca1a4e9d637c2e1ebdf40f84b7503e926f9cac1209a8f385c9d9b5f5db3a5db0d42d047e938ddadbbb97b590c502d066eb1b1804a6f2517ebc358b82e9cfcbfeb4f0006fd29cc27e9219879c364b537aaf5ffea8f6844f044e50e681da9ae9ed4baa09282f1dd38518a9d3cba4ea5fb36bec6ac992f5e58e068ff04ed2df14c09da9cd18415c6a9ce3a0980f7931d20f0c9f6af2bfc91240b07a73ca1408b98e92b81911d0a05f4c95fa6f6dd2e1b250f91adcd1f8224730ccb5228021135aa40eeb04720be905852cc9f3de188718f709b81c210ded15628e181415028882ed97f2845b0504a781e539394b6f51f4a819870ac77e476b8820e5c56066fe53d5713b28a7f9f53810ef440f6435d03b27b43e9805db170cb748b624258a358386e647bf0dbfbe8b9b4d4847351723ed412aa6176d887196248c3fab24b05e8f6884ee6290131762ef7b3f995eeab0c8cf1a4618d244c40dd4196ea3a151b3cba8c4605b97f494b1f703acb50ec88e353c4531f9e9ff6585d63d3199372d3d22adcd10da885a9d17de6ce22973f08a2ea3d41d6a2760f799af5c01ca29415516e54a50d452f990421497e066311f2f4632edf7f853c07f2ea8adcf1873b02550fb9eb7a79e4ddafe41e77e4df95f83bac8329b9c170a64daec92f3bf42e2bdc583127fca1333fac98f1e206ced37bab4d5c115a42d3593a4dee44f196854824f6a0406f07d7206a87b6a41d752f3b9eeddd78123e60f9f474637bd5cf5a8",
        "message": "0103e5661d3743eb97e26eabecf67f020aaf4c6d6e27775be2d694bc702d266f47ca399fb31d3347d549537d3ce3aa7bdc1c837fea0b3bee61b93a"
      }
    ],
    "kernels": [
      {
        "kernel_id": "2ac1d7fcb62c17072e8ba34a3711eff346b3b7f4f937cacacafddde7301b701a",
        "features": 19,
        "commit": "0976f36bfc5f1a0f354fd9a3f829220a09f38c3118625b97829833fd242d00f756",
        "fee": 3900,
        "lock_height": 0,
        "excess": "0976f36bfc5f1a0f354fd9a3f829220a09f38c3118625b97829833fd242d00f756",
        "signature": "1033b9f23eb987efe0a4246e88864652f2ff2c8fd0a70ec81df6c904f48e1ceca7899103f22ba183c393fec13a262c6e1c881507402351d1c1050b70423ef923"
      }
    ]
  }
...

ここで、カーネルのデータに注目する。kernel_id: 2ac1d7fcb62c17072e8ba34a3711eff346b3b7f4f937cacacafddde7301b701aは、↑のペグイン・トランザクションのwitness programと一致しているのが分かる。標準チェーンからMWEBチェーンへの移動でマイナーがコインを不正な宛先に送れらないよう、MWEBのブロックのカーネルには、対応する標準チェーンのペグイン・トランザクションのコミットメント値が含まれるようになっている。

ここまでの一連のデータが、LIP-0003の↓の図のペグイン(緑色)の部分のデータになる。

https://github.com/litecoin-project/lips/raw/master/lip-0003/MW-EB.png

ペグイン後のUTXO

ちなみに、↑ペグインの際にsendtoaddressで0.0005送ったところ、↑のペグイン・トランザクションのアウトプットの値は、0.00067400になっており、listunspentすると2つUTXOが返ってくる↓

$ ./litecoin-cli listunspent
[
  {
    "txid": "e091a837886c078e530bc7f50d5559ddb677d5e99bb94ef41021d99af7e4b9cb",
    "amount": 0.00050000,
    "confirmations": 44,
    "spendable": true,
    "address": "tmweb1qq0h2drunehmgm55str9gp26xplhdwyekklc0g4l8kcqst0vxwv3z6qsx9up7zjmr0rurfpy95fmsx9k2pxs7at4u25nhsuz6dyqcu5030uh9vz0u",
    "label": ""
  },
  {
    "txid": "e091a837886c078e530bc7f50d5559ddb677d5e99bb94ef41021d99af7e4b9cb",
    "amount": 0.00013500,
    "confirmations": 44,
    "spendable": true,
    "address": "tmweb1qqwwlz6l4rdrxfpc0gvch6jtyyyav2tda8mgx6utjgy5zsfvxdcdegqmr0erv0drpnywetc5ekggnupd7thj6ue2z35tz90fu3g286fv3zcgn8zew"
  }
]

ただ通常のUTXOとは少し変わっていて、アウトプットのインデックスはなく、両方とも同じ↑のペグイン・トランザクションを参照してる。1つは、送金額と同じ0.0005で、もう1つは、0.000135。↑のペグイン・トランザクションがマイニングされたブロックのペグイン・カーネルの手数料が0.000039になってるので、これらを全て合算すると、ペグイン・トランザクションのアウトプットの額と一致する。

不思議なのは、ペグインしたMWEB側のUTXOが送金額を指定した0.0005だけでなく複数になっている点。単純に1つだけだと、そのコインの量が分かってしまうので、ブラインドするために最低2つのUTXOが作られてるのか?この辺りの挙動含めて、まだあまりドキュメントに書いてないのでよくわからな部分も多い。

長くなったので、MWEBでの送金やペグアウトについては、また別の記事で。

*1:EB側のチェーンに移動したコインを標準チェーン側でロックしておくためのUTXO

Taroのアセットツリーの構造

Lightning Labsが発表したBitcoin上の新しいアセットプロトコルTaroについて、今回はTaroのアセットツリー周りのデータ構造/表現についてみていく。

Taroのアセットツリー

Taroは、Taprootを利用したアセットのオーバーレイプロトコルになる(TaprootベースのオーバーレイプロトコルはTaroがおそらく初)。なのでTaroを理解する場合、Taprootの知識があった方がいい↓

Taprootのアウトプットは32バイトの公開鍵だが、この公開鍵は、内部公開鍵(Key-Path)とスクリプトツリー(Script-Path)で構成されている。Taroのアセットは、この内、スクリプトツリー内の構造化されたデータへのコミットメントとして表される。

Taroのアセットツリーは、Merkle-Sum Sparse Merkle Treeというデータ構造のツリーになる↓

techmedia-think.hatenablog.com

Taroのアセットツリーは、以下のような2階層のMS-SMTで構成される。

Taro Asset Tree

1階層めは、アセットIDまたはアセットキーファミリーをキーとしたMS-SMT。このツリーのリーフの値は↓

taro_version || asset_id_tree_root || asset_sum

つまり、アセットIDをキーにして、対応するアセットの合計量(asset_sum)と、asset_id_tree_rootをルートとする2階層めのツリーのルートコミットメントおよびtaro_versionから構成されるリーフノードをマッピングしている。

そして2階層めが、アセット毎に作成されるMS-SMT。キーはAsset Script Keyで、リーフは、asset_leafとリーフが保持するそのアセットの量(leaf_sum)で構成される。つまり、あるキーが保持しているアセットの残高を保持するツリーになる。

asset_leaf || leaf_sum

asset_leafは、TLV形式のデータで、以下のデータが現在定義されている。

  • taro_version:使用するTaroのバージョン
  • asset_id:アセットID
  • asset_type:アセットのタイプ(0:通常のアセット、1:収集品)
  • amt:このリーフが保持するアセットの量
  • lock_time:アセットを移動可能なタイムロック
  • prev_asset_witnesses:ネストされたTLVで、対象となるアセットリーフへのマージを検証するためのアセットwitnessを含む。
  • split_commitment:通常のアセットについて、新しいアウトプットの分割の検証を許可するために使用。
  • asset_script_version:以下のTLV値の検証を方法を管理する2バイトのアセットスクリプトバージョン。
  • asset_script_key:このアセットリーフを包含するアセットスクリプトにコミット可能なBIP341方式で導出された外部公開鍵。
  • asset_family_key:BIP340で定義された32バイトの公開鍵、で、assert_idに対する64バイトのBIP340署名が続く。
  • TODO(まだ作業中っぽい)

なお、Asset Script Keyは、BIP341形式の32バイトの公開鍵。なので、2階層めも1階層めと同様に高さ256のツリーになる。

↑のようにアセットの保持状況をネストしたMS-SMTにエンコードして、そのルートハッシュをTaprootのスクリプトツリーにコミットしてるっぽい。

アセットID

↑で既に登場してるけど、オーバーレイプロトコルとしてアセットプロトコルを定義する場合、各アセットを識別するためのIDをどう導出するかを決める必要がある。Taroでは、アセットIDは以下のように計算される32バイトのデータになる。

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

ここで、

  • genesis_outpoint: アセット発行トランザクションで使用されるインプットが参照するUTXOのOutPoint。
  • asset_tag: 特定のアセットを表現するランダムな32バイトの値。複数のアセットを1つのアセットファミリーとしてリンクする際に使用されるタグで、実際にはアセット名のハッシュ値が設定される。
  • asset_meta: 外部リンクやドキュメント、属性値、画像などのメタデータにコミットするために使われるメタデータハッシュ値(32バイト)。
  • output_index: ジェネシストランザクション内で一意なTaroコミットメントを含むアウトプットのインデックス(4バイト)
  • asset_type: アセットのタイプ(1バイト)

この内、genesis_outpointによってアセットIDの一意性が担保される。

参考

次は、アセットの作成や転送の仕組みについて。

Fiat-Shamir変換の安全でない適用による脆弱性Frozen Heart

最近公開された、Fiat-Shamir変換を正しく適用できていないプロトコルや実装において、証明システムの偽造が可能になる脆弱性「Frozen Heart」について↓

blog.trailofbits.com

Fiat-Shamir変換とは?

Fiat-Shamir変換は、証明システムを非対話型にするために使用される有名なスキームで、検証者がランダムに選択するチャレンジの値を(ランダムオラクルモデルとして)暗号学的ハッシュ関数を使って決定論的に導出することで、証明システムのプロトコルを非対話型にする。

シンプルな適用例としては、RFC8235として定義されているSchnorr署名を使って離散対数の知識を知っていることをゼロ知識で証明するプロトコルとか↓

techmedia-think.hatenablog.com

RFC8235の概要は↓(簡略化のため、modの計算や群内の存在確認などは省略)

アリスがP = aGとなる公開鍵Pに対する離散対数(a)の知識をボブに証明したい場合。以下のステップで非対話的に証明する:

  1. アリスはランダムな値vを選択し、V = vGを計算
  2. アリスは暗号学的ハッシュ関数(H)を使ってチャレンジ c = H(G || V || P || UserID || OtherInfo)を計算する。
  3. アリスはr = v - c * aを計算
  4. (P, V, r)をボブに送る。

これに対しボブは、渡された情報(P, V, r, UserID, OtherInfo)からcを計算してV = rG + cPが成立するか検証する。

チャレンジcの値をボブがランダムに作って渡すのではなく↑のようにルールに従って生成することで、チャレンジのやり取りの対話を省略することができる。

Fiat-Shamir変換のポイント

↑のレポートにかかれているけど、Fiat-Shamir変換を適用する際のポイントは、チャレンジのハッシュ計算の際の入力に、証明するステートメントに関するすべての公開値(ランダムなコミットメント値を含む)を含める必要があるということ(↑の例だと入力は、G、V、P、UserID、OtherInfo)。

Frozen Heart

Frozen Heartは、↑のFiat-Shamir変換のポイントを遵守していないプロトコルや実装による脆弱性

↑のRFC8235の例で考えてみよう。例えばチャレンジの計算にVが含まれていないとどうなるか?

  1. チャレンジ c = H(G || P || UserID || OtherInfo)を計算する。
  2. rにランダムな値を設定する。
  3. V = rG + cPを計算する。

こうやって後付けで辻褄があうように算出したVを含む(P, V, r)を検証者に送ると、V = rG + cPのチェックをパスすることが分かる。この時、証明者はV = vGとなるVの離散対数vを知らず、Pの離散対数aも知ることなく、検証をパスする証明を作成できてしまう。

Vがチャレンジのハッシュ計算に含まれていれば、こういった偽造はできない。これが↑のFiat-Shamir変換をする際の重要なポイント。

Frozen Heartの影響を受けるプロトコル/実装

Frozen Heartの脆弱性があるのは、プロトコル自体やその実装が、↑Fiat-Shamir変換のポイントを正しく行っていないケース。

↑のレポートでは、Giraultの知識証明と、値の範囲証明によく使われているBulletproofs、zk-SNARKベースの証明システムPlonKにおける脆弱性が取り上げられている。中でも影響度が大きいのは、BulletproofsとPlonKだろう。

Bulletproofsは、元の論文の非対話型プロトコルに問題があり、楕円曲線の群の位数の範囲内の値に対して証明の偽造が可能で、対象としていた範囲外の値に対して有効な範囲証明が作れてしまう。対象のプロダクトとしては、 Adjoint, Inc.のbulletproofsが取り上げられている。ちなみにMoneroの実装では脆弱性は回避されてるっぽい(Grinはどうなんだろう?)。偽造方法の詳細について、後続のレポートで解説されてる。

PlonKは、論文でFiat-Shamir変換の計算方法を明示的に説明せず、transcriptをハッシュ化するよう記載しており、その内容を明示的に記載していないことから、Dusk Networkのplonk、iden3のSnarkJS、ConsensysのgnarkでFrozen Heartの脆弱性が報告されている。具体的には算術回路への入力値をFiat-Shamirの計算に含めなかったことで、証明の偽造が可能になっていた。つまり、プログラムが正しく実行されたことが保証されなくなってしまう。具体的な偽造手順は、後続のレポートで解説されてる。

PlonKに限らず他の論文でもメインの内容は証明システムの新しい発明であって、それを非対話型にするのにFiat-Shamir変換を使うことがおまけ的に書いてあることは多いので、論文だけ読んでプロダクト実装しても脆弱性が含まれるケースは十分考えられる。zkは機能面ばかりフィーチャーされる傾向にあるけど、透過的なプロトコルと比べて脆弱性やバグがあっても発見し辛いので、このあたりのトレードオフはちゃんと評価する必要がある。

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とかも同じ