Develop with pleasure!

福岡でCloudとかBlockchainとか。

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はあまり良いアプローチではなかった感じかなー。

IONのDIDのリカバリーと無効化操作をアンカリングしてみる

techmedia-think.hatenablog.com

techmedia-think.hatenablog.com

ときたので、残りのRecoverおよびDeactivate操作をアンカリングしてみる。

Recover操作

Recoverは、Update Keyの更新とRecovery Key自体の更新および、DID State Patcheで定義したDID Documentに対する変更を適用する操作になる。DID Documentの更新という意味ではUpdate操作と似ているけど、Update Keyを紛失したり盗まれたとしても、Recovery Keyがあれば(制御下にあれば)、Recover操作によるDIDの更新で、DIDの管理が引き続き可能。一方、Recovery Keyを紛失してしまうと、既存のUpdate KeyによりDIDの更新だけは引き続き可能だけど、盗まれてしまうとDIDの制御権を奪われることになる。そういう意味でRecover Keyの管理の方が重要度が高い。

実際にRecover操作で、DID Documentを更新してみよう。手順は↓

  1. 新しいRecovery Keyを生成
  2. 新しいUpdate Keyを生成
  3. DID Documentに対する変更を定義したDID State Patcheを作成する。今回は新しい署名鍵を生成し、現在のDIDの署名鍵を新しい鍵に置き換えるreplaceアクションを適用。
  4. 2のUpdate Keyのコミットメントと、3のPatchからRecovery Operation Delta Objectを作成。
  5. 4のデータのハッシュと現在のRecovery Keyのデータ、新しいRecovery KeyのコミットメントからRecovery Operation Signed Data Objectを作成。
  6. 5のデータに対して、現在のRecovery Keyで署名したJWSを生成。
  7. JWSデータを使って、Core Proof Fileを作成し、IPFSにアンカリングする。
  8. 4のDeltaオブジェクトを使って、Chunk Fileを作成し、IPFSにアンカリングする。
  9. 8のChunk FileのURIを含む、Provisional Index Fileを作成し、IPFSにアンカリングする。
  10. 9のProvisional Index FileのURIと、7のCore Proof FileのURI、現在のDIDにコミットされているRecovery Keyのコミットメントに対応するReveal ValueからCore Index Fileを作成し、IPFSにアンカリングする。
  11. Core Index FileのURIからAnchor Stringを生成し、それをBitcoinにアンカリングする。

Update操作との違いは、

  • プルーフはProvisional Proof Fileではなく、Core Proof Fileにセット。
  • Recover操作によるDID Documentの変更の差分(delta)や、更新に使用する鍵のReveal Valueは、Provisional Index FileではなくCore Index Fileに配置。

あたりかな。この辺りのデータの配置先をUpdateとRecover/Deactivateでそれぞれ分離するメリットってどこにあるんだろう?同じファイルや方法で扱えた方がシンプルで便利だと思うんだけど。

以下、実際にRecover操作をCASにアンカリングしたコード↓

require 'sidetree'

Sidetree::Params.network = Sidetree::Params::Network::TESTNET

# DIDのsuffix
did_suffix = "EiBRrmEha_Q30GieEwLB-XM8CZd_b49dQ7znhaBxfAHTsQ"

# 現在設定されているRecovery Key
recovery_key =
  Sidetree::Key.new(
    private_key:
      45_036_086_779_068_677_123_348_498_811_216_758_728_966_810_636_876_259_204_257_311_947_782_243_979_294
  )
# 新しいRecovery Keyを生成
new_recovery_key = Sidetree::Key.generate

# 新しいUpdate Keyを生成
new_update_key = Sidetree::Key.generate

# 新しい署名鍵を生成
new_signing_key = Sidetree::Key.generate(id: "signing-key")

# 置き換えるDID Documentを生成
document = Sidetree::Model::Document.new(public_keys: [new_signing_key])
delta =
  Sidetree::Model::Delta.new(
    [document.to_replace_patch],
    new_update_key.to_commitment
  )
# JWSを生成して現在のRecovery Keyで署名
claim = {
  recoveryKey: recovery_key.to_jwk.normalize,
  recoveryCommitment: new_recovery_key.to_commitment,
  deltaHash: delta.to_hash
}
jws = Sidetree::Util::JWS.sign(claim, recovery_key)

ipfs = Sidetree::CAS::IPFS.new

# Core Proof Fileを作成
core_proof_file = Sidetree::Model::CoreProofFile.new(recover_proofs: [jws])
core_proof_file_uri = ipfs.write(core_proof_file.to_compress)

# Recover Operationを作成
recover_op =
  Sidetree::OP::Recover.new(
    did_suffix,
    delta,
    jws,
    recovery_key.to_reveal_value
  )

# Chunk Fileを作成
chunk_file =
  Sidetree::Model::ChunkFile.create_from_ops(recover_ops: [recover_op])
chunk_file_uri = ipfs.write(chunk_file.to_compress)

# Provisional Index Fileを作成
provisional_index_file =
  Sidetree::Model::ProvisionalIndexFile.new(
    chunks: [Sidetree::Model::Chunk.new(chunk_file_uri)]
  )
provisional_index_file_uri = ipfs.write(provisional_index_file.to_compress)

# Core Index Fileを作成
core_index_file =
  Sidetree::Model::CoreIndexFile.new(
    provisional_index_file_uri: provisional_index_file_uri,
    core_proof_file_uri: core_proof_file_uri,
    recover_ops: [recover_op]
  )
core_index_file_uri = ipfs.write(core_index_file.to_compress)

anchor_str =
  Sidetree::Util::AnchoredDataSerializer.serialize(1, core_index_file_uri)

Anchor Stringは、

ion:1.QmT2UBzXXsk4gjmUPYvFkQLXgZayfEUq5hpUEGjVRFphgt

で、アンカリングしたBitcoinトランザクションは、8ed80cf58094d12c4fca6dd9fb2ae136278e78afbd65fa108a5db961f762f7ae。ブロックに取り込まれると、IONのResolverでもDID Documentの更新が確認できる↓

DID Document(署名鍵)に加えて、Recovery Commitment、Update Commitmentが更新されている。

Deactivate操作

Deactivate操作は、Recovery Keyを使ってDID Documentを無効化する操作になる。

手順は、他の操作よりシンプルで、

  1. 無効化対象のDIDのSuffixとRecovery KeyでDeactivate Operation Signed Data Objectを作成
  2. 1のデータに対して、現在のRecovery Keyで署名したJWSを生成。
  3. JWSデータを使って、Core Proof Fileを作成し、IPFSにアンカリングする。
  4. 3のCore Proof FileのURI、現在のDIDにコミットされているRecovery Keyのコミットメントに対応するReveal ValueからCore Index Fileを作成し、IPFSにアンカリングする。
  5. Core Index FileのURIからAnchor Stringを生成し、それをBitcoinにアンカリングする。

DID Documentの更新がないので、Provisional Index FileやChunk Fileが不要になる。

require 'sidetree'

Sidetree::Params.network = Sidetree::Params::Network::TESTNET

# 現在設定されているRecovery Key
recovery_key =
  Sidetree::Key.new(
    private_key:
      22_121_807_773_082_901_989_880_604_296_336_998_182_556_647_810_161_279_933_493_862_174_847_957_422_871
  )

# JWSを生成して現在のRecovery Keyで署名
claim = {
  didSuffix: did_suffix,
  recoveryKey: recovery_key.to_jwk.normalize
}
jws = Sidetree::Util::JWS.sign(claim, recovery_key)

ipfs = Sidetree::CAS::IPFS.new

# Core Proof Fileを作成
core_proof_file = Sidetree::Model::CoreProofFile.new(deactivate_proofs: [jws])
core_proof_file_uri = ipfs.write(core_proof_file.to_compress)

# Deactivate Operationを作成
deactivate_op =
  Sidetree::OP::Deactivate.new(
    did_suffix,
    jws,
    recovery_key.to_reveal_value
  )

# Core Index Fileを作成
core_index_file =
  Sidetree::Model::CoreIndexFile.new(
    core_proof_file_uri: core_proof_file_uri,
    deactivate_ops: [deactivate_op]
  )
core_index_file_uri = ipfs.write(core_index_file.to_compress)

anchor_str =
  Sidetree::Util::AnchoredDataSerializer.serialize(1, core_index_file_uri)

Anchor Stringは、

ion:1.QmWmJ5HWVvga46CcGkem7JTxMZtJrVtsuQDaPmRf3Pi54V

で、アンカリングしたBitcoinトランザクションは、1c18fc397aebd5c1ee0d12a973d8e9fb01d2c2945bf965508480efc422e78a23。ブロックに取り込まれると、IONのResolverでもDID Documentが無効化されたことが分かる(DID Documentの鍵やserviceが削除されている)↓

ということで、Sidetreeに定義された一連の操作(Create / Update / Recover / Deactivate)を一通りやってみた。

ブロックチェーンにアンカリングしたデータを使ってオフチェーンプロトコルを動作させるというコンセプトはやっぱり面白い。ブロックチェーンで担保するのはデータの適用順序だけ、後はオフチェーンのコントラクトやプロトコルで解決する。

IONのDIDを更新してみる

前回の記事でIONのDIDを登録したので↓

techmedia-think.hatenablog.com

今回は、登録したDIDの鍵を更新するUpdate操作をアンカリングしてみる。

Update操作

Update操作は、現在DIDに紐付けられているUpdate Keyを使ってDID Documentの更新(署名鍵やserviceの追加、削除など)を行う操作になる。更新の対象や内容は、DID State Patchesで定義する。

今回は、DIDに署名鍵として登録した公開鍵を新しい公開鍵に更新するreplaceアクションを行うことにする(Patchは複数設定することも可能)。

今回のUpdate操作に必要な手順は↓

  1. 新しい署名用の鍵ペアを生成する。
  2. 1の公開鍵のデータを元に、replaceを行うDID State Patcheを生成する。
  3. DIDに紐付ける新しいUpdate Keyを生成する(このUpdate Keyは、この更新後のDIDのステートを更新する際に使用されるUpdate Keyになる)。なので、更新用の鍵はワンタイムの鍵ということになる。
  4. 3の新しいUpdate Keyのコミットメントを生成する。
  5. 2と4のデータからUpdate Operation Delta Objectを生成する。
  6. 現在のUpdate Keyを使って、JWSデータを生成する。
    • ヘッダーはalg: ES256Kのみ指定。
    • JWSのペイロードは、以下の2つの要素で構成される。
      • 現在のUpdate KeyのデータであるupdateKey
      • 5のUpdate Operation Delta Objectのハッシュ値であるdeltaHash
    • ↑のデータに対して、現在のUpdate Keyで署名した署名値をセットする。
  7. 6のJWSのデータを使って、(Create操作では不要だった)Provisional Proof Fileを生成して、IPFSにアンカリングする。
  8. 5のdeltaファイルからChunk Fileを生成して、IPFSにアンカリングする。
  9. 以下のデータからProvisional Index Fileを生成して、IPFSにアンカリングする。
    • 7のProvisional Proof FileのURI
    • 8のChunk FileのURI
    • 更新対象のDID Suffix(Short-Form形式のDID)
    • 現在のDIDにコミットされているUpdate Keyのコミットメントに対応するReveal Value(JWKのSHA-256 Multihash。コミットメントはdoubule-SHA-256されてる)。
  10. 9のProvisional Index FileのURIを指定して、Core Index Fileを生成し、IPFSにアンカリングする。
  11. 10のCore Index FileのURIからAnchor Stringを生成し、それをBitcoinにアンカリングする。

前回のCreate操作と違うのは、Update操作が可能なことを暗号学的に証明するためのJWSの生成と、それをCASにアンカリングするためのProvisional Proof Fileの作成。

実際に操作を実行

前回登録したDIDを更新しようとしたんだけど、いろいろ試行錯誤して試してたら、

{
code: "canonicalized_object_hash_mismatch",
message: "Canonicalized update request update key object hash does not match expected hash 'EiDBQ56irlBskr7ZawFLcoH131ZvSLbfa2jK1MOny-feIQ'."
}

というエラー以降、更新できなくなってしまったので、新しいDIDを作成して(did:ion:test:EiBRrmEha_Q30GieEwLB-XM8CZd_b49dQ7znhaBxfAHTsQ)↓

こちらを更新することにする。Update処理のサポートをsidetreerbに実装して、↓を実行

require 'sidetree'

Sidetree::Params.network = Sidetree::Params::Network::TESTNET

did = generate_did # ↑で新規作成したSidetree::DIDオブジェクト(作成方法は前回の記事参照)

# DID新規作成時に設定したUpdate Key
update_key =
  Sidetree::Key.new(
    private_key:
      30_922_012_418_511_471_117_584_821_339_133_667_644_396_117_517_409_218_592_473_694_736_410_013_586_765
  )

# 新しい署名鍵を生成
new_signing_key = Sidetree::Key.generate(id: "signing-key")

# 置き換えるDID Documentを生成
document = Sidetree::Model::Document.new(public_keys: [new_signing_key])

# 次のUpdate Keyを生成
next_update_key = Sidetree::Key.generate

# Update delta objectを生成
delta =
  Sidetree::Model::Delta.new(
    [document.to_replace_patch],
    next_update_key.to_commitment
  )

# JWSを生成して署名
claim = { updateKey: update_key.to_jwk.normalize, deltaHash: delta.to_hash }
jws = Sidetree::Util::JWS.sign(claim, update_key)

ipfs = Sidetree::CAS::IPFS.new

# Provisional Proof Fileを作成
provisional_proof = Sidetree::Model::ProvisionalProofFile.new([jws])
provisional_proof_uri = ipfs.write(provisional_proof.to_compress)

# Update operationを作成
update_op =
  Sidetree::OP::Update.new(did.suffix, delta, jws, update_key.to_reveal_value)

# Chunk Fileを作成
chunk_file =
  Sidetree::Model::ChunkFile.create_from_ops(update_ops: [update_op])
chunk_file_uri = ipfs.write(chunk_file.to_compress)

# Provisional Index Fileを作成
provisional_index_file =
  Sidetree::Model::ProvisionalIndexFile.new(
    proof_file_uri: provisional_proof_uri,
    chunks: [Sidetree::Model::Chunk.new(chunk_file_uri)],
    operations: [update_op]
  )
provisional_index_file_uri = ipfs.write(provisional_index_file.to_compress)

# Core Index Fileを作成
core_index_file =
  Sidetree::Model::CoreIndexFile.new(
    provisional_index_file_uri: provisional_index_file_uri
  )
core_index_file_uri = ipfs.write(core_index_file.to_compress)

anchor_str =
  Sidetree::Util::AnchoredDataSerializer.serialize(1, core_index_file_uri)

最終的なAnchor Stringは、

ion:1.QmVKryfVemjT3Nxnea4aJpJRXFJkLpFjNfti1tJngJwBWs

Bitcoinにアンカリングしたトランザクション40ba3f1d10456be725ac176a333e42b0ef9fdf47cb9f325f8f5c4f69b2e931df

ブロックが承認され、IONで取り込まれると、先程のDIDを解決すると、↓のようにdid:ion:test:EiBRrmEha_Q30GieEwLB-XM8CZd_b49dQ7znhaBxfAHTsQの署名鍵が新しく生成した鍵で更新されていることが分かる。

IONのDIDをIPFSとBitcoinにアンカリングしてみる

前回は、IONのDIDを生成した↓

techmedia-think.hatenablog.com

↑では、DID Documentを生成し、IONのプロトコルに沿って識別子であるDIDを計算したけど、実際にこれだけだとローカルで計算してるだけなので、続いて、このDIDをCAS(Content Addressable Storage)とブロックチェーンにアンカリングしてみる。

CASへのアンカリング

Sidetreeでは、以下のファイルでDID操作のデータを管理している。

https://identity.foundation/sidetree/spec/diagrams/file-topology.svg

  • Core Proof File:DIDのRecoverDeactivate操作について、それらが適切な操作であることを証明する暗号学的な証明を含むファイル。具体的には、現在のRecovery Keyとそれに対して有効な署名など(Recoverの場合のみ、次のRecovery Keyのコミットメントを含む)。
  • Provisional Index File:DIDのUpdate操作を証明するデータ(DIDのsuffixデータ、その最新のUpdate Keyのコミットメントに対応するUpdate Key)に加えて、Provisional Proof FileのURIと各Chunk FileのURIが含まれるファイル。
    • Provisional Proof File:Update操作について、それが適切な操作であることを証明する暗号学的な証明を含むファイル。具体的には、現在のUpdate Keyとそれに対して有効な署名が含まれるファイル。
    • Chunk File:DIDの状態を更新する際の、変更のPatchデータや、次のUpdate Keyのコミットメントなどが含まれる。
  • Core Index File:CreateRecoverDeactivateの3つのDID操作の値と、関連するProvisional Index FileのCASのURIが定義されたファイル。RecoverDeactivate操作の場合は、追加でCore Proof FileのURIが含まれる。

この内、最後のCore Index FileのURIブロックチェーンにアンカリングされる。URIからこのファイルを取得すれば、このファイルで行われたDID操作がリストされおり、また各関連ファイルを辿れるようになっている。

新規作成したDIDのアンカリング

今回はDIDのCreate操作をアンカリングしてみる。この場合、作成するのは、Chunk Fileと作成したChunk FileのURIが含まれるProvisional Index Fileおよび、Provisional Index FileのURIとCreateオペレーションのデータが含まれるCore Index Fileの3つ。※ Update/Recover/DeactivateはしないのでProof系のファイルは作らない。

まず、アンカリング対象のDIDを作成(did:ion:test:EiCFPfLlfe_2D8UxjJtGsaE5zsTisGZiOSU16dgq6vHDOw)↓*1

require 'sidetree'

Sidetree::Params.network = Sidetree::Params::Network::TESTNET

recovery_key = Sidetree::Key.generate
update_key = Sidetree::Key.generate
signing_key = Sidetree::Key.generate(id: 'signing-key')

document = Sidetree::Model::Document.new(public_keys: [signing_key])

did = Sidetree::DID.create(document, update_key, recovery_key, method: Sidetree::Params::METHODS[:ion])

Long-FormのDIDは、

Long-Form DID: did:ion:test:EiCFPfLlfe_2D8UxjJtGsaE5zsTisGZiOSU16dgq6vHDOw:eyJkZWx0YSI6eyJwYXRjaGVzIjpbeyJhY3Rpb24iOiJyZXBsYWNlIiwiZG9jdW1lbnQiOnsicHVibGljS2V5cyI6W3siaWQiOiJzaWduaW5nLWtleSIsInB1YmxpY0tleUp3ayI6eyJjcnYiOiJzZWNwMjU2azEiLCJrdHkiOiJFQyIsIngiOiJ0TVFEbnFkLUZIRGJjaGxwYzl6b0JsbVlib29hNk9NRVZyNlZTWERhTHpZIiwieSI6IlVzNEtWYy12OFBRYnJWUTRtdjNvczhoVG1lQUZ3OE5XRFJ6TmY4NHltdXMifSwicHVycG9zZXMiOltdLCJ0eXBlIjoiRWNkc2FTZWNwMjU2azFWZXJpZmljYXRpb25LZXkyMDE5In1dLCJzZXJ2aWNlcyI6W119fV0sInVwZGF0ZUNvbW1pdG1lbnQiOiJFaURCUTU2aXJsQnNrcjdaYXdGTGNvSDEzMVp2U0xiZmEyaksxTU9ueS1mZUlRIn0sInN1ZmZpeERhdGEiOnsiZGVsdGFIYXNoIjoiRWlCeExEX1BVNEVlQlpVNXpKV2wxMGtvTUZmTmtjQTZ4TExvZ0FOWTdfakxKQSIsInJlY292ZXJ5Q29tbWl0bWVudCI6IkVpQ0NhR3l5YU4yOFMydUc4MS1kTjl3c1ZQVTZoUTVYb1AxZFJtQ3pONU9uNUEifX0

↑のDIDを実際にアンカリングしてみる。手順は、

  1. 新規DIDのCreate Operationデータを生成。
  2. 1のデータを使ってChunk Fileを生成。今回のケースだとCreate OperationのDeltaデータが格納される。つまり、登録するDID Documentが含まれるデータ。
  3. Chunk FileをIPFSに書き込み、URIを取得。
  4. 3のURIを持つProvisional Index Fileを生成。今回のケースだとCreateのみなので、2のURIのみ。Updateが含まれる場合は、Provisional Proof FileのURIやオペレーションデータが含まれる。
  5. Provisional Index FileをIPFSに書き込み、URIを取得。
  6. 1のCreate Operationのデータと5のProvisional Index FileのURIからCore Index Fileを生成。今回のケースだとCreateのみなので、5のURIとオペレーションデータのみ。UpdateやRecoverがあれば別途Core Proof FileのURIが含まれる
  7. Core Index FileのURIをIPFSに書き込み、URIを取得。

↑のDIDについて、生成した2のChunk Fileのデータは↓

{"deltas":[{"patches":[{"action":"replace","document":{"publicKeys":[{"id":"signing-key","publicKeyJwk":{"crv":"secp256k1","kty":"EC","x":"tMQDnqd-FHDbchlpc9zoBlmYbooa6OMEVr6VSXDaLzY","y":"Us4KVc-v8PQbrVQ4mv3os8hTmeAFw8NWDRzNf84ymus"},"purposes":[],"type":"EcdsaSecp256k1VerificationKey2019"}],"services":[]}}],"updateCommitment":"EiDBQ56irlBskr7ZawFLcoH131ZvSLbfa2jK1MOny-feIQ"}]}

Provisional Index Fileのデータは↓

{"chunks":[{"chunkFileUri":"QmSVy6tUexQdmzBPpMEGjBs7ajB5dyGKuqZrhZMgvxqt1Q"}]}

Core Index Fileのデータは↓

{"provisionalIndexFileUri":"Qmc6LnGEqYNZ3YKhGNo3fMn8pUVrhXtTWKZEwhWt3H5vMo","operations":{"create":[{"suffixData":{"deltaHash":"EiBxLD_PU4EeBZU5zJWl10koMFfNkcA6xLLogANY7_jLJA","recoveryCommitment":"EiCCaGyyaN28S2uG81-dN9wsVPU6hQ5XoP1dRmCzN5On5A"}}]}}

いずれもIPFSに格納されるデータは↑をGZIP圧縮したデータになる。

sidetreerbに実装してみた↓(事前にIPFS daemonをローカルで実行しておく)。

require 'sidetree'

Sidetree::Params.network = Sidetree::Params::Network::TESTNET

# DIDの生成
recovery_key = Sidetree::Key.generate
update_key = Sidetree::Key.generate
signing_key = Sidetree::Key.generate(id: "signing-key")

document = Sidetree::Model::Document.new(public_keys: [signing_key])

did = Sidetree::DID.create(
      document,
      update_key,
      recovery_key,
      method: Sidetree::Params::METHODS[:ion]
    )

# DIDのCreate Operationを生成
create_op = did.create_op

# Chunk Fileを生成
chunk_file =  Sidetree::Model::ChunkFile.create_from_ops(create_ops: [create_op])

# IPFSクライアントを初期化(パラメータ省略するとデフォルトでhttp://localhost:5001/api/v0にアクセス)
ipfs = Sidetree::CAS::IPFS.new

# Chunk FileをIPFSに書き込み
chunk_file_uri = ipfs.write(chunk_file.to_compress)

# Provisional Index Fileを作成しIPFSに書き込み
provisional_index_file = Sidetree::Model::ProvisionalIndexFile.new(chunks: [Sidetree::Model::Chunk.new(chunk_file_uri)])
provisional_index_file_uri = ipfs.write(provisional_index_file.to_compress)

# Core Index Fileを作成しIPFSに書き込み
core_index_file = Sidetree::Model::CoreIndexFile.new(
          create_ops: [create_op],
          provisional_index_file_uri: provisional_index_file_uri
        )
core_index_file_uri = ipfs.write(core_index_file.to_compress)

最終的なCore Index FileのURIは、

QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW

Bitcoinへのアンカリング

CASへのアンカリングが出来たら、続いてブロックチェーンにアンカリングする。ここで、ブロックチェーンにアンカリングするデータは、Anchor Stringとして定義されているデータで、↑で作成したCore Index FileのURIと、操作の数で構成される。CASにアンカリングされた関連操作はCore Index Fileで参照可能になっているので、そのURIブロックチェーンにアンカリングしている。

Anchor Stringは、単純に操作数とCore Index FileのURI.で連結したデータ(例:1000.QmWd5PH6vyRH5kMdzZRPBnf952dbR4av3Bd7B2wBqMaAcf)。

なので、今回は、Anchor Stringにprefix(ion:)を付けた以下のデータをOP_RETURNを使ってBitcoinトランザクションに埋め込めばいい。

ion:1.QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW

実際に発行したトランザクション45e4459c7f3a36124b8b5df5c5b9314c4187833056f89a0c88ad57997fe1b051。OP_RETURNに↑が記録されているのが分かる。

ちなみに、↑のアンカリングTxの手数料が最低額を下回ってるとBitcoin的にはブロックに格納されるけど、IONとしては有効なCoreファイルとしてエラー処理される。

トランザクションがブロックに格納されると、ionノードを起動していれば新しいブロック内のアンカリングトランザクションを検知し、DIDの処理が行われる↓

Fetched 1 Sidetree transactions from blockchain service in 42 ms.
CommandSucceededEvent {
  connectionId: 'localhost:27017',
  requestId: 13,
  commandName: 'find',
  duration: 28,
  reply: {
    cursor: { firstBatch: [Array], id: 0, ns: 'ion-testnet-core.transactions' },
    ok: 1
  }
}
Downloading core index file 'QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW', max file size limit 1000000 bytes...
Downloading file 'QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW', max size limit 1000000...
Successfully kicked off downloading/processing of all new Sidetree transactions.
Processing previously unresolvable transactions if any...
CommandSucceededEvent {
  connectionId: 'localhost:27017',
  requestId: 14,
  commandName: 'find',
  duration: 1,
  reply: {
    cursor: {
      firstBatch: [],
      id: 0,
      ns: 'ion-testnet-core.unresolvable-transactions'
    },
    ok: 1
  }
}
Fetched 0 unresolvable transactions to retry in 1 ms.
Event emitted: sidetree_observer_loop_success
Waiting for 60 seconds before fetching and processing transactions again.
Read and pinned 240 bytes for CID: QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW.
Event emitted: sidetree_download_manager_download: {"code":"success"}
File 'QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW' of size 240 downloaded.
Downloading provisional index file 'Qmc6LnGEqYNZ3YKhGNo3fMn8pUVrhXtTWKZEwhWt3H5vMo', max file size limit 1000000...
Downloading file 'Qmc6LnGEqYNZ3YKhGNo3fMn8pUVrhXtTWKZEwhWt3H5vMo', max size limit 1000000...
Read and pinned 93 bytes for CID: Qmc6LnGEqYNZ3YKhGNo3fMn8pUVrhXtTWKZEwhWt3H5vMo.
Event emitted: sidetree_download_manager_download: {"code":"success"}
File 'Qmc6LnGEqYNZ3YKhGNo3fMn8pUVrhXtTWKZEwhWt3H5vMo' of size 93 downloaded.
Downloading chunk file 'QmSVy6tUexQdmzBPpMEGjBs7ajB5dyGKuqZrhZMgvxqt1Q', max size limit 10000000...
Downloading file 'QmSVy6tUexQdmzBPpMEGjBs7ajB5dyGKuqZrhZMgvxqt1Q', max size limit 10000000...
Read and pinned 308 bytes for CID: QmSVy6tUexQdmzBPpMEGjBs7ajB5dyGKuqZrhZMgvxqt1Q.
Event emitted: sidetree_download_manager_download: {"code":"success"}
File 'QmSVy6tUexQdmzBPpMEGjBs7ajB5dyGKuqZrhZMgvxqt1Q' of size 308 downloaded.
Parsed chunk file in 1 ms.
CommandSucceededEvent {
  connectionId: 'localhost:27017',
  requestId: 23,
  commandName: 'update',
  duration: 1,
  reply: { n: 1, upserted: [ [Object] ], nModified: 0, ok: 1 }
}
Processed 1 operations. Retry needed: false
Transaction 1.QmQPk9Vi9iSm4aAPEd73txGjqwbHhLYWfoUEpG5eYmy2PW is confirmed at 2315260

そして、ローカルで実行中のIONにDIDを問い合わせると↓、DIDの解決に無事成功!

http://localhost:3000/identifiers/did:ion:test:EiCFPfLlfe_2D8UxjJtGsaE5zsTisGZiOSU16dgq6vHDOw

今回の最小限のCreate操作で、CASやブロックチェーンにどうデータをアンカリングしているのかが大体分かってきた。

*1:前回作成したDIDは、DID Document内の鍵のtypeの設定が漏れてたので再生成。

非対話型のSchnorr署名のハーフアグリゲーション

先日、Blockstreamのブログ記事↓で、非対話型のSchnorrの署名集約スキームについて知ったので、

medium.com

↑にリンクされているドラフトBIPに記載されていた↓のペーパーを斜め読みしてみた。

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

Schnorr署名の集約と言えば、Bitcoinの文脈だと、MuSig2などの対話型の集約プロトコルが有名で、このような集約方法をフルアグリゲーションと呼ぶみたい。これはマルチシグをSchnorr署名の集約特性を利用して実現する方式で、複数の参加者が共通のメッセージに対して対話的に署名を生成し、それを単一の署名に集約する。

↑のハーフアグリゲーションは、マルチシグのような対話型の署名方式ではなく、署名者同士はそれぞれ互いを知らずに個々の署名を生成し、その後不特定の集約者がその署名を集約することを想定している。マルチシグは対話型で、共通のチャレンジに対して署名を生成し、それが単一のSchnorr署名と見分けが付かないような集約アプローチになるのに対して、ハーフアグリゲーションでは各署名者が異なるメッセージにそれぞれ署名し、その署名のサイズが個々の署名データの合算値の約半分になるというもの(フルアグリゲーションのように単一のSchnorr署名と同じサイズになる訳ではない)。そして個々の有効なSchnorr署名をインクリメンタル/シーケンシャルに集約することができる。

この仕組みを活用すると、例えば、

といった事が可能になる。

ペーパーでは、3つのハーフアグリゲーション方式が説明されている(以下、表記は楕円曲線ベースのものに変えてる)。

ASchnorr

Chalkiasらによって提案された集約方式をASchnorrと呼んでいる。

公開鍵 {X_1, X_2}とメッセージ {m_1, m_2}に対するSchnorr署名を {\sigma_1 = (R_1, s_1), \sigma_2 = (R_2, s_2)}として、各チャレンジを {c_1 = H_1(R_1, m_1), c_2 = H_1(R_2, m_2)}とした場合、それぞれ有効なSchnorr署名であれば、以下が成立する。

  •  {s_1G = R_1 + c_1X_1}
  •  {s_2G = R_2 + c_2X_2}

この2つの署名を単純にハーフアグリゲーションしようとすると、 {\tilde{s} = s_1 + s_2}とする方法で、 {\tilde{s}G = R_1 + c_1X_1 + R_2 + c_2X_2}が成立するか検証する方法。

ただ、この集約方法は安全ではない。ある署名のチャレンジ(たとえば、 {c_1})がもう1つの署名のコミットメント( {R_2})に依存していないため、例えば {R_2} {R_2 = r_2G - (R_1 + c_1X_1)}と細工すれば、 {X_1}の離散対数の知識を必要とせずに、 {X_2}の離散対数の知識のみで集約署名を偽造することができる。

ASchnorrでは、各署名に以下のような外部係数を使用して、この偽造問題に対処している。

 {L = \lbrace (R_1, X_1, m_1), (R_2, X_2, m_2) \rbrace}

および、

 {a_1 = H_2(L, 1), a_2 = H_2(L, 2)}

として、集約署名を {\tilde{s} = a_1s_1 + a_2s_2}として、その署名の有効性の検証は、 {\tilde{s}G = a_1 \cdot (R_1 + c_1X_1) + a_2\cdot(R_2 + c_2X_2)}とするというもの。MuSigのアプローチと似てる。

IASchnorr

↑のASchnorrで集約は可能だが、インクリメンタルな集約サポートしていないので、個々の署名がすべて集まってから集約する必要がある。そこで、インクリメンタルな集約をサポートするハーフアグリゲーション方式がIASchnorrと呼ばれる方式。

↑の2つの署名が集約された後に、公開鍵 {X_3}とメッセージ {m_3}に対する署名 {\sigma_3 = (R_3, s_s)}が届いて、これを既存の集約署名に追加するケースを想定する。

単純に集約使用とすると、既に集約済みの署名を通常の署名として扱うことで再度ASchnorrを行うというもの。つまり、

 {L' = \lbrace L, (R_3, X_3, m_3) \rbrace}

および、

 {a'_1 = H_2(L', 1), a'_2 = H_2(L', 2)}

として、 {\tilde{s}' = a'_1 \tilde{s} + a'_2s_3}という集約をする方法。

ただ、この方法の問題は、3つの署名が同じタイミングで集約された場合と、↑のようにインクリメンタルに集約された場合とで、集約結果の署名値が異なり、正しく検証するために、それがどのように集約されたのかという情報が追加で必要になる。

IASchnorrでは、係数を個々の署名すべてから計算するのではなく、それ以前の署名にのみ依存させるよう生成することで、この問題に対処するようになっている。つまり

 {L_i = \lbrace (R_1, X_1, m_1), ..., (R_i, X_i, m_i)\rbrace}

として、i番めの係数は {a_i = H_2(L_i)}となる。こうすると、↑のように署名集約のタイミングによって集約値が異なるようなケースを回避できる。

この方式では、n個の公開鍵とメッセージに対する最終的な署名値は、 {(\lbrace R_1, ..., R_n \rbrace, \tilde{s}'_n)}

SASchnorr

最後に、SASchnorrが、このペーパーで新しく提案されているハーフアグリゲーションの方式で、シーケンシャルに集約した個別の署名をリカバリーできるという特徴を持つ。また集約の方式もASchnorrやIASchnorrとは結構違う。

署名者nは、n-1個の公開鍵 {X_1, ..., X_{n-1}}とメッセージ {m_1, ..., m_{n-1}}に対する集約署名 {(\tilde{R}_{n-1}, \lbrace s_1, ..., s_{n-1} \rbrace)}を受け取ると、 {R_n = r_nG}の代わりに集約コミットメント {\tilde{R_n} = \tilde{R}_{n-1} + R_n}を計算し、チャレンジ {c_n = H(\tilde{R}_n, X_n, m_n, s_{n-1}, n)}を計算し、署名値 {s_n = r_n + c_n x_i}を計算する。

 {(\tilde{R}_{n}, \lbrace s_1, ..., s_{n} \rbrace)}を受け取った検証者は、 {c_n}を計算すると、 {R_n = s_nG - c_nX_n}を計算することで、1つ前の {\tilde{R}_{n-1} = \tilde{R}_n - R_n}を復元することができる。これを繰り返すことで、検証者はすべての個々の署名を復元することができる。

ペーパーでは、ランダムオラクルモデルの下で、Schnorr署名と同等の安全性を証明している。

↑の方式見た感じだと、各署名値が前の署名値に依存しているので、署名フェーズがシーケンシャルになる必要が出てくる。

データサイズ

↑のようにn個の公開鍵とメッセージに対して、以下署名データが必要になる。

  • IASchnorrの場合、 {(\lbrace R_1, ..., R_n \rbrace, \tilde{s}'_n)}=n個のRと1つのs
  • SASchnorrの場合、 {(\tilde{R}_{n}, \lbrace s_1, ..., s_{n} \rbrace)}=1つのR値とn個のs値

個別のSchnorr署名だとn個のRとn個のsで構成されるため、約半分のデータサイズになっていることが分かる。だからハーフアグリゲーションというネーミングなのね。

ドラフトBIP

ドラフトBIPでは、インクリメンタルなハーフアグリゲーションをサポートするようなので、↑の2番めのアプローチがベースになってる模様。まぁ、ブロックやトランザクションの署名を集約するようなケースだと、SASchnorrのようなシーケンシャルな署名プロセスは採用できないので、インクリメンタルなアプローチになるよね。SASchnorrの方は証明書チェーンやルーティングプロトコルなでの利用が期待されているみたい。