2019獨角獸企業重金招聘Python工程師標準>>>
0x00 概論
不同于比特幣使用的工作量證明(PoW)來實現共識,NEO提出了DBFT共識算法。DBFT改良自股權證明算法(PoS),我沒有具體分析過PoS的源碼,所以暫時還不是很懂具體哪里做了改動,有興趣的同學可以看下NEO的官方文檔。本文主要內容集中在對共識協議源碼的分析,此外還會有對于一些理論的講解。關于NEO網絡通信部分源碼分析我還另外寫了一篇博客,所以本文中所有涉及到通信的內容我就不再贅述,有興趣的同學可以去看我的另一篇博客。
0x01 獲取議員名單
NEO的共識協議類似于西方國家的議會,每次區塊的生成都在議長主持下由議會成員共同協商生成新的區塊。NEO網絡節點分為兩種,一種為共識節點,另一種為普通節點。普通節點是不參與NEO新區快生成的,對應于普通人,共識節點參與共識的過程并且都有機會成為議長主持新區塊的生成,對應于議員。 看官方文檔似乎所有的共識節點都可以到NEO的服務器注冊為議員,但是貌似成為議員還是有條件的,據社區大佬說,你賬戶里至少也要由個把億才能成為議員,所以像我這樣的窮逼是沒希望了。但是在分析源碼的時候我發現似乎并不是這樣。源碼中在每輪共識開始的時候調用ConsensusContext.cs中的Reset方法,在 重置共識的時候會調用Blockchain.Default.GetValidators()來獲取議員列表,跟進去這個GetValidators()源碼:
源碼位置:neo/Core/BlockChain.cs
/// <summary>/// 獲取下一個區塊的記賬人列表/// </summary>/// <returns>返回一組公鑰,表示下一個區塊的記賬人列表</returns>public ECPoint[] GetValidators(){lock (_validators){if (_validators.Count == 0){_validators.AddRange(GetValidators(Enumerable.Empty<Transaction>()));}return _validators.ToArray();}}
發現這里是調用了內部的GetValidators(IEnumerable<Transaction> others)方法,但是這里有點意思,這里傳過去的參數,居然是個空的。再看這個內部的GetValidators方法:
源碼位置:neo/Core/BlockChain.cs
public virtual IEnumerable<ECPoint> GetValidators(IEnumerable<Transaction> others){DataCache<UInt160, AccountState> accounts = GetStates<UInt160, AccountState>();DataCache<ECPoint, ValidatorState> validators = GetStates<ECPoint, ValidatorState>();MetaDataCache<ValidatorsCountState> validators_count = GetMetaData<ValidatorsCountState>();foreach (Transaction tx in others){}int count = (int)validators_count.Get().Votes.Select((p, i) => new{Count = i,Votes = p}).Where(p => p.Votes > Fixed8.Zero).ToArray().WeightedFilter(0.25, 0.75, p => p.Votes.GetData(), (p, w) => new{p.Count,Weight = w}).WeightedAverage(p => p.Count, p => p.Weight);count = Math.Max(count, StandbyValidators.Length);HashSet<ECPoint> sv = new HashSet<ECPoint>(StandbyValidators);ECPoint[] pubkeys = validators.Find().Select(p => p.Value).Where(p => (p.Registered && p.Votes > Fixed8.Zero) || sv.Contains(p.PublicKey)).OrderByDescending(p => p.Votes).ThenBy(p => p.PublicKey).Select(p => p.PublicKey).Take(count).ToArray();IEnumerable<ECPoint> result;if (pubkeys.Length == count){result = pubkeys;}else{HashSet<ECPoint> hashSet = new HashSet<ECPoint>(pubkeys);for (int i = 0; i < StandbyValidators.Length && hashSet.Count < count; i++)hashSet.Add(StandbyValidators[i]);result = hashSet;}return result.OrderBy(p => p);}
我把第一個foreach循環中的代碼都刪掉了,因為明顯傳進來的others參數為0,所以循環體里的代碼根本不會有執行的機會。這個方法的返回值是result,它值的數據有兩個來源。第一個是pubkeys,pubkeys來自于本地緩存中的議員信息,這個信息是在區塊鏈同步的時候保存的,也就是說只要共識節點開始接入區塊鏈網絡進行區塊同步,就會獲取到議員信息。而如果沒有緩存議員信息或者緩存的議員信息丟失,就會使用內置的默認議員列表進行共識,之后再在共識的過程中緩存議員信息。 上面說到獲取議員信息有兩種途徑,第二種的使用內置默認議員列表是直接將配置文件protocol.json中的數據讀取到StandbyValidators字段中。接下來主要介紹第一種途徑。 GetValidators方法的第二行調用了GetStates,并且傳入類的類型是ValidatorState,這個方法位于LevelDBBlockChain.cs文件中,完整代碼如下:
源碼位置:neo/Implementations/BlockChains/LevelDB/LevelDBBlockChain.cs
public override DataCache<TKey, TValue> GetStates<TKey, TValue>(){Type t = typeof(TValue);if (t == typeof(AccountState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Account);if (t == typeof(UnspentCoinState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Coin);if (t == typeof(SpentCoinState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_SpentCoin);if (t == typeof(ValidatorState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Validator);if (t == typeof(AssetState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Asset);if (t == typeof(ContractState)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Contract);if (t == typeof(StorageItem)) return new DbCache<TKey, TValue>(db, DataEntryPrefix.ST_Storage);throw new NotSupportedException();}
可以看到這里是直接從leveldb的數據庫中讀取的議員數據。也就是說在讀取數據之前,應該要創建/打開數據庫才行,這部分的操作可以參考neo-cli項目,這個項目就在MainService類的OnStart方法中傳入了數據庫地址。 當然這只是從數據庫中獲取議員信息,向數據庫中存入議員信息的工作主要由LevelDBBlockChain.cs文件中的Persist(Block block) 方法負責,這個方法接收一個區塊類型作為參數,主要工作是將同步到的區塊信息解析保存。涉及到議員信息的關鍵代碼如下:
源碼位置:neo/Implementations/BlockChains/LevelDB/LevelDBBlockChain.cs/Persist
foreach (ECPoint pubkey in account.Votes){ValidatorState validator = validators.GetAndChange(pubkey);validator.Votes -= out_prev.Value;if (!validator.Registered && validator.Votes.Equals(Fixed8.Zero))validators.Delete(pubkey);}
通過調用GetAndChange方法將獲取到的議員賬戶添加到數據庫緩存中。
0x02 確定議長
共識節點通過調用ConsensusService類中的Start方法來開始參與共識。在Start方法中首先是注冊了消息接收、數據保存等的事件通知,之后調用InitializeConsensus開啟共識,InitializeConsensus方法接收一個整形參數,這個參數被稱為為視圖編號,具體視圖的定義可以去查看官方文檔,這里不做解釋。當傳入的視圖編號為0時,就意味是著一輪新的共識,需要重置共識狀態。重置共識狀態的代碼如下:
源碼位置:neo/Consenus/ConsensusContext.cs
/// <summary>/// 共識狀態重置,準備發起新一輪共識/// </summary>/// <param name="wallet">錢包</param>public void Reset(Wallet wallet){State = ConsensusState.Initial; //設置共識狀態為 InitialPrevHash = Blockchain.Default.CurrentBlockHash; //獲取上一個區塊的哈希BlockIndex = Blockchain.Default.Height + 1; //新區塊下標ViewNumber = 0; //初始狀態 視圖編號為0Validators = Blockchain.Default.GetValidators(); //獲取議員信息MyIndex = -1; //當前議員下標初始化PrimaryIndex = BlockIndex % (uint)Validators.Length; //確定議長 p = (h-v)mod n 此處v = 0 TransactionHashes = null;Signatures = new byte[Validators.Length][];ExpectedView = new byte[Validators.Length]; //用于保存眾議員當前視圖編號KeyPair = null;for (int i = 0; i < Validators.Length; i++){//獲取自己的議員編號以及密鑰WalletAccount account = wallet.GetAccount(Validators[i]);if (account?.HasKey == true){MyIndex = i;KeyPair = account.GetKey();break;}}_header = null;}}
在代碼中我添加了詳盡的注釋,確定議長的算法是當前區塊高度+1 再減去當前的視圖編號,結果mod上當前的議員人數,結果就是議長的下標。議員自己的編號則是自己在議員列表中的位置,因為這個位置的排序是根據每個議員的權重,所以理論上只要節點的議員成員是一致的,那么最終獲得的序列也是一致,也就是說每個議員的編號在所有的共識節點都是一致的。 在共識節點中,除了在共識重置的時候會確定議長之外,在每次更新本地視圖的時候也會重新確定議長:
源碼位置:neo/Consensus/ConsensusContex.cs
/// <summary>/// 更新共識視圖/// </summary>/// <param name="view_number">新的視圖編號</param>public void ChangeView(byte view_number){int p = ((int)BlockIndex - view_number) % Validators.Length;//設置共識狀態為已發送簽名State &= ConsensusState.SignatureSent;ViewNumber = view_number;//議長編號PrimaryIndex = p >= 0 ? (uint)p : (uint)(p + Validators.Length);if (State == ConsensusState.Initial){TransactionHashes = null;Signatures = new byte[Validators.Length][];}_header = null;}
0x03 議長發起共識
議長在更新完視圖編號后,如果當前時間距離上次寫入新區塊的時間超過了預定的每輪共識的間隔時間(15s)則立即開始新一輪的共識,否則等到間隔時間后再發起共識,時間控制代碼如下: 源碼位置:neo/Consensus/ConsencusService.cs/InitializeConsensus
//議長發起共識時間控制TimeSpan span = DateTime.Now - block_received_time;if (span >= Blockchain.TimePerBlock)timer.Change(0, Timeout.Infinite); //間隔時間大于預定時間則立即發起共識elsetimer.Change(Blockchain.TimePerBlock - span, Timeout.InfiniteTimeSpan); //定時執行
議長進行共識的函數是OnTimeout,由定時器定時執行。下面是議長發起共識的核心代碼:
源碼位置:neo/Consencus/ConsensusService.cs/OnTimeOut
context.Timestamp = Math.Max(DateTime.Now.ToTimestamp(), Blockchain.Default.GetHeader(context.PrevHash).Timestamp + 1);context.Nonce = GetNonce();//生成區塊隨機數//獲取本地內存中的交易列表List<Transaction> transactions = LocalNode.GetMemoryPool().Where(p => CheckPolicy(p)).ToList();//如果內存中緩存的交易信息數量大于區塊最大交易數,則對內存中的交易信息進行排序 每字節手續費 越高越先確認交易if (transactions.Count >= Settings.Default.MaxTransactionsPerBlock)transactions = transactions.OrderByDescending(p => p.NetworkFee / p.Size).Take(Settings.Default.MaxTransactionsPerBlock - 1).ToList();//添加手續費交易transactions.Insert(0, CreateMinerTransaction(transactions, context.BlockIndex, context.Nonce));context.TransactionHashes = transactions.Select(p => p.Hash).ToArray();context.Transactions = transactions.ToDictionary(p => p.Hash);//獲取新區塊記賬人合約地址context.NextConsensus = Blockchain.GetConsensusAddress(Blockchain.Default.GetValidators(transactions).ToArray());//生成新區塊并簽名context.Signatures[context.MyIndex] = context.MakeHeader().Sign(context.KeyPair);
議長將本地的交易生成新的Header并簽名,然后將這個Header發送PrepareRequest廣播給網絡中的議員。
0x04 議員參與共識
議員在收到PrepareRequest廣播之后會觸發OnPrepareReceived方法:
源碼位置:neo/Consensus/ConsensusService.cs
/// <summary>/// 收到議長共識請求/// </summary>/// <param name="payload">議長的共識參數</param>/// <param name="message"></param>private void OnPrepareRequestReceived(ConsensusPayload payload, PrepareRequest message){Log($"{nameof(OnPrepareRequestReceived)}: height={payload.BlockIndex} view={message.ViewNumber} index={payload.ValidatorIndex} tx={message.TransactionHashes.Length}");if (!context.State.HasFlag(ConsensusState.Backup) || context.State.HasFlag(ConsensusState.RequestReceived))//當前不處于回退狀態或者已經收到了重置請求return;if (payload.ValidatorIndex != context.PrimaryIndex) return;//只接受議長發起的共識請求if (payload.Timestamp <= Blockchain.Default.GetHeader(context.PrevHash).Timestamp || payload.Timestamp > DateTime.Now.AddMinutes(10).ToTimestamp()){Log($"Timestamp incorrect: {payload.Timestamp}");return;}context.State |= ConsensusState.RequestReceived;//設置狀態為收到議長共識請求context.Timestamp = payload.Timestamp; //時間戳同步context.Nonce = message.Nonce; //區塊隨機數同步context.NextConsensus = message.NextConsensus; context.TransactionHashes = message.TransactionHashes; //交易哈希context.Transactions = new Dictionary<UInt256, Transaction>();//議長公鑰驗證if (!Crypto.Default.VerifySignature(context.MakeHeader().GetHashData(), message.Signature, context.Validators[payload.ValidatorIndex].EncodePoint(false))) return;//添加議長簽名到議員簽名列表context.Signatures = new byte[context.Validators.Length][];context.Signatures[payload.ValidatorIndex] = message.Signature;//將內存中緩存的交易添加到共識的context中Dictionary<UInt256, Transaction> mempool = LocalNode.GetMemoryPool().ToDictionary(p => p.Hash);foreach (UInt256 hash in context.TransactionHashes.Skip(1)){if (mempool.TryGetValue(hash, out Transaction tx))if (!AddTransaction(tx, false))//從緩存隊列中讀取添加到contex中return;}if (!AddTransaction(message.MinerTransaction, true)) return; //添加分配字節費的交易 礦工手續費交易LocalNode.AllowHashes(context.TransactionHashes.Except(context.Transactions.Keys));if (context.Transactions.Count < context.TransactionHashes.Length)localNode.SynchronizeMemoryPool();}
議員在收到議長共識請求之后,首先使用議長的公鑰對收到的共識信息進行驗證,在驗證通過后將議長的簽名添加到簽名列表中。然后將內存中緩存并在議長Header的交易哈希列表中的交易添加到context里。 這里需要講一下這個從內存中添加交易信息到context中的方法 AddTransaction。這個方法在每次添加交易之后都會比較當前context中的交易筆數是否和從議長那里獲取的交易哈希數相同,如果相同而且記賬人合約地址驗證通過,則廣播自己的簽名到網絡中,這部分核心代碼如下:
源碼位置:neo/Consensus/ConsensusService.cs/AddTransaction
//設置共識狀態為已發送簽名context.State |= ConsensusState.SignatureSent;//添加本地簽名到簽名列表context.Signatures[context.MyIndex] = context.MakeHeader().Sign(context.KeyPair);//廣播共識響應SignAndRelay(context.MakePrepareResponse(context.Signatures[context.MyIndex]));//檢查簽名狀態是否符合共識要求CheckSignatures();
因為所有的議員都需要同步各個共識節點的簽名,所以議員節點也需要監聽網絡中別的節點對議長共識信息的響應并記錄簽名信息。在每次監聽到共識響應并記錄了收到的簽名信息之后,節點需要調用CheckSignatures方法對當前收到的簽名信息是否合法進行判斷,CheckSignatures代碼如下:
源碼位置:neo/Consensus/ConsensusService.cs
/// <summary>/// 驗證共識協商結果/// </summary>private void CheckSignatures(){//驗證當前已進行的協商的共識節點數是否合法if (context.Signatures.Count(p => p != null) >= context.M && context.TransactionHashes.All(p => context.Transactions.ContainsKey(p))){//建立合約Contract contract = Contract.CreateMultiSigContract(context.M, context.Validators);//創建新區塊Block block = context.MakeHeader();//設置區塊參數ContractParametersContext sc = new ContractParametersContext(block);for (int i = 0, j = 0; i < context.Validators.Length && j < context.M; i++)if (context.Signatures[i] != null){sc.AddSignature(contract, context.Validators[i], context.Signatures[i]);j++;}//獲取用于驗證區塊的腳本sc.Verifiable.Scripts = sc.GetScripts();block.Transactions = context.TransactionHashes.Select(p => context.Transactions[p]).ToArray();Log($"relay block: {block.Hash}");//廣播新區塊if (!localNode.Relay(block))Log($"reject block: {block.Hash}");//設置當前共識狀態為新區塊已廣播context.State |= ConsensusState.BlockSent;}}
CheckSignatures方法里首先是對當前簽名數的合法性判斷。也就是以獲取的合法簽名數量需要不小于M。M這個值的獲取在ConsensusContext類中:
public int M => Validators.Length - (Validators.Length - 1) / 3;
這個值的獲取涉及到NEO共識算法的容錯能力,公式是? = ? (??1) / 3 ?,理解的話就是只要有超過網絡2/3的共識節點是一致的,那么這個結果就是可信的。這個理解起來不是很難,想看分析的話可以參考官方白皮書。也就是說,只要獲取到的簽名數量合法了,當前節點就可以根據已有的信息生成新的區塊并向網絡中進行廣播。
0x05 視圖更新
我個人感覺NEO的共識協議里最雞賊的就是這個視圖的概念了。因為NEO網絡的共識間隔是用定時任務來做的,而不是根據全網算力在數學意義上保證每個區塊生成的大概時間。每輪的共識都是由當前選定的議長來發起,這就有個很大的問題,如果當前選定的議長剛好是個大壞蛋怎么辦,如果這個議長一直不發起共識或者故意發起錯誤的共識信息導致本輪共識無法最終完成怎么辦?為了解決這個問題,視圖概念被引入,在一個視圖生存周期完成的時候,如果共識還沒有被達成,則議員會發送廣播請求進入下一個視圖周期并重新選擇議長,當請求更新視圖的請求大于議員數量的2/3的時候,全網達成共識進入下一個視圖周期重新開始共識過程。議長的選定算法和視圖的編號有關系,這保證了每輪視圖選定的議長不會是同一個。 視圖的生存時間是t*2^(view_number+1),其中t是默認的區塊生成時間間隔,view_number是當前視圖編號。議員在每次共識開始的時候進入編號為0的視圖周期,如果當前周期完成的時候共識沒有達成,則視圖編號+1,并進入下一個視圖周期。定義視圖生存時間的代碼在ConsensusServer類的InitializeConsensus方法中:
源碼位置:neo/Consensus/ConsensusService.cs/InitializeConsensus
context.State = ConsensusState.Backup;timer_height = context.BlockIndex;timer_view = view_number;//議員超時控制 t*2^(view_number+1)timer.Change(TimeSpan.FromSeconds(Blockchain.SecondsPerBlock << (view_number + 1)), Timeout.InfiniteTimeSpan);
當一輪視圖周期完成的時候,如果共識沒有達成則發出更新視圖請求:
源碼位置:neo/Consensus/ConsensusService.cs
/// <summary>/// 發送更新視圖請求/// </summary>private void RequestChangeView(){context.State |= ConsensusState.ViewChanging;context.ExpectedView[context.MyIndex]++;Log($"request change view: height={context.BlockIndex} view={context.ViewNumber} nv={context.ExpectedView[context.MyIndex]} state={context.State}");//重置視圖周期timer.Change(TimeSpan.FromSeconds(Blockchain.SecondsPerBlock << (context.ExpectedView[context.MyIndex] + 1)), Timeout.InfiniteTimeSpan);//簽名并廣播更新視圖消息SignAndRelay(context.MakeChangeView());//檢查是否可以更新視圖CheckExpectedView(context.ExpectedView[context.MyIndex]);}
更新視圖會把當前期望視圖+1并且廣播更新視圖的請求給所有的議員。這里需要注意的是,在當前節點發送了更新視圖的請求之后,節點的當前視圖編號并沒有改變,而只是改變了期望視圖編號。 其他議員在收到更新視圖的廣播后會觸發OnChangeViewReceived方法來更新自己的議員期望視圖列表。
源碼位置:neo/Consensus/ConsensusService.cs
/// <summary>/// 議員收到更新視圖的請求/// </summary>/// <param name="payload"></param>/// <param name="message"></param>private void OnChangeViewReceived(ConsensusPayload payload, ChangeView message){Log($"{nameof(OnChangeViewReceived)}: height={payload.BlockIndex} view={message.ViewNumber} index={payload.ValidatorIndex} nv={message.NewViewNumber}");//消息中新視圖編號比當前所記錄的視圖編號還小則為過時消息if (message.NewViewNumber <= context.ExpectedView[payload.ValidatorIndex])return;//更新目標議員期望視圖編號context.ExpectedView[payload.ValidatorIndex] = message.NewViewNumber;//檢查是否符合更新視圖要求CheckExpectedView(message.NewViewNumber);}
在每次收到更新視圖請求之后都需要檢查一下當前收到的請求數量是不是大于2/3的全體議員數,如果滿足條件,則在新視圖周期里重新開始共識過程。
捐贈地址(NEO):ASCjW4xpfr8kyVHY1J2PgvcgFbPYa1qX7F