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         if err := c.addVerificationToCheckpoint(target, validators, v); err != nil {
  61                 return err
  62         }
  63
  64         return c.saveVerificationToHeader(v, validator.Order)
  65 }
  66
  67 func (c *Casper) addVerificationToCheckpoint(target *state.Checkpoint, validators map[string]*state.Validator, verifications ...*Verification) error {
  68         _, oldBestHash := c.bestChain()
  69         var affectedCheckpoints []*state.Checkpoint
  70         for _, v := range verifications {
  71                 source, err := c.store.GetCheckpoint(&v.SourceHash)
  72                 if err != nil {
  73                         return err
  74                 }
  75
  76                 supLink := target.AddVerification(v.SourceHash, v.SourceHeight, validators[v.PubKey].Order, v.Signature)
  77                 if target.Status != state.Unjustified || !supLink.IsMajority(len(validators)) || source.Status == state.Finalized {
  78                         continue
  79                 }
  80
  81                 if source.Status == state.Unjustified {
  82                         c.justifyingCheckpoints[source.Hash] = append(c.justifyingCheckpoints[source.Hash], target)
  83                         continue
  84                 }
  85
  86                 affectedCheckpoints = append(affectedCheckpoints, c.setJustified(source, target)...)
  87         }
  88
  89         _, newBestHash := c.bestChain()
  90         if oldBestHash != newBestHash {
  91                 c.rollbackNotifyCh <- nil
  92         }
  93
  94         return c.store.SaveCheckpoints(affectedCheckpoints...)
  95 }
  96
  97 func (c *Casper) saveVerificationToHeader(v *Verification, validatorOrder int) error {
  98         blockHeader, err := c.store.GetBlockHeader(&v.TargetHash)
  99         if err != nil {
 100                 return err
 101         }
 102
 103         signature, err := hex.DecodeString(v.Signature)
 104         if err != nil {
 105                 return err
 106         }
 107
 108         blockHeader.SupLinks.AddSupLink(v.SourceHeight, v.SourceHash, signature, validatorOrder)
 109         return c.store.SaveBlockHeader(blockHeader)
 110 }
 111
 112 // source status is justified, and exist a super majority link from source to target
 113 func (c *Casper) setJustified(source, target *state.Checkpoint) []*state.Checkpoint {
 114         var affectedCheckpoint []*state.Checkpoint
 115         target.Status = state.Justified
 116         // must direct child
 117         if target.Parent.Hash == source.Hash {
 118                 c.setFinalized(source)
 119         }
 120
 121         for _, checkpoint := range c.justifyingCheckpoints[target.Hash] {
 122                 affectedCheckpoint = append(affectedCheckpoint, c.setJustified(target, checkpoint)...)
 123         }
 124
 125         delete(c.justifyingCheckpoints, target.Hash)
 126         affectedCheckpoint = append(affectedCheckpoint, source, target)
 127         return affectedCheckpoint
 128 }
 129
 130 func (c *Casper) setFinalized(checkpoint *state.Checkpoint) {
 131         checkpoint.Status = state.Finalized
 132         newRoot, err := c.tree.nodeByHash(checkpoint.Hash)
 133         if err != nil {
 134                 log.WithField("err", err).Panic("fail to set checkpoint finalized")
 135         }
 136
 137         c.tree = newRoot
 138 }
 139
 140 func (c *Casper) authVerificationLoop() {
 141         for blockHash := range c.newEpochCh {
 142                 validators, err := c.Validators(&blockHash)
 143                 if err != nil {
 144                         log.WithField("err", err).Error("get validators when auth verification")
 145                         continue
 146                 }
 147
 148                 for _, validator := range validators {
 149                         key := verificationCacheKey(blockHash, validator.PubKey)
 150                         verification, ok := c.verificationCache.Get(key)
 151                         if !ok {
 152                                 continue
 153                         }
 154
 155                         v := verification.(*Verification)
 156                         target, err := c.store.GetCheckpoint(&v.TargetHash)
 157                         if err != nil {
 158                                 log.WithField("err", err).Error("get target checkpoint")
 159                                 c.verificationCache.Remove(key)
 160                                 continue
 161                         }
 162
 163                         c.mu.Lock()
 164                         if err := c.authVerification(v, target, validators); err != nil {
 165                                 log.WithField("err", err).Error("auth verification in cache")
 166                         }
 167                         c.mu.Unlock()
 168
 169                         c.verificationCache.Remove(key)
 170                 }
 171         }
 172 }
 173
 174 func (c *Casper) verifyVerification(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 175         if err := c.verifySameHeight(v, validatorOrder, trackEvilValidator); err != nil {
 176                 return err
 177         }
 178
 179         return c.verifySpanHeight(v, validatorOrder, trackEvilValidator)
 180 }
 181
 182 // a validator must not publish two distinct votes for the same target height
 183 func (c *Casper) verifySameHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 184         checkpoints, err := c.store.GetCheckpointsByHeight(v.TargetHeight)
 185         if err != nil {
 186                 return err
 187         }
 188
 189         for _, checkpoint := range checkpoints {
 190                 for _, supLink := range checkpoint.SupLinks {
 191                         if supLink.Signatures[validatorOrder] != "" && checkpoint.Hash != v.TargetHash {
 192                                 if trackEvilValidator {
 193                                         c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 194                                 }
 195                                 return errSameHeightInVerification
 196                         }
 197                 }
 198         }
 199         return nil
 200 }
 201
 202 // a validator must not vote within the span of its other votes.
 203 func (c *Casper) verifySpanHeight(v *Verification, validatorOrder int, trackEvilValidator bool) error {
 204         if c.tree.findOnlyOne(func(checkpoint *state.Checkpoint) bool {
 205                 if checkpoint.Height == v.TargetHeight {
 206                         return false
 207                 }
 208
 209                 for _, supLink := range checkpoint.SupLinks {
 210                         if supLink.Signatures[validatorOrder] != "" {
 211                                 if (checkpoint.Height < v.TargetHeight && supLink.SourceHeight > v.SourceHeight) ||
 212                                         (checkpoint.Height > v.TargetHeight && supLink.SourceHeight < v.SourceHeight) {
 213                                         if trackEvilValidator {
 214                                                 c.evilValidators[v.PubKey] = []*Verification{v, makeVerification(supLink, checkpoint, v.PubKey, validatorOrder)}
 215                                         }
 216                                         return true
 217                                 }
 218                         }
 219                 }
 220                 return false
 221         }) != nil {
 222                 return errSpanHeightInVerification
 223         }
 224         return nil
 225 }
 226
 227 func makeVerification(supLink *state.SupLink, checkpoint *state.Checkpoint, pubKey string, validatorOrder int) *Verification {
 228         return &Verification{
 229                 SourceHash:   supLink.SourceHash,
 230                 TargetHash:   checkpoint.Hash,
 231                 SourceHeight: supLink.SourceHeight,
 232                 TargetHeight: checkpoint.Height,
 233                 Signature:    supLink.Signatures[validatorOrder],
 234                 PubKey:       pubKey,
 235         }
 236 }
 237
 238 func validate(v *Verification) error {
 239         if v.SourceHeight%state.BlocksOfEpoch != 0 || v.TargetHeight%state.BlocksOfEpoch != 0 {
 240                 return errVoteToGrowingCheckpoint
 241         }
 242
 243         if v.SourceHeight == v.TargetHeight {
 244                 return errVoteToSameCheckpoint
 245         }
 246
 247         return v.VerifySignature()
 248 }
 249
 250 func verificationCacheKey(blockHash bc.Hash, pubKey string) string {
 251         return fmt.Sprintf("%s:%s", blockHash.String(), pubKey)
 252 }