2021-01-24

Bitcoin Core 0.21.0でサポートされたBIP-157フィルターを確認してみる

Bitcoin Ruby

先日リリースされたBitcoin Core 0.21.0で軽量クライアント向けて新しいフィルターの提供がサポートされるようになった。有効になったBIP-157の仕様については↓

techmedia-think.hatenablog.com

BIP-157のサポートはBitcoin Core起動時に-blockfilterindex=1 -peerblockfilters=1オプションを付けて起動すると有効になる。

フィルターの確認

BIP-157自体はフィルターをP2Pメッセージで提供する仕様を定義したもので、フィルターの仕様はBIP-158で定義されており、以前のバージョンからフィルターの作成自体は可能だった。ブロックハッシュを指定してgetblockfilter RPCを実行すると対象ブロックのフィルターデータが取得できる。

$ ./bitcoin-cli -signet getblockfilter 000000a70fc28dac4bd9638ed2fe72545dbc0d71f9bf0e59e326350c8c53336e
{
  "filter": "0c79dd114255fdef1542cd3f2495e0f9346b4fc32a154639f375e0691ce5a36d",
  "header": "238ca2b3a4c3f2e3eb8c97af339d2cff57b570028563ccef222661ff061dcef5"
}

フィルターのデータは、<datadir>/indexes/blockfilter/basic以下にあり、その内ディレクトリ直下にあるfltrxxxx.datというバイナリファイルにエンコードされたフィルターのデータが格納されている。具体的には<block hash><フィルターのCompactSize><エンコードされたフィルター>という形式で各フィルターのデータが記録されるようになっている。

例えば、signetのブロック000000a70fc28dac4bd9638ed2fe72545dbc0d71f9bf0e59e326350c8c53336eの２つめのトランザクション 47e6e0e2d0c8a6186be35b1a42807383e9e56094c704a818631681f48cc07606の最初のアウトプット

{
  "value": 48.75997730,
  "n": 0,
  "scriptPubKey": {
    "asm": "0 1ed6f4590e7088dbebdf66b7072e87ab9c29b0c0",
    "hex": "00141ed6f4590e7088dbebdf66b7072e87ab9c29b0c0",
    "addresses": [
      "tb1qrmt0gkgwwzydh67lv6mswt584wwznvxqwnjm8n"
    ]
  }
}

が含まれているかどうかは、bitcoinrbで以下のように検証できる。

require 'bitcoin'

block_hash = '6e33538c0c3526e3590ebff9710dbc5d5472fed28e63d94bac8dc20fa7000000'
encoded_filter = '0c79dd114255fdef1542cd3f2495e0f9346b4fc32a154639f375e0691ce5a36d'
 # filterをデコード
filter = Bitcoin::BlockFilter.decode(Bitcoin::BlockFilter::TYPE[:basic], block_hash, encoded_filter).filter
filter.match?('00141ed6f4590e7088dbebdf66b7072e87ab9c29b0c0'.htb)
=> true

実装の詳細については、以前書いた記事を参照。

P2Pメッセージ

↑は今までも確認できた。今回の本題はBIP-157なのでP2Pメッセージになる。P2Pメッセージの確認はRPCではできないので、irbベースでBitcoinのノードと対話的にP2Pメッセージをやりとりするツールbitcoin-p2pを作ってみた。今回は、これを使って確認してみる。

事前準備

bitcoin-p2pは、Rubyが使える環境であればgem install bitcoin-p2pでインストールできる。接続先のノードのアドレスを-hオプションで、接続するネットワーク（mainnet, testnet, signet）を-nオプションを使ってbitcoin-p2pを起動する。

$ bitcoin-p2p -h localhost -n signet
> connected! You can send version message.

となるので、最初にハンドシェイクのためversionメッセージとverackメッセージを交換する。bitcoin-p2pでは、bitcoinrbがロードされているので、bitcoinrbのクラスを使ってBitcoinのP2Pメッセージを構成できる。例えばversionメッセージは、

3.0.0 :001 > ver = Bitcoin::Message::Vresion.new
 => #<Bitcoin::Message::Version:0x00005590317410f0 @version=70013, @services=8, @timestamp=1611462693, @local_addr=#<Bitcoin::Message::NetworkAddr:0x0000559031738ae0 @time=1611462693, @ip_addr=#<IPAddr: IPv4:127.0.0.1/255.255.255.255>, @port=3...

で生成し、必要なパラメータは随時更新した上で、

3.0.0 :002 > send_message(ver)
 => send message data: 0a03cf4076657273696f6e00000000006700000093cb71427d110100080000000000000025f80c6000000000080000000000000000000000000000000000ffff7f00000195bd080000000000000000000000000000000000ffff7f00000195bd519f0f6807576b1c112f626974636f696e72623a302e362e302f0000000000

すると、接続先のノードにversionメッセージが送信される。send_messageはbitcoin-p2pに定義されているメソッドで、bitcoinrbに実装されているメッセージクラスのインスタンスか、P2Pメッセージのデータを渡せば、それを相手に送信する。

versionメッセージを送信すると、すぐに相手からversionメッセージが返ってくる↓

 =>  receive version. payload: {"version"=>70016, "services"=>1097, "timestamp"=>1611462696, "local_addr"=>{"time"=>nil, "ip_addr"=>#<IPAddr: IPv6:0000:0000:0000:0000:0000:0000:0000:0000/ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff>, "port"=>0, "services"=>0}, "remote_addr"=>{"time"=>nil, "ip_addr"=>#<IPAddr: IPv6:0000:0000:0000:0000:0000:0000:0000:0000/ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff>, "port"=>0, "services"=>1033}, "nonce"=>5555482496462444166, "user_agent"=>"/Satoshi:0.21.0/", "start_height"=>21843, "relay"=>true}

※ ちなみにBIP-157のメッセージを確認するので、最初に書いた起動オプションが有効なノードに接続する必要がある。具体的にはサービスフラグのNODE_COMPACT_FILTERSが有効になっているノード。このフラグが有効かどうかは受信した相手のversionメッセージのservicesの値から確認できる。今回はそういったノード探すのも面倒だったので、ローカル環境でsignetに接続したノードを使ってる。

続いて、verackメッセージを返す。

3.0.0 :003 > ack = Bitcoin::Message::VerAck.new
 => #<Bitcoin::Message::VerAck:0x00005590316342c0> 
3.0.0 :004 > send_message(ack)
 => send message data: 0a03cf4076657261636b000000000000000000005df6e0e2

相手からもverackメッセージが返ってくる。ここまでで最初のハンドシェイクは完了。

※ 他のメッセージも送れるようになるが、こちらの送信したメッセージが仕様に準拠していなかったり相手のポリシーに違反する場合は、接続が切断される。この場合、=> connection is closed. please stop.とコンソール上にメッセージが表示されるので、stopで終了する。

フィルタヘッダーの取得

IBDで最初にブロックヘッダーを同期するように、BIP-157でも軽量クライアントは最初にフィルターヘッダーの同期を推奨してる。フィルターヘッダーは、フィルタータイプ=0（Basic）、要求する最初のヘッダーのブロック高、要求する最後のブロックのブロックハッシュ（リトルエンディアン）を指定して、getcfheadersメッセージを送信する。最初にRPCでフィルターを確認したブロックのブロック高が20921で、それから6ブロック分のデータを取得するメッセージが↓

3.0.0 :005 > getcfheaders = Bitcoin::Message::GetCFHeaders.new(0, 20921, "8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000")
 => #<Bitcoin::Message::GetCFHeaders:0x000055e4221f5520 @filter_type=0, @start_height=20921, @stop_hash="8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000"> 
3.0.0 :006 > send_message(getcfheaders)
 => send message data: 0a03cf40676574636668656164657273250000000f40e64500b95100008e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000

すると、↓のcfheadersメッセージが返ってくる。

3.0.0 :007 > 
 => receive cfheaders. {"filter_type"=>0, "stop_hash"=>"8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000", "prev_filter_header"=>"df27cb4b59ebe70c93de3985ba367802e65ebd119671b2a46f612223898de4a6", "filter_hashes"=>["1f257e1e028cea1cc50d41c6acc6039c2d7e6d3611dfb475ef6e1224533f1879", "fc9c229680cefc9e88907dd15952781a11502fa7670e30eedd6c7be7fe2ad8f2", "bd9b4c675c1cec25d8b0ab7bf6132fd143dee1e0918173e3f6c56c6bca72259f", "18357fb16bf1f322fb8a054efeccc05a94bf4837df51288b15da7022572a5396", "dcc177c2588dbde7357c06f0dbd13d5ad4ba25dddfeb337f7e6f25acc119020c", "39ac2e33dbf8450794209b61092185b9fd0da9ee90020c1bb473d8dd9fc37269"]}

フィルターの取得

続いて、フィルターの取得では、getcfiltersメッセージを送信する。使用するパラメータはgetcfheadersと同様。

3.0.0 :008 > cfilter = Bitcoin::Message::GetCFilters.new(0, 20921, "8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000")
 => #<Bitcoin::Message::GetCFilters:0x000055e422038250 @filter_type=0, @start_height=20921, @stop_hash="8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000"> 
3.0.0 :009 > send_message(cfilter)
 => send message data: 0a03cf406765746366696c7465727300250000000f40e64500b95100008e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000

メッセージを送ると、要求した数分のcfilterメッセージが送られてくる。

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"6e33538c0c3526e3590ebff9710dbc5d5472fed28e63d94bac8dc20fa7000000", "filter"=>"0c79dd114255fdef1542cd3f2495e0f9346b4fc32a154639f375e0691ce5a36d"}

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"5b9c72782f163fca7737163462ec11e561b3abe8cad18d0269027a0e4b000000", "filter"=>"010207f0"}

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"df44626bcfd2b104b4b4a4af8c0ceb06b8f855312bc557e7b18468e717000000", "filter"=>"016b8f60"}

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"a47f8529260810d790b4660ca2b7c96d8e9f0b2c926e18227745131ce7000000", "filter"=>"0161c130"}

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"300fea5fcad1f8e7eea5fb705a481c25723b67d94687a26bbe75400c2e010000", "filter"=>"019102d0"}

 => receive cfilter. {"filter_type"=>0, "block_hash"=>"8e2a4663fc79a21a173c2dc6f715bd4bda4f9b939cb806390b98e007ac000000", "filter"=>"016e9cd0"}

最初に受信したのがRPCで確認したブロックのハッシュで、フィルターの値も同じであることが分かる。

ということで（getcfcheckptとcfcheckptメッセージは割愛したけど）、Bitcoin Core 0.21.0で有効化できるようになったBIP-157フィルターが利用できるようになってることを確認できた。これでBIP-37に代わる新しい軽量クライアント向けのフィルタ機能が利用できるようになる。

2021-01-07

楕円曲線のスカラー倍算アルゴリズム Part 1

Cryptography Bitcoin

昨年9月にパテントロックが外れたことで、Bitcoin Coreでもスカラー倍算アルゴリズムの高速化オプションが有効化された↓

github.com

もともと、パテントの存在を知らずHal Finneyによって2013年にlibsecp256k1には実装されてたものの無効化されていたものが有効になったらしい↓

cointelegraph.com

楕円曲線暗号においては、楕円曲線のスカラー倍算の計算をすることが多い。

秘密鍵から公開鍵を算出するのも、楕円曲線のベースポイントGに秘密鍵をスカラー値としたスカラー倍算であるし、ECDSAの署名検証アルゴリズムや、ECDHで共有鍵を導出するといったケースでも。

このスカラー倍算は、素直に実装すると乗算するスカラー値分だけポイントを加算することで計算できる。例えば、xPを計算する場合、Pをx回加算することでxPを求めることができる。ただ、素直にこれを計算すると遅く効率が悪いので、スカラー倍算を高速にするためのアルゴリズムがいろいろある。ということで、実際にどんなアルゴリズムがあって、現在Bitcoin Coreではどんなアルゴリズムを実装しているのか調べてみよう（ボリューム的にBitcoin Coreのアルゴリズムは後日別の記事で）。

バイナリ法

楕円曲線のスカラー倍算を多項式時間で実行するための有名なアルゴリズムがバイナリ法。乗算するスカラー値xをバイナリ形式にし、

ビットが1の場合は、加算と2倍算を行う。
ビットが0の場合は、2倍算のみを行う。

ことで、計算をより高速に行う。

例えばx = 5とした場合、それをバイナリ展開すると101（ ${1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0} }$ ）になる。5Pをバイナリ法で計算すると以下のようになる。

計算結果をQとし初期化(無限遠点Oと)する。計算中に加算する点の一時変数v = Pと初期化する。
最下位ビットは1なので、Qにvを加算し、vを2倍算しv = 2v（この時点でv = 2P）とし、ビットシフトする。
続く最下位ビットは0なので、vを2倍算しv = 2v（つまりこの時点でv = 4P）とし、ビットシフトする。
続く最下位ビットは1なので、Qにvを加算し、vを2倍算しv = 2v（この時点でv = 8P）し、ビットシフトする。
処理するビットが無いので、Qが計算結果。

手順2でQ = Pがセットされ、手順4でさらに4Pが加算されQ = 5Pになる。これがバイナリ法のアルゴリズムで、計算処理で実際に実行されるのは2倍算と加算。

Rubyのecdsa gemでも楕円曲線のスカラー倍算ではこのアルゴリズムを使用している。実装もシンプル↓

# Returns the point multiplied by a non-negative integer.
#
# @param i (Integer)
# @return (Point)
def multiply_by_scalar(i)
  raise ArgumentError, 'Scalar is not an integer.' if !i.is_a?(Integer)
  raise ArgumentError, 'Scalar is negative.' if i < 0
  result = group.infinity
  v = self
  while i > 0
    result = result.add_to_point(v) if i.odd?
    v = v.double
    i >>= 1
  end
  result
end

↑のコードのv.doubleが2倍算、result.add_to_point(v)が加算処理だが、これらは有限体上で計算され、具体的には以下の計算が行われている。

有限体上の加算

アフィン座標の楕円曲線の方程式を ${y^{2} ≡ x^{3} + ax + b \mod p}$ とした場合、２つの座標点 ${P = (x_1, y_1), Q = (x_2, y_2) }$ の加算 ${P + Q = (x_1, y_1) + (x_2, y_2) = (x_3, y_3)}$ （P != Q）の計算は、以下の式で計算される。

$x_{3} = \left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}} \right)^{2} - x_{1} - x_{2} \mod p$
$y_{3} = \left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}} \right) (x_{1} - x_{3}) -y_{1} \mod p$

ecdsa gemのadd_to_pointのコードもこの計算をしてる。なお、 $\frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ は点Pと点Qを結ぶ直線の傾き。

有限体上の2倍算

P = Q、つまり2Pの計算は、以下の式になる。

$x_{3} = \left( \frac{3x_{1}^{2} + a}{2y_{1}} \right)^{2} - 2x_{1} \mod p$
$y_{3} = \left( \frac{3x_{1}^{2} + a}{2y_{1}} \right) (x_{1} - x_{3}) -y_{1} \mod p$

ecdsa gemのdoubleのコードもこの計算をしてる。

ウィンドウ法

バイナリ法を少し変更したものがウィンドウ法で、ウィンドウ法ではまずウィンドウサイズwを決め、スカラー値xをm進展開する。ここでmはm = 2^wで、ウィンドウサイズw = 1の場合↑のバイナリ展開になる。

例えばw = 4とした場合のm進展開(16進展開)であれば、スカラー値xは、

${x = x_0 * 2^{4 * 0} + x_1 * 2^{4 * 1} + x_2 * 2^{4* 2} + ... + x_j * 2^{4 * j}}$

と展開され、各 ${x_i}$ は ${x_i \in｛0, 1, ..., m-1(15)｝}$ の値を取る。

例えばx = 515であれば、 ${x = 3 * 2^{4 * 0} + 0 * 2^{4 * 1} + 2 * 2^{4* 2} = 3 + 0 + 512 = 515}$ と展開される。

事前準備

スカラー倍算を行う点をPとした場合、ウィンドウ法では事前に、i = 1, ..., m-1について ${P_i = i * P}$ を計算する。m = 2⁴であれば、i = {1,...,15}について、 ${P_i = P_{i-1} + P}$ を計算する。つまりこの事前準備で2P, 3P, ..., 15Pが計算される。

計算

計算結果をQとし初期化(無限遠点Oと)する。
i = j〜0について以下の計算をループする。
1. Qの2倍算をw回実行し、結果をQにセットする。
2. ${x_i ＞ 0}$ の場合、事前計算したポイント ${x_iP}$ をQに加算し、結果をQにセットする。

w = 4, x = 515の場合、実際以下の計算が行われる。

最初のループ（j = 2）
1. Qの2倍算を4回実行し、結果をQにセット。この段階でQは無限遠点であるため、Qは無限遠点のまま。
2. Qに2Pを加算しQにセット。この段階でQ = 2P。
2回目のループ（j = 1）
1. Qの2倍算を4回実行し、結果をQにセット。この段階でQ = 32P。
3回目のループ（j = 0）
1. Qの2倍算を4回実行し、結果をQにセット。この段階でQ = 512P。
2. Qに3Pを加算しQにセット。この段階でQ = 515P。

ウィンドウ法もバイナリ法と同様、計算は2倍算と加算処理だが、点の加算回数はバイナリ法に比べて少なくなるという特徴があり、点の加算は2倍算に比べて遅いことからバイナリ法より計算コストが小さくなる。

射影座標を使った高速化

バイナリ法やウィンドウ法で計算される加算や2倍算の計算式を↑に記載したけど、どちらの計算でも逆元の計算（ $\left( \frac{y_{2} - y_{1}}{x_{2} - x_{1}} \right)$ および $\left( \frac{3x_{1}^{2} + a}{2y_{1}} \right)$ の部分）が登場する。この逆元の計算は拡張ユークリッド互助法などを使って行われるが、そのコストは他の加算や乗算と比べて非常に大きいので、逆元の計算を減らすことができれば計算速度も速くなる。

この逆元の計算を回避するために使われるのが射影座標になる。楕円曲線上の点は通常（x, y）座標で表すことが多く、これをアフィン座標と呼ぶ。この平面上の点の座標を、３つの要素（X, Y ,Z）で表現する射影座標と呼ばれる座標系に変換することで、計算コストの高い楕円曲線の除算の計算を回避でき、計算の高速化が可能になるという。

アフィン座標（x, y）は、射影座標（プロジェクティブ座標系）を使うと（x = X/Z mod p, Y/Z mod p）と表現でき、この変換を利用すると、アフィン座標系の楕円曲線の方程式

${y^{2} ≡ x^{3} + ax + b \mod p}$

を、射影座標系における楕円曲線の方程式

${Y^{2}Z ≡ X^{3} + aXZ^{2} + bZ^{3} \mod p}$

に変換できる。また射影座標においては以下が成立する。

２つの点(X, Y, Z), (X', Y', Z')について、X' = cX, Y' = cY, Z' = cZが成立する場合、2点は等しいとみなされる。
射影座標における無限遠点はX = 0かつZ = 0の点である（アフィン座標と違って射影座標では無限遠点も座標表記ができる）。

プロジェクティブ座標系における加算

２つのプロジェクティブ座標系の点 ${P = (X_1, Y_1, Z_1)}$ および ${Q = (X_2, Y_2, Z_2)}$ の加算 ${P + Q = (X_3, Y_3, Z_3)}$ （P != Q）の計算は、以下の式で計算される。

${u = Y_{2}Z_{1} - Y_{1}Z_{2}}$
${v = X_{2}Z_{1} - X_{1}Z_{2}}$
${A = u^{2}Z_{1}Z_{2} - v^{3} -2v^{2}X_{1}Z_{2}}$

として、

${X_{3} = vA}$
${Y_{3} = u(v^{2}X_{1}Z_{2} - A) - v^{3}Y_{1}Z_{2}}$
${Z_{3} = v^{3} Z_{1}Z_{2}}$

プロジェクティブ座標系における2倍算

P = Q、つまり2Pの計算は、以下の式になる。

${w = aZ_{1}^{2} + 3X^{2}_{1}}$
${s = Y_{1}Z_{1}}$
${B = sX_{1}Y_{1}}$
${h = w^{2} - 8B}$

として、

${X_{3} = 2hs}$
${Y_{3} = w(4B - h) - 8Y^{2}_{1}s^{2}}$
${Z_{3} = 8s^{3}}$

上記の計算式から逆元の計算が無くなっていることが分かる。そして算出した座標 ${(X_3, Y_3, Z_3)}$ をアフィン座標に変換 ${(x_3, y_3) = (X_3/Z_3, Y_3/Z_3)}$ する際に逆元の計算が発生するだけ。

ちなみに、 ${(x, y) → (X/Z^{2} \mod p, Y/Z^{3} \mod p)}$ の変換を行うのがヤコビ座標系。座標系としては、加算はプロジェクティブ座標系が速く、2倍算はヤコビ座標系が速いという特性があり、楕円曲線のスカラー倍算という意味ではヤコビ座標系を使った方が高速みたい。

参考

https://written.4403.biz/source/ecc_rev30r.pdf

と、長くなってきたので今回はここまで。

追記：

試しに射影座標を使ってスカラー倍算するコードをRubyで書いてみた↓

↑の同じバイナリ法でも、アフィン座標で計算するのに比べてかなり高速。逆元の計算が変換時以外発生いないだけでこうも違うのね。

2020-11-02

Moneroに導入された新しいリング署名スキームCLSAG

Cryptography Monero

MoneroでRingCT導入時に採用されたMLSAGについて書いた↓

techmedia-think.hatenablog.com

ので、続いて、2020年10月17日のアップグレードで新しく導入されたリング署名スキームCLSAGについて↓

https://eprint.iacr.org/2019/654.pdf

CLSAG

CLSAGはConcise Linkable Spontaneous Anonymous Groupの略で、機能としてはMLSAGと同じ機能を提供するが、署名サイズが小さくなり、署名検証も高速化する。

具体的には、インプット２つとアウトプット２つ持つ典型的なトランザクションについて、MLSAGを使ったトランザクションは約2.5KBだが、CLSAGを使うと1.9KBとなり約25%サイズが削減され、署名検証のスピードも20%の速度改善がみられるみたい。

署名の生成

↑のMLSAGの記事と同様に以下の表記を適用する（modの計算は省略）。

キーベクトルの個数をd
各キーベクトルのリングメンバーの数をn
n * d個の公開鍵のセットを ${L = P_{j, i}}$ 、 ${i \in 1, .., n}$ および ${j \in 1, ..., d}$
署名に使用するリング内の鍵（1..n）のインデックスをπとする。
楕円曲線上の点を出力するハッシュ関数を ${\mathbb H}$
署名対象のメッセージをm
Rをn * d個の全公開鍵の集約鍵

CLSAGで、d個のサイズnのキーベクトルを持つ場合（d ✕ nのマトリックスに対して）にd個の秘密鍵を使って有効な単一の署名を作る手順は↓

d個分対応する秘密鍵 ${x_{j, π}}$ を使ってキーイメージ ${I_j = x_{j, π} \mathbb H(P_{j, π})}$ を生成する（ ${j \in 1, ..., d}$ ）。
ランダムな数値αを生成する（MLSAGはd個生成したけどCLSAGでは１つのみ）。
${i \in 1, ..., n}$ からπを除いて（つまりデコイの数分）、ランダムな数値 ${r_i}$ を生成する（MLSAGはd✕(n-1)個生成していたけど、CLSAGではn-1個）。
n個の公開鍵（ ${i \in 1, ..., n}$ ）を使って集約公開鍵
${W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}$
を計算する（ ${T_j}$ はタグで、実際は”CLSAG_j”というデータのタグになる）。
ここで、 ${w_π = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * x_{j, π}}$ が ${W_π}$ に対応する集約秘密鍵となる。ｂ
d個のキーイメージを集約して集約キーイメージ
${\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}$
を計算する。
最初のチャレンジ ${e_{π+1} = H(T_c || R || m || αG || α \mathbb H(P_{1, π}))}$ を計算する（ ${T_c}$ はタグで、実際は”CLSAG_c”というデータ）。
${e_{π+1}}$ 以外のチャレンジとして、i = π+1, π+2, ..., n, 1, 2, ..., π-1について、それぞれチャレンジ ${e_{i+1} = H(T_c || R || m || r_iG + e_iW_i || r_i \mathbb H(P_{1, i} + e_i \tilde{W}))}$ を計算する。
${r_π = α - e_πw_π}$ を計算する。
署名値は ${σ(m) = e_1, r_1, ..., r_n}$

そしてプライマリキーイメージが ${I_1}$ で、補助イメージが ${(I_2, ..., I_d)}$ 。

署名の検証

キーイメージ ${I_1, ..., I_d}$ が楕円曲線のベースポイントの群内の点が検証する。
n個分、集約公開鍵と集約キーイメージを計算する。
- ${W_i = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * P_{j, i}}$
- ${\tilde{W} = \sum_{j=1}^d H(T_j || R || I_1 || ... || I_d) * I_j}$
${e_1}$ と各rの値を使って
${e'_{i+1} = H(T_c || R || m || r_iG + c_iW_i || r_i \mathbb H(P_{1, i} + c_i \tilde{W}))}$
を計算する。
最終的に計算した ${e'_1}$ が署名値の ${e_1}$ と一致すれば有効な署名。

MLSAGとの違い

↑のCLSAGの署名プロトコルとMLSAGの主な違いは、鍵の集約とLinkability。

鍵の集約

CLSAGでは、各チャレンジを生成する際にd個の鍵セットを単一の鍵として集約することで、元の鍵のマトリクスを一次元にしている。

MLSAGでは、チャレンジの入力値としてd個分 $(r_{j,i}G + e_iP_{j, i}, r_{j, i}\mathbb H(P_{j, i}) + e_iI_j)$ のペア計算する必要があり、dの数が増えるにつれて、計算量も線形増加する。

この部分がCLSAGでは集約鍵 ${W_i}$ と集約キーイメージ ${\tilde{W}}$ を使った単一の ${(r_iG + e_iW_i , r_i \mathbb H(P_{1, i} + e_i \tilde{W}))}$ のペアのみになっている（事前に鍵を集約するための計算はあるけど）。

Linkability

MLSAGの書名スキームではLinkabilityが全てのキーイメージに対して有効になるが、CLSAGの場合この部分に制限が入る。CLSAGではプライマリキーイメージと呼ばれる単一のキーイメージにのみLinkabilityが適用され、残りのキーイメージは補助キーという位置付けになる。

チャレンジの計算の部分で、 ${r_i \mathbb H(P_{1, i} + c_i \tilde{W})}$ と ${P_{1, i}}$ に固定されているのもこのためと思われる。

↑のMLSAGの記事にも書いたが、MoneroのRingCTでは、ワンタイムアドレスによる所有権の証明と、疑似コミットメントの正しさの証明のために２次元の公開鍵セットに対してMLSAGを提供しているが、二重使用に関係するのは前者のみで、前者のキーイメージだけ二重使用のチェックに使われる。そのため、それがプライマリキーイメージとなれば、他のキーイメージにLinkabilityは不要なので、CLSAGの制限は受容可能な条件になる。

なので、各インプット毎にMLSAGやCLSAGを適用してるけど、これをインプット跨いでやろうとすると、CLSAGでは無理になる。

データスペースと計算コストの削減に

d ✕ nのセットに対してMLSAGとCLSAGで署名を生成した場合、

MLSAGの書名データのサイズ：1 + n * dのデータ
CLSAGの書名データのサイズ：1 + nのデータ

nonceとなるrの個数が鍵の集約に伴い✕d必要なくなったので、その分データを削減することができる。また前述したように一度集約鍵の計算をすれば各チャレンジでdセット発生していた楕円曲線の演算をしなくて済むので、その分計算コストが小さくなる。

2020-11-01

RingCTでMLSAGを必要とした理由

Cryptography Monero

Moneroでは、送信者の情報を秘匿するためにトランザクションインプットにデコイとなるUTXOを含めて、UTXOセットの中のいずれかが実際にトランザクションで使用されることを証明するためにリング署名を採用している。Moneroが以前採用していたSchnorr署名の変形でもあるリング署名のスキームLSAGの仕組みについては以前ブログに書いた↓

techmedia-think.hatenablog.com

そして、2020年10月17日のネットワークアップグレードで、新しいリング署名スキームConcise Linkable Spontaneous Anonymous Group (CLSAG) がサポートされた。CLSAGの仕組みについて調べようかと思ったけど、既存のMLSAGの仕組みについて書いてなかったので、まずその内容から。

表記

↑のLSAGの投稿と表記を合わせて（インデックスだけ0からではなく1からにしてある）、

キーベクトルの個数をdとする。
各キーベクトルのリングメンバーの数をn
n * d個の公開鍵のセットを ${L = P_{j, i}}$ 、 ${i \in 1, .., n}$ および ${j \in 1, ..., d}$
署名に使用するリング内の鍵（1..n）のインデックスをπとする。
楕円曲線上の点を出力するハッシュ関数を ${\mathbb H}$
署名対象のメッセージをm

とする。

MLSAG

MoneroでRingCTを導入した際に導入されたリング署名スキームがMultilayer Linkable Spontaneous Anonymous Group (MLSAG)。

LSAGがあるn個の公開鍵セット（リングメンバー）について、その中のいずれかの秘密鍵で署名されたことを証明可能なリング署名スキームなのに対して、MLSAGはd個のサイズnのキーベクトルを持つ場合（d ✕ nのマトリックスに対して）にd個の秘密鍵を使って有効な単一の署名を作ることができる署名スキームとして拡張されたもの。d個分のLSAG署名を作るより、署名データがd - 1個分のサイズ分削減できる。

MoneroでRingCTを導入する際のリング署名スキームとして開発されたけど、Monero以外でも利用可能。

署名の生成

d個分対応する秘密鍵 ${x_{j, π}}$ を使ってキーイメージ ${I_j = x_{j, π} \mathbb H (P_{j, π})}$ を生成する。LSAGだと１つだったけど、dが複数ある前提なのでその数分キーイメージも生成する。
d個分ランダムな数値 ${α_j}$ を生成する。
${i \in 1,..., n}$ からπを除いて（つまりデコイの数分）、 ${j \in 1, ..., d}$ について、ランダムな数値 ${r_{j, i}}$ を生成する。
まず最初にπの次のインデックスπ + 1のチャレンジ ${e_{π + 1} = H(m || α_1G || α_1 \mathbb H(P_{1, π}) || ... || α_dG ||α_d \mathbb H(P_{d, π}))}$ を計算する。
${e_{π + 1}}$ 以外のチャレンジとして、i = π + 1, π +2, ..., n, 1, 2, .., π -1について、それぞれチャレンジ ${e_{i + 1} = H(m || r_{1, i}G + e_iP_{1, i} || r_{1, i} \mathbb H(P_{1, i}) + e_iI_1 || ... || r_{d, i}G + e_iP_{d, i} || r_{d, 1} \mathbb H(P_{d, i}) + e_i I_d)}$ を生成する。
${r_{j, π} = α_j - e_πx_{j, π}}$ を計算する。
署名値は ${σ(m) = (e_1, r_{1, 1}, ..., r_{d, n})}$

理解しやすいよう具体的に、リングメンバーの数 n = 3でキーベクトルの個数 d = 2として、その公開鍵のマトリックスを

d = １：
- ${P_{1, 1} = x_{1, 1}G}$
- ${P_{1, 2} = x_{1, 2}G}$
- ${P_{1, 3} = x_{1, 3}G}$
d = 2：
- ${P_{2, 1} = x_{2, 1}G}$
- ${P_{2, 2} = x_{2, 2}G}$
- ${P_{2, 3} = x_{2, 3}G}$

とし、署名者の秘密鍵のインデックスをπ = 2とする。

生成するキーイメージは以下の２つ。
- ${I_1 = x_{1, 2}\mathbb H(P_{1, 2})}$
- ${I_2 = x_{2, 2}\mathbb H(P_{2, 2})}$
続いてランダムな数値 ${α_1, α_2}$ を生成する。
デコイの数＝２つ分のnonceをdの数分生成する。
- ${r_{1, 1}, r_{1, 3}}$
- ${r_{2, 1}, r_{2, 3}}$
最初のチャレンジ ${e_3 = H(m || α_1G || α_1 \mathbb H(P_{1, 2}) || α_2G || α_2 \mathbb H(P_{2, 2}))}$ を計算する。
残りのチャレンジを計算する。
- ${e_1 = H(m || r_{1, 3}G + e_3P_{1, 3} || r_{1, 3} \mathbb H(P_{1, 3}) + e_3I_1 || r_{2, 3}G + e_3P_{2, 3} || r_{2, 3} \mathbb H(P_{2, 3}) + e_3I_2 )}$
- ${e_2 = H(m || r_{1, 1}G + e_1P_{1, 1} || r_{1, 1} \mathbb H(P_{1, 3}) + e_1I_1 || r_{2, 1}G + e_1P_{2, 1} || r_{2, 1} \mathbb H(P_{2, 1}) + e_1I_2 )}$
最後に、 ${r_{1, 2} = α_{1} - e_2x_{1, 2}}$ と ${r_{2, 2} = α_{2} - e_2x_{2, 2}}$ を計算する。
署名値は $σ(m) = (e_1, r_{1, 1}, r_{1, 2}, r_{1, 3}, r_{2, 1}, r_{2, 2}, r_{2, 3})$ となる。

手順６よりαの値はそれぞれ、

${α_1 = r_{1, 2} + e_2x_{1, 2}}$
${α_2 = r_{2, 2} + e_2x_{2, 2}}$

となり、これを使って手順４の ${e_3}$ を置き換えると、

${e_3 = H(m || (r_{1, 2} + e_2x_{1, 2})G || (r_{1, 2} + e_2x_{1, 2}) \mathbb H(P_{1, 2}) || (r_{2, 2} + e_2x_{2, 2})G || (r_{2, 2} + e_2x_{2, 2}) \mathbb H(P_{2, 2}))}$

つまり、

${e_3 = H(m || r_{1, 2}G + e_2P_{1, 2} || r_{1, 2} \mathbb H(P_{1, 2}) + e_2I_1 || r_{2, 2}G + e_2P_{2, 2} || r_{2, 2} \mathbb H(P_{2, 2}) + e_2I_2 )}$

となり、LSAGと同様、各チャレンジは循環したデータを含むようになる。

LSAGと比較すると

キーイメージと、nonceはdの数分増える。
計算するチャレンジの数は、dが増えても変わらず、リングメンバーの数だけ。
ただチャレンジの入力に、全dの全リングメンバーのデータを含め循環するよう拡張してある。ここがポイント！。

署名の検証

生成した署名の検証も手順はLSAGと同じで、違いは、チャレンジの入力となる各データの計算方法だけ。

キーイメージが楕円曲線のベースポイントの群内の点が検証する。
${e_1}$ と各rの値を使って、 ${e'_{i+1} = H(m || r_{1, i}G + e_iP_{1, i} || r_{1, i} \mathbb H(P_{1, i}) + e_iI_1 || ... || r_{d, i}G + e_iP_{d, i} || r_{d, 1} \mathbb H(P_{d, i}) + e_i I_d)}$ を計算する。
最終的に計算した ${c'_1}$ が署名値の ${e_1}$ と一致すれば有効な署名。

データスペースの節約に

↑のようにチャレンジの入力を多重化したのがMLSAGの仕組み。

d ✕ nのセットに対して、LSAGとMLSAGで署名を生成した場合、

LSAGの署名データのサイズ：（1 + n）* dのデータ
MLSAGの署名データのサイズ：1 + n * dのデータ

となる。nonceであるrの個数は変わらないけど、チャレンジはdの数によって変わらないので、 d - 1個で済む分データスペースを節約できる。

RingCTでMLSAGが必要な理由

2017年1月にMoneroに導入されたRingCTでは、このMLSAGが使われている。

最初は、Moneroで複数インプットがある場合に全インプットに渡って単一のMLSAG署名を作ればデータサイズを削減できるからか？と思ったけどどうもそうではなく、トランザクションの各インプットはそれぞれ個別のMLSAG署名を持っている。

RingCTからConfidential Transactionにより量をPedersen Commitmentとして表現されるようになったため、この機能の導入に伴いMLSAGが必要になっている。

CTの仕組みは

インプットのコミットメントの合計 − （アウトプットのコミットメントの合計 + 手数料へのコミットメント）= 0

が成立することでコインのインフレーションがされていないことを証明するようになっているが、Moneroでこれを単純に導入すると、デコイを含むインプットが参照するコミットメントのどれがゼロへのコミットメントかリンクできるとそもそもデコイにならないという問題が発生する。しかし、0へのコミットメントが計算できないと量が検証できない。

この問題に対処するため、実際に使用するインプットと同じ量を持つ疑似コミットメントを作成する。実際に使用するコミットメントを ${c = rG + aH}$ とすると、疑似コミットメントは ${c' = r'G + aH}$ となり、ブラインドファクターのみが異なる。そしてc - c' = (r - r')G + (a - a)H = (r - r')G は0へのコミットメントとなる。そしてそれが0へのコミットメントであることを証明するためc - c'に対して有効な署名を対応する秘密鍵(r - r')を使って生成できればいい。つまりこの疑似コミットメントはリングメンバーのいずれかのUTXOと同じ量を持つコミットメントであることが証明できる。

だが、単純に疑似コミットメントと署名をトランザクションインプットにセットしただけだと、リングメンバーのコミットメントと差し引いて計算してどれかが分かってしまうので、ここもリング署名にする必要がある。

RingCTでは、

コインの所有者であること
（どのコミットメントがリンクできないようにするための）疑似コミットメントが使用する実際のコミットメントと同じ量を持つこと

の２つを証明するのにリング署名を作成する。つまり、MLSAGの署名を作成するにあたって、

公開鍵のセットは、
- n個のワンタイムアドレスに対応する楕円曲線上の点
- n個の各コミットメントから疑似コミットメントを差し引いた楕円曲線上の点
対応する秘密鍵は、
- ワンタイムアドレスに対応する秘密鍵
- コミットメントのブラインドファクターから疑似コミットメントのブラインドファクターを差し引いた (r - r')の値

となる。なお、二重使用を防ぐために必要なキーイメージはワンタイムアドレスから作られたものだけで良いので、MoneroのRingCTのトランザクションに添付されるキーイメージはインプット毎に１つだけ。

これがRingCTの導入により、n ✕ 2のマトリックスにおけるリング署名を作らないといけない理由で、そのためにMLSAGが導入されたっぽい。

2020-10-26

２ラウンドで安全なマルチシグを生成する署名スキームMuSig2

Cryptography Schnorr

MuSigはもともとSchnorr署名の鍵の集約特性を活かして多重署名（マルチシグ）を単一のSchnorr署名で行う署名スキームで、Rogue-key攻撃に対して堅牢な署名スキーム↓

techmedia-think.hatenablog.com

ただ、署名の生成に以下の３ラウンドの通信が必要になる。

nonce値のコミットメントの交換
nonceの交換
部分署名の交換

そして、今回新しくMuSig2が公開された↓

https://eprint.iacr.org/2020/1261

MuSig2の署名方式

MuSig2では署名生成時の通信ラウンドも３→２に減らすことができる。↑のMuSigの3ラウンドの通信の内、１のnonceのコミットメントの交換プロセスを省略するみたい。省略してどう安全性を担保するのか？具体的な署名方式を見てみよう。

表記

${x_1, x_2, ..., x_n}$ を署名プロセスに参加する各ユーザーの秘密鍵とし、対応する公開鍵を ${X_1 = x_1G, X_2 = x_2G, ..., X_n = x_nG}$ とする。
集約する公開鍵のリストを ${L = (X_1, ..., X_n)}$ とする。
署名対象のメッセージをmとする。

署名の生成

各署名者は以下の手順で署名を生成する。

n人の署名者（署名者のインデックスをiとする）はv個のランダムな値（インデックスをjとする） ${r_{i, j}}$ を生成する。
1で生成した値についてPublic nonce ${R_{i, j} = r_{i, j}G}$ を計算する。
署名者iは、２で導出したPublic nonceのリスト ${R_{i, 1}, ..., R_{i, v}}$ を他の署名者にブロードキャストする。
署名者iは、各署名者の公開鍵から ${a_i = H_{agg}(L, X_i)}$ を計算する。
署名者は４で計算した値を使って、集約公開鍵 $\tilde{X} = \sum_{i=1}^n a_i X_i$ を計算する。
他の全参加者からPublic nonce のリストを受信したら、全参加者の同じインデックスjのPublic nonce $R_j = \sum_{i=1}^n R_{i, j}$ を集約する。
続いて、v個の係数のベクトル ${(b_1, ..., b_v)}$ を計算する。 ${b_1 = 1}$ で、それ以降のbの値は $b_j = H(j, \tilde{X}, (R_1, ..., R_v), m)$ として計算する。つまりこのbは決定論的に生成される。
ここでPublic nonceを集約して署名に使用する集約nonce $R = \sum_{j=1}^v b_j R_j$ を計算する。
さらに署名に使用するチャレンジ $c = H_{sig}(\tilde{X}, R, m)$ を計算する。
そして自身の部分署名 $s_i = c a_i x_i + \sum_{j=1}^v r_{i, j} b_j \mod p$ を計算し、他の署名者にブロードキャストする。
すべての参加者の署名値を受け取ると、 $s = \sum_{i=1}^n s_i \mod p$ を計算する。
最終的な署名値は（R, s）

署名の検証

署名者は以下を実行して署名が正しいか検証する。

各署名者の公開鍵から、 ${a_i = H_{agg}(L, X_i)}$ を計算する。
1から集約公開鍵 $\tilde{X} = \sum_{i=1}^n a_i X_i$ を計算する。
集約公開鍵と署名対象のメッセージおよび、署名データのRを使って、署名に使用するチャレンジ ${c = H_{sig}(\tilde{X}, R, m)}$ を計算する。
最後に $sG = R + c\tilde{X} = R + \sum_{i=1}^n a_icX_i$ が成立するか検証する。成立していれば署名は有効。

集約公開鍵の算出と、チャレンジの作成方法の部分が通常とは異なるが、最後の検証式は通常のSchnorr署名の検証式と同じ。

MuSigとの違い

集約公開鍵 ${\tilde{X}}$ の計算方法は、MuSigと同じでこれがRogue-key攻撃への耐性となるポイント。

MuSigと違うのは署名に使用するnonceの取り扱い。MuSigでは各参加者がPublic nonce ${R_i}$ を交換する前に、必ず ${R_i}$ へのコミットメントを交換し、全員分のコミットメントが揃った上で ${R_i}$ を交換する。

MuSigでnonceのコミットメントの交換が必要な理由

コミットメントの交換ラウンドを省略したり、事前にコミットメントおよびnonceの交換をした場合にどんな問題が起きるかは、Tim Ruffingの発表が分かりやすい。

問題になるのは、複数の署名セッションを並列して実行するケース。

攻撃にはWagnerのアルゴリズムを使用する。このアルゴリズムを利用すると、暗号学的ハッシュ関数Hを使用した場合

${H(m_0) = H(m_1)}$ となるような ${m_0, m_1}$ を発見するのは困難だが、
${H(m_0) = H(m_1) + H(m_2 + ... + H(m_n))}$ となるような ${m_0, m_1, ..., m_n}$ を発見するのは簡単

になる（メッセージの数が増える程、必要な計算量は減る）。

被害者の鍵ペアを ${X_1 = x_1G}$ 、攻撃者の鍵ペアを ${X_2 = x_2G}$ 、両者の集約公開鍵を ${X = X_1 + X_2 = (x_1 + x_2)G}$ とする。

攻撃者は被害者との間に、メッセージmの異なる署名セッションを複数、並列実行する。
被害者がセッションの数分、Public Nonce = ${R_1, R_2, ..., R_n}$ を送信する（ ${R = \sum_{i=1}^n R_i}$ とする）。
攻撃者は、ワグナーのアルゴリズムを使って ${H(P, R, m) = H(P, R_1 + R'_1, m_1) + ... + H(P, R_n + R'_n, m_n)}$ となるPublic nonce ${R'_1, R'_2, ..., R'_n}$ を見つける。右辺が各署名セッションで使われるハッシュ値。
攻撃者は３で見つけたPublic nonceのリストを被害者に送る。
被害者はこれらの値を使って部分的な署名 ${s_1, ..., s_n}$ を計算する。
被害者の部分署名をすべて加算し、攻撃者が自身の部分的な署名を加えると、Public nonce Rとメッセージmについて有効な両者のSchnorr署名が完成する。

ここで、被害者は一度もメッセージmに対して部分署名を作ってはいない。にも関わらずmに対して有効な署名が作れてしまう。つまり、同じ鍵に対して複数の署名セッセションを実行することで（事前にnonceにコミットしていない場合）、偽のメッセージに署名させることができてしまう。

↑が可能なのは、攻撃者が被害者からPublic nonceを受信した後で自身のPublic nonceを細工可能であるからで、この攻撃を回避するためには、Public nonceを交換する前にそのコミットメントを交換する必要がある。これがMuSigでコミットメントの交換ラウンドが必要になっている理由。

尚、コミットメント自体は署名時ではなくても、事前に共有しておくことが可能で、MuSigを実装したBlockstreamが開発しているlibsecp-zkpでは、コミットメントの事前シェアが可能になっている。

MuSig2でコミットメントの交換を不要にしたポイント

MuSig2では、コミットメントの事前交換をせずに↑のWagnerのアルゴリズムを使った攻撃にどう対処しているのか？

↑の攻撃は、同時署名セッションのそれぞれの最初のラウンドで集約Public nonceを制御することで、署名ハッシュを制御する機能に依存している。

MuSig2では、各署名者が１回の署名セッションで生成するnonceが１つではなくv個になっている。そして部分署名を生成する際もnonce ${r_i}$ 単体が単純な加算要素となる訳ではなく、

両者のPublic nonceから係数ベクトル値bを決定論的に生成し、
生成した各係数値をそれぞれのPublic nonceに乗算して集約Public nonceを生成している

この結果、↑のような集約Public nonceの制御が困難になるというのが、コミットメントラウンドを排除できた仕組みみたい。

実際にnonceの生成個数vの値については、ランダムオラクルモデル（ROM）においてv ≧ 4が推奨され、さらにROM + AGM（algebraic group model）の構成でv ≧ 2とされているので、そこまで大きい数値ではない。ただ、個数の根拠となってるセキュリティ証明あたりはまだよく理解できてない。

MuSig2のオーバーヘッド

MuSigと比べた場合のMuSig2のオーバーヘッドは、ブロードキャストするPublic nonceの値がv個に増えるのと、その個数分の操作の計算量。ただ↑のようにv値は小さいので、通信ラウンド１回分に比べたら小さなオーバーヘッドと言えそう。

決定性nonceの生成はNG

単体のSchnorr署名では問題ないが、MuSigやMuSig2などのSchnorrの多重署名スキームでは、決定性nonceの利用は攻撃による秘密鍵の漏洩に繋がるので、MuSig2でもnonceの生成（↑で各署名者がrを生成してる部分）では、安全な乱数生成器が必要になる。

現状、Schnorrの多重署名スキームで安全な決定性nonceを生成するスキームは、こないだ発表されたMuSig-DN↓のみ。

techmedia-think.hatenablog.com

※ ただ、MuSig-DNの場合、高価なゼロ知識証明の生成を必要とする。