blockchain做state-machine會遇上的問題
區塊鍊作為state-machine，其概念如下：區塊鍊每隔一段時間，會有一個新的區塊被”settle”，而我們可以視這個區塊內的transaction，部分或全部為一種command，用來更新”state”。舉幾個簡單的例子：
- 在編號第100的區塊裡，有筆交易，其內容為：Alice → Bob $10，當此區塊settle了，Bob的餘額state從$0更新為$10。
- 在編號第150的區塊裡，有筆交易，其內容為：WIll → Bob $20 ，當此區塊settle了，Bob的餘額state從$10更新為$30，這裡的state會從上一個state更新，而不是從一開始的$0 state更新。
以上例子為比特幣用來計算餘額的方式，每個full node都有完整的歷史交易資料，所以當比特幣區塊鍊達成共識的時候，每個node的最終state (即每個地址的餘額)會相同。
而會有問題的地方，在於區塊鍊與傳統認知的BFT(Byzantine Fault Tolerance) 達成共識的方式不同，區塊鍊的共識為“probabilistically consensus”，區塊鍊隨時都會出現fork，這也是51%攻擊為甚麼有效的地方，因為實際上區塊鍊的共識是可以被改變的。
*先註記一下，這裡指的fork是指正常就會發生的fork，與最近比較有話題的HF(hard fork)/SF(soft fork)這種人為的fork比較沒什麼關係。
*blockchain.info上有一些fork發生的紀錄：https://blockchain.info/orphaned-blocks
當fork發生的時候，有幾個東西可能會改變：
- 沒有相依的交易，其順序會變動
- 原本已經上區塊鍊上的交易消失，須重新等候礦工把它收近區塊裡
- 原本的交易變成非法，而被踢除 (double spending為其中一種例子)
- 相同 block height上的資訊會不見/改變：timestamp, nonce, coinbase, mining reward 易主, …
當fork發生的時候，“無法”改變的東西：
- 原交易內容，交易內容由digital signature保護，除非private key被知道，否則無法改變交易。
- 無法完全移除已被廣播的交易：一旦交易被廣播，只要此筆交易合法便無法完整移除，總有一天會被放上區塊鍊。(人為的fork就是在這邊加上新的規則，讓原本合法的交易變不合法然後剔除)
當fork發生的時候，表示現有的state不正確，要更新到正確的state有幾種方式：
- 重新rescan
- 從錯誤的state開始，往前reverse到fork發生的地方，之後重新parse block，好跟其他人有一樣的state
在比特幣的情況，以每個address balance作為state，其更新的方式為第二種。當fork發生，會用Disconnect()來reverse state。而這些從fork區塊移除的交易，會再重新檢查後若合法再放入memory pool。回到fork發生的block之後，針對正確chain上的新block，重新作Connect()。這裡的重點是，我們用blockchain作為state-machine的時候，我們需要多定義reverse function。
另一種情況，很多bitcoin 2.0會在bitcoin blockchain上，多蓋一層protocol。這種多半是利用transaction上一定的自由度，比如說：OP_RETURN, receive address (只檢查格式正確與否), output順序/數量等等。創造一個新的溝通方式，這裡的溝通方式，可以是指一般的交易，或是特殊token的交易，甚至是一些執行指令。在這種情況底下，需好好利用bitcoin transaction的相依性，確保上層該發生的交易會照順序執行，但這基本上很難做到，因為上層的protocol無法影響下層(舉個例子，bitcoin miner不懂counterparty規則)，上下兩層因此很難有強連結。所以若當fork發生，因為交易順序會變動，上層protocol需要另外有額外的處理方式。同時也因為上下兩層沒有強連結，所以當上層protocol說要“保管”底層bitcoin的時候，多半都是讓bitcoin的transaction發生後，才會有後續settle動作。
回到一開始的敘述：blockchain為probabilistically consensus，所以consensus有機會被改變。但若probabilistic接近1，則可視為finality consensus。要提高blockchain consensus的可信度，就是多等幾個confirmation。在時間不為主要考量的情況下，多等幾個confirmation是沒問題的，但是有些應用，其時間是很重要的concern。
舉個例子，以zero knowledge (ZK) 來實現在bitcoin blockchain上的distributed coin join這件事情。有幾個影響到時間的concern:
- 需要一個coin pool來存放coin commitments。這個pool的update是經過zk的運算，現有的zk演算法皆很耗時。
- zk演算法無法reverse。
以上兩點concern，當fork發生，我必須從頭rescan，慢慢回復到現有state，這會非常耗時，尤其blockchain會越來越長，所耗時間只會越來越多。為了避免從頭rescan的overhead，我們可以直接把每個block所產生的state都記錄(snapshot)下來。這引發了其他問題，若我在memory裡跟其他node sync coin pool的資訊，但為了匿名性，我又不好直接用簽章來保護，可能會讓第三方有機會侵入。所以便直接把coin pool的state，放進block裡。這會需要多餘的空間，但提高了安全性＆方便性。
另一個例子是ethereum，其block interval非常短，且有無數多的smart contract，有許多不同種的function，不可能一一幫你做reverse function。所以ethereum也是直接把smart contract 的state紀錄在blockchain上。些許的差異是state的紀錄方式，以及需要紀錄的頻率。
以上為簡單的筆記，有錯誤再找時間訂正。