consensus/consensus/dpos/signer_queue.go

   1 package dpos
   2
   3 import (
   4         "bytes"
   5         "sort"
   6
   7         "github.com/vapor/protocol/bc"
   8 )
   9
  10 type TallyItem struct {
  11         addr  string
  12         stake uint64
  13 }
  14
  15 type TallySlice []TallyItem
  16
  17 func (s TallySlice) Len() int      { return len(s) }
  18 func (s TallySlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
  19 func (s TallySlice) Less(i, j int) bool {
  20         //we need sort reverse, so ...
  21         if s[i].stake > s[j].stake {
  22                 return true
  23
  24         } else if s[i].stake < s[j].stake {
  25                 return false
  26         }
  27         // if the stake equal
  28         //return bytes.Compare(s[i].addr.ScriptAddress(), s[j].addr.ScriptAddress()) > 0
  29         return s[i].addr > s[j].addr
  30 }
  31
  32 type SignerItem struct {
  33         addr string
  34         hash bc.Hash
  35 }
  36
  37 type SignerSlice []SignerItem
  38
  39 func (s SignerSlice) Len() int      { return len(s) }
  40 func (s SignerSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
  41 func (s SignerSlice) Less(i, j int) bool {
  42         return bytes.Compare(s[i].hash.Bytes(), s[j].hash.Bytes()) > 0
  43 }
  44
  45 // verify the SignerQueue base on block hash
  46 func (s *Snapshot) verifySignerQueue(signerQueue []string) error {
  47
  48         if len(signerQueue) > int(s.config.MaxSignerCount) {
  49                 return errInvalidSignerQueue
  50         }
  51         sq, err := s.createSignerQueue()
  52         if err != nil {
  53                 return err
  54         }
  55         if len(sq) == 0 || len(sq) != len(signerQueue) {
  56                 return errInvalidSignerQueue
  57         }
  58         for i, signer := range signerQueue {
  59                 if signer != sq[i] {
  60                         return errInvalidSignerQueue
  61                 }
  62         }
  63
  64         return nil
  65 }
  66
  67 func (s *Snapshot) buildTallySlice() TallySlice {
  68         var tallySlice TallySlice
  69         for address, stake := range s.Tally {
  70                 if !candidateNeedPD || s.isCandidate(address) {
  71                         if _, ok := s.Punished[address]; ok {
  72                                 var creditWeight uint64
  73                                 if s.Punished[address] > defaultFullCredit-minCalSignerQueueCredit {
  74                                         creditWeight = minCalSignerQueueCredit
  75                                 } else {
  76                                         creditWeight = defaultFullCredit - s.Punished[address]
  77                                 }
  78                                 tallySlice = append(tallySlice, TallyItem{address, stake * creditWeight})
  79                         } else {
  80                                 tallySlice = append(tallySlice, TallyItem{address, stake * defaultFullCredit})
  81                         }
  82                 }
  83         }
  84         return tallySlice
  85 }
  86
  87 func (s *Snapshot) createSignerQueue() ([]string, error) {
  88
  89         if (s.Number+1)%s.config.MaxSignerCount != 0 || s.Hash != s.HistoryHash[len(s.HistoryHash)-1] {
  90                 return nil, errCreateSignerQueueNotAllowed
  91         }
  92
  93         var signerSlice SignerSlice
  94         var topStakeAddress []string
  95         if (s.Number+1)%(s.config.MaxSignerCount*s.LCRS) == 0 {
  96                 // before recalculate the signers, clear the candidate is not in snap.Candidates
  97
  98                 // only recalculate signers from to tally per 10 loop,
  99                 // other loop end just reset the order of signers by block hash (nearly random)
 100                 tallySlice := s.buildTallySlice()
 101                 sort.Sort(TallySlice(tallySlice))
 102                 queueLength := int(s.config.MaxSignerCount)
 103                 if queueLength > len(tallySlice) {
 104                         queueLength = len(tallySlice)
 105                 }
 106                 if queueLength == defaultOfficialMaxSignerCount && len(tallySlice) > defaultOfficialThirdLevelCount {
 107                         for i, tallyItem := range tallySlice[:defaultOfficialFirstLevelCount] {
 108                                 signerSlice = append(signerSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 109                         }
 110                         var signerSecondLevelSlice, signerThirdLevelSlice, signerLastLevelSlice SignerSlice
 111                         // 60%
 112                         for i, tallyItem := range tallySlice[defaultOfficialFirstLevelCount:defaultOfficialSecondLevelCount] {
 113                                 signerSecondLevelSlice = append(signerSecondLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 114                         }
 115                         sort.Sort(SignerSlice(signerSecondLevelSlice))
 116                         signerSlice = append(signerSlice, signerSecondLevelSlice[:6]...)
 117                         // 40%
 118                         for i, tallyItem := range tallySlice[defaultOfficialSecondLevelCount:defaultOfficialThirdLevelCount] {
 119                                 signerThirdLevelSlice = append(signerThirdLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 120                         }
 121                         sort.Sort(SignerSlice(signerThirdLevelSlice))
 122                         signerSlice = append(signerSlice, signerThirdLevelSlice[:4]...)
 123                         // choose 1 from last
 124                         for i, tallyItem := range tallySlice[defaultOfficialThirdLevelCount:] {
 125                                 signerLastLevelSlice = append(signerLastLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 126                         }
 127                         sort.Sort(SignerSlice(signerLastLevelSlice))
 128                         signerSlice = append(signerSlice, signerLastLevelSlice[0])
 129
 130                 } else {
 131                         for i, tallyItem := range tallySlice[:queueLength] {
 132                                 signerSlice = append(signerSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 133                         }
 134
 135                 }
 136
 137         } else {
 138                 for i, signer := range s.Signers {
 139                         signerSlice = append(signerSlice, SignerItem{*signer, s.HistoryHash[len(s.HistoryHash)-1-i]})
 140                 }
 141         }
 142
 143         sort.Sort(SignerSlice(signerSlice))
 144         // Set the top candidates in random order base on block hash
 145         if len(signerSlice) == 0 {
 146                 return nil, errSignerQueueEmpty
 147         }
 148         for i := 0; i < int(s.config.MaxSignerCount); i++ {
 149                 topStakeAddress = append(topStakeAddress, signerSlice[i%len(signerSlice)].addr)
 150         }
 151
 152         return topStakeAddress, nil
 153
 154 }