Bitcoinスクリプトを使わないマルチシグを書いてみた

先日書いたECDSA版Scriptless Scriptsのベースとなっている署名スキームについて↓

techmedia-think.hatenablog.com

実際に2-of-2のマルチシグをScriptless Scriptsで実現するためのRubyのコードを書いてみた（仕組みについては↑の記事参照）。

事前準備としてbitcoinrbと、Paillier暗号を扱うpaillierのgemをインストールしておく。

ロックスクリプト

通常、Bitcoinスクリプトで2-of-2のマルチシグを利用する場合

2 <公開鍵１> <公開鍵2> 2 OP_CHECKMULTISIG

というscriptPubkeyにコインをロックするが、Scriptless Scriptsの場合はスクリプトを使用しない（正確には署名検証だけ行う）ので、マルチシグを構成する二者間の公開鍵に資金をロックする形になる。

まず、マルチシグの参加者はそれぞれBitcoinの鍵を生成する。

require 'bitcoin'
require 'paillier'

# アリスが鍵ペアを生成
alice_key = Bitcoin::Key.generate
alice_pub = alice_key.to_point

# ボブが鍵ペア生成
bob_key = Bitcoin::Key.generate
bob_pub = bob_key.to_point

両者は生成した公開鍵を相手に伝え、相手の公開鍵と自分の秘密鍵を使って新しい公開鍵（楕円曲線上の点）を計算する。

# アリスが計算する場合は
new_pubkey = bob_pub.multiply_by_scalar(alice_key.priv_key.to_i(16))

# ボブが計算する場合
new_pubkey = alice_pub.multiply_by_scalar(bob_key.priv_key.to_i(16))

こうやって計算した公開鍵（点）はどちらも同じ点を指す。この新しい公開鍵宛にコインを送ることで、2-of-2のマルチシグにコインをロックすることになる。ロックされたコインを償還するには、アリスの秘密鍵とボブの秘密鍵を使って計算した署名が必要になる。

アンロック時に使用する署名の作成

ECDSAの署名を生成する際は、通常ランダムなnonceを生成するが、ここでもアリスとボブがそれぞれnonceを生成する。

# アリスはランダムなnonceを生成
alice_r = Bitcoin::Key.generate
alice_R = alice_r.to_point

# ボブはランダムなnonceを生成
bob_r = Bitcoin::Key.generate
bob_R = bob_r.to_point

生成したnonceの公開鍵をお互いに共有する。先程と同じように自分のnonceと相手のnonceに対応した公開鍵を使って新しい公開鍵（楕円曲線上の点）を計算する。

# アリスはボブのナンスの点と自分のrを使ってRを計算
aR = bob_R.multiply_by_scalar(alice_r.priv_key.to_i(16))

# ボブはアリスのナンスの点と自分のrを使ってRを計算
bR = alice_R.multiply_by_scalar(bob_r.priv_key.to_i(16))

先程と同様、aRとbRは同じ点を指す。この点のx座標がECDSA署名のrになる。

point_field = ECDSA::PrimeField.new(ECDSA::Group::Secp256k1.order)

# 共通の点のx座標
r = point_field.mod(aR.x)

また、実際に署名を作成するメッセージダイジェストに両者合意しておく（実際のメッセージはマルチシグをアンロックして使用するトランザクションのsighashだけど、署名検証が通るか確認できれば良いので↓は適当なメッセージ）。

# メッセージ（実際にはマルチシグにロックされたコインを使用するトランザクションのsighashになる）
m = Bitcoin.sha256('message'.htb)
e = ECDSA.normalize_digest(m, ECDSA::Group::Secp256k1.bit_length)

続いて、アリスはPaillier暗号の鍵ペアを生成し、その公開鍵を使ってマルチシグの構成に使用した自分の秘密鍵を暗号化する。

# アリスはPaillier暗号の鍵ペアを生成する
privkey, pubkey = Paillier.generateKeypair(2048)

# アリスはckeyを生成してボブに渡す
ckey = Paillier.encrypt(pubkey, alice_key.priv_key.to_i(16))

暗号化したデータと、暗号化に使用した公開鍵をボブに渡す。

ボブは ${c_1 \gets Enc_{pk_A}((k_2)^{-1} \cdot m' + \rho q)}$ を計算する。 ${\rho}$ は巨大な素数で、qは曲線の位数（そのため最終的にmodすると ${\rho q}$ は消える）。

pq = Paillier::Primes.generatePrime(1024) * ECDSA::Group::Secp256k1.order
c1 = Paillier.encrypt(pubkey, point_field.mod(point_field.inverse(bob_r.priv_key.to_i(16)) * (e)) + pq)

続いて、 ${c_2 = (ckey) \odot (x_2 \cdot r \cdot (k_2)^{-1})}$ を計算。Paillierは暗号化したデータに対して定数の加算（Paillier.eAddConst）・乗算（Paillier.eMulConst）が可能。

c2 = Paillier.eMulConst(pubkey, ckey, point_field.mod(bob_key.priv_key.to_i(16) * r * point_field.inverse(bob_r.priv_key.to_i(16))))

計算したc1、c2を加法準同型演算して ${c_3 = c_1 \oplus c_2}$ を計算する。

c3 = Paillier.eAdd(pubkey, c1, c2)

計算したc3をアリスに送る。

c3を受け取ったアリスは、Paillier暗号の秘密鍵を使ってc3を復号し、 ${s \gets s' \cdot (k_1)^{-1}}$ を計算する。

# アリスはc3を復号する。
s_dash = Paillier.decrypt(privkey, pubkey, c3)

# アリスは復号したデータから署名に必要なsを計算する。
s = point_field.mod(s_dash * point_field.inverse(alice_r.priv_key.to_i(16))).to_i

こやって計算したsは

${s = (k1 \cdot k_2)^{-1} \cdot (m' + x_1 \cdot x_2 \cdot r )}$

になり、有効な署名データのs値になる。

# 署名データとしてエンコード
signature = ECDSA::Format::SignatureDerString.encode(ECDSA::Signature.new(r, s))

こうやって生成した(r, s)が、マルチシグをアンロックするための署名。

実際に、最初に作ったアリスとボブのマルチシグ用の公開鍵で署名を検証すると、正しい署名であると判断される。

# 実際にアリスとボブのマルチシグ用の公開鍵で検証
multisig_pubkey = Bitcoin::Key.new(pubkey: ECDSA::Format::PointOctetString.encode(new_key, compression: true).bth)
puts multisig_pubkey.verify(signature, m)

と、こんな感じでECDSAベースのスクリプトレスなマルチシグの検証ができる。一連のスクリプトはこちら。

ECDSAベースなので、既存のBitcoinのプロトコルでそのまま利用可能だ。従来のBitcoinスクリプトを使った2-of-2のマルチシグと比べて、

署名データは約半分になる
ブロックチェーン上のトランザクションを見ても、誰にもマルチシグであることが分からない

といったメリットがある。

※ 実際に使用する場合は、セキュリティパラメータの調整や、お互いの公開鍵、署名に使用するRを共有する際には、相手から送られてきた公開鍵の秘密鍵を確かに相手は持っていることをゼロ知識で証明するようなプロトコルを導入する必要がある。

Develop with pleasure!

福岡でCloudとかBlockchainとか。

Bitcoinスクリプトを使わないマルチシグを書いてみた

ロックスクリプト

アンロック時に使用する署名の作成