consensus/consensus/dpos/snapshot.go

   1 package dpos
   2
   3 import (
   4         "encoding/json"
   5         "errors"
   6         "math/big"
   7         "sort"
   8         "time"
   9
  10         lru "github.com/hashicorp/golang-lru"
  11         "github.com/vapor/config"
  12         "github.com/vapor/protocol"
  13         "github.com/vapor/protocol/bc"
  14         "github.com/vapor/protocol/bc/types"
  15 )
  16
  17 const (
  18         defaultFullCredit               = 1000 // no punished
  19         missingPublishCredit            = 100  // punished for missing one block seal
  20         signRewardCredit                = 10   // seal one block
  21         autoRewardCredit                = 1    // credit auto recover for each block
  22         minCalSignerQueueCredit         = 300  // when calculate the signerQueue
  23         defaultOfficialMaxSignerCount   = 21   // official max signer count
  24         defaultOfficialFirstLevelCount  = 10   // official first level , 100% in signer queue
  25         defaultOfficialSecondLevelCount = 20   // official second level, 60% in signer queue
  26         defaultOfficialThirdLevelCount  = 30   // official third level, 40% in signer queue
  27         // the credit of one signer is at least minCalSignerQueueCredit
  28         candidateStateNormal = 1
  29         candidateMaxLen      = 500 // if candidateNeedPD is false and candidate is more than candidateMaxLen, then minimum tickets candidates will be remove in each LCRS*loop
  30 )
  31
  32 var errIncorrectTallyCount = errors.New("incorrect tally count")
  33
  34 type Snapshot struct {
  35         config          *config.DposConfig    // Consensus engine configuration parameters
  36         sigcache        *lru.ARCCache         // Cache of recent block signatures to speed up ecrecover
  37         LCRS            uint64                // Loop count to recreate signers from top tally
  38         Period          uint64                `json:"period"`           // Period of seal each block
  39         Number          uint64                `json:"number"`           // Block Number where the snapshot was created
  40         ConfirmedNumber uint64                `json:"confirmed_number"` // Block Number confirmed when the snapshot was created
  41         Hash            bc.Hash               `json:"hash"`             // Block hash where the snapshot was created
  42         HistoryHash     []bc.Hash             `json:"historyHash"`      // Block hash list for two recent loop
  43         Signers         []*string             `json:"signers"`          // Signers queue in current header
  44         Votes           map[string]*Vote      `json:"votes"`            // All validate votes from genesis block
  45         Tally           map[string]uint64     `json:"tally"`            // Stake for each candidate address
  46         Voters          map[string]uint64     `json:"voters"`           // Block height for each voter address
  47         Candidates      map[string]uint64     `json:"candidates"`       // Candidates for Signers (0- adding procedure 1- normal 2- removing procedure)
  48         Punished        map[string]uint64     `json:"punished"`         // The signer be punished count cause of missing seal
  49         Confirmations   map[uint64][]string   `json:"confirms"`         // The signer confirm given block height
  50         Proposals       map[bc.Hash]*Proposal `json:"proposals"`        // The Proposals going or success (failed proposal will be removed)
  51         HeaderTime      uint64                `json:"headerTime"`       // Time of the current header
  52         LoopStartTime   uint64                `json:"loopStartTime"`    // Start Time of the current loop
  53 }
  54
  55 // newSnapshot creates a new snapshot with the specified startup parameters. only ever use if for
  56 // the genesis block.
  57 func newSnapshot(config *config.DposConfig, sigcache *lru.ARCCache, hash bc.Hash, votes []*Vote, lcrs uint64) *Snapshot {
  58
  59         snap := &Snapshot{
  60                 config:          config,
  61                 sigcache:        sigcache,
  62                 LCRS:            lcrs,
  63                 Period:          config.Period,
  64                 Number:          0,
  65                 ConfirmedNumber: 0,
  66                 Hash:            hash,
  67                 HistoryHash:     []bc.Hash{},
  68                 Signers:         []*string{},
  69                 Votes:           make(map[string]*Vote),
  70                 Tally:           make(map[string]uint64),
  71                 Voters:          make(map[string]uint64),
  72                 Punished:        make(map[string]uint64),
  73                 Candidates:      make(map[string]uint64),
  74                 Confirmations:   make(map[uint64][]string),
  75                 Proposals:       make(map[bc.Hash]*Proposal),
  76                 HeaderTime:      uint64(time.Now().Unix()) - 1,
  77                 LoopStartTime:   config.GenesisTimestamp,
  78         }
  79         snap.HistoryHash = append(snap.HistoryHash, hash)
  80         for _, vote := range votes {
  81                 // init Votes from each vote
  82                 snap.Votes[vote.Voter] = vote
  83                 // init Tally
  84                 _, ok := snap.Tally[vote.Candidate]
  85                 if !ok {
  86                         snap.Tally[vote.Candidate] = 0
  87                 }
  88                 snap.Tally[vote.Candidate] += vote.Stake
  89                 // init Voters
  90                 snap.Voters[vote.Voter] = 0 // block height is 0 , vote in genesis block
  91                 // init Candidates
  92                 snap.Candidates[vote.Voter] = candidateStateNormal
  93         }
  94
  95         for i := 0; i < int(config.MaxSignerCount); i++ {
  96                 snap.Signers = append(snap.Signers, &config.SelfVoteSigners[i%len(config.SelfVoteSigners)])
  97         }
  98
  99         return snap
 100 }
 101
 102 // loadSnapshot loads an existing snapshot from the database.
 103 func loadSnapshot(config *config.DposConfig, sigcache *lru.ARCCache, store protocol.Store, hash bc.Hash) (*Snapshot, error) {
 104         data, err := store.Get(&hash)
 105         if err != nil {
 106                 return nil, err
 107         }
 108         snap := new(Snapshot)
 109         if err := json.Unmarshal(data, snap); err != nil {
 110                 return nil, err
 111         }
 112         snap.config = config
 113         snap.sigcache = sigcache
 114         return snap, nil
 115 }
 116
 117 // store inserts the snapshot into the database.
 118 func (s *Snapshot) store(store protocol.Store) error {
 119         data, err := json.Marshal(s)
 120         if err != nil {
 121                 return err
 122         }
 123         return store.Set(&s.Hash, data)
 124 }
 125
 126 // copy creates a deep copy of the snapshot, though not the individual votes.
 127 func (s *Snapshot) copy() *Snapshot {
 128         cpy := &Snapshot{
 129                 config:          s.config,
 130                 sigcache:        s.sigcache,
 131                 LCRS:            s.LCRS,
 132                 Period:          s.Period,
 133                 Number:          s.Number,
 134                 ConfirmedNumber: s.ConfirmedNumber,
 135                 Hash:            s.Hash,
 136                 HistoryHash:     make([]bc.Hash, len(s.HistoryHash)),
 137
 138                 Signers:       make([]*string, len(s.Signers)),
 139                 Votes:         make(map[string]*Vote),
 140                 Tally:         make(map[string]uint64),
 141                 Voters:        make(map[string]uint64),
 142                 Candidates:    make(map[string]uint64),
 143                 Punished:      make(map[string]uint64),
 144                 Proposals:     make(map[bc.Hash]*Proposal),
 145                 Confirmations: make(map[uint64][]string),
 146
 147                 HeaderTime:    s.HeaderTime,
 148                 LoopStartTime: s.LoopStartTime,
 149         }
 150         copy(cpy.HistoryHash, s.HistoryHash)
 151         copy(cpy.Signers, s.Signers)
 152         for voter, vote := range s.Votes {
 153                 cpy.Votes[voter] = &Vote{
 154                         Voter:     vote.Voter,
 155                         Candidate: vote.Candidate,
 156                         Stake:     vote.Stake,
 157                 }
 158         }
 159         for candidate, tally := range s.Tally {
 160                 cpy.Tally[candidate] = tally
 161         }
 162         for voter, number := range s.Voters {
 163                 cpy.Voters[voter] = number
 164         }
 165         for candidate, state := range s.Candidates {
 166                 cpy.Candidates[candidate] = state
 167         }
 168         for signer, cnt := range s.Punished {
 169                 cpy.Punished[signer] = cnt
 170         }
 171         for blockNumber, confirmers := range s.Confirmations {
 172                 cpy.Confirmations[blockNumber] = make([]string, len(confirmers))
 173                 copy(cpy.Confirmations[blockNumber], confirmers)
 174         }
 175         for txHash, proposal := range s.Proposals {
 176                 cpy.Proposals[txHash] = proposal.copy()
 177         }
 178
 179         return cpy
 180 }
 181
 182 // apply creates a new authorization snapshot by applying the given headers to
 183 // the original one.
 184 func (s *Snapshot) apply(headers []*types.BlockHeader) (*Snapshot, error) {
 185         // Allow passing in no headers for cleaner code
 186         if len(headers) == 0 {
 187                 return s, nil
 188         }
 189         // Sanity check that the headers can be applied
 190         for i := 0; i < len(headers)-1; i++ {
 191                 if headers[i+1].Height != headers[i].Height+1 {
 192                         return nil, errInvalidVotingChain
 193                 }
 194         }
 195         if headers[0].Height != s.Number+1 {
 196                 return nil, errInvalidVotingChain
 197         }
 198         // Iterate through the headers and create a new snapshot
 199         snap := s.copy()
 200         for _, header := range headers {
 201
 202                 // Resolve the authorization key and check against signers
 203                 coinbase, err := ecrecover(header, s.sigcache, nil)
 204                 if err != nil {
 205                         return nil, err
 206                 }
 207
 208                 headerExtra := HeaderExtra{}
 209                 if err := json.Unmarshal(header.Extra[extraVanity:len(header.Extra)-extraSeal], &headerExtra); err != nil {
 210                         return nil, err
 211                 }
 212
 213                 snap.HeaderTime = header.Timestamp
 214                 snap.LoopStartTime = headerExtra.LoopStartTime
 215                 snap.Signers = nil
 216                 for i := range headerExtra.SignerQueue {
 217                         snap.Signers = append(snap.Signers, &headerExtra.SignerQueue[i])
 218                 }
 219
 220                 snap.ConfirmedNumber = headerExtra.ConfirmedBlockNumber
 221
 222                 if len(snap.HistoryHash) >= int(s.config.MaxSignerCount)*2 {
 223                         snap.HistoryHash = snap.HistoryHash[1 : int(s.config.MaxSignerCount)*2]
 224                 }
 225
 226                 snap.HistoryHash = append(snap.HistoryHash, header.Hash())
 227
 228                 // deal the new confirmation in this block
 229                 snap.updateSnapshotByConfirmations(headerExtra.CurrentBlockConfirmations)
 230
 231                 // deal the new vote from voter
 232                 snap.updateSnapshotByVotes(headerExtra.CurrentBlockVotes, header.Height)
 233
 234                 // deal the snap related with punished
 235                 snap.updateSnapshotForPunish(headerExtra.SignerMissing, header.Height, coinbase)
 236
 237                 // deal proposals
 238                 snap.updateSnapshotByProposals(headerExtra.CurrentBlockProposals, header.Height)
 239
 240                 // deal declares
 241                 snap.updateSnapshotByDeclares(headerExtra.CurrentBlockDeclares, header.Height)
 242
 243                 // calculate proposal result
 244                 snap.calculateProposalResult(header.Height)
 245
 246                 // check the len of candidate if not candidateNeedPD
 247                 if !candidateNeedPD && (snap.Number+1)%(snap.config.MaxSignerCount*snap.LCRS) == 0 && len(snap.Candidates) > candidateMaxLen {
 248                         snap.removeExtraCandidate()
 249                 }
 250
 251         }
 252         snap.Number += uint64(len(headers))
 253         snap.Hash = headers[len(headers)-1].Hash()
 254         snap.updateSnapshotForExpired()
 255         err := snap.verifyTallyCnt()
 256         if err != nil {
 257                 return nil, err
 258         }
 259         return snap, nil
 260 }
 261
 262 func (s *Snapshot) removeExtraCandidate() {
 263         // remove minimum tickets tally beyond candidateMaxLen
 264         tallySlice := s.buildTallySlice()
 265         sort.Sort(TallySlice(tallySlice))
 266         if len(tallySlice) > candidateMaxLen {
 267                 removeNeedTally := tallySlice[candidateMaxLen:]
 268                 for _, tallySlice := range removeNeedTally {
 269                         delete(s.Candidates, tallySlice.addr)
 270                 }
 271         }
 272 }
 273
 274 func (s *Snapshot) verifyTallyCnt() error {
 275
 276         tallyTarget := make(map[string]uint64)
 277         for _, v := range s.Votes {
 278                 if _, ok := tallyTarget[v.Candidate]; ok {
 279                         tallyTarget[v.Candidate] = tallyTarget[v.Candidate] + v.Stake
 280                 } else {
 281                         tallyTarget[v.Candidate] = v.Stake
 282                 }
 283         }
 284         for address, tally := range s.Tally {
 285                 if targetTally, ok := tallyTarget[address]; ok && targetTally == tally {
 286                         continue
 287                 } else {
 288                         return errIncorrectTallyCount
 289                 }
 290         }
 291
 292         return nil
 293 }
 294
 295 func (s *Snapshot) updateSnapshotByDeclares(declares []Declare, headerHeight uint64) {
 296         for _, declare := range declares {
 297                 if proposal, ok := s.Proposals[declare.ProposalHash]; ok {
 298                         // check the proposal enable status and valid block number
 299                         if proposal.ReceivedNumber+proposal.ValidationLoopCnt*s.config.MaxSignerCount < headerHeight || !s.isCandidate(declare.Declarer) {
 300                                 continue
 301                         }
 302                         // check if this signer already declare on this proposal
 303                         alreadyDeclare := false
 304                         for _, v := range proposal.Declares {
 305                                 if v.Declarer == declare.Declarer {
 306                                         // this declarer already declare for this proposal
 307                                         alreadyDeclare = true
 308                                         break
 309                                 }
 310                         }
 311                         if alreadyDeclare {
 312                                 continue
 313                         }
 314                         // add declare to proposal
 315                         s.Proposals[declare.ProposalHash].Declares = append(s.Proposals[declare.ProposalHash].Declares,
 316                                 &Declare{declare.ProposalHash, declare.Declarer, declare.Decision})
 317
 318                 }
 319         }
 320 }
 321
 322 func (s *Snapshot) calculateProposalResult(headerHeight uint64) {
 323
 324         for hashKey, proposal := range s.Proposals {
 325                 // the result will be calculate at receiverdNumber + vlcnt + 1
 326                 if proposal.ReceivedNumber+proposal.ValidationLoopCnt*s.config.MaxSignerCount+1 == headerHeight {
 327                         // calculate the current stake of this proposal
 328                         judegmentStake := big.NewInt(0)
 329                         for _, tally := range s.Tally {
 330                                 judegmentStake.Add(judegmentStake, new(big.Int).SetUint64(tally))
 331                         }
 332                         judegmentStake.Mul(judegmentStake, big.NewInt(2))
 333                         judegmentStake.Div(judegmentStake, big.NewInt(3))
 334                         // calculate declare stake
 335                         yesDeclareStake := big.NewInt(0)
 336                         for _, declare := range proposal.Declares {
 337                                 if declare.Decision {
 338                                         if _, ok := s.Tally[declare.Declarer]; ok {
 339                                                 yesDeclareStake.Add(yesDeclareStake, new(big.Int).SetUint64(s.Tally[declare.Declarer]))
 340                                         }
 341                                 }
 342                         }
 343                         if yesDeclareStake.Cmp(judegmentStake) > 0 {
 344                                 // process add candidate
 345                                 switch proposal.ProposalType {
 346                                 case proposalTypeCandidateAdd:
 347                                         if candidateNeedPD {
 348                                                 s.Candidates[s.Proposals[hashKey].Candidate] = candidateStateNormal
 349                                         }
 350                                 case proposalTypeCandidateRemove:
 351                                         if _, ok := s.Candidates[proposal.Candidate]; ok && candidateNeedPD {
 352                                                 delete(s.Candidates, proposal.Candidate)
 353                                         }
 354                                 case proposalTypeMinerRewardDistributionModify:
 355                                         minerRewardPerThousand = s.Proposals[hashKey].MinerRewardPerThousand
 356                                 }
 357                         }
 358                 }
 359         }
 360 }
 361
 362 func (s *Snapshot) updateSnapshotByProposals(proposals []Proposal, headerHeight uint64) {
 363         for _, proposal := range proposals {
 364                 proposal.ReceivedNumber = headerHeight
 365                 s.Proposals[proposal.Hash] = &proposal
 366         }
 367 }
 368
 369 func (s *Snapshot) updateSnapshotForExpired() {
 370         // deal the expired vote
 371         var expiredVotes []*Vote
 372         for voterAddress, voteNumber := range s.Voters {
 373                 if s.Number-voteNumber > s.config.Epoch {
 374                         // clear the vote
 375                         if expiredVote, ok := s.Votes[voterAddress]; ok {
 376                                 expiredVotes = append(expiredVotes, expiredVote)
 377                         }
 378                 }
 379         }
 380         // remove expiredVotes only enough voters left
 381         if uint64(len(s.Voters)-len(expiredVotes)) >= s.config.MaxSignerCount {
 382                 for _, expiredVote := range expiredVotes {
 383                         s.Tally[expiredVote.Candidate] -= expiredVote.Stake
 384                         // TODO
 385                         if s.Tally[expiredVote.Candidate] == 0 {
 386                                 delete(s.Tally, expiredVote.Candidate)
 387                         }
 388                         delete(s.Votes, expiredVote.Voter)
 389                         delete(s.Voters, expiredVote.Voter)
 390                 }
 391         }
 392
 393         // deal the expired confirmation
 394         for blockNumber := range s.Confirmations {
 395                 if s.Number-blockNumber > s.config.MaxSignerCount {
 396                         delete(s.Confirmations, blockNumber)
 397                 }
 398         }
 399
 400         // TODO
 401         // remove 0 stake tally
 402
 403         for address, tally := range s.Tally {
 404                 if tally <= 0 && uint64(len(s.Tally)) > s.config.MaxSignerCount {
 405                         delete(s.Tally, address)
 406                 }
 407         }
 408 }
 409
 410 func (s *Snapshot) updateSnapshotByConfirmations(confirmations []Confirmation) {
 411         for _, confirmation := range confirmations {
 412                 _, ok := s.Confirmations[confirmation.BlockNumber]
 413                 if !ok {
 414                         s.Confirmations[confirmation.BlockNumber] = []string{}
 415                 }
 416                 addConfirmation := true
 417                 for _, address := range s.Confirmations[confirmation.BlockNumber] {
 418                         if confirmation.Signer == address {
 419                                 addConfirmation = false
 420                                 break
 421                         }
 422                 }
 423                 if addConfirmation == true {
 424                         s.Confirmations[confirmation.BlockNumber] = append(s.Confirmations[confirmation.BlockNumber], confirmation.Signer)
 425                 }
 426         }
 427 }
 428
 429 func (s *Snapshot) updateSnapshotByVotes(votes []Vote, headerHeight uint64) {
 430         for _, vote := range votes {
 431                 // update Votes, Tally, Voters data
 432                 if lastVote, ok := s.Votes[vote.Voter]; ok {
 433                         s.Tally[lastVote.Candidate] = s.Tally[lastVote.Candidate] - lastVote.Stake
 434                 }
 435                 if _, ok := s.Tally[vote.Candidate]; ok {
 436                         s.Tally[vote.Candidate] = s.Tally[vote.Candidate] + vote.Stake
 437                 } else {
 438                         s.Tally[vote.Candidate] = vote.Stake
 439                         if !candidateNeedPD {
 440                                 s.Candidates[vote.Candidate] = candidateStateNormal
 441                         }
 442                 }
 443                 s.Votes[vote.Voter] = &Vote{vote.Voter, vote.Candidate, vote.Stake}
 444                 s.Voters[vote.Voter] = headerHeight
 445         }
 446 }
 447
 448 func (s *Snapshot) updateSnapshotByMPVotes(votes []Vote) {
 449         for _, txVote := range votes {
 450                 if lastVote, ok := s.Votes[txVote.Voter]; ok {
 451                         s.Tally[lastVote.Candidate] = s.Tally[lastVote.Candidate] - lastVote.Stake
 452                         s.Tally[lastVote.Candidate] = s.Tally[lastVote.Candidate] + txVote.Stake
 453                         s.Votes[txVote.Voter] = &Vote{Voter: txVote.Voter, Candidate: lastVote.Candidate, Stake: txVote.Stake}
 454                 }
 455         }
 456 }
 457
 458 func (s *Snapshot) updateSnapshotForPunish(signerMissing []string, headerNumber uint64, coinbase string) {
 459         // punish the missing signer
 460         for _, signerMissing := range signerMissing {
 461                 if _, ok := s.Punished[signerMissing]; ok {
 462                         s.Punished[signerMissing] += missingPublishCredit
 463                 } else {
 464                         s.Punished[signerMissing] = missingPublishCredit
 465                 }
 466         }
 467         // reduce the punish of sign signer
 468         if _, ok := s.Punished[coinbase]; ok {
 469
 470                 if s.Punished[coinbase] > signRewardCredit {
 471                         s.Punished[coinbase] -= signRewardCredit
 472                 } else {
 473                         delete(s.Punished, coinbase)
 474                 }
 475         }
 476         // reduce the punish for all punished
 477         for signerEach := range s.Punished {
 478                 if s.Punished[signerEach] > autoRewardCredit {
 479                         s.Punished[signerEach] -= autoRewardCredit
 480                 } else {
 481                         delete(s.Punished, signerEach)
 482                 }
 483         }
 484 }
 485
 486 // inturn returns if a signer at a given block height is in-turn or not.
 487 func (s *Snapshot) inturn(signer string, headerTime uint64) bool {
 488         // if all node stop more than period of one loop
 489         loopIndex := int((headerTime-s.LoopStartTime)/s.config.Period) % len(s.Signers)
 490         if loopIndex >= len(s.Signers) {
 491                 return false
 492         } else if *s.Signers[loopIndex] != signer {
 493                 return false
 494
 495         }
 496         return true
 497 }
 498
 499 // check if address belong to voter
 500 func (s *Snapshot) isVoter(address string) bool {
 501         if _, ok := s.Voters[address]; ok {
 502                 return true
 503         }
 504         return false
 505 }
 506
 507 // check if address belong to candidate
 508 func (s *Snapshot) isCandidate(address string) bool {
 509         if _, ok := s.Candidates[address]; ok {
 510                 return true
 511         }
 512         return false
 513 }
 514
 515 // get last block number meet the confirm condition
 516 func (s *Snapshot) getLastConfirmedBlockNumber(confirmations []Confirmation) *big.Int {
 517         cpyConfirmations := make(map[uint64][]string)
 518         for blockNumber, confirmers := range s.Confirmations {
 519                 cpyConfirmations[blockNumber] = make([]string, len(confirmers))
 520                 copy(cpyConfirmations[blockNumber], confirmers)
 521         }
 522         // update confirmation into snapshot
 523         for _, confirmation := range confirmations {
 524                 _, ok := cpyConfirmations[confirmation.BlockNumber]
 525                 if !ok {
 526                         cpyConfirmations[confirmation.BlockNumber] = []string{}
 527                 }
 528                 addConfirmation := true
 529                 for _, address := range cpyConfirmations[confirmation.BlockNumber] {
 530                         if confirmation.Signer == address {
 531                                 addConfirmation = false
 532                                 break
 533                         }
 534                 }
 535                 if addConfirmation == true {
 536                         cpyConfirmations[confirmation.BlockNumber] = append(cpyConfirmations[confirmation.BlockNumber], confirmation.Signer)
 537                 }
 538         }
 539
 540         i := s.Number
 541         for ; i > s.Number-s.config.MaxSignerCount*2/3+1; i-- {
 542                 if confirmers, ok := cpyConfirmations[i]; ok {
 543                         if len(confirmers) > int(s.config.MaxSignerCount*2/3) {
 544                                 return big.NewInt(int64(i))
 545                         }
 546                 }
 547         }
 548         return big.NewInt(int64(i))
 549 }