protocol/state/checkpoint.go

   1 package state
   2
   3 import (
   4         "sort"
   5
   6         "github.com/bytom/bytom/config"
   7         "github.com/bytom/bytom/consensus"
   8         "github.com/bytom/bytom/errors"
   9         "github.com/bytom/bytom/protocol/bc"
  10         "github.com/bytom/bytom/protocol/bc/types"
  11 )
  12
  13 // CheckpointStatus represent current status of checkpoint
  14 type CheckpointStatus uint8
  15
  16 const (
  17         // Growing means that the checkpoint has not ended the current epoch
  18         Growing CheckpointStatus = iota
  19
  20         // Unjustified means thant the checkpoint has ended the current epoch, but not been justified
  21         Unjustified
  22
  23         // Justified if checkpoint is the root, or there exists a super link c′ → c where c′ is justified
  24         Justified
  25
  26         // Finalized if checkpoint c is justified and there is a sup link c→c′ where c′is a direct child of c
  27         Finalized
  28 )
  29
  30 var errIncreaseCheckpoint = errors.New("invalid block for increase checkpoint")
  31
  32 // SupLink is an ordered pair of checkpoints (a, b), also written a → b,
  33 // such that at least 2/3 of validators have published votes with source a and target b.
  34 type SupLink struct {
  35         SourceHeight uint64
  36         SourceHash   bc.Hash
  37         Signatures   [consensus.MaxNumOfValidators]string
  38 }
  39
  40 // IsMajority if at least 2/3 of validators have published votes with sup link
  41 func (s *SupLink) IsMajority(numOfValidators int) bool {
  42         numOfSignatures := 0
  43         for _, signature := range s.Signatures {
  44                 if signature != "" {
  45                         numOfSignatures++
  46                 }
  47         }
  48         return numOfSignatures > numOfValidators*2/3
  49 }
  50
  51 // Checkpoint represent the block/hash under consideration for finality for a given epoch.
  52 // This block is the last block of the previous epoch. Rather than dealing with every block,
  53 // Casper only considers checkpoints for finalization. When a checkpoint is explicitly finalized,
  54 // all ancestor blocks of the checkpoint are implicitly finalized.
  55 type Checkpoint struct {
  56         Height     uint64
  57         Hash       bc.Hash
  58         ParentHash bc.Hash
  59         // only save in the memory, not be persisted
  60         Parent    *Checkpoint `json:"-"`
  61         Timestamp uint64
  62         SupLinks  []*SupLink `json:"-"`
  63         Status    CheckpointStatus
  64
  65         Rewards    map[string]uint64 // controlProgram -> num of reward
  66         Votes      map[string]uint64 // pubKey -> num of vote
  67
  68         MergeCheckpoint func(bc.Hash) `json:"-"`
  69 }
  70
  71 // NewCheckpoint create a new checkpoint instance
  72 func NewCheckpoint(parent *Checkpoint) *Checkpoint {
  73         checkpoint := &Checkpoint{
  74                 ParentHash: parent.Hash,
  75                 Parent:     parent,
  76                 Status:     Growing,
  77                 Rewards:    make(map[string]uint64),
  78                 Votes:      make(map[string]uint64),
  79         }
  80
  81         for pubKey, num := range parent.Votes {
  82                 checkpoint.Votes[pubKey] = num
  83         }
  84         return checkpoint
  85 }
  86
  87 // AddVerification add a valid verification to checkpoint's supLink
  88 func (c *Checkpoint) AddVerification(sourceHash bc.Hash, sourceHeight uint64, validatorOrder int, signature string) *SupLink {
  89         for _, supLink := range c.SupLinks {
  90                 if supLink.SourceHash == sourceHash {
  91                         supLink.Signatures[validatorOrder] = signature
  92                         return supLink
  93                 }
  94         }
  95         supLink := &SupLink{
  96                 SourceHeight: sourceHeight,
  97                 SourceHash:   sourceHash,
  98         }
  99         supLink.Signatures[validatorOrder] = signature
 100         c.SupLinks = append(c.SupLinks, supLink)
 101         return supLink
 102 }
 103
 104 // ContainsVerification return whether the specified validator has add verification to current checkpoint
 105 // sourceHash not as filter if is nil,
 106 func (c *Checkpoint) ContainsVerification(validatorOrder int, sourceHash *bc.Hash) bool {
 107         for _, supLink := range c.SupLinks {
 108                 if (sourceHash == nil || supLink.SourceHash == *sourceHash) && supLink.Signatures[validatorOrder] != "" {
 109                         return true
 110                 }
 111         }
 112         return false
 113 }
 114
 115 // Increase will increase the height of checkpoint
 116 func (c *Checkpoint) Increase(block *types.Block) error {
 117         empty := bc.Hash{}
 118         prevHash := c.Hash
 119         if c.Hash == empty {
 120                 prevHash = c.ParentHash
 121         }
 122
 123         if block.PreviousBlockHash != prevHash {
 124                 return errIncreaseCheckpoint
 125         }
 126
 127         c.Hash = block.Hash()
 128         c.Height = block.Height
 129         c.Timestamp = block.Timestamp
 130         c.MergeCheckpoint(c.Hash)
 131         return nil
 132 }
 133
 134 // Validator represent the participants of the PoS network
 135 // Responsible for block generation and verification
 136 type Validator struct {
 137         PubKey   string
 138         Order    int
 139         Vote     uint64
 140 }
 141
 142 // Validators return next epoch of validators, if the status of checkpoint is growing, return empty
 143 func (c *Checkpoint) Validators() map[string]*Validator {
 144         var validators []*Validator
 145         if c.Status == Growing {
 146                 return nil
 147         }
 148
 149         for pubKey, voteNum := range c.Votes {
 150                 if voteNum >= consensus.ActiveNetParams.MinValidatorVoteNum {
 151                         validators = append(validators, &Validator{
 152                                 PubKey:   pubKey,
 153                                 Vote:     c.Votes[pubKey],
 154                         })
 155                 }
 156         }
 157
 158         if len(validators) == 0 {
 159                 return federationValidators()
 160         }
 161
 162         sort.Slice(validators, func(i, j int) bool {
 163                 numI := validators[i].Vote
 164                 numJ := validators[j].Vote
 165                 if numI != numJ {
 166                         return numI > numJ
 167                 }
 168                 return validators[i].PubKey > validators[j].PubKey
 169         })
 170
 171         result := make(map[string]*Validator)
 172         for i := 0; i < len(validators) && i < consensus.MaxNumOfValidators; i++ {
 173                 validator := validators[i]
 174                 validator.Order = i
 175                 result[validator.PubKey] = validator
 176         }
 177         return result
 178 }
 179
 180 func federationValidators() map[string]*Validator {
 181         validators := map[string]*Validator{}
 182         for i, xPub := range config.CommonConfig.Federation.Xpubs {
 183                 validators[xPub.String()] = &Validator{PubKey: xPub.String(), Order: i}
 184         }
 185         return validators
 186 }