Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

PSBT Bitcoin

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-cliのdecodepsbtコマンド使うといい）。

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

そして、PSBTのインプットデータとして、各インプットのUTXOが参照するトランザクションデータに加えて、２つめのインプットについては、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は１インプット、１アウトプットのトランザクションだが、この署名を別のトランザクションに埋め込んでも、インプットとアウトプットのインデックスが同じである限り（販売用の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

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

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

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

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

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

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

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

Bitcoin

先日書いたCodex32について↓

techmedia-think.hatenablog.com

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

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

準備するもの

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

  • 5個のサイコロ
  • 計算に使用する３つの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の１つめのDie Padsについて、サイコロがマーカーより左にあればツリーを左に降り、右にあれば右に降りる。
    • これを5つのサイコロ分実行すると、最終的にツリーのリーフの1文字に辿り着く。
  6. 1〜5までの作業を繰り返し、26文字を出力する。

この26文字が128 bitのシェアのデータになる。やり直しがなかったとして、１つのシェアを作るのに最低でも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つに使用する初期シェアのシェアインデックスを記入する（今回は、AとC）。
  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つのシェアインデックスが指すシンボルが枠に合わせたシェアに適用するシンボルになる。
    • たとえば、シェアインデックスがAとDのシェアを使う場合、
      • 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

BIP Bitcoin

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

既存のエンコード方法

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

もう１つは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

KZG commitmentをRubyで実装してみた

Cryptography Ruby kzg

多項式コミットメントの１つであるKZG commitmentについて↓

techmedia-think.hatenablog.com

より詳しく理解するためにRubyで実装してみた↓

https://github.com/azuchi/kzg/

セットアップ

KZG commitmentはまず最初に公開パラメーターを生成する。これは基本的に、多項式の最大次数が変わらない限り、最初に１回すればいい計算。

計算自体は単純で、シークレット値（sとする）を生成して、BLS曲線のPointG1のジェネレーターポイントに対して（Gとする）、 {sG, s^{2}G, s^{3}G, ..., s^{n}G}を計算する。同様にPointG2のジェネレーターポイントに対して（Hとする）も。

このシークレット値は知られるといけない値なので、基本的にTrusted Setupになる。最近EthereumでもPROTO-DANKSHARDINGで使用するためのパラメーターを生成するセレモニーやってる。

今回は、調査目的なので適当なシークレット生成してセットアップする（※ 運用用途では使わないように）。

require 'kzg'

secret = xxx # secret number
n = 10
setting = KZG.setup_params(secret, n)

↑で9次の多項式まで表現できるパラメーターを生成。※ Pure Rubyで書いてるので、ちょっと遅い。

コミットメントの作成

続いて任意の多項式に対するコミットメントを作成は↓

coefficients = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
commitment = KZG::Commitment.from_coeffs(setting, coefficients)
commitment.value # コミットメント値

↑は {10x^{9} + 9x^{8} + 8x^{7} + 7x^{6} + 6x^{5} + 5x^{} + 4x^{3} + 3x^{2} + 2x + 1}へのコミットメントになる。

コミットメントの計算の結果得られるのは、多項式の各係数をBLS曲線の有限体の要素として対応する各公開パラメーター（PointG1の点）に乗算して、それらを加算したPointG1の点。

プルーフの作成

続いて、コミットした多項式の評価値（あるxの値におけるf(x)の値）を多項式を開示することなく証明する。たとえば↑の多項式で、x = 35とした場合、f(35) = 808951170278371であることを証明するプルーフを作成する。

proof = commitment.compute_proof(35)

この計算の中身は、

{q(x) = \frac{f(x) - 808951170278371}{x - 35}}のようなq(x)が成立するのは、f(35) = 808951170278371の場合のみ。

このプルーフもPointG1の点となる。

検証

コミット値と↑の証明を提供することで、(x, f(x)) = (35, 808951170278371)がコミットされた多項式の評価結果であることを検証することができる。

x = 35
y = 808951170278371

setting.valid_proof?(commitment.value, proof, x, y)

ここでは、BLSのペアリング特性を利用して、 {\displaystyle e(\pi, (s - x)H) = e(C - yG, H)} が成立するか検証する。つまりBLSを使って、(x, f(x))のペアに対して、↑のq(x)が成立することを検証している。

↑のペアリングの計算から分かるけど、KZG commitmentの単一のプルーフにおいては、PointG2側の公開パラメータ（ {sH, s^{2}H, s^{3}H, ..., s^{n}H}）は、最初のsHのみで済む。

Vector commitmentとしての利用

↑のKZG commitmentをVector commitmentとして利用する場合は、多項式の評価値がコミットする値になる多項式を構成する。たとえば、[3, 2, 9]という３つの値にコミットする場合、(x, f(x))が(1, 3), (2, 2), (3, 9)となる点を通過する多項式を構成する。多項式補間を利用すればこのような多項式を計算することができる。

x = [1, 2, 3]
y = [3, 2, 9]

# x, y座標から多項式を構成
polynomial = KZG::Polynomial.lagrange_interpolate(x, y)

# 計算した多項式のコミットメントを作成
commitment = KZG::Commitment.from_coeffs(setting, polynomial.coeffs)

# x = 3の場合のプルーフを計算
proof = commitment.compute_proof(3)
# f(3) = 9であることを検証
setting.valid_proof?(commitment.value, proof, 3, 9)

今回は、ラグランジュ補間を使って実装してみたけど、go-kzgとかではFFT使ってる。

ということで、実際に実装してみるとふんわり理解してたところが、少し明確になった。次はマルチプルーフとか作ってみるかな。

ウォレットからラベルをエクスポート/インポートするフォーマットを定義したBIP-329

BIP Bitcoin

先日、Bitcoinのウォレットからラベルをエクスポートしたりインポートするためのフォーマットを定義したBIP-329が公開されたので見ておく↓

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

BIP-32のHDウォレットやBIP-39のようなニーモニック、BIP−44によるマルチアカウント階層の定義など、マスターシードや拡張秘密鍵をエクスポートして他のウォレットにインポートすることで、ウォレット間の移行は割と簡単にできるけど、その際に各ウォレットで付けられたラベルの情報は欠落してしまう。

そんなラベルの情報もウォレット間で移行できるようにするため、エクスポート/インポートするためのフォーマットを定義しようというのがBIP-329。

データのフォーマットはJSON Linesフォーマットで、現在、以下のデータに対するラベルのフォーマットが定義されている。JSONベースなので、その後の拡張も簡単。

フォーマットの仕様や、実際のデータイメージは、↓のBIPの意訳参照。

概要

このドキュメントは、ウォレット内のさまざまな共通タイプのレコードに添付できるラベルのエクスポートフォーマットを定義する。

著作権

このBIPはBSD 2-clauseライセンス。

動機

異なるBitcoinウォレットアプリケーション間での、資金のエクスポートとインポート方法は、BIP39やBIP32、BIP44などの標準で明確に定義されている。これらの標準は十分にサポートされており、ユーザーは異なるウォレット間で資金を簡単に移動することができる。しかし、ユーザーが自分のウォレット内のトランザクションやアドレス、公開鍵、インプット、アウトプット、xpubに適用したラベルを移行するために定義された標準はない。Bitcoinが使用するUTXOモデルは、外部から受け取った資金であれ、前のトランザクションのお釣りとして受け取った資金であれ、資金の出所を示す可能性があるため、これらのラベルを価値あるものにしている。どちらの場合も、望ましくない個人情報の漏洩を避けるため、支払い時に注意を払う必要があり、ラベルはこの点で貴重なガイダンスを提供し、いくつかのBitcoinウォレットで使用する際に必須にもなっている。標準化された方法でラベルをインポートおよびエクスポートできるようにすることで、ユーザーが特定のウォレットアプリケーションにロックインされることが無いようにする。

論拠

現在、ラベルのエクスポートとインポート用に広く受け入れられているフォーマットはないが、いくつか使用されている既存のフォーマットがある。SLIP-0015は、アドレスとアウトプットのラベルをエクスポートするためのフォーマットを定義しているが、ウォレットシードと関連する秘密鍵を使用して暗号化する必要があるため、秘密鍵にアクセスできないコーディネーターウォレットが単独で使用することはできない。Electrumウォレットは、アドレスとトランザクションのラベルをJSON形式でインポート/エクスポートしており、他のレコードタイプでも使用できるものの、使用されているフォーマットは自己記述型ではないため、レコードタイプの識別が難しい。

仕様

このBIPでは、軽量で可読性が高く、構造化されているため、JSONフォーマットを使用する。さらにJSON Linesフォーマットを使用する。これにより、ドキュメントの分割や、ストリーミング、インクリメンタルな追加が可能となり、フォーマットエラーによるインポート全体の無効化の可能性を制限することができる。また、行指向であることが多いコマンドライン処理にも便利な形式である。

JSON Lines仕様に加えて、ウォレットからのラベルのエクスポートは、有効なJSONオブジェクトで構成される1行につき1レコードを含むUTF-8エンコードされたテキストファイルである必要がある。行は\nで区切られる。複数行の値は許可されない。各JSONオブジェクトには、以下に定義する3つのkey/valueのペアが含まれていなければならない：

キー 定義
type tx、addr、pubkey、input、output、xpubのいずれか。
ref トランザクション、アドレス、公開鍵、インプット、アウトプットまたは拡張公開鍵への参照。
label 参照先に適用されるラベル

参照は、以下のようにタイプごとに定義される：

タイプ 定義 サンプル
tx hexフォーマットのトランザクションID f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd
addr base58またはbech32フォーマットのアドレス bc1q34aq5drpuwy3wgl9lhup9892qp6svr8ldzyy7c
pubkey 32、33、65バイト公開鍵のhexフォーマット 0283409659355b6d1cc3c32decd5d561abaac86c37a353b52895a5e6c196d6f448
input コロン区切りのトランザクションIDとインプットのインデックス f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd:0
output コロン区切りのトランザクションIDとアウトプットのインデックス f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd:1
xpub BIP32で定義されている拡張公開鍵 xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8Nq...

プライバシーに配慮したデータであるため、エクスポートする際には注意が必要。信頼できないネットワークを経由する場合は、暗号化を強く推奨し、保管中の暗号化も検討する必要がある。暗号化されていないエクスポートデータは、できるだけ早く削除する必要がある。セキュリティ上の理由から秘密鍵のタイプは定義されていない。

インポート

  • インポートするウォレットは、保存していないレコードを無視し、必要に応じてラベルを切り捨てることができる。
  • 公開鍵レコードをインポートするウォレットは、既知のウォレットアドレスと照合するため、、それらからアドレスを導出する場合がある。
  • 拡張公開鍵をインポートするウォレットは、例えばマルチシグの設定において、署名者と照合する場合がある。

後方互換性

このフォーマットの性質により、他のレコードタイプを処理できるように自然に拡張することができる。ただし、この仕様に準拠したウォレットをインポートする場合、ここで定義されていないタイプは無視される可能性がある。

Test Vector

以下の断片が、ウォレットラベルエクスポートを表している。

{ "type": "tx", "ref": "f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd", "label": "Transaction" }
{ "type": "addr", "ref": "bc1q34aq5drpuwy3wgl9lhup9892qp6svr8ldzyy7c", "label": "Address" }
{ "type": "pubkey", "ref": "0283409659355b6d1cc3c32decd5d561abaac86c37a353b52895a5e6c196d6f448", "label": "Public Key" }
{ "type": "input", "ref": "f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd:0", "label": "Input" }
{ "type": "output", "ref": "f91d0a8a78462bc59398f2c5d7a84fcff491c26ba54c4833478b202796c8aafd:1", "label": "Output" }
{ "type": "xpub", "ref": "xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8", "label": "Extended Public Key" }