PoSでのlong range 攻撃は何%のステークを必要とするか


#1

PoSで攻撃者がチェーン巻き戻し(reorg)による二重支払いをするために、何%のステークによる攻撃ができるのか考えたいと思います。

以下を前提とします
①longest chainが採用され、取引所などで参照される
②slasher等の対策で2重投票はできない
③投票者は目先の利益を追う(全員近々トークンを売却予定である)
④time-clockを使わない、非同期的な承認である

以下を共有知識とします
①timeclockを使わないとブロックから分岐して掘り続けて最長チェーンを狙うlong range攻撃に対して、耐性が下がる。
②blockchainのスナップショットはネットワーク上で一意に定まらないので、ネットワーク分裂修復後の長いチェーンの出現とlongrange攻撃のチェーンの区別はつかない。


#2

“PoS” とだけだと前提としては考慮の余地が広すぎる気がしますね。
ある量のtokenをStakeしたNodeについて,

  1. 誰がブロックを提案できるか?StakeしたNodeすべてが同時にブロックを提案できるのか?あるいはランダムに決めるのか, 順番に決めるのか
  2. 提案されたブロックの承認に何%のStakeによる投票が必要か?あるいは, ここは可変の値として議論するか?
  3. 承認はいつ確定するか? “分散システムにおける非同期” という前提となると, 投票は無限時間遅延し得るので, 最悪の場合, 観測可能な時間内に確定しないことになるが, そこはどういう仮定をとるか?

について前提を決めないと無意味な議論になってしまいそうで心配です。いかがでしょうか?


#3

そうですね、
1)同時に提案が最も低そうですね
timeclocke,stamp使わないので
2)とりあえずよく聞く1/3ですが、これってどういう基準で決められているかソース知ってたりします?
3)承認確定は2)の%をクリアした瞬間でよいかと。承認が続くチェーンの長さを競うのが一般的と理解しています。


#4
  1. 同時に提案できないようにするならば, よくあるのはランダムな値を決めてそれに沿ってブロック提案者を割り当てて行くのかな。あるいはPoWで代替えすることも可能だとおもうし, あらかじめブロック提案者を決めておくことも可能だと思う

  2. 1/3のソースは割と簡単に導きだせる気がしている

ノードの総数を N,
byzantineなノードの数を b ,
許容される最大のbyzantineなノードの数を t (閾値threshold)とおく
honestなノードの数は, 閾値より多くないといけないので
(1) t < N - b
honestなノードの半分がbyzantineな挙動をし始めてもSafety(Protocolに沿わないブロックが承認されないこと)が保たれることを考慮すると
(2) (N - b) / 2 + b < t
(1)と(2)から t を消去すると
(3) (N - b) / 2 + b < N - b
これを解くと
(N - b) / 2 < N - 2 * b
N - b < 2 * N - 4 * b
3 * b < N
b / N < 1/3
したがって, byzantineなノードが許容される割合は1/3以下である

というのでどうですかね?


#5

超わかりやすいです。
この導出や条件が微妙に変わってくるから25〜50%の間でbyzantine耐性意見変わってくるんでしょうね。

これは多分byzantineなチェーンと区別がつかずに承認してしまうケースですね。
byzantineに対抗しているmain-chainが存在してとしてもどちらを承認するかは50-50って仮定という理解です。

おそらく、ここが50-50かどうか、攻撃検知できないか(99%)などが議論されている印象ですが、大口のアクティブノードじゃなくなったらどうするかも含めて、1/3が適当であるかは少し分かりません。
導出の理屈がそのままビザンチン耐性1/3になると考えてますが、合ってますか?(結局チェーンのどちらを支持するかと1つのブロックどちらを承認するかは同じ問題なので)

「同時の提案が一番耐性低そう」って意味でしたが、ランダマイズの場合と同じに思えてきました。ランダマイズによる割当が一番同期性を必要としないので採択されている印象ですが、ここはSkipを考えるとアドレス(提案者)指定でなく、アドレスの集合を指定が妥当と思います。すると同時提案をある程度絞るのと同じ(ワンタイムのDelegateみたいな)ですね。単一アドレスへの割当ってブロック生成遅いと問題ありませんか?


#6

byzantineな挙動というのがどういうものか定義されていませんでしたね

canonicalなchainとそうでないchainで二つあるからその確率は, 50-50だと言う事でしょうか?
私の理解としては, そうではなくて単純に安全率としか言えない仮定なんですよね。。。
選ぶ確率が同様に確からしいとは限らない事象なので, 選択肢が二つあったら50-50という訳ではないかと。
ここの許容されるbyzantineなノードの割合は, 安全率をどう取るかで変わってくるかと思います。
先ほどの例では, 1/2にしましたが, 0から1の間で任意にとることができます。

99%の方は読んでないのでどこかで調べてきます

うーむ, どうせならいろんな場合を考えてみたらいいかもですね

  • ブロックの提案/承認/のラウンドが同期/非同期
  • ブロックの提案者をランダムに一つに決める/ランダムに複数決める/Stakeしたノードが自由に提案できる

同期非同期については, 実際にどのようなものを同期/非同期と呼んでいるかについて厳密に決めた方が良さそうな気がしますね


#7

ブロック生成が遅いだけなら特に問題はない気がします。PoWにしろブロック生成が遅くなることは発生しているし、どれくらい遅くなるかはコントロール不能なので。遅くなるというよりはwithholdされるとchainが死ぬので、投票結果として単一アドレスに採掘権を渡すと問題はありそう。
この辺りを考えると、提案されたブロックに対してどれを採用するかの投票 とする方が諸々の問題を解決できそうにおもいました。


#8

byzantineなチェーンってなんじゃろ・・・・monacoinのreorg攻撃で置き換わった後のチェーンをbyzantineなチェーンとするならこれは判別がそもそも不可能なのでは?protocol上は「正しいチェーン」だからこそreorgが起きるわけで。


#9

多分、timestamp偽造しているチェーンで良いと思います。偽造していないなら、掘る速度が早すぎるので制限かけれるはずです


#10

でもtimestampを偽造しているのかネットワークの遅延によるかはわからないのでは。
それをあるスレッショルドで無視したりするならば, それは非同期ではなく, 一部同期的なプロトコルだと思うのですが, どうなんでしょう?


#11

分からないので、byzantineかどうかは分からず、non-byzantineからすると50-50の賭けになるという話です。

つまり以下の文は「仮に偽造していないことが分かるのであれば」が正しい表現ですね


#12

50-50かは正確には分かりませんが。

同期的であれば、この偽造を除外できますが、ネットワーク分裂に対応できないのでそこはトレードオフですね。