瑞波Ripple是如何處理一致共識錯誤的

Ripple是一個國際性支付系統(tǒng)，允許用戶像發(fā)送電子郵件一樣無縫地進(jìn)行跨國界轉(zhuǎn)移資金（包括法定貨幣、數(shù)字貨幣和其他形式的價值）。如同比特幣等其他數(shù)字貨幣，ripple協(xié)議通過去中心化的計算機網(wǎng)絡(luò)允許進(jìn)行P2P交易結(jié)算。然而，與其他數(shù)字貨幣協(xié)議不同，ripple協(xié)議的貨幣是不可知的，不要求用戶使用協(xié)議中的原生貨幣（XRP）。此外，技術(shù)能夠?qū)崿F(xiàn)幾乎實時結(jié)算（3-6秒），而且將把每個國際交易發(fā)送給網(wǎng)絡(luò)中可得的最便宜的買賣差價。

機制

在核心處，ripple有記錄用來交易資產(chǎn)的賬戶、余額和要約信息的“總賬（Ledger）”。類似創(chuàng)建賬戶、進(jìn)行支付、轉(zhuǎn)變資產(chǎn)等操作通過被稱為“交易”的簽署指令來進(jìn)行。

因為ripple是一個用密碼寫的系統(tǒng)，賬戶可通過加密身份進(jìn)行鑒定。交易被與加密身份相匹配的加密簽名檢驗。根據(jù)確定的、已知的規(guī)則，每個服務(wù)器處理每個交易。

雙重支付問題

根本無效的交易可以被所有參與者識別出來，例如從一個只有10美元的賬戶中發(fā)送20美元。然而，也有可能創(chuàng)建兩個交易，其中只有一個有效。這種情況被稱為雙重支付問題。

假設(shè)Alice在某個支付系統(tǒng)中有10美元。假定是一個有用的支付系統(tǒng)，如果她想的話，就必須能向Bob發(fā)送10美元。而且同樣，也可以發(fā)送給Charlie。然而，如果她向Bob和Charlie發(fā)送了相同的10美元，那么支付系統(tǒng)停止使用。因此以某種方法，向Bob發(fā)送10美元的行為必須阻止她向Charlie發(fā)送相同的10美元。

按照慣例，這是由中央機構(gòu)解決的。例如，銀行會清除基于發(fā)行者可利用余額的支票，其中銀行是這些余額的唯一托管人。然而，像ripple一樣的分布式系統(tǒng)，明顯沒有中央機關(guān)。他們必須通過其他方式解決雙重支付問題。

簡化（雙重支付）問題

大部分雙重支付問題可以通過眾所周知的方法來解決，比如阻止一個賬戶支付它沒有的資金。實際上，雙重支付問題可以簡化為給交易排序。

再來看Alice試圖給Bob和Charlie發(fā)送相同10美元的例子。如果支付給Bob的行為被認(rèn)為是第一位，那每個人都會同意她有資金支付Bob。而且如果支付給Charlie的行為被認(rèn)為是第二位，那每個人都會同意她不能把那些資金給Charilie，因為現(xiàn)在是屬于Bob的。

我們也可以按照確定性的規(guī)則給交易排序。由于交易是數(shù)字信息的集合，所以它們能輕易被排序。

沒有中央機關(guān)的情況下，這對解決雙重支付問題來說足夠了，但它要求我們在確定交易結(jié)果之前掌握所有將要發(fā)生的交易，以便于我們進(jìn)行排序。顯然，這是不實際的。

然而，如果我們能把交易分成群組而且就那些群組達(dá)成一致，那么我們就可以在那個群組中對交易進(jìn)行排序。也就是說，只要每個參與者都同意把這些交易按照一個單位來處理，那么他們就能使用確定性的規(guī)則來解決雙重支付問題，不需要任何中央機構(gòu)。參與者只各自對交易進(jìn)行排序，并按照已知的規(guī)則以確定性的方法應(yīng)用到交易上。

Ripple不依賴于兩個互相沖突的交易中的任何一個。根據(jù)確定性規(guī)則，交易群組是已生效的，而且一個群組里有兩個相沖突的交易沒有傷害。根據(jù)排序規(guī)定，第一位的交易會成功，第二位的交易會失敗。

一致共識的基本角色是讓過程中的參與者就交易可以被處理為一個單元來解決雙重支付問題的事宜達(dá)成一致。有四個理由說明這個協(xié)議比預(yù)期更容易達(dá)成。

1. 如果實在沒有理由讓一個交易不被納入此交易群組，那所有可靠的參與者都會同意收納它。如果所有參與者都已經(jīng)同意，那一致共識就不用做任何事情了。

2. 如果有該交易不應(yīng)被納入交易群組的任何理由，所有可靠的參與者會傾向于排斥它。如果交易仍然有效，那就沒有理由在第二輪不包含它，而且那時他們都應(yīng)該同意包含它。

3. 有極少數(shù)的參與者會特別關(guān)心交易分組的方式。當(dāng)所有人的重點是達(dá)成一致時，實現(xiàn)一致最為簡單。只有當(dāng)他們分發(fā)利益時，實現(xiàn)一致才面臨挑戰(zhàn)。確定性原則甚至可以被用來構(gòu)建組群，只有在邊界條件時才會導(dǎo)致不一致。例如，如果在一輪中有兩個相沖突的交易，確定性原則可以被用來決定誰進(jìn)入下一輪。

4. 每個參與者最優(yōu)先的事情是正確性。也就是說，不能違反那些人們所依賴的用來維護(hù)網(wǎng)絡(luò)完整性的準(zhǔn)則。例如，一定不能處理一個沒有被正確簽署的交易。然而，每個可靠參與者的第二優(yōu)先事情是一致性。一個具有雙重支付可能性的網(wǎng)絡(luò)根本沒有效用。每個可靠參與者最重視的是正確性，這個事實推進(jìn)一致性進(jìn)程。

如何實現(xiàn)一致共識

達(dá)成一致性開始于每個想要這樣做的參與者作出最初的決定。這是他們目睹的有效交易集合。

然后參與者大量投入到達(dá)成一致性的過程中：如果一個特定交易沒有得到多數(shù)支持，那參與者將同意推遲那個交易。如果一個特定交易擁有多數(shù)支持，參與者將同意包含這個交易。因此，輕微的多數(shù)快速成為全部支持，而且輕微的少數(shù)快速成為現(xiàn)有這一輪的普遍拒絕者。

為了防止一致性過程停留在50%附近，而且為了減少可靠的收斂性造成的重疊，要求包含某個交易的閾值越來越高。首先，如果超過50%的參與者同意，那參與者將持續(xù)同意包含這個交易。然后這個數(shù)字會上升至60%，而且會持續(xù)增加，直至有爭議性的交易被推遲至下一輪。

如果參與者發(fā)現(xiàn)絕對多數(shù)同意接下來處理某個交易集合，那就會宣布達(dá)成一致共識。

一致共識可能會失敗

開發(fā)一種永遠(yuǎn)都能達(dá)成完美共識的一致性算法是不實際的。理解為什么會這樣的途徑之一是考慮一致共識過程是如何終止的。在某種程度上，每個參與者必須宣布已經(jīng)達(dá)成一致性，而且某些交易集合已被認(rèn)為是這個過程的結(jié)果。該聲明不能撤回地將參與者引入某些作為一致性過程結(jié)果的特定交易集合。

很明顯，有些參與者必須第一個做這件事或者永遠(yuǎn)不會有參與者做，一致性永遠(yuǎn)不能達(dá)成。目前，假設(shè)參與者首先已經(jīng)這樣做了。當(dāng)參與者決定一致性達(dá)成的時候，其他參與者還沒有做出這個決定。如果從他們角度而言，沒能改變這個已被同意的集合，那么他們就會作出一致性達(dá)成的決定。所以他們必須有能力改變被同意的集合。

換句話說，對于終止的一致共識進(jìn)程，某個參與者必須宣布交易集合已達(dá)成一致，盡管其他每個參與者理論上仍能改變同意交易集合的決定。

這種失敗的可能性非常低，但不能縮減為零。技術(shù)性交易（engineering tradeoff）促使這種可能性降至千分之一以下，使得一致共識進(jìn)程明顯放緩，并使一致共識更難容忍網(wǎng)絡(luò)和端點錯誤。

Ripple如何處理一致共識錯誤的

在一輪一致共識進(jìn)程結(jié)束后，每個參與者申請他們認(rèn)為被贊同的交易集合。這促使構(gòu)建他們所認(rèn)為的總賬應(yīng)有的下一個狀態(tài)。

然后，同樣也是驗證者的參與者發(fā)布下一個總賬的加密指紋（cryptographic fingerprint），這被稱為“驗證”。如果達(dá)成一致，那絕大多數(shù)的驗證者應(yīng)發(fā)布相同的指紋。

之后，參與者收集這些驗證。從驗證中，他們可以判斷出先前的一致共識是否會導(dǎo)致絕大多數(shù)參與者同意這個交易集合。

參與者將面臨以下三種情況之一，按可能性大小排序。

1. 他們建立了絕對多數(shù)同意的相同總賬。這種情況下，他們可以認(rèn)為總賬被充分驗證，而且可以信賴總賬的內(nèi)容。

2. 他們建立了不同于絕對多數(shù)同意的總賬。這種情況下，他們必須建立和接受絕對多數(shù)同意的總賬。這是一個典型的例子，他們很早宣布達(dá)成一致，之后其他參與者進(jìn)行了修改。他們必須“跳轉(zhuǎn)”至絕對多數(shù)總賬，從而實現(xiàn)繼續(xù)運轉(zhuǎn)。

3. 收到的驗證中沒有出現(xiàn)明顯的絕對多數(shù)。這種情況下，先前的一致共識就被廢棄了，而且在任何一個總賬被驗證前，必須發(fā)起新一輪一致性協(xié)商。

當(dāng)然，情況1是最常見的。無論如何，情況2是不會損害網(wǎng)絡(luò)的。小部分參與者會每一輪都出現(xiàn)情況2，而且網(wǎng)絡(luò)會順利運行。

情況3導(dǎo)致網(wǎng)絡(luò)停止幾秒來推動進(jìn)程向前，但這極其少見。這種情況下，后來的一致共識更不容易失敗，因為一致共識進(jìn)程化解了不一致，而且只有存在不一致會導(dǎo)致失敗。

在很少的情況中，整個網(wǎng)絡(luò)會幾秒鐘不能取得進(jìn)展。作為交換，交易確認(rèn)的平均次數(shù)會比較少。

理念

系統(tǒng)在某些組件失敗或某些參與者具有惡意的情況下提供結(jié)果的能力是可靠性的一種表現(xiàn)形式。盡管這很重要，但在加密支付系統(tǒng)中還有另一種更為重要的可靠性形式，即系統(tǒng)產(chǎn)生可信賴結(jié)果的能力。也就是說，當(dāng)系統(tǒng)報告結(jié)果可靠時，我們應(yīng)信賴那個結(jié)果。

然而，現(xiàn)實世界系統(tǒng)面臨以上兩種可靠性都讓步的運行狀況。這包括硬件故障、通信故障，甚至不可靠的參與者。Ripple部分設(shè)計理念就是為了發(fā)現(xiàn)并報告結(jié)果可靠性被削弱的情況，而不是提供一定不可靠的結(jié)果。

Ripple一致性算法為工作系統(tǒng)證明提供了另一種方法，而不是不必要地消耗計算資源。拜占庭錯誤是有可能的，而且確實發(fā)生過，但結(jié)果只是少數(shù)延遲。在所有情況中，ripple一致性算法只有在結(jié)果真正可靠時才會進(jìn)行報告。

圖解

這是關(guān)于一致性共識算法的大致圖解。

一致性共識的目的是讓所有服務(wù)器都同意一組交易并生效到最后關(guān)閉總賬（Last Closed Ledger）上。他們不關(guān)心交易是否有效或者交易發(fā)生的順序。他們只關(guān)心所有服務(wù)器都贊同這組數(shù)據(jù)是什么。

一致共識是個持續(xù)迭代的過程。服務(wù)器發(fā)出一組交易的提案，然后其他從對端接收到（提案）的服務(wù)器也發(fā)出自己的提案。

這里我們有某一臺在Ripple網(wǎng)絡(luò)中的服務(wù)器的抽象化圖解。

在中間顯示了關(guān)閉包（Closing Bundle）。這是一組交易，網(wǎng)絡(luò)正在嘗試達(dá)成一致。

現(xiàn)在我們看到，（左上角）一個提案來到了這臺服務(wù)器。在一致共識達(dá)成期間，每個服務(wù)器都發(fā)出一系列的提案。提案就是 該服務(wù)器認(rèn)為應(yīng)該把他包含到關(guān)閉包里的交易列表。

（該服務(wù)器會對）這傳入的提案針對UNL進(jìn)行檢查。如果發(fā)送提案的服務(wù)器在UNL列表上，那么這個提案被發(fā)送到關(guān)閉包，并且里面的所有交易都獲得1票。

而在網(wǎng)絡(luò)試圖達(dá)成在最后一個交易集合的共識（的過程中），新的交易進(jìn)入。這些交易被收集在下一包。它們將被施加到下一個總帳（Ledger）。

在這里，我們看到了一個提案，來源服務(wù)器不是我們的UNL。這個提案被簡單地丟棄，而不用判斷什么要包含到最后關(guān)閉包里。

part2

現(xiàn)在，我們已經(jīng)得到了來自其他服務(wù)器的一些提案。目前我們有5個活躍的UNL服務(wù)器。那些被超過50％的活躍服務(wù)器投過票的交易，都被認(rèn)為應(yīng)該（被服務(wù)器）打包。你可以看到標(biāo)記為綠色的這些交易。

現(xiàn)在，計時器已經(jīng)用完了，所以我們把我們的針對當(dāng)前包的投票發(fā)送到網(wǎng)絡(luò)。一個交易是否該放到當(dāng)前包里，這個（得票率）閾值也從50％提高到60％。這樣有很多不同意見的交易，將有一種傾向–被推到下一個總帳。

我們已經(jīng)收到更多的提案（上圖是Server5的新提案到達(dá)），改變了我們的想法：關(guān)閉包應(yīng)該包括（哪些交易）。（上圖可見“=”這個交易也到達(dá)了3/5的投票率）

一致共識機制認(rèn)為：達(dá)到UNL的80% 服務(wù)器同意的那些交易，應(yīng)該放入這個總賬。你可以看到在這里發(fā)生了，因為每個交易有4個或更多的得票或小于2票。這些交易將被發(fā)送并被施加到上次關(guān)閉總帳（Last Closed Ledger）。 （譯注：這里有個bug？圖標(biāo)為“=”的交易，只有3票，也被發(fā)送到LCL了）

關(guān)閉包開始著手生成新的LCL。你在那個關(guān)閉過程中收集到的新交易，將被添加到之前的沒能到放總帳的交易候選集里?，F(xiàn)在達(dá)成一致共識的過程重新開始……

譯者補充

這個文章只說了proposal過程。實際過程比這個復(fù)雜，一致性會包括兩步，Proposal和Validation；Ledger狀態(tài)會有三個，ClosingLedger，LCL，AcceptedL。

1. Proposal階段會發(fā)出自己的closing ledger，大家不斷根據(jù)收到的proposal建立交集，剩下的建disputed TXs進(jìn)行投票，投票通過的會繼續(xù)保留在closing ledger，得票率要求隨時間提高

2. 投票不通過的留在下一個ledger處理

3. 然后就是靠那個復(fù)雜的ContinuousLedgerTiming：：haveConsensus算法判定何時可以將closing ledger轉(zhuǎn)成LCL并發(fā)出validation

4. 然后validation超過quorum個則將LCL轉(zhuǎn)為accepted ledger繼續(xù)往前走，

5. 之后走的過程中一旦發(fā)現(xiàn)validation最多的LCL和自己的不一樣，則會轉(zhuǎn)入分支切換流程從網(wǎng)絡(luò)獲取新的LCL。