Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

Bitcoin Taproot

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