Develop with pleasure!

福岡でCloudとかBlockchainとか。

KZGコミットメントを計算して理解する

Cryptography kzg

以前ペアリングが可能な楕円曲線を利用するコミットメントスキームであるKZGコミットメントについて書いた↓

techmedia-think.hatenablog.com

楕円曲線を利用したコミットメントスキームとしては、Pedersenコミットメントが有名だが、Pedersenコミットメントではコミットした値を開示する際、すべてのコミット値を開示する必要がある。それに対し、KZGコミットメントでは、コミットした値を部分的に開示することができる。↑の記事では簡単にしか書いてなかったので、今回はこの仕組みを実際に計算しながら理解していこう。

今回は4つの値をベクトルX = (135, 91, 81, 9)にコミットするケースを考える。

Trusted Setup

KZGコミットメントでは、Trusted Setupにより秘密の値（シークレットパラメーター）sを生成し、そこから {s^{i}G}および {s^{i}H}を計算し、これらの値を共有する。そしてsを廃棄する。sは誰にも知られていてはならない。※G、Hなどの記述は↑の前回の記事内容を使用。

とりあえず、説明を簡単にするためs = 2で進める。※ ほんとはもっと巨大な数値。

今回4つの値にコミットするので、 {G, 2G, 4G, 8G}、 {H, 2H, 4H, 8H}がセットアップパラメータとなる。

※ KZGコミットメントではこのTrusted Setupが発生する。このためかEthereumのVerkle Treeの実装では結局Pedersenコミットメントを採用するみたい。

コミットメントの作成

セットアップパラメータが決まったら、値をコミットする。KZGコミットメントでは、コミットするベクトル値から多項式p(x)を作る。この多項式は、ベクトルに含まれるすべての値 {x_i}に対して、 {p(i) = x_i}となるような多項式。

4つの値にコミットするので、今回は3次の多項式 {p(x) = p_0 + p_1 x + p_2 x^{2} + p_3 x^{3}}を作ることになる。そして、ベクトルの値から、p(0) = 135, p(1) = 91, p(2) = 81, p(3) = 9を満たす多項式になる。こういった多項式はラグランジュ補完を使って求めることができる。今回のケースだと、多項式は↓

{p(x) = 135 - 45x - 7x^{2} + 8x^{3}}

となる。この多項式の各項の係数を {p_i}とすると、多項式は以下のように表現できる。

{\displaystyle p(x) = \sum_{i=0}^{n-1} p_i x^{i}}

そして、この係数と↑のセットアップパラメータ {G, 2G, 4G, 8G}を使ってコミットメントを計算する↓

{\displaystyle C = \sum_{i=0}^{n-1}p_i s^{i}G}

↑の例で展開すると、

{C = 135G - 45(2G) - 7(4G) + 8(8G)}

これはセットアップパラメータ {G, 2G, 4G, 8G}と多項式の係数 {p_i}の内積であることが分かる。つまり、コミットメントCは {p(s)\cdot G}と等しい。

コミットメントの作成フェーズでは、コミットするベクトルを多項式に変換し、その多項式をセットアップパラメータを使って楕円曲線上の点にエンコードしている。なので、コミットする値が増えても、コミットメントのサイズは一定のまま。

プルーフの作成

↑でベクトルX = (135, 91, 81, 9)についてのコミットメントCを作ったので、続いて、コミットした値を開示しよう。KZGコミットメントの場合、ベクトルXのすべての要素を開示する必要はなく、部分的に開示ができる。つまりX内の任意の {x_i}について開示が可能。

Xの内、 {y = x_i}を開示する。ここでは、 {y = x_2 = 81}とする。ベクトルはコミットメントにより多項式に変換されているので、3番目のコミット値が81であることは、 {p(2) = 81}（つまり、 {p(2) - 81 = 0}）であることを証明すればいい。

ここで、新たに多項式q(x)を次のように定義する。

{\displaystyle q(x) = \frac{p(x) - y}{x - i}}

これは以下の多項式の性質を利用したもの：

  • 多項式の剰余の定理：多項式 {p(x)}を二項一次多項式 {(x - i)}で割った場合、余りが {p(i)}となるという定理。
  • 多項式 {a(x)}を多項式 {b(x)}で除算した場合の商を {q(x)}、余りを {r(x)}とした場合、 {a(x) = q(x)b(x) + r(x)}と定義できる。

↑により {y = p(x_i)}について、 {p(x) = q(x)(x - i) + y}が成立し、これを変形したものが↑

今回のケースだと、 {y = x_2 = 81}なので、 {q(x) = \frac{p(x) - 81}{x - 2}}。

これらから、上記のような {q(x)}が存在する場合、 {p(x) - y}は {x - i}で割り切れる。ということは、因数定理（多項式 {p(x)}が {(x - i)}で割り切れる場合、 {p(i) = 0}が成立する）から、 {p(i) - y = 0}、つまり {p(2) - 81 = 0}となる。

KZGプルーフは、このような {q(x)}が存在し、この特性を証明するためのもの。

2022.06.30：q(x)の係数の誤りを指摘して頂いたので以下のq(x)の係数および次数を修正しました。

証明者は、多項式q(x)の各係数 {q_i}を計算する。この場合、q(x)の各係数は、 {(q_0 = -27, q_1 = 9, q_2 = 8)}。

そして、この係数とセットアップパラメーターを使って以下のKZGプルーフを計算する。

{\displaystyle \pi = \sum_{i=0}^{n-1}q_is^{i}G}

今回のケースだと

{\displaystyle \pi = -27(2^{0}G) + 9(2^{1}G) + 8(2^{2}G) }

これは、 {\pi = (-27(2^{0}) + 9 (2^{1}) + 8(2^{2}))G}であることから、

{\pi = q(s)\cdot G}であることが分かる。

コミットメントCが {p(s)\cdot G}、プルーフ {\pi}が {q(s)\cdot G}という構成になっていることが分かる。2つとも未知のシークレットパラメータで評価された、異なる多項式。

検証

証明者は、y = p(2) = 81と上記のプルーフを一緒に検証者に渡す。検証者は、以下のペアリングの等価性について検証する。

{e(\pi, sH - iH) = e(C - yG, H)}

つまり、

{e(\pi, sH - 2H) = e(C - 81G, H)}

ここで、sHはセットアップパラメータの１つで定数、iHはHとiから計算できる。

↑の式は、 {\pi = q(s)G, C = p(s)G}であることから、以下のように変形できる。

{e(q(s)G, (s - i)H) = e((p(s) - y)G, H)}

{e(G, H)^{q(s)\cdot (s - i)} = e(G, H)^{p(s) - y}}

{q(s)\cdot (s - i) = p(s) - y}

の検証になる、つまり、ここで検証しているのは↑で説明したq(x)の存在とそれが満たす特性。

検証者は両多項式の各係数 {p_i, q_i}について知らなくても、この特性を確認することができる。この特性が確認できたということは、 {p(i) = y}つまり、 {p(2) = 81}（３つめのコミット値は81）であることが検証されたことになる。

というのがKZGコミットメントで計算している内容。

ペアリング使うのは最後の検証部分のみ。最初ぱっと見た時は、Trusted Setupで生成するパラメータは、NUMSポイントとかを決定論的に生成して代替できないのか？とか思ったけど、↑のような多項式の性質使う上では {s^{i}}で構成されないと無理 よね。

The MergeによるEthereumのPoSへの移行

Ethereum

Ethereum 2.0のロードマップがだいぶ変わっていたので、久しぶりに調べてみた↓

Ethereum 2.0とその変遷

2018年に発表されたEthereum 2.0のロードマップは、シャーディングによりEthereumのスループットを向上させるのが目的で、3つのフェーズで構成されていた。

  • 最初のフェーズ0では、PoSベースのBeacon chainを導入する。
  • 続くフェーズ1では、データシャードを追加する。
  • 最後のフェーズ2では、各シャードでコントラクトの実行ができるように、各シャードにVMを追加する。

https://i.imgur.com/jZLRk9v.png

全フェーズのデプロイには数年間かかるという、長期に渡るロードマップだった。しかし、Ethereumのスケーリングの問題はそれを待つほど余裕がなく、ソリューションのより早い展開が求められていた。

そこで既存のPoWチェーンの改善をするStateless Ethereumなどの研究も始まる。また、Beacon chain自体は割と早く展開できるということもあり、既存のEVMチェーンをEthereum 2.0のシャード0として立ち上げようというEarly Mergeと呼ばれるプランも検討されるようになる。

The Merge

さまざまな検討がされる中、Vitalikから短期的なスケーリングソリューションとしてロールアップに集中しようという提案が行われる。つまり、シャーディングによるスケーリングよりも、すぐにスケーリング効果が見込めるレイヤー2ソリューションであるロールアップに計画をシフトするということ。

その結果、2020年、既存のEVMチェーンをEthereum 2.0のシャード0にするのではなく、Beacon chainと直接統合しようという提案が行われる。つまり、ブロックの承認はBeacon chainを使ってPoSベースで行われるが、そのブロックに含まれるトランザクションの実行は既存のEhereumクライアントを使って実行できるようにするというもの。元々のロードマップでは、フェーズ2まで待たなければVMを利用したコントラクトを実行できなかったが、この方法であれば、PoSベースのEVMチェーンが早く実現できる。これがThe Mergeと呼ばれる新しいPoS移行の計画。

シャードによるVMの実行（もともとのフェーズ2）には、まだ時間がかかるし、未解決の課題もあることから、延期やキャンセルも可能という位置づけみたい。

次にこのThe Mergeでどんな変更が入るのか見ていこう。

Eth1クライアントの変更

既存のEth1クライアントには、TERMINAL TOTAL DIFFICULTYという閾値が設定される。PoWのチェーンでブロックの総難易度がこの閾値を超えるブロックが作られると、そのブロックがPoWの最後のブロックとなる。それ以降のブロックは、Beacon chain上のバリデーターにより作成/認証され、Eth1クライアントはPoWブロックのゴシップを完全に停止する（NewBlockHashesやNewBlockといったP2Pメッセージが処理されなくなる）。

その後、Eth1クライアントはブロックの有効性などは検証しないが、トランザクションのゴシップやEVMによる実行、ステートの管理はPoSに切り替わってもそのまま実行される。このためマージ後、Eth1クライアントは実行エンジンとして動作し、実行レイヤーとして分類される。

Beacon chainの変更

現在のBeacon chainのブロックにはトランザクションデータは含まれていないため、空ブロックを作っているようなものだが、PoW→PoSに切り替わると実行エンジンと通信して、ExecutionPayloadsというデータの生成/検証を依頼するようになる。これには、親のハッシュ、ステートルート、Base fee、実行するトランザクションのリストなどが含まれる。Eth1クライアントから見ると、これが切り替え後のブロックに相当する。Beaconノードは、生成したExecutionPayloadsを含むブロックを作成、承認し、P2Pネットワークの他のノードにゴシップし、共有する。

Beacon chainはEthereumのコンセンサスレイヤーとして動作するが、基本的に実行レイヤーと連携して動作する。これによりBeach chainに実行機能が備わる。

Engine API

実行レイヤーとコンセンサスレイヤーはそれぞれ異なるP2Pネットワークで稼働する。The Merge後に完全に検証可能なノードを構成するためには、Beacon chainのオペレーターは新たに実行エンジンのノードを起動する必要がある。また、実行エンジンの方も最新のチェーンの情報を得るためにBeaconノードと連携する必要がある。このため、Beaconノードと実行エンジンの通信用に新たに以下の３つのメソッドを提供するEngine APIが提供される。これらのAPIは基本的にBeaconノードが実行エンジンに対して呼び出すものになる。

  • engine_executePayload：実行エンジンに対して、ExecutionPayloadが正しいか検証を依頼する。他のBeaconノードから受け取ったブロックの検証の際に使うものと思われる。
  • engine_forkchoiceUpdated：Beaconノードが実行エンジンに対して、ネットワークの最新のブロックを通知するためのAPI。このメソッドでは実行エンジンがExecutionPayloadを生成するのに必要となる情報（timestamp、random、feeReceipent）が渡され、実行エンジンでは、その情報を元に後続のExecutionPayloadを構築する。
  • engine_getPayload：実行エンジンに対して、engine_forkchoiceUpdatedで更新したチェーンの後続の新たなブロック用ExecutionPayloadを要求する。

ブロックヘッダーのフィールドとopcodeの変更

↑でできるだけ影響を最小限にPoSへの移行をするものの、一部変更が発生する。

ブロックはBeacon chain側のコンポーネントになり、これまでのEth1の実行レイヤーとやりとりする。ExecutionPayloadsは、引き続きEth1クライアントにとってみればブロックで、その一部のフィールドはPoSへの切り替えで意味合いが変わってくる。

ブロックヘッダーの変更

具体的には、ブロックヘッダーのフィールドの内、PoWに関連するフィールドは、PoSになると不要になる。ただ、フィールドが削除される訳ではなく、既存のツールへの影響を最小限にするため、以下のように変更される。

  • PoSになるとOmmerは発生しなくなるので、Ommerは常に空になり、その結果ommerHashは空のKecchak256ハッシュ値、つまり固定値になる。
  • PoWが行われなくなるため、
    • difficultyは常に0
    • nonceも常に0
  • mixHashもPoW関連のフィールドだが、0をセットするのではなく、Beacon chainのRANDAOの値が含まれるようになり、フィールド名もrandomに変更される。
opcodeの変更

ブロックのdifficultyを取得するDIFFICULTY(0x44) opcodeは、RANDOMという名前に変更され、元々ブロックヘッダーのmixHashが格納されていた箇所のデータ、つまりPoSに切り替わった後はBeacon chainのRANDAO値を返すようになる。

また、PoSに切り替わってもBLOCKHASH opcodeは使用できるが、PoWが機能しなくなるので、このopcodeが提供していたランダム性はかなり弱くなる。そのため、ランダム性が必要な場合は、↑のRANDOM opcodeの方が適している。

マージ前後の構造の変更を図示したのが↓

https://storage.googleapis.com/ethereum-hackmd/upload_81cabda944c7d4a190a0d37d051e4679.png

ファイナライズ

PoWでは常にreorgの可能性を考慮する必要がああったが、PoSでは正常に動作する限りreorgは発生しない。PoSになると2/3以上のバリデーターによって正規なブロックとして認められたブロックはFinalized Blockとして扱われる。このブロックを覆すためには、攻撃者は最低1/3のステークをバーンする必要がある。

また、Finalized Blockになる前に、チェーンに含まれると予想されるブロックをSafe Head blockと呼ぶ。2/3のバリデーターによる認証はないものの、大多数のバリデーターが正直に行動し、fork-choiceルールへの攻撃がない場合、このブロックがオーファンブロックになることはない。

アプリケーションへの影響

EVMで実行されるコントラクトは引き続き、実行レイヤーのクライアント（gethやNethermind、Besuなど）で処理されるので、大きく仕組みが変わることはなく、コントラクトで影響するのは、

  • BLOCKHASH opcodeが提供していたランダム性は弱まるので、ランダム性が必要な場合は、RANDOM（旧DIFFICULTY）opcodeへの切り替えが推奨される。
  • 現在約13秒前後のブロックタイムが、PoSに切り替わると12秒となるので、特定の平均ブロックタイムを利用するコントラクトでは、意図しないずれが発生する可能性がある。

あたり。

以上が、今後のEthereum 2.0へのロードマップ。方向性としては現実的な計画になってきた感じがする。

今月予定されているArrow Glacierのネットワーク・アップグレードで、difficulty bombが2022年6月まで延期されるようになるので、The Mergeが発生するのは順調に行けば、2022年の6月までの間に実行されるっぽい。

testnetで発見されたNeutrinoのTaproot関連の問題と軽量クライアントの課題

LND Lightning network Bitcoin

少し前に報告されたtestnetで発生したNeutrinoのフィルタ処理の問題について↓

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-November/019589.html

Neutrinoの位置付け

LNノード実装の１つであるLNDのブロックチェーンのバックエンドの連携先の１つがNeutrinoで、LNDにバンドルされている。現状LNDは以下のバックエンドが選択できる。

この内、Neutrinoは軽量クライアントとして位置付けられる。

軽量クライアントは、ブロックチェーン全体をダウンロードすることなく、ウォレットに関連するブロック、Txのみをダウンロードすることで、ノードのリソースコストを最小限に抑え、IoTデバイスやスマートフォンなどの低リソース環境でも動作させることができる。

もともとBitcoinにはBIP-16で定義されたBloom Filterベースのフィルターの仕組みを使ったSPVの仕様があったが、このプロトコルはフルノードへのトラストがネックになる。LNなどのペイメントチャネルでは、自分に関連するTxをオンチェーンで監視する必要があり、正しく検知できないと資金を失うリスクがあるため、このトラストポイントは最小化したい。

そこで、フルノードへのトラストを最小限にし、プライバシーも向上させるように新しく提案された軽量クライアント向けの仕様がBIP-157/BIP158↓

techmedia-think.hatenablog.com

techmedia-think.hatenablog.com

で、このBIPの前身となったのがNeutrino。Neutrinoは実装でもあるものの、Neutrinoプロトコルと呼ばれるのは、このため。

問題の原因

↑のBIP-157/BIP158は、既にBitcoin Coreにも実装されているけど、今回問題となったのはNeutrinoの実装の問題。

BIP-157/BIP158では、フルノードが各ブロック毎に、ブロック内の全トランザクションのインプット（正確にはインプットが参照する前のトランザクションのアウトプット）とアウトプットからフィルターを作成し、そのフィルターをP2Pメッセージで共有するようになっている。

軽量クライアントはブロックヘッダーのダウンロードに加えて、これらのフィルターのヘッダーおよびフィルタ自体をダウンロードする。そして、フィルタに対して自身に関連するトランザクションが含まれているかどうかを軽量クライアント自身がチェックする。この辺りのチェックの仕組みは↓

techmedia-think.hatenablog.com

今回問題になったのは、各ピアから入手したフィルターが競合した場合に、どのフィルターが正しいかチェックする際の実装。

Neutrinoでは競合するフィルターが見つかった場合、対象となるブロックを実際にダウンロードして、フィルターをチェックするようになっている。この振る舞い自体は問題なく、verification.cppに以下のチェックが実装されている。

  1. ブロック内の全TxのアウトプットのscriptPubkeyがフィルタにマッチするかどうか。
  2. ブロック内の全Txのインプットが参照するUTXOのscriptPubkeyがフィルタにマッチするかどうか。

このうち1についてはブロック内のトランザクションにscriptPubkeyがあるので問題ないけど、2のscriptPubkeyをどこから取得するのか？というのが課題になる。Neutrinoは軽量クライアントでブロックチェーン自体のデータを持っていないため、2のscriptPubkeyを持っていない。

そこで、NeutrinoはインプットのsciptSig/witnessのデータからscriptPubkeyを計算するというヒューリスティックを採用していた。計算ロジックは↓

  1. witnessにデータがある＝Segwit UTXOである。
    • witnessのアイテムが2つで、最後の要素のサイズが公開鍵（33バイト）と等しい場合、P2WPKHと判断して、公開鍵からP2WPKHのscriptPubkeyを計算する。
    • それ以外の場合、witnessの最後のデータをwitness scriptとして、P2WSHのscriptPubkeyを計算する。
  2. witnessではなく、scriptSigにデータがある＝非Segwit UTXOである。
    • scriptSigのデータサイズが署名＋圧縮公開鍵の取る範囲内であれば、P2PKHと判断して、公開鍵からP2PKHのscriptPubkeyを計算する。
    • それ以外の場合、P2SHと判断して、scriptSigのデータからredeem scriptを取得しP2SHのscriptPubkeyを計算する。

この内、1のロジックがTaprootに対応しておらず、TaprootのwitnessデータはすべてP2WSHとして判断されてしまい、誤ったscriptPubkeyが計算されてしまう。この結果、インプットが参照する正しいscriptPubkeyとは異なるscriptPubkeyが導出され、それをフィルタにかけるので、本来正しいはずのフィルターを不正なフィルターと判断してまう。

※ コードみた感じだと、P2PKHで非圧縮公開鍵使った場合もフィルターにアンマッチしそうなんだけど、どうなんだろう？

対応

直近の対応

直近の対応としては、↑のインプットのフィルタのチェックはするものの、ミスマッチが発生してもエラーログは吐くが不正なフィルターとは判定しないように修正されたみたい↓

https://github.com/lightninglabs/neutrino/pull/234/files#diff-86f3698bdc171fb0271f7ab951325ba3e6bf24aee52c7e9d645a1cd7040e758d

これ対応が入ったLND v0.13.4がリリースされている。

今後の対応

↑で不正なブロック判定はされなくなったものの、じゃあこの振る舞いを今後どうする？という課題が残る。これは別にNeutrinoに限った話ではなく、軽量クライアント全般に言えることだと思う（複数のピアから入手しているので、その中で一致する数の多いフィルターを正とするというアプローチもあると思うけど）。

そこで対策として挙げられているのが↓

  • 過去のヘッダーの取り扱いに関する緩和策としては、Neutrinoに10万ブロック毎にフィルターのヘッダーをハードコードしてチェックポイントとする（これは既に実装されている）。
  • フルノードからブロックのundoデータを入手できる新しいP2Pメッセージを用意する。ブロックのundoデータには、そのブロックで使用されたUTXOの情報が含まれるので、これをP2Pメッセージで入手できるようにすることで、インプットが参照するscriptPubkeyを補完する。
  • 複数のブロックにまたがるフィルターを作成する
  • マイナーに自身がマイニングしたブロックのフィルターへのコミットを求める。
  • Taprootの構成要素である内部キー/外部キー、Control Block、マークルルート、annexなどを照会可能な新しいフィルタータイプを追加する。

など。

GraftrootとG'rootを組み合わせたEntroot

Bitcoin Taproot

Pieter WuilleとAnthony Townsの議論から、GraftrootとG'rootを組み合わせたEntrootというプロトコルが公開されてる↓

https://gist.github.com/sipa/ca1502f8465d0d5032d9dd2465f32603

Graftrootとは？

Graftrootは、Gregory MaxwellがTaprootを発表した後に追加で提案されたプロトコル。

Taprootは、

  • （集約公開鍵である場合もある）単一の公開鍵を使ったkey-pathによる支払い
  • アンロック条件がエンコードされたマークルツリーを利用するscript-pathによる支払い

をサポートしているが、これはいずれも予め決められたアンロック条件を使った支払いになる。

Graftrootは、key-pathの鍵を使って、任意のスクリプトに署名し、そのスクリプトと署名を提供することで、後から任意の支払い条件を追加できるようにするというプロトコル。

G'rootとは？

G'rootについては、まず先日書いた投稿を参照↓

techmedia-think.hatenablog.com

Condition Point

G'rootでは、楕円曲線の2つめのジェネレーターG2を利用したPedersen Commitment

Q = P + H(s)G2

を利用していたが、ここではそれを少し改良して、G2の代わりにハッシュ値を誰もその離散対数を知らない曲線上の点にマッピングするハッシュ関数hash-to-curve（Hc()）を使用する↓

Q = P + Hc(s)

hash-to-curveの一番簡単な実装は、生成したハッシュ値を楕円曲線のx座標として曲線上の点に変換するというもの（該当するx座標の点がない場合は、値をインクリメントしていく）。G2でなくhash-to-curve使うのは楕円曲線の乗算よりも高速だから。

Entroot

↑のEntrootの説明では、G'rootを再公式化して説明しており、このCondition Pointの使用や、支払いポリシーを3つのノードタイプを持つツリーとして定義しており、基本的に各Condition Pointと支払いポリシーのツリーが

  • 単一の公開鍵によるアンロック
  • 単一の公開鍵とスクリプトによるアンロック
  • （単一の公開鍵とスクリプトを開示した上で）リンクしている別のCondition Pointによるアンロック

を表現できるようになっている。

Entrootは上記の評価ルールに4つめのアンロック条件＝Graftrootの評価ロジックを追加しようというもの。

G'rootでは、スタックで公開されたアイテムを使って、hash-to-curveの要素を削除する。つまりQ - Hc(s)して出てきたPに対する署名検証を行う。そして、スクリプトsの評価を行う。

この時、署名対象のメッセージは、通常その支払いトランザクションのsig hashであるが、もしスタックに別のCondition Point（Qgraft）が含まれている場合、かつそれを署名対象のメッセージとしてPに対して有効な署名が提供されていた場合、Condition Point（Qgraft）が次の評価ポイントとして評価されるようになる。

つまり、任意の評価条件＝Condition Pointに対して、現在のアンロック条件によって有効な署名が提供されていれば、それをアンロック条件として評価するルールを追加しようというもの。

G'rootとの組み合わせで変わること

元々のGraftrootの提案では、key-pathの鍵を使って署名して任意のアンロック条件を追加するというものだった。

しかし、G'rootのロジックに加えると、key-pathの鍵に限定されずに、G'rootのアンロックブランチのいずれかの条件を満たせれば、誰でも任意のアンロック条件を追加できるようになる。元のTaprootの文脈でいうと、key-pathだけじゃなくてscript-pathのどの条件ブランチを使っても新たなアンロック条件を追加できるということ。

Generalized taproot（G'root）

Taproot Bitcoin Cryptography

Generalized taproot（G'root）は、2018年にAnthony Townsによって提案されたPedersen Commitmentを使ってTaprootを実現するプロトコルの提案。

Taprootのscript-pathは、アンロック条件をマークルツリーにエンコードするMAST（Merklized Alternative Script Trees）という仕組みに依存しているが、G'rootは同様のことをマークルツリーを使わずに、Pedersen Commitmentで実現する。

Taprootのロックスクリプトのwitness programは、

Q = P + H(P, s)G

という公開鍵で構成される。この内Pは内部キー、sがスクリプトツリーのルートハッシュから導出した値が含まれる。

key-pathによるアンロックは公開鍵Qに対して有効な署名を提供し、script-pathによるアンロックはスクリプトツリー内のスクリプトとそれが含まれるルートまでのマークルパスとPと、スクリプトを満たすwitnessが提供される。

G'rootの構成

Taprootの場合sを導出するのに、各スクリプト条件をリーフノードとしたスクリプトツリーを構成するが、G'rootではツリーを構成するのではなく、各条件毎に以下のようなPedersen Commitmentを計算し、それを連鎖させていく。

A' = aG + sG2 + H(aG + sG2, B')G

G2はGとは別の楕円曲線上のジェネレーター、B'は別のアンロック条件で構成されるPedersen Commitment。

A'にロックされたコインを使用する方法は、

  1. A'にスクリプト条件がない場合＝つまりs = 0の場合のアンロック
    A' = aG + H(aG, B')Gとなるため、a + H(aG, B')を秘密鍵として公開鍵A'に対して有効な署名を直接提供する。これはs = 0の場合のみ成立する。s != 0の場合、G2が残るので有効な署名は作れない。
  2. スクリプトsを使ってアンロックする場合
    sを公開し、公開鍵A' - sG2に対して有効な署名と、スクリプトsを満たすwitnessを提供する。公開されたsによりA' - sG2でG2が無くなるので、a + H(aG + sG2, B')を秘密鍵として有効な署名を作成することができる。
  3. 別のPedersen Commitment B'の条件を使ってアンロックする場合
    aG + sG2とB'を公開し、B'を満たすwitnessを提供する。

もう少し具体的な例を使うと、例えば以下の複数のアンロック条件を持つG'rootを構成する場合、

各条件ごとにに以下のようなPedersen Commitmentを作成する。

  • D' = z
  • C' = cG + yG2 + H(cG + yG2, D')G
  • B' = bG + xG2 + H(bG + xG2, C')G
  • A' = aG + H(aG, B')G

そしてG'rootのscriptPubkeyはA'となる。A'→B'→C'→D'へのアンロック条件の連鎖を構成し、TaprootのMAST構造を代替する。

A'をアンロックするためには、

  • A'でアンロックする場合は、秘密鍵a + H(aG, B')を使った署名を
  • B'でアンロックする場合は、aG、B'、xを公開して、秘密鍵b + H(bG + xG2, C')を使った署名とスクリプトxを満たすwitnessを
  • C'でアンロックする場合は、aG、B'、bG + xG2とC'、yを公開して、秘密鍵c + H(cG + yG2, D')を使った署名とスクリプトyを満たすwitnessを
  • D'でアンロックする場合は、aG、B'、bG + xG2とC'とスクリプト、スクリプトからzまでのマークルパスを公開し、スクリプトのwitnessを

提供する。使用確率の高いアンロック条件をA'に近い位置に配置するのが、効率的。

※ zの部分は、スクリプトツリーを使ってるので、MASTを使わないという訳ではない。