Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoinの新しいmempool設計の提案

Bitcoinのmempoolについて、既存の課題とそれを改善する新しい設計案が提案されている↓(最近Optechで始まった限定シリーズも、この辺りの話があるから?)

github.com

現在のmempoolの課題

mempoolには、Bitcoinネットワークでブロードキャストされた、まだブロックに格納されていない未承認のトランザクションが保持されている。この未承認トランザクションのすべてについて、インプットで参照する親トランザクションが承認済みのものであれば、トランザクション単体の手数料率を計算してソートするだけで簡単に優先順位が決められる。

ただ、実際は未承認の親を含む子トランザクションがあったり(CPFPとかで)、さらに孫が存在していたりと、関連トランザクションによる未承認のトランザクションチェーンが構成される。

現在のmempoolでは、プール内のこれらのトランザクションについて、祖先ソートと子孫ソートという2つのソート順を維持するようになっている。つまり、親子関係のあるトランザクションチェーンが形成される中で、あるトランザクションから子を辿っていくソートと、親を辿っていくソートが保持されている。この2つのソートを使用するアルゴリズムの問題点として次のようなものが挙げられている↓

mempoolからの退去

最近発生してるように、mempoolが混雑しmempoolのサイズを超えてトランザクションが溢れると、手数料率の低いトランザクションからmempoolから退去させられる。

この退去のアルゴリズムは、子孫手数料率が最も低いトランザクションをその子孫と一緒に削除するというもの。ただ、このアルゴリズムには問題があって、退去させたトランザクションが必ずしもマイニング時のトランザクション選択アルゴリズムにおいて最後の候補(最も収益性の低いもの)であるとは限らないこと。

たとえば、以下のようなトランザクションチェーンがある場合↓

graph TD;
    A[Tx A: size 250, fee 250]-->B;
    A-->C;
    A-->E[Tx E: size 250, fee 49750];
    B[Tx B: size 50000, fee 50000]-->D[Tx D: size 500, fee 52000];
    C[Tx C: size 50000, fee 50000]-->D;

ここで、

  • Tx Eから見た祖先の手数料率は、Tx size = 250 + 250 = 500、fee = 250 + 49750 = 50000から、100 sat/byte
  • Tx Aから見た子孫の手数料率は、AからEすべてを加味するため、Tx size = 101000、fee = 202000から、2 sat/byte

この中では、Tx Aの子孫手数料率が一番低いけど、Eの祖先手数料率は一番高いという状況になる。

現状の退去アルゴリズムでは、子孫の手数料率をみて判断するので、Tx Aが退去対象に選ばれるが(その子孫も)、マイナーにとっては(A, E)のセットをマイニングするのが一番収益が高くなるという状況が発生する。

ここでの問題は、マイニングアルゴリズムにおける一番手数料収益があげられるトランザクションのセットと、退去のアルゴリズムにおける一番手数料率が低いトランザクションのセットのギャップにある。

現在のマイニングアルゴリズムの方も、祖先の手数料率を見ていくアルゴリズムで、性能と収益のバランスを取るもので、最も最適(収益性の高い)トランザクションのセットが見つけられるというものではない(CPFPのようなシナリオで最適なブロックを見つけられるかというと難しい)。

インセンティブ非互換のRBF

RBFにも課題がある。RBFを利用してトランザクションを置換する場合、新しいトランザクションに置換対象よりも高い手数料率を要求するというルールがある。ただ、この比較は新しいトランザクションと置換対象のトランザクションの手数料率を比較しているだけで、両者の子孫トランザクションは考慮されていない。そのため、手数料率の高い子孫トランザクションをmempoolから退去してしまう可能性があり、マイナーのインセンティブとは異なる置換が起きることになる。

また、BIP-125のオプトインRBFの場合、置換する新しいトランザクションのインプットに未承認のTxが含まれてはならないというルールがあるが、新しい未承認の親Txを含めることで結果的に親子で見た時の手数料率が上がる可能性もあり、これもマイナーのインセンティブとは異なる制限になっている。

新しい設計案

↑のような問題を抱える中、新しいmempoolの設計案は、mempool上でトランザクションの全体的な順序を付けて保持しようというもの。

ただ、単純にmempool内のすべてのトランザクション組み合わせの候補を検索し、最も高い手数料率のものを選択するというのを繰り返すという方法だと、指数関数的な実行時間を必要とするため機能しない。

そこで、まず最初にトランザクションクラスタを構成する↓

クラスターの構築

  1. mempool内の全トランザクションでグラフを形成する。
  2. エッジで接続されたトランザクションのセットをクラスタとする。
  3. クラスターのセットが構成されると、各トランザクションは互いに素なクラスターに分割され、各トランザクションは必ず1つのクラスター内に存在しているという状態になる。※ どのトランザクションともエッジがないトランザクションは、それ単体が1つのクラスターになる。

リニアライゼーション

トランザクションクラスターが構成されると次にそのクラスターに対して順序付けを行う。この順序付けのことをリニアライゼーションと呼んでいる。リニアライゼーションは抽象化されいて、具体的なソートアルゴリズムが定義されているわけではない。順序付けができればいいので、既存の祖先手数料率ベースのアルゴリズムでもよければ、トランザクションのすべてのサブセットの組み合わせから収益性が最も良いセットを選択するような最適化アルゴリズムでも良い。

クラスターの制限

クラスターを構成して順序付けをしても、クラスター内に新しいトランザクションを追加すると、クラスター内のトランザクションの順序もそれまでとは全く異なる順序に変わる可能性があるため再度順序付けを行う必要がある。ただ、巨大なクラスターが登場すると、その順序付けの実行も現実的ではなくなるので、クラスターに対してサイズ制限を設ける。

サイズ制限により実行時間にリミットを設けることで、常に個々のクラスターの順序を維持できるようにする。サイズによって指数時間を必要としていた最適な組み合わせの順序付けも実現可能なレベルの時間になる可能性が出てくる。

チャンク

一番ヘビーなリニアライゼーションが終わったら、マイニングや退去の対象となるトランザクションのグループを作るためにリニアライゼーションされたトランザクションリストのチャンク化を行う(リニアライゼーションはクラスター内の順序付けなので、mempool内の全クラスター内の比較はこの時点ではまだできてない)。

たとえば、次のようなトランザクショングラフを持つクラスターについて

リニアライゼーションした結果のトランザクションリストが以下の場合(カッコ内は手数料とサイズ)

まず、リストの先頭から累積手数料率を計算し最も高いサブセットを見つける。↑の場合、

Tx A〜Tx Dまでが最初のチャンクになる。続いて、残ったリストの先頭(↑ではE)からこれを繰り返す。すると、

チャンク 累積手数料率
Tx A〜Tx D 1.92
Tx E 1.25
Tx F〜Tx G 1.07
Tx H〜Tx I 1.02
Tx J 1.01

というチャンクに分割される(※ 手数料率が同じ場合は、チャンクは小さい方が良いのでマージしない)。

結果、手数料率が単調減少するチャンクのリストが構成される。

mempoolの操作

mempoolのクラスター化、リニアライゼーション、チャンク化がすべて終わったら、それ利用してmempoolの各操作を実装するアルゴリズムを作ることができる。

マイニング

マイニング対象のトランザクションセットの構成は、貪欲法を使って実装できる。各クラスターの先頭のチャンク(=最も累積手数料率の高いチャンク)をピックアップ/ソートし、一番手数料率の高いトランザクションパッケージを候補ブロックに追加していく。追加したチャンクのクラスターにまだチャンクが残っていればそれをピックアップする。これをブロックスペースが埋まるまで繰り返す。

ただ、ブロックスペースを埋める終盤になってくると、残りのサイズに対してチャンクがフィットしない可能性が出てくるので、それは別途対応が必要。

退去

mempoolが溢れる場合は、↑のマイニングと逆の処理をして退去対象のトランザクションパッケージをピックアップする。各クラスターから一番最後のチャンク(最も累積手数料率が低いチャンク)をピックアップ/ソートし、一番手数料率の低いパッケージをmempoolから削除する。削除したチャンクのクラスターにまだ他のチャンクが残っていたらピックアップする。これをmempoolが十分なサイズになるまで繰り返す。

この結果、マイニングアルゴリズムで最後に選択されるであろうトランザクションパッケージから順に退去させられるようになる。

RBF

RBFについては、置換トランザクションクラスターに適用した場合のチャンクの手数料率と、置換によって削除されるトランザクションのチャンクの手数料率を比較するようにする。こうすることでマイニングのインセンティブと適合する形でRBFの判断ができるようになる(結果、BIP-125の未承認の親Tx追加のNGルールはなくなる)。

ただし、DoS対策として以下のルールが適用される:

2つめのルールは、単一のトランザクションの処理中にmempool内の大量の再クラスタリング/リニアライゼーションが発生しないようにするためのもの。

今後

以上が新しいmempoolの設定の提案で、このロジックのドラフト実装は既にできおり、現在はこれまでのトランザクション履歴に対して、このロジックの影響を分析中とのこと。

実際に適用されるにしても、まだ先の話になりそう。あと実際適用するとなったら、適用ノードと非適用ノードでmempoolの動作が変わるので、混在期間中のトランザクションのリレー状況がどうなるのかちょっと気になる。

BitcoinでMuSig2*をサポートするためのBIP-327

MuSigは、Schnorr署名でn-of-nのマルチシグを実現するにあたって、Rogue-Key攻撃に対する堅牢性を備えた署名プロトコルMuSig

  • 署名に使用するPublic nonceのコミットメントの交換
  • Public nonceの交換
  • 部分署名の作成、交換

という3ラウンドの通信を必要としたけど、最初のPublic nonceのコミットメントの交換を不要にして2ラウンドにしたのが2020年に提案されたMuSig2↓

techmedia-think.hatenablog.com

そして、これを実際にBitcoinに適用するための提案が最近BIP-327として登録された↓

https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki

MuSig2*

BIP-327で採用しているのは、正確にはMuSig2*というMuSig2を少し最適化した亜種になる。MuSig2のペーパーのAppendix Bに掲載されているけど、違いは集約公開鍵を計算する際の乗算コストを削減する点。

MuSigでは、集約公開鍵を計算する場合、Rogue-Key攻撃への対策として、単純に全公開鍵を加算するのではなく、各公開鍵に係数を乗算した上で加算するようになっている。参加者の個々の鍵ペアを {X_i = x_iG}、集約対象のすべての公開鍵のリストを {L = (X_1, ..., X_n)}とすると、

  1. 最初に、集約の際に各公開鍵に乗算する係数 {a_i = H(L, X_i)}として計算する。
  2. 計算した各係数を対応する公開鍵に乗算して集約公開鍵を計算する。つまり、 {X_{agg} = \sum_{i=1}^n a_iX_i}

MuSig2*では、公開鍵のリストの2番めの公開鍵( {X_2})について、乗算する係数を↑の {a_2}ではなく定数1を使用する。つまり1つの公開鍵分、 {a_i * X_i}の計算コストを削減する最適化を行うのがMuSig2*。

BIP-327の各アルゴリズム

BIP-327で定義されている各アルゴリズムは↓

鍵生成と集約系のアルゴリズム

個々の公開鍵の生成(IndividualPubkey)

各参加者の鍵生成プロセス。通常の鍵生成と同じで、秘密鍵から公開鍵を計算し、33バイトの圧縮形式の公開鍵を出力する。

鍵のソート(KeySort)

公開鍵を集約する前に公開鍵のリストをソートするアルゴリズム。ソートは必須ではなくオプション。33バイトの圧縮公開鍵のリストを入力として受け取り、辞書順にソートした公開鍵のリストを出力する。

公開鍵の集約(KeyAgg)

33バイトの圧縮公開鍵のリストを受け取り、集約公開鍵を計算するアルゴリズムアルゴリズムは、BIP-340互換のx-only公開鍵を導出するために必要なtweak値を持つKeyAgg Contextを出力し、KeyAgg ContextはBIP-340互換のx-only公開鍵を出力する。

1. 33バイトの公開鍵のリストを連結し、タグ付きハッシュを計算

L = H('KeyAgg list', <リストの公開鍵を連結したデータ>)

2. 2番めの公開鍵以外について、係数 {a_i}を計算(2番めの公開鍵の係数は1

a_i = int(H('KeyAgg coefficient', L + <i番目の公開鍵>))

3.各公開鍵に2で計算した係数を乗算

X_i = a_i * <i番目の公開鍵>

4.3の公開鍵をすべて加算したものが集約公開鍵

集約の際は、↑の係数の計算とMuSig2*による2つめの公開鍵への定数の適用から、公開鍵の順番が異なると異なる集約公開鍵が導出される。これについて、KeyAggアルゴリズム自体では、明示的に公開鍵のソートはせず、必要であれば別途集約前に↑のKeySortアルゴリズムでソートすることとしている。

KeyAgg Contextは、集約した結果の楕円曲線上の点と、適用された調整の累積値(後述)と符号反転を追跡する値を持つ。

集約公開鍵の微調整(ApplyTweak)

KeyAggで集約した集約公開鍵に対して、微調整を行う際のアルゴリズム

単純にn-of-nのマルチシグを実現するだけならこの微調整は必要ないが、次のようなユースケースでは微調整が必要になる。

  • マルチシグ以外に、Taprootのスクリプト条件にコミットした集約公開鍵を作る場合
    微調整前のKeyAgg Contextの公開鍵がTaprootの内部鍵になり、Tapscriptのルートハッシュ値から作られる公開鍵を加算する必要がある。
  • BIP-32を使って、集約公開鍵から子鍵を導出する場合

ApplyTweakアルゴリズムは、KeyAgg Contextと調整値(tweak)と調整モード(is_xonly)を入力として受け取り、調整を適用したKeyAgg Contextを出力する。調整モードは調整時にx-only公開鍵を使うかプレーンな33バイトの公開鍵を使うかを決めるパラメーター。↑のユースケースでは前者はx-onlyの調整が必要で、後者はプレーンな調整になる。

nonceの生成(NonceGen)

署名を作成する際に使用するnonceを生成するアルゴリズム。BIP-340の署名やRFC6979のように決定論的なnonce生成は、MuSig2ではセキュリティ上使用できない(詳細はこちら)。

基本的にnonceはランダムに生成するけど、偶然にも一様にランダムに生成されなかった場合を想定して、そのような場合が万が一あったとしても秘密鍵の漏洩を防げるように、入力(公開鍵に加えてオプションで秘密鍵、集約公開鍵、署名対象のメッセージ、補助入力)を使用してnonceの値が変わるような多層防御の仕組みを組み込んでいる。

MuSig2ではPublic nonceのコミットメントの交換ラウンドを排除するため、1つの署名ラウンドで複数個のnonceを生成するようになってる。BIP-327では2個nonceを生成するようになっており、このアルゴリズムの出力は↓

  • 2つのnonceと公開鍵を結合したバイト列(nonce k1 || nonce k2 || 公開鍵
  • 2つのnonceに対応するそれぞれのPublic nonce(R1 = k1G || R2 = k2G

署名セッションで署名参加者は、まずこのPublic nonceを他の参加者に送信する(これが署名時の最初の通信ラウンド)

nonceの集約(NonceAgg)

各参加者が別の参加者のPublic nonceのリストを受け取り、集約するアルゴリズム

各Public nonceには、2つのPublic nonceR1、R2が含まれているので、ここでは、

  • すべてのPublic nonceのR1を合算
  • すべてのPublic nonceのR2を合算

して、2つの楕円曲線上の点が計算できるので、それぞれを33バイトの公開鍵としてエンコードし連結した値を出力する。※ ここで集約したPublic nonceがそのまま集約署名のPublic nonceになる訳ではない。

集約署名のPublic nonce

MuSig2では、 集約署名のPublic nonceは

全参加者のPublic nonce R1の合算値 + 係数 * 全参加者のPublic nonce R2の合算値 

として計算される。ここでR2の合算値に乗算する係数は、

  • NonceAggの値
  • 集約公開鍵
  • 署名対象のメッセージ

を連結したタグ付きハッシュ値(タグはMuSig/noncecoef)で、決定論的に導出される。

この係数をR2のPublic nonceに乗算して最終的な集約署名のPublic nonceを導出することで、MuSig2ではPublic nonceのコミットメントラウンドを省略可能にしている。

署名(Sign

各参加者がそれぞれ個別の署名を生成する際のアルゴリズムは、自分が生成したnonce(自分のk1k2)と秘密鍵x_i)を使って、部分署名

s = k1 + b * k2 + e * a_i * x_i

を計算する。ここで、e集約署名のPublic nonce || 集約公開鍵 || 署名対象のメッセージのタグ付きハッシュ(タグはBIP0340/challenge)。a_iは(Rogue-Key対策で)集約公開鍵を導出する際に乗算した係数。

部分署名を計算したら、これを他の参加者(もしくは署名の集約者)に送信する。これが2ラウンドめの通信

部分署名の検証(PartialSigVerify)

部分署名が有効かどうか検証する際のアルゴリズム

  • 部分署名(s
  • 全参加者のPublic nonceのリスト
  • 署名者のインデックス(i)

を入力として受け取り、Public nonceのリストからNonceAggを実行して集約したR1とR2を計算し、

sG = R1 + b * R2 + e * a_i * X_i

が成立するか、Schnorr署名の検証を行う。この検証が失敗する場合、その部分署名を提供した署名者が不正な署名を送ったことになる。すべての参加者の部分署名がこの検証をパスする場合、署名の集約で有効なSchnorr署名を完成できる。

最後の署名者のみ利用可能な決定性署名(DeterministicSign)

MuSig2では、署名にあたって最初にnonceを生成して他の署名者のPublic nonceを受け取るまでそれらのデータを保持する必要があるという意味でステートフルな構成になる。ただ、署名参加者の内、1人だけならこれをステートレスにすることができる。この署名者は、他の参加者の全Public nonceを受信するまで待機して、その後NonceGen、NonceAgg、Signの各アルゴリズムを一斉に実行し、自分のPublic nonceと部分署名を一緒に他の参加者に送信する。このオペレーションが可能なのは全参加者の中で1人のみで、ステートレス署名者とも呼ばれる。

↑で、MuSig2では決定論的にnonceを生成することはできないとしたけど、このようなステートレスなオペレーションの場合、他の参加者のすべてのPublic nonceを受信した後に実行されるので、自分のnonceは決定論的に生成することができる。

DeterministicSignアルゴリズムは、このように決定論的に導出したnonceを使って決定性署名を作成するアルゴリズム。この決定性nonceは、

  • 自分の秘密鍵
  • 自分以外の署名者のPublic nonceの集約値
  • 集約公開鍵
  • 署名対象のメッセージ
  • 0 or 1(0 = k1, 1 = k2)

を使ったタグ付きハッシュ(タグはMuSig/deterministic/nonce)で計算される。

決定性nonceが導出されたら、それを使って(Signアルゴリズムで)部分署名を生成して、生成したPublic nonceと部分署名を出力する。

部分署名の集約(PartialSigAgg)

各署名者が生成した部分署名を集約するアルゴリズム。集約Public nonceのx座標と部分署名の合算値を出力(R.x, s)。

以上が、BIP-327で定義されてるアルゴリズムアルゴリズムの詳細については、BIP本体を参照。

bip-schnorr gemで実装

BIPの参照実装とTest Vectorを参考にbip-schnorr gemにもMuSig2*を実装してみた↓

require 'schnorr'

sk1 = 1 + SecureRandom.random_number(Schnorr::GROUP.order - 1)
pk1 = (Schnorr::GROUP.generator.to_jacobian * sk1).to_affine.encode

sk2 = 1 + SecureRandom.random_number(Schnorr::GROUP.order - 1)
pk2 = (Schnorr::GROUP.generator.to_jacobian * sk2).to_affine.encode

pubkeys = [pk1, pk2]

# 公開鍵の集約
agg_ctx = Schnorr::MuSig2.aggregate(pubkeys)
# 公開鍵の集約(微調整バージョン)
agg_ctx = Schnorr::MuSig2.aggregate_with_tweaks(pubkeys, tweaks, modes)

## 集約公開鍵は
### 楕円曲線上の点は↓
agg_ctx.q
### x-only公開鍵のhex値は↓
agg_ctx.x_only_pubkey

msg = SecureRandom.bytes(32)

# nonceを生成
sec_nonce1, pub_nonce1 = Schnorr::MuSig2.gen_nonce(
        pk: pk1,
        sk: sk1,  # optional
        agg_pubkey: agg_ctx.x_only_pubkey,  # optional
        msg: msg, # optional
        extra_in: SecureRandom.bytes(4),  # optional
        rand: SecureRandom.bytes(32)  # optional
)

## ステートレス署名者の場合のnonce生成
agg_other_nonce = described_class.aggregate_nonce([pub_nonce1])
pub_nonce2, sig2 = described_class.deterministic_sign(
        sk2, agg_other_nonce, pubkeys, msg, 
        tweaks: tweaks, # optional
        modes: modes, # optional
        rand: SecureRandom.bytes(32)  # optional
)

# nonceの集約
agg_nonce = Schnorr::MuSig2.aggregate_nonce([pub_nonce1, pub_nonce2])

# 部分署名の作成
session_ctx = Schnorr::MuSig2::SessionContext.new(
        agg_nonce, pubkeys, msg, 
        tweaks, # optional
        modes # optional
)
sig1 = session_ctx.sign(sec_nonce1, sk1)

# 部分署名の検証
signer_index = 0
session_ctx.valid_partial_sig?(sig1, pub_nonce1, signer_index)

# 署名の集約
sig = session_ctx.aggregate_partial_sigs([sig1, sig2])

# 通常のSchnorr署名の検証
Schnorr.valid_sig?(msg, agg_ctx.x_only_pubkey, sig.encode)

Ordinal InscriptionのDEX「OpenOrdex」でのPSBTの利用

Bitcoin上でNFTを取引可能にするOrdinalのDEX「OpenOrdex」がリリースされてたのでみてみる↓

github.com

Dockerfileが提供されてるので、ビルドして実行するとローカル環境にOrdinalのDEXが起動する↓

Inscriptionの取得

Inscriptionは、Inscription numberを入力することで指定できる。Collectionページにリストされてるコレクションは、↓のリポジトリから取得してるみたい。

github.com

自分のInscriptionをコレクションに追加したい場合は、↑にPRしてねと。

Inscriptionの画像は、直接トランザクションをパースしてる訳ではなく、https://ordinals.com/にアクセスしてるみたい。

PSBTを利用したトラストレスな購入

OpenOrdexのメリットは、自分のローカル環境にDEX機能を起動でき、トラストレスにInscriptionの購入が可能なところで、それにPSBTを利用してる。PSBTは、ウォレット間や複数のユーザー間でトランザクションを完成させるために必要な共通データのフォーマットを定義した仕様↓

Inscriptionの購入フローは以下の通り。

  1. 購入したいInscriptionを選択し、Buy Inscriptionを押す。
  2. 購入者のアドレスを入力する。この時、指定したアドレスにダミーUTXO(=1,000 sat以下のUTXO)がない場合、↓のようにダミーUTXOを作成するPSBTが提示される(指定したアドレスが持つUTXOをインプットとして、1,000 satのダミーUTXOとお釣りのUTXOを持つトランザクション。どうしてこれが必要なのかは後述)。

ダミーUTXOを作成するため、↑のPSBTをファイナライズしてTxをブロードキャストする。lndをウォレットとして使ってる場合は、以下のコマンドでPSBTに対して署名済みのトランザクションを作れる。

$ lncli wallet psbt finalize <↑のPSBT>
{
    "psbt": "<入力したPSBT>",
    "final_tx": "<ファイナライズされたトランザクション>"
}

あとは、ファイナライズされたTxをブロードキャストすればいい。

ダミーUTXOが作成できたら、↑の購入ページをリロードして、再度Buy Inscriptionを押す。すると今度は購入用のPSBTが表示される↓

このPSBTのトランザクションは、以下のような構成になっている(どんなデータか簡単に確認したい場合は、bitcoin-clidecodepsbtコマンド使うといい)。

  • インプット:以下の3つ
    • ↑で作成したダミーUTXO
    • Inscriptionが現在所有されている売り手のUTXO
    • ダミーUTXOと同じアドレスを持つ支払いに使用するUTXO
  • アウトプット:以下の4つ
    • 購入者のInscriptionのUTXO
    • 売り手のアドレスへの支払い
    • 購入者の将来使用可能な新しいダミーUTXO
    • 支払いのお釣り

そして、PSBTのインプットデータとして、各インプットのUTXOが参照するトランザクションデータに加えて、2つめのインプットについては、Inscriptionの売り手の署名データを含む以下のキーのPSBTインプットが提供されている。

  • PSBT_IN_TAP_INTERNAL_KEY:P2TRアウトプットを構成する際に使用したTaprootの内部キー。
  • PSBT_IN_TAP_KEY_SIG:P2TRアウトプットをアンロックするのに必要な署名。
  • PSBT_IN_FINAL_SCRIPTWITNESS:P2TRアウトプットをアンロックするのに必要なすべてのwitnessデータ(今回の場合はPSBT_IN_TAP_KEY_SIGと同じ)。
  • PSBT_IN_SIGHASH_TYPE:インプットに署名する際に使用されるSIGHASHタイプ。

この時、PSBT_IN_SIGHASH_TYPEの値は0x83で、SIGHASH_SINGLE | SIGHASH_ANYONECANPAYで署名されていることが分かる。

SIGHASH_SINGLEは、全インプットとそのインプットと同じインデックスのアウトプットを保護するSIGHASHタイプだが、これにSIGHASH_ANYONECANPAYを組み合わせてるので、このインプットと、同じインデックスのアウトプットを保護するSIGHASHタイプになる。↑の場合、インプットの売り手のInscriptionと、アウトプットの売り手のアドレスへの支払いを保護する(他の部分は他の署名者によって変更可能)。

つまり、このInscriptionを指定額で販売すること(指定額を受け取ること)にはコミットしていて、その原資や所有者については任意に設定可能な署名データになっている。一応↑のようなトランザクション構成になっているけど、他の部分は変更しても売り手の署名は有効なまま。

PSBTには売り手の署名があるので、あとは買い手がPSBTをファイナライズ(自分の署名を追加)すれば購入トランザクションが完成する。トランザクションブロードキャストして実際に買ってみた

※ 今回は実験用に購入したのでlndのウォレット使ってるけど、リアルにInscriptionが欲しい場合は、うっかり失わないようordとかでちゃんと管理する必要がある。

Nostrを利用したInscriptionの販売

購入したInscriptionは、DEXで販売することもできる。List Inscription For Saleボタンを押すと、売値と受け取るアドレスを入力するウィンドウが表示されるので、希望額とアドレスを入力すると、ここでもPSBTが生成される。このPSBTは、InscriptionのUTXOをインプットとして、指定額を指定したアドレスに送信するトランザクションを構成するもの。そして、PSBTのPSBT_IN_SIGHASH_TYPEの値は先程と同じ、0x83(SIGHASH_SINGLE | SIGHASH_ANYONECANPAY)。このPSBTに署名してPublishすると、Nostrのリレーサーバーに販売情報と署名済みのPSBTが配信される。実際にローカルでPublish後、https://openordex.org/を確認すると公開した情報が確認できた。

↑の購入時に提示されるPSBTの販売者の署名は、このPSBTデータから作られている。販売用のPSBTは1インプット、1アウトプットのトランザクションだが、この署名を別のトランザクションに埋め込んでも、インプットとアウトプットのインデックスが同じである限り(販売用のPSBTではインデックス=0で、↑の購入用のPSBTではインデックス=1になる)署名は有効なまま。

Ordinal Theory

Ordinal Inscriptionのベースになっているのが、Bitcoinでマイニングされたすべてのsatoshiに一意の番号を割り当てるOrdinal Theory。Ordinal Inscriptionの所有者の移転もこのルールに従って行われる。

↑の購入Txを見ると分かるけど、インプットのコインが、

  1. ダミーUTXO:1,000 sat
  2. InscriptionのUTXO:6,696 sat
  3. 購入資金のUTXO:46,678

そして、アウトプットのコインが、

  1. Inscriptionの移転先:7,696 sat
  2. 支払い:10,000 sat
  3. 新しいダミーUTXO:1,000 sat
  4. お釣り:30,190 sat

となっている。最初2つのインプット額=先頭のアウトプット(移転先)の額になっているのが分かる。これはOrdinal Theoryで2つのインプットのsatoshiが最初のアウトプットに割り当てられていることを示すもので、これによりInscriptionの所有者が先頭のアウトプットになっているのが分かる。

最初はどうしてダミーUTXOを用意するのが疑問だったけど、

  • 販売用のPSBTのように売り手のInscriptionのインプットと支払い受取のアウトプットが最初に来るとInscriptionの所有者が移転できない
  • SIGHASH_SINGLEで保護可能なのは同一インデックスのインプットとアウトプットなので、支払い受取のアウトプットを1つ後ろにすると、インプットのInscriptionも1つ後ろにずらす必要がある
  • アウトプットの先頭はInscriptionの購入者のUTXOとなるので、販売資金をインプットの先頭に配置できない(インプットの最初2つ分が、先頭のアウトプットに移転されるので)

といった理由からなんだろう。Bitcoinの既存のSIGHASHタイプはそんなに柔軟ではないので、こういう制約が出てくるけど、インプットと任意のインデックスのアウトプットをマッピング可能なSIGHASH_GROUP とかが導入されると、ダミーUTXOは無くせそう。

でもこれ、InscriptionのUTXOが保持している金額は、購入者に渡るのでそれを見越して販売価格設定する必要があるな。あと後から販売価格変えようと思っても、すでに公開したPSBT持ってる人がいたら前の価格で購入される。あと、Inscriptionが購入される度に、ダミーUTXOの価格分、InscriptionのUTXOが保持する金額も増えていくんじゃ?

以上がOpenOrdexでのPSBTの利用方法。誰もトラストすることなく、Inscriptionの販売、購入が可能で、トランザクション手数料以外の手数料を支払う必要もない。それにしても、PSBTとNostrのリレーサーバーを上手く利用してDEX作ってるの面白いな。

実際に紙とペンでCodex32のマスターシードの生成/検証/リカバリーをしてみる

先日書いたCodex32について↓

techmedia-think.hatenablog.com

手計算可能と書いたけど、チェックサムの生成や、シェアの正しさの検証、追加シェアの導出やシェアを使ったリカバリーが本当に手計算可能なのか?実際にやってみる。やり方は、この冊子にまとめられている。

※ 実際にCodex32のシェアをロード可能なウォレットは現時点ではないので、あくまで実験。

準備するもの

Codex32でシェア、シードを作成するのにデジタル機器は必要ない。用意するのは

  • 5個のサイコロ
  • 計算に使用する3つのVolvelle回転盤。冊子のP.21〜27の材料を切り取って組み立てると、3つの回転盤が出来上がる。
    • 加算用:有限体上の要素の加算用の回転盤
    • 変換用:有限体上の要素の乗算用の回転盤
    • リカバリー用:ラグランジュ補間に使用する回転盤

新しいシードの作成

初期シェアの作成

まず新しいシード用にk個の初期シェアを作成する。サイコロの偏り除去ワークシート(P.11、12)を用意しておく↓

  1. 5個のサイコロに対して、それぞれ対応するマーカーを作成し(ポストイットとかに対応するサイコロの番号書くとかでOK)、マーカーをワークシートのFree Spaceの場所に初期配置する。
  2. 5個のサイコロを振って、Free Spaceの隣のDie Padsの各サイコロの出目の部分にマーカーを移動する。
  3. 再度5個のサイコロを振って、今度はサイコロ自体を同じDie Padsの出目の部分に配置する。
  4. もし、サイコロの出目が同じだった場合、そのサイコロについて、2と3を再度行う。
  5. Die Padsのそれぞれ異なる場所にマーカーとサイコロが配置されたら、続いてP.11の右上のワークシートのツリーの頂上からツリーを降りていく。
    • まずDie Tracksの1つめのDie Padsについて、サイコロがマーカーより左にあればツリーを左に降り、右にあれば右に降りる。
    • これを5つのサイコロ分実行すると、最終的にツリーのリーフの1文字に辿り着く。
  6. 1〜5までの作業を繰り返し、26文字を出力する。

この26文字が128 bitのシェアのデータになる。やり直しがなかったとして、1つのシェアを作るのに最低でも5個のサイコロを52回振る必要がある。

チェックサムの計算

続いて、↑のシェアのチェックサムを計算する。チェックサムの計算には、P.17のチェックサムのワークシート↓

と加算用の回転盤↓

と、P.15, 16のチェックサムテーブル↓

を使用する。

  1. まず、ワークシートの非ピンクの太字の四角の中を左上から埋めていく。
    • 一番左上のMS1の後は、閾値パラメーターkの値、4文字の識別子、1文字のシェアインデクスを埋める。
    • それ以降は、先程生成した26文字のシェアを順番に埋めていく。
  2. 続いて、最初の行と2行目を加算し、その値を3行目に埋めていく。この時の加算に、加算用の回転盤を使う。たとえば1行目が2、2行目が3の場合の2 + 3は、↑の加算用の回転盤で▲を2に合わせた上で、回転盤内の3が指す枠の値(M)になる。
  3. 3行目の左端2文字で、P15, 16のMS32 チェックサムテーブルの該当レコードを探し、その値で4行目を埋める。
  4. 2,3を繰り返し、ワークシートの非ピンクの部分を埋めていく。
  5. 非ピンクが埋まったら、今度は下の行からスタートしてピンクの枠を埋めていく。下からなので、加算用の回転盤で回転盤内の枠が指す値をマッピングしてその時▲が指す値が1つ上のピンクの枠の値になる。
  6. すべて埋まったら、対角線上のピンクの太字の枠がチェックサムの値になる。ちょうど13文字。

ここまで完了したら、Codex32エンコードされたシェアが完成する。

※ シェア=シードとする場合は、k = 0、シェアインデックス=sとしてチェックサムを計算する。

チェックサムの検証

↑でシェアは完成したけど、一応チェックサムが正しいか検証しておこう。チェックサムの検証の手順は↓

  1. 新しいチェックサムワークシートを用意する。
  2. MS1以降の右上に番号がついた太枠のマスを、さっき計算したCodex32文字列(48文字)で埋めていく(ピンクの部分も含めて)。
  3. さっきと同じように、上から順に加算用の回転盤を使って今度は一番下まで計算していく。
  4. 最終行がSECRETSHARE32となったら検証成功。

追加シェアの生成

閾値の数分↑の方法で初期シェアを作成したら、追加のシェアを作成できるようになる。

追加シェアを導出するのに使用するのは、k個の初期シェアと、追加分のチェックサムワークシートと、Translationワークシート(P. 18〜20)↓

↑は、P.19のk = 2の場合のワークシート。kの値によって使用するワークシートが異なる。さらにtranslation/fusion用の回転盤↓

と、加算用の回転盤を使用する。

追加シェアの導出方法は(今回はk = 2で行う)、

  1. 最初にk = 2のTranslationワークシート(P. 19)をコピーする。
  2. 左の列の上2つに使用する初期シェアのシェアインデックスを記入する(今回は、AC)。
  3. 2の下に導出するシェアのシェアインデックスを記入する(今回はD)。
  4. 2のシェアインデックスの右隣のマスにTranslationシンボルを記入する。このシンボルは、kの値毎に用意されている変換テーブルを使って導出する。k = 2の場合は↓(他の閾値のテーブルは冊子のModule 2に含まれてる)
    • 今回はDを導出するので、AのシンボルはΠCのシンボルはρ
  5. 続いて既存のシェアの文字をTranslation回転盤を使って変換していく。
    • まず、回転盤のFusionの面で回転盤をシェアインデックスに対応するシンボルに合わせる(↑のAのシェアであればΠに合わせる)。
    • 合わせたら、回転盤を裏返してTranslationを表にする。そして各シェアの文字をそれが▲で指す文字に変換してマスを埋めていく。
  6. 5をk個分繰り返して既存のシェアの変換を終える。
  7. k個埋まったら、加算用の回転盤を使って縦の文字を加算して最終行のマスを埋める。

7を全部埋め終わったら、それが新しいシェアになる。新しいシェアインデックスに対してこれを繰り返せば追加のシェアを作っていける。

マスターシードのリカバリ

続いて、リカバリーをやってみる。シェアの生成や検証ができれば、シードのリカバリーは普通は対応するウォレットにシェアをロードすればいいので、このリカバリー自体を手動でやることはあまりないかも。

  1. リカバリーに使用するk個のシェアを準備する。
  2. 各シェアが正しいかチェックサムを検証する(↑に書いた方法で)。
  3. リカバリーはシェアインデックスがsのデータをTranslationワークシートを使って計算する。計算方法は追加シェアの導出とほぼ同じで、シンボルの導出にリカバリー用の回転盤を使用する部分だけ違う↓
    • リカバリー用の回転盤の枠を使用する1つのシェアインデックスに合わせる。その状態でもう1つのシェアインデックスが指すシンボルが枠に合わせたシェアに適用するシンボルになる。
    • たとえば、シェアインデックスがADのシェアを使う場合、
      • Aのシンボルは、Aを枠に合わせた状態でDが指すΛ
      • Dのシンボルは、Dを枠に合わせた状態でAが指すΘ
    • 各シンボルが見つかったらそれをTranslationワークシートに記載して、追加シェアの導出と同じように計算する。
  4. 加算が終わると、シェアインデックス = SのマスタシードをエンコードしたCodex32文字列が入手できる。

実際にBIP-32のシードにするには、導出したCodex32データのペイロードをbit変換する必要がある。

※ k > 2の場合は、↑の手順3でピックアップするシンボルが1つのシェアに付き複数になる。この複数のシンボルを融合して1つのシンボルにする必要がある。これにはFusion回転盤を使用する。

  1. まず最初のシンボルをFusion回転盤の枠に合わせる。
  2. その状態で、内側の回転盤内で次のシンボルを見つける。このシンボルが新しいシンボルなので、そのシンボルに外側の回転盤の枠を合わせる。
  3. 2をすべてのシンボル分繰り返した最後のシンボルが融合後のシンボルで、これをTranslationワークシートに記載する。

感想

本当に手作業だけで、シェアの生成、検証、シードのリカバリーが可能だった。作業するのに1時間以上はかかるけど。

↑のようにCodex32は回転盤を使ってチェックサムやシャミアの秘密分散法の計算を行うスキーム。その数学的な背景については、以下で公開されてる↓

https://secretcodex32.com/docs/2022-09-26--math.pdf

よくこんなの考えるなー。

手計算でBIP-32シードを生成/検証可能な新しいシードエンコード方式Codex32

Bitcoinの主要ウォレットはBIP-32 HDウォレットをサポートしており、単一のマスターシードから、支払いや受け取りに使用するすべての鍵を導出するようになっている。オンチェーンの資金は、基本的にこのマスターシードだけ保持していれば、そこからリカバリーができる。

既存のエンコード方法

このマスターシードのエンコード方法として現在最も主流なのが、BIP-39ニーモニックワードとしてエンコードする方法。12個や24個の単語として覚えておく方法。

もう1つはSLIP-39。こちらは、BIP-39が単一のシードを単語に変換するのに対し

  • シャミアの秘密分散法を利用してマスターシードを複数のシェアに分割し、
  • 各シェアをニーモニックワードにエンコード
  • 予め設定した閾値数分のシェアを集めたら、マスターシードを復元できる

TrezorのShamir Bakupなどで採用されている。

Codex32

↑のような方式を使わずに、マスターシードそのまま保存するということも可能だけど、データの欠落やコピーミスなんかで、誤ったデータになっていないか確認できる機能は欲しい。

最近このマスターシードについて、Codex32という新しいエンコード方式のBIPドラフトが提案された↓

https://github.com/apoelstra/bips/blob/2023-02--volvelles/bip-0000.mediawiki

Codex32の機能については、↑のBIPよりこのウェブサイトの方が分かりやすいかも。

Codex32では、マスターシードをBech32のアルファベット(BIP-173参照)を使って

2種類のエンコード方法をサポートしている。

既存のエンコード方法との違いは、

  • 単語リストを使わずに、Bech32のアルファベットを使用するので、エンコード結果はコンパクトになる。
  • ソフトウェアを使わずに手計算で、シェアやシードの生成や検証ができる。

特に後者が特徴的で、シェアの正しさの検証のためにデジタル機器にシェアを入力する機会をなくすことができる。

一方で、手計算をサポートするため、BIP-39でサポートされるようなシードに対するパスフレーズの設定はできない。

データフォーマット

Codex32のフォーマットは、BIP-173のBech32フォーマットと似ており、以下のデータで構成される。

  • 人が識別可能な部分:ms
  • セパレーター: 1
  • データ部:
    • 閾値パラメーター(k):2〜9までの1桁の閾値。もしくは0。このため、Codex32でサポートされる閾値の最大値は9。
    • 識別子(ID):4つのbach32文字で構成される、このシェアを識別するための任意の値。
    • シェアインデックス:シェアのインデックスを表す値で、任意のbech32文字。
    • ペイロード:最大74文字のbech32文字列で、シェアやシードの値
    • チェックサム:13文字のbech32文字列のチェックサム

シードもシェアも同じこのフォーマットを使用する。シェアインデックスがsの場合、シードを直接エンコードしたもので、それ以外の場合はシェアをエンコードしたデータになる。

新しいマスターシードの生成

新しくマスターシードを生成する場合、まず先に閾値分のシェアを生成して、そのデータからマスターシードを生成する。具体的な手順は、

  1. マスターシードのビットサイズを決める。128 bit〜512 bitの範囲で、8の倍数であること。
  2. 閾値kを決める(2〜9)
  3. 4文字の識別子を決める。
  4. k回分、ランダムにシェアを生成する↓
    1. bech32のアルファベットの先頭から順次文字をピックアップしてシェアインデックスとする。
    2. ここまでで、プレフィックスms1閾値k、4文字の識別子、シェアインデックスの9文字が揃う。
    3. シードのビットサイズ / 5を切り上げた個数分、ランダムなbech32文字を選択する(128 bitの場合26文字)。
    4. 13文字のチェックサムを計算し、追加する。

結果、k個のシェアをエンコードしたリストができる。シェアのランダムなbech32文字の選択方法については、特に明記されてないけど、サイコロとワークシート使った導出方法とかは紹介されてる。

マスターシードは、このk個のシェアからシャミアの秘密分散法によって計算される。↑のシェアインデックスをxの値として、ランダムなシェアの値と合わせてラグランジュ補間でマスターシークレットを導出するみたい。

マスターシードは、x = 16として多項式を評価した値で、bech32文字の16番目の要素がsなので、マスターシードのシェアインデックスはsになってるっぽい。

補間したデータのシークレット値は、8bit単位に変換し、過剰分を切り詰めるとマスターシードになる。

新しいシェアの生成

閾値分のシェアが準備できたら、他のシェアも生成することができる。シェアの生成は↑のマスターシードの計算方法と同様で、異なるのはラグランジュ補間で多項式を評価する際の値だけ。マスターシードの場合はsだったけど、代わりに新しく生成するシェアのインデックスをx値として評価することで、シェアが導出できる。

既存のマスタシードを使用する場合

既にあるマスタシードを利用する場合は、まず最初にそのシードデータを以下の手順でCodex32フォーマットに変換する。

  1. 閾値kを決める。
  2. 4文字の識別子を決める。
  3. シェアインデックスをsとする。
  4. マスターシードを8 bit 単位から5 bit単位に変換し、Bech32文字に変換する。
  5. チェックサムを計算する。

これでマスターシードのCodex32文字列ができるので、続いて、k-1個のシェアを生成する。この時、シェアの生成方法は↑の新しいマスターシードの生成方法と同じでランダムにシェアを生成する。

k-1個ランダムに選択したシェアとx = s = 16となるシードデータがあれば、後はそれを使っていくつでもシェアを生成できる。k個のシェアが作れたらマスターシードのCodex32データはマスターシードごと削除してもいい。

チェックサムの計算

チェックサムは、

を元に計算される13文字のbech32文字で、最大4文字の誤り、最大8文字の消失を訂正できる機能を持つ。BIP-173と同じ文字セットを使用したBCH符号ベースのチェックサムだが、文字数やパラメーター、計算対象(hrpは含まない)、bit変換時の不要データの扱い(切り詰め)などは異なる。

ロングCodex32

↑の13文字のチェックサムでサポートされるデータ部は最大80文字(ペイロードは74文字、46バイトまで)で、それを超えるサイズのシードデータを扱う場合には、15文字のロングチェックサムを持つ、ロングCodex32フォーマットを用いることになる。

BIP-32のシードは32バイトで通常のCodex32フォーマットで十分なものの、BIP-32ではこのシードを最大64バイトにすることもでき、この場合は通常のCodex32ではエンコードできない。このようなシードをエンコードする場合にロングCodex32が使用され、この場合

シェアの生成方法やマスターシードのリカバリー方法は通常のCodex32と同様。

Rubyで実装

Pythonコードスニペットを参考にRubyで実装してみた↓

github.com