Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

Bitcoin Ruby Scriptless Scripts ECDSA

先日書いた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を共有する際には、相手から送られてきた公開鍵の秘密鍵を確かに相手は持っていることをゼロ知識で証明するようなプロトコルを導入する必要がある。

効率的な二者間のECDSAプロトコル

Bitcoin Scriptless Scripts ECDSA Cryptography

以前、Andrew PoelstraがBitcoinスクリプトを書くことなくスマートコントラクトを実現するScriptless Scriptsについて紹介されていたが、これはいずれもSchnorr署名を必要とする仕組みだった。現在のBitcoinのプロトコルでサポートしているのはECDSAのみであるため、当然ながらSchnorrを必要とするScriptless Scriptsは現在のBitcoinでは使えない。ただ、Scriptless Script以外にもSchnorr署名の鍵や署名の集約機能によりトランザクションサイズを削減したり、さまざまなコントラクトへ応用が効くことからSchnorrの導入をしようという流れではある。

そんな中、先日LightningのMLにScriptless ScriptをSchnorrの代わりにECDSAを使って行う方法がポストされた。

[Lightning-dev] Scriptless Scripts with ECDSA

ホワイトペーパー「Scriptless Scripts with ECDSA」も添付されてる↓

https://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180426/fe978423/attachment-0001.pdf

このECDSAでScriptless Scriptを実現するためにベースとなったのが、イスラエルのバル＝イラン大学のYehuda Lindellが2017年に公開した以下のホワイトペーパーだ。

https://eprint.iacr.org/2017/552.pdf

この内容について「Scriptless Scripts with ECDSA」のペーパーで簡単に説明されてたので見てみる（本家のは長かったので時間ができたら読む）。

ECDSA署名について

まずECDSAの署名方式について。アリスが秘密鍵 x とそれに対応する公開鍵 {g^{x}} を持ち、その鍵を使ってメッセージ m に署名したい場合、アリスはメッセージ m に対して以下のように署名を計算する。

  1. ランダム値 k を選択する。
  2. {R = g^{k}}を計算する。
  3. 計算したRの点を {(r_x, r_y)}とし、 {r = r_x}とする。つまりrは点Rのx座標。
  4. 署名 {s = k^{-1} \cdot (LSB(H(m)) + r \cdot x)}を計算する。ここでLSBは最下位bitの関数を表し、Hはハッシュ関数を表す。
  5. 署名の出力は(r, s)

効率的な二者間のECDSAプロトコル

ECDSAの主な課題の１つは効率的な2-of-2の署名プロトコルを設計することだった。最近Yehuda Lindellがこのプロトコルの効率的な構成ついて論文を発表した。ECDSAベースのScriptless Scriptsの提案はLindellのプロトコルの延長にあたるので、ここでそれについて説明する。より詳細な説明とセキュリティ分析についてオリジナルの論文を読むことを勧める。

アリスは公開鍵 {P_1 = g^{x_1}}とナンス {R_1 = g^{r_1}}を、ボブは公開鍵 {P_2 = g^{x_2}}とナンス {R_2 = g^{r_2}}をそれぞれ持つ。最後にアリスはボブにckey = Enc {pk_A} (x1)を提供する。これはアリスのみが解読可能なx1のPaillier暗号だ。このアリスとボブの2-of-2のマルチシグは以下のように動作する。

  1. アリスとボブは、P1、P2、R1、R2とm'について合意する。ここでm'はLSB(H(m))。また、アリスとボブは安全のためP1、P2、R1、R2についてその秘密鍵を確かに持っていことを証明するための非対話型のゼロ知識を追加で交換する必要がある。これはこの後で提案されるプロトコルにおいても同様の基本的な手順として組み込まれているが、読みやすさを優先して省略する。
  2. アリスは {R \gets (R_2)^{r1}}を計算し、ボブは {R \gets (R_1)^{r2}}を計算する。それぞれ計算したRから同じx座標 {r = r_x}を計算することができる。
  3. ボブは {c_1 \gets Enc_{pk_A}((k_2)^{-1} \cdot m' + \rho q)}と {c_2 = (ckey) \odot (x_2 \cdot r \cdot (k_2)^{-1})}を計算する。ここで {\rho}は巨大な乱数を表し、qは暗号操作中に使用される剰余を表す。続いてボブは {c_3 = c_1 \oplus c_2}を計算する。この {\oplus}はPaillier暗号の加法準同型演算を表す。 したがって
{c_3 = Enc_{pk_A} ((k_2)^{-1} \cdot m' + \rho q + x_1 \cdot x_2 \cdot r \cdot (k_2)^{-1})}

となる。 {c_3}は言わば、ボブからのpre-signatureを暗号化したものになる。最後にボブはアリスに {c_3}を送る。

4.アリスは {c_3}を復号して、s'を得る。続いて {s \gets s' \cdot (k_1)^{-1}}を計算し、(r, s)をECDSA署名のアウトプットとする。

悪意あるボブはプロトコルから逸脱して任意の値を暗号化する可能性があるが、アリスはペア(r, s)が公開鍵Qのもとで有効なECDSA署名であることを検証することで、ボブが正しく振る舞ったかどうか判断することができる。正しくない場合アリスはプロトコルを中止することができる。

というのがホワイトペーパーに記載されている内容で、マルチシグスクリプトを構成することなくマルチシグ的なことができるようになってる。この二者間のECDSAプロトコルをベースにしているのがECDSA版のScriptless Scripts。（スクリプトレスなマルチシグという意味では↑もScriptless Scriptsと言えるだろう。）

途中で急にk1、k2が出てきてるけど、これは単なる書き間違いでr1、r2のことを指してるんだと思う。

ポイント

基本的にはECDSAの署名形式に沿ってないといけないので、アリスとボブによる署名データは乱数kから生成した点Rのx座標と、 {s = k^{-1} \cdot (LSB(H(m)) + r \cdot x)}で計算される(r, s)のペアである必要がある。

通常は１人で作る署名だけど、２つの鍵を使った2-of-2のマルチシグ的な用途のECDSA署名を↑のプロトコルで可能にしているポイントは以下の２つだと思う。

Rの計算

↑のプロトコルではまず署名に使用する点Rの算出方法が変わっていて、アリスがランダムに生成した点R1とボブがランダムに生成した点R2をそれぞれ共有し、その点に自分の点の秘密鍵を乗算して新しい点を計算している。アリスの場合はk1 * R2、ボブの場合はk2 * R1。こうして出来た点Rは同じ点を指す。

この点をECDSAの署名に使う場合、計算した点Rのx座標が署名データの１つのrになり、sを計算する際は、 {s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x)}となる。

秘密鍵を使ったsの計算

もう１つのポイントは、署名データ {s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x)}を計算する際の秘密鍵xの部分だけど、ここがアリスの秘密鍵x1とボブの秘密鍵x2をそれぞれ使って計算するようになるので、結果的にsは、 {s = (k1 \cdot k2)^{-1} \cdot (LSB(H(m)) + r \cdot x1 \cdot x2)}になる。

当然両者が自分の持つ秘密鍵x1とx2を明らかにすることはないので、お互い相手の秘密鍵を知らないままsを計算するために、加法準同型性のあるPaillier暗号を使ってるんだと思う。

アリスはPaillier暗号の鍵ペアを生成し、公開鍵をボブに送っておく。自分の秘密鍵x1を公開鍵を使って暗号化しボブに送る（これがckey）。その後ボブは送ってもらったアリスの公開鍵を使って↑c1を計算し暗号化する。さらにckeyを使ってc2を計算し、Pailier暗号の加法特性を利用してc3を導出し、アリスに送る。アリスはPaillier暗号の自分の秘密鍵を使ってc3を復号すると、

{(k_2)^{-1} \cdot m' + \rho q + x_1 \cdot x_2 \cdot r \cdot (k_2)^{-1}}
{(k_2)^{-1} \cdot (m' + x_1 \cdot x_2 \cdot r ) + \rho q}

が手に入るので、それに {k^{-1}}を掛けると

{(k1 \cdot k_2)^{-1} \cdot (m' + x_1 \cdot x_2 \cdot r ) + \rho q}

とお互いの秘密鍵x1、x2を使って計算されたどこかてみた形のsが入手できるようになるっぽい( {\rho q}は最終的にmod qして消える)。いやー、よく考えるなー。

個人的に {\rho q}の意図がイマイチよく分かってないのと、セキュリティ周りなどちゃんと確認するにはオリジナルのホワイトペーパーの方読んだ方が良いんだろうなー。

参考

Pailier暗号については↓のサイトが分かりやすかった。

elliptic-shiho.hatenablog.com

Adaptor Signatureの計算をRubyで書いてみた

Bitcoin Ruby Scriptless Scripts

Andrew Poelstraが発表したScriptless Scriptsとその応用であるAdaptor Signatureについて実際に計算部分をRubyで計算してみた。

前提となるSchnorr署名

Andrew PoelstraのScriptless ScriptsはSchnorr署名が前提となるので、まずその公式について。

秘密鍵をx、署名対象のメッセージをm、署名時に選択するランダム値をrとする。xとrの公開鍵をそれぞれP = xG、R = rGとする。

sG = R + H(P || R || m)P

を満たす、(s, R)が有効な署名。ECDSAに比べてシンプルね。

2-of-2のAdaptor Signature

続いて、Schnorrを使ったAdaptor Signatureについて。

アリスが鍵ペアPA = xa GとランダムなナンスRA = ra G、ボブが鍵ペアPB = ba GとランダムなナンスRB = rb Gを持っている場合、Adaptor Signatureは以下のようにして作成する。

  1. アリスはランダム値tを選択し、T = tGを計算する。
  2. アリスとボブはそれぞれPA、PB、RA、RBを共有し、アリスはボブにTを送る。
  3. アリスとボブはそれぞれe = H(J(A, B) || RA + RB + T || m)を計算する。
  4. アリスはAdaptor Signature s' = ra + e * xaを計算し、ボブに送る。
  5. ボブはアリスから受け取ったs'についてs'G == RA + ePAが成立するか検証する。
  6. 5が成立する場合、ボブはsB = rb + e * xbを計算し、アリスに送る。
  7. アリスはsA = ra + t + e * xaを計算し、s = sA + sBを計算しブロードキャストする。
  8. ボブはs - sB - s' = (ra + t + e * xa) - (ra + e * xa) = tを計算して、tの値を知る。

※ J(A, B)はアリスとボブの鍵を集約したもの。

これをRubyで（bitcoinrb使って）書くと↓な感じになる。シンプルに書いたので省略してるけど、実際に使用する場合は曲線の位数を使って剰余をとる必要がある。

require 'bitcoin'

# 署名対象のメッセージ
m = 'message'

# [Alice]アリスの鍵
alice_key = Bitcoin::Key.generate
PA = alice_key.to_point
ra = 1 + SecureRandom.random_number(ECDSA::Group::Secp256k1.order - 1)
RA = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(ra)

# [Bob]ボブの鍵
bob_key = Bitcoin::Key.generate
PB = bob_key.to_point
rb = 1 + SecureRandom.random_number(ECDSA::Group::Secp256k1.order - 1)
RB = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(rb)

# PA,RA,PB,RB,mは共有

# [Alice]STEP1, アリスはランダム値tから T=tGを計算
t = 1 + SecureRandom.random_number(ECDSA::Group::Secp256k1.order - 1)
T = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(t)

# [Alice]STEP2, アリスはボブにTを送る。

# [Alice][Bob]STEP3, アリスとボブ共にeを計算
J = ECDSA::Format::PointOctetString.encode(PA + PB, compression: true)
e = Bitcoin.sha256((J + ECDSA::Format::PointOctetString.encode(RA + RB + T, compression: true) + m).htb).to_i(16)

# [Alice]STEP4, アリスはAdaptor Signature s' = ra + e * xa を計算してボブに送る
s_dash = ra + e * alice_key.priv_key.to_i(16)

# [Bob]STEP5, ボブはs'G == RA + ePAを検証
verify = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(s_dash) == (RA + PA.multiply_by_scalar(e))
puts verify

# [Bob]STEP6, sB = rb + e * xbを計算してアリスに送る。
sB = rb + e * bob_key.priv_key.to_i(16)

# [Alice]STEP7, アリスは s = sA + sBを計算し、ブロードキャストする。
sA = ra + t + e * alice_key.priv_key.to_i(16)
s = sA + sB

# [Bob]STEP8, t = s -sB - s' = (ra + t + e * xa) - (ra + e * xa)を求める。
puts t == s - sB -s_dash # アリスが最初に作ったtと一致する。

これをクロスチェーンのAtomic Swapなんかに利用する場合、各チェーン毎にキーペア（PA1、PB1、PA2、PB2）があり、トランザクションもそれぞれ異なるので、mもm1、m2の２つになる。またアリスが生成するAdaptor Signatureもチェーン毎に２つ必要で、上記のステップ３〜６を両方のチェーン分で行うことになる。ステップ７のアリスがブロードキャストするのは片方のチェーンのみで、そのチェーンの署名データsを見て、ボブはステップ８のtの計算をする。

そのtと予めアリスからもらっていたAdaptor Signatureを使って自分が貰う方のコインのチェーンの償還トランザクションのアリス分の署名を作成し、自分の署名と組み合わせて署名データsを作成する。

大まかな流れは以前書いた↓参照。

techmedia-think.hatenablog.com

LNの強化：コントラクト違反時の防衛強化とSigned Sequence Commitment

Bitcoin Lightning network

Lightning Networkのセキュリティ強化およびクライアントをよりスケーラブルにするための強化案について@roasbeef ‏がBPASE 2018で発表した内容↓（スライド 、トランスクリプト）について見てみる。

www.youtube.com

トピックとしては

  • コントラクトの違反が発生した場合の防衛強化
  • LNクライアントの履歴データの削減
  • Covenantsを利用したHTLCの改善
  • マルチパーティチャネル
  • 手数料のコントロール

まずこの内の先頭２つについて、どういうものかまとめてみた。

コントラクトの違反が発生した場合の防衛戦略の強化

LNのコミットメントトランザクションには古いトランザクションをブロードキャストする不正が行われた場合に、不正を行った相手の資金を没収するトランザクションを作成しブロードキャストすることができる。このため、不正を働くインセンティブをなくしている。

この仕組みは、コミットメントトランザクションをブロードキャストした際に、ブロードキャストした側がコインを入手するには、そのトランザクションがブロックに格納されて指定ブロック数待つ必要があり、その間にそのコミットメントトランザクションを作成した際に使用したシークレットが分かれば相手がそのコインを入手できるというコントラクトによって成立している。

この場合、不正を働かれたユーザーは、古いコミットメントトランザクションがブロックに格納されてから指定ブロック数までの間に資金を取り戻すトランザクションをブロードキャストし、ブロックに入れられなければならない。ただメモリプールのトランザクションがいっぱいで混雑している場合、必ずしも資金を取り戻すためのトランザクションが先にブロックに入るという保証はなく、ひょっとすると指定されたタイムロック期間までにブロックに入ることなく不正を働いた側のトランザクションが先にブロックに入ってしまうという可能性も考えられなくはない。

↑のプレゼンテーションで@roasbeefが提案してるのは、こういうケースの防衛のため、不正を働いたユーザーのコインを取引相手が没収するのではなく、不正を働いたユーザーの残高をそっくりそのままマイナーへの手数料へ加えてしまおうという提案。

誰かが古い状態のコミットメントトランザクションをブロードキャストしようとすると、トランザクションはその特定の状態にロックされる。例えば、ボブの最新の残高は$2で、以前の残高が$10だったとして、ボブは$10の状態に戻そうとする場合。取引相手は古い自分の残高についてはすぐに入手でき、ボブはトランザクションがブロックに格納されてから指定されたブロック分待つと$10入手できる。ただこれは不正行為なので、取引相手はシークレットを使って$10のアウトプットをすぐに入手しようと試みる。この時タイムロックはされているとはいえ、ボブより早く取引相手の作ったトランザクションがブロックに取り込まれる必要がある。問題となるケースは、ブロックが混雑していて、取引相手の作成したトランザクションがなかなかブロックに入れられずタイムロックの期間が過ぎてしまうようなケースだ。この場合取引相手が取る戦略として、$10のアウトプットのボブの取り分をマイナーへの手数料へ回す。実際に前の状態のコミットメントトランザクションをブロックに入れることにボブが成功する唯一のケースは、ブロックが混雑していて、取引相手がボブの残高をそのまま手数料にするのを考慮すると、ボブの残高より高い手数料をマイナーに支払う場合になる。これはボブにとって何の得にもならないケースだ。このため、例え大量にトランザクションが詰まっていたとしてもマイナーがより高い手数料を求める傾向があれば、ボブは何も手にすることはなくなるだろうと。

各クライアントの履歴データの削減

LNでチャネルをオープンしオフチェーン決済をする際は、毎回オンチェーン上のマルチシグにロックした資金の残高を決済額に応じて更新するコミットメントトランザクションを作成し、前に作成したコミットメントがブロードキャストされないよう、前のコミットメントトランザクションのシークレットを交換するステップを踏む。チャネルをクローズする際はチャネルの最終残高を二者のアドレスに送付するクロージングトランザクションを協力して作成するため、このコミットメントトランザクションがブロードキャストされることはない。コミットメントトランザクションがブロードキャストされるケースは、相手と連絡がつかなくなった場合で、その時チャネルをクローズするのに使われる。

また相手が自分に有利な過去のコミットメントトランザクションをブロードキャストしようとする不正を働くケースに対応するため、交換したシークレットや相手の署名データは全て保存しておかなければならない。

現在、古い状態のトランザクションを取り消すのに使っているのがRevocation Keyを使うアプローチ↓

techmedia-think.hatenablog.com

オフチェーン決済によって高速で安価に決済ができるようになるのはLNメリットで、効率的な意味でもそういったペイメントチャネルのライフタイムが長くなることが望ましいが、その分、ローカルで各決済の状態遷移をずっと管理しておく必要があり、決済の数に比例してストレージコストも増える。そこでコミットメントの無効化の仕組みを改善しようというのが今回の提案↓

Signed Sequence Commitment

今回提案されている新しいコミットメントの無効化の方法がSigned Sequence Commitmentと呼ばれる方法。

今までの無効化のアプローチは、状態を更新する（オフチェーン決済をする）際に前のコミットメントトランザクションで使用していたRevocation Keyを相手に明らかにする方法をとっていたけど、Signed Sequence Commitmentでは

  • 各状態（オフチェーン決済）にステートナンバーを割り当てる。
  • ステートナンバーにコミットするコミットメントを作成する。

状態を更新する（新しい決済をする）際には、以下の処理を行う。

  1. 前の状態のコミットメントを開く。
  2. コミットメントを（今までのRevocation Keyの代わり）に、新しいオフチェーン決済トランザクションのアウトプットスクリプトに入れる。
  3. ステートナンバーをインクリメントした新しいコミットメントを作成する。
  4. 生成した新しいコミットメントに両者の鍵で署名をする（この時の署名は集約署名にするみたい。具体的な署名形式は話されてない。）

取引相手が不正をして前の状態のトランザクションをブロードキャストした場合は、そのトランザクションのステートナンバーより、大きなステートナンバーへのコミットメントの有効な署名を提供することで（Revocation Keyの代わりに）、相手の資金を入手できるようにする。

Signed Sequence Commitmentでは、最新のステートナンバーへのコミットメントの有効な署名があれば、過去の状態のどんなコミットメントトランザクションがブロードキャストされても、その署名のみで不正を無効化することができるようになる。これにより、今まで過去の決済数分のRevocation Keyをローカルストレージに保持しなければならなかったのが、最新の署名データのみをローカルストレージに保存しておけばよくなる。

ただ、これを実現するためには、ステートナンバーへのコミットメントに対する署名検証（任意のデータに対する署名検証）が必要になる。現在Bitcoinには任意のデータに対する署名検証を行うopcodeは無いので、↑のスライドでも紹介されているOP_CHECKSIGFROMSTACK*1が必要になり、そのスクリプトの導入を提案している。

LNに限らず、外部オラクルを利用したコントラクトの作成もできるので、任意のデータに対して署名検証する仕組みは欲しいなー。

*1:Blockstreamが提供するサイドチェーンElementsで実装されている、スタック上のアイテム（公開鍵、メッセージ、署名データ）の署名検証をするopcode。

Compact Blockとは異なる方法でブロックアナウンス時のトランザクションの重複を解消するプロトコル「Graphene」

Bitcoin

昨年スタンフォードで開催されたScaling Bitcoin 2017のBrian N. Levineのセッションで発表されてたのが効率的なブロック伝播のためのプロトコルGraphene↓

www.youtube.com

時間が空いたけど、どういうプロトコルなのかホワイトペーパーを読んでみた↓（珍しく短めのペーパーで読みやすい）。

http://forensics.cs.umass.edu/graphene/graphene-short.pdf

コンセプトはBIP-152のCompact Blockと同じだ。新しいブロックをアナウンスする際に、既存のblockメッセージを使って伝播すると、そのペイロードにはブロックに含まれる全トランザクションが入ってる。ただ、ブロックに入っている（コインベースを除く）ほとんどのトランザクションは、既にほとんどのピアがメモリプール内に持っているものなので、blockメッセージのペイロードとして受け取ると二重にトランザクションのデータを受け取ることになり無駄が生じる。

BIP-152として現在のBitcoin Coreで実装されているCompact Blockでは、blockメッセージを使わずに、ブロックヘッダと短縮したTXID（6バイト）のリストを使ってブロックを通知し、受信側のピアが自身のメモリプール内に持っていないトランザクションがあればそれを要求する方法を取り、既に持っているトランザクションデータについては送られてこないようにしている。詳細は↓

techmedia-think.hatenablog.com

Grapheneもこのトランザクションの重複を解消するためのプロトコルで、Compact Blockの場合はブロック内のトランザクションリストの短縮TXIDを使用してブロックに入っているトランザクションの情報を相手のピアに伝えるという方法を取っているが、Grapheneでは代わりにBloom FilterとIBLT（Invertible bloom lookup tables）を利用している。具体的には以下のステップで新しいブロックをアナウンスする。

  1. 新しいブロックの送信者はそのブロックの存在をinvメッセージを使って受信側のピアに伝える（このプロセスは今までと変わらない）。
  2. 受信側のピアはinvのブロックハッシュを確認し、自分がまだ受け取っていないブロックなら、相手にそのブロックを要求する。
  3. 送信側のピアは、ブロック内の全トランザクションのTXIDを要素にしてBloom FilterとIBLT I 作成し、ブロックヘッダと合わせて受信側ピアに送信する。
  4. 受信側のピアはメモリプール内の全トランザクションのTXIDを受信したBloom Filterにかけ、ブロックに含まれている可能性があるTXIDをピックアップし、ピックアップしたTXIDを使って受信者のIBLT I' を作成する。
  5. 受信側のピアは生成した I' と送信者から受け取った Iの差分を計算し、ブロックに含まれるTXIDをデコードする。

※ IBLTは、key-valueペアの挿大、削除、検索、リストアップをサポートしている確率的なデータ構造で、Bloom Filterと同様Bitcoin特有の技術ではない。

両者が作成するIBLTの各セルは以下の値を持っている。

  • count（2バイト）
  • hash値（4バイト）
  • value（TXIDのラスト5バイト）

Bloom Filterには偽陽性があるため、フィルタにかけた結果合致する可能性があると判断されたTXIDも実はブロックに含まれていない可能性がある。このためBloom Filter単体ではブロックに含まれているトランザクションを確定することはできず、あくまで可能性があるトランザクションのリストをピックアップするだけ。IBLTは差分を取れるので、Bloom Filterを使って受信側が作ったIBLTと送信者が作成したIBLTの差分を取ることで、Bloom Filterでピックアップしたトランザクションリストの中から実際のブロックには含まれていないものを除外したリストを作成できるという仕組みっぽい。

Compact Blockとは異なりBloom FilterとIBLTにより確率的にブロックに含まれるトランザクションリストを判断するのがGrapheneの仕組みみで、その際Compact Blockの短縮TXIDよりも小さいデータサイズで済むと。

ただ基本的に実現していることはCompact Blockと同様、トランザクションの二重伝播の無駄をなくすということなので、Graphene単体でビッグブロックを劇的にスケールするような仕組みではない。Compact Blockの短縮TXIDよりもデータ効率は良いが、そのデータサイズも2000トランザクション持つブロック当たり、7,8KBぐらいの差なのでそこ単体を追求してもパフォーマンスの劇的な改善は見込めない。ただ、ブロックサイズが増えるとCompact Blockの場合、短縮TXIDのデータはリニアに増えるけど、Grapheneの場合はBloom FilterとIBLTのサイズはリニアには増えないので、（既存の1MBのBTCでは既にCompact Blockでトランザクションの重複は排除済でそんなに効果ないけど）ビッグブロックを前提とした選択肢としての採用はありだと思う。

以下、ホワイトペーパーの日本語訳。

イントロダクション

我々はGrapheneと呼ばれる新しいブロックのアナウンス方法を提案する。この文書は、これまでに発表されているものに追加の実験を加えたGrapheneのより詳細な説明をまとめたものだ。

Grapheneのブロックは、Compact BlockやXtreme Thinblock関連の方法の一部だ。例えば、以下の詳細な例では、17.5 KBのXtreme ThinblockはCompact Blockでエンコードすると10 KBで、Grapheneでエンコードすると2.5 KBになる。シミュレーションでは、GrapheneのエンコードはCompact Blockの約10%のスペースでエンコードできることが分かった。我々はBloom FilterとInvertible bloom lookup tables (IBLTs)の新しいインタラクティブな組み合わせを使って、BitcoinのP2Pネットワークにおける調整の問題に対する効率的なソリューションを提供する。

ブロックの通知は、ブロックを構成するトランザクションを使って検証される。しかし大多数のピアは既にそのトランザクションを受信しており、メモリプール内のトランザクションと識別するだけでいい。原則としてブロックの通知にはそのTXIDのみを含める必要がある。例えばCoralloのCompact Blockの設計ではトランザクションIDのリストを含めることで通知するブロックのサイズを大幅に削減しているが、ピア間の調整コストが増える。Xtreme Thinblockは、Compact Blockと同じように機能するが、データのオーバーヘッドが大きい。具体的には、受信者のメモリプールに無いブロックに対してinvメッセージが送信されると、受信者は持っていないブロックの要求と一緒にIDpoolのBloom Filterをを送信する。その結果、Xtreme ThinblockはCompact Blockよりも大きくなる。コミュニティはブロックの通知を減らすために（Bloom Filterを使用しない）IBLTsの使用について議論してきたが、そのスキームは正式に評価はされておらず、我々のアプローチより効率が悪い。我々の方法は新しいものだ。Compact BlockやXtreme Thinkblockよりも小さく、送信者と受信者の間で3つのメッセージのやりとり（inv、getdata、response）が必要なことを実証した。

Grapheneプロトコル

f:id:techmedia-think:20180413111759p:plain
Figure 1：Grapheneプロトコルのサマリ

他のアプローチと異なり、GrapheneはトランザクションIDの明示的なリストを送信しない。代わりに、小さなBloom Filterととても小さなIBLTを送信する。Grapheneの背景は以下の通りで、Figure 1に概要を示している。

送信者はブロック内のトランザクションIDのリストからIBLT I を作成する。また受信者が同じ（もしくは同様の）IBLTを作成できるように、送信者はブロック内のトランザクションのBloom Filter S を作成する。受信者はSを使って、受信したトランザクションIDのプール（IDpoolと呼ぶ）からフィルタにマッチするものをピックアップし受信者のIBLT I' を作成する。受信者は I' を使って I のデコードを試みる。デコードに成功するとブロックを構成するトランザクションIDが返される。Sに含まれる可能性があると誤って判断され I' に追加されたトランザクションの数は、送信者によって管理されるパラメータによって決定される。このパラメータを使うと、とても高い確率でデコード可能な I を送信者は作成することができる。

まとめると、送信者が作成するBloom Filterは、受信者が自身のメモリプール内のどのトランザクションがブロックにあるか決めるのに使われる。他のアプローチでは、偽陽性率と非常に低くするため大きなBloom Filterを使っているが、Grapheneの偽陽性率は高く、IBLTがその間違いを修正する。同様にIBLTのみを使うケースでは、我々の２つの仕組みを使うケースよりもはるかに大きくなる。

Bloom Filterはy個のアイテムを表すx bitの配列だ。最初にxビットはクリアされている状態で、アイテムがフィルタに追加されるたびに、k個のハッシュ関数を使って選択されたkビットがビット列にセットされる。フィルタに必要なビット数は {x = y \frac{-ln(f)}{ln^{2} (2)}}で、fは意図する偽陽性率。Grapheneの場合、 {f = \frac{a}{m - n}}を使用する（ここでaは I と I' の期待差）。Bloom Filterにはn個のエントリーがあり、バイトに変換する必要があるので、そのサイズは {\frac{-ln(\frac{a}{m-n})}{ln^{2}(2)} \frac{1}{8}}になる。またaがIBLTサイズの主要なパラメータであるケースもある。I のセルの数が I のエントリーリストと I' のエントリーリストとの間の予想対称差がd倍の場合、非常に高い確率でIBLT I は I' でデコードできる。我々のケースでは、期待差はaで、d = 1.5で設定する。

IBLTの各セルは、カウント、ハッシュ値および保存された値を持つ（鍵を持つことも可能だが、必要無い）。我々の場合、カウントフィールドは2バイトで、ハッシュ値は4バイト、値はトランザクションIDのラスト5バイト（衝突を防ぐのに十分なサイズ）。まとめると、エントリーの対称差があるIBLTのサイズは、1.5(2 + 4 + 5)a = 16.5a バイトとなる。したがってBloom FilterとIBLTの合計コスト（サイズ）Tは

{T(a) = n \frac{-ln(f)}{c} + aτ = n \frac{-ln(\frac{a}{m−µ})}{c} + aτ }

となる。全てのBloom Filterの定数を {c = 8 ln^{2}(2)}としてグループ化し、IBLTエントリーのオーバーヘッドを定数τ = 16.5とする。

Bloom Filterを可能な限り小さく設定するには、フィルタの偽陽性率を許可されている限り高くなるようにする必要がある。すべてのinvメッセージがブロックの前に送信済みであると仮定した場合、受信者はすべてのトランザクションをIDpool内に既に持っていることが分かっている（メモリプール内にある必要はない）。したがって、µ = n。すなわちブロック内の全てのトランザクションはフィルタを通過することが保証されているので、m - n個のトランザクションが誤検出になることを許容する。さらに、

{T(a) = n \frac{-ln(\frac{a}{m-n})}{c} +aτ }　（1）

aについて導関数をとる式（1）は、a = n/(cτ )の時、最小になる。

Bloom FilterとIBLTの実際の実装にはいくつかの天井関数が含まれているため、以下のように書き直せる。

{T(a) = \bigg( \lceil ln (\frac{m-n}{a}) \rceil \lceil \frac{n ln(\frac{m-n}{a})}{\lceil ln(\frac{m-n}{a}) \rceil ln^{2}(2)} \rceil \bigg) \frac{1}{8} + \lceil a \rceil τ}　（2）

式（2）の最適値は、簡単なループで見つけることができる。実際には、aの最小値を見つけるループ検索はほとんどコストがかからず、シミュレーションでそれを行う。

IBLTのランダム化特性のため、デコードに失敗する可能性は非常に低いがゼロではない。その場合、送信者はセル数を2倍にしたIBLT（これでも非常に小さい）を再送信する。実際のIBLTとBloom Filterのエンコードの我々のシミュレーションでは、この倍増は非常に少数の失敗したIBLTにとって十分なものだった。

他のアプローチとの比較

我々はGrapheneがCompact Blockに比べて厳密に効果的であると前述したが、説明のためここで例を示す。

m = 4000 のトランザクションのIDPoolを持つ受信者は、n = 2000 のトランザクションを持つ新しいブロックを要求する。コストを最小化するaの値は、a = n/(cτ ) = 31.5である。送信者は偽陽性率 f = a m−n = 31.5/2000 = 0.01577でトータルサイズ2000 × −ln(0.01577) c = 2.1 KBのBloom Filter Sを作成する。送信者はまた、合計16.5a = 521バイトのセルを持つIBLTも作成する。まとめると、合計2160B+521B = 2.6 KBがネットワークを介して送信される。受信者は同じサイズのIBLTを作成し、Eppsteinらが紹介した技術を使って、デコードの前にIBLTをもう一方から減算する。比較すると、n個のトランザクションが含まれるブロックについて、Compact Blockのコストは2000 × 5B = 10 KBで、Grapheneの3倍以上のコストがかかる。

またXtreme Thinblockは、全てのIDとBloom Filterを含んでいるため、Compact Blockよりも確実に大きく、GrapheneはXtreme Thinblockよりも厳密に優れている。

シミュレーション

f:id:techmedia-think:20180413185239p:plain
Figure 2：GrapheneとCompact Blockの比較。

Figure 2はCompact BlockとGrapheneのシミュレーション結果を示している。各試行ではブロックサイズとメモリプールのサイズをインプットとして取る。そして各プロトコルが実行され、必要とされたバイト数が記録される。Bloom FiltreとIBLTは確率的な仕組みなので、シミュレーションでは実際のデータ構造を使い、結果が正確であることを保証する。プロット上の各点は、その時点での何百ものシミュレーションの平均。エラーバーは小さすぎて表示できてない。

図から分かるようにGrapheneはメモリプールのサイズに応じてCompact Blockの1/10以下のコストになる。Grapheneのサイズはメモリプールのサイズに依存するが、その成長は非常に遅い。

順序付けられたブロック

Grapheneはブロック内のトランザクションの順序については何も指定していないが、代わりにトランザクションをID順にソートすること前提としている。Bitcoinは、あるトランザクションがブロック内の別のトランザクションに依存している場合、依存しているトランザクションは依存先の後に配置される必要がある。ただ標準的な順序付けは簡単に指定できる。マイナーがある特定の方法でトランザクションを並べたい場合（例えばASIC Boostのような）、そのオーダリングはIBLTと一緒に送られる。n個の要素があるブロックで、ワーストケースの場合、リストは {n \log{2}(n)}ビット長くなる。その余分なデータがあったとしても、GrapheneのアプローチはCompact Blockよりはるかに効率的だ。上記の例で、Grapheneが順序付けをする場合、追加のコストはn = 2000 トランザクションで、 {n \log{2}(n) bits = 2000 \times \log{2}(2000) bits = 2.74 KB}になる。この結果Grapheneのコストは5.34 KBになるが、まだCompact Blockの半分だ。