Develop with pleasure!

福岡でCloudとかBlockchainとか。

楕円曲線上の点を出力するハッシュ関数の標準化 Hash to Curves

楕円曲線を使用したPedersen CommitmentやBLS署名など、誰もその離散対数を知らない点を利用する暗号プロトコルを最近よく見かける。ただ、プロトコルの説明では、そのような点の導出方法があまり詳しく書かれていなかったりすることもあり、アルゴリズムの選択を誤ると脆弱性の原因となる可能性が出てくる。

そんな点の導出方法について、さまざまな楕円曲線に対応した推奨アルゴリズムを定義しようというのが、現在IETFでドラフトが提案されている任意の入力値を楕円曲線上の点に変換するハッシュ関数

datatracker.ietf.org

ハッシュ関数の仕様

この仕様では、入力値(バイト列)を楕円曲線の点にエンコードするのに以下の3つの関数を定義している。※ 正式な仕様は↑参照。

hash_to_field

hash_to_field関数は、任意の入力値(バイト列)msgを有限体F上の1つ以上の要素にハッシュする関数。

  • 入力
    • 任意の入力値msg
    • 出力する要素の数count
  • 出力
    • count個の有限体Fの要素のリスト

hash_to_field関数は、まず補助関数expand_messageを呼んで、msgハッシュ値を計算する。仕様では、SHA-2やSHA-3、BLAKE2のハッシュ関数に加えて、可変長の出力値をサポートするSHAKE128、BLAKE2Xが利用可能になっている。 続いて、生成したハッシュ値を有限体F上の要素として解釈する。※ expand_message関数は、countで指定した要素数を満たす長さのランダムデータを出力する。

具体的な疑似コードは、5.1章に記載されてる

map_to_curve

map_to_curve関数は、有限体F上の要素から有限体F上に構成された楕円曲線E上の点を計算する写像関数。

  • 入力
    • 有限体Fの要素u
  • 出力

写像関数自体は、対象とする楕円曲線の形式(モンゴメリ曲線、ワイエルシュトラス曲線、ツイストされたエドワーズ曲線など)によって、それぞれ推奨されるロジックがある模様。具体的な仕様は、6章で定義されている。SSWU(Simplified Shallue-van de Woestijne-Ulas)方式とか*1、Elligator 2方式とか。

基本的には楕円曲線の方程式から座標を計算することになるので、y座標の候補は2つ存在することになる。この曖昧さの解消のため、関数の入力値でy座標の偶奇を指定できるようにしているっぽい。どちらかに固定すると出力される点の数が半分になるから?

clear_cofactor

clear_cofactor関数は楕円曲線E上の点を部分群G上の点に変換する関数。

Bitcoin楕円曲線secp256k1やNISTの曲線P-256、P-384、P-521などcofactor = 1の曲線においては、この操作は必要ない。

2つのエンコード方式

基本的には上記の3つの関数を順に実行して、任意の入力値を楕円曲線G上の点に変換する。

  1. hash_to_field関数で有限体Fの要素を出力
  2. 1の要素をmap_to_curve関数で楕円曲線上の点に変換
  3. 2の点に対してclear_cofactor関数を実行した点が最終的に出力される点

上記のシンプルなエンコード方式をencode_to_curve関数として定義している。ただ、この関数は入力値に対して出力される点が一様にランダムではないとされていて、一様に分布する点を出力する関数としてhash_to_curve関数を定義している。この関数の処理は、

  1. hash_to_field関数で有限体Fの要素を2つ出力(count = 2を指定)
  2. 1の2つの要素をmap_to_curve関数で楕円曲線上の点に変換(Q0, Q1)
  3. 2の2つの点を加算してR = Q0 + Q1を計算
  4. 3の点Rに対してclear_cofactor関数を実行した点が最終的に出力される点P

というもので、出力する有限体の要素が2つになり、それらの点を加算しているのが違い。これが一様な分布でG上の点を出力するポイントなのか。

暗号スイート

現在定義されている暗号スイートのリストがこちら

Bitcoinが採用しているsecp256k1以外に、NIST系の曲線やcurve25519、BLS12-381などが定義されている。これ以外の楕円曲線を利用したHash to Curveを定義する方法はこちら

参照実装

参照実装はこちら。現状、Sage、Go、Rustで書かれたものがある。

Hash and Increment

単純な楕円曲線ハッシュ関数だとHash and Incrementという手法がある。ハッシュ値楕円曲線上の点のx座標として対象となる点を探し、有効な点でなければ有効な点が見つかるまでハッシュ値を1ずつインクリメントしていく。

この場合、入力する値によって計算コストが変わってくるのと、定数時間処理にするのが難しいので、今回のHash to Curvesみたいな提案が出てきてるのかな。

*1:曲線の方程式のパラメーターa, bが0の場合(secp256k1やBLSなどの曲線の場合)、SSWU方式はそのまま使えないので、aとbが0ではない同種写像を持つ曲線を使ってSSWUで計算した点を、元の曲線の点に変換するSSWUAB0方式が採用されている。

Erlayをサポートするために必要なP2Pプロトコルを定義したBIP-330

Bitcoinで新しいトランザクションリレープロトコルの提案Erlayをサポートするために必要な、新しいP2Pメッセージを定義したBIP-330が公開されてたので見てみる↓

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

BIP-330では、以下の5つの新しいP2Pメッセージとそのプロトコルフローが定義されてる。

  • sendtxrcncl:ノード間でトランザクションの照合をサポートを通知するためのメッセージで、ノードとのハンドシェイク時にやりとりする。
  • reqrecon:ノード間で照合ラウンドを開始する際のメッセージ。
  • sketch:照合のために必要なスケッチを送信するためのメッセージ。以下の2つのケースで送信される。
    • reqreconを送信したノードに対して、受信側のノードが自身の未通知のトランザクションから作成したスケッチを送信する際。
    • スケッチのデコードに失敗したノードからreqsketchextが送られてきた場合に、拡張スケッチを作成し、それを送信する際。
  • reqsketchext:照合に失敗して、差分を見つけるのに拡張スケッチが必要であることを相手ノードに伝える際のメッセージ。
  • reconcildiff:照合の結果、送信者が持っていないトランザクションを相手ノードに伝えるためのメッセージ。

2つのノード間のセットの照合の仕組みであるMinisketchについては、以前書いた記事参照↓

techmedia-think.hatenablog.com

各メッセージの詳細仕様や、プロトコルのフローについては、以下のBIPの意訳参照↓

Bitcoin Coreへの実装は、現在PRのドラフトが作成されており、sendtxrcnclの実装はマージされており、残りはまだこれから。

概要

このドキュメントは、効率的なトランザクションリレープロトコル(例:Erlay)の構成要素である、2つのノード間のトランザクション照合の通知のためのP2Pプロトコルの拡張を定義するものである。これは、ほぼ帯域幅コストをかけずにネットワークの接続性を高めるための一歩となる。

動機

現在のBitcoinネットワークでは、32バイトのトランザクションIDが、invメッセージを介して、接続されたピア間で少なくとも一方向に通知される。その結果、トランザクションの通知コストが高くなる:O(ノード数✕ノード毎の接続数)。

このドキュメントで提案する技術を使用する照合ベースのプロトコルは、invベースのフラッディング方式よりも優れたスケーリング特性を持つことができる。

ネットワークの接続性を高めることで、パーティショニング攻撃に対する堅牢性を高めることができる。したがって、(高オーバーヘッドなしに)トランザクションリレーの帯域幅をO(ノード数)に改善すれば、接続性を高めることでネットワークのセキュリティを向上させることができる。また、Bitcoinノードの実行に必要な帯域幅を削減し、より多くのユーザーがフルノードを実行できるようにする可能性がある。

Erlay

Erlayは、帯域幅効率のために設定されたセット(集合)の照合(set reconciliation)を使用する高レベルのトランザクションリレープロトコルの例である。

ここで説明する内容は、プロトコルの修正版であることに注意してほしい(ペーパーに記載されているものとは異なる)。

Erlayでは、フラッディング(invメッセージを使用してすべてのピアに通知する)と照合の両方を使ってトランザクションを通知する。フラッディングは高価なため、Erlayでは接続の小さなサブセットでの高速リレーを促進するために、必要な場合にのみ フラッディングを使用する。

効率的なセットの照合は、フラッディングによってトランザクションを受け取らなかったノードにトランザクションを配信し、さらに残りの接続の同期を確実にすることを意図している(直接接続しているノードのペアは、互いに知らないものはないはず)。

効率的なセットの照合は、次のように動作する。

  1. 各ノードは各ピア用に照合セットを保持し、このプロトコルが無ければinvメッセージを使用して通知されたであろうトランザクションが配置する。
  2. 時々、各ノードはその照合キューから照合するピアを選び、その結果、双方が相手側に知られているトランザクションを知ることになる。
  3. 照合ラウンドが終われば、対応する照合セットをクリアする。

セットの照合ラウンドの詳細は以下を参照。

Erlayは、

このドキュメントでは、トランザクションリレーのための効率的な照合ベースのプロトコル(Erlayなど)を可能にするために必要なP2Pレイヤーの拡張を提案する。

仕様

新しいデータ構造

P2Pプロトコルでは、まず効率的なトランザクションリレーを支援するためにいくつかの新しいデータ構造が導入される。

32 bitの短縮トランザクションID

短縮IDは以下のように計算される:

  • 双方から与えられるエントロピー {salt_1} {salt_2}とする。これらの交換方法の詳細については、sendtxrcncl参照。
  •  {salt_1 < salt_2}となるように2つのsaltをソートする(どちらが何を送ったかは重要ではない)。
  •  {h = TaggedHash("Tx Relay Salting", salt_1, salt_2)}を計算する。この2つのsaltは、64 bitのリトルエンディアンのバイトオーダーでエンコードされ、TaggedHashはBIP-340で定義されているもの。
  • hのリトルエンディアンのバイトオーダーの先頭8バイトを64 bit整数として解釈したものを {k_0}とする。
  • hのリトルエンディアンのバイトオーダーの2つめの8バイトを64 bit整数として解釈したものを {k_1}とする。
  •  {s = SipHash-2-4((k_0, k_1), wtxid)}とする。ここでwtxidはBIP-141で定義されたwitnessデータを含むトランザクションハッシュ。
  • 短縮IDは、1 + (s mod 0xFFFFFFFF)

この結果、IDは[1..0xFFFFFFFF]の範囲に一様に分布し、これは32 bitのスケッチの要素として使用するための条件となる。詳しくは次の段落を参照。

短縮トランザクションIDのスケッチ

照合ベースのリレーでは、Fuzzy Extractorsのペーパーで紹介されたBCHベースの安全なスケッチPinSketchを使用する。

  • スケッチには所定の容量があり、セットの要素数が容量を超えない場合は、スケッチをデコードすることで、常にセット全体を復元することができる。容量cの非ゼロのbビット要素のスケッチはbc bitで格納できる。
  • 2つのセット間の対称差(つまり、一方のセットにはあるが、両方のセットにはないすべての要素)のスケッチは、2つのセットのスケッチを結合することで入手できる。

ここで使用されるスケッチは、有限体 {GF(2^{32})}の要素で構成される。具体的には、有限体の要素を {x^{32} + x^{7} + x^{3} + x^{2} + 1}を法とするGF(2)上のxの多項式として表す。整数を有限体の要素にマップするには、整数の各ビットi(値 {2^{i}})を多項式表現における {x^{i}}の係数として扱えばいい。たとえば、整数 {101 = 2^{6} + 2^{5} + 2^{2} + 1}は、フィールド要素 {x^{6} + x^{5} + x^{2} + 1}マッピングされる。これらのフィールド要素は、互いに加算、乗算することができるが、その具体的な内容は本ドキュメントの対象外である。

容量cの短縮IDのスケッチは、c個のフィールド要素のシーケンスで構成される。1つめは、セット内の短縮IDの和、2つめはすべての短縮IDの3乗和、3番目は5乗和...となり、最後の要素(2c - 1乗の和)まで続く。これらの要素はリトルエンディアンのバイトオーダーの32ビット整数としてエンコードされ、4c byteでシリアライズされる。

以下は、スケッチの作成をするPython 3.2+のコード実装。

FIELD_BITS = 32
FIELD_MODULUS = (1 << FIELD_BITS) + 0b10001101

def mul2(x):
    """Compute 2*x in GF(2^FIELD_BITS)"""
    return (x << 1) ^ (FIELD_MODULUS if x.bit_length() >= FIELD_BITS else 0)

def mul(x, y):
    """Compute x*y in GF(2^FIELD_BITS)"""
    ret = 0
    for bit in [(x >> i) & 1 for i in range(x.bit_length())]:
        ret, y = ret ^ bit * y, mul2(y)
    return ret

def create_sketch(shortids, capacity):
    """Compute the bytes of a sketch for given shortids and given capacity."""
    odd_sums = [0 for _ in range(capacity)]
    for shortid in shortids:
        squared = mul(shortid, shortid)
        for i in range(capacity):
            odd_sums[i] ^= shortid
            shortid = mul(shortid, squared)
    return b''.join(elem.to_bytes(4, 'little') for elem in odd_sums)

minisketchライブラリは、これらのスケッチの構築、結合、デコードを効率的に実装している。

プロトコルフロー

セットの照合は、主にリクエストに応じた照合セットスケッチの送信とデコードで構成される。

スケッチはwtxidベースなので、双方のピアがBIP-339サポートを通知した場合にのみ、Erlayのネゴシエーションとサポートが有効になるはず。

https://github.com/bitcoin/bips/raw/master/bip-0330/recon_scheme_merged.png

スケッチの拡張

ノードが受信したスケッチから、セットの差分を再構築できない場合、ノードはスケッチの拡張を要求する。ピアは次に拡張を送信する。拡張というのは、同じトランザクションで(より多くの差分をデコード可能な)より容量の大きいスケッチから、最初にすでに送信されたスケッチを差し引いたもの(帯域幅を節約するため)を指す。この最適化を可能にするため、イニシエーターは最初に受信したスケッチをローカルに保存することになっている。スケッチの拡張は、単に新しい要素を配列に連結するだけなので、この最適化は可能だ。

新しいメッセージ

いくつかの新しいプロトコルメッセージ:sendtxrcnclreqreconsketchreqsketchextreconcildiffが追加される。このセクションでは、そのシリアライズ方法、内容、セマンティクスについて説明する。

以下では、整数はすべてリトルエンディアンのバイトオーダーでシリアライズされる。ブール値は1バイトでエンコードされ、正確に0か1でなければならない。配列は、他のP2Pメッセージと同様、長さを表すCompactSizeというプレフィックスを付けてシリアライズされる。

sendtxrcncl

sendtxrcnclメッセージは、照合プロトコルのサポートを通知する。これは一度だけ送信され、サポートしないノードでは無視されることが期待される。

verackの前にwtxidrelayを付けて送信すること(順序は問わない)。

verackの後にsendtxrcnclが送信された場合、送信者は切断されるはずである。

sendtxrcnclverackの前に送信されたが、verackまでにwtxidrelayメッセージが受信されない場合、sendtxrcnclは無視されるはずである。接続は正常に進行するが、照合はサポートされないようにする必要がある。

相手側がversionトランザクションリレーをサポートしない(fRelay=0)と指定した場合は、送信してはならない。それ以外の場合、送信者は切断されるべき。

このペイロードは、以下で構成される:

名称 定義
uint32 version 送信者は現在1にセットする必要があり、それ以外の場合は受信者はメッセージを無視する必要がある。v1は最小のプロトコルバージョンで、それ以下はプロトコル違反となる。
uint64 salt 短縮トランザクションIDの計算に使用されるsalt。

双方のピアが、sendtxrcnclを送信しサポートを確認した後、P2P接続のイニシエーターが照合のイニシエーターのロールを担い(reqreconメッセージを送信する)、もう一方のピアが照合のレスポンダの役割を担う(reqreconメッセージに応答する)。reqreconメッセージは、照合のイニシエーターによってのみ送信される。

reqrecon

reqreconメッセージは照合ラウンドを開始する。

名称 定義
uint16 set_size セットの差分の推定に使用される、送信者の照合セットのサイズ。
uint16 q セットの差分を推定するために使用される係数。送信者側でPRECISION=(215) - 1を乗算、切り上げし、受信者側でPRECISIONで除算する。

reqreconを受信した受信者は、

  • 特定のcapacity=f(set_size, local_set_size, q)sketchメッセージを構築し送信する(正確な関数は以下で提案)。local_set_sizeは、受信者の照合セットの大きさを表す。
  • 受信者の現在の照合セットのスナップショットを作成し、セット自体はクリアする。スナップショットは、ノードがreconcildiffメッセージを受信するまで保持される。

reconcildiffメッセージが送信されるまで、新しいreqreconメッセージは送信できない。

sketch

sketchメッセージは、セットの照合を実行するために必要なスケッチを通信するために使用される。

名称 定義
byte[] skdata 送信者の照合用のスナップショットのスケッチ

sketchメッセージは、次の2つの場合に受信する:

1. 初期のスケッチ。sketchメッセージを受信すると、ノードは受け取ったスケッチを、対応する照合セットに対してローカルで計算したスケッチを組み合わせることで、差分のスケッチを計算する。受信ノードは、続いて結果の差分のスケッチをデコードする。

  • デコードに失敗した場合、受信ノードはreqsketchextメッセージを送信して、拡張スケッチを要求する。あるいは、ノードは、失敗フラグをセット(success=false)したreconcildiffメッセージを送信して、照合をすぐに終了させることができる。
  • デコードが成功した場合、reconcildiffメッセージにsuccess=trueをセットする。

また、受信者は現在の照合セットのスナップショットを作成し、セット自体はクリアする。スナップショットはreconcildiffメッセージが送信されるまで保持される。これはスケッチの拡張を有効にするために必要である。

2. スケッチの拡張。スケッチの拡張と最初に受信したスケッチを結合することで、拡張されたスケッチが得られる。次に、受信者側のノードは、受信した拡張されたスケッチと対応する照合セットのスナップショットに対してローカルで計算された拡張スケッチと結合することで、拡張差分スケッチを計算する。次に、受信ノードは、その結果の拡張差分スケッチをデコードしようとする。

  • デコードに失敗した場合、受信側のノードは、失敗フラグをセット(success=false)したreconcildiffメッセージを送信して、すぐに照合を終了させる。
  • デコードが成功した場合、reconcildiffメッセージにsuccess=trueをセットする。

いずれの場合も、success=falseのreconcildiffは、フラッディングへのフォールバックとして、照合セット(または拡張後に失敗したセットのスナップショット)から全トランザクションを通知することも伴う必要がある。success=trueのreconcildiffには、デコードされた差分から、送信側で欠落しているトランザクションに対応する未知のトランザクションの短縮IDを含んでなければならない。差分から得られる短縮IDは、メッセージの受信者に不足しているものにも対応しており、これらはinvメッセージによって通知されるべきである。

reqsketchext

reqsketchextメッセージは、最初のセットの照合が失敗し、セットの差分を見つけるのにスケッチの拡張が必要であることを知らせるために、照合のイニシエーターによって使用される。

このメッセージのペイロードは空である。

reqsketchextメッセージを受信すると、ノードはそれにsketchメッセージで対応する。このメッセージには最初に送られた部分を除いたより大きな容量(最初にスケッチされた同じトランザクションの)スケッチの拡張が含まれている。

reconcildiff

reconcildiffメッセージは、送信側で照合中に欠落が見つかったトランザクションを照合のイニシエーターが通知するのに使用される。

名称 定義
uint8 success メッセージの送信者が、セットの差分のデコードに成功したかどうかを示す
uint32[] ask_shortids 送信者が持っていない短縮IDの配列

(照合が成功した)success=1のreconcildiffメッセージを受信したノードは、wtxidを含む32 bitのIDで要求されたトランザクション(依存関係のある親トランザクションを含む)の要求のためにinvメッセージを送信する。(照合が失敗した)success=0の場合、受信者は照合セットのすべてのトランザクションinvメッセージで通知する必要がある。どちらの場合も、メッセージの送信者が受信者に欠落していると思われるトランザクションが、invメッセージを介して通知され、従来のinvの重複の排除が適用される。

対応する照合セットのスナップショットは、その後メッセージの送信者と受信者によりクリアされる。

送信者は、受信者側に欠落しているトランザクションを通知するために、reconcildiffメッセージと一緒にinvメッセージも送信しなければならない。

ローカルステート

このBIPはステートフルなプロトコルを示唆しており、適切に動作するためにすべてのノードにおいていくつかの変数を格納する必要がある。

照合用のsalt

照合のサポートをネゴシエーションする際、ピアは照合セットに使用するのsaltを互いに送信する(上記の短縮IDの構築方法を参照)。これらのsalt(または結果のsaltのみ)は、接続の両側で保持される必要がある。

照合セット

各ノードは、通常のフラッディングプロトコルで送信されたであろうトランザクションを表す、トランザクションの照合をサポートするすべてのピアのためにwtxidのセットを格納する。トランザクションを受信すると、このセットに追加される(ピアによって設定された最低手数料などのポリシーを満たす場合)。照合セットは、最初のスケッチの送信後に、対応するセットのスナップショットに移行する。

照合セットのスナップショット

最初のスケッチを送信後(reconcildiffメッセージの送信または受信のいずれか)、すべてのノードは現在の照合セットのスナップショットを保存し、セットをクリアする必要がある。これはスケッチの拡張をより安定させるために重要である(拡張はセットのスナップショットに対して計算されるべきであるため)。そうでなければ、拡張は最初のスケッチを送信した後に受信したトランザクションを含んでしまうことになる。スナップショットは照合ラウンドの終了後(reconcildiffメッセージの送信または受信)、クリアされる。

スケッチの容量の見積もりと係数q

上記で、照合の要求を受信した際、ノードは送信すべきスケッチの容量を推定することを提案したcapacity=f(set_size, local_set_size, q)

これには次の関数を提案する。

capacity=|set_size - local_set_size| + q * min(set_size, local_set_size) + c

直感的に、qはセットの不一致を表す。セットが近いほど最適なqの値は小さくなる。Erlayのペーパーによると、qは実際のセットのサイズとセットの差分が分かると、ピアとの前回の照合のための最適なqの値として導出されべるべきである。たとえば、前回のラウンドで、set_size=30、local_set_size=20で実際の差分が12にだった場合、ノードは次のようにqを計算する必要がある。

q = (12 - |30-20|) / min(30, 20)=0.1

qの導出は、プロトコルのバージョンに応じて変更することができる。たとえば、簡略化のために静的な値を選択することもできる。ただ、より洗練された(非静的な)パラメーターの選択と将来的に互換性を持たせるためには、qはすべての照合要求で送信されるパラメーターのままであることを提案する。

パラメーターcについては、空のスケッチの送信を避け、過小見積もりによるオーバーヘッドを減らすために、c=1を使用することが提案される。

後方互換

従来のクライアントは、この変更後も完全に互換性があり、相互運用可能である。

このプロトコルを実装していないクライアントは、この変更後も既存のプロトコルを使用して完全な互換性を保つ。なぜならトランザクション通知の照合は、そのサポートをネゴシエートしたピアに対してのみ使用されるためである。

論拠

セットの照合にPinSketchを使用する理由は?

PinSketchは、IBLTよりも帯域幅効率が高く、特に私たちが想定している差分の小さいセットに対して動作する。PinSketchはCPISyncと同程度の帯域幅だが、デコードについてCIPSyncが3次の計算量であるのに対して、PinSketchは2次の計算量になる。このためPinSkechは大幅に高速化される。

32 bitの短縮トランザクションIDを使用するのはなぜ?

実際にMinisketchを使用するには、トランザクションIDを短くする必要がある(理想的には1要素あたり64 bit)。トランザクションあたりのbit数が少なければ、余計な帯域幅を節約し、スケッチに対する演算をより速くすることもできる。私達の試算では、32 bitは(リンク毎に個別のsaltを使用するすることで可能になる)非Adversarial Modelにおいて、低い衝突率を提供する。

Bisectionではなくスケッチの拡張を使用するのはなぜ?

Bisectionは、スケッチの拡張に代わるもので、同じ初期容量を持つ2つめのスケッチがtxID空間の半分で計算される。スケッチの線形特性により、この1つだけを送信することで、照合のイニシエーターは別の半分の同じ容量のスケッチを計算することができる。2つのスケッチにより、イニシエーターは、最初のスケッチで可能な2倍の差分を再構築することができる。

実際には、これによりイニシエーターは、拡張スケッチと同様に、最初の照合失敗の帯域幅のオーバーヘッドを償却し、オーバーヘッドを無視できるようにすることができる。

スケッチの拡張の主なメリットは、実装がシンプルであること。Bisectionの実装は難しい。なぜなら、最終的には2つのスケッチで動作し、1つのスケッチがデコードされ、別のスケッチが失敗するシナリオを処理しなければならないため。

将来、複数の拡張/Bisectionを許可することになると、さらに難しくなる。この場合、Bisectionは再帰的でなければならず(そして、4/8/16...のスケッチを生成)、一方スケッチの拡張では常に1つの拡張スケッチで終えることができる。

スケッチの拡張はまた、より柔軟である。容量10のスケッチを4つ拡張するのは、容量14のスケッチを計算し、拡張を送るだけですむ。一方Bisectionで、容量を102/104/10*8/...と異なるものに増やすのは実装的には高度なものになる。

Bisectionの唯一のメリットは、より大きな容量のスケッチを計算する必要がないことである(指数関数的なコスト)。私たちは、このプロトコルは現在、通常最大でも20の容量を持つ条件で動作するよう設計されているため、この効率は重要ではないと考えている。

実装

https://github.com/bitcoin/bitcoin/pull/21515

lnd v0.15.3-betaで発生した2度目の障害の内容

少し間が空いたけど、

techmedia-think.hatenablog.com

の障害からそんなに間を開けずに、再度LNDでチェーン同期ができなくなる障害が発生したので、その内容をまとめておく。

障害の原因

障害のトリガーとなったは、500,142 byte(125,109 vbyte)のこのトランザクション

トランザクションには1つのインプットと1つのアウトプットがあり、アウトプットは話題に挙がった

you'll run cln. and you'll be happy.

というデータがOP_RETURNで書かれているだけ。

インプットが参照するUTXOは、このUTXO。TaprootのUTXOであることが分かる。

サイズが大きいのはインプットのwitnessデータ(500,042 byte)で、以下のデータで構成されている。

  • 500,000個の空データ
  • 0x50:TapscriptではOP_SUCCESS80として機能
  • c11dae61a4a8f841952be3a511502d4f56e889ffa0685aa0098773ea2d4309f624:Tapscript利用時のControl Blockで、
    • Control Byte:c1
    • Taprootの内部鍵:1dae61a4a8f841952be3a511502d4f56e889ffa0685aa0098773ea2d4309f624
    • マークルパスは空

つまり、呼び出された時点でスクリプトは成功するOP_SUCCESS系のopcode単体のスクリプトを1つもつTapscriptにコインがロックされている。単にコインを使用する(アンロックする)のであれば、↑のwitnessデータの内、0x50とControl Blockの2つの要素のみがあれば良い。今回はその前に500,000個の空データが余計にプッシュされている。インタープリターの処理としては、

  1. まずwitnessデータをスタックプッシュする。
    1. 500,000個の空データをプッシュ
    2. 0x50をスタックにプッシュ
    3. Control Blockのデータをスタックにプッシュ
  2. TaprootのscriptPubkey(OP_1 9bb9efbddf9d70afd3ac2cef011747236bdf90832a78b08f57d1139f07aa9185)を実行
    1. Control Blockをスタックからポップして検証
    2. 0x50を評価した時点で、成功判定(スタックには500,000個の空データが残ったまま)

という処理が実行される。

LNDがライブラリとして使用しているBTCDでは、(DoS対策としているが)witnessデータの最大要素数を500,000個に制限していたため、それを超える↑のトランザクションを不正なトランザクションとして処理してしまったのが今回の障害の原因。

マイナーの協力が必要

前回の障害と違うのは、↑のトランザクションは以下の2つの理由から非標準トランザクションであること。

  • まずトランザクションサイズが125,109 vbyteで、これは標準ルールの制約である100,000 vbyteの上限を超えている。
  • OP_SUCCESS系のopcodeが含まれている。これらのopcodeは、将来のopcodeの拡張のため従来予約されていたOP_NOP系のopcodeの取り回しを改善するために導入されたもの。現状Tapscriptの実行中にこれらのopcodeが登場した場合、非標準として処理される。

非標準トランザクションBitcoin Coreではmempoolへは受け入れられずリレーもされない。それでもコンセンサスルールとしては有効なので、マイナーの協力があればブロックに格納することができる。ブロックに格納されていれば非標準トランザクションでも↑のインタープリターの処理が実行され有効なトランザクションとして判定される。

なので、このトランザクションのマイニングに協力したマイナーがいたということ。トランザクションアウトプットはOP_RETURNのアウトプットのみなので、インプットのビットコイン(0.03682719 BTC)はすべてマイナーの手数料になる。これが報酬?

↑のスクリプト見る限り署名検証の必要はないので、むしろマイナーは500,000個の空データをプッシュ部分削除して、単に0.03682719 BTCだけ頂くということも可能よね。

修正内容

修正内容は、BTCDのwitnessデータの最大要素数のチェックの値を500,000から4,000,000(コンセンサスである最大トランザクションweight)に引き上げるというもの↓

https://github.com/btcsuite/btcd/pull/1907/files

責任ある開示

もともとこのバグ自体は、Anthony Townsによって発見され、LNDとBTCDのリードメンテナである@roasbeefに開示されていた模様。ただ、障害を発生するためには非標準トランザクションをマイニングするマイナーの協力が不可欠であったため、他の変更と一緒に修正することで脆弱性の修正を隠して対応する予定(脆弱性の悪用がされないように)だった模様↓

残念ながら、そのリリース前に悪用されてしまった。

Liquidにも影響

ちなみにこのトランザクションは、BlockstreamのLiquidのWatchmenにも影響し、ペグアウトが一時できなくなった模様。

使用しているrust-bitcoinのバグみたいだけど、rust-bitcoinでは数ヶ月前に修正版はリリースしていたっぽい。

状況的には、全体的にTaprootのコンセンサスについて各ライブラリがテストされてるような感じだなー。

2つの集合の対称差を求めるアルゴリズムを実装したMinisketch

Bitcoinの新しいトランザクションリレープロトコルの提案Erlay↓

techmedia-think.hatenablog.com

のコアとなる実装の1つがMinisketch

Minisketchは、2つの集合の対称差を求めるアルゴリズムPinsketchを実装したライブラリ。つまりAとBという2つの集合があったとして、Aには含まれているがBには含まれていない要素+Bには含まれているけどAには含まれていない要素を帯域幅効率良い方法で算出できるライブラリ。Erlayでは、2つのフルノード間でmempool内のトランザクションの差分を求めるのに、このMinisketchを利用している。

Minisketchの特性

Minisketchは、

  • 要素の集合からスケッチを作成し、
  • 2つのスケッチを組み合わせて、2つの元の集合間の対称差のスケッチを計算する。
  • (スケッチには予め決められた容量があり、集合内の要素の数がこの容量を超えない限り)スケッチから集合の要素を復元することができる。

スケッチは、以下の3つのパラメーターを持つ:

  • 容量(c):スケッチが照合可能な、要素の差異の数。
  • フィールドサイズ(b):スケッチに格納する要素のビット数。集合の要素のサポートされる範囲は {1..2^{b}-1}までの整数。
  • 実装(implementation):実装の指定値で0をデフォルトでサポート。ハードウェアによってより効率的なアルゴリズムを使用できることも。

容量がcで要素がbビットのスケッチは、b✕cビットを格納できる。なお、加算はXORなので、同じ要素をスケッチに2回追加するとスケッチから削除されるので注意。

具体的な利用手順は、アリスとボブがそれぞれ要素の集合を持っていて、その要素の多くが重なっている場合、以下のようになる:

  1. アリスとボブは自身の集合の要素を計算する。
  2. アリスは自分のスケッチをボブに送信する。
  3. ボブは2つのスケッチを組み合わせ、対称的な差分スケッチを入手する。
  4. ボブは差分スケッチから要素を復元する。
  5. ボブは差分の各要素をアリスに送信して、自身の不足要素を要求する。

minisketchのライブラリをFFIでラッパーしたminisketchrbを利用すると↑のプロセスはRubyで以下のように書ける。

require 'minisketch'

b = 12
impl = 0
c = 4

# アリスがスケッチを作成
sketch_a = Minisketch.create(b, impl, c)

# アリスが要素をスケッチに追加
(3000...3010).each do |i|
  sketch_a.add(i)
end

# アリスはスケッチをシリアライズ
serialized_a = sketch_a.serialize

# ボブがスケッチを作成して要素を追加
sketch_b = Minisketch.create(b, impl, c)
(3002...3012).each do |i|
  sketch_b.add(i)
end

# ボブはアリスから受け取ったデータからアリスのスケッチを復元
sketch_ba = Minisketch.create(b, impl, c)
sketch_ba.deserialize(serialized_a)

# ボブは両者のスケッチをマージ
sketch_b.merge(sketch_ba)

# 差分の要素を復元
_, difference = sketch_b.decode(c)
puts difference # 3000, 3001, 3010, 3011が出力される

Minisketchのアルゴリズム

続いて、Minisketchがどうやって↑を実現しているのか、アルゴリズムをちょっと見とく。

フィールド要素への変換とべき級数の集合

まず集合の各要素は {1..2^{b} - 1}の範囲の整数(bはスケッチのフィールドサイズ)である。この各要素は、スケッチに追加する際に有限体 {GF(2^{b})}のフィールドにマッピングされる。(b=32の場合)有限体の要素は {x^{32} + x^{7} + x^{3} + x^{2} + 1}を法とするGF(2b)上のxの多項式として表され、整数の各ビットi(値 {2^{i}})を多項式表現における {x^{i}}の係数として扱う。たとえば、整数 {101 = 2^{6} + 2^{5} + 2^{2} + 1}は、フィールド要素 {x^{6} + x^{5} + x^{2} + 1}マッピングされる。このため、整数と有限体の要素はそれぞれ加算と乗算をサポートする。

続いて、要素(mとする)を以下の形式のべき級数マッピングする関数をSとする。

 {S(m) = 1 + mx + m^{2}x^{2} + m^{3}x^{3} + ...}

※ 無限に続いていくけど、任意の値xに対して実際にこの式を評価することはないので、収束は気にしなくていいみたい。

単一の要素に対する↑を集合 {M = m_1, m_2, ...}に拡張する。

 {S(M) = S(m_1) + S(m_2) + ... = (1 + 1 + ...) + (m_1 + m_2 + ...)x + (m_1^{2} + m_2^{2})x^{2} + ...}

また、同じ要素の加算はXORとなるため、m + m = 0となり、これをSにも適用すると、以下のような計算が成立するようにする。

 {S(m_1, m_2) + S(m_2, m_3) = S(m_1) + S(m_2 + m_2) + S(m_3) = S(m_1, m_3)}

要素の復元

ポイントは、このようなべき級数から集合内の要素を復元する方法。

↑から単一の要素のべき級数S(m)は等比級数であることから、 {(1 - mx)^{-1}}に収束し、

 {(1 - mx)S(m) = 1}

が成立し、さらに複数の要素に拡張していく。たとえば要素が2つの場合は、

 {(1 - m_1x)(1 - m_2x)S(m_1, m_2) = (1 - m_1x)(1 - m_2x)(S(m_1) + S(m_2)) = (1 - m_2x) + (1 - m_1x)}

3つの場合は、

 {(1 - m_1x)(1 - m_2x)(1 - m_3x)S(m_1, m_2, m_3) = (1 - m_1x)(1 - m_2x)(1 - m_3x)(S(m_1) + S(m_2) + S(m_3)) = (1 - m_2x)(1 - m_3x) + (1 - m_1x)(1 - m_3x) + (1 - m_1x)(1 - m_2x)}

と、任意の要素 {m_i \in M}について {1 - m_ix}をS(M)に乗算するとn-1次の多項式になる。

このことから、P = S(M)Lがn-1次の多項式になるような、いろんな {m_i}のn個の異なる {(1 - m_ix)}係数の積である多項式Lを見つけることができたら、それらの値 {m_i}がMの要素として復元できるということらしい。

多項式S(M)の係数を {s_i}多項式Lの係数を {l_i}として {S(M) = s_0 + s_1x + s_2x^{2} + s_3x^{3} + ...}および {L = l_0 + l_1x + l_2x^{2} + l_3x^{3} + ...} {l_0 = 1})とした場合、上記が成立するためには、次数n以上の多項式Pの係数はすべて0になることから、

次数n+1から2nまでのS(M)の係数について、以下が成立する。

  • {s_{n+1} + s_{n+0}l_1 + s_{n-1}l_2 + s_{n-2}l_3 + ... + s_1l_n = 0}
  •  {s_{n+2} + s_{n+1}l_1 + s_{n+0}l_2 + s_{n-1}l_3 + ... + s_2l_n = 0}
  •  {s_{n+3} + s_{n+2}l_1 + s_{n+1}l_2 + s_{n+0}l_3 + ... + s_3l_n = 0}
  • ...
  •  {s_{2n} + s_{2n-1}l_1 + s_{2n-2}l_2 + s_{2n-3}l_3 + ... + s_nl_n = 0}

このn個の未知の数を持つn個の連立方程式ガウスの消去法で解くと、多項式Lの係数が得られるので、その式を {(1 - m_ix)}形式に因数分解することで、m個の要素が復元できるということらしい。

上記の基本形に対して、さらに

  • 明示的に要素数nが分かっていない場合(上限値としてnが定まる場合)のサポートや、
  • スケッチのサイズを半分にする最適化
  • 因数分解の代わりに根の探索アルゴリズムの使用
  • 逆数の演算の回避

など様々な最適化が行われてる模様。

Taroのオンチェーンアドレス仕様

techmedia-think.hatenablog.com

↑のアセットの新規発行に続いて、アセットを送付しようと思ったけど、その前にアセットを受け取る際に必要になるTaroのオンチェーンアドレス仕様について見ておく。

Taroアドレス

Taroのアセットを受け取る際のアドレスは既存のBitcoinアドレスではなく、その仕様は↓のBIPドラフトに定義されている。

https://github.com/Roasbeef/bips/blob/bip-taro/bip-taro-addr.mediawiki

アドレスはエンコード仕様にTaprootと同じbech32mを採用しており、bech32mのhuman-readable parts(HRP)は

  • mainnetがtarobc
  • testnet/signettarotb
  • regtestがtarort

で(BIPドラフトではtarotarotと記載されてるけど、tarodのα版では↑のように定義されてる)、データ部は、以下のTLVデータで構成される。

タイプ 定義
0 taro_version Taroのバージョン。現在は0。
2 asset_id 受け取るアセットのアセットID。※ ただα版の実装ではIDではなくアセットジェネシスになってる。
3 asset_key_family アセットファミリーキー。異なるアセットIDのアセットを関連付けるために使用する鍵。ノーマルタイプのアセットを追加発行する際に、発行済のアセットと追加発行したアセットでIDが異なるので、それを紐付けるために利用。
4 asset_script_key アセットを受け取る公開鍵
6 internal_key アセットを受け取るトランザクションアウトプット(Taprootアウトプット)で使用するTaprootの内部鍵(公開鍵)
8 amt 受け取るアセットの量
9 asset_type アセットタイプ(省略時は0=ノーマル)Type:2がジェネシスになるのであれば必要ないので無くなるものと思われる。

タイプが厳密に連番じゃないのは、ライトニングの機能ビットと同様で、奇数値のフィールドはオプションであることを示すため(↑ではasset_key_familyasset_typeがオプション)。1と5使ってないのは何でだろう?

アセットの受信者は、受け取りたいアセットの情報と、受け取りに使用する鍵(asset_script_keyinternal_key)から↑のTaroアドレスを生成する。

tarocliでアドレスを生成

tarocliaddrs newコマンドを使用すればTaroアドレスが生成される。前回1,000発行したアセットを500ほど受け取るアドレスの生成は↓

$ tarocli addrs new --amt 500 --genesis_bootstrap_info a92eb9e8d42437b8879ff571903fcbb74b55fc558c3cbc80ba8ca293bcd82eaf000000010874657374636f696e116d6574616461746120666f7220746573740000000000
{
    "encoded": "tarotb1qqqsqqjy4yhtn6x5ysmm3pul74ceq07tka94tlz43s7teq963j3f80xc96hsqqqqqyy8getnw33k76twz9kk2arpv3shgcfqvehhygr5v4ehgqqqqqqqqppq5746x7psp9fvl0mhs6f80zcnpzlch5v97xh46j6459sy80supf9svgzkf72uhhmf2a2ma8s8glra7dqagk96n47fda64q6dkmu32xjfw7syq8lgp7syf8tft",
    "asset_id": "9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061ca",
    "asset_type": "NORMAL",
    "amount": "500",
    "family_key": null,
    "script_key": "02a7aba378300952cfbf778692778b1308bf8bd185f1af5d4b55a16043be1c0a4b",
    "internal_key": "02564f95cbdf695755be9e0747c7df341d458ba9d7c96f755069b6df22a3492ef4",
    "taproot_output_key": "37fc965befde457f4c7943750d83a5743a565fb12eaf7c01c3084fe8b106f533"
} 

アセットの情報はgenesis_bootstrap_infoで指定する。このデータは、アセット発行の際に使用したアセットジェネシスのデータ(アセットIDを算出する際のデータ)になる。tarocliではassets listコマンドの出力結果にも含まれている。

受信者は↑のbech32mアドレスを送信者に送り、送信者はそのアドレスから送金先のTaroアウトプットを作成することになる。

taproot_output_keyは、500個分のアセット9333d8360be674dfae320b7ae16bd3b618726637fad107a1d2b248a3083061caをリーフノードとして空のMS-SMTツリーに挿入してTaroのアセットツリーを構成し、それとinternal_keyをTaprootの内部鍵として利用して計算したTaprootのwitness programになる。そのため、実際に受信者が受け取るTx内のアウトプットのscriptPubkeyは、

OP_1 <37fc965befde457f4c7943750d83a5743a565fb12eaf7c01c3084fe8b106f533>

となり、P2TRアドレスに変換すると、

tb1pxl7fvkl0mezh7nregd6smqa9wsa9vha396hhcqwrpp873vgx75es923e09

となる。

tarocliで↑のアドレスを作成した段階で、連携先のlndのウォレットにこのアドレスがインポートされていることが確認できた。

単純に、↑のP2TRアドレスをTaroアドレスとしないのは、どういったツリーが構成されるか送信者も検証する必要があるからかな。