ブラインドMuSig2

MuSig2は、n-of-nのマルチシグを暗号技術のみで構成するSchnorrベースのスクリプトレスなマルチシグスキーム↓

techmedia-think.hatenablog.com

そのブラインド版がブラインドMuSig2↓

https://github.com/halseth/ephemeral-signing-service/blob/main/doc/general.md

MuSig2の場合、通常署名者は

• 何のメッセージに署名しているのか
• 他の署名者の情報（公開鍵）

について知ることができる。ブラインド版は、これらの情報を秘密にしたまま有効なSchnorr署名を構成できるようにしたもの。

署名者であれば一般的には署名内容を把握した上で署名すべきだけど、こういったブラインド署名は、

• 一定数の署名をプライバシーを保ちながらアウトソースしたい場合
• エフェメラル署名サービスを利用したVault

などのケースにおいて有用な可能性がある。

ブラインドMuSig2

署名者が2人（アリスとボブ）いて、2-of-2のマルチシグを構成する場合、参加者の公開鍵を以下とする（小文字が秘密鍵）。

• 
• 

ブラインド版では、署名者が署名内容について知らずに署名をできるようにするためコーディネーターという役割を導入する。このコーディネーターは、署名対象のメッセージ（m）や、参加者、ブラインド係数などの情報を把握するが、署名者の協力がないと（＝署名者の秘密鍵がないと）有効な署名を生成することはできない。

まずコーディネーターは、集約公開鍵を導出する。

ランダムなsalt値rを選択して以下の鍵係数を計算する（saltを使う理由は、署名者が候補となる公開鍵を総当たりで試して、誰と一緒に署名セッションに参加しているかを確認できないようにするため）。

• 
• 
• 

続いて、鍵係数を使って集約公開鍵を計算する。この集約公開鍵の計算自体は、通常のMuSig2と同じ計算。ただブラインド版では各署名者は互いの公開鍵を知らないため、コーディネーターのみが導出できる。各署名者は集約公開鍵を知らないため、オンチェーンにX'が登場しても自分が関与したトランザクションであることが認識できない。

続いて署名の生成。署名者のアリスとボブは、署名に使用する2つの公開ナンスを計算する：

• と
• と

コーディネーターは各署名者から受け取った公開ナンスを使って集約ナンスを計算する。

• 
• 

続いて、ナンスの係数を計算し、集約ナンスをとする。

公開ナンスの生成から集約ナンスの計算は、通常のMuSig2と同様。ただ署名に使われる最終的なナンスはブラインド値を加味した以下のR'になる。

続いて、ブラインド値を選択し、以下の署名ナンスを計算する：

続いて署名対象のメッセージmを使ってを計算する。

続いて、メッセージをブラインドするために各署名者に対して以下を行う（βはチャレンジeをブラインドし、γはブラインダーbをブラインドする）。

• アリスに対して
  • とを計算し、を送る。
• ボブに対して
  • とを計算し、を送る。

このように、各署名者は署名するメッセージについて何も知らない。

各署名者は、以下のようにブラインド部分署名を計算する。

• アリスの場合
  • 
• ボブの場合
  • 

各署名者からブラインド部分署名を受け取ったコーディネーターは、R'に対応させるため以下の加算を行う。

• 
• 

続いて、部分署名を合算して集約署名を計算する。

結果の（R', s）がメッセージmおよび集約公開鍵X'に対して有効なSchnorr署名となる。

この署名は以下の署名検証のチェックを満たす。

検証式から分かるように、ブラインド値はすべて署名ナンスR'で回収される。

ブラインド値のについては、おそらくオンチェーン上のTxを監視してそれらの署名値などと組み合わせて事後分析などできないようにするためのブラインド値と思われるけど、いずれもコーディネーター側でしか計算には使わないので1つあれば十分な気がする。

課題と信頼モデル

MuSig2の設計上の重要な点は、鍵係数（l）とブラインド値（b）の選択。通常のMuSig2の場合、すべての署名者が係数が適切に構成されていることを検証できるけど、ブラインド版ではこれらの値がブラインド化されているため署名者の検証が不可能になる。そのため上記のブラインドモデルはコーディネーターを信頼するモデルとなる。

コーディネーターに悪意がある場合、署名すべきではないメッセージに署名させたり、それにより鍵情報が漏洩する可能性もある。

Bitcoinの2106年のブロックタイムスタンプオーバーフローに対処するBitBlend提案

Bitcoinのブロックヘッダーのタイムスタンプフィールドは、32bitの符号なし整数となっており、その最大値が指す時刻は2106年2月7日6時28分15秒。

Bitcoinでは、新しくマイニングされたブロックのタイムスタンプには、過去11ブロックのタイムスタンプの中央値よりも大きな時刻を設定しなければならないというコンセンサスルールがある。そのため、2106年の最大値に達するとそれ以降新しいブロックがマイニングできなくなる。

そのため随分先ではあるものの、いずれはこの問題に対処する必要があり、その対処方法として提案されている手法の1つが2024年1月に提案されたBitBlend↓

BitBlend

https://bitblend2106.github.io/bitcoin/BitBlend2106.pdf

BitBlendでは32bitの時刻フィールドを再解釈することで、この問題を解決する。現状この時刻はUNIX時間なので1970年からの経過秒数になってる。これを完全なタイムスタンプの下位32bitとして解釈する。

このタイムスタンプの新しい解釈では、

1. 32bitの値にゼロパディングをし64bit変数とし
2. 1を直近11ブロックの中央値（MTP = Median Time Past）と比較し、
3. 1の時刻がMTPの半分未満である場合、32bit制限によるオーバーフローが発生したと想定されるため、このオーバーフローを補正するために、
   • MTPの上位32bitと新しい時刻の下位32bitをブレンドし、
   • ブレンドした結果にを加算する。

このルールを適用により、過去からの時刻の連続性を維持したまま、タイムスタップを64bit空間に拡張することができる。2106年のオーバーフローだけでなく、136年ごとに発生する将来の各32bitのオーバーフローも補正できる。

具体例で見ると、

2106年のタイムスタンプのMTPが4,294,967,000（0xfffffed8）で、その次のブロックのタイムスタンプの値が1,000（0x03e8）だった場合、タイムスタンプ値が4,294,967,000 / 2よりも小さいため、オーバーフローが発生したと判断され、64bit値のMTPの上位32bitの値を使って（この時点では0）以下のブレンドを実行し、

(0 << 32) | 1000 = 1000

を加算した値を64bitのタイムスタンプ値として評価する。

2242年ごろに2回めのオーバーフローが発生する際は、MTPを8,589,000,000（0x01fff1bd40）で、その次のブロックのタイムスタンプの値が2,000（0x07d0）だった場合、再度オーバーフローが発生したと判断され、64bit値のMTPの上位32bitの値を使って（この時点では1）以下のブレンドが実行される

(1 << 32) | 2,000 = 4,294,969,296

この値にを加算した値を64bitのタイムスタンプ値として評価する。

上記のように、ノードの内部ではブロックのタイムスタンプの処理は64bit表現で行うようにすることで、ノード間のもろもろのP2P通信は既存の32bitのまま行いながら、2106年以降もブロックのマイニングが可能になる。

タイムロックへの影響

Bitcoinには、

• トランザクションのnLocktimeフィールドを用いる絶対時間ベースのCLTV（OP_CHECKLOCKTIMEVERIFY）と、
• トランザクションインプットのnSequenceを用いる相対時間ベースのCSV（OP_CHECKSEQUENCEVERIFY）

の2種類のタイムロックのスキームがある。

両者ともブロック高を用いたタイムロック設定においては、32bitのタイムスタンプのオーバーフローの影響は受けない。

CLTVのタイムスタンプについては、2106年で自然に期限切れになる。トランザクションのnLocktimeには32bit値以上を指定できないので、そのまま機能停止して64bitに拡張しないことを↑のペーパーでは提案している。ブロック高で指定する代替手段があるので機能的な問題はないと思われる。

CSVのタイムスタンプについては、上記のBitBlendの仕組みにより2106年以降もこれまでと同様に動作する。CSVのチェックには2つのチェックがある、

まず、

UTXOが参照するトランザクションのブロックの時刻＋相対的なオフセット≦ 現在のブロックの時刻

これはスクリプトインタプリタの外部で行われるチェック。

もう1つは、インタプリタで行われる以下のチェック

スクリプト内で指定されたCSVの値 ≦ nSequenceフィールドの値

実際の時刻のチェックは、前者で行われ、そのブロック時刻はBitBlendにより64bitで行われる。内部の時刻が64bitになるだけで現状と同じ動作になる。

というのがBitBlendの提案。既存のインタプリタやP2Pメッセージへの影響を最小限にしながら、オーバーフローに対処する提案になってる。

NTTを必要としない既存のNIST曲線を用いたゼロ知識証明

昨年Googleが公開したECDSAを利用した匿名認証のペーパーで↓、P-256などの既存のNIST曲線で動作するゼロ知識証明の仕組みが面白そうだったので読んでみた

eprint.iacr.org

VCと匿名性とリンク不能性

ここ数年、VC（Verifiable Credential）の活用の提案が活発だけど、ユースケースによっては、発行者が認めたClaimをすべて開示する必要はなく、すべて開示されることによるプライバシー上の問題も発生する。そこで、クレデンシャルに記載されている自身の情報を必要な部分だけ開示したり（選択的開示）することができる。

たとえば、運転免許証のMDOCドキュメントにはユーザーの個人情報や属性情報のハッシュが格納される。例えば18歳以上であることのデータであれば、

{
  "valueDigests": {
    "org.iso.18013.5.1": {
      14: "8CFE...604C",  // 年齢18歳超の属性のハッシュ値
      ...
    }
  }
}

で、そのハッシュ値は以下のデータから作られる↓

"digestID": 14,
"random": "8c082af3d5d78b98bcc00bd26fae5130",  // ランダムな値（ナンス）
"elementIdentifier": "age_over_18",            // 属性の識別子
"elementValue": true                           // 属性の値

自分が18歳以上であることを証明したい場合、ハッシュの元となった上記のデータを開示することで証明することができる。

ただ、異なる機関に対して同じ認証情報が提供され、それが相互に関連付けられるとそれが同一人物によるものであることがリンクできてしまう。

冒頭の論文は、ハッシュの元のデータを公開することなくゼロ知識証明でそれが正しいことを証明することで、このリンク問題を解消する提案。

BBS+などで実現するアプローチは既にあるが、その場合BBS+をサポートするようにデバイスやセキュアエレメントの更新が必要になり、コスト面やNISTで標準化されていないスキームという点で現実的なハードルがある。この論文のスキームはECDSAベースなので、既に展開されているデバイスやセキュアエレメントを使用できるというメリットがある（たとえば、マイナンバーカードは2026年の更新で、デジタル署名アルゴリズムがRSAからECDSAに切り替わる予定とされている）。

ゼロ知識証明アプローチ

18歳以上であることをゼロ知識証明システムで証明する場合、

• 免許証の発行者の公開鍵
• 証明したい属性のフィールド名（age_over_18）
• 期待するフィールドの値（true）
• セッショントランスクリプト

を公開入力（つまり検証者が確認可能な情報）とし、

• MDOC全体
• デバイスの秘密鍵で署名されたデバイス署名

を秘密の入力（証明者のみが知る情報＝witness）として、「age_over_18 = trueを含む有効なMDOCを持っている」ことを証明する算術回路を構築する。

証明者は秘密の情報からプルーフを生成し、検証者は回路と公開入力およびプルーフを使って検証する。回路を使って検証される内容は↓

1. 発行者の公開鍵に対してMSOの有効な署名があること
2. 属性のハッシュ値の検証
3. 属性値（true）の検証
4. デバイスの公開鍵を用いたデバイスの認証（署名検証）
5. 有効期限の検証

この算術回路は以下の3つのサブ回路を組み合わせたものになる：

• ECDSAの署名検証回路
• SHA-256回路：SHA-256のラウンド関数を回路化
• CBOR*1パース回路

この中で、特にネックになるのがECDSAの署名検証回路になる。

ECDSAとゼロ知識証明

多くのゼロ知識証明システムでは、計算の正しさを効率的に検証するため多項式を利用している。Groth16やPlonkなどの主要なゼロ知識証明システムは、

• 多項式の乗算：制約の検証、商多項式の計算
• 多項式の評価：コミットメントの計算、検証点での評価
• 多項式の補間：witnessから多項式の構築

などの計算を効率的に行うためにNTTを利用している↓

techmedia-think.hatenablog.com

ただ、↑の記事の最後でも触れたように、NTTを利用するためには適切な有限体（適切な原始根を持つ有限体）を持つ楕円曲線を選択する必要がある。

一方、現在チップなど含め広く採用されている楕円曲線はP-256曲線が主流で、このP-256曲線はNTTに適した有限体ではない（高次の原始根が存在しない）。P-256を用いたゼロ知識証明を行うには、演算を別の体でエミュレートする必要があり、回路が巨大化し、とても非効率なものになってしまう。

P-256に限らずECDSA用にNISTが定義している曲線はいずれもNTTに適していない。これは当時このようなゼロ知識証明用の要件がなかったから。後に設計されたSNARKフレンドリーな曲線BN255やBLS12-381、Pasta (Pallas/Vesta)などは、NTTと親和性があるよう意図的に設計されたもの。

Ligero + Sumcheckアプローチ

論文ではNTTに代わって、LigeroとSumcheckという2つの仕組みを利用している。

Ligeroを簡単に説明すると、証明者は実行トレースをリード・ソロモン符号でエンコードし、その結果をマークルツリーでコミットする。 検証者は、ランダムに選択した位置の評価値を要求して、それが正しくエンコードされていること、そして制約を満たしていることを確認するというスキーム。詳細は↓

techmedia-think.hatenablog.com

Ligeroでも多項式の評価を高速化するためにNTTを利用することは可能だけど、NTTがなくてもLigeroの場合、やや遅いものの愚直に多項式の評価ができる。これはLigeroが評価点に対して、ペアリングを必要としたり、プロトコルが評価点の乗法群に依存するなど、既存の証明システムで求められるような特定の構造を要求しないため。

Sumcheckプロトコルは多変数多項式の総和を効率的に検証するためのプロトコル↓

techmedia-think.hatenablog.com

Ligeroは回路全体の実行トレース（回路の各ゲートの入出力をすべて記録したデータに対するコミットメント）を作成するため、例えばSHA-256を1ブロック検証する場合、このコミットメントは約13万要素になる。コミットメントの作成にはリード・ソロモン符号によるエンコードが必要で、これがボトルネックになる。

そのため、回路の検証はSumcheckで行うようになっており、回路内のすべてのゲートを個別にチェックするのではなく全ゲートの計算結果の総和をチェックする。

1. 署名検証を算術回路（quad form表現）に変換し、
2. その回路をd個の層に分割し、
3. 各層についてその値が次の層の値から正しく計算されているかをSumcheckで検証し、
4. 最後に1点だけ自分で検証する（↑の記事内のを選択した評価）

（回路の層毎の分割や具体的な多項式の展開とかまだよく分かってない）

SumcheckはNTT自体の代替ではなく、NTTの対象を小さくするための圧縮技術（回路の検証を対数サイズのトランスクリプトに圧縮する）という位置づけ。

Sumcheck自体はゼロ知識証明プロトコルではないため、Sumcheckでの対話記録をトランスクリプトとしてワンタイムパッドで暗号化する。そしてLigeroは元のwitnessと暗号化用のパディング、暗号化されたトランスクリプトにコミットする。

また単にSumcheckとLigeroを導入しただけでなく、P-256の有限体用に最適化されたリード・ソロモン符号やECDSAの検証に特化した回路設計、楕円曲線演算の効率的な回路化などの最適化が行われている模様。※ちなみに、厳密にNTTを使っていない訳ではなく、最適化で二次拡大体上で一部NTTによる高速化は使用してるみたい。

また最後に、ECDSAとSHA-256の回路は異なる体で動作するため、各回路の入力整合性をMAC（メッセージ認証コード）で検証する手法が提案されている。

ベンチマークでは、

• ECDSA署名検証のゼロ知識証明は、Pixel 6 Proで約80msで生成
• MDOC全体の匿名認証（署名検証、ハッシュ検証、CBORパースを含む）は、最大2231バイトのMSOに対して約1.2秒で証明を生成

という実用的なパフォーマンスが報告されている。

以上が論文のざっくりとした内容。

*1:Concise Binary Object Representation、JSONに似た構造を持つバイナリフォーマットでMDOCのエンコードに使われている

数論変換（NTT）

最近の主要なゼロ知識証明システムで、多数の多項式の演算が必要になる。多項式の加算であれば、単に同じ次数の係数同士を加算するだけなので、必要な演算回数は係数の個数分。n-1次の多項式であればO(n)の加算で済む。一方、多項式の乗算の場合、その結果の次数が同じ項をまとめる必要があり、単純に計算するとO(n²)の乗算と同程度の加算が必要になる。

たとえば、2つの3次多項式を

• 
• 

とした場合、その積は、

となる。

畳み込み演算

2つの多項式の積の各係数は、各多項式の係数列の畳み込みで求めることができる。具体的には、f(x)のk次の係数は、

で計算できる（が存在しない場合は0とみなす）。

たとえば、上記の2つの多項式の係数列は、低次数項順に並べ替えると、

• 
• 

で、各係数は、

• 
• 
• 
• 
• 
• 
• 

n-1次の多項式の場合、この単純な畳込み演算の計算量はO(n²)。

離散フーリエ変換

上記のような畳み込み演算のように多項式の各係数を直接使って計算する以外に、任意のx値に対して評価値を計算しその積を使って計算する方法もある。単純な方法だと、n-1次の多項式の場合、n個の任意のx値を選択し、を求めてラグランジュ補間を使ってf(x)を求めるとか。

演算を高速にする方法の1つが、高速フーリエ変換（FFT）を用いる方法。FFTは離散フーリエ変換（DFT）を効率的に計算するアルゴリズムで、DFTを用いた方式では、評価点として1のn乗根（iは虚数単位）という特殊な複素数のべき乗を使用する。

1. p(x)についてDFTにより評価値を導出（）
2. q(x)についてDFTにより評価値を導出（）
3. 点ごとに評価値を乗算（）
4. 逆DFTでf(x)の係数を算出（）

Rubyでコードを書くと↓

# DFT（単純な O(n²) 版）
def dft(coeffs)
  n = coeffs.size
  # e^(2πi/n) = cos(2π/n) + i*sin(2π/n)
  angle = 2 * Math::PI / n

  (0...n).map do |k|
    (0...n).sum do |j|
      theta = angle * j * k
      coeffs[j] * Complex(Math.cos(theta), Math.sin(theta))
    end
  end
end

# 逆DFT
def idft(values)
  n = values.size
  angle = -2 * Math::PI / n

  (0...n).map do |j|
    (0...n).sum do |k|
      theta = angle * j * k
      values[k] * Complex(Math.cos(theta), Math.sin(theta))
    end / n
  end
end

# DFTを使った多項式乗算
def poly_multiply_dft(p, q)
  # 積の次数に合わせてサイズを決定（2のべき乗にパディング）
  result_size = p.size + q.size - 1
  n = 1
  n *= 2 while n < result_size

  # ゼロパディング
  p_padded = p + [0] * (n - p.size)
  q_padded = q + [0] * (n - q.size)

  # Step 1, 2: DFTで点値表現に変換
  p_dft = dft(p_padded)
  q_dft = dft(q_padded)

  # Step 3: 点ごとに乗算
  r_dft = p_dft.zip(q_dft).map { |a, b| a * b }

  # Step 4: 逆DFTで係数表現に戻す
  r = idft(r_dft)

  # 実部を取り出して丸める（浮動小数点誤差の除去）
  r.map { |c| c.real.round }
end

# 実行
p_coeffs = [5, 1, 3, 2]  # p(x) = 5 + x + 3x² + 2x³
q_coeffs = [1, 2, 4, 1]  # q(x) = 1 + 2x + 4x² + x³

puts "p(x)の係数: #{p_coeffs}"
puts "q(x)の係数: #{q_coeffs}"
puts "DFTベース:   #{poly_multiply_dft(p_coeffs, q_coeffs)}"

高速フーリエ変換

上記のDFTベースだと計算量はO(n²)で、畳み込みと変わらないけど、FFTの分割統治法アプローチで高速化できる。具体的には、係数を偶数番目と奇数番目に分けて半分のサイズのDFTに分解し、それを再帰的に繰り返し、2つの小さなDFTの結果を組み合わせて最終的にサイズnのDFTの結果を得る（この結合処理をバタフライ演算と呼ぶ）。結果、計算量はO(n log n)になる。

Rubyで書くと↓

# FFT版
def fft(coeffs)
  n = coeffs.size
  return coeffs if n == 1

  # 偶数インデックスと奇数インデックスに分割
  even = (0...n).step(2).map { |i| coeffs[i] }
  odd  = (1...n).step(2).map { |i| coeffs[i] }

  # 再帰的にFFT
  e = fft(even)
  o = fft(odd)

  # バタフライ演算で結合
  angle = 2 * Math::PI / n
  result = Array.new(n)

  (0...n/2).each do |k|
    omega_k = Complex(Math.cos(angle * k), Math.sin(angle * k))
    t = omega_k * o[k]
    result[k]       = e[k] + t
    result[k + n/2] = e[k] - t
  end

  result
end

# 逆FFT
def ifft(values)
  n = values.size
  return values if n == 1

  even = (0...n).step(2).map { |i| values[i] }
  odd  = (1...n).step(2).map { |i| values[i] }

  e = ifft(even)
  o = ifft(odd)

  # 逆FFTはωの指数が負
  angle = -2 * Math::PI / n
  result = Array.new(n)

  (0...n/2).each do |k|
    omega_k = Complex(Math.cos(angle * k), Math.sin(angle * k))
    t = omega_k * o[k]
    result[k]       = e[k] + t
    result[k + n/2] = e[k] - t
  end

  result
end

# FFTを使った多項式乗算
def poly_multiply_fft(p, q)
  result_size = p.size + q.size - 1
  n = 1
  n *= 2 while n < result_size

  p_padded = p + [0] * (n - p.size)
  q_padded = q + [0] * (n - q.size)

  p_fft = fft(p_padded)
  q_fft = fft(q_padded)

  r_fft = p_fft.zip(q_fft).map { |a, b| a * b }

  r = ifft(r_fft)

  # 逆FFTでは最後にnで割る
  r.map { |c| (c.real / n).round }
end

# 実行
p_coeffs = [5, 1, 3, 2]
q_coeffs = [1, 2, 4, 1]

puts "p(x)の係数: #{p_coeffs}"
puts "q(x)の係数: #{q_coeffs}"
puts "FFTベース:  #{poly_multiply_fft(p_coeffs, q_coeffs)}"

数論変換

ただFFTは複素数の浮動小数点演算を行うため丸め誤差が発生する可能性があり、ゼロ知識証明システムでは有限体上での正確な演算が必要になるため、この誤差が問題になる。

そこで、複素数の1のn乗根を有限体上の原始n乗根に置き換えたのが数論変換（NTT=Number Theoretic Transform）。素数pに対して、p - 1がnで割り切れる場合、有限体に、以下を満たす位数nの元が存在する。

• 
• （1 ≤ k < nに対して）

この原始根を使うことで、FFTと同じアルゴリズムが有限体上で動作する。つまり計算量O(n log n)で有限体上の多項式の乗算が誤差なく行える。

NTTを利用する上で重要なのがpの選択に伴う位数nのサイズ。このサイズにより、扱える多項式の係数の数が制限される。

p - 1 = 2^k × m（mは奇数）とした場合、上では、最大2^k個までの次数を持つ積多項式の計算が可能になる。そのため、主要なゼロ知識証明システムではNTTに適した素数の有限体を選ぶのが重要になっている。Bitcoinが使っているsecp256k1とかはこの数が少ないので不向きな有限体になる。

NTTを使った計算をRubyで書くと↓

# NTT用の定数
# p = 998244353 = 119 × 2^23 + 1 はNTT-friendlyな素数
# 原始根 g = 3
MOD = 998244353
PRIMITIVE_ROOT = 3

# モジュラ逆元
def mod_inverse(a, mod = MOD)
  mod_pow(a, mod - 2, mod)
end

# モジュラべき乗
def mod_pow(base, exp, mod = MOD)
  result = 1
  base %= mod
  while exp > 0
    result = result * base % mod if exp.odd?
    exp >>= 1
    base = base * base % mod
  end
  result
end

# NTT（FFTと同じ構造、複素数→有限体に置き換え）
def ntt(coeffs, inverse: false)
  n = coeffs.size
  return coeffs if n == 1

  # 偶数インデックスと奇数インデックスに分割
  even = (0...n).step(2).map { |i| coeffs[i] }
  odd  = (1...n).step(2).map { |i| coeffs[i] }

  # 再帰的にNTT
  e = ntt(even, inverse: inverse)
  o = ntt(odd, inverse: inverse)

  # 原始n乗根を計算
  # ω = g^((p-1)/n) mod p
  # 逆変換の場合は ω^(-1) を使う
  if inverse
    omega = mod_pow(PRIMITIVE_ROOT, (MOD - 1) - (MOD - 1) / n)
  else
    omega = mod_pow(PRIMITIVE_ROOT, (MOD - 1) / n)
  end

  # バタフライ演算
  result = Array.new(n)
  omega_k = 1

  (0...n/2).each do |k|
    t = omega_k * o[k] % MOD
    result[k]       = (e[k] + t) % MOD
    result[k + n/2] = (e[k] - t + MOD) % MOD 
    omega_k = omega_k * omega % MOD
  end

  result
end

# 逆NTT
def intt(values)
  n = values.size
  result = ntt(values, inverse: true)

  # 最後にnの逆元を掛ける
  n_inv = mod_inverse(n)
  result.map { |x| x * n_inv % MOD }
end

# NTTを使った多項式乗算
def poly_multiply_ntt(p, q)
  result_size = p.size + q.size - 1
  n = 1
  n *= 2 while n < result_size

  p_padded = p + [0] * (n - p.size)
  q_padded = q + [0] * (n - q.size)

  p_ntt = ntt(p_padded)
  q_ntt = ntt(q_padded)

  r_ntt = p_ntt.zip(q_ntt).map { |a, b| a * b % MOD }

  intt(r_ntt)
end

# 実行
p_coeffs = [5, 1, 3, 2]
q_coeffs = [1, 2, 4, 1]

puts "p(x)の係数: #{p_coeffs}"
puts "q(x)の係数: #{q_coeffs}"
puts "NTTベース:  #{poly_multiply_ntt(p_coeffs, q_coeffs)}"

LND 0.18.5以下に存在した脆弱性

先日Matt Morehouseによって開示されたバージョン0.18.5以下のLNDに存在した脆弱性について↓

Disclosure: Critical vulnerabilities fixed in LND 0.19.0 - Implementation - Delving Bitcoin

この投稿ではLNDに存在した3つの脆弱性が開示されている。1つはDoSで残り2つは資金損失系。

DoS脆弱性

LND 0.18.5以下のバージョンに影響するDoS脆弱性。

morehouse.github.io

LNDは、ピアからメッセージを受信すると、メッセージを適切なサブシステムで処理できるようにキューに入れるようになっており、

• サブシステムのgossiperとchannel linkでは、ピアごとに最大1,000メッセージをキューイング可能
• Lightningプロトコルのメッセージは最大64KBのサイズになり得る
• LNDは利用可能なファイルディスクリプタ数まで多数のピア接続を許可していた（ちなみに自分のUmbrelのLNDプロセスにおけるファイルディスクリプタ数は1073741816だった）

のが問題となった。

攻撃者はターゲットノードに多数のピア接続をし、64KBのquery_short_channel_idsをスパム送信することで、ターゲットノードのメモリをOOMでクラッシュさせることができる。8GBのRAMを搭載するノードに対して、実験では5分以内にOOMを引き起こすことができたとのこと。

緩和策

この脆弱性への対応として、LND 0.19.0では、

• キューのサイズが1,000メッセージから50メッセージに縮小し、
• チャネルを開設していないピアからの接続を100件までに制限

するという緩和策が導入された。

過剰フェイルバックによる資金喪失

2つめの脆弱性はこちら↓

morehouse.github.io

過剰フェイルバックの脆弱性は、もともとLND 0.17.5以下に存在していて、LND 0.18.0で修正された経緯がある↓

techmedia-think.hatenablog.com

今回報告されたのは、その亜種。

前回の脆弱性は、上記の記事のステップ⑩のレスポンスを下流ノードが返さずに⑨のコミットメントトランザクションをブロードキャストし、上流のLNDを再起動させることで、該当HTLCのさらに上流へのフェイルバックが行われるというもの。

今回の脆弱性は、下流の攻撃者が⑨のコミットメントトランザクションをブロードキャストするのではなく、被害者の上流ノードに⑦のコミットメントトランザクションをブロードキャストさせ、その後再起動させることで、該当HTLCのさらに上流へのフェイルバックが行われるというもの。これは、攻撃者のノードが被害者のノードにerrorメッセージを送信することでトリガーすることができる。

この亜種は、将来の過剰なフェイルバック脆弱性を防ぐためにBOLT 5をアップデートしていた際に発見され、プリイメージが既に判明しているHTLCはフェイルバックしないようにするチェックが追加され修正された。

置換遅延攻撃

３つめの脆弱性は、LND 0.18.5以下のバージョンに影響するもので、トランザクションのバッチ処理およびその手数料の引き上げを管理するLNDのスイーパーシステムを狙ったもの↓

morehouse.github.io

このスイーパーシステムには2つの弱点がある：

• バッチトランザクション内のインプットの内１つでも競合するトランザクションが承認されると、残ったインプットで再度バッチトランザクションを作成しなおすが、その際手数料が最小値にリセットされる。
• 競合トランザクションによる二重使用後、再集約が次のブロックまで遅延される。

これらを悪用した攻撃のシナリオが↓

1. 攻撃者は被害者と直接チャネルを開き、被害者が許容する最小のCLTVデルタ（デフォルトだと80ブロック）を使って、約40個のHTLCを自分宛にルーティングする。この時最後のHTLCを最大額とする。
2. 攻撃者は、HTLCを期限切れになるまで保持し、被害者がチャネルを強制閉鎖する。ここで上流のHTLCのタイムアウトまで80ブロックのカウントダウンが始まる。
3. 被害者のスイーパーは、40個のHTLCタイムアウトを1つのトランザクションに集約してブロードキャストする。
4. 攻撃者はmempoolを監視して3のトランザクションを検知し、その内1つのインプットについてプリイメージを使って回収する競合トランザクションを作成し置換させる。
5. 4のトランザクションが承認されると、被害者はそのプリイメージを使って上流のHTLCを解決できるが、残りの39個については、再集約は次のブロックまで遅延される。つまり競合トランザクションが承認されたブロック高をNとすると再集約されるのはN+1のブロックの承認後。
6. N + 1ブロックが承認されると、被害者は残りのHTLCタイムアウトを含む新しいバッチトランザクションをブロードキャストする。この時、手数料は手数料関数の最小値にリセットされる。攻撃者は4以降の攻撃を繰り返す。
7. 80ブロック経過後、攻撃者は残りのHTLCを窃取（下流はプリイメージで、上流はタイムアウトで）する。

再集約の遅延が+1ブロック分あるので、80ブロックの期限に対して40回の置換で済むようになってる。

攻撃コスト

攻撃者は最大40個のトランザクションを置換する必要があり、その際、バッチトランザクションの手数料を上回る手数料を支払う必要がある。

• 攻撃全体の平均手数料率を1.4 sat/vBと仮定し、
• バッチトランザクションに平均20個のHTLCが存在すると仮定すると（最初は40個で1つずつ減ってくため）

置換毎の平均コストは、HTLC 20個 × HTLCあたり166.5 vB × 1.4 sat/vB = 4,662 sats。

これが40回なので総コストは、40 × 4,662 sats = 186,480 sats。

つまり、20万sats未満のコストでチャネルの全資金を盗むことができる。

緩和策

LND 0l19.0では、

• 再集約時の遅延をなくし、
• 手数料値のリセットを修正し積極的にバンプし続ける

ように修正し、攻撃にかかるコストを引き上げた：

• 2倍のHTLCと回数（最低80回）の置換が必要になり
• 毎回、高騰した手数料を上回る必要がある