protocol/auth_verification.go

   1 package protocol
   2
   3 import (
   4         "encoding/hex"
   5         "fmt"
   6
   7         log "github.com/sirupsen/logrus"
   8
   9         "github.com/bytom/bytom/protocol/bc"
  10         "github.com/bytom/bytom/protocol/state"
  11 )
  12
  13 // AuthVerification verify whether the Verification is legal.
  14 // the status of source checkpoint must justified, and an individual validator ν must not publish two distinct Verification
  15 // ⟨ν,s1,t1,h(s1),h(t1)⟩ and ⟨ν,s2,t2,h(s2),h(t2)⟩, such that either:
  16 // h(t1) = h(t2) OR h(s1) < h(s2) < h(t2) < h(t1)
  17 func (c *Casper) AuthVerification(v *Verification) error {
  18         if err := validate(v); err != nil {
  19                 return err
  20         }
  21
  22         target, err := c.store.GetCheckpoint(&v.TargetHash)
  23         if err != nil {
  24                 c.verificationCache.Add(verificationCacheKey(v.TargetHash, v.PubKey), v)
  25                 return nil
  26         }
  27
  28         validators, err := c.Validators(&v.TargetHash)
  29         if err != nil {
  30                 return err
  31         }
  32
  33          if _, ok := validators[v.PubKey]; !ok {
  34                 return errPubKeyIsNotValidator
  35         }
  36
  37         if target.ContainsVerification(v.SourceHash, validators[v.PubKey].Order) {
  38                 return nil
  39         }
  40
  41         c.mu.Lock()
  42         defer c.mu.Unlock()
  43
  44         // root of tree is the last finalized checkpoint
  45         if v.TargetHeight < c.tree.checkpoint.Height {
  46                 // discard the verification message which height of target less than height of last finalized checkpoint
  47                 // is for simplify check the vote within the span of its other votes
  48                 return nil
  49         }
  50
  51         return c.authVerification(v, target, validators)
  52 }
  53
  54 func (c *Casper) authVerification(v *Verification, target *state.Checkpoint, validators map[string]*state.Validator) error {
  55         validator := validators[v.PubKey]
  56         if err := c.verifyVerification(v, validator.Order, true); err != nil {
  57                 return err
  58         }
  59
  60         checkpoints, err := c.addVerificationToCheckpoint(target, validators, v)
  61         if err != nil {
  62                 return err
  63         }
  64
  65         if err := c.store.SaveCheckpoints(checkpoints...); err != nil {
  66                 return err
  67         }
  68
  69         return c.saveVerificationToHeader(v, validator.Order)
  70 }
  71
  72 func (c *Casper) addVerificationToCheckpoint(target *state.Checkpoint, validators map[string]*state.Validator, verifications ...*Verification) ([]*state.Checkpoint, error) {
  73         _, oldBestHash := c.bestChain()
  74         var affectedCheckpoints []*state.Checkpoint
  75         for _, v := range verifications {
  76                 source, err := c.store.GetCheckpoint(&v.SourceHash)
  77                 if err != nil {
  78                         return nil, err
  79                 }
  80
  81                 supLink := target.AddVerification(v.SourceHash, v.SourceHeight, validators[v.PubKey].Order, v.Signature)
  82                 if target.Status != state.Unjustified || !supLink.IsMajority(len(validators)) || source.Status == state.Finalized {
  83                         continue
  84                 }
  85
  86                 if source.Status == state.Unjustified {
  87                         c.justifyingCheckpoints[source.Hash] = append(c.justifyingCheckpoints[source.Hash], target)
  88                         continue
  89                 }
  90
  91                 affectedCheckpoints = append(affectedCheckpoints, c.setJustified(source, target)...)
  92         }
  93
  94         _, newBestHash := c.bestChain()
  95         if oldBestHash != newBestHash {
  96                 c.rollbackNotifyCh <- nil
  97         }
  98
  99         return affectedCheckpoints, nil
 100 }
 101
 102 func (c *Casper) saveVerificationToHeader(v *Verification, validatorOrder int) error {
 103         blockHeader, err := c.store.GetBlockHeader(&v.TargetHash)
 104         if err != nil {
 105                 return err
 106         }
 107
 108         signature, err := hex.DecodeString(v.Signature)
 109         if err != nil {
 110                 return err
 111         }
 112
 113         blockHeader.SupLinks.AddSupLink(v.SourceHeight, v.SourceHash, signature, validatorOrder)
 114         return c.store.SaveBlockHeader(blockHeader)
 115 }
 116
 117 // source status is justified, and exist a super majority link from source to target
 118 func (c *Casper) setJustified(source, target *state.Checkpoint) []*state.Checkpoint {
 119         var affectedCheckpoint []*state.Checkpoint
 120         target.Status = state.Justified
 121         // must direct child
 122         if target.Parent.Hash == source.Hash {
 123                 c.setFinalized(source)
 124         }
 125
 126         for _, checkpoint := range c.justifyingCheckpoints[target.Hash] {
 127                 affectedCheckpoint = append(affectedCheckpoint, c.setJustified(target, checkpoint)...)
 128         }
 129
 130         delete(c.justifyingCheckpoints, target.Hash)
 131         affectedCheckpoint = append(affectedCheckpoint, source, target)
 132         return affectedCheckpoint
 133 }
 134
 135 func (c *Casper) setFinalized(checkpoint *state.Checkpoint) {
 136         checkpoint.Status = state.Finalized
 137         newRoot, err := c.tree.nodeByHash(checkpoint.Hash)
 138         if err != nil {
 139                 log.WithField("err", err).Panic("fail to set checkpoint finalized")
 140         }
 141
 142         c.tree = newRoot
 143 }
 144
 145 func (c *Casper) authVerificationLoop() {
 146         for blockHash := range c.newEpochCh {
 147                 validators, err := c.Validators(&blockHash)
 148                 if err != nil {
 149                         log.WithField("err", err).Error("get validators when auth verification")
 150                         continue
 151                 }
 152
 153                 for _, validator := range validators {
 154                         key := verificationCacheKey(blockHash, validator.PubKey)
 155                         verification, ok := c.verificationCache.Get(key)
 156                         if !ok {
 157                                 continue
 158                         }
 159
 160                         v := verification.(*Verification)
 161                         target, err := c.store.GetCheckpoint(&v.TargetHash)
 162                         if err != nil {
 163                                 log.WithField("err", err).Error("get target checkpoint")
 164                                 c.verificationCache.Remove(key)
 165                                 continue
 166                         }
 167
 168                         c.mu.Lock()
 169                         if err := c.authVerification(v, target, validators); err != nil {
 170                                 log.WithField("err", err).Error("auth verification in cache")
 171                         }
 172                         c.mu.Unlock()
 173
 174                         c.verificationCache.Remove(key)
 175                 }
 176         }
 177 }
 178
 179 func (c *Casper) verifyVerification(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 180         if err := c.verifySameHeight(v, validatorOrder, trackEvilValidator); err != nil {
 181                 return err
 182         }
 183
 184         return c.verifySpanHeight(v, validatorOrder, trackEvilValidator)
 185 }
 186
 187 // a validator must not publish two distinct votes for the same target height
 188 func (c *Casper) verifySameHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 189         checkpoints, err := c.store.GetCheckpointsByHeight(v.TargetHeight)
 190         if err != nil {
 191                 return err
 192         }
 193
 194         for _, checkpoint := range checkpoints {
 195                 for _, supLink := range checkpoint.SupLinks {
 196                         if supLink.Signatures[validatorOrder] != "" && checkpoint.Hash != v.TargetHash {
 197                                 if trackEvilValidator {
 198                                         c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 199                                 }
 200                                 return errSameHeightInVerification
 201                         }
 202                 }
 203         }
 204         return nil
 205 }
 206
 207 // a validator must not vote within the span of its other votes.
 208 func (c *Casper) verifySpanHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 209         if c.tree.findOnlyOne(func(checkpoint *state.Checkpoint) bool {
 210                 if checkpoint.Height == v.TargetHeight {
 211                         return false
 212                 }
 213
 214                 for _, supLink := range checkpoint.SupLinks {
 215                         if supLink.Signatures[validatorOrder] != "" {
 216                                 if (checkpoint.Height < v.TargetHeight && supLink.SourceHeight > v.SourceHeight) ||
 217                                         (checkpoint.Height > v.TargetHeight && supLink.SourceHeight < v.SourceHeight) {
 218                                         if trackEvilValidator {
 219                                                 c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 220                                         }
 221                                         return true
 222                                 }
 223                         }
 224                 }
 225                 return false
 226         }) != nil {
 227                 return errSpanHeightInVerification
 228         }
 229         return nil
 230 }
 231
 232 func makeVerification(supLink *state.SupLink, checkpoint *state.Checkpoint, pubKey string, validatorOrder int) *Verification {
 233         return &Verification{
 234                 SourceHash:   supLink.SourceHash,
 235                 TargetHash:   checkpoint.Hash,
 236                 SourceHeight: supLink.SourceHeight,
 237                 TargetHeight: checkpoint.Height,
 238                 Signature:    supLink.Signatures[validatorOrder],
 239                 PubKey:       pubKey,
 240         }
 241 }
 242
 243 func validate(v *Verification) error {
 244         if v.SourceHeight%state.BlocksOfEpoch != 0 || v.TargetHeight%state.BlocksOfEpoch != 0 {
 245                 return errVoteToGrowingCheckpoint
 246         }
 247
 248         if v.SourceHeight == v.TargetHeight {
 249                 return errVoteToSameCheckpoint
 250         }
 251
 252         return v.VerifySignature()
 253 }
 254
 255 func verificationCacheKey(blockHash bc.Hash, pubKey string) string {
 256         return fmt.Sprintf("%s:%s", blockHash.String(), pubKey)
 257 }