Ethereum Casper - fork choice rule 之GHOST 與 RPJ


UPDATE : 
文中的RPJ在8/16之後被改為IMD(Immediate message driven)
「2018.08.16: I am from now on going to use “immediate message driven GHOST” to refer to what I previously referred to as “recursive proximity to justification” or “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的祖先們也被證明是合法的,所以後代可以基於這個blocks被justify的機率是高的。
原文在這裡
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. 
然而,這個方式也不是沒缺點,RPJ缺少了stability。以上面的例子來說,如果黃色的分鏈其他的validator繼續投票,有效分鏈就會變成黃色鏈了。不過Vitalik也提到,如果是在每個block都做justification,而不只是check point,就可以解決stability這個問題,不過這個提議或許還需要社群作討論才會有結論,就先知道就好。


reference: 
https://ethresear.ch/t/attestation-committee-based-full-pos-chains-version-2/2427

留言

這個網誌中的熱門文章

瑞士滑雪分享2 - 策馬特

What's New in Ethereum Serenity (2.0)

動手實做零知識 - circom