Kimi的筆記

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...

最近重新追了一下Ethereum Casper的進展，發現到好多新東西（應該是之前看得太表面 ＸＤ），Casper跟sharding會綁一起，然後又有個beacon chain，zk-STARK（zk-SNARK的升級版）也來湊一腳，短時間有點難消化，有興趣的人可以google上面幾個keyword。 不過，今天想要介紹的是BLS signature（這又是什麼？？？？？），這個新的簽章方式讓Casper往前再邁進一步！ BLS是Boneh–Lynn–Shacham的縮寫，有興趣的可以參考 wiki 。這個簽章方式厲害的是，可以把所有signature加起來，然後驗證。如果以現今的ECDSA簽章，100個人簽同一個message，那訊息量就是乘以100倍，以Ethereum官方估計，Casper的validators約有30萬，每一個finality都需要2/3的節點做投票，光是驗證signature這件事，大概就要花到一天，所以以現行的ECDSA簽章方式根本不可行。這也是之前Casper的bottleneck之一，Ethereum的researcher, Justin Drake提出了這個 方案 ，當然也不是拿了就可以用的，BLS的介紹可以參考 BLS signatures: better than Schnorr ，寫得非常清楚也好懂。下面會簡單介紹一下。 首先，就是要找到一個特殊的橢圓對稱曲線可以達到以下的算式     e(a x P, b x Q) = e(P, ab x Q) = e(ab x P, Q) = e(P, Q)^(ab) 也就是某種的交換律 用上面那邊文章的圖做解釋     pk ：私鑰     P ：公鑰     H(m) ：可以看作是hash過的message     S ：簽章 驗證簽章會滿足     e(P, H(m)) = e(G, S) 也就是 signature 可以用 P（公鑰） 跟 H(m)（hash過的message） 做 驗證，跟我們以往的認知是一致的。從公式看BLS在sign跟verify都很簡潔，資料量的部分也小了許多（好像是33 bytes）。而...