NEO DBFT共識(shí)算法源碼分析

這篇文章主要介紹“NEO DBFT共識(shí)算法源碼分析”的相關(guān)知識(shí)，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“NEO DBFT共識(shí)算法源碼分析”文章能幫助大家解決問題。

NEO DBFT共識(shí)算法

dbft改進(jìn)自算法pbft算法，pbft算法通過多次網(wǎng)絡(luò)請(qǐng)求確認(rèn)，最終獲得多數(shù)共識(shí)。其缺點(diǎn)在于隨著隨著節(jié)點(diǎn)的增加，網(wǎng)絡(luò)開銷呈指數(shù)級(jí)增長，網(wǎng)絡(luò)通信膨脹，難以快速達(dá)成一致。neo的解決方案是通過投票選取出一定數(shù)量的節(jié)點(diǎn)作為記賬人，由此減少網(wǎng)絡(luò)消耗又可以兼顧交易速度，這也是dbft中d的由來。

代碼結(jié)構(gòu)說明

├── Consensus
│   ├── ChangeView.cs           //viewchange 消息
│   ├── ConsensusContext.cs     //共識(shí)上下文
│   ├── ConsensusMessage.cs     //共識(shí)消息
│   ├── ConsensusMessageType.cs //共識(shí)消息類型 ChangeView/PrepareRequest/PrepareResponse
│   ├── ConsensusService.cs     //共識(shí)核心代碼    
│   ├── ConsensusState.cs       //節(jié)點(diǎn)共識(shí)狀態(tài)
│   ├── PrepareRequest.cs       //請(qǐng)求消息
│   └── PrepareResponse.cs      //簽名返回消息

共識(shí)狀態(tài)變化流程

• 1:開啟共識(shí)的節(jié)點(diǎn)分為兩大類，非記賬人和記賬人節(jié)點(diǎn)，非記賬人的不參與共識(shí)，記賬人參與共識(shí)流程

• 2:選擇議長，Neo議長產(chǎn)生機(jī)制是根據(jù)當(dāng)前塊高度和記賬人數(shù)量做MOD運(yùn)算得到，議長實(shí)際上按順序當(dāng)選

• 3:節(jié)點(diǎn)初始化，議長為primary節(jié)點(diǎn)，議員為backup節(jié)點(diǎn)。

• 4:滿足出塊條件后議長發(fā)送PrepareRequest

• 5:議員收到請(qǐng)求后，驗(yàn)證通過簽名發(fā)送PrepareResponse

• 6:記賬節(jié)點(diǎn)接收到PrepareResponse后，節(jié)點(diǎn)保存對(duì)方的簽名信息，檢查如果超過三分之二則發(fā)送 block

• 7:節(jié)點(diǎn)接收到block，PersistCompleted事件觸發(fā)后整體重新初始化，

共識(shí)上下文核心成員

        public const uint Version = 0;
        public ConsensusState State;       //節(jié)點(diǎn)當(dāng)前共識(shí)狀態(tài)
        public UInt256 PrevHash;
        public uint BlockIndex;            //塊高度
        public byte ViewNumber;            //試圖狀態(tài)
        public ECPoint[] Validators;       //記賬人     
        public int MyIndex;                //當(dāng)前記賬人次序
        public uint PrimaryIndex;          //當(dāng)前記賬的記賬人
        public uint Timestamp;
        public ulong Nonce;
        public UInt160 NextConsensus;      //共識(shí)標(biāo)識(shí)
        public UInt256[] TransactionHashes;
        public Dictionary<UInt256, Transaction> Transactions;
        public byte[][] Signatures;        //記賬人簽名
        public byte[] ExpectedView;        //記賬人試圖
        public KeyPair KeyPair;

        public int M => Validators.Length - (Validators.Length - 1) / 3;   //三分之二數(shù)量

ExpectedView 維護(hù)視圖狀態(tài)中，用于在議長無法正常工作時(shí)重新發(fā)起新一輪共識(shí)。

Signatures 用于維護(hù)共識(shí)過程中的確認(rèn)狀態(tài)。

節(jié)點(diǎn)共識(shí)狀態(tài)

    [Flags]
    internal enum ConsensusState : byte
    {
        Initial = 0x00,           //      0
        Primary = 0x01,           //      1
        Backup = 0x02,            //     10
        RequestSent = 0x04,       //    100
        RequestReceived = 0x08,   //   1000
        SignatureSent = 0x10,     //  10000
        BlockSent = 0x20,         // 100000
        ViewChanging = 0x40,      //1000000
    }

代理節(jié)點(diǎn)選擇

neo的dbft算法的delegate部分主要體現(xiàn)在一個(gè)函數(shù)上面,每次產(chǎn)生區(qū)塊后會(huì)重新排序資產(chǎn)，選擇前記賬人數(shù)量的節(jié)點(diǎn)出來參與下一輪共識(shí)。

    /// <summary>
        /// 獲取下一個(gè)區(qū)塊的記賬人列表
        /// </summary>
        /// <returns>返回一組公鑰，表示下一個(gè)區(qū)塊的記賬人列表</returns>
        public ECPoint[] GetValidators()
        {
            lock (_validators)
            {
                if (_validators.Count == 0)
                {
                    _validators.AddRange(GetValidators(Enumerable.Empty<Transaction>()));
                }
                return _validators.ToArray();
            }
        }

        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>();
			///更新賬號(hào)資產(chǎn)情況
            foreach (Transaction tx in others)
            {
                foreach (TransactionOutput output in tx.Outputs)
                {
                    AccountState account = accounts.GetAndChange(output.ScriptHash, () => new AccountState(output.ScriptHash));
                    if (account.Balances.ContainsKey(output.AssetId))
                        account.Balances[output.AssetId] += output.Value;
                    else
                        account.Balances[output.AssetId] = output.Value;
                    if (output.AssetId.Equals(GoverningToken.Hash) && account.Votes.Length > 0)
                    {
                        foreach (ECPoint pubkey in account.Votes)
                            validators.GetAndChange(pubkey, () => new ValidatorState(pubkey)).Votes += output.Value;
                        validators_count.GetAndChange().Votes[account.Votes.Length - 1] += output.Value;
                    }
                }
                foreach (var group in tx.Inputs.GroupBy(p => p.PrevHash))
                {
                    Transaction tx_prev = GetTransaction(group.Key, out int height);
                    foreach (CoinReference input in group)
                    {
                        TransactionOutput out_prev = tx_prev.Outputs[input.PrevIndex];
                        AccountState account = accounts.GetAndChange(out_prev.ScriptHash);
                        if (out_prev.AssetId.Equals(GoverningToken.Hash))
                        {
                            if (account.Votes.Length > 0)
                            {
                                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);
                                }
                                validators_count.GetAndChange().Votes[account.Votes.Length - 1] -= out_prev.Value;
                            }
                        }
                        account.Balances[out_prev.AssetId] -= out_prev.Value;
                    }
                }
                switch (tx)
                {
#pragma warning disable CS0612
                    case EnrollmentTransaction tx_enrollment:
                        validators.GetAndChange(tx_enrollment.PublicKey, () => new ValidatorState(tx_enrollment.PublicKey)).Registered = true;
                        break;
#pragma warning restore CS0612
                    case StateTransaction tx_state:
                        foreach (StateDescriptor descriptor in tx_state.Descriptors)
                            switch (descriptor.Type)
                            {
                                case StateType.Account:
                                    ProcessAccountStateDescriptor(descriptor, accounts, validators, validators_count);
                                    break;
                                case StateType.Validator:
                                    ProcessValidatorStateDescriptor(descriptor, validators);
                                    break;
                            }
                        break;
                }
            }
			//排序
            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);
        }

議長選擇

在初始化共識(shí)狀態(tài)的時(shí)候會(huì)設(shè)置PrimaryIndex，獲知當(dāng)前議長。原理就是簡單的MOD運(yùn)算。 這里有分為兩種情況，如果節(jié)點(diǎn)正常則直接塊高度和記賬人數(shù)量mod運(yùn)算即可，如果存在一場情況，則需要根據(jù)view_number進(jìn)行調(diào)整。

    //file /Consensus/ConsensusService.cs   InitializeConsensus方法 
    if (view_number == 0)
        context.Reset(wallet);
    else
        context.ChangeView(view_number);

    //file /Consensus/ConsensusContext.cs
    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);//當(dāng)前記賬人
        if (State == ConsensusState.Initial)
        {
            TransactionHashes = null;
            Signatures = new byte[Validators.Length][];
        }
        ExpectedView[MyIndex] = view_number;
        _header = null;
    }

    //file /Consensus/ConsensusContext.cs
    public void Reset(Wallet wallet)
    {
        State = ConsensusState.Initial;
        PrevHash = Blockchain.Default.CurrentBlockHash;
        BlockIndex = Blockchain.Default.Height + 1;
        ViewNumber = 0;
        Validators = Blockchain.Default.GetValidators();
        MyIndex = -1;
        PrimaryIndex = BlockIndex % (uint)Validators.Length; //當(dāng)前記賬人
        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;
    }

狀態(tài)初始化

如果是議長則狀態(tài)標(biāo)記為ConsensusState.Primary，同時(shí)改變定時(shí)器觸發(fā)事件，再上次出塊15s后觸發(fā)。議員則設(shè)置狀態(tài)為 ConsensusState.Backup，時(shí)間調(diào)整為30s后觸發(fā)，如果議長不能正常工作，則這個(gè)觸發(fā)器會(huì)開始起作用（具體后邊再詳細(xì)分析）。

    //file /Consensus/ConsensusContext.cs
    private void InitializeConsensus(byte view_number)
    {
        lock (context)
        {
            if (view_number == 0)
                context.Reset(wallet);
            else
                context.ChangeView(view_number);
            if (context.MyIndex < 0) return;
            Log($"initialize: height={context.BlockIndex} view={view_number} index={context.MyIndex} role={(context.MyIndex == context.PrimaryIndex ? ConsensusState.Primary : ConsensusState.Backup)}");
            if (context.MyIndex == context.PrimaryIndex)
            {
                context.State |= ConsensusState.Primary;
                if (!context.State.HasFlag(ConsensusState.SignatureSent))
                {
                    FillContext();  //生成mine區(qū)塊
                }
                if (context.TransactionHashes.Length > 1)
                {   //廣播自身的交易  
                    InvPayload invPayload = InvPayload.Create(InventoryType.TX, context.TransactionHashes.Skip(1).ToArray());
                    foreach (RemoteNode node in localNode.GetRemoteNodes())
                        node.EnqueueMessage("inv", invPayload);
                }
                timer_height = context.BlockIndex;
                timer_view = view_number;
                TimeSpan span = DateTime.Now - block_received_time;
                if (span >= Blockchain.TimePerBlock)
                    timer.Change(0, Timeout.Infinite);
                else
                    timer.Change(Blockchain.TimePerBlock - span, Timeout.InfiniteTimeSpan);
            }
            else
            {
                context.State = ConsensusState.Backup;
                timer_height = context.BlockIndex;
                timer_view = view_number;
                timer.Change(TimeSpan.FromSeconds(Blockchain.SecondsPerBlock << (view_number + 1)), Timeout.InfiniteTimeSpan);
            }
        }
    }

議長發(fā)起請(qǐng)求

議長到了該記賬的時(shí)間后，執(zhí)行下面方法，發(fā)送MakePrepareRequest請(qǐng)求，自身狀態(tài)轉(zhuǎn)變?yōu)镽equestSent，也設(shè)置了30s后重復(fù)觸發(fā)定時(shí)器（同樣也是再議長工作異常時(shí)起效）。

    //file /Consensus/ConsensusContext.cs
    private void OnTimeout(object state)
    {
        lock (context)
        {
            if (timer_height != context.BlockIndex || timer_view != context.ViewNumber) return;
            Log($"timeout: height={timer_height} view={timer_view} state={context.State}");
            if (context.State.HasFlag(ConsensusState.Primary) && !context.State.HasFlag(ConsensusState.RequestSent))
            {
                Log($"send perpare request: height={timer_height} view={timer_view}");
                context.State |= ConsensusState.RequestSent;
                if (!context.State.HasFlag(ConsensusState.SignatureSent))
                {
                    context.Timestamp = Math.Max(DateTime.Now.ToTimestamp(), Blockchain.Default.GetHeader(context.PrevHash).Timestamp + 1);
                    context.Signatures[context.MyIndex] = context.MakeHeader().Sign(context.KeyPair);
                }
                SignAndRelay(context.MakePrepareRequest());
                timer.Change(TimeSpan.FromSeconds(Blockchain.SecondsPerBlock << (timer_view + 1)), Timeout.InfiniteTimeSpan);
            }
            else if ((context.State.HasFlag(ConsensusState.Primary) && context.State.HasFlag(ConsensusState.RequestSent)) || context.State.HasFlag(ConsensusState.Backup))
            {
                RequestChangeView();
            }
        }
    }
    }

議員廣播簽名信息

議員接收到PrepareRequest，會(huì)對(duì)節(jié)點(diǎn)信息進(jìn)行驗(yàn)證，自身不存在的交易會(huì)去同步交易。交易同步完成后，驗(yàn)證通過會(huì)進(jìn)行發(fā)送PrepareResponse ，包含自己的簽名信息，表示自己已經(jīng)通過了節(jié)點(diǎn)驗(yàn)證。狀態(tài)轉(zhuǎn)變?yōu)镃onsensusState.SignatureSent。

    //file /Consensus/ConsensusContext.cs
    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;
        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))
                    return;
        }
        if (!AddTransaction(message.MinerTransaction, true)) return;
        if (context.Transactions.Count < context.TransactionHashes.Length)
        {
            UInt256[] hashes = context.TransactionHashes.Where(i => !context.Transactions.ContainsKey(i)).ToArray();
            LocalNode.AllowHashes(hashes);
            InvPayload msg = InvPayload.Create(InventoryType.TX, hashes);
            foreach (RemoteNode node in localNode.GetRemoteNodes())
                node.EnqueueMessage("getdata", msg);
        }
    }

    //file /Consensus/ConsensusContext.cs
    private bool AddTransaction(Transaction tx, bool verify)
    {
        if (Blockchain.Default.ContainsTransaction(tx.Hash) ||
            (verify && !tx.Verify(context.Transactions.Values)) ||
            !CheckPolicy(tx))
        {
            Log($"reject tx: {tx.Hash}{Environment.NewLine}{tx.ToArray().ToHexString()}");
            RequestChangeView();
            return false;
        }
        context.Transactions[tx.Hash] = tx;
        if (context.TransactionHashes.Length == context.Transactions.Count)
        {
            if (Blockchain.GetConsensusAddress(Blockchain.Default.GetValidators(context.Transactions.Values).ToArray()).Equals(context.NextConsensus))
            {
                Log($"send perpare response");
                context.State |= ConsensusState.SignatureSent;
                context.Signatures[context.MyIndex] = context.MakeHeader().Sign(context.KeyPair);
                SignAndRelay(context.MakePrepareResponse(context.Signatures[context.MyIndex]));
                CheckSignatures();
            }
            else
            {
                RequestChangeView();
                return false;
            }
        }
        return true;
    }

共識(shí)達(dá)成后廣播區(qū)塊

其他節(jié)點(diǎn)接收到PrepareResponse后，在自己的簽名列表中記錄對(duì)方的簽名信息，再檢查自己的簽名列表是否有超過三分之二的簽名了，有則判斷共識(shí)達(dá)成開始廣播生成的區(qū)塊。狀態(tài)狀變?yōu)镃onsensusState.BlockSent。

    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;
        }
    }

Blockchain_PersistCompleted后恢復(fù)狀態(tài)

區(qū)塊廣播后，節(jié)點(diǎn)接收到這個(gè)信息，會(huì)保存區(qū)塊，保存完成后觸發(fā)PersistCompleted事件，最終回到初始狀態(tài)，重新開始新一輪的共識(shí)。

    private void Blockchain_PersistCompleted(object sender, Block block)
    {
        Log($"persist block: {block.Hash}");
        block_received_time = DateTime.Now;
        InitializeConsensus(0);
    }

錯(cuò)誤分析

如果議長無法完成記賬任務(wù)

這種情況下議長在超出時(shí)間之后依然無法達(dá)成共識(shí)，此時(shí)議員會(huì)增長自身的ExpectedView值，并且廣播出去，如果檢查到三分之二的成員viewnumber都加了1,則在這些相同viewnumber的節(jié)點(diǎn)之間開始新一輪共識(shí)，重新選擇議長，發(fā)起共識(shí)。如果此時(shí)原來的議長恢復(fù)正常，time到時(shí)間后會(huì)增長自身的viewnumber，慢慢追上當(dāng)前的視圖狀態(tài)。

關(guān)于“NEO DBFT共識(shí)算法源碼分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。