Ethereum Casper — fork choice rule 之GHOST 與 RPJ
本篇在介紹Casper FFG POS鏈，鏈分叉的解決方法
在POW的世界中，就是比挖礦速度來決定最長鏈，那POS勒?! 怎麼解決分叉的問題？怎麼確認哪條分叉是有效的鏈？如果有一小群attackers ，假造了一堆block，變成最長的鏈，大家就傻傻的follow嗎?!
Casper FFG 一開始選用GHOST(Greedy Heaviest-Observed Sub-Tree) 作為選擇有效鏈的方式。GHOST原則上就是選總分最高的那條鏈當作有效鏈（在Casper FFG中，選擇最多人投票的鏈當作主鏈，而不是最長的當主鏈，所以這邊都是寫有效鏈，而不是最長鏈），下面是一個例子
最上面黃色的是最新被確認(finalized)的block，綠色的(I J)是鏈的head，每個區塊上的字母，代表簽章的人
- C沒有被選擇，是因為B的簽章數比C多
- F沒有被選擇，是因為(G H)的簽章數是5(G,H,I,J,M)，而F只有3(F,K,L)
- (I J)簽章數是2，多於M(1個)，所以最後選定是 (I J) 這個區塊
GHOST選定有效鏈方式大概就這樣，還滿直覺的。
前幾週，基於GHOST選鏈的方式作了一些小修改，提出新的方式叫做RPJ（Recursive Proximity to Justification）。GHOST是票數多的當選，而RPJ是比最大值，也就是取每條分叉上的最大值，擁有最大值的那條鏈即為有效鏈。
以這個鏈為例，黃色分鏈最大值為51，綠色分鏈最大值為65，所以綠色鏈會被選為主鏈，就這樣（講完覺得有點空虛….XD）。為什麼會改用RPJ？這個方式的概念是，如果某個block被證明是合法的(justified)，這隱含了這個block的祖先們也被證明是合法的，所以一個區塊 justified 的機率會是其子孫區塊中最接近 justified 的機率（這邊感謝NIC Lin的糾正，下方會附上NIC LIN comment的原文）。
原文在這裡（英文不夠好，所以這裡附上原文）
The philosophy here is that if a block is justified, that implicitly justifies its ancestors as well, so the proximity of a block to being justified is really the minimum of the proximities of any of its descendants.
NIC Lin的comment，直接引用原文
這邊原文寫錯了，是 maximum of the proximities of any of its descendants。 一個區塊 justified 隱含其區塊的祖先 justified 的意思，所以一個區塊 justified 的機率會是其子孫區塊中最接近 justified 的機率。
然而，這個方式也不是沒缺點，RPJ適用於跨epoch的選擇，但是在每個epoch內，依然需要另一種fork choice rule去選擇，但是有兩種fork choice rule不是個好主意，會缺少了stability。所以目前載往epoch-less的方向走（謝謝 NIC Lin 的補充）。
reference:
https://ethresear.ch/t/attestation-committee-based-full-pos-chains-version-2/2427
https://ethresear.ch/t/recursive-proximity-to-justification-as-ffg-fork-choice-rule/2561
https://ethresear.ch/t/pos-fork-choice-rule-desiderata/2636
https://ethresear.ch/t/epoch-less-casper-ffg-liveness-safety-argument/2702
Originally published at kimiwublog.blogspot.com.
