Multi/Threshold-Signature
References
accountable schnorr multisig by jeff
Multisig
the case of schnorr
communicationがだるい
n-of-mのためには非効率なmerkle tree活用が必要
the case of bls
ペアリング検証の非効率性
複数の署名集約はできるがペアリング計算自体はその署名数だけ行う必要がある
security consideration
the case of threshold
group key setupのためのcommucation(対話&検証)がだるい
Just spliting a secret key into chunks
ECDSA
https://gyazo.com/5178239f1b60b11d6fe1584528466904
P2PKH
Locking Script
OP_DUP OP_HASH160 <Cafe Public Key Hash> OP_EQUAL OP_CHECKSIG
Unlocking Script
<Cafe Signature> <Cafe Public Key>
Multi-sig
Locking Script
2 <Public Key A> <Public Key B> <Public Key C> 3 OP_CHECKMULTISIG
Unlocking Script
OP_0 <Signature B> <Signature C>
P2SH
UTXOに含まれてしまう複雑なScriptをハッシュ値で小さくしTxデータサイズを小さくする
複雑なlocking scriptをそのハッシュ値に置き換える。
Redeem Script
2 <Public Key A> <Public Key B> <Public Key C> 3 OP_CHECKMULTISIG
Locking Script
OP_HASH160 <20-byte hash of redeem script> OP_EQUAL
Unlocking Script
<SIgnature B> <Signature C> redeem_script
マルチシグや閾値署名が難しい
Scriptが必要、署名や公開鍵の集約ができない
署名構造が複雑すぎてatomic swapやLightningのためにBitcoin Scriptが必要になる。
Scriptless Scriptの仕組みとポテンシャル
Schnorr
シンプルな署名方式
発明から年月が経っておりセキュリティ根拠も十分。
(x, X)を鍵ペア、rを署名者が選択するランダムナンスとする。
$ R = rG
$ s = r + H(X, R, m)x
が署名。
検証は、
sG = R + H(X, R, m)X
bip-schnorr
Multisig
それぞれの署名者の公開鍵を$ X_iとし、その合計をXとする。
それぞれの署名者はランダムな$ r_iを選び、他の署名者と$ R_i = r_iGを共有する。
よって、それぞれの署名者は全ての署名者の$ R_iを利用し、その合計Rを計算できる。
これを用いて、それぞれの署名者は$ s_i = r_i + H(X, R, m)x_iを計算する。
この$ s_iを署名をブロードキャストする人に集めて、$ s_iの合計値sを計算し、最終的な署名(R, s)が生成する。
検証は通常のShnorrと同じで$ sG = R + H(X, R, m)X
Xによって公開鍵の集約もでき、sとRの合計値を利用しているので署名集約もできている。
Problems
3 communication roundsが必要
他の署名者のランダム値を知った後に自分のランダム値を変更できないように$ hash(R_i)をあらかじめ全ての署名者に送信しておく。
実際に$ R_iを集めてRを計算する。
署名する。
Rogue key attack
一人の公開鍵に対応する秘密鍵のみで署名ができてしまう問題。
例えば、アリス$ X_aとボブ$ X_bの公開鍵でマルチシグするとき、アリスがボブに$ X_aを送信し、ボブは自分の公開鍵を$ X_b' = X_b - X_aとして送信した場合、鍵の集約をすると$ X_a + X_b' = X_a + X_b - X_a = X_bとなり、ボブの秘密鍵だけで署名できてしまうことになる。
単純な対策としては、あらかじめその秘密鍵を持っている証明をしておく。この場合、ボブは$ X_b'の秘密鍵は持っていないので証明することができない。
ECDSAと同じようにsecretとmassgeに基づいた決定論的乱数(r)を利用できない。
m-of-nのマルチシグを実現するのはけっこうトリッキー(公開鍵の組み合わせでmerkle tree構成やPVSSを用いた(t,n)閾値署名など)
Musig
schnorr-multisigにおけるRogue key attack問題を解決したマルチシグ手法。
schnorrの場合は、単純にそれぞれの署名者の公開鍵の合計をXとしていたのに対し、Musigでは$ L = H(X_1, X_2,...)とし、$ H(L, X_i)X_iの合計をXとする。つまり全ての公開鍵のハッシュ値を公開鍵に乗算した和にしている。
これにより$ R_i = r_iGに関しては、schnorrと同じで、$ s_i = r_i + H(X, R, m)H(L, X_i)x_iとなり、それぞれの$ s_iに対して署名ごとに異なる(公開鍵情報$ X_iによって変化する)$ H(L, X_i)を秘密鍵$ x_iに乗算している。よって、攻撃者はrogue key attackにおける不正な公開鍵を生成することができなくなる。
Simple Schnorr Multi-Signatures with Applications to Bitcoin
Add MuSig module
Threshold Signatures and Accountability
Schnorr Signatures in CodeChain
https://www.youtube.com/watch?v=j9Wvz7zI_Ac
Monero multisignatures explained
BLS-multisignature
署名検証(pairing)の計算コスト
セキュリティ根拠
2-of-3 multisigを考える。hash(x)をスカラーハッシュとし、H(x)をcurveへのハッシュとする。
Setup phase
それぞれの署名者の鍵ペアを$ (pk_i, Pi)とすると集約公開鍵は$ a_i = hash(P_i, {P_1, P_2, P_3})とし、$ P = a_1P_1 + a_2P_2, a_3P_3で計算できる。
Threshold-ECDSA
署名に必要な乱数kはRGNsの不正を防ぐために、RFC6979で定められている、secretとmessageに基づいて決定的に決まるkで計算する。
shareの乗算により多項式の次数が2倍になるのでtを多項式次数とした時に少なくとも2t+1の参加者が必要というのが、'96 paperの手法。
'06 paperの手法では、secret shareを$ x = x_1*x_2として用いているが次数を2以上に一般化するのが困難。
'16 paperでsecret share xをそれぞれの署名者の公開鍵で加法準同型暗号化したciphertextを参加者間でシェア。ただ、効率性が悪くscalableじゃない、zkp使ったり。
'18 paperでSPDZアプローチのMPCで効率的な手法を提案。
Fast Multiparty Threshold ECDSA with Fast Trustless Setup
Threshold-Schnorr
provably secure distributed schnorr signatures and a {t,n} threshold scheme
threshold-signatures-and-accountability
Threshold-BLS
shielded K-of-N multisig using a tree of K-choose-N MultiRedDSA keys