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         if (s.Number+1)%s.config.MaxSignerCount != 0 || s.Hash != s.HistoryHash[len(s.HistoryHash)-1] {
  89                 return nil, errCreateSignerQueueNotAllowed
  90         }
  91
  92         var signerSlice SignerSlice
  93         var topStakeAddress []string
  94         if (s.Number+1)%(s.config.MaxSignerCount*s.LCRS) == 0 {
  95                 // before recalculate the signers, clear the candidate is not in snap.Candidates
  96
  97                 // only recalculate signers from to tally per 10 loop,
  98                 // other loop end just reset the order of signers by block hash (nearly random)
  99                 tallySlice := s.buildTallySlice()
 100                 sort.Sort(TallySlice(tallySlice))
 101                 queueLength := int(s.config.MaxSignerCount)
 102                 if queueLength > len(tallySlice) {
 103                         queueLength = len(tallySlice)
 104                 }
 105                 if queueLength == defaultOfficialMaxSignerCount && len(tallySlice) > defaultOfficialThirdLevelCount {
 106                         for i, tallyItem := range tallySlice[:defaultOfficialFirstLevelCount] {
 107                                 signerSlice = append(signerSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 108                         }
 109                         var signerSecondLevelSlice, signerThirdLevelSlice, signerLastLevelSlice SignerSlice
 110                         // 60%
 111                         for i, tallyItem := range tallySlice[defaultOfficialFirstLevelCount:defaultOfficialSecondLevelCount] {
 112                                 signerSecondLevelSlice = append(signerSecondLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 113                         }
 114                         sort.Sort(SignerSlice(signerSecondLevelSlice))
 115                         signerSlice = append(signerSlice, signerSecondLevelSlice[:6]...)
 116                         // 40%
 117                         for i, tallyItem := range tallySlice[defaultOfficialSecondLevelCount:defaultOfficialThirdLevelCount] {
 118                                 signerThirdLevelSlice = append(signerThirdLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 119                         }
 120                         sort.Sort(SignerSlice(signerThirdLevelSlice))
 121                         signerSlice = append(signerSlice, signerThirdLevelSlice[:4]...)
 122                         // choose 1 from last
 123                         for i, tallyItem := range tallySlice[defaultOfficialThirdLevelCount:] {
 124                                 signerLastLevelSlice = append(signerLastLevelSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 125                         }
 126                         sort.Sort(SignerSlice(signerLastLevelSlice))
 127                         signerSlice = append(signerSlice, signerLastLevelSlice[0])
 128
 129                 } else {
 130                         for i, tallyItem := range tallySlice[:queueLength] {
 131                                 signerSlice = append(signerSlice, SignerItem{tallyItem.addr, s.HistoryHash[len(s.HistoryHash)-1-i]})
 132                         }
 133
 134                 }
 135
 136         } else {
 137                 for i, signer := range s.Signers {
 138                         signerSlice = append(signerSlice, SignerItem{*signer, s.HistoryHash[len(s.HistoryHash)-1-i]})
 139                 }
 140         }
 141
 142         sort.Sort(SignerSlice(signerSlice))
 143         // Set the top candidates in random order base on block hash
 144         if len(signerSlice) == 0 {
 145                 return nil, errSignerQueueEmpty
 146         }
 147         for i := 0; i < int(s.config.MaxSignerCount); i++ {
 148                 topStakeAddress = append(topStakeAddress, signerSlice[i%len(signerSlice)].addr)
 149         }
 150
 151         return topStakeAddress, nil
 152
 153 }