NEO源码分析之DBFT共识协议 精选投稿

naoye 6月前 280

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;  //设置共识状态为 Initial
            PrevHash = Blockchain.Default.CurrentBlockHash;   //获取上一个区块的哈希
            BlockIndex = Blockchain.Default.Height + 1;  //新区块下标
            ViewNumber = 0;     //初始状态 视图编号为0
            Validators = 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); //间隔时间大于预定时间则立即发起共识
         else
           timer.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共识算法的容错能力,公式是f= [(n-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的全体议员数,如果满足条件,则在新视图周期里重新开始共识过程。

 zzzz

作者:廖京辉

本文由NEL内容奖励计划支持    


最后于 5月前 被naoye编辑 ,原因:
最新回复 (0)
全部楼主
返回