PBFT的數(shù)學(xué)證明

在實(shí)際的拜占庭容錯(cuò)中，如果N = 3F + 1，N個(gè)節(jié)點(diǎn)的系統(tǒng)可以容忍F個(gè)故障節(jié)點(diǎn)。

實(shí)際拜占庭容錯(cuò)系統(tǒng)中的每個(gè)決策都需要2F + 1批準(zhǔn)，其中Fare是故障節(jié)點(diǎn)。

我們現(xiàn)在將在數(shù)學(xué)上證明上述兩個(gè)定義，它們是彼此的推論。以下計(jì)算是斯坦福大學(xué)筆記中數(shù)學(xué)的簡(jiǎn)化。

分布式系統(tǒng)的兩個(gè)重要特性是活躍性和安全性。

活躍性

活躍性是系統(tǒng)繼續(xù)運(yùn)行時(shí)在分布式系統(tǒng)環(huán)境中使用的術(shù)語(yǔ)。這意味著即使出現(xiàn)一些錯(cuò)誤，系統(tǒng)也不會(huì)停止運(yùn)行。在區(qū)塊鏈的情況下，活躍意味著系統(tǒng)將繼續(xù)向鏈中添加新的區(qū)塊，并且在任何時(shí)候系統(tǒng)都不會(huì)停止工作。

安全性

當(dāng)系統(tǒng)收斂于單個(gè)決策時(shí)，安全性是分布式系統(tǒng)環(huán)境中使用的術(shù)語(yǔ)。在分布式系統(tǒng)中，節(jié)點(diǎn)可能會(huì)分成兩個(gè)決策或進(jìn)一步拆分，分布式系統(tǒng)的安全性確保了即使存在故障節(jié)點(diǎn)，網(wǎng)絡(luò)也會(huì)在所有可靠節(jié)點(diǎn)上以單個(gè)決策結(jié)束。

證明

非拜占庭式故障

給定網(wǎng)絡(luò)中的N個(gè)節(jié)點(diǎn)，具有f個(gè)故障節(jié)點(diǎn)，保證活躍性和安全性所需的仲裁大小Q是多少？

仲裁定義為網(wǎng)絡(luò)正常運(yùn)行和做出有效決策所需的最小節(jié)點(diǎn)數(shù)。仲裁由誠(chéng)實(shí)的節(jié)點(diǎn)組成。

活躍度

為了避免網(wǎng)絡(luò)停止，必須至少存在一個(gè)非故障節(jié)點(diǎn)。因此，為了活躍度：

Q 《= N - f

安全度

為了避免網(wǎng)絡(luò)分裂成多個(gè)決策，大多數(shù)決策者應(yīng)該在線。我們需要一個(gè)誠(chéng)實(shí)的多數(shù)，仲裁大小應(yīng)該大于節(jié)點(diǎn)總數(shù)的一半，以便我們做出有利于我們的決定。

因此，為了安全：

Q 》 N/2

2Q - N 》 0

通過(guò)梳理我們得到的兩個(gè)條件，

N 《 2Q 《=2（N-f）

f 《 N/2

N 》 2f

因此，對(duì)于非拜占庭式故障

拜占庭式故障

假設(shè)網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，其中f個(gè)故障節(jié)點(diǎn)可能會(huì)遇到拜占庭式故障，那么要保證活躍性和安全性，需要多少仲裁大小Q？

遭受拜占庭式失敗的節(jié)點(diǎn)可以投票給無(wú)效的區(qū)塊或決策，導(dǎo)致決策中的分裂，并因此分叉。

活躍度

為了避免網(wǎng)絡(luò)停止，必須存在至少一個(gè)非故障節(jié)點(diǎn)或仲裁。由于拜占庭節(jié)點(diǎn)可能無(wú)法回復(fù)。

因此，為了活躍度：

Q 《= N - f

安全性

為了避免網(wǎng)絡(luò)分裂成多個(gè)決策，大多數(shù)決策者應(yīng)該在線。然而，與非拜占庭式失敗不同，拜占庭式失敗中的節(jié)點(diǎn)也可以投票，因此我們需要在投票過(guò)程中考慮故障節(jié)點(diǎn)。

Q 》 N/2

2Q - N 》 0

此公式提供了網(wǎng)絡(luò)中可能存在的最大失敗節(jié)點(diǎn)數(shù)。

因此，為了安全起見(jiàn)，也可以將其寫(xiě)為：

2Q - N 》 f

其中f是可容忍故障節(jié)點(diǎn)的最大數(shù)量。

把這兩個(gè)條件結(jié)合起來(lái)

N + f 《 2Q 《 2（N - f）

N + f 《 2N - 2f

3f 《 N

N 》 3f

if N = 3f + 1

then 2Q 》 4f + 1

or

Q 》 2f + 1/2

因此，對(duì)于拜占庭式的失敗

Qmin = 3f + 1

在node.js中實(shí)現(xiàn)PBFT

在本節(jié)中，我們將實(shí)現(xiàn)一個(gè)以PBFT為共識(shí)算法的區(qū)塊鏈。值得注意的是，該區(qū)塊鏈不會(huì)使用加密貨幣，但如果我們使用賬戶(hù)模型，則可以使用。此外，由于PBFT易受Sybil攻擊，因此只能在許可的環(huán)境下運(yùn)行，因此需要了解網(wǎng)絡(luò)成員。

先決條件

· Node.js

· Postman

· VS code

架構(gòu)與設(shè)計(jì)

為了實(shí)施PBFT，我們將開(kāi)發(fā)以下組件：

1. 錢(qián)包類(lèi) - 用于公鑰和簽名數(shù)據(jù)。

2. 事務(wù)類(lèi) - 創(chuàng)建事務(wù)并驗(yàn)證它們。

3. 區(qū)塊類(lèi) - 創(chuàng)建區(qū)塊，驗(yàn)證塊并驗(yàn)證區(qū)塊的提議者。

4. 區(qū)塊鏈類(lèi) - 創(chuàng)建鏈，添加區(qū)塊，計(jì)算提議者，驗(yàn)證區(qū)塊，更新區(qū)塊。

5. P2p Server類(lèi) - 在對(duì)等體之間廣播和接收數(shù)據(jù)。

6. 驗(yàn)證者 - 生成并驗(yàn)證驗(yàn)證者

7. 事務(wù)池，區(qū)塊池，提交池，準(zhǔn)備池和消息池 - 分別存儲(chǔ)事務(wù)，區(qū)塊，提交，準(zhǔn)備和新輪消息。

8. App - 用于與區(qū)塊鏈交互的Express API

9. 配置 - 存儲(chǔ)全局變量

10. Chain Utilities - 用于存儲(chǔ)散列和驗(yàn)證簽名等常用功能。

創(chuàng)建一個(gè)根目錄pbft并將其cd入其中。此項(xiàng)目中的所有文件都存在于根目錄中。

mkdir pbft && cd pbft

ChainUtil類(lèi)

我們將從創(chuàng)建一個(gè)chain-util.js文件開(kāi)始，該文件將在此項(xiàng)目中多次使用。此文件將用于創(chuàng)建用于簽名數(shù)據(jù)的密鑰對(duì)，為事務(wù)生成ID，散列數(shù)據(jù)和驗(yàn)證簽名。

我們需要三個(gè)模塊來(lái)執(zhí)行這些功能。因此我們需要安裝它們。

npm i --save elliptic uuid crypto-js

創(chuàng)建一個(gè)ChainUtil類(lèi)并將其導(dǎo)出。

// EDDSA allows us to create keypairs

// It is collection of cryptographic algorithms that are used to create keypairs

const EDDSA = require（“elliptic”）.eddsa;

// ed25519 allows us to create key pair from secret

const eddsa = new EDDSA（“ed25519”）;

// uuid/v1 creates timestamp dependent ids

const uuidV1 = require（“uuid/v1”）;

// used for hashing data to 256 bits string

const SHA256 = require（“crypto-js/sha256”）;

class ChainUtil {

// a static function to return keypair generated using a secret phrase

static genKeyPair（secret） {

return eddsa.keyFromSecret（secret）;

}

// returns ids used in transactions

static id（） {

return uuidV1（）;

}

// hashes any data using SHA256

static hash（data） {

return SHA256（JSON.stringify（data））.toString（）;

}

// verifies the signed hash by decrypting it with public key

// and matching it with the hash

static verifySignature（publicKey， signature， dataHash） {

return eddsa.keyFromPublic（publicKey）.verify（dataHash， signature）;

}

}

module.exports = ChainUtil;

pbft_chain_util.js

事務(wù)類(lèi)

接下來(lái)，我們將創(chuàng)建一個(gè)事務(wù)類(lèi)。在項(xiàng)目文件夾中創(chuàng)建文件transaction.js。此項(xiàng)目中的事務(wù)將包含以下屬性：

· id - 用于識(shí)別

· from - 發(fā)件人的地址

· input - 一個(gè)進(jìn)一步包含要存儲(chǔ)的數(shù)據(jù)和時(shí)間戳的對(duì)象

· hash - 輸入的SHA256

· signature - 發(fā)件人簽名的哈希

在文件中創(chuàng)建一個(gè)類(lèi)Transaction并將其導(dǎo)出。

// Import the ChainUtil class used for hashing and verification

const ChainUtil = require（“。/chain-util”）;

class Transaction {

// the wallet instance will be passed as a parameter to the constructor

// along with the data to be stored.

constructor（data， wallet） {

this.id = ChainUtil.id（）;

this.from = wallet.publicKey;

this.input = { data： data， timestamp： Date.now（） };

this.hash = ChainUtil.hash（this.input）;

this.signature = wallet.sign（this.hash）;

}

// this method verifies wether the transaction is valid

static verifyTransaction（transaction） {

return ChainUtil.verifySignature（

transaction.from，

transaction.signature，

ChainUtil.hash（transaction.input）

）;

}

}

module.exports = Transaction;

pbft-transaction.js

錢(qián)包類(lèi)

接下來(lái)是錢(qián)包。錢(qián)包持有公鑰和密鑰對(duì)。它還負(fù)責(zé)簽署數(shù)據(jù)哈希并創(chuàng)建簽名事務(wù)。

在項(xiàng)目目錄中創(chuàng)建文件wallet.js。添加一個(gè)類(lèi)Wallet并將其導(dǎo)出。

// Import the ChainUtil class used for hashing and verification

const ChainUtil = require（“。/chain-util”）;

// Import transaction class used for creating transactions

const Transaction = require（“。/transaction”）;

class Wallet {

// The secret phase is passed an argument when creating a wallet

// The keypair generated for a secret phrase is always the same

constructor（secret） {

this.keyPair = ChainUtil.genKeyPair（secret）;

this.publicKey = this.keyPair.getPublic（“hex”）;

}

// Used for prining the wallet details

toString（） {

return `Wallet -

publicKey： ${this.publicKey.toString（）}`;

}

// Used for signing data hashes

sign（dataHash） {

return this.keyPair.sign（dataHash）.toHex（）;

}

// Creates and returns transactions

createTransaction（data） {

return new Transaction（data， this）;

}

// Return public key

getPublicKey（） {

return this.publicKey;

}

}

module.exports = Wallet;

pbft-wallet.js

驗(yàn)證者類(lèi)

由于PBFT是一種許可的區(qū)塊鏈一致性算法，我們需要存儲(chǔ)每個(gè)節(jié)點(diǎn)系統(tǒng)中所有節(jié)點(diǎn)的地址。我們可以通過(guò)選擇一個(gè)密鑰，創(chuàng)建一個(gè)錢(qián)包，獲取其公鑰并將該密鑰存儲(chǔ)到一個(gè)文件中來(lái)手動(dòng)執(zhí)行此操作。當(dāng)我們運(yùn)行我們的項(xiàng)目時(shí)，它會(huì)讀取此文件以獲取密鑰。

但是，不是手動(dòng)執(zhí)行此操作，我們可以通過(guò)創(chuàng)建類(lèi)并添加可以返回N個(gè)節(jié)點(diǎn)的公鑰列表的函數(shù)來(lái)自動(dòng)執(zhí)行此操作。

我們將創(chuàng)建一個(gè)Validator類(lèi)，它將生成每個(gè)節(jié)點(diǎn)都知道的公鑰列表。在這個(gè)項(xiàng)目中，我們使用了每個(gè)節(jié)點(diǎn)的密碼短語(yǔ)

NODE1，NODE2，NODE3 。..。..

這樣，我們就可以更容易地創(chuàng)建公鑰列表，并使用相同的公鑰從命令行創(chuàng)建節(jié)點(diǎn)。

// Import the wallet class

const Wallet = require（“。/wallet”）;

class Validators {

// constructor will take an argument which is the number of nodes in the network

constructor（numberOfValidators） {

this.list = this.generateAddresses（numberOfValidators）;

}

// This function generates wallets and their public key

// The secret key has been known for demonstration purposes

// Secret will be passed from command line to generate the same wallet again

// As a result the same public key will be generatedd

generateAddresses（numberOfValidators） {

let list = ［］;

for （let i = 0; i 《 numberOfValidators; i++） {

list.push（new Wallet（“NODE” + i）.getPublicKey（））;

}

return list;

}

// This function verfies if the passed public key is a known validator or not

isValidValidator（validator） {

return this.list.includes（validator）;

}

}

module.exports = Validators;

注意：密鑰不應(yīng)該公開(kāi)。只有在演示中我們才使用這樣的密鑰。在實(shí)際項(xiàng)目中，發(fā)送注冊(cè)請(qǐng)求以使節(jié)點(diǎn)成為驗(yàn)證者。如果整個(gè)網(wǎng)絡(luò)批準(zhǔn)此請(qǐng)求，則該節(jié)點(diǎn)將成為驗(yàn)證者，并將公鑰添加到列表中。

Config.js文件

網(wǎng)絡(luò)中的驗(yàn)證者數(shù)量可以通過(guò)命令行傳遞，但更容易將其存儲(chǔ)在文件中并在需要的地方導(dǎo)入。

創(chuàng)建一個(gè)文件config.js并創(chuàng)建三個(gè)變量NUMBER_OF_NODES，MIN_APPROVALS和TRANSACTION_THRESHOLD

// Maximum number of transactions that can be present in a block and transaction pool

const TRANSACTION_THRESHOLD = 5;

// total number of nodes in the network

const NUMBER_OF_NODES = 3;

// Minmu number of positive votes required for the message/block to be valid

const MIN_APPROVALS = 2 * （NUMBER_OF_NODES / 3） + 1;

module.exports = {

TRANSACTION_THRESHOLD，

NUMBER_OF_NODES，

MIN_APPROVALS

};

PBFT-config.js