PBFT的數學證明
在實際的拜占庭容錯中,如果N = 3F + 1,N個節點的系統可以容忍F個故障節點。
實際拜占庭容錯系統中的每個決策都需要2F + 1批准,其中Fare是故障節點。
我們現在將在數學上證明上述兩個定義,它們是彼此的推論。以下計算是斯坦福大學筆記中數學的簡化。
分散式系統的兩個重要特性是活躍性和安全性。
活躍性
活躍性是系統繼續執行時在分散式系統環境中使用的術語。這意味著即使出現一些錯誤,系統也不會停止執行。在區塊鏈的情況下,活躍意味著系統將繼續向鏈中新增新的區塊,並且在任何時候系統都不會停止工作。
安全性
當系統收斂於單個決策時,安全性是分散式系統環境中使用的術語。在分散式系統中,節點可能會分成兩個決策或進一步拆分,分散式系統的安全性確保了即使存在故障節點,網路也會在所有可靠節點上以單個決策結束。
證明
非拜占庭式故障
給定網路中的N個節點,具有f個故障節點,保證活躍性和安全性所需的仲裁大小Q是多少?
仲裁定義為網路正常執行和做出有效決策所需的最小節點數。仲裁由誠實的節點組成。
活躍度
為了避免網路停止,必須至少存在一個非故障節點。因此,為了活躍度:
Q <= N - f
安全度
為了避免網路分裂成多個決策,大多數決策者應該線上。我們需要一個誠實的多數,仲裁大小應該大於節點總數的一半,以便我們做出有利於我們的決定。
因此,為了安全:
Q > N/2
2Q - N > 0
透過梳理我們得到的兩個條件,
N < 2Q <=2(N-f)
f < N/2
N > 2f
因此,對於非拜占庭式故障
拜占庭式故障
假設網路中有n個節點,其中f個故障節點可能會遇到拜占庭式故障,那麼要保證活躍性和安全性,需要多少仲裁大小Q?
遭受拜占庭式失敗的節點可以投票給無效的區塊或決策,導致決策中的分裂,並因此分叉。
活躍度
為了避免網路停止,必須存在至少一個非故障節點或仲裁。由於拜占庭節點可能無法回覆。
因此,為了活躍度:
Q <= N - f
安全性
為了避免網路分裂成多個決策,大多數決策者應該線上。然而,與非拜占庭式失敗不同,拜占庭式失敗中的節點也可以投票,因此我們需要在投票過程中考慮故障節點。
Q > N/2
2Q - N > 0
此公式提供了網路中可能存在的最大失敗節點數。
因此,為了安全起見,也可以將其寫為:
2Q - N > f
其中f是可容忍故障節點的最大數量。
把這兩個條件結合起來
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
因此,對於拜占庭式的失敗
Qmin = 3f + 1
在node.js中實現PBFT
在本節中,我們將實現一個以PBFT為共識演算法的區塊鏈。值得注意的是,該區塊鏈不會使用加密貨幣,但如果我們使用賬戶模型,則可以使用。此外,由於PBFT易受Sybil攻擊,因此只能在許可的環境下執行,因此需要了解網路成員。
先決條件
Node.js
Postman
VS code
架構與設計
為了實施PBFT,我們將開發以下元件:
錢包類 - 用於公鑰和簽名資料。
事務類 - 建立事務並驗證它們。
區塊類 - 建立區塊,驗證塊並驗證區塊的提議者。
區塊鏈類 - 建立鏈,新增區塊,計算提議者,驗證區塊,更新區塊。
P2p Server類 - 在對等體之間廣播和接收資料。
驗證者 - 生成並驗證驗證者
事務池,區塊池,提交池,準備池和訊息池 - 分別儲存事務,區塊,提交,準備和新輪訊息。
App - 用於與區塊鏈互動的Express API
配置 - 儲存全域性變數
Chain Utilities - 用於儲存雜湊和驗證簽名等常用功能。
建立一個根目錄pbft並將其cd入其中。此專案中的所有檔案都存在於根目錄中。
mkdir pbft && cd pbft
ChainUtil類
我們將從建立一個chain-util.js檔案開始,該檔案將在此專案中多次使用。此檔案將用於建立用於簽名資料的金鑰對,為事務生成ID,雜湊資料和驗證簽名。
我們需要三個模組來執行這些功能。因此我們需要安裝它們。
npm i --save elliptic uuid crypto-js
建立一個ChainUtil類並將其匯出。
// 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");
classChainUtil{
// a static function to return keypair generated using a secret phrase
staticgenKeyPair(secret){
return eddsa.keyFromSecret(secret);
}
// returns ids used in transactions
staticid(){
return uuidV1();
}
// hashes any data using SHA256
statichash(data){
return SHA256(JSON.stringify(data)).toString();
}
// verifies the signed hash by decrypting it with public key
// and matching it with the hash
staticverifySignature(publicKey, signature, dataHash){
return eddsa.keyFromPublic(publicKey).verify(dataHash, signature);
}
}
module.exports = ChainUtil;
pbft_chain_util.js
事務類
接下來,我們將建立一個事務類。在專案資料夾中建立檔案transaction.js。此專案中的事務將包含以下屬性:
id - 用於識別
from - 發件人的地址
input - 一個進一步包含要儲存的資料和時間戳的物件
hash - 輸入的SHA256
signature - 發件人簽名的雜湊
在檔案中建立一個類Transaction並將其匯出。
// Import the ChainUtil class used for hashing and verification
const ChainUtil = require("./chain-util");
classTransaction{
// 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
錢包類
接下來是錢包。錢包持有公鑰和金鑰對。它還負責簽署資料雜湊並建立簽名事務。
在專案目錄中建立檔案wallet.js。新增一個類Wallet並將其匯出。
// 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");
classWallet{
// 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) {
returnthis.keyPair.sign(dataHash).toHex();
}
// Creates and returns transactions
createTransaction(data) {
return new Transaction(data, this);
}
// Return public key
getPublicKey() {
returnthis.publicKey;
}
}
module.exports = Wallet;
pbft-wallet.js
驗證者類
由於PBFT是一種許可的區塊鏈一致性演算法,我們需要儲存每個節點系統中所有節點的地址。我們可以透過選擇一個金鑰,建立一個錢包,獲取其公鑰並將該金鑰儲存到一個檔案中來手動執行此操作。當我們執行我們的專案時,它會讀取此檔案以獲取金鑰。
但是,不是手動執行此操作,我們可以透過建立類並新增可以返回N個節點的公鑰列表的函式來自動執行此操作。
我們將建立一個Validator類,它將生成每個節點都知道的公鑰列表。在這個專案中,我們使用了每個節點的密碼短語
NODE1,NODE2,NODE3 ......
這樣,我們就可以更容易地建立公鑰列表,並使用相同的公鑰從命令列建立節點。
// Import the wallet class
const Wallet = require("./wallet");
classValidators {
// 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());
}
returnlist;
}
// This function verfies if the passed public key is a known validator or not
isValidValidator(validator) {
returnthis.list.includes(validator);
}
}
module.exports = Validators;
注意:金鑰不應該公開。只有在演示中我們才使用這樣的金鑰。在實際專案中,傳送註冊請求以使節點成為驗證者。如果整個網路批准此請求,則該節點將成為驗證者,並將公鑰新增到列表中。
Config.js檔案
網路中的驗證者數量可以透過命令列傳遞,但更容易將其儲存在檔案中並在需要的地方匯入。
建立一個檔案config.js並建立三個變數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
};