區(qū)塊鏈系統(tǒng)中拜占庭容錯(cuò)PBFT工作的實(shí)現(xiàn)原理解析

在本文中，我們將了解區(qū)塊鏈系統(tǒng)中實(shí)際拜占庭容錯(cuò)（PBFT）的工作，該算法背后的數(shù)學(xué)，其意義，編寫(xiě)其偽代碼，然后使用node.js實(shí)現(xiàn)它。

容錯(cuò)與容錯(cuò)系統(tǒng)

想象一下你的車(chē)的發(fā)動(dòng)機(jī)出了什么問(wèn)題，但是它仍然在工作，但是車(chē)速大大降低了，我們稱(chēng)之為容錯(cuò)，它具有容錯(cuò)特性。

任何系統(tǒng)在未知或已知故障的影響下繼續(xù)運(yùn)行，導(dǎo)致系統(tǒng)容量降低，可稱(chēng)為容錯(cuò)系統(tǒng)，并具有容錯(cuò)特性。

與其他系統(tǒng)不同，容錯(cuò)系統(tǒng)在發(fā)生故障時(shí)不會(huì)崩潰，相反，即使出現(xiàn)故障，系統(tǒng)也會(huì)以較低的吞吐量或較高的延遲運(yùn)行。

拜占庭容錯(cuò)

拜占庭故障特別存在于分布式系統(tǒng)中。這些故障是系統(tǒng)節(jié)點(diǎn)之間錯(cuò)誤信息的結(jié)果。系統(tǒng)中存在的故障或錯(cuò)誤信息的原因?qū)τ诜植际较到y(tǒng)的成員來(lái)說(shuō)大多是未知的。因此，在這種情況下，一個(gè)節(jié)點(diǎn)可能行為異常，并向網(wǎng)絡(luò)中的不同節(jié)點(diǎn)發(fā)送不同的響應(yīng)，因此很難將該節(jié)點(diǎn)歸類(lèi)為惡意或故障。因此，為了對(duì)故障節(jié)點(diǎn)做出決策，系統(tǒng)的誠(chéng)實(shí)節(jié)點(diǎn)達(dá)成共識(shí)，可以得出不受惡意/故障節(jié)點(diǎn)影響的結(jié)論的系統(tǒng)可以被視為拜占庭容錯(cuò)系統(tǒng)。

具有拜占庭容錯(cuò)能力的系統(tǒng)解決了拜占庭將軍問(wèn)題中出現(xiàn)的問(wèn)題。

拜占庭容錯(cuò)系統(tǒng)沒(méi)有識(shí)別出故障/惡意并找出問(wèn)題所在，而是在沒(méi)有系統(tǒng)成員出現(xiàn)故障的情況下繼續(xù)運(yùn)行。（因此吞吐量和效率會(huì)降低）

實(shí)戰(zhàn)拜占庭容錯(cuò)

Castro和Liskov開(kāi)發(fā)了一種新方法，可以在分布式系統(tǒng)中達(dá)成共識(shí)，通過(guò)復(fù)制節(jié)點(diǎn)/狀態(tài)機(jī)來(lái)容忍故障/惡意節(jié)點(diǎn)。但是PBFT只能容忍這樣的節(jié)點(diǎn)，直到故障節(jié)點(diǎn)的數(shù)量少于所有節(jié)點(diǎn)的三分之一。網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)在彼此之間傳遞關(guān)于決策的消息來(lái)達(dá)成關(guān)于決策的共識(shí)。誠(chéng)實(shí)的節(jié)點(diǎn)越多，系統(tǒng)就越安全。由于更多數(shù)量的誠(chéng)實(shí)節(jié)點(diǎn)將就錯(cuò)誤/惡意節(jié)點(diǎn)就不正確的決定達(dá)成一致而就正確決策達(dá)成一致，因此大多數(shù)人會(huì)拒絕虛假信息。

為了保證系統(tǒng)安全，pbft需要系統(tǒng)中3f + 1個(gè)節(jié)點(diǎn)，其中f是系統(tǒng)可以容忍的最大故障節(jié)點(diǎn)數(shù)。因此，對(duì)于要做出任何決定的節(jié)點(diǎn)組，需要來(lái)自2f + 1個(gè)節(jié)點(diǎn)的批準(zhǔn)。

區(qū)塊鏈中的PBFT

區(qū)塊鏈中的實(shí)用拜占庭容錯(cuò)算法從分布式系統(tǒng)中使用的版本繼承了許多概念。在這種情況下，達(dá)成共識(shí)以確定塊的有效性。

系統(tǒng)中的節(jié)點(diǎn)彼此共享消息以向鏈提交塊。在這種情況下，惡意節(jié)點(diǎn)可能廣播被篡改的塊，因此，被最大數(shù)量的節(jié)點(diǎn)視為有效的塊被整個(gè)網(wǎng)絡(luò)視為有效。

PBFT的意義

在比特幣（工作證明）中，區(qū)塊提議者是算力最快的礦工，而在利益證明中，區(qū)塊提議者是最富有的礦工。在PBFT中，區(qū)塊創(chuàng)建者可能不是任何特殊的礦工，但是提交給鏈的建議區(qū)塊將是一致同意的區(qū)塊。從而提供與PoW和PoS相同的目的，即向鏈添加新區(qū)塊。

狀態(tài)與消息

本節(jié)描述了每個(gè)節(jié)點(diǎn)在不同會(huì)話(huà)中的各種狀態(tài)以及節(jié)點(diǎn)在任何一輪塊建議期間相互傳遞的不同消息：

· NEW ROUND：提議者發(fā)送新的區(qū)塊提案。驗(yàn)證者等待PRE-PREPARE消息。

· PRE-PREPARED：驗(yàn)證者已收到PRE-PREPARE消息并廣播PREPARE消息。然后它等待PREFARE或COMMIT消息的2F + 1。

· PREPARED：驗(yàn)證者已收到2F + 1個(gè)PREPARE消息并廣播COMMIT消息。然后它等待2F + 1 COMMIT消息。

· COMMITTED：驗(yàn)證者已收到2F + 1個(gè)COMMIT消息，并能夠?qū)⒔ㄗh的區(qū)塊插入?yún)^(qū)塊鏈。

· FINAL COMMITTED：成功地將新塊插入到區(qū)塊鏈中，并且驗(yàn)證者已準(zhǔn)備好進(jìn)行下一輪。

· ROUND CHANGE：驗(yàn)證者在同一個(gè)建議的輪數(shù)上等待2F + 1個(gè)ROUND CHANGE消息。

算法

NEW ROUND

· 提議者以循環(huán)方式選舉產(chǎn)生。

· 提議者從事務(wù)池收集事務(wù)。

· Proposer創(chuàng)建一個(gè)區(qū)塊提議并將其廣播到網(wǎng)絡(luò)。提議者的狀態(tài)現(xiàn)在變?yōu)镻RE-PERPARED狀態(tài)。

· 驗(yàn)證者接收PRE-PREPARE消息并進(jìn)入PRE-PREPARED狀態(tài)。

· 驗(yàn)證這現(xiàn)在驗(yàn)證提議，然后向其他驗(yàn)證者廣播PREPARE消息。

PRE-PREPARED

· 驗(yàn)證者等待2F + 1個(gè)有效的PREPARE消息，然后進(jìn)入PREPARED狀態(tài)。

· 驗(yàn)證者現(xiàn)在在進(jìn)入PREPAPRED狀態(tài)時(shí)廣播COMMIT消息。

PREPARED

· 驗(yàn)證者等待2F + 1提交消息，然后進(jìn)入COMMITTED狀態(tài)。

COMMITTED

· 驗(yàn)證者將接收到的2F+1提交消息附加到塊中，并將塊添加到區(qū)塊鏈中。

· 當(dāng)區(qū)塊插入到鏈中時(shí)，驗(yàn)證者現(xiàn)在轉(zhuǎn)移為FINAL COMMITED狀態(tài)。

FINAL COMMITTED

· 新一輪的提案選舉將啟動(dòng)。

偽代碼

本節(jié)介紹上述算法的偽代碼：

// NEW_ROUND：

State = NEW_ROUND

proposer = get_proposers_address（ blockchain ）

if （ current_validator == proposer ）

block = create_block（ transaction_pool ）

broadcast_block（ block ）

State = PRE_PREPARED

// PRE_PREPARED：

ON message.type == PRE_PREPARE

verify_block（ message.block ）

verify_validator（ message.block ）

broadcast_prepare（ message.block ）

State = PREPARED

// PREPARED：

ON message.type == PREPARE

verify_prepare（ message.prepare ）

verify_validator（ message.prepare ）

prepare_pool.add（ message.prepare ）

if （ prepare_pool.length 》 2F+1 ）

broadcast_commit（ message.prepare ）

State = COMMITTED

// COMMITTED：

ON message.type == COMMIT

verify_commit（ message.commit ）

verify_validator（ message.commit ）

commit_pool.add（ message.commit ）

if （ commit_pool.length 》 2F+1 ）

commit_list = commit_pool.get_commits（）

block.append（ commit_list ）

blockchain.append（ block ）

State = FINAL_COMMITTED

// FINAL_COMMITTED：

new_round（）

本節(jié)將以圖解方式說(shuō)明算法，以便更好地理解：

在新一輪開(kāi)始之前，在節(jié)點(diǎn)之間廣播事務(wù)，以便所有節(jié)點(diǎn)在其池中具有相同的事務(wù)。 在池中有足夠數(shù)量的事務(wù)之后，這些節(jié)點(diǎn)開(kāi)始新一輪。

提議者以循環(huán)方式選擇。 節(jié)點(diǎn)8成為提議者，其余節(jié)點(diǎn)就此達(dá)成一致。 提議者發(fā)送PRE-PREPARE消息，每個(gè)節(jié)點(diǎn)進(jìn)入PRE-PREPARED狀態(tài)。

提議者廣播PRE-PREPARE消息，其中包含建議的區(qū)塊。 其余節(jié)點(diǎn)將此消息廣播到其他節(jié)點(diǎn)。

如果每個(gè)節(jié)點(diǎn)就建議的區(qū)塊達(dá)成一致，則發(fā)送PREPARE消息。 在2F + 1這樣的消息之后，節(jié)點(diǎn)將狀態(tài)改變?yōu)镻REPARED。

準(zhǔn)備好的節(jié)點(diǎn)互相發(fā)送COMMIT消息，在2F + 1提交后，節(jié)點(diǎn)移動(dòng)到COMMIT狀態(tài)并將區(qū)塊添加到鏈中。 添加區(qū)塊后，它們將移至FINAL COMMITTED狀態(tài)。

在FINAL COMMITTED之后，節(jié)點(diǎn)計(jì)算一個(gè)新的提議者。