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では接続の小さなサブセットでの高速リレーを促進するために、必要な場合にのみフラッディングを使用する。

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

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

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

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

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のネゴシエーションとサポートが有効になるはず。

スケッチの拡張

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

新しいメッセージ

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

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

sendtxrcncl

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

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

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

sendtxrcnclがverackの前に送信されたが、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=(2¹⁵) - 1を乗算、切り上げし、受信者側でPRECISIONで除算する。

reqreconを受信した受信者は、

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

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

sketch

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

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

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

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

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

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

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

デコードに失敗した場合、受信側のノードは、失敗フラグをセット（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

Develop with pleasure!

福岡でCloudとかBlockchainとか。