Bitcoin筆記 6 - Bitcoin consensus algorithm

單一identity的好處

在管理上單一身分制有好處，至少security issue會比較好處理吧。那為何bitcoin採取多identity(每個人都可以任意創造身分)的近似匿名制(pseudonymity)呢? 因為這是他設計的理念，達成近似匿名性。

演算法討論假設: bitcoin有辦法隨機選中一個node

在這個假設前提下，討論bitcoin的consensus algorithm，之後再來證明這個隨機選擇如何達成的。

在consensus block chain形成的過程中，每加入一個block，都來自此隨機選中的node的提議，但是其他所有的nodes如何對此提議出的block達成共識呢? 任何一個贊成此提議的node，會在他們的block chain後面加上這個block，並且之後從此延長block chain。反對者則忽視這個block，之後延伸block chain也不會出現這個提議。

簡化過的演算法:
1. 某node進行交易時，會對所有的nodes廣播此交易
2. 每一個node都在監聽網路，除了擁有一份consensus block chain，並且擁有一份目前尚未加入consensus block chain的transaction list (block)
3. 當某個被隨機選中的node，他可以廣播給其他的node，提出他目前的transaction list形成的block，當作所有nodes的consensus block chain的下一個block
4. 其餘所有的nodes聽到廣播後，根據檢驗此block內所有的transactions的"有效性"(e.g. 數位簽名, 惡意散播,. ...)
5. 所有nodes根據4. 的結果在他們自己的consensus block chain copy中決定是否加入此block

Bitcoin演算法如何避免惡意侵犯

舉例來說，如果某個時候所有nodes看到的consensus block chain如下:

每個block擁有一個hash pointer指向前一個block，一直到最起始的genisis block(創世紀!!!)。

steal coin: 如果此時惡意Alice被隨機選中來提出下一個block candidate，她能侵吞某人的bitcoin嗎? 答案是不行! 因為每個transaction都有digital signature和hash pointer等密碼學機制保護，由於無法偽造digital signature，所以侵吞偷竊bitcoin是達不到的。

denial of service: 如果Alice想要惡意攻擊另一名使用者Bob，就由denial of transaction，意即不把所有跟Bob相關的transaction放入proposed block candidate中呢? 由於惡意者與大多數其他nodes的誠實政策牴觸(假設多數是誠實的話)，本次Alice的提議將會被多數否決，而Bob只要等待之後被選中的(絕大機率為誠實nodes)的node propose一個合法合理的block，將能讓關於Bob的transaction放入consensus block chain中。

double spending attack: 最後就是之前提到的double spending attack，Alice可以把bitcoin送給Bob，而這個交易被廣播之後，在下一輪中被選中的誠實node把這個觀察到的交易放入propose block，形成一個新的consensus block chain:

複習一下，這個transaction是一個data structure，包含alice的簽名，以及一個hash pointer指向這個coin前一筆的交易紀錄，見上圖。所以每個block有hash pointer指向前一個隨機選中的node提出的block，形成consensus block chain，而且每個block中的transaction，也有hash pointer指向前一筆關於此coin的transaction。

如果此時Bob看到consensus block chain是上圖的結果，他可能認為Alice給他的錢幣已經完成交易並且被公認了，所以就安心把貨品或是服務提供給Alice，但! Alice有可能可以逆轉此block chain型態，如果下一次隨機被選中的node是Alice能掌控的惡意node的話! 此惡意node除了能denial前一筆alice給bob的交易之外，甚至能把這個原本要給Bob的coin給了另一個人A'，不過當然此筆惡意交易也必須遵守transaction chain的規則，包含一個hash pointer指向前一筆交易紀錄。

怎麼辦?

Longest-valid chain rule

每個誠實的node都遵循一個規則來決定目前被proposed的block是否該被加入long-term consensus block chain，此規則即為: 永遠延長最長的有效(valid)鍊分支。

不過valid除了密碼學上的有效驗證外，不能區分上圖double spending attack中Alice的惡意block與正確交易block的"有效性"，而且因為兩個分支的長度都一樣，所以有可能下兩回合的honest nodes都追隨惡意block那個branch，使得原本正確的block變成一個orphan block，此時這次的double spending attack成功了:

但也不全然沒救，如果Alice是付bitcoin給Bob換取其他東西，則由於Bob知道Bitcoin network要達成consensus是必須在幾個回合之後才能確定的話，Bob可以觀察是否幾個回合後，這個正確的交易block被network nodes納入了long-term consensus block，如果有的話，再把服務或是貨品遞送給Alice，通常會等待k=6 confirmations: (數學上惡意的branch加入long term consensus 的機率會隨著k的增加而指數性的下降)

這邊有個關鍵點是，所有nodes在兩個branch一樣長度時候的投票要怎麼favor honest transactions? 看來是不行，因為nodes只能驗證簽名有效性，但不能驗證honesty，所以此時是隨機投票嗎? 那如果是這樣，double spending attack似乎有P(successful attack | malicious node is chosen) = 50%以上的conditional probability，不過由於malicious node被選中的機率極低(假設一個bitcoin network多數是honest node)，似乎應該是安全的? 有待以後課程補充。