consensus/consensus/dpos/dpos.go

   1 package dpos
   2
   3 import (
   4         "bytes"
   5         "encoding/json"
   6         "errors"
   7         "math/big"
   8         "sync"
   9         "time"
  10
  11         lru "github.com/hashicorp/golang-lru"
  12         log "github.com/sirupsen/logrus"
  13         "github.com/vapor/chain"
  14         "github.com/vapor/common"
  15         "github.com/vapor/config"
  16         "github.com/vapor/consensus"
  17         "github.com/vapor/crypto"
  18         "github.com/vapor/crypto/ed25519/chainkd"
  19         "github.com/vapor/protocol"
  20         "github.com/vapor/protocol/bc"
  21         "github.com/vapor/protocol/bc/types"
  22         "github.com/vapor/protocol/vm/vmutil"
  23 )
  24
  25 const (
  26         inMemorySnapshots  = 128             // Number of recent vote snapshots to keep in memory
  27         inMemorySignatures = 4096            // Number of recent block signatures to keep in memory
  28         secondsPerYear     = 365 * 24 * 3600 // Number of seconds for one year
  29         checkpointInterval = 360             // About N hours if config.period is N
  30         module             = "dpos"
  31 )
  32
  33 //delegated-proof-of-stake protocol constants.
  34 var (
  35         SignerBlockReward     = big.NewInt(5e+18) // Block reward in wei for successfully mining a block first year
  36         defaultEpochLength    = uint64(3000000)   // Default number of blocks after which vote's period of validity
  37         defaultBlockPeriod    = uint64(3)         // Default minimum difference between two consecutive block's timestamps
  38         defaultMaxSignerCount = uint64(21)        //
  39         //defaultMinVoterBalance           = new(big.Int).Mul(big.NewInt(10000), big.NewInt(1e+18))
  40         defaultMinVoterBalance           = uint64(0)
  41         extraVanity                      = 32            // Fixed number of extra-data prefix bytes reserved for signer vanity
  42         extraSeal                        = 65            // Fixed number of extra-data suffix bytes reserved for signer seal
  43         defaultDifficulty                = big.NewInt(1) // Default difficulty
  44         defaultLoopCntRecalculateSigners = uint64(10)    // Default loop count to recreate signers from top tally
  45         minerRewardPerThousand           = uint64(618)   // Default reward for miner in each block from block reward (618/1000)
  46         candidateNeedPD                  = false         // is new candidate need Proposal & Declare process
  47 )
  48
  49 var (
  50         // errUnknownBlock is returned when the list of signers is requested for a block
  51         // that is not part of the local blockchain.
  52         errUnknownBlock = errors.New("unknown block")
  53
  54         // errMissingVanity is returned if a block's extra-data section is shorter than
  55         // 32 bytes, which is required to store the signer vanity.
  56         errMissingVanity = errors.New("extra-data 32 byte vanity prefix missing")
  57
  58         // errMissingSignature is returned if a block's extra-data section doesn't seem
  59         // to contain a 65 byte secp256k1 signature.
  60         errMissingSignature = errors.New("extra-data 65 byte suffix signature missing")
  61
  62         // errInvalidMixDigest is returned if a block's mix digest is non-zero.
  63         errInvalidMixDigest = errors.New("non-zero mix digest")
  64
  65         // errInvalidUncleHash is returned if a block contains an non-empty uncle list.
  66         errInvalidUncleHash = errors.New("non empty uncle hash")
  67
  68         // ErrInvalidTimestamp is returned if the timestamp of a block is lower than
  69         // the previous block's timestamp + the minimum block period.
  70         ErrInvalidTimestamp = errors.New("invalid timestamp")
  71
  72         // errInvalidVotingChain is returned if an authorization list is attempted to
  73         // be modified via out-of-range or non-contiguous headers.
  74         errInvalidVotingChain = errors.New("invalid voting chain")
  75
  76         // errUnauthorized is returned if a header is signed by a non-authorized entity.
  77         errUnauthorized = errors.New("unauthorized")
  78
  79         // errPunishedMissing is returned if a header calculate punished signer is wrong.
  80         errPunishedMissing = errors.New("punished signer missing")
  81
  82         // errWaitTransactions is returned if an empty block is attempted to be sealed
  83         // on an instant chain (0 second period). It's important to refuse these as the
  84         // block reward is zero, so an empty block just bloats the chain... fast.
  85         errWaitTransactions = errors.New("waiting for transactions")
  86
  87         // errUnclesNotAllowed is returned if uncles exists
  88         errUnclesNotAllowed = errors.New("uncles not allowed")
  89
  90         // errCreateSignerQueueNotAllowed is returned if called in (block number + 1) % maxSignerCount != 0
  91         errCreateSignerQueueNotAllowed = errors.New("create signer queue not allowed")
  92
  93         // errInvalidSignerQueue is returned if verify SignerQueue fail
  94         errInvalidSignerQueue = errors.New("invalid signer queue")
  95
  96         // errSignerQueueEmpty is returned if no signer when calculate
  97         errSignerQueueEmpty = errors.New("signer queue is empty")
  98 )
  99
 100 type Dpos struct {
 101         config     *config.DposConfig // Consensus engine configuration parameters
 102         store      protocol.Store     // Database to store and retrieve snapshot checkpoints
 103         recents    *lru.ARCCache      // Snapshots for recent block to speed up reorgs
 104         signatures *lru.ARCCache      // Signatures of recent blocks to speed up mining
 105         signer     string             // Ethereum address of the signing key
 106         lock       sync.RWMutex       // Protects the signer fields
 107         lcsc       uint64             // Last confirmed side chain
 108 }
 109
 110 //
 111 func ecrecover(header *types.BlockHeader, sigcache *lru.ARCCache, c chain.Chain) (string, error) {
 112         xpub := &chainkd.XPub{}
 113         xpub.UnmarshalText(header.Coinbase)
 114         derivedPK := xpub.PublicKey()
 115         pubHash := crypto.Ripemd160(derivedPK)
 116         address, err := common.NewAddressWitnessPubKeyHash(pubHash, &consensus.ActiveNetParams)
 117         if err != nil {
 118                 return "", err
 119         }
 120
 121         return address.EncodeAddress(), nil
 122 }
 123
 124 //
 125 func New(config *config.DposConfig, store protocol.Store) *Dpos {
 126         conf := *config
 127         if conf.Epoch == 0 {
 128                 conf.Epoch = defaultEpochLength
 129         }
 130         if conf.Period == 0 {
 131                 conf.Period = defaultBlockPeriod
 132         }
 133         if conf.MaxSignerCount == 0 {
 134                 conf.MaxSignerCount = defaultMaxSignerCount
 135         }
 136         if conf.MinVoterBalance == 0 {
 137                 conf.MinVoterBalance = defaultMinVoterBalance
 138         }
 139         // Allocate the snapshot caches and create the engine
 140         recents, _ := lru.NewARC(inMemorySnapshots)
 141         signatures, _ := lru.NewARC(inMemorySignatures)
 142         return &Dpos{
 143                 config:     &conf,
 144                 store:      store,
 145                 recents:    recents,
 146                 signatures: signatures,
 147         }
 148 }
 149
 150 // Authorize injects a private key into the consensus engine to mint new blocks with.
 151 func (d *Dpos) Authorize(signer string) {
 152         d.lock.Lock()
 153         defer d.lock.Unlock()
 154         d.signer = signer
 155 }
 156
 157 func (d *Dpos) VerifySeal(c chain.Chain, header *types.BlockHeader) error {
 158         return d.verifyCascadingFields(c, header, nil)
 159 }
 160
 161 func (d *Dpos) verifyCascadingFields(c chain.Chain, header *types.BlockHeader, parents []*types.BlockHeader) error {
 162         // The genesis block is the always valid dead-end
 163         height := header.Height
 164         if height == 0 {
 165                 return nil
 166         }
 167
 168         var (
 169                 parent *types.BlockHeader
 170                 err    error
 171         )
 172
 173         if len(parents) > 0 {
 174                 parent = parents[len(parents)-1]
 175         } else {
 176                 parent, err = c.GetHeaderByHeight(height - 1)
 177                 if err != nil {
 178                         return err
 179                 }
 180         }
 181
 182         if parent == nil {
 183                 return errors.New("unknown ancestor")
 184         }
 185
 186         if _, err = d.snapshot(c, height-1, header.PreviousBlockHash, parents, nil, defaultLoopCntRecalculateSigners); err != nil {
 187                 return err
 188         }
 189
 190         return d.verifySeal(c, header, parents)
 191 }
 192
 193 // verifySeal checks whether the signature contained in the header satisfies the
 194 // consensus protocol requirements. The method accepts an optional list of parent
 195 // headers that aren't yet part of the local blockchain to generate the snapshots
 196 // from.
 197 func (d *Dpos) verifySeal(c chain.Chain, header *types.BlockHeader, parents []*types.BlockHeader) error {
 198         height := header.Height
 199         if height == 0 {
 200                 return errUnknownBlock
 201         }
 202         // Retrieve the snapshot needed to verify this header and cache it
 203         snap, err := d.snapshot(c, height-1, header.PreviousBlockHash, parents, nil, defaultLoopCntRecalculateSigners)
 204         if err != nil {
 205                 return err
 206         }
 207
 208         signer := ""
 209
 210         if height > d.config.MaxSignerCount {
 211                 var (
 212                         parent *types.BlockHeader
 213                         err    error
 214                 )
 215                 if len(parents) > 0 {
 216                         parent = parents[len(parents)-1]
 217                 } else {
 218                         if parent, err = c.GetHeaderByHeight(height - 1); err != nil {
 219                                 return err
 220                         }
 221                 }
 222
 223                 //parent
 224                 xpub := &chainkd.XPub{}
 225                 xpub.UnmarshalText(parent.Coinbase)
 226                 derivedPK := xpub.PublicKey()
 227                 pubHash := crypto.Ripemd160(derivedPK)
 228                 parentCoinbase, err := common.NewAddressWitnessPubKeyHash(pubHash, &consensus.ActiveNetParams)
 229                 if err != nil {
 230                         return err
 231                 }
 232
 233                 //current
 234                 xpub.UnmarshalText(header.Coinbase)
 235                 derivedPK = xpub.PublicKey()
 236                 pubHash = crypto.Ripemd160(derivedPK)
 237                 currentCoinbase, err := common.NewAddressWitnessPubKeyHash(pubHash, &consensus.ActiveNetParams)
 238                 if err != nil {
 239                         return err
 240                 }
 241                 signer = currentCoinbase.EncodeAddress()
 242
 243                 parentHeaderExtra := HeaderExtra{}
 244                 if err = json.Unmarshal(parent.Extra[extraVanity:len(parent.Extra)-extraSeal], &parentHeaderExtra); err != nil {
 245                         return err
 246                 }
 247
 248                 currentHeaderExtra := HeaderExtra{}
 249                 if err = json.Unmarshal(header.Extra[extraVanity:len(header.Extra)-extraSeal], &currentHeaderExtra); err != nil {
 250                         return err
 251                 }
 252
 253                 // verify signerqueue
 254                 if height%d.config.MaxSignerCount == 0 {
 255                         err := snap.verifySignerQueue(currentHeaderExtra.SignerQueue)
 256                         if err != nil {
 257                                 return err
 258                         }
 259
 260                 } else {
 261                         for i := 0; i < int(d.config.MaxSignerCount); i++ {
 262                                 if parentHeaderExtra.SignerQueue[i] != currentHeaderExtra.SignerQueue[i] {
 263                                         return errInvalidSignerQueue
 264                                 }
 265                         }
 266                 }
 267                 // verify missing signer for punish
 268                 parentSignerMissing := getSignerMissing(parentCoinbase.EncodeAddress(), currentCoinbase.EncodeAddress(), parentHeaderExtra)
 269                 if len(parentSignerMissing) != len(currentHeaderExtra.SignerMissing) {
 270                         return errPunishedMissing
 271                 }
 272                 for i, signerMissing := range currentHeaderExtra.SignerMissing {
 273                         if parentSignerMissing[i] != signerMissing {
 274                                 return errPunishedMissing
 275                         }
 276                 }
 277
 278         }
 279
 280         if !snap.inturn(signer, header.Timestamp) {
 281                 return errUnauthorized
 282         }
 283
 284         return nil
 285 }
 286
 287 // Prepare implements consensus.Engine, preparing all the consensus fields of the header for running the transactions on top.
 288 func (d *Dpos) Prepare(c chain.Chain, header *types.BlockHeader) error {
 289         if d.config.GenesisTimestamp < uint64(time.Now().Unix()) {
 290                 return nil
 291         }
 292
 293         if header.Height == 1 {
 294                 for {
 295                         delay := time.Unix(int64(d.config.GenesisTimestamp-2), 0).Sub(time.Now())
 296                         if delay <= time.Duration(0) {
 297                                 log.WithFields(log.Fields{"module": module, "time": time.Now()}).Info("Ready for seal block")
 298                                 break
 299                         } else if delay > time.Duration(d.config.Period)*time.Second {
 300                                 delay = time.Duration(d.config.Period) * time.Second
 301                         }
 302                         log.WithFields(log.Fields{"module": module, "delay": time.Duration(time.Unix(int64(d.config.GenesisTimestamp-2), 0).Sub(time.Now()))}).Info("Waiting for seal block")
 303                         select {
 304                         case <-time.After(delay):
 305                                 continue
 306                         }
 307                 }
 308         }
 309         return nil
 310 }
 311
 312 func (d *Dpos) Finalize(c chain.Chain, header *types.BlockHeader, txs []*bc.Tx) error {
 313         height := header.Height
 314         parent, err := c.GetHeaderByHeight(height - 1)
 315         if parent == nil {
 316                 return err
 317         }
 318         //parent
 319         var xpub chainkd.XPub
 320         xpub.UnmarshalText(parent.Coinbase)
 321         pubHash := crypto.Ripemd160(xpub.PublicKey())
 322         parentCoinbase, err := common.NewAddressWitnessPubKeyHash(pubHash, &consensus.ActiveNetParams)
 323         if err != nil {
 324                 return err
 325         }
 326
 327         //current
 328         xpub.UnmarshalText(header.Coinbase)
 329         pubHash = crypto.Ripemd160(xpub.PublicKey())
 330         currentCoinbase, err := common.NewAddressWitnessPubKeyHash(pubHash, &consensus.ActiveNetParams)
 331         if err != nil {
 332                 return err
 333         }
 334
 335         //header.Timestamp
 336         t := new(big.Int).Add(new(big.Int).SetUint64(parent.Timestamp), new(big.Int).SetUint64(d.config.Period))
 337         header.Timestamp = t.Uint64()
 338
 339         if header.Timestamp < uint64(time.Now().Unix()) {
 340                 header.Timestamp = uint64(time.Now().Unix())
 341         }
 342
 343         if len(header.Extra) < extraVanity {
 344                 header.Extra = append(header.Extra, bytes.Repeat([]byte{0x00}, extraVanity-len(header.Extra))...)
 345         }
 346
 347         header.Extra = header.Extra[:extraVanity]
 348         // genesisVotes write direct into snapshot, which number is 1
 349         var genesisVotes []*Vote
 350         parentHeaderExtra := HeaderExtra{}
 351         currentHeaderExtra := HeaderExtra{}
 352         if height == 1 {
 353                 alreadyVote := make(map[string]struct{})
 354                 for _, voter := range d.config.SelfVoteSigners {
 355                         if _, ok := alreadyVote[voter]; !ok {
 356                                 genesisVotes = append(genesisVotes, &Vote{
 357                                         Voter:     voter,
 358                                         Candidate: voter,
 359                                         Stake:     0,
 360                                         //Stake:     state.GetBalance(voter),
 361                                 })
 362                                 alreadyVote[voter] = struct{}{}
 363                         }
 364                 }
 365         } else {
 366                 parentHeaderExtraByte := parent.Extra[extraVanity : len(parent.Extra)-extraSeal]
 367                 if err := json.Unmarshal(parentHeaderExtraByte, &parentHeaderExtra); err != nil {
 368                         return err
 369                 }
 370                 currentHeaderExtra.ConfirmedBlockNumber = parentHeaderExtra.ConfirmedBlockNumber
 371                 currentHeaderExtra.SignerQueue = parentHeaderExtra.SignerQueue
 372                 currentHeaderExtra.LoopStartTime = parentHeaderExtra.LoopStartTime
 373                 currentHeaderExtra.SignerMissing = getSignerMissing(parentCoinbase.EncodeAddress(), currentCoinbase.EncodeAddress(), parentHeaderExtra)
 374         }
 375
 376         // calculate votes write into header.extra
 377         currentHeaderExtra, err = d.processCustomTx(currentHeaderExtra, c, header, txs)
 378         if err != nil {
 379                 return err
 380         }
 381         // Assemble the voting snapshot to check which votes make sense
 382         snap, err := d.snapshot(c, height-1, header.PreviousBlockHash, nil, genesisVotes, defaultLoopCntRecalculateSigners)
 383         if err != nil {
 384                 return err
 385         }
 386
 387         currentHeaderExtra.ConfirmedBlockNumber = snap.getLastConfirmedBlockNumber(currentHeaderExtra.CurrentBlockConfirmations).Uint64()
 388         // write signerQueue in first header, from self vote signers in genesis block
 389         if height == 1 {
 390                 currentHeaderExtra.LoopStartTime = d.config.GenesisTimestamp
 391                 for i := 0; i < int(d.config.MaxSignerCount); i++ {
 392                         currentHeaderExtra.SignerQueue = append(currentHeaderExtra.SignerQueue, d.config.SelfVoteSigners[i%len(d.config.SelfVoteSigners)])
 393                 }
 394         }
 395         if height%d.config.MaxSignerCount == 0 {
 396                 currentHeaderExtra.LoopStartTime = currentHeaderExtra.LoopStartTime + d.config.Period*d.config.MaxSignerCount
 397                 // create random signersQueue in currentHeaderExtra by snapshot.Tally
 398                 currentHeaderExtra.SignerQueue = []string{}
 399                 newSignerQueue, err := snap.createSignerQueue()
 400                 if err != nil {
 401                         return err
 402                 }
 403
 404                 currentHeaderExtra.SignerQueue = newSignerQueue
 405
 406         }
 407         // encode header.extra
 408         currentHeaderExtraEnc, err := json.Marshal(currentHeaderExtra)
 409         if err != nil {
 410                 return err
 411         }
 412         header.Extra = append(header.Extra, currentHeaderExtraEnc...)
 413         header.Extra = append(header.Extra, make([]byte, extraSeal)...)
 414         return nil
 415 }
 416
 417 func (d *Dpos) Seal(c chain.Chain, block *types.Block) (*types.Block, error) {
 418         header := block.BlockHeader
 419         height := header.Height
 420         if height == 0 {
 421                 return nil, errUnknownBlock
 422         }
 423
 424         if d.config.Period == 0 && len(block.Transactions) == 0 {
 425                 return nil, errWaitTransactions
 426         }
 427         // Bail out if we're unauthorized to sign a block
 428         snap, err := d.snapshot(c, height-1, header.PreviousBlockHash, nil, nil, defaultLoopCntRecalculateSigners)
 429         if err != nil {
 430                 return nil, err
 431         }
 432         if !snap.inturn(d.signer, header.Timestamp) {
 433                 return nil, errUnauthorized
 434         }
 435
 436         var xPrv chainkd.XPrv
 437         if config.CommonConfig.Consensus.Dpos.XPrv == "" {
 438                 return nil, errors.New("Signer is empty")
 439         }
 440         xPrv.UnmarshalText([]byte(config.CommonConfig.Consensus.Dpos.XPrv))
 441         sign := xPrv.Sign(block.BlockCommitment.TransactionsMerkleRoot.Bytes())
 442         pubHash := crypto.Ripemd160(xPrv.XPub().PublicKey())
 443
 444         control, err := vmutil.P2WPKHProgram([]byte(pubHash))
 445         if err != nil {
 446                 return nil, err
 447         }
 448
 449         block.Proof = types.Proof{Sign: sign, ControlProgram: control}
 450         return block, nil
 451 }
 452
 453 func (d *Dpos) IsSealer(c chain.Chain, hash bc.Hash, header *types.BlockHeader, headerTime uint64) (bool, error) {
 454         var (
 455                 snap    *Snapshot
 456                 headers []*types.BlockHeader
 457         )
 458         h := hash
 459         height := header.Height
 460         for snap == nil {
 461                 // If an in-memory snapshot was found, use that
 462                 if s, ok := d.recents.Get(h); ok {
 463                         snap = s.(*Snapshot)
 464                         break
 465                 }
 466                 // If an on-disk checkpoint snapshot can be found, use that
 467                 if height%checkpointInterval == 0 {
 468                         if s, err := loadSnapshot(d.config, d.signatures, d.store, h); err == nil {
 469                                 log.WithFields(log.Fields{"func": "IsSealer", "number": height, "hash": h}).Warn("Loaded voting snapshot from disk")
 470                                 snap = s
 471                                 break
 472                         } else {
 473                                 log.Warn("loadSnapshot:", err)
 474                         }
 475                 }
 476
 477                 if height == 0 {
 478                         genesis, err := c.GetHeaderByHeight(0)
 479                         if err != nil {
 480                                 return false, err
 481                         }
 482                         var genesisVotes []*Vote
 483                         alreadyVote := make(map[string]struct{})
 484                         for _, voter := range d.config.SelfVoteSigners {
 485                                 if _, ok := alreadyVote[voter]; !ok {
 486                                         genesisVotes = append(genesisVotes, &Vote{
 487                                                 Voter:     voter,
 488                                                 Candidate: voter,
 489                                                 Stake:     0,
 490                                                 //Stake:     state.GetBalance(voter),
 491                                         })
 492                                         alreadyVote[voter] = struct{}{}
 493                                 }
 494                         }
 495                         snap = newSnapshot(d.config, d.signatures, genesis.Hash(), genesisVotes, defaultLoopCntRecalculateSigners)
 496                         if err := snap.store(d.store); err != nil {
 497                                 return false, err
 498                         }
 499                         log.Info("Stored genesis voting snapshot to disk")
 500                         break
 501                 }
 502
 503                 header, err := c.GetHeaderByHeight(height)
 504                 if header == nil || err != nil {
 505                         return false, errors.New("unknown ancestor")
 506                 }
 507
 508                 height, h = height-1, header.PreviousBlockHash
 509         }
 510
 511         snap, err := snap.apply(headers)
 512         if err != nil {
 513                 return false, err
 514         }
 515
 516         d.recents.Add(snap.Hash, snap)
 517
 518         if snap != nil {
 519                 loopIndex := int((headerTime-snap.LoopStartTime)/snap.config.Period) % len(snap.Signers)
 520                 if loopIndex >= len(snap.Signers) {
 521                         return false, nil
 522                 } else if *snap.Signers[loopIndex] != d.signer {
 523                         return false, nil
 524
 525                 }
 526                 return true, nil
 527         } else {
 528                 return false, nil
 529         }
 530 }
 531
 532 // snapshot retrieves the authorization snapshot at a given point in time.
 533 func (d *Dpos) snapshot(c chain.Chain, number uint64, hash bc.Hash, parents []*types.BlockHeader, genesisVotes []*Vote, lcrs uint64) (*Snapshot, error) {
 534
 535         var (
 536                 headers []*types.BlockHeader
 537                 snap    *Snapshot
 538         )
 539         h := hash
 540
 541         for snap == nil {
 542                 // If an in-memory snapshot was found, use that
 543                 if s, ok := d.recents.Get(h); ok {
 544                         snap = s.(*Snapshot)
 545                         break
 546                 }
 547                 // If an on-disk checkpoint snapshot can be found, use that
 548                 if number%checkpointInterval == 0 {
 549                         if s, err := loadSnapshot(d.config, d.signatures, d.store, h); err == nil {
 550                                 log.WithFields(log.Fields{"number": number, "hash": h}).Warn("Loaded voting snapshot from disk")
 551                                 snap = s
 552                                 break
 553                         }
 554                 }
 555                 if number == 0 {
 556                         genesis, err := c.GetHeaderByHeight(0)
 557                         if err != nil {
 558                                 return nil, err
 559                         }
 560                         if err := d.VerifySeal(c, genesis); err != nil {
 561                                 return nil, err
 562                         }
 563
 564                         snap = newSnapshot(d.config, d.signatures, genesis.Hash(), genesisVotes, lcrs)
 565                         if err := snap.store(d.store); err != nil {
 566                                 return nil, err
 567                         }
 568                         log.Info("Stored genesis voting snapshot to disk")
 569                         break
 570                 }
 571                 var header *types.BlockHeader
 572                 if len(parents) > 0 {
 573                         header = parents[len(parents)-1]
 574                         if header.Hash() != h || header.Height != number {
 575                                 return nil, errors.New("unknown ancestor")
 576                         }
 577                         parents = parents[:len(parents)-1]
 578                 } else {
 579                         var err error
 580                         header, err = c.GetHeaderByHeight(number)
 581                         if header == nil || err != nil {
 582                                 return nil, errors.New("unknown ancestor")
 583                         }
 584                 }
 585                 headers = append(headers, header)
 586                 number, h = number-1, header.PreviousBlockHash
 587         }
 588
 589         // Previous snapshot found, apply any pending headers on top of it
 590         for i := 0; i < len(headers)/2; i++ {
 591                 headers[i], headers[len(headers)-1-i] = headers[len(headers)-1-i], headers[i]
 592         }
 593         snap, err := snap.apply(headers)
 594         if err != nil {
 595                 return nil, err
 596         }
 597         d.recents.Add(snap.Hash, snap)
 598
 599         // If we've generated a new checkpoint snapshot, save to disk
 600         if snap.Number%checkpointInterval == 0 && len(headers) > 0 {
 601                 if err = snap.store(d.store); err != nil {
 602                         return nil, err
 603                 }
 604                 log.Info("Stored voting snapshot to disk", "number", snap.Number, "hash", snap.Hash)
 605         }
 606         return snap, err
 607 }
 608
 609 // Get the signer missing from last signer till header.Coinbase
 610 func getSignerMissing(lastSigner string, currentSigner string, extra HeaderExtra) []string {
 611
 612         var signerMissing []string
 613         recordMissing := false
 614         for _, signer := range extra.SignerQueue {
 615                 if signer == lastSigner {
 616                         recordMissing = true
 617                         continue
 618                 }
 619                 if signer == currentSigner {
 620                         break
 621                 }
 622                 if recordMissing {
 623                         signerMissing = append(signerMissing, signer)
 624                 }
 625         }
 626         return signerMissing
 627 }